Patent ID: 8200944
Filing Date: 2012-06-12
Classification: G06F

Abstract:
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.