Method for instruction pipelining on irregular register files

1. A method of pipelining instructions of a target program executed at a target computer architecture having a first cluster and a second cluster, each cluster comprising a first functional unit, a second functional unit, a first local register file connected to the first functional unit, a second local register file connected to the second functional unit, and a global register file having a ping-pong structure formed by a first register bank and a second register bank, the method comprising steps of:

(a) determining a minimum initial interval (MII);

(b) grouping the instructions which are performed on the same functional unit based on a data dependency graph and a modulo reservation table (MRT) so that the operands of dependent instructions are assigned to the same local register file;

(c) assigning the virtual registers of the instructions that have data dependency across the first functional unit and the second functional unit to the global register file;

(d) modulo scheduling the instructions based on a current value of initial interval (II), increasing the II and repeating steps (a), (b) and (c) if no valid schedule for the current II is found;

(e) allocating the virtual registers of the scheduled instructions into the corresponding register files;

(f) transferring a set of virtual registers from the first or second register file to the global register file if step (e) fails on a first iteration; and

(g) repeating step (e) and increasing the current II if step (e) fails again;

wherein the step (f) further comprises steps of:

collecting a set of transferable virtual registers, wherein the transferable virtual registers are the operands used and defined by the same functional unit and assigned to a same bank;

constructing a transparent register transformation (TRT) table, wherein the TRT table records the transferable virtual registers and the corresponding scores;

transferring a transferable virtual register having the highest score in the TRT table from the first local register to the global register if the capacity of the first local register is zero; and

transferring a transferable virtual register having the highest score in the TRT table from the second local register to the global register if the capacity of the second local register is zero.

2. The method of claim 1 , wherein step (a) comprises the steps of:

determining a resource bound (ResMII) according to a total resource requirement of the target program;

determining a recurrence count (RecMII) according to the data dependency graph; and

selecting the larger of the RecMII and the RecMII as the MII.

3. The method of claim 1 , wherein step (b) comprises steps of:

(b1) obtaining the data dependency graph and the MRT;

(b2) selecting one functional unit, determining a longest path with the selected functional unit, and grouping the longest path by unifying the labels of selected vertexes;

(b3) selecting another functional unit, determining a longest path with the selected functional unit among all the un-grouped vertexes and grouping the longest path by unifying the labels of the selected vertexes; and

(b4) repeating steps (b2) and (b3) until each vertex of the data dependency graph is selected.

4. The method of claim 1 , wherein step (e) comprises steps of:

constructing the capacity of the first and second local register files;

decreasing the capacity of the first local register files by 1 when a virtual register is allocated in the first local register file; and

decreasing the capacity of the second local register file by 1 when a virtual register is allocated in the second local register.

5. The method of claim 1 , wherein the score of each transferable virtual register is calculated by:

increasing the score by 4 if the capacity of the first or second local register file is increased by 1 after transferring the virtual register from the first or second local register file to the global register file;

increasing the score by 2 if the capacity of the global register file is not increased after transferring the virtual register from the first or second local register file to the global register file; and

increasing the score by a fraction according to the reusability of the virtual register, wherein the fraction is a normalized figure considering all the reusability of the virtual registers in the TRT table.

6. The method of claim 1 , wherein the first functional unit is a load/store unit.

7. The method of claim 1 , wherein the second functional unit is an arithmetic unit.

8. A non-transitory computer readable medium having computer readable program code embedded in the medium for scheduling multiple groups of instructions in a computer program for execution on a processor, said processor comprising a first functional unit, a second functional unit, a first local register file connected to the first functional unit, a second local register file connected to the second functional unit, and a global register file having a ping-pong structure formed by a first register bank and a second register bank, the computer readable program code including:

(a) code for determining a minimum initial interval (MII);

(b) code for grouping the instructions by associated functional units based on a data dependency graph and a modulo reservation table (MRT) so that the operands of dependent instructions are assigned to the same local register file;

(c) code for assigning the virtual registers of the instructions that have data dependency across the first functional unit and the second functional unit to the global register file;

(d) code for modulo scheduling the instructions based on a current value of II, increasing the II and repeating codes (a), (b) and (c) if no valid schedule for the current II is found;

(e) code for allocating the virtual registers of the scheduled instructions into the corresponding register files;

(f) code for transferring a set of virtual registers from the first or second register file to the global register file and allocating the virtual registers of the scheduled instructions into the corresponding register files if allocating the virtual register fails on the first iteration; and

(g) code for increasing the II and modulo scheduling the instructions if the allocation operand fails again;

wherein the code in (f) further comprises of:

code for collecting a set of transferable virtual registers, wherein the transferable virtual registers are the operands used and defined by the same functional unit and assigned to a same bank:

code for constructing a transparent register transformation (TRT) table, wherein the TRT table records the transferable virtual registers and the corresponding scores;

code for transferring a transferable virtual register having the highest score in the TRT table from the first local register to the global register if the capacity of the first local register is zero; and

code for transferring a transferable virtual register having the highest score in the TRT table from the second local register to the global register if the capacity of the second local register is zero.