Gravitation force (GF) values and repulsion force (RF) values are calculated for that instruction at every possible schedule point. Then the GF values and RF values are normalized to calculate the Balance Force (BF) values. The algorithm finds out the schedule point with the maximize BF value, and schedules the instruction to it.The selleck screening library process is repeated until all the instructions are successfully pre-scheduled. The details of this algorithm will be discussed in the following.4.1.1. Calculation of GF Value Gravitation force value GF(i, x, y) indicates the tightness of data dependence relation between Instruction i and Schedule-Point (x, y). The calculation of GF values only applies to the possible schedule point of Instruction i.There are three factors that will influence the GF value.

The number of data dependence relations from each cluster. For the purpose of minimizing the number of inter-cluster data communications, we would like instructions having data dependence relations to be placed in the same cluster. For example, when Instruction i is to be prescheduled, if there are three data dependence relations from Cluster A and only one data dependence relation from Cluster B, then, assigning Instruction i to Cluster A would be a better choice, because we only have one inter-cluster data communications.The span of the data dependence relations. If the number of active inter-cluster data communications exceeds the number of registers in the global register file, then some instructions must delay their write access to the global register file.

So, if an inter-cluster data communication is unavoidable, then we would like it to be a short one. For example, if both Instruction j from Cluster A and Instruction k from Cluster B have data dependence relations with Instruction i and Instruction j is scheduled two clock cycles before Instruction k, then when Instruction Anacetrapib i is to be prescheduled, it is preferred to pre-schedule Instruction i to Cluster A, because in that case, we will get a shorter inter-cluster data communications.The number of active inter-cluster data communications at Schedule-Point (x, y) of instructions from the neighborhood of Instruction i. the neighborhood of Instruction i, B(i) is defined as the set of instructions that have data dependence relations with Instruction i. And an active inter-cluster data communication from Instruction j means that (1) Instruction j is not in Cluster x (2) the inter-cluster data communication from Instruction j goes to Cluster x, and (3) the inter-cluster data communication is not finished at Cycle y. When calculating gravitation force, these three factors must all be taken into consideration.