Register scoreboarding to support overlapped execution of vector memory reference instructions in a vector processor

• US 6,266,759 B1
• Filed: 12/14/1998
• Issued: 07/24/2001
• Est. Priority Date: 12/14/1998
• Status: Expired due to Fees

• Current Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Birrittella, Mark S.
• Primary Examiner(s): Ellis, Richard L.
• Application Number:
  US09/211,118
• Time in Patent Office: 953 Days
• Field of Search: 712/3, 712/4, 712/5, 712/6, 712/7, 712/208, 712/216, 712/200, 712/215, 712/209, 712/218, 712/217, 711/207, 711/208, 711/128, 711/209
• US Class Current: 712/5
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory

Abstract

A vector-processor SIMD RISC computer system uses virtual addressing and overlapped instruction execution. Indicators for each of the architected registers assume different states when an instruction, overlapped with a vector memory-reference instruction, has or has not read from or written to a particular register. Multiple overlapped vector memory-reference instructions are assigned separate sets of indicators. Indicators in a certain state prevents a subsequent overlapped instruction from writing to its associated register.

Claims

1. A method of overlapping the execution of multiple instructions in a virtual-address vector computer having architectural registers holding multiple vector elements, and a control unit for reading and writing said vector elements in said registers in accordance with a sequence of instructions, the method comprising:

executing a plurality of the instructions overlapped in time with each other, at least one of the instructions being a vector memory reference instruction (VMRI);

repeating the following operations for each of the overlapped instructions;

If the instruction is a VMRI, assigning a column of indicators to the VMRI, the indicators in the column corresponding to respective ones of the registers and setting all of the indicators in the column to an “

unused”

state;

identifying one of the registers as a source register for the overlapped instructions;

if the indicator corresponding to the source register is in the “

unused”

state, setting said indicator corresponding to the source register to a “

live”

state;

identifying one of the registers as a target register for the overlapped instruction;

if the indicator corresponding to the target register is in the “

unused”

state, setting said indicator corresponding to the target register to a “

dead”

state;

if the indicator corresponding to the target register is in the “

live”

state, stalling the overlapped instructions.

2. The method of claim 1, further comprising:

detecting completion of the VMRI;

setting the indicators in the column to the “

unused”

state.

3. The method of claim 2, wherein the completion of the VMRI is a successful completion.

4. The method of claim 3, further comprising freeing the column for use by a subsequent VMRI in the sequence of instructions.

5. The method of claim 2, wherein the completion of the VMRI denotes a page fault.

6. The method of claim 5, further comprising rolling back the overlapped instructions.

7. The method of claim 1, further comprising reading the contents of the source register.

8. The method of claim 1, further comprising writing to the target register if the indicator corresponding to the target register is not in the “

live”

state.

9. A method of overlapping the execution of multiple instructions in a virtual-address vector computer having architectural registers holding multiple vector elements, and a control unit for reading and writing said vector elements in said registers in accordance with a sequence of instructions, the method comprising:

executing a plurality of the instructions overlapped in time with each other, a plurality of the overlapped instructions being vector memory reference instructions (VMRIs);

repeating, for each of the overlapped instructions,

identifying one of the registers as a source register for overlapped instruction;

if any of the indicators in the row corresponding to the source register is in the “

unused”

state, setting the indicator in the row corresponding to the source register and in the column corresponding to a current one of the instructions to a “

live”

state;

identifying one of the registers as a target register for the overlapped instruction;

if any of the indicators in the row corresponding to the target register is in the “

unused”

state, setting the indicator in the row corresponding to the target register and in the column corresponding to the current one of the instructions to a “

dead”

state;

if any of the indicators corresponding to the target register in the “

live”

state, stalling the overlapped instructions.

10. The method of claim 9, further comprising identifying those of the columns assigned to any of the VMRIs.

11. The method of claim 10, wherein the overlapped instructions are stalled only if the indicators in the “

live”

state are located in any of the identical columns.

12. The method of claim 10, further comprising reading the contents of the source register.

13. The method of claim 10, further comprising writing to the target register if none of the indicators in the row corresponding to the target register and in any of the identified columns is in the “

live”

state.

14. The method of claim 9, further comprising:

detecting completion of one of the VMRIs;

setting the indicators in the column assigned to the completed VMRI to the “

unused”

state.

15. The method of claim 14, further comprising freeing the column assigned to the completed VMRI.

16. The method of claim 15, further comprising reassigning the freed column to another of the plurality of VMRIs.

17. The method of claim 14, further comprising rolling back the overlapped instructions.

18. A vector computer for executing overlapped instructions including vector memory-reference instructions (VMRIs) containing virtual addresses representing multi-element vectors, the computer comprising:

a memory subsystem for translating the virtual addresses to and from real addresses in response to the VMRIs;

a set of architectural registers coupled to the memory subsystem;

a matrix of indicators in a plurality of rows each corresponding to one of said registers and in at least one column associated with one of the VMRIs, each of the indicators being capable of assuming any of at least three different states, including

an “

unused”

state indicating that its corresponding register has been neither written nor read during execution of one of the overlapped instructions,

a “

dead”

state indicating that its corresponding register has been written during execution of one of the overlapped instructions,

a “

live”

state indicating that its corresponding register has been read during execution of one of the overlapped instructions;

a control unit coupled to said registers and to said memory unit for reading and writing particular ones of the registers in response to the overlapped instructions, and for stalling executing of the overlapped instructions when both

one of the overlapped instructions requests writing one of the registers, and

one of the indicators associated with said one register is in the “

live”

state.

19. The computer of claim 18 wherein the matrix of indicators includes a plurality of columns, and wherein the control unit includes issue logic for assigning different ones of the columns to different ones of the VMRIs.

20. The computer of claim 19, wherein the number of columns in the matrix is determined by the number of VMRIs capable of overlapping each other.

21. The computer of claim 19, wherein the control unit includes issue logic for clearing the indicators of one of the columns in response to the completion of one of the VMRIs.

22. The computer of claim 19, wherein the control unit includes issue logic for freeing the indicators of one of the columns in response to the completion of one of the VMRIs.

23. The computer of claim 18, wherein the memory subsystem comprises:

a memory unit for storing data at the real addresses; and

a load/store unit for translating between the real addresses and the virtual addresses.

24. The computer of claim 23, wherein the data includes elements of multi-element vectors.

25. The computer of claim 23 wherein the memory subsystem further comprises a translation buffer coupled between said memory unit and said load/store unit.

26. The computer of claim 23, further comprising a vector processing unit having a vector function unit coupled to the registers.

27. The computer of claim 26, further comprising a scalar processing unit coupled to said vector processing unit and to said load/store unit.

28. A vector computer for executing overlapped instructions including vector memory-reference instructions (VMRIs) containing virtual addresses representing multi-element vectors, the computer comprising:

memory means for translating the virtual addresses to and from real addresses in response to the VMRIs;

a set of register means coupled to the memory means;

a matrix of indicator means in a plurality of rows each corresponding to one of said register means and in a plurality of columns each associated with a different one of the VMRIs, each of the indicator means being capable of assuming any of at least three different states, including

an “

unused”

state indicating that its corresponding register means has been neither written nor read during execution of one of the overlapped instructions,

a “

dead”

state indicating that its corresponding register means has been written during execution of one of the overlapped instructions,

a “

live”

state indicating that its corresponding register means has been read during execution of one of the overlapped instructions;

control means coupled to said register means and to said memory means for reading and writing particular ones of the register means in response to the overlapped instructions, and for stalling executing of the overlapped instructions when both

one of the overlapped instructions requests writing one of the register means, and

one of the indicator means associated with said one register means is in the “

live”

state.

29. The computer of claim 28, wherein the control unit includes issue logic for clearing the indicators of one of the columns in response to the completion of its associated VMRI.

30. The computer of claim 29, wherein the completion of the associated VMRI occurs in response to a page fault in translating the virtual addresses to or from the real addresses.