Software based application specific integrated circuit

A processing device is provided. A cluster includes a plurality of groups of processing elements. A multi-word device is connected to the processing elements within the groups. Each processing element in a particular group is in communication with all other processing elements within the particular group, and only one of the processing elements within other groups in the cluster. Each processing element is limited to operations in which input bits can be processed and an output obtained without reference to other bits. The multi-word device is configured to cooperate with at least two other processing elements to perform processing that requires reference to other bits to obtain a result.

BACKGROUND

1. Field of the Disclosure

The present invention relates to custom designed integrated circuits. More specifically, the present invention relates to a system and method for custom designing an integrated circuit that executes software in a manner that is consistent with the speed of hardware circuitry.

2. Background Information

In general, there are two types of custom designed integrated circuits. The first is the application-specific integrated circuit (ASIC). These chips are, quite literally, custom designed hardware circuits. They are extremely fast and utilize relatively low power.

A drawback is that the design process incurs enormous non-recurring engineering costs. Millions of dollars need to be expended before the first chip is even sold. The chip is also dedicated to its design purpose, and cannot be reconfigured for other uses.

The other primary type of custom designed integrated circuits is the field-programmable gate array (FPGA). FPGAs contain programmable logic components called “logic blocks”, and a hierarchy of reconfigurable interconnects that allow the blocks to be “wired together”—somewhat like many (changeable) logic gates that can be inter-wired in (many) different configurations. Various computer tools are provided whereby a user can custom design a circuit using the tool. The tool will form the interconnections in the FPGA to execute the programmed circuit.

FPGAs have advantages over ASICs in that they have much lower non-recurring engineering costs, and are reconfigurable. However, FPGAs are significantly slower than ASIC chips, consume relatively high amounts of power, and have a high per unit cost.

The market currently does not have a configurable chip that can provide the advantages of both FGPAs and ASIC chips without the corresponding disadvantages.

In general, the design of software based processing has various limits on its processing speed. In contrast, hardware has far faster processing.

SUMMARY OF THE INVENTION

Embodiments herein provide a methodology for emulating hardware-like functionality on a programmable chip.

DETAILED DESCRIPTION

It is to be understood that the figures and descriptions of embodiments of the present disclosure have been simplified to illustrate elements/steps relevant for a clear understanding of the present disclosure, while eliminating, for the purpose of clarity, other elements/steps found or used in typical presentations, productions, data delivery, computing systems, devices and processes. Those of ordinary skill in the art may recognize that other elements and/or steps are desirable and/or required in implementing embodiments of the present disclosure. However, because such elements and steps are well known in the art, and do not facilitate a better understanding of the present disclosure, a discussion of such elements/steps is not provided herein.

Embodiments of the invention herein provide a new custom design methodology that uses software on an integrated circuit to emulate the operability of hardware circuitry. Like an FPGA, the embodiments are reconfigurable and have low non-recurring engineering costs. Like an ASIC, they have high speed and consume relatively little power.

Referring now toFIG. 1, a processing element (“PE”)100is shown. PE100is a basic building block of an integrated circuit according to an embodiment. It is similar to a basic microcontroller, and forms an individual processing module. PE100may be an 8-bit processing module, but the invention is not so limited; and it may be any desired size, including but not limited to 2-bit, 4-bit, 16-bit, 32-bit, etc.

As discussed in more detail below, PE100includes an arithmetic logic unit (“ALU”)102to perform logical operations. However, PE100preferably does not perform mathematical operations.

By way of example in the context of this application, a logical operation is one in which the input bits can be considered and a result can be obtained without reference to other bits, regardless of the content of the bits that are operated upon. AND (^) and OR (*) operations are examples of logical operations.

In contrast, a mathematical operation is one in which input bits can be considered and a result may need to be obtained with the additional consideration of at least one other bit. Addition (+), or multiplication (−) are examples of mathematical operations, because the result may require reference to other bits.

The nature of the distinction between logical and mathematical operations can be seen in the following example. Consider the 4-bit word A of 0110, and the 4-bit word B of 0101. Consider now the logical operation of A AND B (A^B). The operation and the result can be viewed as follows:

In the above operation, each column of bits resolves without reference to another column of bits. Thus, in bit column zero, 0 AND 1 it results in 0 without reference to any bits in any other columns. This is the case for all columns regardless of what the particular bits are.

Consider now the mathematical operation of A plus B (A+B). Using the same A and B above, we get:

In the above example, resolution of this particular value of A and B requires at least some consideration of other bits. Specifically, bit column 2 results in 1+1=2. Since bits are in binary, this results in zero in bit column 2 and a carry over of one (1) into bit column 3. To reach the result in bit column 3, the operation required consideration of not only the values of A and B in bit column 3, but any carryover from bit column 2. In this manner, the operation of addition can thus require consideration of other bits.

It is noted that generic mathematical operations are not value dependent. For example, consider the addition of 0000+0000=0000. Processing of any two (2) bits provides a result (zero) without reference to other bits. From the perspective of the processing of the data, this operation appears as a logical operation, in that there is no consideration of other bits. Addition is nonetheless a mathematical operation because it could potentially be called upon to rely upon other bits based on the values. The system that performs the addition should be constructed to account for that possibility. Thus, a component that performs the mathematical operation of generic addition should be structured to account for that possibility.

It is noted that there may be exceptions in which a specific mathematical function could be considered a logical function. One such possible exception is when the data subset that it would consider would be known to require only consideration of input bits without reference to other bits. For example, as discussed above, generic addition is a mathematical function because of the possibility of carryover for the sum of 1+1=2. However, if it were known at the programming level that a limited data set would be presented for addition that would not induce carryover (e.g., 0+0, 0+1, 1+0, but not 1+1), then this function could meet the definition of a logic operation and could be assigned to a PE100for processing.

Another example is the function A≠B, which can be built with extremely fast hardware and thus accommodated into a PE100.

Referring now toFIG. 2, each PE100is preferably assigned into groups200. The embodiment ofFIG. 2shows four PE100s (PE0, PE1, PE2, PE3) assigned to group200. The assignment of four PE's100to a group200may provide certain advantages compared with other numbers, but the invention is not limited to four per group.

In the embodiment ofFIG. 2, each PE100forms a “positional pair” with another PE100based on relative orientation. Thus, each PE100forms a first horizontal positional pair with a horizontal neighbor, a second vertical positional pair with a vertical neighbor, and a third diagonal positional pair with a diagonal neighbor. For example PE0 has a vertical pair relationship with PE2, a horizontal pair relationship with PE1, and a diagonal pair relationship with PE3.

Each PE100within group200preferably has bidirectional communication with every other PE100in the group through pathways202. Pathways207are labeled according to their pair relationship. Thus for example the communication between vertical pair PE0 and PE2 is designated Vpe. In this configuration, each PE100has full connectivity with all of the other PEs within the group200. Each PE100can access the result of any other PE within the group200. Each PE100can swap data with other PEs100within the group200. As discussed below, PEs100within a group can also be used collectively to support mathematical operations.

FIG. 2also shows the preferred physical matrix orientation of the PEs100within group200. This particular matrix layout provides the overall minimum distance between PEs100, which improves the potential processing speed of group200. However, other configurations could also be used, although with a possible corresponding potential reduction in speed based on longer distances between PEs100.

Referring now toFIG. 3, group200is preferably associated with an instruction storage204and a data storage206. Storages204and206may be a RAM, either alone or in combination with other elements to support the functions of the RAM (collectively “RAM”), such as a random access memory (RAM). The nature and relationship of instruction storage204and data storage206are discussed in more detail below.

Referring now toFIG. 4, several groups200of PEs100form a cluster400. The embodiment ofFIG. 4shows four groups200(G0, G1, G2, G3) assigned to cluster400. The assignment of four groups200to a cluster400may provide certain advantages compared with other numbers, but the invention is not limited to four per cluster.

FIG. 4also shows the preferred physical orientation of the groups200within cluster400, although the invention is not limited to such configuration.

PEs100in different groups200within cluster400preferably form “conjugate pairs” with commonly situated PEs in different groups. Conjugate pairs are PEs100that share the same physical orientation within the groups200of the cluster400.

For example, referring now toFIG. 5, PE2 is the upper left most PE100within group G0 of cluster400. PE6, PE10, and PE14 share that same position in the other groups200. PE2, PE6, PE10, and PE14 will thus form 4 different conjugate pairs on vertical, horizontal and diagonal basis (Vb, Hb and Db, respectively) through which the PEs100can communicate with each other.

Thus, as shown inFIG. 5, the top left PEs100within group G2 of cluster400can bidirectionally communicate with every other top left PE100within the other groups200of cluster400. PE10 can communicate with its vertical pair PE2, with its diagonal pair PE6, and its horizontal pair PE14.

In another example as shown inFIG. 6, lower right PE1 can communicate with its vertical pair PE9, horizontal pair PE5, and its diagonal pair PE13.

It is to be understood that the remaining fourteen (14) PEs100within the cluster400of the embodiment have similar connections consistent with the principles discussed above, and are not separately described herein. Preferably each PE100does not communicate with other PEs in other groups200within cluster400other than as discussed herein. However, the invention is not so limited, and other such connections may exist.

Referring now toFIG. 7, communications to and from each cluster400preferably routes through a switching element700. The switching element700may be a 32 bit switch to provide a single bit input and output to each PE100in cluster400, but this need not be the case and the invention is not so limited. Each of the PEs100may connect to switching element700, and under such an embodiment would exchange information with the outside environment solely through switching element700.

Referring now toFIG. 7A, as noted above switching element700may be made of sub-elements.FIG. 7Ashows an embodiment in which switching element700is made of two sub-switching elements710. In an embodiment in which cluster400includes four groups200, each sub-switching element is the pathway for communications with two of the four groups. InFIG. 7A, the lower sub-switching element710handles groups G0 and G1, while the upper sub-switching element710handles groups G2 and G3. Other configurations could also be used. It is to be understood that switching element700as shown in the figures, such asFIG. 7, is generic to any such switching configuration unless noted otherwise.

Each switch700has a portion of its operations (referred to herein as “portions”, although it is to be understood that the portions do not necessarily refer to physical portions) devoted to one of the PEs100within each group.

Referring now toFIG. 7B, which is an exploded version ofFIG. 7, switch700has four (4) portions SW0-SW3. As discussed above, groups200within cluster400preferably communicate through conjugate pairs of commonly placed PEs100on vertical, horizontal and diagonal basis (Vb, Hb and Db, respectively). Preferably the corresponding portion of the switch700similarly communicates only with the PE's within those conjugate pairings of commonly placed PEs100. InFIG. 7B, portion SW2 of switch700connects to PE2 and its common pairs PE6, PE10, and PE14 that share the same physical orientation in other groups. The remaining portions of switch700similarly connect with their corresponding pairs in the groups.

As discussed in more detail below, switch700may be its own processing element, and would operate under control of instruction storage204.

Referring now toFIG. 8, the larger circuit800is defined by multiples of clusters400. The clusters400are connected in parallel by the switching elements700. The switching elements700preferably communicate through their common portion, e.g., SW2 of one switching element700would only communicate with switching element SW2 of another switching element700. This establishes a concept of byte lanes that will extend from the switches700to higher and lower stages of the architecture. The byte lanes are preferably the same word size as the bits of each PE100.

Four clusters400are shown inFIG. 8, but in practice larger circuit800could support as many clusters400as desired.

Clusters400may further be organized into independent groups. A higher layer switch fabric may connect the clusters400to each other within the group, preferably using the same or similar methodology as the switch fabric defined by switching elements700inFIG. 8. However, other switch fabrics may be used. The independent groups of clusters400may themselves be connected by a still higher layer switch fabric, preferably using the same or similar methodology as the switch fabric defined by switching elements700inFIG. 8.

Each PE100within SD-ASIC1010is preferably the same size to promote uniformity of design and operation. For ease of discussion, the embodiments herein are referred to as if all of the PEs100are the same size and design. However, the invention is not so limited, and it is to be understood that PEs100may have different sizes and/or designs.

Each PE100is its own mini-processor, configured to operate as one processor consistent with its size (e.g., 8 bits) that executes logical operations. If larger machines for logical operations are needed, then PEs100can cooperate to combine their individual processing power into larger machines. Thus, within any particular group200, any number of PEs100can combine to form a machine of their combined size. By way of non-limiting example, if each PE100is an 8-bit processor, then four (4) PEs100working collectively within a group200can form a 32-bit processor. Two groups200can combine together to form a 64-bit processor. Individual PEs100could work across groups200, and potentially across clusters400and even super clusters900, to similarly combine.

As a practical matter, there may be an upper limit on the number of PEs100that can combine in this manner. By way of non-limiting example, 64 bits may be the largest machine that can be formed, but the invention is not so limited, and other limits (or no limits at all) may be used. If a limit is present, then processing that would require a larger machine would be addressed at the software level to break the processing down into chunks that could be operated on by sets of PEs100, possibly along with other PEs100directed to processing the results of the chunks into the larger result.

Referring now toFIG. 12as discussed above, the various PEs100may perform logical operations, but preferably not mathematical operations. To provide mathematical operations, a multi-word arithmetic logic unit1200, which may be made of subgroups, is provided in each cluster400. Multi-word arithmetic logic unit (MWU)1200is preferably a reconfigurable arithmetic coprocessor, although the invention is not limited thereto.

MWU1200provides mathematical operation capabilities, including but not limited to addition, multiplication, and shift (left or right). The logical operations of PEs100and the mathematical operations of MWU1200collectively provide the same capabilities of any prior art processing element that provides both of these operations, but with significantly enhanced speed.

Specifically, prior art logic elements have been designed to provide both logical operations and mathematical operations. The mathematical operations are the more resource demanding of the two, requiring more area, power, and time to process. Further, the slower speed of the mathematical operations tends to control the overall speed of the processor.

Yet from a programming perspective of some embodiments herein, there tend to be far more logical operations than mathematical operations. Thus, the processing speed of the majority of operations is limited by the processing speed required for the minority operations.

The division of logical operations into the PEs100and mathematical operations into MWU1200disassociates the logic operations from the physical limitations of the mathematical operations. PEs100can thus operate at significantly higher speeds than MWU1200, and can (particularly when leveraged with various other embodiments herein) approach or reach the processing speed of electronic hardware. Since the majority of executable software is made up of logical operations which can be executed at this speed, the overall processing speed of cluster400far exceeds that of typical processing chips that execute software.

MWU1200preferably does not provide any logical operations, as the PEs100provide that functionality. However, this need not be the case as MWU1200may be configured to perform, and may in fact perform, some logical operations, although this may result in some reduction of overall processing speed.

Referring now toFIG. 13, the cooperation between the PEs100and the MWU1200within a cluster400is shown at a logical level. The individual data storage206for each group200is also shown for reference.

The execution of mathematical operations calls for cooperation between PEs100in different groups200, typically between conjugate pairs. Thus, referring now toFIG. 14, to perform a basic mathematical operation, two conjugate pair PEs100from two different groups combine with a portion of MWU1200to form a miniature combined logical/mathematical unit1402.FIG. 14shows PE0 and PE8 in this configuration, but any conjugate pair of PEs100could be used. The individual PEs100provide the input data, the portion of MWU1200performs the mathematical operation, and the results are provided to one or both of the PEs100that provided the input data.

By way of non-limiting example, suppose the mathematical operation is A+B=C. In the machine1402ofFIG. 14, PE0 provides A to MWU1200, and PE8 provides B to MWU1200. MWU1200performs the addition and calculates C. MWU then provides C back to PE0 and/or PE8 that provided the input.

Machine1402is the smallest mathematical processor that can be created, and is consistent with the size of the PEs100. Thus, if PEs100are 8-bit processors, then machine1402is an 8-bit machine.

As with the individual PEs100, the formation of the mathematical/logical machines is scalable based on the needs of the design. Machine1404uses four (4) PEs100and MWU1200to form a machine twice the size of machine1406. Machine1406uses two (2) entire groups200with sixteen (16) PEs100to form a machine twice the size of machine1404and four times the size of machine1402. Indeed, an entire cluster400could be combined to form a machine eight times the size of machine1402. If the PEs100are 8-bit machines, then the cluster400in its entirety can form a 64-bit machine for mathematical/logical operations.

FIG. 15shows a more detailed version of the MWU1200in relation to the cluster400, MWU1200may be organized into three sub-units, one each for addition, multiplication, and shifting. These collectively can provide the nine basic mathematical operations of operations: ADD (addition), SUB (subtraction), MUL (multiplication), SMUL (signed multiplication), CLT (compare less than), SCLT (signed compare less than), LS (left shift), RS (right shift), ARS (arithmetic right shift).

Each sub-unit is subdivided into a number of stages equal to the number of PEs100in half of the cluster; inFIG. 15, this is eight (8) stages. Each stage receives input from and sends output to a matched pair of PEs, one from each half of the cluster, The stages of a sub-unit can be used individually for single-byte arithmetic, ganged together into a 64-bit operation, or in any combination of multi-byte arithmetic that fits into 64-bits.

FIG. 16shows a more detailed view of aspects of a PE100and its relationship with data storage206, instruction storage204, and other components discussed herein. The central component is the ALU102. In the embodiment ofFIG. 16, ALU102has two inputs102aand102b, and one output102c. ALU102also receives instruction commands from an instruction decoder, which itself receives instructions from instruction storage204and/or switch700(“L2SW”).

Input102abranches through a variety of paths to provide ALU102of PE100with a variety of possible inputs. Input can be received from (1) the positional paired PE100s within its group (Vpe, Dpe, and Hpe as shown inFIGS. 2 and 3), (2) the conjugate paired PEs100from other groups200within the cluster400(Vb, Db, and Hb and shown inFIGS. 5 and 6), (3) the switch700, (4) the output of the MWU1200, (5) a delayed circuit1602(which provides a delayed version of the output102cof ALU102, (6) a code value (imm) provided directly from the instruction storage204, and (7) data from data storage206. However, the invention is not so limited, and other inputs may be provided as appropriate.

For ease of design, the potential various input signals are fed to input102athrough a variety of multiplexers, either standalone or in cascade format (where the output of one multiplexer feeds another multiplexer). The various multiplexers are under the control of the instruction storage204, although only one such control signal is shown inFIG. 16for multiplexer A.

Output102cbranches off in multiple directions, including back into input102bthrough a delay element (shown as a perpendicular line). This collectively forms a feedback loop. ALU102is thus configured as an accumulator machine, in that one input102bfor any given instruction is always the value of the ALU102that was set on the previous instruction. The other input102a, if required, is selected from any of the various data paths to input102adiscussed above.

Output102cbranches through a variety of paths to make the output available to a variety of circuit components. One such branch, as discussed above, is fedback into input102bof ALU102. Other branch paths make the output102cavailable to: (1) the positional paired PE100s within its group (Vpe, Dpe, and Hpe as shown inFIGS. 2 and 3), (2) the conjugate paired PEs100from other groups200within the cluster400(Vb, Db, and Hb and shown inFIGS. 5 and 6), (3) the switch700, (4) the MWU1200, (5) a delay/hold circuit1602, and (6) data storage206.

Delay/hold circuit1502is a collection of registers and a multiplexer that can store and provide prior values of the output102cof ALU102for later use.

A multiplexer1604is also provided to produce a command code CC that can be used for various purposes. One such purpose is to dynamically interface the PE100and instruction storage204, discussed below.

The design of PE100relative to other PEs preferably has a critical path as small as possible. Using currently available technology, PEs100configured as shown inFIGS. 2, 3 and 16can achieve critical paths of 80 pico seconds. With continued improvements in the underlying components, a critical path of 60 pico seconds is possible.

FIG. 17shows the architectural layout of the components of a cluster400. The PEs100(shown as “ALU”) within the groups200are as close to the center as possible, and surrounded by the data storage206, instruction storage204, MWU1202, switches700/710, and other supporting components. This configuration optimizes the processing speed of the cluster400.

FIG. 18shows an embodiment with various connections of the PE100as shown inFIG. 16with other components within cluster400.

As discussed above, each group200has corresponding data storage206, which may be a data RAM. For ease of discussion, reference is made to herein as data RAM206(which may be RAM, either alone or with supporting elements), although it is to be understood that other storage may be used.

Referring now toFIG. 19, the relationship between aspects of the PEs100and the data RAM206are shown. Each data RAM206includes a column1902dedicated to a corresponding PE100in group200, and an address decoder1904. For ease of reference, only PE0 and PE3 are shown with their corresponding column1902, although it is to be understood that PE1 and PE2 are present and similarly connected.

Each PE100has connections to its corresponding dedicated column1902of the data RAM206(shown for clarity inFIG. 19only for PE0). Those connections may include write1912, read1914, column selector1916, and read/write command1918, although other connections could also be present.

Address decoder1904also receives two portions of an address. The first portion of the address is provided directly from one of the PEs100in the group200along a first address path1906. A second portion of the address is also provided by PEs100in the group along a second address path1908. Address paths1906and/or1908preferably pass through some type of intermediate element1910, such as a register, which provides a hold and delay quality.

In the embodiment ofFIG. 19, preferably only one of the PEs100at a time provides the least significant 8 bit portion of the address, and the register1910provides a second higher significant 8 bit portion of the address. In this manner, the address selected is based on a current and prior output of the PEs100within the group200.

Address decoder1904utilizes the addresses provided by the first and second address paths1906and1908, and converts them into a word line to select a row within data RAM206, represented as1920. Similarly, the column selector1916selects a column in data RAM1902. In combination, the selection of row and column identifies a particular location in data RAM206. Read1914and write1912will allow data to be read from or written to, respectively, data RAM206by the corresponding PE100.

In this configuration, activation of a particular word line by address decoder1904allows multiple PEs100to independently read and write to corresponding locations within their dedicated portions of data RAM206.

As discussed above, the various PEs100can combine to create larger machines. Their corresponding relationships with the data RAM206scale proportionally. Thus, by way of non-limiting example, two PEs can collectively form a 16-bit machine, made of two component halves that can either independently interact with data RAM206for 8-bit words, or collectively operate for 16-bit words.

As discussed above, data storage is preferably the combined size of the PEs100within its assigned group. Thus, by way of non-limiting example, four (4) 8-bit PEs100in group200would call for a 32-bit data RAM206.

In an alternative embodiment, an extra bit could be provided in data RAM206for each column1902assigned to each PE100within the group200. Thus, by way of non-limiting example, four (4) 8-bit PEs100in group200would call for a 36-bit data RAM206. The additional bit provides for the optional generation of a parity bit that can be used to identify errors in the data stream.

In this alternative embodiment, when eight PEs100in two groups within the same cluster400form a 64-bit machine, then the total of eight (8) extra bits is sufficient to allow for generation of an error correction code (ECC) for the 64-bit words of the machine. The ability to generate such a code is preferably part of the data RAM206, and not further discussed here.

Each group200has corresponding instruction storage206, which may be an instruction RAM. For ease of discussion, reference is made to herein as instruction RAM204(which may be RAM, either alone or with supporting elements), although it is to be understood that other storage may be used.

Referring now toFIG. 20, the relationship between aspects of the PEs100and the instruction RAM204within a group200are shown. Each instruction RAM204includes an instruction loader2002to load instructions into rows of individual storage2004reserved for each PE100; for ease of reference, only PE0 and PE3 are shown, although it is to be understood that the remaining PEs100of the group200are similarly present. Preferably instructions are provided to loader2002via the switch fabric discussed above, but other methodologies may be used.

A program counter2006is repeatedly cycling through a count that sequentially activates each row (word line represented by2020) of the individual storage2004. Thus by way of non-limiting example the first count activates the first word line, and the second count activates the second word line, etc. In this manner, instruction RAM204does not need a specific address decoder, although such a configuration could nonetheless be used. Program counter preferably counts in response to an external signal, preferably a completion detection signal2610(discussed below) provided by switch700through instruction loader2002.

As discussed below, each PE has the ability to indicate whether or not to receive an instruction. This indication is sent via the column select pathway2008and interacts with the word line from program counter2006. If the PE100indicates that it will receive an instruction, then the instruction contained in that word line within instruction storage2004is sent to PE100via pathway2008, which will then execute the instruction. If the PE indicates that it will not receive an instruction (which may be an affirmative signal to that effect or the absence of an enabling signal) then no instruction is sent to the PE100, and that PE100is inactive.FIG. 20shows PE0 as active, and PE3 as inactive (sometimes referred to as a sleep state).

Instruction memories tend to operate at slower speeds than the PEs100. As such, a multiplexer2012is provided to select amongst portions of instruction lines. For example, each line of instruction in each instruction storage2004could be 44 bits, which requires a processing time of about 320 ps. A four way multiplexer selects from one of four sets of the instructions; this allows four different instructions of 11 bits to be read into each PE100, These four sets of instructions can be read out sequentially at 80 ps, which is the preferred speed of the PE100. The processing of the PE100will thus be consistent with the smaller sets of instructions as provided. To the extent that PEs100and/or individual storage2004are of different sizes, then preferably a distribution (such as multiplexer2012) is provided to separate the instructions into smaller sizes consistent with the size of PE100. The multiplexer2012(or whatever distribution structure is provided, can be controlled by a variety of sources, including data RAM206, or previously loaded instructions from instruction RAM204.

Referring now toFIG. 21, when an extra bit is provided for parity or ECC, a separate instruction storage2102is provided for the same. These bits may be fed into the multiplexers2012, or an ECC generator2104that outputs to the multiplexer2012(the latter is shown inFIG. 21). The ECC generator can also provide an instruction on its own pathway2006to indicate whether to receive an instruction or not.

As discussed above, switch700may itself by its own processor, which may require instructions to process. Referring now toFIG. 22, a separate instruction storage2202is provided for switch700(or, as discussed below, at least the portion of the switch700under control for the group).

The same instruction storage204ofFIG. 22could be used for all groups200. However, in certain embodiments, control over a switch700, or sub switches710, need only be effectuated by some of the groups200. For example, consider the embodiment ofFIG. 7A, in which switch700is provided as two sub-switches710. Each sub-switch700is associated with two groups200of cluster400. Of those groups200, only one would have a data storage perFIG. 22to provide instructions to the sub-switch710. The instruction storage204of the groups that do not provide instructions for the switch710would be consistent withFIGS. 19 and 20.

A separate switch instruction storage2202is provided with instructions for the corresponding portion of switch700. Like the PEs100, switch700has the ability to indicate whether or not to receive an instruction. This indication is sent via the column select pathway2208and interacts with the word line from program counter2006. If the switch indicates that it will receive an instruction, then the instruction contained in that word line in instruction storage2004is sent to switch700, which will then execute the instruction. If switch700indicates that it will not receive an instruction (which may be an affirmative signal to that effect or the absence of a signal) then no instruction is sent to the switch700, and that switch700is inactive.

Although no ECC components fromFIG. 21are shown inFIG. 22, it is to be understood that such ECC components could be present.

Referring now toFIG. 23, each switch700(or sub-switch) may include first and second portions2302,2304(optionally referred to as upper and lower, respectively, although the invention is not limited thereto). The portions are shown inFIG. 23as physical portions, but it is to be understood that the different portions could be physical and/or logical portions.

The first portion2302is responsible for routing within the switch fabric formed by the various switches700. The second portion2304is responsible for the flow of data from the switch fabric into and out of its corresponding groups200. If the groups200assigned to the switch700are inactive, then at least the second portion2304can be inactive (and thus issue the inactive command) to save power. The first portion2302of the switch700can remain active to facilitate higher level data routing. In the alternative, the first portion2302of the switch2302can also be inactive if the particular switch700is not needed for routing within the switch fabric.

As discussed above, each PE100can issue signals that indicate whether or not it will receive an instruction. The typical reason that the system would not want the PE100to receive an instruction is some condition or event that would cause instructions to be skipped. For example, suppose that a PE100is at the first word line in the instruction RAM204. If a first condition is met, the program would want the PE100to execute the next (second) line of instructions. In this case, the PE100would indicate that it was ready to receive its next instruction.

However, if the first condition is not met, then the program would want PE100to “skip” to the fifth instruction line in the instruction RAM204. Since instructions are read out in sequence via the program counter2006, there is no option in instruction storage204or PE100to skip ahead to the fifth instruction. Instead, PE100goes inactive while the second, third and fourth lines of code are read out by the program counter. When the program counter reaches the fifth line of code, then the PE100reenters the active state so it can receive the fifth line of code. PE100thus effectively “skips” from the first to the fifth line by not receiving the intervening lines of code. This ability to “skip” is directed by a conditional command CC from multiplexer1604with PE100, discussed above with respect toFIG. 16.

An alternative embodiment would have pipelining in the instruction decoding, and therefore the column select into the instruction RAM204would be adjusted accordingly. In this embodiment, the column select may only be disabled if the skip is above a certain number of instructions.

Embodiments of the operation and architecture of the ALU102within PE100is now addressed. As discussed above, the ALU102has one output102cand two inputs102aand102b, for which the input102bis the feedback of the output102c. In this configuration, ALU102is acting as an accumulator circuit. ALU102is also receiving instructions on what logical operations to perform on the inputs102aand102bto generate the desired output102c.

In the above configuration, ALU102thus needs three things to perform an Operation—the input102a, the input102bas feedback from102c, and the instructions as to what logical operation to perform. Of these three needs, two are met in advance—the ALU102will already have instructions and the input102b; it is simply waiting for the input102ato fill the set before it can act. Under these conditions, because ALU102is limited to logical operations, ALU102can pre-process the output102cbased on the two possible values (0 or 1) and have the potential resultant values ready to output based on the nature of the input102awhen it arrives.

A conceptual example of this for a one-bit machine is shown inFIGS. 24A and 24B. By way of example, suppose the instruction is for an OR of single bits A and B to produce result C, where B is known in advance (as is the case with input102bfor ALU102). InFIGS. 24A and 24B, a processing element2402A is configured to operate as an OR gate. In the embodiment ofFIG. 24A, the OR gate functionality will calculate C when A becomes available. The speed to generate the output C is dependent upon the speed at which it takes processing element2402to perform the logical OR operation. Thus, if B=0, the speed of processing element2042inFIG. 24Awould be the time it takes for the OR gate to determine C based on the value of A.

However, since (1) B is known in advance, and (2) A can only assume two values, 0 or 1), then in an embodiment of the invention, ALU102can process in advance what the result would be based on A=0 and A=1. Those two outputs—CA=0and CA=1, respectively—are then fed to a multiplexer2404. When the input A arrives, rather than being an input that is processed to define the output, it becomes a control signal to the multiplexer2404that simply selects the appropriate preprocessed value. If A=1, the CA=1value is passed to the output C. If A=0, then the CA=0value is passed to the output C. Since the speed of a multiplexer responding to a control signal is typically faster than the time it takes to process an input to generate an output, the processing element2402B is faster than processing element2402A. Preferably, the ALU102of PE100is designed according to the example shown inFIG. 24B.

The above example scales up the bit size of the ALU102. Thus, if the ALU102is an 8-bit machine, then ALU102preprocesses the output102cindividually for each of the 8 bits. Again, the speed of the ALU is set by the multiplexer selection speed rather than the speed to perform the logical operation.

It should be noted that even the above processing forFIG. 24Bmay not be necessary. For example, if value B had been B=1, then for A OR B, the result is C=1 regardless of the value of A. Thus, separate processing for A=0 and A=1 was not necessary.

This can be addressed by defining the environment for the ALU102and optimizing the processing elements. By way of non-limiting example, suppose that the logical operations to be performed by ALU102were AND, OR, and XOR. Those possible logical operations, in combination with the possible values, generate the following truth table:

Combining the needs for a processing element2402to process consistent with this table and multiplexer2404, then all or part of2402and2404can be optimized into a single circuit that is much faster than three different logic gates for AND, OR, and XOR.

Exemplary architecture and methodology for ALU102per the above is shown in U.S. Ser. No. 61/646,653 entitled Implementation Method for Fast NCL Data path, filed May 14, 2012, the subject matter of which is expressly incorporated herein by reference in its entirety.

To operate effectively, the overall circuitry needs to maintain some level of synchronization so that the PEs in one group200or cluster400do not get ahead of a different group or cluster. Since timing of activity within each group200is dictated by program counter2006, some mechanism is preferred to ensure that one program counter2006is not advancing operations of its group200before the circuit is ready.

One way to accomplish this is to have a global clock connect to each program counter2006, such that counter2006moves in synchronization with the clock signal.

However, a design that occupies less area and requires less power omits a global clock in favor of local feedback and complete detection. Specifically, within a cluster each PE100may have a complete detection feature that generates a complete detection signal when the active PE has finished the processing of the logic to which it was instructed to perform. Switch700similarly may have a complete detection feature that generates a complete detection signal when it has completed its assigned operation. To the extent that there are inactive PEs100or switches700, the circuit is not waiting on this inactive element to complete processing, and thus their individual completion detection signals would generally default to output such a complete detection signal.

All of these completion signals are being generated within the various clusters400through the circuit1000. To create synchronization, various completion detection signals are collected locally at the cluster400level and from neighboring clusters. This will cascade throughout the circuit1000to synchronize the entire circuit.

Specifically, referring now toFIG. 26, within each cluster400, the completion detection signals are received locally by cluster complete detection circuitry2602cluster completion detection circuit2602may be part of switch700/710, but may be located elsewhere.

Cluster completion detection circuit2602receives the complete detection signals of the PEs100within each group200within the cluster400. These could be distinct signals sent from each of the PEs100, or on a group200basis (in which the individual groups200may have their own completion detection circuits, such as AND gates, for generating a group200completion circuit that resolves completion of the PEs100within the group200).FIG. 26shows such completion signals at2604. Although only one signal is shown from each group200, this signal represents either a single group signal and/or signals from the individual PEs100.

Cluster completion detection circuit2602also receives the completion detection signals of switch700, shown at2606. To the extent that cluster completion detection circuit2602is part of switch700, then2606may be an internal signal of switch700.

As discussed with respect toFIG. 8, each cluster400has adjacent clusters400. With the exception of cluster400along the edges, each non-edge cluster will have eight (8) surrounding clusters400. Of these, four (4) are adjacent in the switch fabric to the left, right, top and bottom, each of which contains its own switch700. Cluster completion detection circuit2602also receives the completion detection signals of these four (4) horizontal and vertically adjacent switches700from adjacent switches700.

In response to these various completion signals, the completion detection circuit2602, which may be part of switch700, generates a cluster completion detection signal2610. This completion detection signal2610is sent to the program counters2006within the individual groups200, which respond by moving to the next count to implement the next instruction. This completion detection signal2610is also sent to the top, bottom, left, and right groups200so that their completion detection circuits2602can themselves process their own completion detection processing.

The above design triggers a cascade effect of self-synchronization. Specifically, as discussed above, each cluster400synchronizes based on its own state and the states of the neighboring clusters. Thus, for example inFIG. 27, five clusters400make up a synchronization group2702(shown in dashed lines) that includes clusters A-E. However, there is an adjacent synchronization group2704(shown in solid line) that includes clusters C-H. Synchronization groups2702and2704overlap in clusters C, D, and E. Thus, the efforts of the individual synchronization groups2702and2704to synchronize amongst themselves cause the groups2702and2704to effectively synchronize collectively.

As noted above, this effect cascades throughout the circuit1000. For any synchronization group, there is some degree of overlap in shared clusters400with up to eighteen (18) surrounding synchronization groups (clusters400along the edge will have less). Each of those eighteen (18) surrounding synchronization groups have upwards of there own eighteen (18) surrounding synchronization groups, and so on, all working together to synchronize. Effectively, every synchronization group in the entire circuit1000works toward a common goal of reaching a global state of completion.

When that global state of completion is reached, all of the PEs100can receive there next set of instructions. Each cluster completion detection circuit2602within each cluster400(to the extent the cluster has active elements) sends a command to the program counter2006in the instruction storage204to advance the count to the next instruction word line.

In the above completion detection discussion, Applicants note that the MWU1200is not monitored for completion detection. As discussed above, logic functions take less time to compute than mathematical functions. The above methodology, by driving completion detection and subsequent instructions based on the speed of the logic processing of the PEs100, operates based on the speed of logic operations without being restricted by the slower speed of the mathematics. Mathematics thus can still be ongoing while the circuit1000is otherwise synchronizing for the next instruction.

In some cases the mathematics may not be complete by the time the circuit reaches a state by which the next instruction is generated by the program counters2006. However, as the time for the mathematics is known, the delay is simply accounted for in the programming. For example, if the mathematics would not be complete for three (3) logic instructions, then the code that controls the PEs100would be designed to put those PEs100to sleep for two instruction cycles, and then wake the PEs100to process the mathematics on that third instruction cycle.

Further, as discussed above, the logic processing of the PEs100are preferably not operating at the speed of logic operations perFIG. 24A, but rather the speed that it takes to switch to the proper output based on pre-calculation of the logic operations perFIGS. 24B and 25. This is a the factor that controls the overall speed of circuit1000, independent of the restrictions of mathematical operations.

As discussed above, clusters400may be placed into groups. A non-limiting theoretical example is shown inFIG. 9, in which clusters400may be organized into super clusters900. In the embodiment ofFIG. 9, sixty four (64) clusters400are provided in an 8×8 matrix to provide1024PEs100, although any number may be included in a super cluster900. A higher layer switch fabric910connects the clusters400to each other within super clusters900, preferably using the same methodology as the switch fabric defined by switching elements700inFIG. 8. However, other switch fabrics may be used.

FIG. 11shows an optional feature of an embodiment, in which at least one super cluster900is provided with an optional column1102of clusters400. This optional column1102provides fault tolerance without changing routing or scheduling. Some or all of the super clusters900in SD-ASIC1000may have such an optional column. By way of non-limiting example, one out of every four super clusters900could include an optional column1102. These spare clusters400could be in other configurations, such as rows or randomly distributed.

Circuit1010according to the methodologies discussed herein leverage many of the advantages of FPGAs and ASICs without corresponding disadvantages:

It will be apparent to those skilled in the art that modifications and variations may be made in the systems and methods of the present invention without departing from the spirit or scope of the invention. It is intended that the present invention cover the modifications and variations of this invention provided they come within the scope of the appended claims and their equivalents.