Scalable massively parallel group partitioned diagonal-fold switching tree computing apparatus.

0001This invention relates to computers and particularly to massively parallel array processors.

0002During the detailed description the following document works will be referenced as an aid for the reader: D.E. Rumelhart, J.L. McClelland, and the PDP Research Group, <i>Parallel Distributed Processing Vol. 1</i>: <i>Foundations</i> Cambridge, Massachusetts: MIT Press 1986. (Herein referred to as "Rumelhart 86".)

BACKGROUND OF THE INVENTION

0003In the never ending quest for faster computers, engineers are linking hundreds, and even thousands of low cost microprocessors together in parallel to create super supercomputers that divide in order to conquer complex problems that stump today's machines. Such machines are called massively parallel. Multiple computers operating in parallel have existed for decades. Early parallel machines included the ILLIAC which was started in the 1960s. Other multiple processors include (see a partial summary in U.S. Patent 4,975,834 issued December 4, 1990 to Xu et al) the Cedar, Sigma-1, the Butterfly and the Monarch, the Intel ipsc, The Connection Machines, the Caltech COSMIC, the N Cube, IBM's RP3, IBM's GF11, the NYU Ultra Computer, the Intel Delta and Touchstone.

0004Large multiple processors beginning with ILLIAC have been considered supercomputers. Supercomputers with greatest commercial success have been based upon multiple vector processors, represented by the Cray Research Y-MP systems, the IBM 3090, and other manufacturer's machines including those of Amdahl, Hitachi, Fujitsu, and NEC.

0005Massively Parallel (MP) processors are now thought of as capable of becoming supercomputers. These computer systems aggregate a large number of microprocessors with an interconnection network and program them to operate in parallel. There have been two modes of operation of these computers. Some of these machines have been MIMD mode machines. Some of these machines have been SIMD mode machines. Perhaps the most commercially acclaimed of these machines has been the Connection Machines series 1 and 2 of Thinking Machines, Inc.. These have been essentially SIMD machines. Many of the massively parallel machines have used microprocessors interconnected in parallel to obtain their con-currency or parallel operations capability. Intel microprocessors like i860 have been used by Intel and others. N Cube has made such machines with Intel '386 microprocessors. Other machines have been built with what is called the "transputer" chip. Inmos Transputer IMS T800 is an example. The Inmos Transputer T800 is a 32 bit device with an integral high speed floating point processor.

0006As an example of the kind of systems that are built, several Inmos Transputer T800 chips each would have 32 communication link inputs and 32 link outputs. Each chip would have a single processor, a small amount of memory, and communication links to the local memory and to an external interface. In addition, in order to build up the system communication link adaptors like IMS C011 and C012 would be connected. In addition switches, like a IMS C004 would be profited to provide, say, a crossbar switch between the 32 link inputs and 32 link outputs to provide point to point connection between additional transputer chips. In addition, there will be special circuitry and interface chips for transputers adapting them to be used for a special purpose tailored to the requirements of a specific device, a graphics or disk controller. The Inmos IMS M212 is a 16 bit process, with on chip memory and communication links. It contains hardware and logic to control disk drives and can be used as a programmable disk controller or as a general purpose interface. In order to use the concurrency (parallel operations) Inmos developed a special language, Occam, for the transputer. Programmers have to describe the network of transputers directly in an Occam program.

0007Some of these MP machines use parallel processor arrays of processor chips which are interconnected with different topologies. The transputer provides a crossbar network with the addition of IMS C004 chips. Some other systems use a hypercube connection. Others use a bus or mesh to connect the microprocessors and there associated circuitry. Some have been interconnected by circuit switch processors that use switches as processor addressable networks. Generally, as with the 14 RISC/6000s which were interconnected last fall at Lawarence Livermore by wiring the machines together, the processor addressable networks have been considered as coarse-grained multiprocessors.

0008Some very large machines are being built by Intel and nCube and others to attack what are called "grand challenges" in data processing. However, these computers are very expensive. Recent projected costs are in the order of $30,000,000.00 to $75,000,000.00 (Tera Computer) for computers whose development has been funded by the U.S. Government to attack the "grand challenges". These "grand challenges" would include such problems as climate modeling, fluid turbulence, pollution dispersion, mapping of the human genome and ocean circulation, quantum chromodynamics, semiconductor and supercomputer modeling, combustion systems, vision and cognition.

Problems addressed by our Scalable MP Group Partitioned Diagonl-Fold

Switching Tree Apparatus

0010One problem area involved in the implementation of a massively parallel processing system is the processor interconnection mechanism and scalability. This problem for massively parallel array processors to attack adequately the interconnection and scalability problems which exist in massively parallel computing systems has been addressed as we will describe. By way of a completely connected neural network model our preferred computing apparatus is described demonstrating a scalable and completely connected computing apparatus suitable for other general purpose applications.

SUMMARY OF THE INVENTION

0011We have provided a Scalable Massively Parallel Group Partitioned Diagonal-Fold Switching Tree Computing Apparatus which is also referred to as the Switching-Tree provides a scalable interconnection switching apparatus that maintains complete connectivity of the Root Tree Processors attached to the Diagonal-Fold Trees. The apparatus contains N Root Tree Processors, N Diagonal-Fold Trees, and <i>N</i>² Processing Elements (PEs). A completely connected neural network model will be used to demonstrate the scalability and complete connectivity of the Switching-Tree Computer and suitability of the structure as a massively parallel processor with general purpose capabilities. In accordance with our invention, we have provided an organization of PEs that can be partitioned into groups of PEs based upon technology or application constraints. Each group has multiple PEs that contain instruction and data storage units, receive instructions and data, and execute instructions, and may interface with external storage for instructions and data. The groups of PEs also execute a special type of "group" instructions and each PE interfaces with a communicating ALU trees. For neural applications, the N Root Tree Processors emulate the neuron operations, supporting, either in program code or hardware, the neuron activation functions, e.g. a sigmoid generator, and the Switching-Tree provides for interconnecting the groups and PEs into an N neuron structure for communicating both instructions, data, and the outputs of the neuron activation function units back to the input Processing Elements by way of the communicating ALU trees. The processor groups are used to create a high performance general purpose computing apparatus which maintains complete connectivity of the Root Tree Processors by way of their interconnected PEs.

0012These and other improvements are set forth in the following detailed description. However, specifically as to the improvements, advantages and features described herein, reference will be made in the description which follows to the below-described drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

0013<ul id="ul0001" list-style="none"><li>FIGURE 1 shows the Processor Element Architecture.</li><li>FIGURE 2 illustrates a Diagonal-Fold Four Root Tree Processor Array.</li><li>FIGURE 3 shows a Triangular Array of Dimension K.</li><li>FIGURE 4 shows a Triangular Array Partitioned into Multiple Triangle and Square Arrays.</li><li>FIGURE 5 shows Example Partitioned Triangle and Square Arrays with Diagonal-PEs and General-PEs.</li><li>FIGURE 6 shows Two Square Arrays of Elements Separated From Dual Element X by X Array.</li><li>FIGURE 7 shows Two Square Arrays of Elements Folded.</li><li>FIGURE 8. shows a Diagonal-Fold Tree 64 PE Array For an 8 Neuron Network Emulation.</li><li>FIGURE 9 shows an 8 neuron array model split into 1 square and 2 smaller triangular processor arrays.</li><li>FIGURE 10 shows the inner square of the 8 neuron array model.</li><li>FIGURE 11 shows the folded inner square separated into two triangular arrays.</li><li>FIGURE 12 shows a preferred external ALU function, sigmoid emulation, and tree communications path.</li><li>FIGURE 13 shows a 16 neuron array model weight matrix with neuron Y values.</li><li>FIGURE 14 shows triangular arrays 1 and 2.</li><li>FIGURE 15 shows triangular arrays 3 and 4.</li><li>FIGURE 16 shows a folded inner square 5 separated into two triangular arrays.</li><li>FIGURE 17 shows a folded inner square 6 separated into two triangular arrays.</li><li>FIGURE 18 shows a folded inner square 7 separated into two triangular arrays.</li><li>FIGURE 19 shows a folded inner square 8 separated into two triangular arrays.</li><li>FIGURE 20 shows a folded inner square 9 separated into two triangular arrays.</li><li>FIGURE 21 shows a folded inner square 10 separated into two triangular arrays.</li><li>FIGURE 22 illustrates a preferred external ALU function, sigmoid emulation, with a tree communication path.</li><li>FIGURE 23 illustrates a switching tree mechanism: 8 and 16 neuron examples.</li><li>FIGURE 24 illustrates alternatively a modified 8 neuron switching mechanism to support learning.</li><li>FIGURE 25 illustrates a Generalized Triangular Processor Array Partitioned by X.</li><li>FIGURE 26 illustrates a Generalized Inner Square Array.</li><li>FIGURE 27 illustrates the First Separated Square Array Partitioned From the Chosen Arbitrary Inner Square.</li><li>FIGURE 28 illustrates the First Separated Square Array Folded into a Triangular Array.</li><li>FIGURE 29 illustrates the Second Separated Square Array Partitioned From the Chosen Arbitrary Inner Square.</li><li>FIGURE 30 illustrates the Second Separated Square Array Folded into a Triangular Array.</li><li>FIGURE 31 illustrates the Square Array of First Outputs From the Triangular Arrays.</li><li>FIGURE 32 illustrates the Folded First Output Array With External Switches and ALU Tree Added</li><li>FIGURE 33 illustrates the Folded First Output Array With External Switches in ALU Tree Summation Mode 1.</li><li>FIGURE 34 illustrates the Folded First Output Array With Switches in Y Value Reverse Communications Mode 2.</li><li>FIGURE 35 shows an Eight Neuron Structure (G=4, H=16): Mode 1: Forward ALU Tree Summation.</li><li>FIGURE 36 shows an Eight Neuron Structure (G=4, H=16): Mode 2: Y Value Reverse Communications.</li><li>FIGURE 37 shows an Eight Neuron Structure (G=4, H=16): Mode 3: E Value Reverse Communications.</li><li>FIGURE 38 shows an Eight Neuron Structure (G=4, H=16): Mode 4: Weighted Error ALU Tree Summations (General-PEs Select Opposite E values for Multiplication).</li><li>FIGURE 39 shows a Sixteen Neuron Structure (N=16, G=16, H=16) Mode 1: Forward ALU Tree Summation.</li><li>FIGURE 40 shows a Sixteen Neuron Structure (N=16, G=16, H=16) Mode 2: Y Reverse Communication.</li><li>FIGURE 41 illustrates an Alternative Building Block - The Folded Inner Square. (Note: For convenience of illustration, FIGURES may be separated in parts and as a convention we place the top of the FIGURE as the first sheet, with subsequent sheets proceeding down when viewing the FIGURE, in the event that multiple sheets are used.)</li></ul>

0014Our detailed description follows as parts explaining our preferred embodiments of our invention provided by way of example.

DETAILED DESCRIPTION OF THE INVENTION

0015Before considering our preferred embodiments, it may be worthwhile to introduce some common features which are used in illustrating our preferred embodiments.

1. INTRODUCTION

0016The scalable massively parallel group partitioned diagonal-fold switching tree computing apparatus is described by way of a neural emulation example. For neural emulation the neuron model to be employed must be described. Consequently, the following neuron definition is provided. The change has been the addition of a term <i>Ex</i>_<i>i</i> which represents the external input to a neuron processing element.<maths id="math0001"><img file="EP0569764A2_D0001.tif" /></maths>

0017In many feed-forward neural networks only the input layer of neurons use an external input. In the literature - Rumelhart 86, the input neurons of a feedforward network take on an identity activation/output function, where <i>Y</i>₁=<i>Ex</i>₁, rather than the sigmoid function as do the other neurons in the neural network. A sigmoid function can be used instead for the input neurons, allowing all neurons to posses the same activation function, by extending the range of <i>Ex</i>_<i>i</i> to - <i>A</i> ≦ <i>Ex</i>_<i>i</i> ≦ + <i>A</i>, where - A will equate to <i>Y</i>_<i>i</i> = 0 and + A will equate to <i>Y</i>_<i>i</i> = 1 assuming the case where <i>Ex</i>_<i>i</i> is the only input to a neuron. Within some acceptable range of error, the input neurons can be forced to a "0" or a "1" state via use of the external input <i>Ex</i>_<i>i</i>. The <i>Ex</i>_<i>i</i> for the other neurons in the network can be equated to zero if not required. The neuron activation function <i>F</i>(<i>z</i>_<i>i</i>) is set equal to a sigmoid function whose form, for example, is:<maths id="math0002"><img file="EP0569764A2_D0002.tif" /></maths> Where: <ul id="ul0002" list-style="none"><li>· e = Natural Log (2.71828...)</li><li>· For the function <i>F</i>(<i>z</i>_<i>i</i>):<maths id="math0003"><img file="EP0569764A2_D0003.tif" /></maths></li><li>· 0≦<i>F</i>(<i>z</i>_<i>i</i>)≦1</li><li>· T is a global control parameter used to modify the slope of the sigmoid function for a given set of <i>z</i>_<i>i</i> values.</li></ul>

0018The TSNAP structure due to its use of <i>N</i>² processing elements and N Communicating ALU Trees (CATs), can not be easily built, for non trivial values of N. A TSNAP structure, representative of a massively parallel processing system, for non trivial N, suggests the necessity for a scalable design based on a processing array that can be used as a common "building block" that is implementable on a single chip. To demonstrate the scalability of the TSNAP structure, it is required that a TSNAP be partitioned into equal size processor array "building blocks", that can be used to construct larger arrays having the same triangular structure, and to preserve the TSNAP functionality in the constructed structure. Assume that the requirements of the previous statement can be demonstrated, the partitioning method can be utilized to build a TSNAP for an arbitrary size of N, governed by the designers chosen partitioning restrictions, thereby demonstrating a machine organization that is scalable.

0019Briefly then, for neural emulation, the programmability of the processor elements (PEs) modeling the connection weight function, termed synapse function, is obtained through the instructions which are received at a PE INSTR register from the attached communicating ALU tree that is in a communications mode. Each PE upon receipt of an instruction will execute the operation specified by that instruction sending the result to the specified destination which may be the attached ALU tree. The instruction types include a data and command path determining instruction, arithmetic, and logical instructions. The TSNAP multiplication elements are depicted in -- Fig 'SPA1' unknown -- A and B while an example of the corresponding processor elements are shown in -- Fig 'SPA1' unknown -- C and D. Each PE contains an instruction register for each processing element specifying the source and destination paths and EXU functions; a Diagonal-PE contains one instruction register and the General-PE contains two instruction registers.

0020To clarify the concepts presented, a 4 neuron example is shown in -- Fig 'SPA3' unknown --. An example of the neural emulation equation for neuron 3, generated by Root Tree Processor #3, is written here and the corresponding storage elements are highlighted in -- Fig 'SPA3' unknown <i>--.</i><maths id="math0004"><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">Y₃=F(W</mtext></mrow><mrow><mtext mathvariant="italic">3,1</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">Y₁+W</mtext></mrow><mrow><mtext mathvariant="italic">3,2</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">Y₂+W</mtext></mrow><mrow><mtext mathvariant="italic">3,3</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">Y₃+W</mtext></mrow><mrow><mtext mathvariant="italic">3,4</mtext></mrow></msub><mtext mathvariant="italic">Y₄)</mtext></mrow></math><img file="EP0569764A2_D0004.tif" /></maths>    This invention addresses how a TSNAP type of processor structure, for a given size of N, can be built utilizing a single common replicatable design that is also used for physically expanding the system, thereby providing a scalable design. In the first section, a partitioning approach demonstrates that a triangular array of PEs is partitionable into multiple triangular and square arrays of PEs. The second section presents a partitioning algorithm that creates two triangular arrays from each square array produced by application of the partitioning approach, under a set of element mapping rules. It is shown that the triangular arrays that result from the partitioning algorithm are equivalent to the triangular arrays produced by application of the partitioning approach. Two examples are presented in the following section demonstrating application of the partitioning methodology to the TSNAP structure. The next sections are concerned with presenting a "regular" interconnection mechanism that connects multiple "building block" arrays into a system that preserves the functionality of a constructed TSNAP. In the first of these next sections the functionality requirements of the partitioned design are discussed. Second, an algorithm that creates a "regular" interconnection mechanism is presented. Third, the interconnection mechanism is shown to preserve the TSNAP functionality requirements. Fourth, two examples are presented demonstrating application of the interconnection mechanism. A final section, briefly discusses an alternative scaling approach.

2. TRIANGULAR ARRAY PARTITIONING

0021By construction, consider a triangular array of elements with the property that each edge of the array possesses K elements, -- Fig 'THEORM1' unknown --. <u>THE PARTITIONING APPROACH</u>: Let K and X be integers such that K is divisible by X, then a triangular array of dimension K can be partitioned into:<maths id="math0005"><img file="EP0569764A2_D0005.tif" /></maths> AND<img file="EP0569764A2_D0006.tif" /> A triangular array can be partitioned into<img file="EP0569764A2_D0007.tif" /> partitions,<img file="EP0569764A2_D0008.tif" /> being trapezoids and one partition being an equilateral triangle of dimension X. (see -- Fig 'PART3' unknown --) A trapezoid contained by the <i>i</i>^<i>th</i> and (<i>i</i>+1)^<i>th</i> horizontal "lines" possesses dimensions X (side), iX (top), X (side on diagonal edge of the triangle), and (i+1)X (bottom). There being iX and iX + X elements in the top and bottom edges of the <i>i</i>^<i>th</i> trapezoid suggests that the trapezoid can be partitioned by X into "i" X by X square arrays and one equilateral triangular array of dimension X, -- Fig 'PART3' unknown--. Thus, given that there are<img file="EP0569764A2_D0009.tif" /><img file="EP0569764A2_D0010.tif" /> partitions, there are equilateral triangles of dimension X. Additionally, because there are "0" squares due to the first partition (the first partition is an equilateral triangle), one X by X square due to the second partition, and<img file="EP0569764A2_D0011.tif" /> X by X squares in the last<img file="EP0569764A2_D0012.tif" /> partition, there are:<maths id="math0006"><img file="EP0569764A2_D0013.tif" /></maths>

3. PARTITIONING ALGORITHM

0022The partitioning approach suggests the subdivision of a triangular array into triangles and squares. The ultimate goal of the partitioning, however, is not to provide the capability of having two common designs to produce one arbitrary TSNAP structure, as the approach suggests, but rather to provide a single "building block". To that extent, it is demonstrated that it is possible to partition an arbitrary TSNAP triangular structure into multiple triangular arrays of equal size. Clearly, the square arrays that are a result of the partitioning approach can not be subdivided into two equal size triangular arrays. To achieve the partitioning of the square arrays, further considerations must be associated with the structures resulting from the partitioning approach. By observing the TSNAP structure, the following holds true: <ul id="ul0003" list-style="none"><li>1. The diagonal edge elements contain single processing elements, the Diagonal-PEs.</li><li>2. The rest of the elements contain dual processing elements, the General-PEs.</li></ul> By utilizing this consideration on the type of elements contained in the triangular structure and applying the partitioning approach, there is produced: <ul id="ul0004" list-style="none"><li>1.<img file="EP0569764A2_D0014.tif" /> triangular arrays of dimension X, wherein the X diagonal elements are single processor Diagonal-PEs and the rest of the processors are dual processor General-PEs, -- Fig 'SQRE1' unknown --A, where a processor element is indicated by "a".</li><li>2.<maths id="math0007"><img file="EP0569764A2_D0015.tif" /></maths> square arrays of dimension X, wherein all processor elements are General-PEs, -- Fig 'SQRE1' unknown --B, where a dual processor element is indicated by a "bc".</li></ul> A partitioning algorithm, for the square structure described in -- Fig 'SQRE1' unknown --B, which takes a square array of dual processor elements, as produced from the partitioning approach, and creates two triangular arrays equivalent to the partitioning approach's triangular array made up of single Diagonal-PEs on the diagonal and dual General-PEs otherwise, is possible and described by the following: <ul id="ul0005" list-style="none"><li>1. Begin with a partitioning approach square array, as exemplified by -- Fig 'SQRE1' unknown --B..</li><li>2. Create two X by X arrays, labeled (C) and (D) in -- Fig 'SQRE2' unknown --, where the first X by X array (C) is made up of the elements "b" from -- Fig 'SQRE1' unknown --B, and the second X by X array (D) is made up of the elements "c" from -- Fig 'SQRE1' unknown --B.</li><li>3. Fold both arrays (C) and (D), -- Fig 'SQRE3' unknown --.</li></ul> It should be noted, in -- Fig 'SQRE3' unknown --, that the triangular arrays contain single processing elements equivalent to Diagonal-PEs on the diagonal and dual processing elements equivalent to General-PEs otherwise. Therefore, if N is divisible by X, it can be concluded that a TSNAP triangular array of size N can be partitioned into smaller triangular arrays each of size X, having single Diagonal-PEs in the diagonal and dual General-PEs in the rest.

4. PARTITIONING EXAMPLES

0023To clarify the partitioning of a triangular array, consider a TSNAP structure suitable for the emulation of an eight neuron network, based upon the synapse processor architecture shown in -- Fig 'TRNGL1' unknown --, where:<maths id="math0008"><img file="EP0569764A2_D0016.tif" /></maths> and where the multiplication operation is specified by a MPYA-R1*R2→T instruction indicating that R1, containing <i>W</i>_<i>ij</i>, is multiplied by R2, containing <i>Y</i>_<i>j</i>, with the product result sent to the attached ALU tree. For the purposes of demonstrating the partitioning steps the external input term <i>Ex</i>_<i>i</i> can be ignored.

0024The partitioning methodology suggests that the TSNAP structure can be partitioned into multiple triangular and square arrays which, for the eight neuron example with K=8 and X=4 partitions, consists of 2 triangular arrays and 1 square array. Separating the sub-divided arrays from the main structure and allowing the final stage of the ALU trees to be external to the arrangement of PEs results in the structure shown in -- Fig 'TRNGL2' unknown --, which contains the three structures i.e. the two triangular arrays and one square array. It should be noted that the triangular arrays contain the single Diagonal-PEs in the diagonal elements and the dual General-PEs in the rest of the elements and the square array is composed of General-PEs only. Since the goal is to produce a single chip array design that can be replicated to build an arbitrary size N TSNAP structure, the square structures must be partitioned into triangular structures, as indicated by the partitioning algorithm.

0025It can be observed that in the partitioned square array of the eight neuron example, -- Fig 'TRNGL2' unknown --, that there are two sets of orthogonal trees interconnecting the dual processor General-PEs producing four outputs from the horizontal set of trees and four outputs from the vertical set of trees. The first step is to separate the square array, -- Fig 'SQSPLIT' unknown --A, into two square arrays of single processors, -- Fig 'SQSPLIT' unknown --B and -- Fig 'SQSPLIT' unknown --C, where the separation keeps intact the horizontal and vertical trees and their connected processor. Folding both the horizontal tree and vertical tree square processor arrays along their top-left to bottom-right diagonal creates two triangular arrays with single Diagonal-PEs on the diagonal and dual General-PEs in the rest of the elements, -- Fig 'TRNGL4' unknown --A and -- Fig 'TRNGL4' unknown --B. It is observed that the triangular structures produced from the partitioning approach are of the same form and dimension as the triangular arrays produced by application of the partitioning approach. The partitioning process also partitions the Communicating ALU Tree (CAT), moving a portion of the tree external to the triangular array chips. The portion of the tree that remains on the triangular array chips for values of X is given by: <maths id="math0009"><math display="inline"><mrow><mtext>Number of on Chip CAT Stages = </mtext><mtext mathvariant="italic">ceiling</mtext><mtext>(log₂</mtext><mtext mathvariant="italic">X</mtext><mtext>)</mtext></mrow></math><img file="EP0569764A2_D0017.tif" /></maths> The resulting number of CAT stages that must be external to the triangular array chips is given in terms of N and X as: <maths id="math0010"><math display="inline"><mrow><mtext>Number of External CAT Stages = </mtext><mtext mathvariant="italic">ceiling</mtext><mtext>(log₂</mtext><mtext mathvariant="italic">N</mtext><mtext>) </mtext><mtext mathvariant="italic">- ceiling</mtext><mtext>(log₂</mtext><mtext mathvariant="italic">X</mtext><mtext>)</mtext></mrow></math><img file="EP0569764A2_D0018.tif" /></maths> The ceiling function produces the closest integer value that is larger than the operand if the operand is fractional and the operand value otherwise. For values of X that are not a power of 2, a balanced binary tree is maintained through use of delay elements in the tree stages, as appropriate. The external ALU tree summation and sigmoid emulation functions, and CAT communication paths, completing the 8 neuron model, are shown in -- Fig 'TRNGL5' unknown -- where the (→) indicates the CAT summation path and the (←) indicates the CAT communications path. By following the partitioning process, the large triangular structure of -- Fig 'TRNGL1' unknown -- has been shown to be made up of 4 smaller triangular arrays.

0026To facilitate the description of the partitioning process and resulting common "building block" triangular processor array chip, a new notation relating to groups of processors will be introduced here. The number of groups of processor arrays, i.e. the number of triangular array chips, is indicated by "G" and "H" represents the number of single processor elements within a group G, accounting for the dual processor General-PEs. G and H, in terms of N and the partitioning factor X, where X is determined from technology considerations, are specified by the following equations:<maths id="math0011"><img file="EP0569764A2_D0019.tif" /></maths> For example, in the N=8 neuron emulation case with X=4, each partitioned triangular structure represents a group chip of size H=16. -- Fig 'TRNGL2' unknown -- depicts two group chips, one producing signals A1, A2, A3, and A4 and the second producing signals B5, B6, B7, and B8. -- Fig 'TRNGL4' unknown -- depicts the separated triangular array group chips, one producing signals B1, B2, B3, and B4 and the other producing signals A5, A6, A7, and A8. To make the N=8 triangular array, -- Fig 'TRNGL1' unknown --, four group chips, G=4, are required.

0027Another example, where N=16, is presented to further clarify the partitioning process. The first step is to partition the 16 neuron emulation structure into groups of triangular and square arrays based on a choice of X. For the N=16 neuron example, an X=4 was chosen as shown in --Fig 'TRNGL6' unknown --. For a 16 neuron model using a group size H of 16, there are 4 triangular arrays, labeled <u>1, 2, 3,</u> and <u>4</u> and 6 square arrays, labeled <u>5, 6, 7, 8, 9,</u> and <u>10</u>. The square arrays are each separated into two single processor square arrays, preserving their horizontal and vertical trees, and then folded into the desired triangular arrays. The resulting 16 triangular arrays, in this case, are shown in -- Fig 'TRNGL7' unknown -- through --Fig 'TRNGL14' unknown --, each marked with a group label referring to -- Fig 'TRNGL6' unknown -- The external ALU tree summation and sigmoid emulation functions, and CAT communications paths, completing the 16 neuron model, are shown in -- Fig 'TRNGL15' unknown --, where (→) indicates the forward summation path and the (←) indicates the reverse communications path. For ease of representation, in -- Fig 'TRNGL6' unknown -- through -- Fig 'TRNGL16' unknown -- and other figures used through out this paper, please note the letters A through G are substituted for numeric values 10 through 16 for the neuron weights and Y values: <ul id="ul0006" list-style="none"><li>· A = 10</li><li>· B = 11</li><li>· C = 12</li><li>· D = 13</li><li>· E = 14</li><li>· F = 15</li><li>· G = 16</li></ul>

5. EXTERNAL TREE REQUIREMENTS AND DESCRIPTION

0028It should be noted that the partitioning algorithm applied to restructure the square arrays as two triangular arrays, affected the CAT communication path. We continue our discussion on the group partitioning algorithms, with the purpose of demonstrating that the functionality of the original structure can be preserved after partitioning has been completed. In order to demonstrate the preservation of functionality, it is important to establish the functional requirements. First, for ease of description, the external tree requirements without learning are described, using an example tree and switching mechanism for both the N=8 and N=16 with X=4 examples, -- Fig 'TRNGL16' unknown --. Second, additional requirements and how they are met in order to include support for learning are described.

0029-- Fig 'TRNGL16' unknown --A presents the external switch path mechanism and CATs and for the 8 neuron emulation example for Y1 and Y5 while -- Fig 'TRNGL16' unknown --B presents the external switches and CATs for the 16 neuron emulation example for Y1, Y5, Y9, and YD. The same type of switching tree mechanisms are used for the other emulated neuron outputs in each example. It is important to note that a path switch in the CAT communications path is implemented by the switching tree mechanism. For example in -- Fig 'TRNGL16' unknown --A "Switch Position For Communications", Y1 is communicated to the A1 and A5 CAT paths while Y5 is communicated to B1 and B5. Referring to -- Fig 'TRNGL2' unknown -- and -- Fig 'TRNGL4' unknown --, triangular structures, it can be observed that within the Diagonal-PEs and General-PEs, the Y values are received into the correct register, opposite from the respective ALU tree's source point. The same switch in the communications path is observed in the 16 neuron example, -- Fig 'TRNGL16' unknown --B.

0030The switching tree mechanism, -- Fig 'TRNGL16' unknown --, requires further modification for the support of back-propagation learning. There are four different operating modes to be supported by the switching tree mechanism. Two of the modes are due to the neuron emulation of equations 1 and 2, as presented in -- Fig 'TRNGL16' unknown --A and -- Fig 'TRNGL16' unknown --B, and the other two are due to back-propagation learning. In particular, the operating modes are: <ul id="ul0007" list-style="none"><li>1. External summation of the partially created neuron input ALU summation function from the group chips.</li><li>2. Reverse communication of neuron output Y values.</li><li>3. Reverse communication of error signals <i>E</i>_<i>i</i> in learning, where <i>E</i>_<i>i</i> = <i>δ</i>_<i>i</i> - LEARN 90.</li><li>4. External summation of the weighted error ALU summations <i>ER</i>_<i>i</i> in learning, where</li></ul><maths id="math0012"><img file="EP0569764A2_D0020.tif" /></maths> Operating modes 1 and 4 relate to the CAT summation paths and operating modes 2 and 3 relate to the CAT communications path. The external ALU function and communication requirements for learning and neuron execution are different. Therefore, different values are externally summed and different values are communicated depending upon whether the hardware is in a neuron emulation mode or emulating a learning mode. In more detail, consider the communication paths for neuron execution as compared to learning. In neuron emulation mode, a communicated <i>Y</i>_<i>j</i> must be multiplied with its appropriate <i>W</i>_<i>i,j</i>, while in learning, a communicated error signal, <i>E</i>_<i>i</i>, must be multiplied with its appropriate <i>W</i>_<i>i,j</i> (see Rumelhart 86 and LEARN 90. This seemingly small change in subscripts of the reverse communicated values, <i>Y</i>_<i>j</i> and <i>E</i>_<i>i</i>, indicates that different communications paths are required for the <i>Y</i>_<i>j</i> value as compared to the <i>E</i>_<i>i</i> value. The different paths are due to the separated triangles of the partitioned inner square. The splitting apart of the partitioned inner square General-PE array into two single processor arrays, separated the internal General-PE path switch, required for complete connectivity. To maintain functionality, the internal General-PE path switch must, in some manner, be restored. The switching tree, -- Fig 'TRNGL16' unknown -- of the examples, must be modified to support both different path requirements for neuron emulation and learning. -- Fig 'TRNGL17' unknown -- presents the modified switching tree mechanism for the 8 neuron example where the labeled figures 1-4 correspond to the four switch operating modes described above. It will be noted that not all paths are modified, depending upon the operating mode. Using -- Fig 'TRNGL17' unknown --as an example, the operating mode (1) neuron input ALU summation paths, for signals A1 and B5, are the same paths required for the weighted error ALU summations, operating mode (4), for signals A1 and B5. In addition, the communication's paths for signals A1 and B5 are the same in both neuron emulation, operating mode (2), and in learning, operating mode (3). It should be noticed from -- Fig 'TRNGL2' unknown --, that A1 and B5 are associated with the diagonal triangular arrays not requiring use of the partitioning algorithm. The paths which must be modified, depending upon the operating mode, are those paths that are associated with the separated triangular structures from the partitioned inner squares.

6. SWITCHING TREE MECHANISM

0031The previous discussion concerning the four operating modes, suggests the necessity of a general switching mechanism and a procedure for defining the switch connections. In this section a procedure is presented that defines the switching tree for the interconnection of the "building block" chips generated from the partitioning algorithm. Following the description of the procedure to create a switching tree, it is demonstrated that the functionality for neural emulation is preserved by the switching tree mechanism.

0032Consider a generalized triangular array, as depicted in -- Fig 'EXTSWTR' unknown --, with the triangular and square arrays outlined, as produced by application of the partitioning approach with a partition size of X. It should be noted that the triangular and square array output signals are listed on the edges of the arrays in -- Fig 'EXTSWTR' unknown --. The triangular array outputs are placed on the bottom edge of the triangular array and the square array outputs are placed on the bottom and right side edges of the square arrays. It is assumed that balanced binary CATs are used throughout, where delay elements are used as appropriate to ensure a balanced tree. The generalized neuron emulation equations can be written as a function of the partitioned triangular and square array output signals, in terms of K, L, X, and N, by the following:<maths id="math0013"><img file="EP0569764A2_D0021.tif" /></maths><maths id="math0014"><img file="EP0569764A2_D0022.tif" /></maths> Consider an arbitrary inner square array, based on an arbitrary K and L shown in -- Fig 'GTPX' unknown --. Note that the balanced binary tree is symbolically depicted in -- Fig 'GTPX' unknown -- by using the letter "A" at node points. In applying the square partitioning algorithm, the arbitrary inner square can be partitioned into two folded triangular arrays. The algorithm is applied by separating the inner square into two square arrays, -- Fig 'SQSEP1' unknown -- and -- Fig 'SQSEP2' unknown --, followed by the folding to the triangular arrays, -- Fig 'FLDSQ1' unknown -- and -- Fig 'FLDSQ2' unknown --. To summarize, a generalized triangular array is used, from which a set of neuron equations are specified in terms of triangular and square array output signals, and the partitioning algorithm is applied creating the G triangular arrays.

0033As defined for, but not limited to, neuron emulation, i.e. the emulation of equation 1, the outputs of the partitioned triangular arrays are grouped into square arrays of output signals in the following manner: <ul id="ul0008" list-style="none"><li>1. Create the first of N/X square arrays composed of the partitioned group chips output signals for the Root Tree Processor emulated neurons represented by output signals <i>Y</i>₁, <i>Y</i>_<i>X</i>₊₁, <i>Y</i>_2<i>X</i>+1, ... , <i>Y</i>_<i>N-X</i>₊₁, -- Fig 'GRPSQ' unknown --. <ul id="ul0009" list-style="none"><li>a. Place the chips output signals associated with <i>Y</i>₁ in the first row of the array.</li><li>b. Place the chips output signals associated with <i>Y</i>_<i>X</i>₊₁ in the second row of the array.</li><li>c. Place the chips output signals associated with <i>Y</i>_2<i>X</i>+1 in the third row of the array.</li><li>d. Continue placing the chips output signals . . . in rows of the array, until:</li><li>e. Place the chips output signals associated with <i>Y</i>_<i>N-X</i>₊₁ in the last row of the array.</li></ul></li><li>2. Create the second of N/X square arrays composed of the partitioned group chips output signals for the Root Tree Processor emulated neurons represented by output signals Y₂, <i>Y</i>_<i>X</i>₊₂, <i>Y</i>_<i>2X</i>₊₂, ... , <i>Y</i>_<i>N-X</i>₊₂.</li><li>3. Continue creating square arrays composed of the partitioned group chips output signals for the Root Tree Processor emulated neurons represented by output signals . . . , until:</li><li>4. Create the <i>N</i>/<i>X</i>^<i>th</i> square array composed of the partitioned group chips output signals for the Root Tree Processor emulated neurons represented by output signals <i>Y</i>_<i>X</i>, <i>Y</i>_2<i>X</i>, <i>Y</i>_3<i>X</i>, ... , <i>Y</i>_<i>N</i>.</li></ul> This procedure creates N/X square arrays of output signals from the partitioned triangular arrays. For example, the first square array for the Root Tree Processor emulated neurons represented by output signals <i>Y</i>₁, <i>Y</i>_<i>X</i>₊₁, <i>Y</i>_2<i>X</i>+1, ... , <i>Y</i>_<i>N-X</i>₊₁ is shown in -- Fig 'GRPSQ' unknown --. In the next step of the switching tree procedure, each of these N/X squares is folded and external switches and ALU trees are added as shown in the following example for the Folded First Output Array -- Fig 'FFOA' unknown --. The <i>z</i>_<i>i</i> outputs of the N/X switching tree mechanisms are connected to the appropriate Host/Root Tree Processor completing the mechanism description.

7. SWITCHING TREE PRESERVES FUNCTIONALITY

0034To support the four operational modes, namely the neuron input summation (1), the Y value communications (2), the error signal communications (3), and the weighted error summation (4), the switches depicted in -- Fig 'FFOA' unknown -- require only two positions, assuming a bidirectional signal capability is possessed by the switches. In addition, balanced binary trees are assumed to be used in the switching tree mechanism.

0035The functionality of the switching tree for the emulation of equation 1 is demonstrated by examining operating mode (1) neuron input forward summation and operating mode (2) Y value communications. The folded first output array is used in these examples by setting the switches and observing that the functionality is met. For the neuron input summation operating mode (1), the switches are placed as depicted in -- Fig 'SWTSUM' unknown --. To verify the neuron input summation function is maintained through the switching tree, an arbitrary Y value is used, chosen based upon the arbitrary inner square separated from the general triangular array structure. For this example <i>Y</i>_<i>(K</i>_{-1)<i>X</i>+1} is chosen. The general equation for <i>Y</i>_<i>(K</i>_{-1)<i>X</i>+1} is repeated here: <maths id="math0015"><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">Y</mtext></mrow><mrow><mtext mathvariant="italic">(K</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>-1)</mtext><mtext mathvariant="italic">X</mtext><mtext>+1</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">F</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>1,(</mtext><mtext mathvariant="italic">K</mtext><mtext>-1)</mtext><mtext mathvariant="italic">X</mtext><mtext>+1</mtext></mrow></msub><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext>2,(</mtext><mtext mathvariant="italic">K</mtext><mtext>-1)</mtext><mtext mathvariant="italic">X</mtext><mtext>+1</mtext></mrow></msub><msup><mrow><mtext>+</mtext></mrow><mrow><mtext>...</mtext></mrow></msup><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext mathvariant="italic">K,</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>(</mtext><mtext mathvariant="italic">K</mtext><mtext>-1)</mtext><mtext mathvariant="italic">X</mtext><mtext>+1</mtext></mrow></msub><msup><mrow><mtext>+</mtext></mrow><mrow><mtext>...</mtext></mrow></msup><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext mathvariant="italic">L</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>,(</mtext><mtext mathvariant="italic">K</mtext><mtext>-1)</mtext><mtext mathvariant="italic">X</mtext><mtext>+1</mtext></mrow></msub><msup><mrow><mtext>+</mtext></mrow><mrow><mtext>...</mtext></mrow></msup><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">A</mtext></mrow><mrow><mtext mathvariant="italic">N/X,</mtext></mrow></msub><msub><mrow><mtext>​</mtext></mrow><mrow><mtext>(</mtext><mtext mathvariant="italic">K</mtext><mtext>-1)</mtext><mtext mathvariant="italic">X</mtext><mtext>+1)</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">F</mtext><mtext>(</mtext><msub><mrow><mtext mathvariant="italic">z</mtext></mrow><mrow><mtext>(</mtext><mtext mathvariant="italic">K</mtext><mtext>-1)</mtext><mtext mathvariant="italic">X</mtext><mtext>+1</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0569764A2_D0023.tif" /></maths> In examining -- Fig 'SWTSUM' unknown -- it can be observed that the equation for <i>Y</i>_<i>(K</i>_{-1)<i>X</i>+1} is preserved. For the Y value communications mode (2), the switches are placed as depicted in -- Fig 'SWTYREV' unknown --. In the original<maths id="math0016"><img file="EP0569764A2_D0024.tif" /></maths> TSNAP structure prior to partitioning, the <i>Y</i>_<i>(K</i>_{-1)<i>X</i>+1} value would be communicated to each output signal point listed in the <i>Y</i>_<i>(K</i>_{-1)<i>X</i>+1} equation. In particular, referring to -- Fig 'GTPX' unknown -- the generalized inner square array prior to partitioning, <i>Y</i>_<i>(K</i>_{-1)<i>X</i>+1} would be returned through <i>A</i>_<i>L</i>_{,<i>(K</i>-1)<i>X</i>+1}. In each leaf node of the <i>A</i>_<i>L</i>_{,<i>(K</i>-1)<i>X</i>+1} tree in -- Fig 'GTPX' unknown --, the General-PEs would receive the <i>Y</i>_<i>(K</i>_{-1)<i>X</i>+1} value and switch paths internally to provide the correct destination point.

0036After partitioning the TSNAP structure, multiple triangular arrays are attached through the switching tree. Using the switching tree mechanism with switch settings as depicted in -- Fig 'SWTYREV' unknown --, <i>Y</i>_<i>(K</i>_{-1)<i>X</i>+1} would be transferred to points <i>A</i>_<i>K,N</i>_-<i>X</i>+1, <i>A</i>_<i>K</i>_{,(<i>L</i>-1)X+1}, <i>A</i>_<i>K</i>_{,(<i>K</i>-1)<i>X</i>+1}, <i>A</i>_<i>K</i>_,<i>X</i>+1, and <i>A</i>_<i>K</i>_,1. In following path <i>A</i>_<i>K</i>_{,(<i>L</i>-1)<i>X</i>+1}, which tree is shown in -- Fig 'FLDSQ2' unknown -- we find that <i>Y</i>_{(<i>K</i>-1)<i>X</i>+1} would enter the General-PEs leaf nodes and be switched internally to the proper register for the returning Y value.

0037In a similar manner, the other two operating modes can be demonstrated to function correctly with the switching tree mechanism.

0038In general, it can be concluded that the procedure for determining the switching tree mechanism preserves the TSNAP functionality, supporting the four operating modes, in the TSNAP structure constructed from multiple "building block" arrays and switching tree mechanisms.

8. SWITCHING TREE EXAMPLES

0039To further clarify the switching tree mechanism two examples are presented. The first example follows from the eight neuron emulation model with G=4 and H=16. -- Fig 'TRNGL18' unknown -- depicts the switching tree configured for mode (1) providing the neural input summations to the Host/Root Tree Processors. For example in -- Fig 'TRNGL18' unknown --, Y7' is generated in Root Tree Processor 7 from the A7 and B7 inputs supplied to the switching tree. A7 supplies the quantity (W71Y1 + W72Y2 + W73Y3 + W74Y4) while B7 supplies the quantity (W75Y5 + W76Y6 + W77Y7 + W78Y8). In Y value communication's mode (2) the switching tree mechanism is configured as shown in -- Fig 'TRNGL19' unknown --. For example, Y7 is communicated to points B3 and B7 which are the correct paths for Y7.

0040The switching tree is configured for operation mode (3) as shown in -- Fig 'TRNGL20' unknown -- which communicates the error signals <i>E</i>_<i>i</i>, for example <i>E</i>₇ through points A7 and B7 with the General-PEs switching the internal path in the same manner as the General-PEs received Y values. For the weighted error summation operating mode (4), the General-PEs select the W values that are associated with the opposite processor, as symbolized by the "X" cross in the center of the General-PE cells depicted in -- Fig 'TRNGL21' unknown --. The operand choice is easily determined by the instruction received in each General-PE processor. For example: <maths id="math0017"><math display="inline"><mrow><mtext>ER7 = B3 + B7</mtext></mrow></math><img file="EP0569764A2_D0025.tif" /></maths> Where: <maths id="math0018"><math display="inline"><mrow><mtext>B3 = W17*E1 + W27*E2 + W37*E3 + W47*E4</mtext></mrow></math><img file="EP0569764A2_D0026.tif" /></maths><maths id="math0019"><math display="inline"><mrow><mtext>B7 = W57*E5 + W67*E6 + W77*E7 + W87*E8</mtext></mrow></math><img file="EP0569764A2_D0027.tif" /></maths>    The scalability obtained through use of the partitioning algorithms and the switching mechanism is easily seen in an example that doubles the number of neurons from 8 to 16, using four times as many triangle processing array chips, -- Fig 'TRNGL22' unknown -- and -- Fig 'TRNGL23' unknown --. In these examples, the switching tree mechanism is modified to support the larger system.

0041For example in -- Fig 'TRNGL22' unknown --: <maths id="math0020"><math display="inline"><mrow><mtext>Y7 = A7 + B7 + C7 + D7</mtext></mrow></math><img file="EP0569764A2_D0028.tif" /></maths> Where: <maths id="math0021"><math display="inline"><mrow><mtext>A7 = W71*Y1 + W72*Y2 + W73*Y3 + W74*Y4</mtext></mrow></math><img file="EP0569764A2_D0029.tif" /></maths><maths id="math0022"><math display="inline"><mrow><mtext>B7 = W75*Y5 + W76*Y6 + W77*Y7 + W78*Y8</mtext></mrow></math><img file="EP0569764A2_D0030.tif" /></maths><maths id="math0023"><math display="inline"><mrow><mtext>C7 = W79*Y9 + W7A*YA + W7B*YB + W7C*YC</mtext></mrow></math><img file="EP0569764A2_D0031.tif" /></maths><maths id="math0024"><math display="inline"><mrow><mtext>D7 = W7D*YD + W7E*YE + W7F*YF + W7G*YG</mtext></mrow></math><img file="EP0569764A2_D0032.tif" /></maths> In -- Fig 'TRNGL23' unknown -- Y7 is reverse communicated through points B3, B7, B11, and B15 which, it can be observed, are the correct group chip output points by noting the General-PE destinations for Y7 in the B3, B7, B11, and B15 group chips.

0042In general, as the group partitioning algorithm is applied to larger structures with a fixed size of X, more ALU tree stages are added to the external ALU tree. Assuming an implementation where a processor group is placed on a single chip, i.e. H processing elements on a chip, then a scalable processor array design can be built where only the switching trees need to be modified as additional group chips are added. This can be seen in the 8 and 16 neuron model examples, where the same size triangular array chip design is used in the construction of both N=8 and N=16 TSNAP structures and only the external CATs are modified.

9. ALTERNATIVE SCALING METHODS

0043From the perspective of the reviewed partitioning approach presented in this paper, alternatives also exist. One will be briefly mentioned for completeness. It should be noted that the inner squares prior to separation into triangles, could be folded, as exemplified by folding the 8 neuron inner square of -- Fig 'TRNGL2' unknown -- shown in -- Fig 'FLDSQR' unknown --, and be used as a common replicatable "building block". By zeroing out the weights and Y values for half of the folded array, a folded square array can model the functions of the edge triangular arrays using twice as many processors. With this arrangement of groups, there is still a requirement for an external switching function. Instead of requiring the switching function due to the separated folded inner square triangular arrays, the switching function is needed for the edge triangular arrays modeled on the folded square building block. Since the folded square building block approach requires twice as many PEs in a processor group, for a given size diagonal triangular array, and there is still a requirement for a switching tree function, the folded square building block approach will not be considered further in this paper, though it represents a viable alternative that merits additional research.

10. SWITCHING TREE IMPLEMENTATION CONSIDERATIONS

0044An important consideration for the implementation of the switching tree is the method of changing the CATs' summation/communication state and the switching trees' switch state in synchronism and to ensure no hazards in operation. Based upon an architectural definition of the processor elements that they respond as programmable execution units, and with an additional restriction that a single instruction response completion interlocking mechanism be utilized between the Root Tree Processors and the PEs, the hazard free control of the CATs and switching trees can be obtained. The Root Tree Processors represent the controlling source for instructions/data processed by the PEs. Consequently, the hazard free control of the system is obtained by ensuring the Root Tree Processors never send an instruction, or data value in a pending PE instruction automatic mode, to be executed by the PEs, until the previous instruction has completed, as indicated by a response completion signal SVLM 91 or a Root Tree Processor timeout LEARN 90. The Root Tree Processors also control a synchronization tag signal, one per CAT, which is set active whenever instructions or data are sent to the PEs and set inactive otherwise. The synchronization tag can be used to provide directional control for the CAT ALU nodes and switching tree switch states. When the synchronization tag is active, the CAT ALU nodes and the switching tree switch states are set to the communication mode, allowing an instruction or data value to bypass the ALU nodes and be sent to the proper points by the correct setting of the switches. When the synchronization tag is inactive, the CAT and switching tree switches are placed into the ALU function mode (summation mode for neural emulation). For example, the Root Tree Processors first set the synchronization tags active, second send the instruction, or data in a pending PE automatic mode, to the PEs, and third set the synchronization tags inactive at the conclusion of the instruction/data message. The Root Tree Processors then wait for the timeout or completion indication before sending the next instruction/data to the PEs.

0045It may be desirable that a switching tree group be incorporated on a single chip. For this situation the limiting parameter to be considered is the I/O capacity of the chip rather than the chip real estate logic density. The switching tree, as described previously, requires G + X I/O lines in support of the group chips' and tree roots' signals. Additional I/O lines for control must also be accounted for. For example, X synchronization tag and 2 switch mode control signals may be utilized. For development purposes, a beginning assumption for a switching tree chip I/O count would be G + 2X + 2 + spare I/O lines. For a large system, where G=256 and X=16 for example, the number of I/O lines for technology considerations would be 290 + spare.

11. SUMMARY

0046A partitioning methodology that creates a common "building block" chip, whose size can be determined due to technology considerations has been demonstrated. Based upon technology constraints and the desired applications, a size of X can be determined that optimizing the use of the available real estate. By utilizing the common "building block" chips, a completely connected Root Tree Processor system suitable for completely connected neural network emulation may be constructed that meets requirements. The system once built, can be expanded without greatly impacting a system implementation, but greatly improving system performance.