Macroscalar Processor Architecture

• US 20100122069A1
• Filed: 11/06/2009
• Published: 05/13/2010
• Est. Priority Date: 04/23/2004
• Status: Active Grant

• Current Assignee: Jeffry E. Gonion
• Original Assignee: Jeffry E. Gonion
• Inventors: Gonion, Jeffry E.
• Granted Patent: US 8,065,502 B2
• Time in Patent Office: Days
• US Class Current: 712/216
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A macroscalar processor architecture is described herein. In one embodiment, a processor receives instructions of a program loop having a vector block and a sequence block intended to be executed after the vector block, where the processor includes multiple slices and each of the slices is capable of executing an instruction of an iteration of the program loop substantially in parallel. For each iteration of the program loop, the processor executes an instruction of the sequence block using one of the slices while executing instructions of the vector block using a remainder of the slices substantially in parallel. Other methods and apparatuses are also described.

Claims

1. A method for aggregating a program loop, the method comprising:

receiving by the processor instructions of a program loop having a vector block and a sequence block intended to be executed after the vector block, wherein the processor includes a plurality of slices and each of the slices is capable of executing an instruction of an iteration of the program loop substantially in parallel; and

for each iteration of the program loop, executing an instruction of the sequence block using one of the slices while executing instructions of the vector block using a remainder of the slices substantially in parallel.

2. The method of claim 1, further comprising determining whether any instruction of the sequence block depends on a result of the vector block, wherein an execution of the sequence block in parallel with the vector block is performed if no instruction of the sequence block depends on the result of the vector block.

3. The method of claim 1, wherein the vector block includes a first and second instructions, wherein the sequence block includes a third and fourth instructions intended to be executed after the first and second instructions, and wherein the method further comprises:

executing the third instruction of the sequence block using a first slice of the processor while executing a second instruction of the vector block using a second slice of the processor substantially in parallel during a first iteration of the program loop; and

executing the first instruction of the vector block using the first slice of the processor while executing a fourth instruction of the sequence block using the second slice of the processor substantially in parallel during a second iteration of the program loop.

4. The method of claim 3, wherein the fourth instruction depends on a result of the third instruction of the sequence block, and wherein the second iteration is performed after the first iteration.

5. A method for aggregating a program loop, the method comprising:

determining whether a number of dynamic registers of a processor to be used in a program loop exceeds a predetermined threshold, the processor including a plurality of static registers, dynamic registers, and extended registers; and

allocating one or more of the extended registers to be used in the program loop in place of at least a portion of the determined number of dynamic registers intended to be used in the program loop, such that a number of dynamic registers used in aggregating the program loop does not exceed the predetermined threshold.

6. The method of claim 5, wherein determining whether a number of dynamic registers of a processor to be used is performed by a compiler in view of source code of the program loop, and wherein the compiler inserts one or more directives into machine executable code based on the source code to indicate one or more extended registers to be used in place of one or more dynamic registers by the processor at runtime.

7. The method of claim 6, wherein the one or more directives specify an offset from which at least a portion of the dynamic registers to be used is shifted, and wherein the shifted portion of the dynamic registers are replaced with the allocated one or more extended registers by the processor at runtime.

8. The method of claim 7, wherein the one or more directives further specify a number of the dynamic registers to be shifted with the specified offset to where the one or more extended registers allocated to replace the shifted dynamic registers.

9. The method of claim 8, wherein the one or more directives further specify a starting location of the dynamic registers from which the number of the dynamic registers is to be shifted.

10. A method for aggregating a program loop, the method comprising:

identifying a static register of a processor to be accessed by an instruction of an iteration of a program loop, wherein a value of the static register is used in a subsequent iteration; and

in response to the instruction executed by the processor, copying the value of the static register to a dynamic register of the processor, the dynamic register being used in the subsequent iteration of the program loop, wherein copying the value of the static register is performed without additional instructions from source code corresponding to the instruction of the iteration received by the processor.

11. The method of claim 10, wherein the static register accessed by the instruction includes a write operation to the static register by the instruction.

12. The method of claim 10, wherein the static register accessed by the instruction includes a read operation from the static register by the instruction.

13. The method of claim 10, further comprising specifying the static register from which the value is copied and the dynamic register to which the value is copied.

14. The method of claim 13, further comprising inserting by a compiler one or more directives prior to the instruction of the program loop to specify the static and dynamic registers.

15. A method for aggregating a program loop, the method comprising:

identifying instructions of a sequence block of a program loop, the sequence block including a first conditional branch code and a second conditional branch code dependent upon a predicate condition, wherein the first conditional branch code is longer than the second conditional branch code; and

modifying the instructions such that when instructions of the second branch code that satisfy the predicate condition have been executed during a current iteration, execution of a next iteration starts without examining a remainder of the first branch code that has not been executed in the current iteration.

16. The method of claim 15, wherein the first conditional branch code is executed when the predicate condition is in a first state, wherein the second conditional branch code is executed when the predicate condition is in a second state, and wherein a remainder of the current iteration is skipped when the second branch code has been executed and the predicate condition is in the second state.

17. The method of claim 15, wherein modifying the instructions is performed by a compiler, and wherein the compiler inserts one or more directives to indicate skipping the current iteration when the second branch code has been executed.

18. A method for aggregating a program loop, the method comprising:

receiving a first instruction to determine a first predicate based on a conditional test and a second instruction to conditionally set a second predicate based on a condition of the first predicate; and

converting the first and second instructions into a single instruction, which when executed by a processor, sets the second predicate based on the conditional test only if a result of the conditional test satisfies a predetermined criteria, wherein the single instruction is executed by the processor without using a register to store the condition of the first predicate.

19. The method of claim 18, wherein the first and second instructions are received from source code, and identified and converted by a compiler.

20. The method of claim 19, wherein the compiler inserts one or more directives prior to the single instruction to specify the predetermined criteria, which when satisfied by the result of the conditional test, assigns the result of the conditional test to the second predicate.

21. The method of claim 18, wherein the predetermined criteria is one of a true state and a false state.

22. A method for aggregating a program loop, the method comprising:

identifying instructions of a program loop including a first set of one or more instructions to be executed when a predicate condition is satisfied and a second set of one or more instructions to be executed when the predicate condition is not satisfied;

executing the first set of the instructions as a first vector block for one or more consecutive iterations during which the predicate condition is satisfied; and

executing the second set of the instructions as a second vector block for one or more consecutive iterations during which the predicate condition is not satisfied.

23. The method of claim 22, further comprising maintaining at runtime a value to indicate that the predicate condition is satisfied, wherein each bit of the value corresponds to an iteration respectively, and wherein a number of consecutive bits having a predetermined logical value determines the number of iterations for vector block execution.

24. The method of claim 23, wherein identifying the instructions is performed by a compiler, wherein the compiler inserts one or more directives to indicate that an aggregation factor for the first and second vector blocks should be calculated at runtime if a state of the predicate condition changes.

25. A method for aggregating a program loop, the method comprising:

identifying one or more instructions of a program loop dependent upon a predicate condition based on a first variable of a previous iteration and a second variable of a current iteration;

for all iterations of the program loop, recursively shifting a value of a static register associated with the first variable to an extended register associated with the static register of the first variable for a current iteration and substantially simultaneously shifting a value of a dynamic register associated with the second variable for the current iteration to an extended register associated with the dynamic register of the second variable for a next iteration; and

executing the one or more instructions of the program loop as a vector block using the shifted extended registers for the first and second variables.

26. The method of claim 25, wherein recursively shifting further comprises shifting a value of a dynamic register associated with the second variable for the last iteration of the program loop to the static register associated with the second variable.

27. The method of claim 25, wherein identifying the one or more instructions is performed by a compiler, wherein the compiler inserts one or more directives to specify a static register and a dynamic register being shifted through.

28. A method for aggregating a program loop, the method comprising:

identifying one or more instructions of a program loop having a branch instruction that causes the program loop to branch dependent upon a predicate condition after a memory write operation; and

modifying at least one of the one or more instructions to cause a processor for executing the one or more instructions to branch after the memory write operation executed as a vector block for iterations prior to and including an iteration during which the predicate condition is satisfied.

29. The method of claim 28, further comprising inserting one or more directives in source code containing the one or more instructions to cause the processor to branch after the memory write operation is executed as a vector block for a current iteration.

30. The method of claim 29, wherein identifying one or more instructions, modifying at least one of the one or more instructions, and inserting one or more directives operations are performed by a compiler based on the source code.

31. A method for aggregating a program loop, the method comprising:

identifying one or more instructions of a program loop having a first loop having a first set of instructions including a second loop, the second loop having a second set of instructions to be executed as a sequence block; and

modifying at least one of the instructions such that for each iteration of executing the second set of instructions of the second loop, executing the first set of instructions of the first loop as a vector block for all iterations of the program loop.

32. The method of claim 31, further comprising:

maintaining a predicate flag to indicate whether iterations of the second loop have been completed; and

repeating executing the first set of instructions of the first loop based on the predicate flag until all iterations of the second loop are completed.

33. The method of claim 32, wherein the predicate flag includes a plurality of bits, each bit corresponding to an iteration of the second loop.

34. The method of claim 33, further comprising setting a bit of the predicate flag to a predetermined logical value if an associated iteration of the second loop is completed, wherein repeating executing the first set of instructions of the first loop is performed if any bit of the predicate flag is not set to the predetermined logical value.

35. The method of claim 31, wherein identifying one or more instructions and modify at least one of the instructions are performed by a compiler based on source code containing the one or more instructions of the program loop.

36. A method for aggregating a program loop, comprising:

identifying one or more instructions of a program loop, wherein during each iteration of the program loop, a member of a first array referenced by a first index is assigned to a member of a second array referenced by a second index dependent upon a predicate condition;

for each iteration of the program loop, at runtime by a processor, incrementally assigning a value to a dynamic register associated with the respective iteration only if the predicate condition is satisfied during the respective iteration; and

executing the one or more instructions as a vector block that assign a member of the first array to a member of the second array referenced by the dynamic register associated with each iteration.

37. The method of claim 36, further comprising:

counting a number of active iterations of the program loop, wherein an iteration is an active iteration if the predicate condition is satisfied during the respective iteration; and

storing the counted number of active iterations into a static register associated with second index after the vector block execution.

38. The method of claim 36, wherein identifying the one or more instructions is performed by a compiler and wherein the compiler inserts one or more directives to specify a dynamic register associated with an iteration to be incrementally assigned based on a base value and an increment amount specified within the one or more directives.

39. The method of claim 38, wherein the base value is determined based on a value of a static register associated with the second index prior to the vector block execution.

40. A method for aggregating a program loop, the method comprising:

identifying at runtime one or more instructions of a program loop, the one or more instructions being executed depending on one or more predicate conditions; and

dispatching one of the instructions to one or more functional units of a processor if the one or more predicate conditions are satisfied while a remainder of the instructions is not dispatched.

41. The method of claim 40, wherein evaluating the one or more predicate conditions and dispatching are performed by one or more iteration units of the processor, wherein an instruction is dispatched if it corresponds to a type of the iteration unit.

42. The method of claim 40, further comprising executing the dispatched instruction using an execution unit of the processor.

43. A machine implemented method, comprising:

receiving a data stream of a program executed within a processor, the data stream including a plurality of virtual memory pages each having virtual memory addresses and identified by a virtual memory page number; and

for each virtual memory page, transmitting physical addresses corresponding to the virtual memory addresses and the virtual memory page number associated with respective virtual memory page to a controller to enable the controller to prefetch at least a portion of a remainder of the corresponding physical memory page based on a physical address and the virtual memory page number of the corresponding physical memory page.

44. The method of claim 43, further comprising for each virtual memory page of the data stream, translating at least a portion of the virtual memory addresses of the respective virtual memory page into at least a portion of the physical addresses.

45. The method of claim 43, wherein the controller is capable of prefetching the remainder of the corresponding physical memory without having to examine characteristics of multiple physical addresses in order to determine whether remaining addresses belong to an identical physical memory page, based on a relationship between the physical address and the virtual memory page number of the physical memory page.

46. The method of claim 43, wherein the physical address of the respective physical memory page is a starting physical address of the respective physical memory page.

47. A machine implemented method, comprising:

in response to a data stream of a program executed within a processor, the data stream including a plurality of physical memory pages each having physical memory addresses and each of the physical memory pages corresponding to a virtual memory page identified by a virtual memory page identifier, for each physical page, determining whether a predetermined physical address of a respective physical page is associated with a predetermined virtual memory page identifier; and

prefetching at least a portion of a remainder of the respective physical page if the predetermined physical address of the respective physical page is associated with the predetermined virtual memory page identifier.

48. The method of claim 47, wherein the prefetching is performed without having to examining multiple physical addresses of the respective physical memory page in order to determine whether the multiple physical addresses belong to an identical physical memory page.

49. The method of claim 47, wherein the predetermined physical address is a starting address of the respective physical memory page.

50. The method of claim 47, wherein the predetermined virtual memory page identifier is a next virtual memory page number.

51. The method of claim 50, wherein determining is performed at an end of a physical memory page corresponding to a previous virtual memory page with respect to the next virtual memory page number.

52. An apparatus for aggregating a program loop, the apparatus comprising:

means for receiving by the processor instructions of a program loop having a vector block and a sequence block intended to be executed after the vector block, wherein the processor includes a plurality of slices and each of the slices is capable of executing an instruction of an iteration of the program loop substantially in parallel; and

for each iteration of the program loop, means for executing an instruction of the sequence block using one of the slices while executing instructions of the vector block using a remainder of the slices substantially in parallel.

53. An apparatus for aggregating a program loop, the apparatus comprising:

means for identifying a static register of a processor to be accessed by an instruction of an iteration of a program loop, wherein a value of the static register is used in a subsequent iteration; and

in response to the instruction executed by the processor, means for copying the value of the static register to a dynamic register of the processor, the dynamic register being used in the subsequent iteration of the program loop, wherein copying the value of the static register is performed without additional instructions from source code corresponding to the instruction of the iteration received by the processor.

54. An apparatus for aggregating a program loop, the apparatus comprising:

means for identifying instructions of a program loop including a first set of one or more instructions to be executed when a predicate condition is satisfied and a second set of one or more instructions to be executed when the predicate condition is not satisfied;

means for executing the first set of the instructions as a first vector block for one or more consecutive iterations during which the predicate condition is satisfied; and

means for executing the second set of the instructions as a second vector block for one or more consecutive iterations during which the predicate condition is not satisfied.