US 4,449,201 AGrant
Geometric Processing System Utilizing Multiple Identical Processors
Issue Date:1984-05-15
•6 Claims
•7 Drawing Sheets
Abstract
A graphic display system uses a plurality of identical processor units each of which is controlled by microcode to perform a particular function in transforming, clipping, and scaling geometric data for presentation on a display. Each processor includes a plurality of function units which can operate independently, in parallel, or in master-slave mode. Each function unit comprises a plurality of one bit slice circuits which can be fabricated using VLSI techniques. Each one bit slice includes a multilevel memory which collectively provide a dispersed stack for the function unit.
Metadata
Assignee
- The Board of Trustees of the Leland Stanford Junior University
Inventor
- James H. Clark
Application Information
Application Number:US 2590174
Filing Date:1981-04-30
Priority Date:1981-04-30
Art Unit:236
Classifications
IPC:
G06F 1520
Field of Search:
364200 MS File;900 MS File;515;518;521;754;718;748
Patent Drawings (7 sheets)
Description
Background of the Invention
This invention relates generally to computer-controlled graphic display systems, and more particularly the invention relates to a processor and graphic system which utilizes the processor.
In graphic systems where geometric data is utilized for the presentation of images on a display, basic functions include coordinate transformation of the geometric data, clipping the transformed data to the boundaries of a viewing window, and scaling the clipped data to a rectangular region of the destination drawing device or display surface. For realtime graphics, special-purpose data processors or digital computers are required to timely handle the computation intensive tasks.
Special-purpose digital computers have been available in recent years for performing the requisite computation in graphic display systems. However, present commercially available computers for graphics processing are complex and expensive compared to architectures that could be structured to optimally utilize state of the art semiconductor processing techniques including very large scale integration (VLSI).
For maximum utilization of VLSI processing, the computer architecture must comprise a simple, repeating circuit configuration. Further, parallelism of compution capability should be available to maximize computation speed. Present commercially available systems do not fully utilize these capabilities.
Summary of the Invention
Accordingly, an object of the invention is a graphic display system which utilizes a plurality of identical processor units which are readily structured for different computational tasks.
Another object of the invention is an improved processor for use in graphic display systems.
Still another object of the invention is a graphic display processor which is readily implemented using VLSI techniques.
Yet another object of the invention is a processor which comprises a plurality of function units for parallel data processing.
Another object of the invention is a graphics processor including a plurality of function units each of which comprises repetitive circuit blocks for the collective operation on digital data.
A feature of the invention is a bit slice circuit for operating on one bit of digital data.
Another feature of the invention is a function unit comprising a plurality of bit slices for operating on digital data in accordance with a microcode.
Another feature of the invention is the use of two of these function units for simultaneously operating on the two parts of floating-point data: a mantissa unit and a characteristic unit.
Yet another feature of the invention is a bit slice circuit including a multilevel memory whereby a computer comprising the bit slice circuits has a dispersed stack.
Briefly, in accordance with the invention a graphic display processing system is provided for transforming coordinates of geometric data, clipping the geometric data for selected viewing, and scaling the clipped data for presentation on a viewing screen. Each of the functions is achieved by a plurality of architecturally identical processors which are selectively controlled to implement the desired function.
More particularly, a processor in accordance with the invention and which may provide any of the functions in a graphic display system comprises a plurality of identical function units which can be independently operated, operated in parallel, or operated in a master-slave mode. Each function unit comprises a plurality of one bit slice circuits each including arithmetic logic means for operating on a bit of data and with each one bit slice circuit interconnected with at least one adjacent one bit slice circuit for cooperatively operating on a next most significant bit of multiple bit data.
In accordance with another feature of the invention each one bit slice circuit includes a multiple level storage means which cooperatively function as a dispersed data stack for the function unit. The arithmetic logic unit has two inputs and one output. A first bus and a second bus are provided to the first and second inputs of the ALU, respectively, and a third bus is provided to the ALU output.
An upshifting register having an input and an output is operatively connected to receive a data bit from a lower order circuit and transfer the data bit to the first bus, and the upshifting register is also operatively connected to receive a data bit from the third bus and transfer the data bit to a higher order circuit.
Similarly, a downshifting register has an input and an output operably connected to receive a data bit from a higher order circuit and transfer the data bit to the second bus, with the downshifting register also interconnected to receive a data bit from the third bus and transfer the data bit to a lower order circuit.
An accumulator register is interconnected between the third bus and the first bus for accumulating a data bit from the ALU output and reapplying the data bit to the first input of the ALU. An interface register is connected to the second bus for transferring a data bit from an input-output bus to the second bus.
By operating a plurality of one bit slice circuits together, a multiple bit data word can be selectively manipulated under microcode control.
The invention and objects and features thereof will be more readily apparent from the following detailed description and appended claims when taken with the drawings.
Brief Description of the Drawings
FIG. 1 is a pictorial representation of the functions of a graphic display system in receiving and presenting geometric data to a display.
FIG. 2 is a functional block diagram of a graphic display system utilizing a plurality of identical processors in accordance with the present invention.
FIG. 3 is a functional block diagram of a graphics processor in accordance with the present invention.
FIG. 4 is a functional block diagram of a portion of a function unit in the processor of FIG. 3.
FIG. 5 is a functional block diagram of a one bit slice circuit as used in the function unit of FIG. 4.
FIG. 6 is a detailed circuit diagram of the one bit slice circuit of FIG. 5.
FIGS. 7A-7C illustrate the operation of the function units of the processor of FIG. 3 in carrying out the functions illustrated in FIG. 1.
Detailed Description of the Preferred Embodiment
System Overview
The operation of a graphics display system in accordance with the invention is illustrated pictorially in FIG. 1. Objects defined geometrically in a first coordinate system are received and transformed to a second coordinate system which is compatible with the display system. For example, the object 10 defined in X, Y, and Z coordinates is transformed and rotated into a virtual display coordinate system. After transformation of the coordinates, a viewing window 12 is defined in the virtual drawing space whereby the transformed objects mapped in the drawing space are restricted to the window by clipping or removing data which fall outside of the viewing window. For example, assuming that the object 10 is mapped completely within the window 12, all of object 10 will be displayed. However, an object 14 which lies both within the viewing window 12 and outside of the window will be clipped at the plane which defines the left side of window 12. An object 16 which lies completely outside of the viewing window will be clipped in its entirety and not displayed. For two dimensional objects, the clipping requires four separate operations, namely the left plane, the right plane, the top plane, and the bottom plane. For a three dimensional presentation two additional operations may be added for the front and back viewing planes.
Thereafter, the viewing window and objects defined therein must be scaled to the viewport of the destination display device 20. Thus, if the viewing window 12 is to occupy less than all of the viewing space 20 then the coordinates must be reduced in scale and defined for the portion of the display 20 where the window and objects therein are to be displayed.
FIG. 2 is a functional block diagram of a graphics display system in accordance with one embodiment of the present invention for carrying out these functions. In this embodiment the system comprises 12 architecturally identical processors with four processors 21-24 performing the matrix transformation, six processors 25-30 performing the clipping, and two processors 31, 32 performing the scaling of geometric data. As will be described further hereinbelow, each processor is provided with the microcode for performing any of the requisite functions, and configuration registers are provided to define the microcode and hence the function for each processor.
Algorithms required for performing the transformation, clipping, and scaling functions are knwon. See for example Giloi, Interactive Computer Graphics Datastructures, Algorithms, Languages, Prentise Hall Inc, 1978, pages 84-107 and Newman and Sproull, Introduction to Computer Graphics Addison-Wesley, 1979, pages 333 and 342, As disclosed by Giloi, a convenient way to accomplish two, three or four dimensional coordinate transformation is with a four by four matrix. The matrix allows the combined transformations of rotation, scaling, translation and perspective, all by one single matrix multiplication. The matrix multiplication operation is expressed as four simultaneous dot-product operations, one for each column of the 4.times.4 transformation matrix. That is, the operation ##EQU1## is accomplished by four dot-product units. Processor 21 performs the dot-product of [x y z w] with [a.sub.x b.sub.x c.sub.x d.sub.x ] to produce x', processor 22 performs the dot-product of [x y z w] with [a.sub.y b.sub.y c.sub.y d.sub.y ] to produce y'. Similarly, processor 23 produces z' and processor 24 produces w'.
Processor 21 holds a stack of [a.sub.x b.sub.x c.sub.x d.sub.x ] values. The top of this stack is the "current" first column of the matrix. Similar stacks are provided for processors 22-24 for the y, z, and w columns, respectively. Commands provide for pushing the top of this stack down, PUSHMM, popping the level of the stack by one, POPMM, loading a new column onto the stack, LOADMM, and multiplying the existing matrix on the top of the stack by a new incoming matrix. All of these commands are described in the microcode, infra.
As discussed by Newman and Sproull, the four by four matrix allows rotations, scaling, translations, and a number of other transformations to be done with a single entity. It also conveniently handles two and three dimensional objects, and two successive transformations can be composed by a single multiplication of the transformation matrices. Four processors can transform an incoming four component vector into a four component vector expressed relevant to a coordinate system that is fixed to the observer.
After transformation, the geometric data is clipped by the use of an algorithm that determines which part of the data lies within window boundaries. For points, if the point is inside the screened area it is displayed; otherwise it is suppressed. For lines, there are several possibilities: the line is totally in, totally out, or part in and part out. The clipping operation is to determine which of these cases apply and if it is the last, determine the points where the line enters the window, or crosses the plane in question. This "clipping" operation is done by a logarithmic search for the point of intersection of the line segment and the plane. See Knuth, Donald E., Sorting and Searching, Vol. III, Addison-Wesley Publishing Company, 1973, page 422.
For three dimensions the window is a set of planes that extend outwardly from the eye of the observer; these planes can be thought of as extending through the rectangle defined by a two dimensional boundary with the window representing the part of the picture that is to be mapped onto the destination display. The six processors 25-30 hold the plane equations for the end points of a line with the sign of the plane equation for each point telling which side of the plane the point is on. By convention, this sign is chosen to be negative if the point is on the "outside"of the plane, meaning that it is not visible to the observer because it is outside of the window. Thus, a line segment having both signs negative is completely out of the viewing area while one having both signs positive is completely in the viewing area. The function of the clipper is to discard segments that are completely outside of its plane, pass segments that are completely inside, or find the point of intersection of the segment with the plane and pass results. Assuming a three dimensional representation, the six processors 25-30 are required for testing line segments against the left and right planes of the window, the top and bottom planes of the window, and the front and back planes of the window. When a segment crosses a plane, the processor finds the intersection point by a logarithmic search for the point. That is, on each microcycle each of the four units (the plane equation unit and the three coordinate units) computes the midpoint of its representation of the line. Choosing one of the end points as a reference point, it then determines if the midpoint is on the same side of the plane as this point. If so, then the reference point is updated by moving it to the midpoint. This is repeated until the precision of the mantissa is reached. A similar algorithm is disclosed by Sproull and Sutherland, "A Clipping Divider," Proceedings of the FJCC, 1968.
The function of scaling is accmplished by the two processors 31 and 32. The scaling operation scales objects remaining after clipping from the window to a viewport, which is expressed in the integer coordinate system of the destination display. In three dimensions, both perspective division and scaling to destination device coordinates simultaneously take place. In two dimensions only scaling is done. The perspective division/scaling operation requirement can be accomplished for two coordinates in a single processor in accordance with the invention. However, for three dimensional scaling the second processor is required. For example, the scaling operations for the coordinates are given as ##EQU2##
A processor behaving as a scaling processor requires two of the computation units, one to accomplish the divide operation, e.g. x/w, and the other to accomplish the multiplication of this quotient with V.sub.sx. Rather than do the complete divide before doing the multiply, however, each bit of the quotient, starting with the most significant bit, is used to govern the addition of the successive partial products in accumulating the product, as discussed by Sproull & Sutherland, supra.
Processor
Having now described an overview of the graphics display system and functions thereof, consider now a processor in accordance with the invention for use in the system. FIG. 3 is a functional block diagram of the processor which comprises four identical function units labeled W (40-41), X (42-43), Y (44-45), and Z (46-47) with each function unit including a characteristic portion (8 bits) and a mantissa portion (24 bits). As will be described further hereinbelow, each function unit comprises a plurality of one bit slice circuits, 48 each for operating on a bit of the characteristics or the mantissa. The particular function of the processor is defined by a characteristic and control flow program logic array 50 and a mantissa program logic array 52. While shown as separate units, PLA 50 and PLA 52 can be a single unit. ALU decoders 51 and 53 receive the microcode from PLA 50 and PLA 52, respectively, and provide the control to the W, X, Y, and Z function units through drivers 54 and 56. Input pads 58 provide data through input registers 59 to the function units, and data is transferred from the function units through output registers 60 to output pads 61.
Data are presented at the 16 input pins 58 connected to input registers 59. Then an input request is made by raising the request flag Rin. A four-cycle "handshake" is completed by the clock circuit, as described in Chapter 7 of Mead & Conway, Intro. to VLSI Systems, Addison-Wesley Publishing Company, 1980. First, the high order bits are latched into the 16 bits of 59. On the next microcycle, all 32 input bits, the 16 high-order bits plus the input pin values, are transferred over the B bus (I/O bus) to the appropriate computing unit, w(40,41), x(42,43), y(44,45) or z(46,57).
On output, data are transferred via the B bus to the output registers 60. On the first cycle, the high order 16 bits are presented at the output pins 61 and a 4-cycle handshake for output is initiated. Then the low order bits of 60 are transferred to 61.
Each computing unit consists of two identical function units with different numbers of bits, e.g. the X computing unit is the 8-bit characteristic function unit 43 and the 24-bit mantissa function unit 42.
The ALU decoders 53 receive a 4-bit code and generate 3-bit values for driving the control lines of the mantissa ALU's in 40-46 (even). Likewise, decoders 51 receive a 4-bit code for generating the control signals of 41-47 (odd).
Function Units
As indicated above, each function unit comprises a plurality of one bit slice circuits with each circuit operating on one bit of a data word. FIG. 4 is a functional block diagram of a portion of a function unit showing four one bit slices 71-74 with each slice including a multi-level storage or stack, a plurality of registers, and an arithmetic logic unit (ALU). The ALU is conventional as described by Mead and Conway, Introduction to VLSI Systems, Boston: Addison Wesley 1980. Carry chains are provided between adjacent one bit slice circuits as required for the next most signifcant bit and the next least significant bit, respectively. PLA control of the function unit is accomplished through stack drivers 76 which control push and pop operations of the stack, a Q source decoder 77, a P bus enable 78, and an ALU function decoder 79. Signals from the function units to the PLA, designated Nu (normalize up) and Nd (normalize down) are provided through a PLA 80 (designated normalize PLA), and a sign function PLA 81 controls the sign signal. Each one bit slice is connected to a common bus designated B bus.
Each of the four Characteristic Function Units and each of the four Mantissa Function Units has the following behavior. However, the Nu and Nd (Normalize Up and Normalize Down) and UZero outputs of the characteristic units are not used by the Control.
During each microcycle of the machine, signals come out of the Control PLA that drive each of the inputs to the function unit shown. That is, each of the following inputs are driven on each microcycle:
Push--push the output of the ALU onto the Data Stack.
Pop--pop the data stack.
Qsource[1:0]--enable one of (Stack, Bbus, or D) onto Q bus.
Psource--enable one of A or U onto P bus.
ALU OpCode[3:0]--selects one of the 9 ALU functions:
P plus Q
P minus Q
Minus P plus Q
Pass P
Pass Q
P minus 1
Q minus 1
Minus P
Minus Q
PokeSave-Save the current sign bit of the ALU in SaveBit
Select[1:0]-select one of the sign functions:
Same-Sign=(SignBit=SaveBit).
Sign-Sign=SignBit.
Save-Sign=SaveBit.
R to B-Transfer the ALU output to the Bbus.
Each microcycle of the machine, a function unit generates the following inputs to the PLA:
Nu-Normalize up=(A and B and C') or (A' and B' and C)
Nd-Normalize down=(A and B') or (A' and B).
Sign--the sign according to Select given above
Uzero=1 if the uregister is all zero bits.
One Bit Slice
FIG. 5 is a block diagram of one of the one bit slices which comprise the function unit. The circuit includes the ALU 80 having a first input (P) and a second input (Q) and one output (R). A first bus 81 is provided to the P input and a second bus 82 is provided to the Q input. A third bus 83 is connected to the ALU output. The multiple level stack 84 has an input connected to the bus 83 for receiving data from the ALU output, and the stack has an output connected to the bus 82 for loading the Q input of ALU 80. An upshifting register 85 is connected to the bus 83 for transferring data to the next most significant bit slice circuit, and register 85 is connected to receive data from the next lower significant bit circuit for application to bus 81. Similarly, a downshifting register 86 is connected to receive a bit from the next most significant slice circuit for transfer to bus 82, and the register 86 also is connected to receive data from bus 83 for transfer to the next lower significant bit circuit. An accumulator register 87 is connected to bus 83 for reapplying data to input bus 81, and an isolation register 88 is connected to the common B bus for transfer of external data to bus 82.
FIG. 6 is a detailed circuit diagram of the one bit slice illustrated in FIG. 5 and further illustrates the registers (comprising serially connected inverters) and the signal designations for control of the registers, the stack, and the ALU. The same numerals are used for like elements in FIG. 5.
Operation of the bit-slice is illustrated by a simple example such as causing the Accumulator to have one added to it. At the beginning of phase 2 of the clock (phi 2), the value of the accumulator is enabled onto the P bus via A to P (89). During this phase of the clock, the carry-chain of the ALU is also precharged (90), the value of the P bus is latched into the input register of the ALU, and the ALU function code (P plus 1) is enabled to the ALU function drivers (91). Then the phi 1 phase of the clock is enabled, during which the ALU generates the sum, and at the end of this phase of the clock, the output of the ALU is enabled via 92 onto the R bus. The result is then loaded into the accumulator via poke A (93) on the next phase 2 of the clock phi 2. The clock may stop any time during phase 1, and 94 ensures that the accumulator's contents are kept static.
Function Unit Operation
FIGS. 7A-7C illustrate the operation of the four computation units of each processor in carrying out the coordinate transformations, clipping, and scaling. In FIG. 7A the transformation is accomplished by the four by four matrix multiplication with each function unit X, Y, Z, W operating independently in carrying out the matrix multiplication. The parallelism capability of the function units of the processor working independently decreases the time requirement in performing the transformations. As part of the transformation, each processor uses the four function units to perform a dot product of the two four component vectors. One of the four component vectors is the graphical input point that is to be transformed from the object's definition coordinate system into the user's virtual drawing space, while the other is one column of a four by four matrix that specifies how the incoming vector is to be transformed. This column of the matrix is held on the top of the push down stack for the computing element. The transformation units collectively hold the four columns of the matrix on the tops of the pushdown stacks. The primary operation of the processor acting as a transformation unit is the dot product operation. In addition, transformation units interpret commands to be passed on to the clipping and scaling units, commands that push and pop the top of the matrix stack, and commands that allow passage of the current matrix stack to the clipping and scaling units for temporary stack overflow. All of these operations are accomplished by the control circuitry which is stored in the control program logic arrays.
In FIG. 7B the clipping function is accomplished by three of the computation units operating as slaves to one control computation unit. The clipping operation involves determining the point of intersection of a line segment with a plane. Because the clipping operation is preceded by the transformation operation, the line whose intersection is to be computed is transformed into a coordinate system in which the expression of the plane is very simple. After trnsformation, the planes against which the line is tested have the equations:
The only difference between the six clipping units is the particular point of the control circuitry that does the computation. Depending upon the processor's configuration register, the computer computes one of the plane equations given above for each end point of the line and stores the result in the W function unit. In general, the results of any of the above computations is not 0 because neither end point of the line segment will lie on the plane in question. The sign of the plane equation value stored in the W function unit indicates the side of the plane on which the end point lies. If both end points are on the same side of the plane then the segment is either completely inside the window or completely outside the window. If the end points are completely outside of the window, the clipping unit no longer considers the line segment and returns to its input state awaiting the next line segment or end point in a string of line segments. If the line segment is completely inside the window, the line segment is passed on to the next clipping unit or to the scaling subsystem.
If the line segment crosses the plane, the point of intersection is computed by the control circuitry as specified by a set of commands, and the resulting endpoints that are inside the window are passed onto the next unit. After passing through all clipping units the resulting segment will lie completely within the window and can be passed on to the scaling unit.
FIG. 7C illustrates the scaler operation in which two computation units provide control and two computation units operate under that control. Two computation units are required for each of the coordinates being scaled. Because each processor has four computation units, one processor is used to simultaneously scale two coordinates. Thus, in two dimensional systems only one processor is required, whereas in a three dimensional system two processors are required.
The scaling operation simultaneously projects the end points of line segments onto the viewing window and maps the floating point coordinates supplied at the input into integer coordinates relative to the coordinate system of the destination display device. The graphic objects that lie within the window are mapped to a rectangular area of the destination device, or the viewport. The size and location of the viewport are specified by the viewport registers. Viewport registers, stored in the pushdown stacks of the function units, specify the location and size of the viewport.
Microprogramming
The processor in accordance with the invention is a quasi general purpose, four-component vector function unit which is driven and controlled by microcode. The microcode is a representation of the logic equations in finite state language which are implemented in the logic circuitry of the program logic array (PLA). Attached hereto and incorporated by reference is a printout of the microcode for a processor in accordance with the invention which is written using the SLIM program language developed at Stanford University.
The microcode defines the behavior of the preferred embodiment. It is written in SLIM [Hennessy, John L., "A Language for Microcode Description and Simulation in VLSI", CSL Technical Report No. 193 Dept. of Electrical Engineering]. The first section is the "Environment." The second section is the actual microcode.
The main body of the microcode is identified by principal blocks marked A-X for further clarification. Block A illustrates most of the characteristics. Each block is described below.
Block A--These first few micro-instructions are executed only once each time the graphics processor is RESET. They cause the configuration register to be loaded.
1. The first line of A is used to gather simulation statistics and plays no role in the behavior of the processor.
2. The second line has three commands that define three different values in the control PLA:
Enable (Data Input)--cause the clock circuit to stop in phi 1 until an input Request, Rin, is presented. After the request is presented, the next phase, phi 2, is issued.
Poke (In Type)--cause the Configuration Register to be loaded with the low-order 6-bits of the input pins.
3. The third line enables the input registers to the B bus and calls the microcode subroutine that passes the remaining configuration register values for the remaining processors in the pipeline. Then Block B is entered.
Block B--Input a command, decode it and transfer to the appropriate block of Microcode.
1. The first line enables loading of the Command Register and the Input Register.
2. The next state (enclosing set of "[" and "]") transfers to an appropriate block of Microcode depending upon the command type.
3. The next line causes the command to be ignored if it is unrecognized.
Block C--Pass 16-bit data values through the processor unaltered.
1. Output the pass command itself only if not the last processor in the pipeline (Scale XY).
2. Enable the pass count to the B bus, call the PASSN microsubroutine.
3. Go to Start state.
4. Enable B bus to characteristic Q bus, Load A (accumulator) of w-characteristic function unit with pass count from B bus, test is count is negative and conditionally return.
5. In a single state loop, successively counting down the A register of the w-characteristic function unit until negative, pass the 16-bit value at the input pins to the output pins. Return from subroutine when count of A register goes negative.
Block D--This microcode block causes the viewport registers to be loaded if the processor is a scaler type. Otherwise, the command and data are passed through the processor.
Block E--This block is used if the input command is either a move or draw instruction and the processor is a scaling unit. The microcode prepares the input values to be scaled.
Block F--This block aligns exponents by shifting the dividend.
Block G--This is a 1-state loop that does the simultaneous multiply and divide.
Block H--This block adds the viewport offset, e.g. V.sub.cx, to the product obtained.
Block I--This block outputs the values obtained.
Block J--Load a new, incoming matrix to the top of the matrix stack.
Block K--Store the current matrix to the output.
Block L--Microcode to push and pop the matrix stack.
Block M--Multiply the present matrix at the top of the stack with the incoming matrix. Leave the result on the top of the stack.
Block N--Do a Move or Draw Command as a matrix transformer processor.
Block O--Do Move Command as a clipping unit.
Block P--Do a Draw Command as a clipping unit.
Block Q--Logic to assist in clipping polygons.
Block R--Rearrange stack for output.
Bock S--Actual clipping micro-subroutine in which the logarithmic search in the plane intersection point is done.
Block T--Preadd subroutine used extensively to align exponents for adding or subtracting vectors.
Block U--Input/Output micro-routines.
Block V--Micro-routine to compute the value of the plane equation to be loaded into the w computing unit.
Block W--Dot-product micro-routine, used extensively by transformation processors.
Block X--Normalize micro-routine, used extensively to renormalize floating point numbers after arithmetic operations.
Summary
A graphic display system utilizing a plurality of processors operating under microcode control has been described. The processor comprises a plurality of function units which can be operated independently, in parallel, or in master-slave modes and each function unit comprises a plurality of simple one bit slice circuits which are readily fabricated using VLSI techniques. The multilevel memories of the bit slice circuits cooperatively function as a dispersed stack.
While the invention has been described with reference to a specific embodiment, the description is illustrative of the invention and is not to be construed as limiting the invention. Various modifications and applications may occur to those skilled in the art without departing from the true spirit and scope of the invention as defined by the appended claims. ##SPC1## ##SPC2## ##SPC3## ##SPC4## ##SPC5## ##SPC6##
Claims
What is claimed is:
1. A processor for use in a geometric processing system comprising a plurality of identical function units, each of said function units operating on multiple bit data and comprising a plurality of one bit slice circuits each including arithmetic logic means for operating on a bit of said data with each of one bit slice circuit interconnected with like circuits including at least one lower order circuit for operating on a lower order bit an at least one higher order circuit for operating on a higher order bit of said multiple bit data, each of said one bit slice circuits including a multiple level storage means which cooperatively functions as a dispersed data stack for said function unit, each one bit slice circuit comprising a single bit arithmetic logic unit having a first ALU input, a second ALU input, and an ALU output, a first bus for transferring a data bit to said first ALU input, a second bus for transferring a data bit to said second ALU input, a third bus for transferring a data bit from said ALU output, an upshifting register having an input and first and second outputs, said input operably connected to receive a data bit from a lower order circuit and said first output transferring the data bit to said first bus, and said first input operably connected to receive a data bit from said third bus and said second output transferring the data bit to a higher order circuit, a downshifting register having an input and first and second outputs operably connected to receive a data bit from a higher order circuit and transferring the data bit to said second bus, and said first input operably connected to receive a data bit from said third bus and said second output transferring the data bit to a lower order circuit, an accumulator register interconnected between said third bus and said first bus for receiving a data bit from said ALU output and applying said data bit to said first ALU input, an interface register connected to said second bus for transferring a data bit from an input/output bus to said second bus, and a multiple level register interconnected with said second and said third bus for saving and restoring bits for processing, and control means for controlling said function units to cooperatively provide at least a portion of one of the functions including matrix transformations, clipping and scaling functions.
2. A geometric processing system for receiving geometric data, transforming coordinates of said geometric data, clipping said transformed data for selective presentation on a viewing screen, and scaling said data for presentation on said viewing screen, comprising a first plurality of processor units for transforming coordinates of said geometric data, a second plurality of processors operably connected with said first plurality of processor units for receiving and clipping transformed coordinates for selective viewing of the geometric data, and a third plurality of processorss operably connected with said second plurality of processor units for scaling said clipped data, each of said processor units comprising a plurality of function units, each of said function units operating on multiple bit data and comprising a plurality of one bit slice circuits each including arithmetic logic means for operating on a bit of said data with each of one bit slice circuit interconnected with like circuits including at least one lower order circuit for operating on a lower order bit and at least one higher order circuit for operating on a higher order bit of said multiple bit data, each of said one bit slice circuits including a multiple level storage means which cooperatively function as a dispersed data stack for said function unit, and control means for controlling said function units to cooperatively provide at least a portion of one of the functions including matrix transformations, clipping, and scaling functions.
3. A geometric processing system as defined by claim 2 wherein each one bit slice circuit comprises a single bit arithmetic logic unit having a first ALU input, a second ALU input, and an ALU output, a first bus for transferring a data bit to said first ALU input, a second bus for transferring a data bit to said second ALU input, a third bus for transferring a data bit from said ALU output, an upshifting register having an input and first and second outputs, said input operably connected to receive a data bit from a lower order circuit and said first output transferring the data bit to said first bus, and said first input operably connected to receive a data bit from said third bus and said second output transferring the data bit to a higher order circuit, a downshifting register having an input and, first and second outputs operably connected to receive a data bit from a higher order circuit and transferring the data bit to said second bus, and said first input operably connected to receive a data bit from said third bus and said second output transferring the data bit to a lower order circuit, an accumulator register interconnected between said third bus and said first bus for receiving a data bit from said ALU output and applying said data bit to said first ALU input, an interface register connected to said second bus for transferring a data bit from an input/output bus to said second bus, and a multiple level register interconnected with said second and said third bus for saving and restoring bits for processing.
4. A processor for use in a geometric processing system comprising a plurality of identical floating point function units (W, X, Y, Z), each function unit including a first portion for operating on the mantissa of a floating point number and a second portion for operating on the characteristic of a floating point number, each portion of a function unit including a plurality of identical circuits for operating on multiple bit data, each circuit comprising an arithmetic logic unit having a first ALU input, a second ALU input, and an ALU output, a first bus for transferring data to said first ALU input, a second bus for transferring data to said second ALU input, a third bus for transferring data from said ALU output, an upshifting register having an input and first and second outputs, said input operably connected to receive data from a lower order circuit and said first output transferring the data to said first bus, and said input operably connected to receive data from said third bus and said second output transferring the databit to a higher order circuit, a downshifting register having an input and first and second outputs, said input operably connected to receive data from a higher order circuit and said first output transferring the data to said second bus, and said input operably connected to receive data from said third bus and said second output transferring the data to a lower order circuit, an accumulator register interconnected between said third bus and said first bus for receiving data from said ALU output and applying said data to said first ALU input, an interface register connected to said second bus for transferring data from an input/output bus to said second bus, a multiple level register interconnected with said second and said third bus for saving and restoring data for processing, and control means for controlling said function units to cooperatively provide at least a portion of one of the functions including matrix transformations, clipping, and scaling functions.
5. A geometric processing system having multiple identical pipelined processors for receiving geometric data, transforming coordinates of said geometric data, clipping said transformed data, and scaling said clipped data, said system comprising a first plurality of serially connected processors for receiving and transforming coordinates of said geometric data, a second plurality of serially connected processors serially connected with said first plurality of serially connected processors for receiving and clipping transformed coordinates, and a third plurality of serially connected processors serially connected with said second plurality of serially connected processors for scaling said clipped data, each of said processors comprising a plurality of function units (W, X, Y, Z), each function unit including a first portion for operating on the mantissa of a floating point number and a second portion for operating on the characteristic of a floating point number, and control means for controlling said function units to cooperatively provide at least a portion of one of the functions including matrix transformations, clipping, and scaling functions.
6. The system as defined by claim 5 wherein each portion of a function unit includes a plurality of identical circuits for operating on multiple bit data, each circuit comprising an arithmetic logic unit having a first ALU input, a second ALU input, and an ALU output a first bus for transferring data to said first ALU input, a second bus for transferring data to said second ALU input, a third bus for transferring data from said ALU output, an upshifting register having an input and first and second outputs, said input operably connected to receive data from a lower order circuit and said first output transferring the data to said first bus, and said input operably connected to receive data from said third bus and said second output transferring the data bit to a higher order circuit, a downshifting register having an input and first and second outputs, said input operably connected to receive data from a higher order circuit and said first output transferring the data to said second bus, and said input operably connected to receive data from said third bus and said second output transferring the data to a lower order circuit, an accumulator register interconnected between said third bus and said first bus for receiving data from said ALU output and applying said data to said first ALU input, an interface register connected to said second bus for transferring data from an input/output bus to said second bus, and a multiple level register interconnected with said second and said third bus for saving and restoring data for processing.
Patent Citations (9)
Non-Patent Literature (11)
- "Bit-Sliced Microprocessor Architecture," N. A. Alexandridas, Computer, pp. 56-76, Jun. 1978.
- "Instance Rectangles and Picture Structure," W. M. Newman, Proceedings of the Conference on Computer Graphics, Pattern Recognition and Data Structure, May 1975, pp. 297-301.
- "A Three Dimensional Display Processor Design, Stowell and Garrett, Proceeding of the Conference on Computer Graphics," Pattern Recognition and Data Structure, May 1975, pp. 157-162.
- "Reentrant Polygon Clipping," Communication of the ACM, vol. 17, No. 1, pp. 32-42, Jan. 1974.
- "Introduction to VLSI Systems", Mead and Conway, Addison-Wesley Publishing Company, 1980.
- "Interactive Computer Graphics, Data Structures, Algorithms, Languages," Prentice-Hall, Inc., 1977.
- "A Clipping Divider," Sproull and Sutherland, Proceedings, Fall Joint Computer Conference, 1968, p. 765.
- "Computer-Aided Design," Clark, Twelfth Annual Meeting, Stanford Computer Forum, Feb. 1980.
- "Structuring a VLSI System Architecture," Clark, Lamda, 2nd Quarter, 1980, pp. 25-30.
- "A VLSI Geometry Processor for Graphics," Clark, Computer, Jul. 1980, pp. 59-67.
- "A VLSI Geometry Engine for Computer Graphics," Clark, Conference on Advanced Research in Integrated Circuits, Jan. 28-30, 1980, M.I.T.