Assembler system and method for a geometry accelerator

• US 5,889,997 A
• Filed: 05/30/1997
• Issued: 03/30/1999
• Est. Priority Date: 05/30/1997
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Strunk, Glenn W.
• Primary Examiner(s): Tramrnell, James P.
• Assistant Examiner(s): SMITH-STEWART, DEMETRA R
• Application Number:
  US08/866,574
• Time in Patent Office: 669 Days
• Field of Search: 395/706, 395/705, 395/561, 395/567, 395/571, 395/580, 395/581, 395/590, 395/595, 395/500, 395/583, 395/586, 345/433, 345/434, 345/418, 345/419, 345/501, 345/502, 345/503, 345/522
• US Class Current: 717/151
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

An assembler system enables efficient usage of space in a read only memory (ROM) that permits multiway instruction branching. Source code is analyzed and assembled by the assembler system and the assembler system then efficiently places the instructions in the ROM. The source code includes at least the following elements or an equivalent counterpart thereof: next state statements, nonaligned instructions, align statements, and aligned instructions. Next state statements serve as a flag to separate the various instructions. Nonaligned instructions are defined as those instructions that are nonaddressable by other instructions, i.e., those instructions that are not branched to. Align statements serve as a flag to the assembler system that a plurality k (where k is equal to 2ⁿ and where n is a positive integer) of aligned instructions directly follow in succession. Furthermore, aligned instructions are defined as those that are addressable by a plurality of other instructions, i.e., those instructions that can be branched to by a branch instruction. A branch instruction can be a nonaligned or an aligned instruction. The assembler system is configured to store the nonaligned instructions in the ROM in succession starting with a lowest memory location and moving to higher memory locations. Moreover, the assembler system is configured to store aligned instructions in the ROM in sets of k instructions starting with a highest memory location and moving toward lower memory locations, a lowest location of each set of the ROM being a mathematical multiple of k.

Claims

1. An assembler method for enabling efficient usage of space in a read only memory (ROM) that permits multiway branching, comprising the steps of:

providing source code having nonaligned and aligned instructions, each of the nonaligned instruction being nonaddressable by other instructions, each of the aligned instructions being addressable by a plurality of other instructions,

storing the nonaligned instructions in the ROM, starting with a lowest memory location and moving to higher memory locations; and

storing the aligned instructions in the ROM, starting with a highest memory location and moving to lower memory locations.

2. The method of claim 1, further comprising the steps of:

providing the source code with an align statement, the align statement associated with a number k of aligned instructions and indicating the number k, where k is equal to 2ⁿ and where n is a positive integer; and

based upon the align statement, storing the number k of aligned instructions within a highest set of available contiguous locations of the ROM that has a lowest location that is a mathematical multiple of k.

3. The method of claim 1, further comprising the step of:

storing sets of k aligned instructions within corresponding sets of contiguous locations of the ROM, where k is equal to 2ⁿ and where n is a positive integer and a first location of each corresponding set being a mathematical multiple of k; and

enabling branching to an aligned instruction of one of the corresponding sets by providing logic that is external to the ROM and that is configured to define at least one least significant bit of a next address associated with a branch instruction.

4. The method of claim 1, further comprising the steps of:

implementing a plurality of control units of a geometry accelerator in the ROM via the instructions;

storing sets of k aligned instructions within corresponding sets of contiguous locations of the ROM, a first location of each set being a mathematical multiple of k;

implementing a stack of a plurality of processing elements;

executing the instructions with the processing elements in order to modify image data of the geometry accelerator; and

after execution of a branch instruction, enabling branching to an aligned instruction of one of the sets by defining at least one least significant bit of a next address associated with the branch instruction via logic that is external to the ROM.

5. The method of claim 1, further comprising the steps of:

providing the source code with a plurality of align statements, each align statement associated with a number k of aligned instructions and indicating said number k, where k is equal to 2ⁿ and where n is a positive integer;

based upon a first align statement, storing a first number k1 of aligned instructions within a highest set of available contiguous locations of the ROM that has a lowest location that is a mathematical multiple of k1; and

based upon a second align statement, storing a second number k2 of aligned instructions within another highest set of available contiguous locations of the ROM that has another lowest location that is a mathematical multiple of k2.

6. The method of claim 1, further comprising the steps of:

providing the source code with a plurality of align statements, each align statement associated with a number k of aligned instructions and indicating said number k, where k is equal to 2ⁿ and where n is a positive integer;

based upon a first align statement, storing a first number k1 of aligned instructions within a highest set of available contiguous locations of the ROM that has a lowest location that is a mathematical multiple of k1; and

based upon a second align statement, storing a second number k2, which is different than the first number, of aligned instructions within another highest set of k1 available contiguous locations of the ROM that has another lowest location that is a mathematical multiple of k1.

7. An assembler configured to implement the steps of claim 1 and store the instructions within a geometry accelerator for a computer graphics system that has the ROM.

8. An assembler method for enabling efficient usage of space in a read only memory (ROM) that permits multiway branching, comprising the steps of:

providing source code having code fragments that include nonaligned, align, and aligned instructions, the nonaligned instruction being nonaddressable by other instructions, the align statements indicating a following set of k aligned instructions, where k is equal to 2ⁿ and where n is a positive integer, the aligned instructions being addressable by a plurality of other instructions;

analyzing the code fragments in succession and storing the nonaligned and aligned instructions in the ROM by;

storing any of the nonaligned instructions in the ROM, in succession starting with a lowest memory location and moving toward higher memory locations; and

storing any of the aligned instructions in the ROM, starting with a highest memory location and moving to lower memory locations, by storing sets of k instructions associated with each of the align statement within sets of k contiguous locations of the ROM, a first location of each set of the ROM being a highest memory location, at a time of analysis of the align statement, that is a mathematical multiple of k.

9. The method of claim 8, further comprising the step of storing the instructions of the source code within a ROM of a geometry accelerator for a computer graphics system.

10. The method of claim 8, further comprising the steps of

based upon a first align statement, storing a first number k1 of aligned instructions within a highest set of available contiguous locations of the ROM that has a lowest location that is a mathematical multiple of k1;

and

based upon a second align statement, storing a second number k2, which is different than the first number, of aligned instructions within another highest set of available contiguous locations of the ROM that has another lowest location that is a mathematical multiple of k2.

11. The method of claim 8, further comprising the steps of:

based upon a first align statement, storing a first number k1 of aligned instructions within a highest set of available contiguous locations of the ROM that has a lowest location that is a mathematical multiple of k1; and

based upon a second align statement, storing a second number k2, which is different than the first number, of aligned instructions within another highest set of k1 available contiguous locations of the ROM that has another lowest location that is a mathematical multiple of k1.

12. An assembler system for enabling efficient usage of space in a read only memory (ROM) that permits multiway branching, the system comprising logic configured to analyze instructions of source code and store the instructions in the ROM, the instructions including nonaligned and aligned instructions, each of the nonaligned instructions being nonaddressable by other instructions, each of the aligned instructions being addressable by a plurality of other instructions, the logic configured to store the nonaligned instructions in the ROM, starting with a lowest memory location and moving to higher memory locations, and the logic configured to store the aligned instructions in the ROM, starting with a highest memory location and moving to lower memory locations.

13. The system of claim 12, further comprising source code with an align statement, the align statement associated with a number k of aligned instructions and indicating the number k, where k is equal to 2ⁿ and where n is a positive integer;

and wherein the logic is configured to store, based upon the align statement, the number k of aligned instructions within highest contiguous locations of the ROM having a lowest location that is a mathematical multiple of k.

14. The system of claim 12, wherein the logic is configured to store sets of aligned instructions in the ROM that have a different number of the aligned instructions.

15. A geometry accelerator, comprising:

a stack of a plurality of processing elements;

a plurality of control units implemented in a read-only memory (ROM) via instructions, each of the control units configured to drive a processing element in order to modify image data;

a next address associated with each of the instructions and defining a location in the ROM of a next instruction to be executed;

nonaligned and aligned instructions situated in the ROM, each of the nonaligned instructions being nonaddressable by other instructions, each of the aligned instructions being addressable by a plurality of other instructions, the nonaligned instructions being stored in the ROM in succession starting with a lowest memory location and moving to higher memory locations, and the aligned instructions being stored in the ROM in sets of locations starting with a highest memory location and moving toward lower memory locations; and

branch logic configured to define the next address for a currently executing instruction associated with a corresponding ROM-based control unit.

16. The accelerator of claim 15, wherein the aligned instructions are stored in the ROM in sets of k, where k is equal to 2ⁿ and where n is a positive integer, and wherein each set of k aligned instructions begins with a memory address that is a mathematical multiple of k.

17. The accelerator of claim 16, wherein the ROM further comprises different sets of the aligned instructions having different numbers of the aligned instructions.