Thread optimized multiprocessor architecture

Cross Reference to Related Applications

0001This application claims priority to <patcit id="pcit0001" dnum="US76495506P"><text>U.S. Provisíonal Patent Application No. 60/764,955, filed February 3, 2006</text></patcit>. The entire contents of that provisional application are incorporated herein by reference.

Background and Summary

0002Computer speed may be increased using two general approaches: increase instruction execution speed or do more instruction execution in parallel. As instruction execution speed approaches the limits of electron mobility in silicon, parallelism becomes the best alternative to increasing computer speed.

0003Previous attempts at parallelism have included: <ol id="ol0001"><li>1. Overlapping next instruction fetching with current instruction execution.</li><li>2. Instruction pipelining. An instruction pipeline breaks each instruction into as many pieces as possible and then attempts to map sequential instructions into parallel execution units. Theoretical maximum improvement is seldom achieved due to the inefficiencies of multi-step instructions, inability of many software programs to provide enough sequential instructions to keep the parallel execution units filled, and the large time penalty paid when a branch, loop, or case construct is encountered requiring the refilling of the execution units.</li><li>3. Single instruction multiple data or SIMD. This type of technique is found in the Intel SSE instruction set, as implemented in the Intel Pentium 3 and other processors, In this technique, a single instruction executes on multiple data sets. This technique is useful only for special applications such as video graphics rendering.</li><li>4. Hypercube. This technique employs large two-dimensional arrays and sometimes three-dimensional arrays of processors and local memory. The communications and interconnects necessary to support these arrays of processors inherently limits them to very specialized applications.</li></ol>

0004A pipeline is an instruction execution unit consisting of multiple sequential stages that successively perform a piece of an instruction's execution, such as fetch, decode, execute, store, etc. Several pipelines may be placed in parallel, such that program instructions are fed to each pipeline one after another until all pipelines are executing an instruction. Then the instruction filling repeats with the original pipeline. When N pipelines are filled with instructions and executing, the performance effect is theoretically the same as an N times increase in execution speed for a single execution unit.

0005Successful pipelining depends upon the following: <ol id="ol0002"><li>1. An instruction's execution must be able to be defined as several successive states.</li><li>2. Each instruction must have the same number of states.</li><li>3. The number of states per instruction determines the maximum number of parallel execution units.</li></ol>

0006Since pipelining can achieve performance increases based on the number of parallel pipelines, and since the number of parallel pipelines is determined by the number of states in an instruction, pipelines encourage complex multi-state instructions.

0007Heavily pipelined computers very seldom achieve performance anywhere near the theoretical performance improvement expected from the parallel pipeline execution units. Several reasons for this pipeline penalty include: <ol id="ol0003"><li>1. Software programs are not made up of only sequential instructions. Various studies indicate changes of execution flow occur every 8-10 instructions. Any branch that changes program flow upsets the pipeline. Attempts to minimize the pipeline upset tend to be complex and incomplete in their mitigation.</li><li>2. Forcing all instructions to have the same number of states often leads to execution pipelines that satisfy the requirements of the lowest common denominator (i.e., the slowest and most complex) instructions. Because of the pipeline, all instructions are forced into the same number of states, regardless of whether they need them or not. For example, logic operations (such as AND or OR) execute an order of magnitude faster than an ADD, but often both are allocated the same amount of time for execution.</li><li>3. Pipelines encourage multi-state complex instructions. Instructions that might require two states are typically stretched to fill 20 states because that is the depth of the pipeline. (The Intel Pentium 4 uses a 20 state pipeline.)</li><li>4. The time required for each pipeline state must account for propagation delays through the logic circuitry and associated transistors, in addition to the design margins or tolerances for the particular state.</li><li>5. Arbitration for pipeline register and other resource access often reduces performance due to the propagation delays of the transistors is the arbitration logic.</li><li>6. There is an upper limit on the number of states into which an instruction may be split before the additional state actually slows down execution, rather than speeds it up. Some studies have suggested that the pipeline architecture in the last generation of Digital Equipment Corporation's Alpha processor exceeded that point and actually performed slower that the previous, shorter pipelined version of the processor.</li></ol>

Splitting Apart the Pipelines

0008One perspective to re-factoring CPU design is to think of pipelined execution units that are then split into multiple (N) simplified processors. (Registers and some other logic may need to be duplicated in such a design.). Each of the N simplified processors would have the following advantages over the above-discussed pipelined architectures: <ol id="ol0004"><li>1. No pipeline stalls, No branch prediction necessity.</li><li>2. Instructions could take as much or as little time as they need, rather than all being allocated the same execution time as the slowest instruction.</li><li>3. Instructions could be simplified by reducing the necessary execution states, thereby reducing the pipeline penalty.</li><li>4. Each state eliminated from the pipeline could eliminate propagation delays and remove design margins necessary for the state.</li><li>5. Register arbitration could be eliminated.</li></ol>

0009Furthermore, a system with N simplified processors could have the following advantages over a pipelined CPU: <ol id="ol0005"><li>1. The limit of maximum pipeline parallelism would be eliminated.</li><li>2. Unlike a pipelined processor, multiple standalone processors could be selectively powered down to reduce power consumption when not in use.</li></ol>

Other Problems with Current Approaches to Parallelism

0010Many implementations of parallelism succumb to the limits of Amdahl's Law. Acceleration through parallelism is limited by overhead due to non-serializable portions of the problem. In essence, as the amount of parallelism increases, the communications necessary to support it overwhelms the gains due to the parallelism.

Stoplight Sitting at Redline

0011Another inefficiency of current processors is the inability of scaling the computing power to meet the immediate computing demand. Most computers spend most of their time waiting for something to happen. They wait for I/O, for the next instruction, for memory access, or sometimes human interface. This waiting is an inefficient waste of computing power. Furthermore, the computer time spent waiting often results in increased power consumption and beat generation.

0012The exceptions to the waiting rule are applications like engine controllers, signal processors, and firewall routers. These applications are excellent candidates for parallelism acceleration due to the predefined nature of the problem sets and solution sets. A problem that requires the product ofN independent multiplications may be solved faster using N multipliers.

0013The perceived performance of a general purpose computer is really its peak performance. The closest a general purpose computer gets to being busy is running a video game with a rapid screen refresh, compiling a large source file, or searching a database. In an optimal world, the video rendering would be factored into special purpose, shading, transforming, and rendering hardware. One method of factoring the programming to such special purpose hardware is the use of "threads."

0014Threads are independent programs that are self contained and infrequently communicate data with other threads. A common use of threads is to collect data from slow realtime activity and provide the assembled results. A thread might also be used to render a change on a display. A thread may transition through thousands or millions of states before requiring further interaction with another thread. Independent threads present an opportunity for increased performance through parallelism.

0015Many software compilers support the generation and management of threads for the purposes of factoring the software design process. The same factoring will support multiple CPU parallel processing via the technique of Thread Level Parallelism implemented in a Thread Optimized Microprocessor (TOMI) of the preferred embodiment.

Thread Level Parallelism

0016Threading is a well understood technique for factoring software programs on a single CPU. Thread level parallelism can achieve program acceleration through use of a TOMI processor.

0017One significant advantage of a TOMI processor over other parallel approaches is that a TOMI processor requires minimal changes to current software programming techniques. New algorithms do not need to be developed. Many existing programs may need to be recompiled, but not substantially rewritten.

0018An efficient TOMI computer architecture should be built around a large number of simplified processors. Different architectures may be used for different types of computing problems.

Fundamental Computer Operations

0019For a general purpose computer, the most common operations in order of declining frequency are: Loads and stores; Sequencing; and Math and logic.

Load and Store

0020The parameters of LOAD and STORE are the source and destination. The power of the LOAD and STORE is the range of source and destination (for example, 4 Gbytes is a more powerful range than 256 bytes). Locality relative to the current source and destination is important for many data sets. Plus 1, minus 1 are the most useful. Increasing offsets from the current source and destination are progressively less useful.

0021LOAD and STORE may also be affected by the memory hierarchy. A LOAD from storage may be the slowest operation a CPU can perform.

Sequencing

0022Branches and loops are the fundamental sequencing instructions. Instruction sequence changes based on a test is the way computers make decisions.

Math and Logic

0023Math and logic operations are the least used of the three operations. Logic operations are the fastest operations a CPU can perform and can require as little as a single logic gate delay. Math operations are more complex since higher order bits depend on the results of lower order bit operations. A 32-bit ADD can require at least 32 gate delays, even with carry lookabead. MULTIPLY using a shift and add technique can require the equivalent of 32 ADDs.

Tradeoffs of Instruction Size

0024The perfect instruction set would consist of op-codes that are large enough to select infinite possible sources, destinations, operations, and next instructions. Unfortunately the perfect instruction set op-codes would be infinitely wide and the instruction bandwidth would therefore be zero.

0025Computer design for high-instruction bandwidth involves the creation of an instruction set with op-codes able to efficiently define the most common sources, destinations, operations, and next instructions with the fewest op-code bits.

0026Wide op-codes lead to high instruction bus bandwidth requirements and the resulting architecture will be quickly limited by the Von Neumann bottleneck, wherein the computer's performance is limited by the speed with which it fetches instructions from memory.

0027If a memory bus is 64 bits wide, one could fetch a single 64-bit instruction, two 32-bit instructions, four 16-bits instructions, or eight 8-bit instructions in each memory cycle. A 32-bit instruction had better be twice as useful as a 16-bit instruction since it cuts the instruction bandwidth in half.

0028A major objective of instruction set design is to reduce instruction redundancy. In general an optimized efficient instruction set takes advantage of the locality of both instructions and data. The easiest instruction optimizations have long since been done. For most computer programs, the most likely next instruction is the sequentially next instruction in memory. Therefore instead of every instruction having a next instruction field, most instructions assume the next instruction is the current instruction + 1. It is possible to create an architecture with zero bits for source and zero bits for destination.

Stack Architectures

0029Stack architecture computers are also called zero operand architectures. A stack architecture performs all operations based on the contents of a push down stack. A two operand operation would require both operands be present on the stack. When the operation executes, both operands would be POP'd from the stack, the operation would be performed, and the result would be PUSH'd back on the stack. Stack architecture computers can have very short op-codes since the source and destination are implied as being on the stack.

0030Most programs require the contents of global registers that may not always be available on the stack when needed. Attempts to minimize this occurrence have included stack indexing that allows accessing operands other than those on the top of the stack. Stack indexing squires either additional op-code bits resulting in larger instructions or additional operations to place the stack index value on the stack itself. Sometimes one or more additional stacks are defined. A better but not optimal solution is a combination stack/register architecture.

0031Stack architecture operation is also often redundant in ways that defy obvious optimizations. For example, each POP and PUSH operation has the potential to cause a time wasting memory operation as the stack is manipulated in memory. Furthermore, the stack operation may consume an operand that may be immediately needed for the next operation, thereby requiring operand duplication with the potential of yet another memory operation. Take for example, the operation of multiplying all the elements of a one dimensional array by 15.

0032On a stack architecture, this is implemented by: <ol id="ol0006" compact="compact"><li>1. PUSH start address of array</li><li>2. DUPLICATE address (So we have the address to store the result to the array.)</li><li>3. DUPLICATE address (So we have the address to read from the array.)</li><li>4. PUSH INDIRECT (PUSH the contents of the array location pointed to by the top of stack)</li><li>5. PUSH 15</li><li>6. MULTIPLY (15 times the array contents we read in line 3)</li><li>7. SWAP (Get the array address on the top of the stack for the next instruction.)</li><li>8. POP INDIRECT (POPs the multiplication result and stores it back to the array.)</li><li>9. INCREMENT (Point to the next array item.)</li><li>10. Go to step 2. until the array is done.</li></ol>

0033The loop counter in line 9 would require an additional parameter. In some architectures, this parameter is stored on another stack.

0034On a hypothetical register/accumulator architecture, the example is implemented by: <ol id="ol0007" compact="compact"><li>1. STORE POINTER start address of array</li><li>2. READ POINTER (Read the contents of the address pointed to into an accumulator.)</li><li>3. MULTIPLY 15</li><li>4. STORE POINTER (Store the result into the address pointed to.)</li><li>5. INCREMENT POINTER</li><li>6. Go to line 2 until the array is done.</li></ol>

0035Compare the nine steps for the stack architecture versus the five steps for the register architecture for the above example. Furthermore, the stack operation has at least 3 possible opportunities for an extra memory access due to stack operation. The loop control of the hypothetical register/accumulator architecture could easily be handled in a register.

0036Stacks are useful for evaluating expressions and are used as such in most compilers. Stacks are also useful for nested operations such as function calls. Most C compilers implement function calls with a stack. However, without supplementing by general purpose storage, a stack architecture requires lots of extra data movement and manipulation. For optimization purposes, stack PUSH and POP operations should also be separated from math and logic operations. But as can be seen from the example above, stacks are particularly inefficient when loading and storing data repeatedly, since the array addresses are consumed by the PUSH INDIRECT and POP INDIRECT.

0037In one aspect, the invention comprises a system comprising: (a) a plurality of parallel processors on a single chip; and (b)computer memory located on the chip and accessible by each of the processors; wherein each of the processors is operable to process a de minimis instruction set, and wherein each of the processors comprises local caches dedicated to each of at least three specific registers in the processor.

0038In various embodiments: (1) the size of each of the local caches is equivalent to one row of random access memory on the chip; (2) the at least three specific registers with an associated cache include an instruction register, source register, and destination register; (3) the de minimis instruction set consists of seven instructions; (4) each of the processors is operable to process a single thread; (5) an accumulator is an operand for every instruction, except an increment instruction; (6) a destination for each instruction is always an operand register; (7) three registers auto-increment and three registers auto-decrement; (8) each instruction requires only one clock cycle to complete; (9) the instruction set comprises no BRANCH instruction and no JUMP instruction; (10) each instruction is at most 8 bits in length; and (11) a single master processor is responsible for managing each of the parallel processors.

0039In another aspect, the invention comprises a system comprising: (a) a plurality of parallel processors on a single chip; and (b) computer memory located on the chip and accessible by each of the processors, wherein each of the processors is operable to process an instruction set optimized for thread-level parallel processing.

0040In various embodiments: (1) each of the processors is operable to process a de minimis instruction set; (2) each of the processors comprises local caches dedicated to each of at least three specific registers in the processor; (3) the size of each of the local caches is equivalent to one row of random access memory on the chip; (4) the at least three specific registers include an instruction register, source register, and destination register; (5) the de minimis instruction set consists of seven instructions; (6) each of the processors is operable to process a single thread; and (7) a single master processor is responsible for managing each of the parallel processors.

0041In another aspect, the invention comprises a method of thread-level parallel processing utilizing a plurality of parallel processors, a master processor, and a computer memory on a single chip, wherein each of the plurality of processors is operable to process a de minimis instruction set and to process a single thread, comprising: (a) allocating local caches to each of three specific registers in each of the plurality of processors; (b) allocating one of the plurality of processors to process a single thread; (c) processing each allocated thread by the processors; (d) processing the results from each thread processed by the processors; and (e) de-allocating one of the plurality of processors after a thread has been processed.

0042In various embodiments: (1) the de minimis instruction set consists of seven instructions; (2) instruction in the de minimis instruction set is at most 8 bits in length; and (3) each instruction in the de minimis instruction set is processed in one clock cycle.

Brief Description of the Drawings

0043<ul id="ul0001" list-style="none"><li><figref idref="f0001">FIG. 1</figref> depicts exemplary TOMI architecture of one embodiment.</li><li><figref idref="f0002">FIG. 2</figref> an exemplary instruction set.</li><li><figref idref="f0003">FIG. 2A</figref> shows a forward branch in operation.</li><li><figref idref="f0004">FIG. 3</figref> illustrates effective addresses of different addressing modes.</li><li><figref idref="f0005">FIG. 4</figref> illustrates how data paths from 4-32 bits are easily created.</li><li><figref idref="f0006">FIG. 5</figref> depicts exemplary local caches.</li><li><figref idref="f0007">FIG. 6</figref> depicts exemplary cache management states.</li><li><figref idref="f0008">FIG. 7</figref> shows one embodiment of additional processing functionality organized to take advantage of a wide system RAM bus.</li><li><figref idref="f0009">FIG. 8</figref> depicts an exemplary memory map.</li><li><figref idref="f0010">FIG. 9</figref> depicts an exemplary process availability table.</li><li><figref idref="f0011">FIG. 10</figref> illustrates three components of processor allocation.</li><li><figref idref="f0012">FIG. 11</figref> depicts exemplary factoring.</li><li><figref idref="f0013">FIG. 12</figref> depicts exemplary system RAM.</li><li><figref idref="f0014">FIG. 13</figref> depicts an exemplary floorplan for a monolithic array of 64 processors.</li></ul>

Detailed Description of Certain Embodiments

0044The TOMI architecture of at least one embodiment of the present invention preferably uses the minimum logic possible to operate as a general purpose computer. The most common operations are given priority. Most operations are visible, regular, and available for compiler optimization.

0045In one embodiment, the TOMI architecture is a variation on accumulator, register, and stack architectures, as illustrated in <figref idref="f0001">FIG. 1</figref>. In this embodiment: <ol id="ol0008"><li>1. Like an accumulator architecture, the accumulator is always one of the operands, except for the increment instruction.</li><li>2. Like a register architecture, the destination is always one of the operand registers.</li><li>3. The accumulator and program counter are also in the register space and may therefore be operated on.</li><li>4. Three special registers auto-increment and auto-decrement and are useful for creating stacks and streams of input and output.</li><li>5. All operations require a single clock cycle (and two states: clock high, clock low).</li><li>6. All instructions are 8-bits in length, simplifying and speeding instruction decode.</li><li>7. There is no BRANCH or JUMP instruction.</li><li>8. There are just seven instructions enabling 3 bits of operator selection from an 8-bit instruction, as illustrated by <figref idref="f0002">FIG. 2</figref>.</li></ol>

0046Some of the benefits of the preferred embodiment include: <ol id="ol0009"><li>1. All operations run at the maximum speed allowed by the logic, rather than being constricted by the equality necessitated by a pipeline. Logic operations are fastest. Math operations are next fastest, Operations requiring memory access are slowest.</li><li>2. The architecture scales to any data width, limited only by package pins, adder carry times, and usefulness.</li><li>3. The architecture is near the minimum possible functionality necessary to perform all the operations of a general purpose computer.</li><li>4. The architecture is very transparent, very regular, and most operations are available to the optimizing compiler.</li></ol>

0047The architecture is designed to be simple enough to be replicated numerous times on a single monolithic chip. One embodiment embeds multiple copies of the CPU monolithically with memory. A 32-bit CPU may be implemented in fewer than 1,500 gates, with most of the gates defining the registers. Nearly 1,000 TOMI CPUs of a preferred embodiment can be implemented using the same number of transistors as a single Intel Pentium 4.

Instruction Set

0048The seven instructions in the instruction set are shown in <figref idref="f0002">FIG. 2</figref> along with their bit mappings. Each instruction preferably consists of a single 8-bit word.

Addressing Modes

0049<figref idref="f0004">FIG. 3</figref> illustrates the effective addresses of the different addressing modes.

0050The addressing modes are: <ul id="ul0002" list-style="none" compact="compact"><li>Immediate</li><li>Register</li><li>Register Indirect</li><li>Register Indirect Auto-increment</li><li>Register Indirect Auto-decrement</li></ul>

Special Cases

0051Register 0 and Register 1 both refer to the Program Counter (PC). All operations with Register 0 (the PC) as the operand are conditional on the accumulator carry bit (C) equals 1. If C=1, the old value of PC is swapped into the accumulator (ACC). All operations with Register 1 (the PC) as the operand are unconditional.

There Is No Branch

0052Branch and lump operations are usually a problem for CPU designers because they require many bits of precious op-code space. The branching function may be created by loading the desired branch address into the ACC using LOADACC, xx and then using the STOREACC, PC instruction to effect the branch. A branch may be made conditional on the state of C by storing to Register 0.

Skip

0053A skip may be created by executing INC, PC, Execution will require two cycles, one for the current PC increment cycle to complete and one for the INC. A skip may be made conditional on the state of C by incrementing Register 0.

A Relative Branch

0054A relative branch may be created by loading the desired offset into the ACC and then executing the ADD, PC instruction. A relative branch may be made conditional on the state of C by adding to Register 0.

Forward Branches

0055Forward branches are more useful than rearward branches since the location of the rearward branches necessary for loops is easily captured by saving the PC as the program steps through the top of the loop the first time.

0056A more efficient forward branch than the relative branch may be created by loading the least significant bits of the branch endpoint into the ACC and then storing to the PC. Since the PC can be accessed both conditionally or unconditionally depending upon the use of Register 0 or Register 1, the forward branch may also be conditional or unconditional by the selection of the PC register (Register 0 or Register 1) as the destination operand.

0057For example: <ul id="ul0003" list-style="none" compact="compact"><li>LOADI, #1C</li><li>STOREACC, PC</li></ul>

0058If the most significant bits of the ACC are zero, only the least significant 6 bits are transferred to the PC register. The most significant bits of the register remain unchanged if the least significant 6 bits of the current PC register are smaller than the ACC value to be loaded. If the least significant 6 bits of the current PC register are greater than the ACC value to be loaded, the current PC register is incremented, starting with the 7th bit.

0059This effectively allows branches of up to 31 instructions forward. This method of forward branching should be used whenever possible because not only does it require 2 instructions versus 3 instructions for the relative branch, but it does not require a pass through the adder, which is one of the slowest operations. <figref idref="f0003">Fig. 2A</figref> shows the forward branch in operation.

Loops

0060The top of a loop may be saved using LOADACC, PC. The resulting pointer to the top of the looping construct may then be stored in a register or pushed into one of the autoindexing registers. At the bottom of the loop, the pointer may be retrieved with LOADACC, EA and restored to the PC using STOREACC, PC, thereby causing a backwards loop. The loop may be made conditional on the state of C by storing to Register 0 thereby causing a conditional backwards loop.

Self Modifying Code

0061It is possible to write self-modifying code using STOREACC, PC. An instruction may be created or fetched into the ACC and then stored into the PC where it will execute as the next instruction. This technique may be used to create a CASE construct.

0062Assume a jump table array in memory consisting of N addresses and base address of JUMPTABLE. For convenience, JUMPTABLE might be in low memory so its address can be created with LOADI or a LOADI following by one or more right shifts, ADD, ACC.

0063Assume that the index into the jump table is in ACC and the base address of the jump table is in a general purpose register named JUMPTABLE: <tables id="tabl0001" num="0001"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="48mm" /><colspec colnum="2" colname="col2" colwidth="74mm" /><tbody><row><entry>ADD, JUMPTABLE</entry><entry align="center">Add the index to the base address of the jump table.</entry></row><row><entry namest="col1" nameend="col2" align="left">LOADACC, (JUMPTABLE) Load the indexed address</entry></row><row><entry>STOREACC, PC</entry><entry align="center">Execute the jump,</entry></row></tbody></tgroup></table></tables>

0064If low order memory starting at 0000 is allocated to system calls, each system call may be executed as follows where SPECIAL_FUNCTION is the name of an immediate operand 0-63: <tables id="tabl0002" num="0002"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="49mm" /><colspec colnum="2" colname="col2" colwidth="48mm" /><tbody><row><entry>LOADI, SPECIAL_FUNCTION</entry><entry>Load the system call number</entry></row><row><entry>LOADACC, (ACC)</entry><entry>Load the address of the system</entry></row><row><entry>call</entry><entry /></row><row><entry>STOREACC, PC</entry><entry>Jump to the function</entry></row></tbody></tgroup></table></tables>

Right Shift

0065The basic architecture does not envision a right shift operation. Should such an operation be required, the solution of a preferred embodiment is to designate one of the general purpose registers as the "right shift register." A STOREACC, RIGHTSHIFT would store the ACC right shifted a single position into the "right shift register" whers its value could be read with LOADACC, RIGHTSHIFT.

Architectural Scalability

0066The TOMI architecture preferably features 8-bit instructions, but the data width need not be restricted. <figref idref="f0005">FIG. 4</figref> illustrates how any width data paths from 4-32 bits are easily created. Creating larger width data handling only requires increasing the width of the register set, the internal data paths, and the ALU to the desired widths. The upper bound of the data path is only limited by the carry propagation delay of the adder and the transistor budget.

0067The preferred TOMI architecture is implemented as a Von Neumann memory configuration for simplicity, but a Harvard architecture implementation (with separate data and instruction buses) is also possible.

Common Math Operations

0068Two's complement math can be done several ways. A general purpose register may be preconfigured as all "1s" and named ALLONES. The operand will be assumed to be in a register named OPERAND: <tables id="tabl0003" num="0003"><table frame="none"><tgroup cols="1" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="84mm" /><tbody><row><entry>LOADACC, ALLONES</entry></row><row><entry>XOR, OPERAND</entry></row><row><entry>INC, OPERAND The "2s" complement is left in OPERAND.</entry></row></tbody></tgroup></table></tables>

Common Compiler Constructions

0069Most computer programs are generated by a compiler. Therefore, a useful computer architecture should be adept at common compiler constructions.

0070A C compiler will normally maintain a stack for passing parameters to function calls. The S, X, or Y registers may be used as the stack pointer. The function call will push the parameters onto one of the autoindexing registers acting as the stack, using, for example: STOREACC, (X)+. Upon entering the function the parameters will be POP'd into general purpose registers for use.

Stack Relative Addressing

0071There will be times when there are more elements passed in the function call than can conveniently fit in the general purpose registers. For the purposes of the following example it is assumed that a stack push operation decrements the stack. IfS is being used as the stack register, to read the Nth item relative to the top of the stack: <tables id="tabl0004" num="0004"><table frame="none"><tgroup cols="1" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="27mm" /><tbody><row><entry>LOADI, N</entry></row><row><entry>STOREACC, X</entry></row><row><entry>LOADACC, S</entry></row><row><entry>ADO, X</entry></row><row><entry>LOADACC, (X)</entry></row></tbody></tgroup></table></tables>

Indexing Into as Array

0072Upon entry into the array function, the base address of the array is located in a general purpose register named ARRAY. To read the Nth element in the array: <tables id="tabl0005" num="0005"><table frame="none"><tgroup cols="1" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="33mm" /><tbody><row><entry>LOADI, N</entry></row><row><entry>STROREACC,X</entry></row><row><entry>LOADACC, ARRAY</entry></row><row><entry>ADD, X</entry></row><row><entry>LOADACC, (X)</entry></row></tbody></tgroup></table></tables>

Indexing Into an N Word Element Array

0073Sometimes an array will be allocated for elements N words wide. The base address of the array is located in a general purpose register named ARRAY. To access the first word of the Nth element in a 5 word wide array: <tables id="tabl0006" num="0006"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="33mm" /><colspec colnum="2" colname="col2" colwidth="51mm" /><tbody><row><entry>LOADI, N</entry><entry /></row><row><entry>STOREACC, X</entry><entry>Store in temporary register</entry></row><row><entry>ADD, ACC</entry><entry>Multiply by 2</entry></row><row><entry>ADD, ACC</entry><entry>By 2 again = 4</entry></row><row><entry>ADD, X</entry><entry>plus 1 = 5</entry></row><row><entry>LOADACC, ARRAY</entry><entry /></row><row><entry>ADD, X</entry><entry>plus the base address of the array</entry></row><row><entry>LOADACC, (X)</entry><entry /></row></tbody></tgroup></table></tables>

Local TOMI Caching

0074A cache is memory smaller in size and faster in access than the main memory. The reduced access time and the locality of program and data accesses allow cache operations to increase performance of a preferred TOMI processor for many operations. From another perspective, a cache increases parallel processing performance by increasing independence of a TOMI processor from main memory. The relative performance of cache to main memory and the number of cycles the TOMI processor can execute before requiring another main memory load or store to or from cache determine the amount of performance increase due to TOMI processor parallelism.

0075TOMI local caches enhance the performance increase due to TOMI processor parallelism. Each TOMI processor preferably has three associated local caches, as illustrated in <figref idref="f0006">FIG. 5</figref>: <ul id="ul0004" list-style="none"><li>Instruction - associated with the PC</li><li>Source - associated with the X register</li><li>Destination - associated with the Y register</li><li>The optimal dimensions of these caches are application dependent. A typical embodiment may require 1024 bytes for each cache, In other words, 1024 instructions, and 256 32-bit words of source and destination. At least two factors determine the optimum size of the caches. First is the number of states the TOMI processor can cycle before another cache load or store operation is required. Second is the cost of the cache load or store operation from main memory relative to the number of TOMI processor execution cycles possible during the main memory operation.</li></ul>

Embedding TOMI Processors in RAM

0076In one embodiment, a wide bus connects the large embedded memory to the caches, so a load or store operation to the caches can occur quickly. With TOMI processors embedded in RAM, a load or store of an entire cache would consist of a single memory cycle to a RAM column. In one embodiment the embedded memory will be responding to request of 63 TOMI processors, so the response time of a cache load or store for one TOMI processor may be extended while the load or store of another TOMI processor cache competes.

0077Caches may be stored and loaded based on changes of the associated memory addressing registers X, Y, PC, as illustrated in <figref idref="f0007">FIG. 6</figref>. For example, the total width of the PC register might be 24 bits. If the PC cache is 1024 bytes, the lower 10 bits of the PC would define access within the PC cache. When the PC is written such that there is a change in the upper 14 bits, a cache load cycle would be required. The TOMI CPU associated with that PC cache would stop executing until the cache load cycle was complete and the indicated instruction could be fetched from the PC cache.

Cache Double Buffering

0078A secondary cache may be loaded in anticipation of the cache load requirement, The two caches would be identical and alternately be selected and deselected based on the contents of the upper 14 bits of the PC, In the example above, when the upper 14 bits of the PC changed to match that of the data pre-cached in the secondary cache, the secondary cache would become selected as the primary cache. The old primary cache would now become the secondary cache. Since most computer programs linearly increase in memory, one embodiment of the invention would have the secondary cache always fetching the contents of the cache contents of main memory referenced by the upper 14 bits of the current PC plus 1.

0079The addition of secondary caches will reduce the time the TOMI processor must wait for memory data to be fetched from main memory when moving outside of the boundary of the current cache. The addition of secondary caches nearly doubles the complexity of a TOMI processor. For an optimal system, this doubling of complexity should be offset by a corresponding doubling of performance of the TOMI processor. Otherwise, two simpler TOMI processors without secondary cache can be implemented with the same transistor count.

High Speed Multiply, Floating Point Operations, Additional Functionality

0080Integer multiplication and all floating point operations require many cycles to perform, even with special purpose hardware. Thus, they should be factored into other processors rather than included in the basic TOMI processor. Digital Signal Processing (DSP) operations often use deeply pipelined multipliers that produce a result every cycle even though the total multiplication may require many cycles. For signal processing applications that repeat the same algorithm over and over, such a multiplier architecture is optimal and may be incorporated as a peripheral processor to a TOMI processor, but it would likely increase complexity and reduce overall performance if it were incorporated directly in the TOMI processor. <figref idref="f0008">FIG. 7</figref> shows one example of additional processing functionality organized to take advantage of the wide system RAM bus.

TOMI Interrupt Strategy

0081An interrupt is an event external to the normal sequential operation of a processor that causes the processor to immediately change its sequence of operation.

0082Examples of interrupts might be completion of an operation by an external device or an error condition by some hardware. Traditional processors go to great lengths to quickly stop normal sequential operation, save the state of current operation, begin performing some special operation to handle whatever event caused the interrupt, and when the special operation is completed restore the previous state and continue sequential operation. The primary metric of interrupt handling quality is the time to respond.

0083Interrupts pose several problems for traditional processors. They make execution time indeterminate, They waste processor cycle storing and then restoring status. They complicate processor design and can introduce delays that slow every processor operation.

0084Immediate interrupt response is unnecessary for most processors, with the exceptions being error handling and those processors directly interfacing to real world activity.

0085In one embodiment of a multiprocessor TOMI system, only one processor possesses primary interrupt capability. All other processors run uninterrupted until they complete some assigned work and stop themselves or until they are stopped by the coordinating processor.

Input/Output (I/O)

0086In one embodiment of the TOMI processor environment, a single processor is responsible for all interfacing to the external world.

Direct Memory Access (DMA) Control

0087In one embodiment, immediate response to the external world in a TOMI processor system occurs via a DMA controller. A DMA controller, when requested by an external device, transfers data from the external device to the internal data bus for writing to the system RAM, The same controller also transfers data from the system RAM to the external device when requested. A DMA request would have the highest priority for internal bus access.

Organizing an Array of TOMI Processors

0088The TOMI processor of preferred embodiments of the invention is designed to be replicated in large numbers and combined with additional processing functionality, a very wide internal bus, and system memory on a monolithic chip. An exemplary memory map for such a system is illustrated in <figref idref="f0009">FIG. 8</figref>.

0089The memory map tor each processor dedicates the first 32 locations (IF hex) to the local registers for that processor (see <figref idref="f0004">FIG. 3</figref>). The remainder of the memory map is addressable by all processors through their cache registers (see <figref idref="f0007">FIG. 6</figref>). The addressability of the system RAM is limited only by the width of the three registers associated with the local caches; PC, X, and Y. If the registers are 24 bits wide, the total addressability would be 4 Mbytes, but there is no upper limit.

0090In one embodiment, 64 TOMI processors are implemented monolithically with memory. A single master processor is responsible for managing the other 63. When one of the slave processors is idle, it is not clocking so it consumes little or no power and generates little or no heat. On initialization, only the master processor is operational. The master begins fetching and executing instructions until a time that a thread should be started. Each thread has been precompiled and loaded into memory. To start a thread, the master allocates the thread to one of the TOMI CPUs.

Processor Availability

0091Coordination of the availability of TOMI processors to do work preferably is handled by the Processor Availability Table shown in <figref idref="f0010">FIG. 9</figref>. The coordinating (master) processor preferably can perform the following functions: <ol id="ol0010"><li>1. Push the calling parameters for a slave processor onto its stack, including but not limited to the execution address of the thread, the source memory, and the destination memory.</li><li>2. Start a slave processor.</li><li>3. Respond to a slave processor thread completion event either by polling or by responding to an interrupt.</li></ol>

Requesting a Processor

0092The coordinating processor may request a processor from the availability table. The number of the lowest processor with an available_flag set to "0" is returned. The coordinating processor may then set the available_flag associated with the available processor to "1", thereby starting the slave processor. If no processor is available, the request will return an error. Alternatively, processors may be allocated by the coordinating processor based upon a priority level associated with the requested work to be performed. Techniques to allocate resources based upon priority schemes are well-known in the art. <figref idref="f0011">FIG. 10</figref> illustrates three preferred components of processor allocation; Coordinating Processor initiating operations, Slave Processor operations, and Coordinating Processor result handling through interrupt response.

Step-by-Step Starting a Slave Processor

0093<ol id="ol0011"><li>1. Coordinating processor pushes the parameters for the thread to run onto its own stack. Parameters may include: starting address of the thread, source memory for the thread, destination memory for the thread, and last parameter_count.</li><li>2. Coordinating processor requests an available processor.</li><li>3. Processor allocation logic returns either the number of the numerically lowest slave processor that has both its associated available_flag set and its associated done_flag cleared, or an error.</li><li>4. If an error was returned, the coordination processor may either retry the request until a slave processor becomes available or perform some special operation to handle the error.</li><li>5. If an available processor number was returned, the coordinating processor clears the available_flag for the indicated processor. This operation pushes the parameter_count number of stack parameters to the stack of the selected slave processor. The done_flag is cleared to zero.</li><li>6. The slave processor retrieves the top stack item and transfers it to the slave processor's program counter.</li><li>7. The slave processor then fetches the memory column indicated by the program counter into the instruction cache.</li><li>8. The slave processor begins executing instructions from the beginning of the instruction cache. The first instructions will likely retrieve the calling parameters from the stack.</li><li>9. The slave processor executes the thread from the instruction cache. When the thread completes, it checks the state of its associated done_flag. If the done_flag is set, it waits until the done_flag is cleared, indicating the coordinating processor has handled any previous results.</li><li>10. If the interrupt vector associated with the slave processor is set to -1, no interrupt will be created by setting the done_flag. The coordinating processor may therefore poll for the done_flag to be set.</li></ol>

0094When the coordinating processor detects that the done_flag is set, it may handle the slave processor's results and possibly reassign the slave processor to do new work. When the slave processor's results have been processed, the associated coordinating processor will clear the associated done_flag.

0095If the interrupt vector associated with the slave processor is not equal to -1, setting the associated done_flag will cause the coordinating processor to be interrupted and begin executing an interrupt handler at the interrupt vector address.

0096If the associated available_flag has been set also, the coordinating processor may also read the return parameters pushed on the slave processor's stack.

0097The interrupt handler will handle the slave processor's results and possibly reassign the slave processor to do new work. When the slave processor's results have been processed, the interrupt handler running on the coordinating processor will clear the associated done_flag.

009811. If the done_flag is clear, the slave processor sets its associated done_flag and saves the new start_time. The slave processor may continue to do work or may return to the available state. To return to the available state, the slave processor may push return parameters onto its stack, followed by a stack count and set its available_flag.

Memory Locking

0099TOMI processors read and write system memory through their caches. A completely cached column is read or written at one time. Any processor may read any portion of system memory. An individual processor may lock a column of memory for its exclusive writing. This locking mechanism avoids memory writing conflicts between processors.

Suggested Applications

0100Parallelism effectively accelerates applications that may be factored into independent pieces of work for individual processors. One application that factors nicely is image manipulation for robotic vision. Image manipulation algorithms include correlation, equalization, edge identification, and other operations. Many are performed by matrix manipulation. Very often the algorithms factor nicely, as illustrated in <figref idref="f0012">FIG. 11</figref>.

0101In <figref idref="f0012">FIG. 11</figref>, the example imagemap shows 24 processors, with a processor allocated to manipulate the image data for a rectangular subset of the total imagemap.

0102<figref idref="f0013">FIG. 12</figref> shows how the TOMI system RAM may be allocated in one embodiment. One block of system RAM holds the image capture pixels, and another block holds the processed results.

0103In operation, the coordinating processor has allocated a DMA channel to transfer the image pixels from an external source to the internal system RAM every fixed amount of time. A typical speed of image capture might be 60 images per second.

0104The coordinating processor then enables slave processor 1 by pushing the address of the imagemap to be used by the X register, the address of the processed image to be used by the Y register, the parameter count of 2, and the address of the image processing algorithm, The coordinating processor subsequently and similarly enables processors 2 through 25. The processors continue to execute independently and in parallel until the image processing algorithm is completed.

0105When the algorithm is completed, each processor sets its associated done_flag in the Processor Availability Table. The results are handled by the coordinating processor, which is polling for completion or responding to an interrupt on the "done" event.

0106<figref idref="f0014">FIG. 13</figref> shows an exemplary floorplan for a monolithic array of 64 processors.

0107It will be appreciated that the present invention has been described by way of example only and with reference to the accompanying drawings, and that improvements and modifications may be made to the invention without departing from the scope or spirit thereof.

<u>SPECIFIC EMBODIMENTS:</u>

0108<ol id="ol0012"><li>1. A system comprising: <ul id="ul0005" list-style="none" compact="compact"><li>a plurality of parallel processors on a single chip; and</li><li>computer memory located on said chip and accessible by each of said processors,</li></ul> wherein each of said processors is operable to process a <i>de minimis</i> instruction set, and wherein each of said processors comprises local caches dedicated to each of at least three specific registers in said processor.</li><li>2. A system as in embodiment 1, wherein the size of each of said local caches is equivalent to one row of random access memory on said chip,</li><li>3. A system as in embodiment 1, wherein the at least three specific registers with an associated cache include an instruction register, source register, and destination register.</li><li>4. A system as in embodiment 1, wherein said <i>de minimis</i> instruction set consists of seven instructions.</li><li>5. A system as in embodiment 1, wherein each of said processors is operable to process a single thread.</li><li>6. A system as in embodiment 1, wherein an accumulator is an operand for every instruction, except an increment instruction.</li><li>7. A system as in embodiment 1, wherein a destination for each instruction is always an operand register.</li><li>8. A system as in embodiment 1, wherein three registers auto-increment and three registers auto-decrement.</li><li>9. A system as in embodiment 1, wherein each instruction requires only one clock cycle to complete.</li><li>10. A system as in embodiment 1, wherein said instruction set comprises no BRANCH instruction and no JUMP instruction.</li><li>11. A system as in embodiment 1, wherein each instruction is at most 8 bits in length.</li><li>12. A system as in embodiment 1, wherein a single master processor is responsible for managing each of said parallel processors.</li><li>13. A system comprising: <ul id="ul0006" list-style="none" compact="compact"><li>a plurality of parallel processors on a single chip; and</li><li>computer memory located on said chip and accessible by each of said processors,</li></ul> wherein each of said processors is operable to process an instruction set optimized for thread-level parallel processing,</li><li>14. A system as in embodiment 13, wherein each of said processors is operable to process a <i>de minimis</i> instruction set.</li><li>15. A system as in embodiment 13, wherein each of said processors comprises local caches dedicated to each of at least three specific registers in said processor.</li><li>16. A system as in embodiment 15, wherein the size of each of said local caches is equivalent to one row of random access memory on said chip.</li><li>17. A system as in embodiment 15, wherein the at least three specific registers include an instruction register, source register, and destination register.</li><li>18. A system as in embodiment 14, wherein said <i>de minimis</i> instruction set consists of seven instructions.</li><li>19. A system as in embodiment 13, wherein each of said processors is operable to process a single thread,</li><li>20. A system as in embodiment 13, wherein a single master processor is responsible for managing each of said parallel processors,</li><li>21. A method of thread-level parallel processing utilizing a plurality of parallel processors, a master processor, and a computer memory on a single chip, wherein each of said plurality of processors is operable to process a <i>de minimis</i> instruction set and to process a single thread, comprising: <ol id="ol0013" compact="compact"><li>(a) allocating local caches to each of three specific registers in each of said plurality of processors;</li><li>(b) allocating one of the plurality of processors to process a single thread;</li><li>(c) processing each allocated thread by said processors;</li><li>(d) processing the results from each thread processed by said processors; and</li><li>(e) de-allocating one of said plurality of processors after a thread has been processed.</li></ol></li><li>22. A method as in embodiment 21, wherein the <i>de minimis</i> instruction set consists of seven instructions.</li><li>23. A method as in embodiment 21, wherein each instruction in the <i>de minimis</i> instruction set is at most 8 bits in length.</li><li>24. A method as in embodiment 21, wherein each instruction in the <i>de minimis</i> instruction set is processed in one clock cycle.</li></ol>