Assembler System and Method for a Geometry Accelerator

The present invention generally relates to computer graphics systems and, in particular, to an assembler system and method for permitting efficient use of space in a read-only memory (ROM) in, for example, a geometry accelerator that permits multiway logic branching.

Computer graphics systems are commonly used for displaying graphical representations of objects on a two-dimensional display. Current computer graphics systems provide highly detailed visual representations of objects and are used in a variety of applications.

A typical computer that employs a computer graphics system is shown in FIG. 1. Referring to FIG. 1, the computer 11 includes a central processing unit (CPU) 12, a system memory 14 for storing software that is executed by the CPU 12, a graphics system 16 for processing graphics data received from the CPU 12, a local interface 18 configured to electrically interconnect the foregoing elements, and a display 21 connected to the graphics system 16 via a connection 22 and configured to display the image data generated by the graphics system 16.

The graphics system 16 breaks down objects to be represented on the display 21 into graphics primitives. "Primitives" are basic components of a image data and may include points, lines, vectors, and polygons, such as triangles and quadrilaterals. Typically, hardware and/or software is implemented in the graphics system 16 in order to render, or draw, the graphics primitives that represent a view of one or more objects being represented on the display 21.

Generally, the primitives of an object to be rendered are defined by the CPU 12 in terms of primitive data. For example, when a primitive is a triangle, the CPU 12 may define the primitive in terms of, among other things, x, y, and z coordinates and color values (e.g., red, green, blue) of its vertices. Additional primitive data may be used in specific applications. Rendering hardware in a rasterizer of the graphics system ultimately interpolates the primitive data to compute the final display screen pixel values that represent each primitive, and the R, G, and B color values for each pixel.

The graphics system 16 is shown in further detail in FIG. 2. As shown in FIG. 2, the computer graphics system 16 includes one or more geometry accelerators 23 that are configured to receive vertex data from the CPU 12 and define the primitives that make up the view to be displayed. Each geometry accelerator 23 comprises a number of specialty control units 17 for processing the image data, including for example, a transform mechanism (TRANS) 24 for performing transformations on the vertex data, such as scaling or moving a vertex in space, a clip mechanism (CLIP) 26 for clipping portions of objects that extend beyond a boundary, a light mechanism (LIGHT) 28 for enhancing the image data by simulating light conditions, and a plane equation mechanism (PLANE) 32 for defining the primitives in terms of mathematical floating point plane equations. Each of the control units 17 is typically implemented via cell logic and as separate distinct state machines. The output of the geometry accelerator 23, referred to as rendering data, is used to generate final screen coordinate and color data for each pixel and each primitive. The output 33 is passed to a floating point to fixed point (FP-TO-FIXED) transformation unit 34, which converts the geometry accelerator output 33 to fixed point format 35 and which passes the value to a rasterizer 36. The rasterizer 36 produces pixel data 37, which is communicated to a frame buffer controller 38 and then to a frame buffer 42. The frame buffer 42 serves to temporarily store the pixel data prior to communication to the display. The pixel data is passed from the frame buffer 42 through a digital-to-analog converter (DAC) 44 and then to the display 21.

The operations of the geometry accelerator 23 are highly mathematical and computation intensive. One frame of a three-dimensional (3D) graphics display may include on the order of hundreds of thousands of primitives. To achieve state-of-the-art performance, the geometry accelerator 23 may be required to perform several hundred million floating point calculations per second. Furthermore, the volume of data transfer between the CPU 12 and the graphics system 16 is very large. The data for a single quadrilateral may be on the order of sixty-four words of thirty-two bits each. Additional data transmitted from the CPU 12 to the geometry accelerator 23 includes light parameters, clipping parameters, and other parameters needed to generate the graphics image for the display 21.

It is common in geometry accelerators 23 to have a stack of processing elements 52, as illustrated in FIG. 3, including but not limited to, an arithmetic logic unit (ALU) 54, a multiplier 55, a divider 56, a comparison mechanism 57, a clamping mechanism 58, etc., along with register and random access memory (RAM) work spaces 61, 62. The processor elements are typically shared by the plurality of specialty control units 17. Each control unit 17 is capable of directing the processing activities of individual processor elements 52 to accomplish specific computational tasks.

To provide processor element access to each control unit 17, adequate control line connectivity and access control should be established between the processor elements 52 and each control unit 17. One solution to providing control line connectivity is illustrated in FIG. 3 and involves multiplexing the control lines between each control unit and each processor element 52. A multiplexer (MUX) 66 of FIG. 3 serves this purpose. The MUX 66 is controlled by a MUX control mechanism 68. The MUX control mechanism 68 provides an enable signal 69 to the MUX 66 in order to control which one of the control units 17 is allowed to access the processor elements 62 at a given time. In operation, the MUX control 68 asserts an enable signal 69 pertaining to a particular control unit 17 to the MUX 66 and a go signal 72 to the particular control unit 17. In turn, the particular selected control unit 17 generates operands and a processor start signal to begin a processing operation, which are ultimately forwarded to the stack 51. The control unit 17 accesses the stack 51 and the specific desired processing element 52 via an appropriate connection 74, MUX 66, and connection 76. The control unit 17 causes the operating processing element 52 to retrieve data from the input buffer 77 (usually, a FIFO buffer) and store a result(s) in an output buffer 82 (usually, FIFO buffer). The control unit 17 can initiate any number of operations via one or more of the processing elements 52. When the control unit 17 is done with its turn, then it asserts a done signal 84 to the MUX control 68. The MUX control 68 then asserts another go signal 72 to another control unit 17, while providing an enable signal 69 corresponding to the next control unit 17.

A problem with the foregoing design is the large number of gate levels that are required to implement the MUX 66. Another problem is that the MUX 66 increases the time needed for signals to be communicated from the control unit 17 to the processing elements 52. Gate delay alone is part of this increase. Loading also contributes to the time delay, even if a tri-state MUX 66 is employed to replace the multi-layered gate arrangement. Furthermore, the aforementioned problems are magnified as the number of control units 17 and the number of processing elements 52 are increased.

A heretofore unaddressed need exists in the industry for a system and method for better interfacing control units 17 with processing elements 52 in order to optimize the performance of a geometry accelerator in a computer graphics system.

Briefly described, the invention provides for an assembler system and method for enabling efficient usage of space in a read only memory (ROM) that permits multiway instruction branching. In general, multiway branching would normally require skipping instruction locations within the ROM in order to accommodate the multiway branching. However, the invention provides a way to assemble the code without having to skip locations, thereby enabling efficient use of all space within the ROM.

Although not limited to this particular application, the invention is implemented in connection with the ROM of a geometry accelerator for a graphics system. The ROM is designed to implement control units in the geometry accelerator. Each of the control units is configured to drive a processing element in order to modify image data. A next address associated with each of the instructions defines a location in the ROM of a next instruction to be executed. Branch logic is configured to define the next address for a currently executing instruction associated with a corresponding ROM-based control unit.

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 code fragments 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=2.sup.n and 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. Finally, a branch instruction can be a nonaligned or an aligned instruction.

In accordance with a significant feature of the invention, the assembler system is configured to, by using the next state and align statements, (a) store the nonaligned instructions in the ROM in succession starting with a lowest memory location and moving to higher memory locations, and (b) store aligned instructions in the ROM in sets of k (where k=2.sup.n and n is a positive integer) 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. In the preferred embodiment, the assembler system is capable of storing in the ROM different size sets of aligned instructions that have different numbers of instructions (i.e., k1, k2, etc.).

The invention can also be viewed as providing a method for enabling efficient usage of space in a ROM that permits multiway instruction branching. In this regard, the method can be broadly summarized as follows: (a) providing source code having instructions 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 ie equal to 2.sup.n and where n is a positive integer, the aligned instructions being addressable by a plurality of other instructions; (b) analyzing the instructions in succession and storing the instructions in the ROM by: (1) storing any of the nonaligned instructions in the ROM, in succession starting with a lowest memory location and moving toward higher memory locations; and (2) 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 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.

The invention has numerous advantages, a few of which are delineated hereafter, as merely examples.

An advantage of the invention is that it permits no-penalty multiway branching in microcode of a ROM.

Another advantage of the invention is that it is particularly suited for enabling efficient use of space in a ROM that permits multiway branching within a geometry accelerator for a computer graphics system.

Another advantage of the invention is that it enables software programmers to create source code for software-based control units of a geometry accelerator without having to address the issue of placement of the instructions in the ROM.

Another advantage of the invention is that it can be implemented in connection with k-way instruction branching, where k=2.sup.n and where n is a positive integer, i.e., branching to k possible locations (i.e., 2, 4, 8, 16, 32, . . . , m) after execution of each instruction.

Another advantage of the invention is that it facilitates an architecture that enables parallel execution of instructions.

Another advantage of the invention is that software bugs that are specific to the software-based control units of the geometry accelerator are discovered early in the development cycle, during the compile phase, when they are the least costly to correct.

Another advantage of the invention is that it can be implemented in hardware, software, or a combination thereof. When implemented in software, it can be stored, utilized, and transported while residing on any computer readable medium.

Other features and advantages of the invention will become apparent to one with skill in the art upon examination of the following drawings and detailed description. It is intended that all such additional features and advantages be included herein with the scope of the present invention, as is defined by the claims.

The invention can be better understood with reference to the following drawings. The components of the drawings are not necessarily to scale relative to each other, emphasis instead being placed upon clearly illustrating principals of the present invention. Furthermore, like reference numerals designate corresponding parts throughout the several views.

FIG. 1 is an electronic block diagram showing a computer having a graphics system;

FIG. 2 is an electronic block diagram showing the graphic system of FIG. 1;

FIG. 3 is an electronic block diagram showing a prior art embodiment of the geometry accelerator of FIG. 2;

FIG. 4 is an electronic block diagram showing a geometry accelerator of the invention having control units implemented in a read-only memory (ROM) and branch logic configured to assist instruction branching within the ROM;

FIG. 5 is an electronic block diagram showing a specific hierarchical logic implementation of the branch logic of FIG. 4 having a branch central intelligence mechanism.

FIG. 6 is a schematic diagram showing an implementation example of fields within a microcode instruction disposed within the ROM of FIG. 4;

FIGS. 7A-7C is a state diagram showing an implementation example of the branch central intelligence mechanism of FIG. 5;

FIG. 8 is a flow chart showing an implementation example of each control unit within the ROM of FIGS. 4 and 5;

FIG. 9 is a schematic diagram showing a simplified implementation example of possible microcode that can be disposed within the ROM of FIGS. 4 and 5;

FIG. 10 is an electronic block diagram of an assembler system and method of the present invention;

FIG. 11 is a flow chart showing an implementation example of the assembler system of FIG. 10; and

FIG. 12 is a schematic diagram showing a simplified implementation example of possible source code and its placement within the ROM of FIGS. 4, 5, and 10 using the assembler system of FIGS. 10 and 11.

Generally, referring to FIG. 4, the present invention provides for efficient implementation of control units 17 of a geometry accelerator (FIG. 2) of a computer graphics system 16 (FIGS. 1, 2) within a read-only memory (ROM) 101. Implementation of the control units 17 within the ROM 101 better interfaces the control units 17 with processing elements 52, minimizes space requirements, and increases the overall speed of the geometry accelerator 23. Furthermore, the implementation enables multiway logic branching, which further enhances performance. In other words, multiple decisions can be made at the same time and in parallel. The assembler system and method of the present invention, which will be described in detail with reference to FIGS. 10 through 12, is configured to efficiently assemble and place instructions within the ROM 101 so that no spaces need to be skipped in order to accommodate the aforementioned multiway branching.

In architecture, with reference to FIG. 4, the geometry accelerator 23 includes a number of specialty control units 17 for processing the image data, including for example but not limited to, a transform mechanism (TRANS) 24 for performing transformations on the vertex data, such as scaling or moving a vertex in space, a decomposition mechanism (DECOMP) 25 for decomposing primitives, such as converting a quadrilateral into a triangle, a clip mechanism (CLIP) 26 for clipping portions of objects that extend beyond a boundary, a bow-tie mechanism (BOW-TIE) 27 for processing a bow-tie configuration in order to determine its intersection point and to decompose the primitive into triangles, a light mechanism (LIGHT) 28 for shading and enhancing the image data by simulating one or more light conditions, a classify mechanism (CLASS) 29 for classifying a primitive as front facing or back facing for special effects, a plane equation mechanism (PLANE) 32 for defining the primitives in terms of mathematical floating point plane equations, and a fog mechanism (FOG) 39 for, in essence, imposing a background color upon an object in an image to enhance distance perspective.

Significantly, the geometry accelerator 23 further includes branch logic 102 configured to manipulate, if appropriate, a next address within an instruction currently being executed by the ROM 101 so that the current instruction can ultimately branch to one of up to eight possible instruction locations (only four, in the preferred embodiment), a stack 51 of processing elements 52 as previously described and configured to execute instructions from the ROM 101, an input buffer 77 configured to receive data from the CPU 12 (FIG. 1), and an output buffer 82 configured to provide output data to the rasterizer 31 (FIG. 2). The branch logic 102 is configured to receive an address 104 from the ROM 101 as well as state data 106 from the ROM 101, the stack 51, the CPU 12 (FIG. 1), and/or elsewhere. The state data can include many types of information regarding the state of the geometry accelerator 23, for example, but not limited to, information regarding whether or not a control unit 17 has concluded operation, information regarding the type of primitive or polygon, information regarding whether or not the primitive includes light parameters, rendering mode information, light mode information, etc. Based on the state data 106, the branch logic 102 is configured to make a determination as to whether the next address 104 associated with the current instruction should be modified or left unchanged, and if it is to be modified, how to change the next address.

As shown in FIG. 4, the branch logic 102 is configured to receive the next address, or a part thereof, from the ROM 101 and is configured to output a new next address (modified or unmodified) 108 to the ROM 101. The instruction that is currently executed in the ROM 101 includes the next address 104 in a corresponding next address field (e.g., see FIG. 6). The next address 108 will advise the ROM 101 where to go to next for the next instruction after the current instruction has been fully executed.

An example of logic functionality that may be employed within the branch logic 102 is as follows. Assume that primitive data is passed through the transform mechanism 24 and that state data 106 from the transformation control unit 24 in ROM 101 indicates that the primitive is off-screen. Further assume that the current instruction had a next address 104 pointing to the clipping control unit 26. In this case, the branch logic 102 may be configured to change the next address 104 so that the next address 108 points to the beginning of the transformation control unit 24 in order to wait for the next primitive to be processed.

As another example, consider the scenario where lighting is turned off and the address of the current instruction points to the light mechanism 28. In this case, the branch logic 102 may modify the next address so that the current instruction points to a different control unit 17, for example, the plane equation mechanism 32.

An example of a possible specific implementation of the geometry accelerator 23 is shown in FIG. 5. With reference to FIG. 5, the specific implementation includes branch logic 102 having a hierarchical arrangement of logic functionality. More specifically, the branch logic 102 includes a branch central intelligence mechanism 112 configured to make high level logical decisions and distributed control unit logic 114, which comprises a plurality of individual control unit logic elements (CU LOGIC ELMT) 115 corresponding respectively with each control unit 17. Each control unit logic element 115 is configured to make lower level logical decisions to help each respective control unit 17 accomplish conditional branching and to control indirect addressing.

In the preferred configuration for this specific implementation of FIG. 5, the ROM 101 includes the plurality of control units 17 in the form of generally distinct separate software modules; however, interleaved coding implementations are possible. The code of the modules are executed one at a time, and each drives a particular processing element 52 with instructions 76 (in the preferred embodiment, 211 bits).

Each microcode instruction residing in the ROM 101 has at least the fields set forth in FIG. 6. Referring to FIG. 6, each instruction includes a branch field 121, a next address field 104, a next vertex field 122, a next light field 123, an init (flag) field 124, a data path control (instruction) field 125, a condition code field 126, and an operational control unit identification (ID) field 127. These fields are described hereafter.

The branch field 121 contains help information concerning the number of possible branching locations. Because in the preferred embodiment branching can occur to one of four possible instruction locations, the branch field 121 includes two bits, a 2-way.sub.-- 4-way bit 128 and a cond.sub.-- uncond bit 129. The former indicates whether the branch is either two-way or four-way and the other defines whether the instruction is conditional or unconditional. "Unconditional" means that indirect branching will not occur after execution of the current instruction and, accordingly, the next address will not be modified by the control unit logic 114. "Conditional" means that indirect branching will occur after execution of the current instruction and, therefore, one or two bits of the next address will be replaced by the control unit logic 114. One bit is replaced, if two way branching, and two bits are replaced, if four way branching.

The next address field 104 identifies the address corresponding with the next instruction to be executed in the ROM 101, which may be in one of a plurality of locations. Each of the control unit logic elements 115 (FIG. 5) is configured to evaluate and define a next address field 104 for a currently executing instruction associated with a corresponding ROM-based control unit 17. Each next address field 104 is merely partially defined in the ROM 101 from the outset, and the control unit logic elements 115 fully define the next address field dynamically during operation by setting one or more bits (in the preferred embodiment, 2 LSBs) associated with the next address field 104.

The next vertex field 122 (preferably, 1 bit) advises the external vertex/light counter 139 (FIG. 5) when to increment its vertex count for the primitive at issue.

The next light field 123 (preferably, 1 bit) advises the external vertex/light counter 139 when to increment its light count for the primitive at issue.

The initialize field 124 identifies whether or not registers 61 and/or RAM work space 62 should be initialized (cleared or preset). Initialization typically occurs when the transform control unit 24 receives a new primitive.

The data path control field 125 is essentially the instruction to be executed by the processing element 52. The data path control field 125 can perform at least the following functions: defines the location of an operand(s) in the registers 61 and/or the RAM 62; defines an operation(s) to be performed upon an operand(s); advises the output buffer 82 when to load data from a processing element 52; and identifies a location(s) where an execution result(s) is to be stored in the registers 61, RAM 62, and/or output buffer 82.

The condition code field 126 identifies a condition code that is essentially state data that identifies the current state of the control unit 17 that is currently in operation within the ROM 101. The condition codes are specific to each control unit 17 in a sense that specific condition code values can mean different things in different control units 17. The condition codes 17 can be utilized in an infinite number of ways to affect logic decisions in the control unit logic elements 115 as well as in the branch central intelligence mechanism 112. For purposes of clarification, some specific examples of condition codes, their meaning, and their interpretation will be described in further detail hereinafter during the discussion of the logic for the control unit logic elements 115 and the branch central intelligence mechanism 112.

The operational control unit identification (ID) field 127 identifies the particular control unit 17 that is currently operating in the ROM 101.

With reference to FIG. 5, the stack 51 includes, as previously mentioned, a plurality of processing elements 52, denoted by reference numerals 54-58, and register and RAM space 61, 62. At any given time, one of the processing elements 52 executes instructions 76 from one of the control units 17 in the ROM 101. During execution, each processing element 52 may receive data from the input buffer 77, and during or after execution, each processing element 52 may place the result(s) in the output buffer 82 under the command of a control unit 17 via load signal 143 preferably (1 bit) for communication to the rasterizer 31 (FIG. 2). The input buffer 77 can provide vertex information to the stack 51. The processing elements 52 are configured to provide flags 131 (10 bits) to the branch logic 102, when appropriate, and depending upon the particular processing element 52. For example, the compare processing element 57 may provide a flag(s) 131 that indicates that two operands are equal, that two operands are not equal, that one operand is greater than another, that one operand is less than another, etc.

A state management address decode mechanism 132 is provided to receive global state data (54 bits, of which 32 bits are data, 21 bits are address, and 1 bit is indicative of whether the input buffer has valid/invalid data), including mode information, from the CPU 12 (FIG. 1) by way of the input buffer 77, as indicated by reference arrow 133. An unload signal 135 (1 bit) from the state management address decode 132 provokes the foregoing transfer of the state data. The mode information controls some behavioral aspects of the geometry accelerator 23. In the preferred embodiment, there are three 32-bit registers controlling the three respective modes of operation: a rendering mode, a first light mode, and a second light mode. Generally, the rendering mode register defines global information concerning the types of graphics effects, or features, that will be accomplished in the image data via suitable processing, for example but not limited to, lighting, fog, texture mapping, etc. Furthermore, the first and second light mode registers define more specific information on how the graphics effects are to be applied to the image data, for example but not limited to, the number and type of lights to be turned on, the type of texture mapping, etc.

The branch central intelligence mechanism 112 of the branch logic 102 receives the mode information 134 (in the preferred embodiment, 200 bits) from the state management address decode mechanism 132. The branch central intelligence mechanism 112 also receives the flags 131 from the stack 51, the condition codes 126 from the ROM 101, and an operational control unit signal 136a (in this example, 3 bits) from the ROM 101 indicative of which control unit 17 is currently operating within the ROM 101. Based upon state data, i.e., the mode information 134, the flags 131, the condition codes 126, and the operational control unit signal 136a, the branch central intelligence mechanism 112 produces and outputs an appropriate next control unit signal 138 to an individual control unit logic element 115 corresponding with the operational control unit 17. The next control unit signal 138 defines which control unit 17 should be branched to next pursuant to the logic within the branch central intelligence mechanism 112.

Each of the individual control unit logic elements 115 situated within the control unit logic 114 assists a corresponding control unit 17 in accomplishing branching and indirect addressing. Each of the individual control unit logic elements 115 is configured to make logical decisions for its respective control unit 17 based upon and as a function of state data, including in the preferred embodiment, two least significant bits (LSBs) 104' of the next address 104 from the current instruction of the ROM 101, the branch field 121 from the current instruction of the ROM 101, a condition code 126 from the current instruction of the ROM 101, last vertex and light signals 137 from a vertex/light counter 139 indicative of whether or not the current instruction involves the last vertex and last light to be processed in a grouping of vertices/lights associated with a code subroutine, and the flags 131 from the stack 51.

The functionality of each control unit logic element 115 may be implemented in cell logic, a look-up table, or any other suitable logic mechanism. As examples of the logic within each individual control unit logic element 115, consider the following. These examples should not be construed as limiting, as there are an infinite number of possible logic configurations.

As a first example, assume that a particular control unit 17 in the ROM 101 is operating. In this example, the condition code may be correlated with the logic in the corresponding control unit logic element 115 so that when the corresponding control unit logic element 115 is forwarded a condition code having a value of i (where i is any number) from the particular control unit 17, then the control unit logic element 115 evaluates the last vertex bit 137 and if the last vertex bit 137 is asserted, then the control unit logic element 115 sets the next address 104 so that the current instruction branches to the light control unit 28.

As another example, assume that the plane equation mechanism 32 is operating, that mathematical operations are being performed upon a plane equation vector, that plane equation parameters dx and dy have already been computed along the vector, and that a compare operation is presently being performed by the compare processing element 57 in the stack 51. In this example, a condition code of value i (any number) from the plane equation mechanism 32 may require the respective control unit logic element 115 to examine a flag 131 from the stack 51 concerning the outcome of the compare operation and define the next address 104 accordingly. Further, if dx is greater than dy based upon the flag 131 (i.e., the code is currently operating upon an x major vector), then the control unit logic element 115 will force the current instruction to branch to a first location in the code. Otherwise, if dy is greater than dx based upon the flag 131 (i.e., the code is currently operating upon an y major vector), then the control unit logic element 115 will force the current instruction to branch to a second location in the code that is different than the first.

As yet another example, assume that a particular control unit 17 is operating and that a condition code having a value of i (any number) indicates to its corresponding control unit logic element 115 to examine the next control unit signal 138 from the branch central intelligence mechanism 112. In this case, when the control unit logic element 115 detects the appropriate condition code of i, then it sets the next address 104 so that branching occurs to another control unit 17 based upon the next control unit signal 138 from the branch central intelligence mechanism 112.

Implementation of a plurality of individual control unit logic elements 115 reduces the size of requisite microcode instructions 76 that must be stored in the ROM 101, and furthermore, reduces the amount of routing logic necessary to implement branching functionality. In other words, the logic of the plurality of individual control unit logic elements 115 could be implemented with a single logic element; however, the single element logic would be much larger in size and logic complexity, and therefore, undesirable, especially for an integrated circuit implementation.

A vertex and light (vertex/light) counter 139 is implemented using any suitable logic. The vertex/light counter 139 is designed to count and track vertices as well as lights for a primitive. It produces a last vertex signal 137 and a last light signal 137 for the individual control unit logic elements 115 to indicate that the last vertex and last light, respectively, of the primitive has been processed based upon and as a function of the following signals: a flag initialize bit 141 from the ROM 101, next vertex/light signals 142 from the ROM 101, and primitive information 144 (12 bits, of which 4 bits indicate primitive type and 8 bits indicate the number of lights that are turned on) from the state management address decode mechanism 132, including the primitive type (e.g., point, vector, triangle, quadrilateral, etc.) and the number of lights, if any, that are turned on.

A MUX 146 receives LSBs 148 (in the preferred embodiment, 2 bits) of the next address 104 from the individual control unit logic elements 115. The operational control unit signal 136b (3 bits, in this example) from the ROM 101 forces the MUX 146 to select the appropriate connection 148 associated with the appropriate control unit logic element 115 corresponding with the operational control unit 17.

A latch 149, preferably a conventional data-type (D-type) flip-flop storage latch, is configured to receive the LSBs 151 from the MUX 146. The latch 149 is clocked by a system clock signal (CK) 152.

A latch 155, preferably a D-type flip-flop storage latch, receives the upper nine bits 104" of the next address 104 from the ROM 101. The latch 155 is clocked by the clock signal (CK) 152. The latch 155 outputs the nine bits 156, which are combined with the two bits 154 from the latch 149, in order to create the next address 108 (11 bits) for the ROM 101.

As an example, FIG. 7 illustrates a state diagram for a possible implementation of the branch central intelligence mechanism 112 (FIG. 5). In FIG. 7, the diamond-shaped blocks represent logical decisions made by the branch central intelligence mechanism 112, and the rectangular-shaped blocks represent logic functionality performed by control units 17 within the ROM 101. Hence, FIG. 7 illustrates how the branch central intelligence mechanism 112 decides which control unit 17 is selected and utilized next for each primitive.

Initially, a dispatch mechanism 24', which is essentially a header in the transform mechanism 24, awaits the arrival of a primitive. Once a primitive arrives, the dispatch mechanism 24' advises the branch central intelligence mechanism 112 of this fact.

The branch central intelligence mechanism 112 continues to monitor the mode information 134 until a primitive arrives. This functionality is indicated at block 71. After a primitive arrives, the branch central intelligence mechanism 112 produces a next control signal unit 138 corresponding with the transform mechanism 24.

After the transform mechanism has transformed the primitive, then a determination is made as to whether the primitive should be trivially rejected, as indicated at block 72. A primitive is trivially rejected if the entire primitive is off the screen, in which case the process will revert back to the dispatch mechanism 24'. If the primitive should not be trivially rejected, than the branch central intelligence mechanism 112 makes a determination as to whether the primitive needs to be classified, as denoted at block 73.

In the preferred embodiment, primitives can be classified as front facing or back facing. Generally, lighting is adjusted based upon these parameters. If the primitive is of the type that needs to be classified, then the branch central intelligence mechanism 112 generates a next control signal 138 that corresponds with the classify mechanism 29. Further, after the classify mechanism 29 classifies the primitive, then the branch central intelligence mechanism 112 determines whether the primitive is culled.

In the preferred embodiment, culling is a feature that has been added to optimize rendering speed. In essence, the user can specify whether front or back facing primitives should be discarded. If the current primitive is a primitive to be discarded, then the process will revert back to the dispatch mechanism 24'. Otherwise, the branch central intelligence mechanism 112 makes a determination as to whether the light mechanism 28 should be called, pursuant to block 75.

If the branch central intelligence mechanism 112 determines at block 73 that the primitive need not be classified, then the branch central intelligence mechanism 112 next makes a determination as to whether the primitive should be lighted with the light mechanism 28, as indicated at block 75.

If at block 75 it is determined that the primitive should be lighted, then the branch central intelligence mechanism 112 defines an appropriate next control unit signal 138 so that the light mechanism 28 is called. If a primitive is not constant color, then it will be lighted.

After lighting, the branch central intelligence mechanism 112 makes a determination as to whether fog should be applied to the primitive, as indicated at block 76. If so, then the fog mechanism 39 is called.

After application of fog or if at block 76 it is determined that not fog will be applied, then the branch central intelligence mechanism 112 initializes internal registers, as indicated in block 77. In this regard, a "FIRST" variable is asserted (set to "1") to indicate that this is the first primitive, a "QUAD.sub.-- A" variable is asserted to indicate that this is a type "A" quadrilateral (i.e., a convex quadrilateral), and a variable "BOW-TIE" is deasserted (set to "0") to indicate that this is not a bow tie.

After setting the internal registers, at block 78, the branch central intelligence mechanism 112 determines whether the primitive needs to be clipped. If so, then process flow continues through blocks 81-86. If not, then process flow continues through blocks 91-95.

In the event that clipping of the primitive is to be performed, then the branch central intelligence mechanism 112 determines whether the primitive is a quadrilateral, as indicated at block 81. If so, then the decomposition mechanism 25 is called. Otherwise, the decomposition mechanism 25 is not called.

After the quadrilateral analysis and decomposition, if necessary, then any specified clipping planes are processed in serial fashion. Each specified clipping plane is processed in a loop as indicated in blocks 83-85 in FIG. 7. Prior to entering the loop, internal registers are initialized. A variable "MODEL.sub.-- CLIP.sub.-- PASS" is initialized to 0 so that the first clipping plane is considered and analyzed. With each pass through the loop, a determination is made as to whether there is a bow-tie, as indicated at block 83, in which case the bow-tie mechanism 27 is called in order to compute the intersection point. Further, the clip mechanism 26 and then the plane equation mechanism 32 are employed to further process the data, as illustrated. In the loop, the logic at block 84 increments the model.sub.-- clip.sub.-- pass variable, and the logic at block 85 causes the process flow to revert back to block 83, until all clipping planes have been processed.

At block 86, a determination is made as to whether this primitive is the first triangle of the quadrilateral. If not, then process flow reverts back to block 71. If so, then at block 87, the branch central intelligence mechanism 112 sets internal registers in order to process to second triangle of the quadrilateral. In this regard, the variable "MODEL.sub.-- CLIP.sub.-- PASS" is set to 0 and the variable "FIRST" is set to 0.

If at block 78, it is determined that the primitive is not to be clipped, then the plane equation mechanism 32 is called, and then the branch central intelligence mechanism 112 verifies whether the primitive is a type "A" (convex) quadrilateral, as indicated at block 91. This is accomplished by observing the flags from the stack 51 and condition codes 126. Specifically, the branch central intelligence mechanism 112 is provided by an appropriate condition code 126 to analyze the flags 131 from the stack 51. The flags 131 indicate the type of quadrilateral. If not, then the process will revert back to block 71 to wait for another primitive. Otherwise, in the case where the primitive is not a type "A" (convex) quadrilateral, then the primitive is decomposed via the decomposition mechanism 25.

Next, the branch central intelligence mechanism 112 makes a determination as to whether the primitive is a bow-tie, as indicated at block 93. If not, then the plane equation mechanism 32 is called. Otherwise, the bow-tie mechanism 27 is called and then the plane equation mechanism 32. The logic of blocks 94-95 insure that both triangles of the bow-tie are processed.

Operation

The operation of the geometry accelerator 23 having the control units 17 implemented in the ROM 101 will now be described with reference to FIGS. 8 and 9. FIG. 8 shows a flow chart 161 that reflects operation of an example of a control unit 17 within the ROM 101 in conjunction with the branch logic 102. In this example, in general, a control unit 17 processes all vertices and all lights, if any, of a grouping of vertices and lights corresponding with a primitive at issue. Reference will be made to both FIGS. 5 and 8 in the following discussion.

First, primitive data and state data is provided to the input buffer 77 by the CPU 12 (FIG. 1). The state management address decode 132 reads the state data 133 by asserting an unload signal 135 to the input buffer 77. In turn, the state management address decode 132 decodes the state data and provides mode information 134 to the branch central intelligence mechanism 112. Moreover, the branch central intelligence mechanism 112 provides next control unit signals 138 to respective control unit logic elements 115.

A microcode instruction is read by ROM 101, and a microcoded control unit 17 therein is accorded the opportunity to operate within the ROM 101. The microcoded control unit 17 performs an initialization routine at the start of a grouping of vertices/lights, as indicated in flow chart block 162. Here, the control unit 17 of the ROM 101 basically initializes flags, such as flag init 141, and register and RAM space 61, 62 in the stack 51.

Next, a vertex looping routine is commenced, which processes data associated with a vertex of the primitive during each loop operation. As indicated at block 163, the appropriate control unit logic element 115 determines via the last vertex bit 137 whether the vertex that was recently operated on in the past by the stack 51 is the last vertex of the primitive that is currently at issue.

If so, then the control unit 17 is forced to transfer control of the stack 51 to another control unit 17, as indicated by block 164, by the control unit logic element 115. In this case, the control unit logic element 115 accomplishes this by modifying one or both of the next address LSBs 104'. The high level logic associated with the branch central intelligence mechanism 112 ultimately determines which control unit 17 is utilized next. The control unit logic element 115 determines the appropriate branch location, i.e., how to modify the next address LSBs 104', based upon the next control unit signal 138 from the branch central intelligence mechanism 112.

When the previously processed vertex was not the last and thus more remain to be processed, then the microcode of the control unit 17 performs one or more operations on the present vertex using one or more of the processing elements 52, as indicated at block 165. The corresponding control unit logic element 115 dictates branching during these operations, based upon the branch field 121, the condition codes 126, and flags 131.

For each vertex, a light looping routine is commenced, if applicable, which processes data associated with a light(s) of the primitive during each loop operation. As indicated at block 166, the appropriate control unit logic element 115 determines via the last light bit 137 whether the light that was previously operated on by the stack 51 is the last light of the vertex that is currently at issue.

If not, then light operations are performed, as indicated at block 167. The corresponding control unit logic element 115 dictates branching during these light operations, based upon the branch field 121, the condition codes 126, and flags 131. After the light operations, a light counter is advanced, as denoted at block 168, and process flow reverts back to block 166 to identify another light, if any remains to be processed.

If no more lights remain to be processed at block 166, then the vertex counter 139 (FIG. 5) is advanced via the next.sub.-- vertex signal 142, as indicated at block 166 in FIG. 8, and another vertex is retrieved for processing, if any remain, as indicated at block 163 in FIG. 8.

The aforementioned process continues in cyclical fashion until all vertices and lights, if any, have been processed in a grouping, in which case one or more other microcoded control units 17 may be given authorization to commence operation until processing on the primitive is complete.

Microcode Example

To further clarify operation, a specific simplified example of microcode in the ROM 101 will now be discussed with reference to FIG. 9. In this example, it is assumed that the ROM 101 contains at least eleven instructions having the contents set forth in FIG. 9.

The ROM 101 will commence the launch of the instruction in location 0. At commencement of code pertaining to a control unit 17, an initialization routine is performed. Because the initialize flag in the instruction is asserted at this point in view of commencement of a new control unit 17, the ROM 101 would assert the flag.sub.-- intialize signal 141 (FIG. 5) to the vertex counter 139 (FIG. 5), thereby causing the vertex counter 139 to initialize its vertex count. The vertex counter 139 is advised of the type of primitive and the number of vertices by the state management address decode 132 via primitive information signal 144. Further, the nonconditional flag of this instruction is asserted in the branch field 121, and therefore, the control unit logic elements 115 need not look to the two-way.sub.-- four-way flag, at all, and need not modify the next address LSBs 104'. Because there is no indirect addressing, the control unit logic elements 115 do not modify the next address field 104. Finally, the instruction evaluates the next.sub.-- address field, which indicates that the next instruction to be executed is that in instruction location 1. Accordingly, the next instruction that is executed is that situated in location 1.

The instruction situated in location 1 does not require initialization as the initialize flag is deasserted. Therefore, the flag init signal 141 to the vertex counter 139 is deasserted. The conditional flag of the branch field 121 is asserted, and therefore, the appropriate control unit logic element 115 interprets the two-way.sub.-- four-way flag, which is set to 0, indicating that the branching is two-way. The next address field of the instruction can be defined by the logic element 115 to branch to the instruction in location 2 or location 3, depending upon the condition code 126 and any flag 131 from the stack 51. If the last light or vertex has not been processed in a grouping of vertices/lights based upon the condition code 126, flags 131, and the last signal 137, then the control unit logic element 115 can be configured to cause the ROM 101 to select the instruction situated in location 2. To do this, the control unit logic element 115 defines the next address LSBs 148 appropriately. In this case, the control unit logic element 115 allows LSB1 of the next address 104 to be passed through unchanged to next address 108 and forces LSB0 of the next address 104 to be deasserted ("0").

The instruction in location 2 does not require initialization, as indicated by the deasserted initialization flag. The vertex counter 139 (FIG. 5) is not advanced per a deasserted flag.sub.-- init signal 141. Moreover, the data path control field 125, which is passed to the stack 51 from the ROM 101 on connection 76, causes the ALU 54 (FIG. 5) to execute by adding operands A and B. Operands A and B are retrieved from the registers 61 and/or RAM 62, the location of which is defined in the data path control 125 of the instruction. The result is stored in the register 61, RAM 62, and/or output buffer 82 by the ALU 54. The nonconditional flag is asserted, and therefore, the two-way.sub.-- four-way flag need not considered, and the control unit logic element 115 need not modify the next address LSBs. Further, the next address is that which is in location 4, as prescribed by the instruction.

The instruction in location 4 is launched by the ROM 101 after conclusion of the instruction in location 2. No initialization occurs, and the vertex counter 139 is not advanced. The instruction causes the ALU 54 to add operands C and D. Operands C and D are retrieved from the registers 61 and/or RAM 62 based upon the data path control 125. The result is stored in the register 61, RAM 62, and/or output buffer 82 by the ALU 54. Further, the instruction is not conditional, and transfers directly to the instruction in location 5. Again, the control unit logic element 115 does not modify the next address LSBs in this case.

The instruction in location 5 does not initialize and does not advance the vertex counter 139. It causes the multiplier 55 (FIG. 5) to multiply operands E and F. Operands E and F are retrieved from the registers 61 and/or RAM 62. The result is stored in the register 61, RAM 62, and/or output buffer 82 by the multiplier 55. The instruction is nonconditional, and therefore, the instruction can only branch to one other instruction, that which is situated in location 6, pursuant to the next.sub.-- address field. Again, the control unit logic element 115 does not modify the next address LSBs in this case.

The instruction in location 6 does not perform an initialization process pursuant to the initialize flag. Its data path control field causes the compare mechanism 57 (FIG. 5) to compare the quantities (A+B), (C+D). The instruction is nonconditional. It causes the ROM 101 to look to the instruction in location 1, after incrementing the vertex counter 139, in accordance with the next.sub.-- vertex field.

For each primitive, the aforementioned operations will occur once for each vertex, i.e., the ROM 101 will cycle through ROM locations 1, 2, 4, 5, and 6. Thus, in the case of a triangle having three vertices, three cycles through the aforementioned instructions would occur. After the last vertex/light, the branch central intelligence mechanism 112 will recognize a condition code, for example, "7" as shown in FIG. 9, that indicates that the branch logic 115 for this control unit 17 should observe the last signal 137 and determine if it is the last vertex light. In this case, it is. In this event, the branch central intelligence mechanism 112 advises an appropriate control unit logic element 115 of the next control unit 17 to be utilized. The next address field 104 may be set by the appropriate control unit logic element 115 to indicate that the ROM 101 should advance to location 3 for the next instruction.

At location 3, the instruction is conditional, as indicated by the asserted conditional flag. Moreover, the four-way flag is asserted, thereby indicating that the next instruction can be in one of four different locations in the ROM 101, or locations 8-11. The control unit logic element 115 makes the decision by defining the next address LSBs, based upon and as a function of the next control unit signal 138 from the branch central intelligence mechanism 112, the condition code 126 from the ROM 101, and any flags 131 from the stack 51. In this example, locations 8-11 correspond to instructions that commence routines for clipping, shading, plane equations, and decomposition. As illustrated in FIG. 9, this instruction indicates a condition code of "5." The condition code "5" might indicate to the control unit logic element 115 that it should examine the next control unit signal 138 from the branch central intelligence mechanism 112 in order to jump to another control unit 17. The next control unit 17 could be for example the light mechanism if the branch central intelligence mechanism 112 determines that shading should occur next, in which case the control unit logic element 115 would define the next address LSBs so that the next address would be defined as location 9.

Assembler System

The assembler system 180 of the present invention is shown in FIG. 10. The assembler system 180 of the invention can be implemented in software, hardware, or a combination thereof. Although not limited to this application, the assembler system 180 of the invention is particularly suited for orienting microcode instructions within the ROM 101 of the geometry accelerator 23. In this regard, the assembler system 180 analyzes source code 182 having instructions and stores (assembles) them in appropriate locations of the ROM 101 to efficiently use all of the space within the ROM 101.

Furthermore, in the preferred embodiment, the assembler system 180 is implemented in software that is stored in a suitable computer readable medium and executed by a general purpose or other suitable computer. In fact, the assembler system 180 can be stored on any computer-readable medium for use by or in connection with a computer-related system or method. In the context of this document, a computer-readable medium is an electronic, magnetic, optical, or other physical device or means, for example, a random access memory (RAM) or portable computer storage device, that can contain or store a computer program for use by or in connection with a computer-related system or method.

The branching mechanism of the preferred embodiment associated with the software-based control units 17 of the geometry accelerator allows branching to either two or four instructions at a time, but those instructions need to be aligned on a two or four instruction boundary, respectively, within the ROM 101 in order to ensure that the two LSBs 104' of the next address 104 (FIG. 5) are initialized to zeros and therefore can be properly manipulated by the branch logic 102 (FIG. 4). The assembler system 180 is configured to store the source code instructions so that there is no need for skipping locations within the ROM 101 in order to accommodate the boundary requirements.

The source code 182 that is analyzed and sorted by the assembler system 180 includes at least the following code fragments or an equivalent counterpart thereof: next.sub.-- state statements, nonaligned instructions, align statements, and aligned instructions. Next.sub.-- 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 180 that a plurality k (where k=2.sup.n 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. Finally, a branch instruction can be a nonaligned or an aligned instruction.

In general, in accordance with the methodology of the invention, the nonaligned instructions of the source code 182 are stored in the ROM 101, starting with a lowest memory location and moving to higher memory locations, while the aligned instructions are stored in the ROM 101, starting with a highest memory location and moving to lower memory locations. More specifically, the source code is analyzed. The source code fragments are analyzed individually in succession, and the nonaligned and aligned instructions therein are stored in the ROM by the assembler system 180, as follows: (1) storing any of the nonaligned instructions in the ROM, in succession starting with a lowest memory location and moving toward higher memory locations; and (2) 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 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. In the preferred embodiment, the assembler system 180 is capable of storing in the ROM 101 different size sets of aligned instructions that have different numbers of instructions (i.e., k1, k2, etc.).

FIG. 11 illustrates a high level flow chart of a possible implementation of the architecture, functionality, and operation of the assembler system 180 (FIG. 10). In the preferred embodiment, the assembler system 180 is implemented in software, and therefore, the blocks in the flowchart of FIG. 11 represent high level modules, segments, or portions of software code. In operation, the assembler system 180 loops through and analyzes each code fragment (instruction or statement) in the source code 182 (FIG. 10) and sorts the instructions in the code 182 into an appropriate location within the ROM 101, pursuant to the software of FIG. 11, which is more specifically described hereinafter.

With reference to FIG. 11, initially, a determination is made as to whether any more code fragments remain to be processed, as indicated in block 191. Upon completion of processing of all code fragments in the source code 182, the assembler system 180 concludes. Otherwise, when code fragments remain to be processed, then the next code fragment is retrieved from the source code 182 and analyzed, as indicated in block 192.

Next, a determination is made as to whether the code fragment currently at issue is an align statement, as denoted in block 193. If the code fragment is not an align statement, then the code fragment is assumed to be a nonaligned instruction (because no previous align statement identified it as an aligned instruction), and therefore, it is stored within the ROM 101 in a location having the lowest available address, as is indicated in block 194. Afterwards, process flow reverts back to block 191.

If at block 193, it is determined that the code fragment is an align statement, then k (where k=2.sup.n and where n is a positive integer) aligned instructions directly follow in succession in the source code, and the logical operations set forth in block 195 are performed. The align statement comprises an indicator that identifies the specific number k. In the preferred embodiment, the align statement is in the form of "align.sub.-- k." In the preferred embodiment, two-way and four-way branching is implemented, and consequently, there will be two or four aligned instructions (i.e., k=2.sup.n =2 or 4) following each align statement.

Block 195 determines whether the align statement has associated with it the maximum number m of aligned instructions. In other words, it determines whether k=m. If so, then the k aligned instructions are stored in the highest available set of respective contiguous ROM locations, the first of which is a mathematical multiple of k. This logical operation is set forth in block 196. In the preferred embodiment, because there is only 2- and 4-way branching, the k aligned instructions can equal a maximum of four in number. Afterwards, the process flow reverts back to block 191, where another code fragment is retrieved, if any remain to be processed.

If, at block 195, it is determined that there is not the maximum number m of aligned instructions associated with the current align statement, then a further determination is made as indicated at block 197 as to whether there are any and enough already allocated locations for the current k aligned instructions. A simple array is utilized to save allocated locations from previous operations. In the preferred embodiment, block 197 is reached when there are only 2 aligned instructions. Moreover, in the preferred embodiment, because there is only two- and four-way branching, sets of four ROM locations are allocated, the highest two of which are utilized immediately and the other two of which await the next set of two aligned instructions.

Thus, in accordance with block 197, an inquiry is made as to whether there is an available set of k locations within an already allocated set of locations (the allocated set having one of k, 2(k), 4(k), . . . total locations in number).

If so, then pursuant to block 198 the k aligned instructions currently at issue are placed in the highest vacant locations in the allocated set, and the utilized locations are marked in the array to indicate that they are no longer allocated for future use. In the preferred embodiment, because sets are allocated in groups of four, if there is an existing allocated set at this point, then the highest vacant locations will be merely the remaining two lowest locations of the four-location set. However, this may not be the case if sets are allocated in numbers greater than four at a time.

When, at block 197, it is determined that there are not any locations available in a previously allocated set, then, as indicated in block 199, a search is made to find more locations that can be allocated. First, k locations are searched, then 2(k) locations, and so on to the maximum number m of aligned instructions. In each of the foregoing search cases, a search is made for a particular number (one of k, 2(k), . . . ) of contiguous ROM locations that are the highest in memory and that have a first (lowest address in the set of locations) location that is a mathematical multiple of the particular number. If some locations can be allocated in accordance with this methodology, then the variable i is set to equal the number of identified locations.

In the preferred embodiment, four contiguous ROM locations are searched for at block 199 that are the highest in memory address and that have a first (lowest address in the set of four locations) location that is a mathematical multiple of four.

Block 201 makes a determination as to whether any allocatable locations have been found. If so, then process flow reverts to block 203.

If at block 201 no locations are found to be allocatable, then the maximum number m of locations is allocated, as denoted by block 202, variable i is set to equal m, and process flow then reverts to block 203. In the preferred embodiment, this maximum number m is four.

Block 203 takes the i locations that are allocated and splits them up into k, 2(k), 4(k), . . . , i/2 sets of separate allocated locations.

Next, as indicated at block 204, the current k aligned instructions are placed in the highest locations that were allocated in block 203. Further, a marker(s) is set to advise a later align.sub.-- k operation that there are vacant locations to be utilized.

At this point in the preferred embodiment, the two aligned instructions currently at issue are stored in the highest available set of two respective contiguous ROM locations within the set of four that were just allocated. Moreover, a marker(s) is set to advise a later align.sub.-- 2 operation that there are vacant locations to be utilized.

Finally, after the logical operations of block 204, process flow reverts back to block 191, where another code fragment is retrieved for analysis from the source code, if any remains, and the aforementioned process continues.

As a simplified alternative embodiment to that is shown in FIG. 11 and described above, blocks 195 through 204 of FIG. 11 could be replaced with logic that simply stores the k aligned instructions in the highest available set of respective contiguous ROM locations, the first of which is a mathematical multiple of k However, this implementation is not optimal in that some locations may be skipped in the ROM 101. Afterward, process flow would revert back to block 191.

A specific implementation example of the flow chart functionality of FIG. 11 is illustrated in detail in FIG. 12. Referring to FIG. 12, an example of possible source code 182 (having instructions A through S) is shown along the right side, while a sequence of locations within the ROM 101 is shown along the left side. Reference arrows 206a-206f indicate spatially where aligned instructions are stored within the locations of the ROM 101. The remaining nonaligned instructions are stored in succession at the lower end of the address spectrum, while the aligned instructions are stored in groups at the high end of the address spectrum, moving downwardly in address.

More specifically, when the assembler system 180 begins analyzing the source code 182, a first instruction A is not an align statement and has not been designated as an aligned instruction by a previous align statement. Accordingly, the instruction A is considered a nonaligned instruction and placed within ROM location 0 (decimal system nomenclature). The assembler system 180 next analyzes a next.sub.-- state (NEXT.sub.-- STATE) statement, which is utilized to demarcate consecutive code fragments in the source code 182. In the preferred embodiment, source code instructions can be executed substantially simultaneously to enable parallel processing, and therefore, NEXT.sub.-- STATE statements are utilized to separate code fragments that may include instructions to be executed simultaneously.

An instruction B is next recognized and is viewed as a nonaligned instruction, because there was no align statement previous to it to indicate otherwise. Therefore, the nonaligned instruction B is placed in the ROM location having the lowest memory address, or location 1 (decimal), as shown in FIG. 12. A NEXT.sub.-- STATE statement is next observed by the assembler system 180 to indicate that a new code fragment is upcoming.

The next code fragment to be recognized and analyzed by the assembler system 180 is an ALIGN.sub.-- 4 statement. This statement indicates to the assembler system 180 that the next four instructions are aligned instructions, and therefore, should be placed in four consecutive ROM locations having the highest memory address and having a lowest memory location that is addressable by an address that is a mathematical multiple of four (i.e., k=2.sup.n =4 aligned instructions). Accordingly, the instructions C-F are placed in ROM locations 2040-2043, respectively, as indicated by reference arrow 206a, where the first location beginning the sequence is addressable by an address 2040 that is a mathematical multiple of four.

As shown, after recognizing another NEXT.sub.-- STATE statement, the assembler system 180 analyzes the instruction G, which it concludes is a nonaligned instruction. In this case, the assembler system 180 places the instruction G at the next consecutive location at the low end of memory, or in this case, location 2.

The next code fragment to be recognized by the assembler system 180 is an ALIGN.sub.-- 2 statement. This indicates that the next two consecutive instructions are aligned. When only two instructions are aligned, four locations are allocated, two of which are immediately used, the other two of which await the next set of two aligned instructions. In this case, the highest set of four locations where the first location of the set is addressable by an address that is a multiple of four is 2044-2047. In accordance with the normal rule of the methodology, the next two instructions H, I would normally be stored in the highest two consecutive locations within this set, or in locations 2046, 2047, respectively. However, in this example implementation, location 2047 is allocated to storing CRC and date information. Therefore, in this exceptional circumstance, the instructions H, I are placed in the lowest two consecutive locations 2044, 2045, respectively, of the four location set, as indicated by reference arrow 206b.

The next code fragment to be recognized and analyzed by the assembler system 180 is an ALIGN.sub.-- 2 statement. This indicates to the assembler system 180 that the next two consecutive instructions J, K are aligned instructions. In this case, a next set of four locations having the highest memory addresses and having a lowest location that is a multiple of k (4 in this case) is identified as locations 2036-2039. Locations 2038, 2039 are used for storing the instructions J, K, as indicated by reference arrow 206c, and locations 2036, 2037 are saved for a later set of two aligned instructions.

After recognizing another NEXT.sub.-- STATE statement, the assembler system 180 retrieves instruction L, assumes that it is a nonaligned instruction, and stores it within the ROM location having the lowest memory address, i.e., location 3.

The assembler system 180 next recognizes the code fragment ALIGN.sub.-- 4. This align statement indicates that the next four instructions M-P are aligned instructions. Accordingly, the assembler system 180 seeks another four consecutive locations having the highest memory addresses and a first location in this set that is addressable with an address that is a multiple of k (4 in this case). In this example, the instructions M-P are stored in locations 2032-2035, as indicated by reference arrow 206d.

Next, the assembler system 180 recognizes another NEXT.sub.-- STATE statement and takes nonaligned instruction Q and places it in the location having the lowest ROM memory address, i.e., location 4.

After yet another NEXT.sub.-- STATE statement, the assembler system 180 retrieves another ALIGN.sub.-- 2 statement. Accordingly, it retrieves subsequent instructions R and S, as denoted by respective NEXT.sub.-- STATE statements, and places them in respective ROM locations 2036, 2037, which were left remaining in the four location set that was identified previously when the two aligned instructions J and K were assembled. This operation is indicated by reference arrow 206f.

The foregoing methodology continues until all of the instructions in the source code 182 are analyzed and stored within the ROM 101.

In concluding the detailed description, it should be noted that it will be obvious to those skilled in the art that many variations and modifications may be made to the preferred embodiment and specific examples without substantially departing from the principles of the present invention. All such variations and modifications are intended to be included herein within the scope of the present invention, as set forth in the following claims. Further, in the claims hereafter, any "means" element is defined to include any structure(s) or material(s) for performing any specified function(s) to the extent that such inclusion does not render the claim invalid.