Scalable Flow Virtual Learning Neurocomputer

In addition, filed concurrently are related applications:

A LEARNING MACHINE SYNAPSE PROCESSOR SYSTEM APPARATUS G. G. Pechanek, S. Vassiliadis, and J. G. Delgado-Frias, U.S. Ser. No. 07/702,261, filed May 17, 1991 now abandoned sometimes referred to as "LEARNING MACHINE", or Pechanek LEARN 91.

VIRTUAL NERUOCOMPUTER ARCHITECTURES FOR NEURAL NETWORKS, G. G. Pechanek, J. G. Delgado-Frias, and S. Vassiliadis, U.S. Ser. No. 07/702,260, filed May 17, 1991, issued as U.S. Pat. No. 5,243,688 sometimes referred to as "VIRTUAL", or Penchanek VIRTUAL 91.

PLAN: PYRAMID LEARNING ARCHITECTURE NEUROCOMPUTER, G. G. Pechanek, S. Vassiliadis, and J. G. Delgado-Frias, U.S. Ser. No. 07/702,263, filed May 17, 1991, now abandoned sometimes referred to as "PLAN".

These co-pending applications and the present application are owned by one and the same assignee, namely, International Business Machines Corporation of Armonk, N.Y.

The descriptions set forth in these co-pending applications are hereby incorporated into the present application by this reference.

The inventions relate to a scalable flow virtual learning neurocomputer system and apparatus and particularly to a scalable hybrid control flow/data flow virtual learning neurocomputer which employs a new group partitioning algorithm, and a scalable virtual learning architecture, synapse processor architecture (SPA) mapping, inner square folding and array separation, with capability of back propagation for virtual learning.

During the detailed discussion of our inventions, we will reference other work including our own unpublished works which are not Prior Art but which will aid the reader in following our discussion. These additional references are:

D. E. Rumelhart, J. L. McClelland, and the PDP Research Group, Parallel Distributed Processing Vol. 1: Foundations Cambridge, Mass.: MIT Press 1986. (Herein referred to as "Rumelhart 86".)

J. J. Hopfield, "Neurons With Graded Response Have Collective Computational Properties Like Those of Two-State Neurons," Proceedings of the National Academy of Sciences 81, pp. 3088-3092, May, 1984. (Herein referred to as "Hopfield 84".)

A LEARNING MACHINE SYNAPSE PROCESSOR SYSTEM APPARATUS G. G. Pechanek, S. Vassiliadis, and J.G. Delgado-Frias, U.S. Ser. No. 07/702,261, filed May 17, 1991 sometimes referred to as "LEARNING MACHINE" or Pechanek LEARN 91.

VIRTUAL NERUOCOMPUTER ARCHITECTURES FOR NEURAL NETWORKS, G. G. Pechanek, J. G. Delgado-Frias, and S. Vassiliadis, U.S. Ser. No. 07/702,260, filed May 17, 1991, issued as U.S. Pat. No. 5,243,688 sometimes referred to as "VIRTUAL" or Pechanek VIRTUAL 91.

H. Hellerman, Digital Computer System Principles McGraw-Hill Book Company, pp. 346-348. (Herein referred to as "Hellerman 67".)

Virtual learning implies the ability to modify the virtual connection weights and the virtual neural state values stored in an external memory. This function would be desireable for an environment which demands the complete scalability of other functions developed in co-pending applications. This function and an apparatus for achieving it has not been developed.

We have provided a virtural learning neurocomputer apparatus which is termed the Scalable Virtual Learning Machine (SVLM) providing high performance direct emulation and virtual learning capability in a completely connected scalable architecture. Our SVLM provides the ability to modify the virtual connection weights and the virtual neural state values stored in the external memory to which the apparatus can be connected. In accordance with our inventions we have provided a scalable group partitioned virtual neural synapse processor architecture apparatus with an N neuron structure partitioned into groups of synapse processing units. Each group has multiple synapse processing units that contain instruction and data storage units, receive instructions and data, and execute instructions, and interface with external data storage for weights and neuron output values for V neurons, where V>N and V is the number of neurons in the neural network to be emulated on the group partitioned N neuron structure. The groups execute group instruction and have communicating adder trees. The N neuron structure has neuron activation function units in the preferred form of a sigmoid generator, and the structure provides for interconnecting the groups into an N neuron structure which supports V neurons and for communicating both instructions, data, and the outputs of the neuron activation function units back to the input synapse processing units by way of the communicating adder trees.

The scalable flow virtual learning neurocomputer system appratus has a scalable hybrid control flow/data flow and employs a group partitioning algorithm for the scalable virtual learning architecture. We provide synapse processor architecture mapping, inner square folding and array separation, with capability of back propagation for virtual learning.

The group partitioning algorithm creates a common building block of synapse processors containing their own external memory. The processor groups are used to create a general purpose virtual learning machine which maintains complete connectivity with high performance. The synapse processor group allows a system to be scalable in virtual size and allows direct execution capabilities. Internal to the processor group, the synapse processors are designed as a hybrid control flow/data flow architecture with external memory access and reduced synchronization problems.

The general computer architecture supporting neural networks which is developed utilizes a method of folding and separating an array of "synapse" processors creating a cluster of processors, or a processor group, which represents a common building block for neurocomputer implementations. A neurocomputer made up of these processor groups directly executes a completely connected N neuron network model and supports a virtual mode of execution for network models containing greater than N neurons. The synapse processor architecture (SPA) of each processor in the group supports the direct emulation scalability resulting from the group partitioning algorithm and supports virtual synapse scalability through the use of external memory. One of the features of the unique SPA is that it allows both control flow operation with sequential instruction execution and data flow operation where the execution is dependent upon the receipt of valid tagged data. Another unique feature of the architecture is the method of interfacing to processor groups which supports complete connectivity in a neural network model even though multiple processor groups are utilized in an implementation. Other unique features of the neurocomputer are the group notification of the completion of operations local to the synapse processors and support of learning algorithms.

These and other improvements are set forth in the following detailed description. For a better understanding of the inventions, together with advantages and features, reference may be had to the co-pending applications for other developments we have made in the field. 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.

FIG. 1 and FIGS. 1A and 1B shows a 4-neuron structure supporting 16 virtual neurons (256 Weights) weights.

FIG. 2 and FIGS. 2A-2D illustrates an 8 neuron array model.

FIG. 3 and FIGS. 3A-3D shows an 8 neuron array model split into 1 square and 2 smaller triangular processor arrays.

FIG. 4 and FIGS. 4A and 4B shows the folded inner square of the 8 neuron array model.

FIG. 5 and FIGS. 5A and 5B shows the folded inner square separated into two triangular arrays.

FIG. 6 shows a preferred external summation, sigmoid generator, and reverse communications path.

FIG. 7 and FIGS. 7A-7C shows a 16 neuron array model weight matrix with neuron Y values.

FIG. 8 and FIGS. 8A and 8B shows triangular arrays 1 and 2.

FIG. 9 and FIGS. 9A and 9B shows triangular arrays 3 and 4.

FIG. 10 and FIGS. 10A and 10B shows a folded inner square 5 separated into two triangular arrays.

FIG. 11 and FIGS. 11A and 11B shows a folded inner square 6 separated into two triangular arrays.

FIG. 12 and FIGS. 12A and 12B shows a folded inner square 7 separated into two triangular arrays.

FIG. 13 and FIGS. 13A and 13B shows a folded inner square 8 separated into two triangular arrays.

FIG. 14 and FIGS. 14A and 14B shows a folded inner square 9 separated into two triangular arrays.

FIG. 15 and FIGS. 15A and 15B shows a folded inner square 10 separated into two triangular arrays.

FIG. 16 and FIGS. 16A and 16B illustrates a preferred external summation, sigmoid generator, with a reverse communication path.

FIG. 17 and FIGS. 17A, 17Ba, and 17Bb illustrates a switching mechanism.

FIG. 18 illustrates alternatively a modified 8 neuron switching mechanism to support learning.

FIG. 19 and FIGS. 19A and 19B illustrates alternatively a modified 16 neuron switching mechanism to support learning.

FIG. 20 and FIGS. 20A and 20B illustrates another part of a modified 16 neuron switching mechanism to support learning.

FIG. 21 is a table illustrating the V and N relationship to storage and operating cycles.

FIG. 22 and FIGS. 22A-22D illustrates a 4 neuron scalable virtual learning machine with V=16, N=4, G=4.

FIG. 23 shows an external memory structure.

FIG. 24 and FIGS. 24A and 24B illustrates a scalable virtual learning machine's external memory structure for V=16, N=4, H=16, with 1 weight, 1 Y value bit per processor element, and H weight elements per processor group.

FIG. 25 and FIGS. 25A and 25B illustrates a synapse processor architecture with external memory, with a diagnoal synapse processor (DSYP) and a general synapse processor (GSYP).

FIG. 26 shows the 4-neuron SVLM timing for a 16 neuron neural network.

FIG. 27 shows the cycle time expanded to show detailed timing.

FIG. 28 illustrates a memory subsystem associate with each synapse processor group and the external memory addresssing structure.

FIG. 29 illustrates a neuron processor tagged instruction/data format.

FIG. 30 illustrates a neural network for solving the input/output problem.

FIG. 31 and FIGS. 31A-31D shows an 11 neuron I/O encoder problem mapped onto a 4 neuron scalable SVLM with V=16, N=4, G=4.

FIG. 32 and FIGS. 32A-32D illustrates the initializiation.

FIG. 33 and FIGS. 33A-33D illustrates first layer execution.

FIG. 34 and FIGS. 34A-34D illustrates set SO count to advance mode and reverse communicate Y1' and Y2'.

FIG. 35 and FIGS. 35A-35D illustrates second layer execution.

FIG. 36 and FIGS. 36A-36D illustrates reverse communicate Y3'.

FIG. 37 and FIGS. 37A-37D illustrates third layer execution.

FIG. 38 and FIGS. 38A-38 D illustrates reverse communicate Y4', Y5', Y6', and Y7'.

FIG. 39 and FIGS. 39A-39D illistrates fourth layer execution.

FIG. 40 and FIGS. 40A-40D shows the learning mode of Load S & I bits and SO and IA Counts, change data path to R4, and reverse communicate E8, E9, E10 and E11.

FIG. 41 and FIGS. 41A-41D shows the learning mode of issue MPY R6*R3 T to start multiply for weighted error summations: ER4, ER5, ER6 and ER7.

FIG. 42 and FIGS. 42A-42D shows learning mode of create weighted error summations: ER4, ER5, ER6 and ER7.

FIG. 43 and FIGS. 43A-43D shows the learning mode of step 1 weight updating MPY R5*R3 .fwdarw.R4.

FIG. 44 and FIGS. 44A-44D shows learning mode of step 2 weight updating MPY R4*IMD .fwdarw.R4.

FIG. 45 and FIGS. 45A-45D shows the learning mode of weight updating in external memory, ADD R6+R4.fwdarw.EXTMEM2.

(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.)

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

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

For the purposes of this description, the number V will be used to denote the number of neurons contained in the network to be modeled on the neurocomputer and the number N will denote the number physical neurons available in the physical implementation. For virtual processing V>N. The computational tasks to be implemented by the neurocomputer architectures described in this description are given by equation 1 and 2 which are based on a subset of the full Parallel Distributed Processing model of Rumelhart 86 and the Hopfield network, Hopfield 84. ##EQU1## Where: V is the number of neurons in the neural network.

The subscripts on the weights W (such as W.sub.13) are to be interpreted as meaning the weight of the connection from Neuron 3 to Neuron 1.

Y.sub.j is the j.sup.th neuron output value connected to the i.sup.th neuron input through a connection weight of W.sub.ij.

Ex.sub.j is an external input to the i.sup.th neuron.

-A<Ex.sub.j .ltoreq.+A where -A equates to Y.sub.j =0 and +A equates to Y.sub.j =1(.+-.an acceptable range of error) for the case where Ex.sub.j is the only input to the neuron.

F(Z.sub.j) is the neuron activation function which many times is set equal to a sigmoid activation function whose form, for example, is: ##EQU2## Where: For the function ##EQU3## 0.ltoreq.F(Z.sub.j).ltoreq.1 T is a global control parameter used to modify the slope of the sigmoid function for a given set of Z.sub.j values.

e=Natural log (2.71828 . . . )

Equations 1 and 2, for a completely connected V neuron network, contain four basic operations:

1. V.sup.2 Multiplications

2. V Product Summations

3. V Activation Functions

4. V.times.V Communications

Neurocomputer implementations have many difficult problems to surmount requiring a high degree of parallelism to achieve high performance. In relationship to the four basic operations for neural execution, it would be desireable to have V.sup.2 multiplication engines, V product summation and activation mechanisms, and a V.times.V communications medium with minimum delay. Typically V is large compared to N, where N represents the physically realizable neurocomputer. Since V>N, a virtual emulation capability in the neurocomputer is desireable in order to support numerous sizes of neural network models. Learning imposes further requirements in that more general purpose execution capabilities are needed in the neurocomputer architecture. Complete connectivity along with high performance in conjunction with virtual and learning capability, while providing an architecture which is scalable in both virtual capacity and in direct emulation capability, has been a difficult task. These issues are addressed with the Scalable Virtual Learning Machine (SVLM).

While our other co-pending applications are basic and applicable to many situations where they provide the best way of delivering a solution to needed problems, there are, we now recognize in certain situations, certain limitations which can be found in specific environments. For example, the General Purpose Learning Machine (GPLM) Synapse Processing Architecture (SPA) of our Pechanek LEARN 91. has the storage capacity of only a single connection weight and neuron val e per synapse processing element as is appropriate for the direct execution of a neural network model. This direct emulation capability limits V to be less than or equal to N. Further the GPLM utilized a simple state machine control mechanism not requiring the utilization of tagged data for synchronizational control of the automatic mode (see Pechanek LEARN 91). As V becomes large and virtual capability is added, the state machine control becomes complex. The SPA also contained local processing instructions which did not provide notification of completion to the instruction-issuing learning processor. A state machine control operation in the learning processor was assumed such that time outs, dependent upon instruction type, determined when a new instruction could be sent to the synapse processors. The virtual TSNAP of Pechanek VIRTUAL 91 included the storage of the virtual connection weights and neuron values within the synapse processing elements, allowing the emulation of networks of V neurons where V>N but thereby setting V to a fixed number and linking V and N to the technology capability. In addition, the virtual TSNAP did not support learning capability, using only a simple multiplication functional unit and the necessary weight and Y value storage instead. Multiple difficulties arise with both approaches due to the above characteristics as the number of neurons V to be emulated increases. One difficulty is the limitation on the size of a neural network which can be emulated on the structures. The GPLM will be limited to a physical implementation of N neurons, allowing only networks of V neurons where V.ltoreq.N can be emulated. Whereas the GPLM limited N, the virtual TSNAP limits V, also due to technology consideration. Once V is chosen and the chips built for the virtual TSNAP, V cannot be increased. Another difficulty is the practical consideration of the number of synapse processors which can be placed on a chip due to a chosen technology's cell and I/O capacity. Assuming a large number of synapse processing elements on a chip and a large number of chips utilized in a desired system, the synchronization control becomes very difficult. A state machine control approach for all operations is not feasible for large systems; once a state machine controlled system is built, it will not be easily extendable. In order to solve the synchronization of an instruction's automatic mode of operation, a new architecture is developed to support both control flow (sequential instruction execution) and data flow (data dependent execution) modes of operation. An instruction's automatic mode of operation becomes defined as a data flow controlled operation which requires valid tagged data to be received prior to "firing" the function. The local processing of instructions without notification also becomes problematic for large systems. A new method of notification of local processing completion is defined whereby the group summation trees are utilized, providing not only successful operation completion but also communication of errors which may have occurred in an operation. In this manner, the completion of all operations are notified to the instruction/data issuing processor, thus ensuring proper control and further allowing scalability.

Given a limited number of synapse processors on a chip, a special situation which may occur, the question becomes how can one build a large N neurocomputer with learning capability made up of multiple synapse processing chips which supports V neurons, where V.gtoreq.N, allowing future growth through expansion of not only the weight and neuron value storage thereby increasing the virtual capacity, but also expansion of the synapse processing elements, thereby increasing the direct execution capacity improving performance? Multiple new concepts will be presented in this description, such as a group partitioning algorithm, the hybrid control flow/data flow architecture, and notification of local synapse processing completion in order to solve this scalability problem while still preserving learning and complete connectivity among the modeled neurons and providing high emulation performance. A method of breaking a large triangular array of processors into smaller triangular processor array groups via a novel partitioning algorithm is presented which allows a practical scaling mechanism. An external memory architecture is developed, allowing the growth of the connection weight and neuron value storage only dependent upon the amount of external memory utilized. Both the GPLM of the co-pending application and the virtual TSNAP of the co-pending application may be inadequate to accomplish the scalability in both capacity and performance. A new neurocomputer architecture is developed maintaining its support of learning and representing a new type of neurocomputer to be referred to as the Scalable Virtual Learning Machine (SVLM). To illustrate the best way of developing this kind of machine, we will present examples of our preferred embodiments. Presented first is the synapse processor architecture mapping onto a virtual TSNAP structure, next the inner square folding and array separation group partitioning algorithm, followed by the description of the new synapse processor architecture and group architecture supporting external memory, hybrid control flow/data flow operation, and notification of local synapse processing completion, with or without errors. An example of back-propagation learning will also be presented demonstrating the utilization of the new architecture.

The virtual TSNAP of Pechanek VIRTUAL 91 includes the weights and neuron values in the synapse processor cells and shares the multipliers and adder trees in a cyclic fashion with the use of an iterative adder. Each iterative add cycle generates a partial sum, stored in the iterative adder (IA), which accumulates the network summation each iterative add cycle.

The register multiplier architecture of the virtual TSNAP can be mapped onto the Synapse Processor Architecture of Pechanek LEARN 91. There are two types of processor "cell" structures used for learning in the synapse processor architecture, the DSYP, diagonal synapse processing "cell" and the GSYP, general synapse processing "cell". The DSYP contains one weight/Y value multiplication element and the GSYP contains two weight/Y value multiplication elements. The connection weight and neuron value storage requirements for a virtual 16 neuron network mapped onto a four physical neuron GPLM is shown in FIG. 1. The DSYPs are outlined with dots and the GSYPs are outlined with dashes. The weights within the DSYPs and GSYPs are grouped into four columns where each column is made up of the connection weights associated with four iterative add cycles. In this example, four iterative add cycles are necessary to produce a neuron output. As depicted, the first set of four iterative add cycles will produce Y1', Y2', Y3', and Y4'. The second set of fout iterative add cycles will produce Y5', Y6', Y7', and Y8'. This continues until all 16 neuron outputs are produced. The merged structure represents the starting point for describing the new SVLM architecture.

A GPLM structure of Pechanek LEARN 91 for eight neurons is shown in FIG. 2 where: ##EQU4##

It can be noticed that there are one square and two smaller triangular arrangements of synapse processor cells within the larger triangular structure of FIG. 2. Separating these out from the main structure and allowing the final stage of the summation tree to be external to the arrangement of synapse processors creates the structure shown in FIG. 3. FIG. 3 contains three structures i.e. the two triangular arrays and one square array. In order to support scalability, a common replicatable design is desired. Since there are two types of structures shown in FIG. 3, a square and two triangular arrangements of synapse processors, scalability via a single design is not achievable. It will now be shown how the square organization can be restructured into two triangular arrays the same size as the other two triangular arrays making up the original 8 neuron model, thereby creating a common replicatable design. In order to accomplish this the square structure is first folded along its diagonal as is shown in FIG. 4 with all synapse processors kept intact and only the summation trees folded. By rearranging the weight and Y value storage within each synapse processor, the folded structure of FIG. 4 can be redrawn as two separate triangular processing arrays as shown in FIG. 5. By following this procedure the large triangular structure of FIG. 2 has been shown to be made up of 4 smaller triangular arrays.

A new notation relating to groups of processors will now be introduced where G represents the number of groups and H represents the number of synapse processor elements within a group G. Each smaller triangular structure represents a group G of size H=16 in this case. FIG. 3 depicts two groups one producing A1, A2, A3, and A4 and the second producing B5, B6, B7, and B8. FIG. 5 depicts the separated triangular array groups one producing B1, B2, B3, and B4 and the other producing A5, A6, A7, and A8. To make the N=8 neuron triangular array, FIG. 2, four groups, G=4, are required. The external summation and sigmoid generation functions, and reverse communication paths, completing the 8 neuron model, are shown in FIG. 6 where the (.fwdarw.) indicates the forward summation path and the (.rarw.) indicates the reverse communications path.

This partitioning concept is next presented for a 16 neuron neurocomputer. The first step is to partition the 16 neuron structure into groups of triangular and square arrays as shown in FIG. 7. For a 16 neuron model using a group size H of 16, there are 4 triangular arrays, labeled 1, 2, 3, and 4 and 6 square arrays, labeled 5, 6, 7, 8, 9, and 10. The square arrays are next folded and separated into the desired triangular arrays. The resulting 16 triangular arrays, in this case, are shown in FIGS. 8 through 15, each marked with a group label referring to FIG. 7. The external summation and sigmoid generation functions, and reverse communications paths, completing the 16 neuron model, are shown in FIG. 16, where (.fwdarw.) indicates the forward summation path and the (.rarw.) indicates the reverse communications path. For ease of representation in FIGS. 8-17 please note:

A=10

B=11

C=12

D=13

E=14

F=15

G=16

In general, as the group partitioning algorithm is applied to larger structures with a given size H, more summation stages are added to the external summation tree. Assuming an implementation where a processor group is placed on a single chip, i.e. H synapse processing elements on a chip, then a scalable neurocomputer design can be built where only the external summation tree needs to be modified as additional group chips are added. This can be seen in the 8 and 16 neuron model examples.

The rearrangement of Y values, which allows the square array to be restructured as two triangular arrays, affects the reverse communications path. The switching path mechanism is shown in more detail in FIG. 17. FIG. 17A presents the switches for the 8 neuron example for Y1 and Y5 while 17B presents the switches for the 16 neuron example for Y1, Y5, Y9, and YD. The same switching mechanism is used for the other neuron outputs in each example. It should be noticed that a path switch in the reverse communications path is implemented by the switching mechanism. For example in FIG. 17A Switch Position For Reverse Communications, Y1 is reverse communicated to the A1 and A5 summation path while Y5 is reverse communicated to B1 and B5. Looking back to FIGS. 3 and 5, triangular structures only, it will be seen that within the DSYPs and GSYPs the received Y values are serialized into the correct register, opposite from the respective summation tree's source point. The same switch in the reverse communications path is followed in the 16 neuron example, FIG. 17B.

The external switching mechanism, FIG. 17, requires further modification for the support of back-propagation learning. There are four different operating modes to be supported by the external processing switching mechanism, two due to the neuron execution, as presented in FIGS. 17A and 17B, and two due to back-propagation learning:

1. External summation of the neuron input summation function.

2. Reverse communication of neuron output Y values.

3. Reverse communication of error signals E.sub.j in learning.

4. External summation of the weighted error summations ER.sub.j in learning.

Operating modes 1 and 4 relate to the forward summation paths, and operating modes 2 and 3 relate to the reverse communications path. The external summation and reverse communication requirements for learning and neuron execution are different. Therefore, different values are externally summed and different values are reverse communicated depending upon whether the hardware is in a neuron execution mode or in a learning mode. In more detail, consider the reverse communication paths for neuron execution as compared to learning. In neuron execution mode, a reverse communicated Y.sub.j must be multiplied with its appropriate W.sub.ij, while in learning, a reverse communicated error signal, E.sub.j, must be multiplied with its appropriate W.sub.ij. This seemingly small change in subscripts of the reverse communicated values, Y.sub.j and E.sub.j, indicates that different reverse communications paths are required for the Y.sub.j value as compared to the E.sub.j value. The different paths are due to the separated triangles of the folded square. The external switch, FIG. 17 of the examples, must be modified to support both different path requirements.

An additional change to the switching function of FIG. 17 is made to accommodate the forward summation requirements. FIG. 18 presents the modified external switching mechanism for the 8 neuron example where the labeled FIGS. 1-4 correspond to the four switch operating modes described above. FIGS. 19 and 20 present the modified external switching mechanism for the 16 neuron example. FIG. 19 corresponds to the switch operating modes 1 and 2 while FIG. 20 corresponds to switch operating modes 3 and 4. It will be noted that not all paths change depending upon the operating mode. Using FIG. 18 as an example, the neuron input forward summation paths (1) for A1 and B5 are the same paths required for the weighted error summations (4) for A1 and B5. In addition, the reverse communication's paths for A1 and B5 are the same in both neuron execution and in learning. It will be noticed from FIG. 3, that A1 and B5 are associated with the diagonal triangular arrays not requiring use of the folding algorithm. The paths which must change depending upon the operating mode are those that are associated with the separated triangular structures from the folded inner squares.

It should be noted that the folded inner square prior to separating, FIG. 4, could be used as a common replicatable building block. By zeroing out the weights and Y values for half of the folded array the folded 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 processors in a processor group, for a given size diagonal triangular array, and there is still a requirement for an external switching function, the folded square building block approach will not be considered further in this description. Neither the 8 nor the 16 neuron example, FIGS. 2 through 17, requires virtual capability as V=N in both cases. The virtual neural processing capability requires, in addition to the storage of more than one weight and Y value per synapse processing element, a method of processing a portion of the neuron input sum of products function. An iterative adder with a Partial Sum (PS) storage element allows the total neural processing to be broken up into multiple cycles, adding a previous partial sum to the newest partial summation generated. An example which adds virtual capability to the processor group concept is described next for the case where V=16, N=4, H=4, and G=4, FIG. 22, which will be used later in this description in the virtual learning example. FIG. 22 includes the modified switching mechanism, an iterative adder with Partial Sum (PS) storage, and the Initialization and Control Learning Processor which interfaces with the Host computer. The HOST computer assumes the responsibilities of initializing the processor groups through the learning processor. For example, the loading of the number of neurons in the network to be emulated, all the connection weights, (the initial neuron values, if required,) "teacher" values in support of a learning algorithm, the number of network update cycles to be run, as well as starting the model into execution are requirements which must be met prior to beginning an emulation cycle. In addition, the learning processor can contain a tracing facility for monitoring a network's execution.

There are G=4 groups where each group contains H=4 processing elements labeled in FIG. 22 as G1, G2, G3, and G4 where:

G1 generates A1 and A2

G2 generates A3 and A4

G3 generates B1 and B2

G4 generates B3 and B4

Since V=16, there are V.sup.2 connection weights to be stored in memory. For this example, FIG. 22, there are four groups of four processing elements each resulting in sixteen total processing elements in the completed system. Therefore, there are required sixteen connection weights in each processing element to support a completely connected network of sixteen neurons.

Let a SO denote a Structure Output cycle and IA denote a partial sum Iterative Add cycle. In general, given V virtual neurons and N physical neurons, assuming, for simplicity, both are powers of 2, and a connection weight and neuron value storage associated with each synapse processing element, a virtual learning structure is formed:

(V/N) Y values to be stored at each synapse processor element (1 element per DSYP and 2 elements per GSYP).

(V.sup.2 /N.sup.2) connection weights to be stored at each synapse processor element.

(V/N) Iterative Add (IA) cycles of N.sup.2 weight * Y value multiplications each per Structure Output (SO) cycle.

(V/N) SO cycles of N neuron values per SO cycle.

For example, FIG. 21 shows a V, N relationship to storage and operating cycles.

In FIG. 22 each connection weight memory of 16 weight values is organized into four SO sets of four values each, labeled S01, S02, S03, and S04, on the connection weight storage blocks. Each set requires four partial sum iterative add cycles to generate one set of neuron N=4, values.

A few other general comments are in order for FIG. 22 regarding the switching mechanism and the iterative adder. The switching mechanism shown is a composite picture of all paths required to support the four switch operating modes of the structure. The iterative adder concept was presented in co-pending application Pechanek VIRTUAL 91 where an additional delay in the summation path was required due to the iterative adder. In the present architecture it will be noted that the iterative adder delay is not necessary as this function is incorporated in the last stage of the summation tree utilizing a 3 to 1 adder, FIG. 22. Additionally, an external input, Ex.sub.j path, as presented in co-pending application Pechanek LEARN 91 is provided prior to the neuron activation function input.

The synapse processing architecture (SPA) provided by Pechanek LEARN 91 had the storage capacity of only a single connection weight per synapse processing element as appropriate for the direct execution of a neural network model. For larger network models, which contain V neurons where V>N, a general method of expanding the weight and neuron value storage is required without greatly impacting performance or requiring a new chip design containing expanded internal storage. For data parallel system processing provided in Pechanek LEARN 91 the same scaling issues apply where matrix elements must be easily accessed from the synapse processor level.

The memory can be thought of as being split among groups of synapse processors where each group has independent read/write and addressing capabilities. This concept is shown in FIG. 23 illustrating a preferred external memory structure.

Assuming an external connection weight memory configuration as shown in FIG. 24, the memory is arranged in G groups where, given N physical neurons and H processor elements within a processor group, G=N.sup.2 /H. For example, assuming N=256 and H=256 then G=256.sup.2 /256=256. If one assumes that a chip contains a single processor group, then a 256 neuron neurocomputer is made up of 256 group chips containing a total of 65,536 synapse processing elements. The external memory word length is made up of two pieces, one associated with the connection weight interface and the other associated with the neuron Y value interface. Both the weight and Y values are in bit-serial format. One weight memory address accesses H weight bits where there is one weight bit per processor elements in the processor group, (1 synapse processor element per Diagonal SYnapse Processor, DSYP, and 2 synapse processor elements per General SYnapse Processor, GSYP, FIG. 25). For simplicity, assume an even power of two criteria for specifying H and N, then the .sqroot. represents the number of Y values utilized within the processor group. The external memory interface then has a composite word length of (H+ECC1+.sqroot.+ECC2) bits, the ECC1 bits correspond to error correction code bits on each group of H bits, and the ECC2 bits correspond to error correction code bits on each .sqroot. bits. Both ECC1 and ECC2 bits are determined using an error detection and error correction coding scheme such as the Hamming single-error correction code illustrated in Hellerman 67 which requires ECC additional bits based on equations 4 and 5: ##EQU5## For example, with H=64, corresponding to 64 synapse processing elements, then ECC1=7 additional bits must be used. The ECC interface will allow the fix up of data detected as in error. The weight array interface is bidirectional, allowing each synapse processor write access to its external weight value storage as is required to support learning. In addition to the weight memory, two other external memory arrays are utilized, one for the present neuron state value (Y) and one for the updated neuron state value (Y'). There are .sqroot. HY values output for each processor group. The present and new Y value arrays may be toggled back and forth every network update cycle. For example, the Present Y Value Array will output Y values for a whole network update cycle while updated Y values are being loaded into the New Y Value Array. For the next network update cycle, the arrays switch meaning where the newly updated Y values (New Y Value Array) are used as the present values in the next network update cycle and the previous Present Y Value Array is overwritten with new Y values. An array selector signal, which selects one array for output and the other array for loading Y values, allows the arrays to toggle back and forth. In another mode of operation, only the present Y value array is used and new Y values overwrite previously stored Y values. The synapse processor internal register length, which corresponds to the bit length of the parameters used, is D bits long which includes within the D bits the Conditional Execution Bit (CEB), FIG. 29. D external memory addresses correspond to H separate values of D bits each, which can be loaded 1 value per processor element in a bit-serial fashion. The external weight memory holds Q*H values or equivalently Q*D memory locations of H+ECC1 bits per memory location. Memory values are accessed for groups of processors and memory values can be read from or written to via group processor controls.

The memory connection to the synapse processor cells is depicted in FIG. 25. A memory connects to a diagonal synapse processor cell, FIG. 25A, with two external memory I/O line going to the distributor. The weight and Y value path from external memory is controlled by a stored PATH address. There is one address for the weight memory with bidirectional I/O lines, i.e. weight values can be either read from or written to memory separately but not simultaneously. There are two addresses for the Y value arrays, one set of addresses for each array and each independently controlled. For the G-cell synapse processors, FIG. 25B, a bidirectional weight bit and an output Y value bit for each synapse processor element are connected to the distributor allowing separate paths to the internal two processor elements in a GSYP. All memory accesses are loaded into the internal processor registers. The updated Y values, Y', are sourced to external memory directly from their entry point to the processor group chip. The Y values coming from the external memory are fanned out on the processor group chip to the synapse processor elements.

The source and destination addresses are relative to the command register. The relative addressing is shown in FIG. 25A and 25B where the top command register CMD TREG relative addresses are shown in columnar fashion located to the right of the register blocks, while the relative addressing for the bottom command register CMD BREG is shown in columnar fashion located to the left of the register blocks. It should be noted, for example, that the bottom command register R2 is the same as the top command register R5. A bit string received from the Add tree, if it is a command, is serialized into one of the two CMD registers in each G-cell and the single CMD register of a diagonal cell. Alternatively, a data bit string received from the Add tree, is serialized to one of the six other registers available in a G-cell and one of the 3 other registers available in a diagonal cell. In the DSYPs a source or destination address of R4 through R6 and CR2 are mapped as follows:

R4.fwdarw.R3

R5.fwdarw.R2

R6.fwdarw.R1

CR2.fwdarw.CR1

An example timing diagram for a 4 neuron SVLM with V=16 neuron capacity for which there are 16/4=4 SO cycles of 4 IA cycles each, is shown in FIG. 26.

Each SO cycle is made up of V/N IA cycles. An IA cycle consists of the weight times Y value multiplication followed by the summation of the V/N multiplied values and storing the partial summation result in the iterative adder. To ensure that good performance, the weight and Y values for the next IA cycle need to have been accessed during the first IA's multiply time. For this to occur, a requirement is placed upon the EXU's multiplier (or any EXU function) such that all operands entering the EXU are not held fixed, external to the EXU, during a function's execution. For the multiplier, this implies that it must contain its own operand register, if required, and for good performance, a result bit is generated one cycle later from when its corresponding operand bits enter the multiplier. To ensure no hazards occur the following relationship, equation 6, for the EXecution Unit (EXU) multiplier function must be met. This is applicable to other EXU functions also, equation 7.

Where:

D bits per read/write access

.delta..sub.extmem is the external memory access delay

.delta..sub.M is the multiplier delay, typically 2*(D-1) clock cycles long

.delta..sub.EXU(fn) the delay of an EXU specified function

All functions of the EXU can be made to execute in the same length of time by padding shorter executing functions. In this fashion the longest executing function determines the criteria for the external memory access timing. For example, assuming the multiplication function is the longest EXU executing function and the multiplication of two 32 bit operands takes 64 clock cycles to accomplish, the maxmimum external memory access delay of a 32 bit operand is 64 clock cycles. By forcing all EXU functions to be of the same delay no stricter requirements are placed on the external memory access delay. FIG. 27 depicts a timing diagram for one SO cycle which generates one set of N neuron values. The numbered items are explained in detail:

1. Begin IA1 cycle with first bit serialized into the EXU multiplier.

2. The first bit of the multiplied result exits the multiplier and enters the summation tree.

3. The first bit of the multiplied result plus a partial sum of 0 exits the 3 to 1 adder and enters the partial sum register.

4. The last bit of the multiplied result exits the multiplier and enters the summation tree.

5. The last bit of the multiplied result plus a partial sum of 0 exits the 3 to 1 adder and enters the partial sum register.

6. The last bit of the second IA cycle's partial sum is stored into the partial sum register.

7. The last bit of the third IA cycle's partial sum is stored into the partial sum register.

8. The last bit of the fourth IA cycle's partial sum enters the sigmoid generator.

9. The first bit of the sigmoid result exits the sigmoid generator and enters the summation tree for the reverse communications back to either external memory or a register in the synapse processor.

10. The last bit of the sigmoid result exits the sigmoid generator and enters the summation tree for reverse communications.

11. The last bit of the sigmoid result is received in either external memory or in a register (first set of N Y values stored).

The time from 1 to 4 represents the time available to load a new Y value or weight value from external memory, as illustrated by FIG. 27, where the time scale is expanded to show detailed timing.

The processor group size depends upon the chip technology cell and I/O specifications. There will be one memory subsystem associated with each synapse processor group chip as depicted in FIG. 28.

There must be two types of commands required to support the processor group concept, one dedicated for group only commands and the other associated with the synapse processors. The command format also must support the external memory as a new source and destination point. Addressing for external memory can be obtained by using the immediate data field of a synapse command. Further, the Conditional Execution Bit, CEB, must be associated with each weight and Y value stored in the external memory.

For example with N=256 neurons, H=256, and D=33 bits the command format L is defined as:

A data word example with N=256 neurons, H=256, and D=33 bits (CEB +32 bits Data) the data format L is defined as:

Since the internal instructions and data are D bits long, FIG. 29, and each must be received in their entirety, the external memory address is formed by appending ceiling (log.sub.2 D) bits to the memory address specified in the instruction field. The ceiling function takes the next largest integer of the function in parenthesis result. For example, 6 bits are appended to the address for a 33 bit data word stored in memory and 5 bits for a 32 bit word. The additional bits are generated automatically from a counter which is incremented each bit-slice access from the memory. After D bits have been accessed per instruction specified memory address, the counter returns to zero in preparation for the next access. In a D=32 bit example, a 15 bit external memory address field in the instruction translates to a 15+5 bit external memory address allowing a 20 bit field or Q*D=2.sup.20 or 1 MEG locations of H+ECC bits each or 2.sup.15 * H (32K*H) weight values. For an H=256 processor group with D=32 bits there are addressable up to 8 MEG connection weights per processor group chip.

The Broadcast bit indicates the following:

B=0: Command/Data is for a specific group.

B=1: Command/Data is for all groups.

There is a single group command register within each processor group chip. An alternative exists for utilization of the group command register for acting as the command source for all synapse processing elements. By utilizing one command register per processor group, the individual processing element command registers could be eliminated by combining the synapse processor commands with the group commands. One group command register would save H command registers, representing a considerable savings in chip real estate. The savings in chip real estate, however, does not come free, as the group command decode must now be distributed to each of the processing elements to control the H-EXUs H-distributors, and H-selectors. In addition to the wiring problem this may cause, there is also a timing penalty due to the potentially large fanout of signals from the centralized source. Consequently, the synapse processing element command registers are left intact and only group oriented commands, typically associated with the external memory control, are implemented. There is a single group tag which is loaded into all H tag registers at initialization time. There are two types of commands specified, both with the Command Bit set to a "1" to differentiate the commands from the data (where the Command Bit is set to a "0"). A Group Bit (G) specifies whether the command is for the synapse processors (G=0) or for the group of synapse processors (G=1). Table 1 lists the presently defined group commands. The SO counter can be set to advance or decrement depending upon the requirements, advancing in neural execution mode and decrementing in back-propagation learning mode, for example. For advancing, the counter begins at 1 and advances to the specified SO COUNT and then wraps around to 1. For decrementing, the counter begins at the SO COUNT and decrements to 1 and then wraps around to the SO COUNT. For sparsely connected networks, the SO count and IA count for each group can be specified by a group command, GLDCT with S=00& I=0, thereby not requiring the SO or IA counters to be clocked, as will be shown in the back-propagation learning example. When specified to count, the IA counter is always advanced at the completion of the instruction execution. The SO counter is advanced or decremented at the completion of all IA count cycles.

For any neural network emulation, the group level commands must be issued to specify the number of IA cycles per SO cycle and the total number of SO cycles required for emulation of V neurons in the network model. In addition, the "S", "I", and "U" bits specify how the processor group accesses the external memory, providing control on the addressing via the "S" and "I" bits and control on how the external Y value arrays are utilized via the "U" bit. With the "S" bits set to a "00", the external memory address will not advance beyond the presently defined SO cycle, though the memory address will advance for each IA cycle, if "I"=1, allowing full execution of the IA cycles for the presently defined SO cycle. With "S" set to a "01" the SO count will advance after the next instruction is executed, which requires the specified number of IA cycles to be completed. Advancing the SO and IA counters allows execution to proceed through the V neurons where V.ltoreq.N. Holding the SO count fixed allows repeated execution of the N neuron values being executed, a facility used when multiple layers of a multilayer neural network are mapped onto a single SO cycle set of N neurons. With the "U" bit set to a "0", only one Y value array is utilized, for example the Present Y Value Array which causes newly updated Y values to overwrite the old Y values stored in the array. With the "U" bit set to a "1", both Y value arrays are used such that new Y values are only written to the opposite array which is being used for the present network emulation, and the arrays toggle their meaning after V neurons have been updated. A Y value can be read from external memory while a Y value is being written to the external memory. If "U"="0", this simultaneous operation must occur from the same external memory array, requiring an array two port operation.

Since the group command is common to all synapse processors on a chip, only one input path is necessary to communicate to the group. To accomplish this, one of the processor summation tree paths is designated as unique in that it also serves as the group communications path. Once specified, this path is uniquely identified and used for group communications from the initialization and control learning processor.

With the Command Bit set to a "1" and the Group Bit set to a "0", the command received is specified for the synapse processors. Table 2 lists the synapse processor's instruction set which supports external memory . An external memory address may be specified in the immediate data field of an instruction or may be specified to use the present SO and IA count values for the address i.e. for local address control of the external memory. The source or destination code specifies which addressing mode to use. SYNAPSE PROCESSOR INSTRUCTION SET CMND *AUTO* SOURCE 1 SOURCE 2 DESTINATION IMMED. DATA COMMENTS NOP N.U. N.U. N.U. N.U. N.U. NO OPERATION PATH N.U. ADD TREE NOT USED R1, R2, R3, R4, IF DESTINATION IS CR1 OR CR2 SET THE COMMAND PATH BIT = 0 (N.U.) R5, R6, C FOR PATH TO CR1 AND = 1 FOR PATH TO CR2. CR1, CR2 E IF DESTINATION IS R1, R2, . . . , R6 THEN SET THE DATA PATH EXT. MEM. 1, 2 B EXT.MEM. REGISTER TO THE DESTINATION ADDRESS AND THE DESTINATION ADDRESS REGISTER'S CEB AS SPECIFIED. PATH N.U. EXT. MEM. DESTINATION 1 DESTINATION 2 IF DESTINATION IS CR1 OR CR2 SET THE COMMAND PATH -- (WEIGHT PATH) -- (Y PATH) -- C BIT = 0 FOR PATH TO CR1 AND = 1 FOR PATH TO CR2. R1, R2, R3, R4, R1, R2, R3, R4, E IF DESTINATION IS R1, R2, . . . , R6 THEN SET THE R5, R6 R5, R6, B DATA PATH REGISTER TO THE DESTINATION ADDRESS CR1, CR2 CR1, CR2 AND THE DESTINATION REGISTER'S CEB AS SPECIFIED. MPY 0 = NO R1, R2, R3, R4, R5, R1, R2, R3, R4, R1, R2, R3, R4, DATA OR 1 = AUTO R6, IMD1, IMD2 R5, R6, IMD1, R5, R6, ADD TREE, EXT. MEM. IMD2 EXT. MEM. 1, 2 ADDRESS ADD 0 = NO R1, R2, R3, R4, R5, R1, R2, R3, R4, R1, R2, R3, R4, DATA OR 1 = AUTO R6, IMD1, IMD2 R5, R6, IMD1, R5, R6, ADD TREE, EXT. MEM. IMD2 EXT. MEM. 1, 2 ADDRESS AND 0 = NO R1, R2, R3, R4, R5, R1, R2, R3, R4, R1, R2, R3, R4, DATA CEB VECTOR = (CEB1, CEB2, . . . , CEB6) 1 = AUTO R6, IMD1, IMD2, R5, R6, IMD1 R5, R6, ADD TREE, OR WHERE CEBx = DEB BIT FOR REGISTER Rx CEB VECTOR IMD2, EXT. MEM. 1, 2, EXT. MEM. CMP FLAGS CEB VECTOR ADDRESS OR 0 = NO R1, R2, R3, R4, R5, R1, R2, R3, R4, R1, R2, R3, R4, DATA CEB VECTOR = (CEB1, CEB2, . . . , CEB6) 1 = AUTO R6, IMD1, IMD2, R5, R6, IMD1, R5, R6, ADD TREE, OR WHERE CEBx = CEB BIT FOR REGISTER Rx CEB VECTOR IMD2, EXT. MEM. 1, 2, EXT. MEM. CMP FLAGS CEB VECTOR ADDRESS INV 0 = NO R1, R2, R3, R4, R5, N.U. R1, R2, R3, R4, DATA CEB VECTOR = (CEB1, CEB2, . . . , CEB6) 1 = AUTO R6, IMD1, IMD2, R5, R6, ADD TREE, OR WHERE CEBx = CEB BIT FOR REGISTER Rx CMP FLAGS, EXT. MEM. 1, 2, EXT. MEM. CEB VECTOR CEB VECTOR ADDRESS EXOR 0 = NO R1, R2, R3, R4, R5, R1, R2, R3, R4, R1, R2, R3, R4, DATA CEB VECTOR = (CEB1, CEB2, . . . , CEB6) 1 = AUTO R6, IMD1, IMD2, R5, R6, IMD1, R5, R6, ADD TREE, OR WHERE CEBx = CEB BIT FOR REGISTER Rx CEB VECTOR IMD2, EXT. MEM. 1, 2, EXT. MEM. CMP FLAGS CEB VECTOR ADDRESS CMPR 0 = NO R1, R2, R3, R4, R1, R2, R3, R4, TRF, BRF, EF DATA TRF = TOP REG. > BOT REG. or IMD1 or IMD2 1 = AUTO R5, R6, IMD1, R5, R6, IMD1, FLAGS BRF = BOT REG. > TOP REG. or IMD1 or IMD2 IMD2 IMD2 EF = TOP REG. = BOT REG. or IMD1 or IMD2 MIN 0 = NO R1, R2, R3, R4, R1, R2, R3, R4, R1, R2, R3, R4, DATA OR MIN(SOURCE1, SOURCE2) = DESTINATION 1 = AUTO R5, R6, IMD1, R5, R6, IMD1, R5, R6, ADD TREE, EXT. MEM. IMD2 IMD2 EXT. MEM. 1, 2 ADDRESS MAX 0 = NO R1, R2, R3, R4, R1, R2, R3, R4, R1, R2, R3, R4, DATA OR MAX(SOURCE1, SOURCE2) = DESTINATION 1 = AUTO R5, R6, IMD1, R5, R6, IMD1, R5, R6, ADD TREE, EXT. MEM. IMD2 IMD2 EXT. MEM. 1, 2 ADDRESS READM N.U. EXT. MEM. 1, 2 N.U. R1, R2, R3, R4, EXT. MEM. R5, R6, ADD TREE ADDRESS WRITEM N.U. R1, R2, R3, R4, N.U. EXT. MEM. 1, 2 EXT. MEM. R5, R6, IMD ADDRESS *AUTO* = 1 .fwdarw. AUTOMATIC REPEAT OF FUNCTION AFTER RECEIPT OF UPDATED DATA FROM SOURCE EXTERNAL TO SYNAPSE PROCESSOR *IMD1, IMD2* = IMMEDIATE DATA IN COMMAND REGISTERS 1 OR 2, AS SPECIFIED *EXT. MEM. 1 = USE EXT. MEM. ADDRESS IN IMMED. DATA FIELD *EXT. MEM. 2 = USE PRESENT SO AND IA COUNT VALUES AS ADDRESS, i.e. LOCAL ADDRESSING

The definition of the Automatic bit depends upon the setting of the S bits which are loaded by a group command. The definition is as follows:

A=0, S=00: Single SO cycle update; with "I"=1 all IAs at present SO cycle are executed and then wait for next instruction. The SO count is not advanced.

A=0, S=01 or 10: Execute present SO cycle and advance or decrement the SO count and then wait for a new command. With "I"=1 all IAs at present SO cycle are executed.

A=1, S=00: Execute present SO cycle then wait for new data. Upon receipt of valid tagged data execute the same SO cycle and wait for new data. This procedure is repeated upon every receipt of valid tagged data, continuing until a new command is received which stops it.

A=1, S=01 or 10: Execute present SO cycle and advance or decrement the SO count and then wait for new data. Upon receipt of valid tagged data, execute a SO cycle and advance or decrement the SO count and then wait for new data. This procedure is repeated upon every receipt of valid tagged data, continuing until a new command is received which stops it.

The automatic bit essentially specifies when an execution cycle begins; For A=0 the execution cycle begins only on receipt of an instruction and for A=1 the execution cycles begin, after the first execution of the automatic instruction, bn every receipt of valid tagged data.

Before continuing with the synapse processor instruction set discussion, a brief description of the utilization of the "A", "S", "I", and "U" bits will be reviewed in their application to two "classic" types of neural networks. Beginning with the Hopfield network, the automatic bit will be set to a "1", the "S" bits set to a "01", the "1" and the "U" bits each set to a "1". Each set of N Y values will be written each SO cycle into the Y array opposite to the one being used for the present V neuron network emulation. This is accomplished by overlapping the write operation with the fetch of a set of present Y values by utilizing separate address and control lines for each Y value array. After the receipt of the last set of N values making up the V neuron emulation, the selection of the Y array will toggle such that the recently updated Y values will be treated as the present Y values for the next network update cycle. This process will continue until a new command is received which stops the operation, such as a NOP instruction. In a multilayer network emulation, the Automatic bit will probably be set to a "1", the "S" and "I" bits will be set dependent upon the network execution sequence, and the "U" bit will be set to a "0". If multiple layers are mapped onto one set of N neurons in SVLM, the "S" bits will be set to a "00" for the execution of a subset of those layers. For example with 3 layers mapped onto one set of N neurons, "S" will be kept set at a "00" for the execution of the first 2 layers. Then a Group Command would he issued, changing "S" to a "01" so that the network emulation can continue with advancing the SO count after the execution of the next layer (i.e. the third layer of the three mapped onto one SO cycle set of N neurons). Since "U" is set to "0", the new Y data overwrites the Y data in the present Y value array such that each layer's execution will utilize the previous layers calculated Y value data, which is the normal operation in a feedforward multilayer neural network. In order to specify the "U", "I", and "A" bits, capitals "U", "I", and "A" will be appended to an instruction mnemonic to indicate whether the specified bits are set to a "1". If "U", "I", or "A" are not appended to an instruction, the bits are set to a "0". The "S" bits value is specified as either "1" or "2" as no specification indicates the "S" bits are "00" and "11" is not presently defined.

The synapse processor instruction set contains an external memory address field (immediate data field) which, through the use of the PATH (EXT.MEM.) command, allows external memory to be specified as a data source. The utilization of the PATH command with external memory will be described first, followed by the description of the common method the other instructions used in writing to external memory.

The PATH command sets up the data and cmd (command) path within a synapse processor, for information either reverse communicated up the Adder tree or accessed from external memory, by loading the Add tree destination path in one path register and the EXT. MEM. register destination path in another separate register, FIG. 25. The PATH command's Source 1 field determines which register is to be used and can be viewed as a command field extension further defining the PATH command. The PATH command specifies only the destination point for data received from the Add tree or from EXT. MEM.. Because of this, a PATH command specifying data received from EXT.MEM. with a destination of EXT.MEM. would not accomplish anything, as the same data would be received and sent to the same location without any processing, i.e. a NOP action. The path once specified remains the same unless a new PATH command is received which changes the path. For example, in a Hopfield network model on SVLM, if the default paths had been changed due to previous processing, the PATH commands for the reverse communicated Y values and the virtual weights would be issued once allowing, in reverse communication mode within a GSYP synapse processing cell, the top Adder tree to connect its Y value to the bottom Y value register and the bottom Adder tree to connect its Y value to the top Y value register. For the Hopfield model, this path command remains in effect through out the network execution, assuming a fixed weight mode of execution. The PATH command also allows the specification of the path for the next commands. In a virtual mode example of the Hopfield network, the fetch of the weight values from the external memory will be done during the previously fetched weight multiplication time.

In data flow computing, an instruction execution waits until all operands have been received, at which point the instruction is "fired". The data dependent controlling mechanism can be viewed as using tagged data such that when the valid data operands are received with matching tags the instruction is executed. Given the operands may not be received at the same time, this data dependent mechanism offers great performance potential and resolution of synchronization problems. The automatic mode is a data dependent operation in that the next execution of the instruction will not occur until valid data with a matching tag are received. Reverse communicated Y values, for example, sent back to a processor group will contain a common group tag. The receiving processor group will compare each Y value's tag in the synapse processing elements with the group tag and if they match the auto instruction will be executed. For the present architectural example, all .sqroot.H tags to a processor group chip must have the same group tag or a groud error will occur. In a similar manner, data from external memory can be tagged. The tagging control may not be done in the same manner as the reverse communicated data from an external source since each processor group chip interfaces to its own set of external memory arrays. For example, using a tag does not imply that a tag is associated with each weight and Y value in memory since the tag is the same for all stored values. Rather, a tag source may be set up in external memory which is multiplexed onto the data lines at the appropriate times. Alternatively, a different type of tag can be used on the external memory interface to minimize the interfacing impact. Since the memory and group chip are tightly coupled, a smaller tag field can be used than that required from the reverse communications tree path, as identification between different group chips is not required. Equations 6 and 7 must be revisited depending upon the implementation decision.

Many instructions specify a destination which is local to the individual synapse processor. This local processing can cause synchronization problems if not handled correctly. In the GPLM of co-pending Pechanek LEARN 91, the synchronization problem was localized to the learning processor at the neuron output point. No notification of local processing completion was generated from the synapse processors. Rather a fixed hardware mechanism was provided at the neuron output point to guarantee safety of the operations. Any local processing command to the same synapse processor was to be separated from the next command to that same synapse processor by the specified instruction's execution time. For example, a multiply could take 2*(D-1) clocks to ensure the completion of a MPY command before the second command can be sent. For SVLM this time out method is not sufficient to resolve the synchronization problem. A new method is used where all local instructions notify completion of execution to the issuing point. The method uses the summation tree as the communications channel. Consider a local operation done at each synapse processing element where the result is stored back into a local synapse register. At the successful completion of the local operation, assume each synapse processing element entered a value of "1" to the summation tree. Then, after a delay of log.sub.2 N cycles, a summed value of N would result, indicating normal completion of all N local operations associated with a particular summation tree. Any other value would indicate an error had occurred in the operation sequence. By allowing each processor group chip to append an error value different than the other group chips, isolation to a failing chip becomes feasible. In a similar manner, different summed values could indicate different types of errors detected. This communications of local operation completion incurs a small time penalty as compared to the time out approach in that the next instruction to a processor group cannot be sent until notification of completion has been received. The time to communicate instruction completion is small, being a log.sub.2 N delay addition to the local execution time. Non-local instructions, i.e. those instructions where the destination is the ADD TREE, provide notification of operation completion when the converged tree result reaches the learning processor. The learning processor must only distinguish between local and non-local instructions for instruction issuing synchronization control, and no variable time out control is required.

As a final note, a SVLM compiler would be required to ensure no destination conflicts occur in programs using the described instruction set.

An input/output encoder problem will be used to demonstrate how back-propagation is employed on the SVLM structure. Table 3 presents the input to output pattern encoding problem recognized by Rumelhart 86.

The network structure used for this problem is shown in FIG. 30, which illustrates an example neural network for the input/output encoding problem.

Multi-layer networks are mapped onto a completely connected network structure where unused connection paths are kept at a zero weight value by the weight registers' Conditional Execution Bit being set to zero. For the virtual machine, the size of the largest layer of neurons dictates the minimum size of N the number of physical neurons in the SVLM structure. There are 11 neurons in the I/O encoder problem but the largest layer has only 4 neurons which is the criteria for determining the number of physical neurons. A 4 neuron SVLM structure will be used in the input/output encoding problem. For example, the one already depicted in FIG. 22 is made up of four groups, G=4, each of size H=4 capable of emulating a 16 neuron network.

The input/output encoder problem does not require all possible connections available in the 11-neuron SVLM structure. For example, the input/output encoder network equation for neuron 9 is:

FIG. 31 shows the general 11 neuron SVLM with each synapse processing external memory Weight and Y values shown for a completely connected 11 neuron structure. There are 121 weights in a completely connected 11 neuron network all of which are presented in FIG. 31. Note that the neuron mapping is different than that presented in FIG. 22 to allow the processing of the largest layer of N neurons to be accomplished in one update cycle of N neurons. Further note that layers 1 and 2, neuron outputs Y1, Y2, and Y3, are mapped to the S01 cycle of N neurons.

During execution mode the Y values are calculated layer by layer, layer 1 first whose Y value results are used for layer 2, and continuing through the layers. After all K layers of neurons have been processed, the network is placed into a learning mode. The output neurons calculate the error signals from the output layer and then reverse communicate the error signal values through the tree to the synapse processing cells. The back-propagation of error signals is done layer by layer beginning at the output layer and continuing to the input layer. The error signals are used in the weight updating algorithm. By executing the proper instructions in the various synapse processors, the back-propagation algorithm can be executed.

A detailed example with ordered procedures will explain how the input/output encoder learning problem is implemented with a back-propagation algorithm when mapped onto the SVLM.

For some pattern p (in general the superscript p is removed for clarity) the following itemized procedure is followed in the SVLM neurocomputer: (The "no-connection" weights are blanked out for clarity. The positions of the registers, as viewed relative to the command register, within each synapse processing element are shown in FIG. 31.)

1. SVLM is initialized by reading in the initial set of weight and Y values from external memory with the CEB bits set to a "0" for those connections not to be used in the model, FIG. 32. Only 22 out of 121 possible connection weights for a completely connected 11 neuron model are utilized in the I/O encoder example. Three SO cycles of three IA cycles each are executed to obtain the 11 neuron outputs. The fourth SO and IA cycle are not needed in this example as there are no neuron 13, 14, 15, or 16 in the I/O encoder problem. A Group command is issued to load the IA and SO counts and set the "S", "I", and "U" control bits. GLDCT 0,1,1 sets "S", "I", and "U" to "0"s and loads SO=1 and IA=1.

2. After initialization, SVLM is placed into execution mode and an input pattern applied, EX1 and EX2. The default path is assumed for the General Synapse Processors. Specifically, commands received from the top ADD tree go to CR2, the bottom command register, and commands received from the bottom ADD tree go to CR2, the top command register. Data received from the top ADD tree goes to R5 the Y.sub.j register and data received from the bottom ADD tree goes to R5 the Y.sub.j register. (Relative addressing is assumed.)

3. The four physical neurons issue MPYA R1*R2.fwdarw.ADD TREE (T). The automatic mode is used to improve performance by not having to reissue the multiply instruction for each layer of the network execution. Since layers 1 and 2 are mapped onto the S01 cycle of N neurons "S"="00" keeping the SO counter from advancing the SO count. In addition, with the "U" bit set to a "0" the newly updated Y values will be utilized in the next neuron updates. Since the Y value registers in the SVLM structure are initially zero, all weight times Y values will produce a zero product which when summed produce a zero summation value.

4. The first layer of neurons is executed on the SVLM structure, creating the first layer neuron outputs and their derivatives, FIG. 33. (The learning processor ignores the other two neuron output values.)

Y.sub.1 =F(Ex.sub.1)

Y.sub.2 =F(Ex.sub.2)

Dr.sub.1 =Y(1-Y.sub.1)

Dr.sub.2 =Y.sub.2 (1-Y.sub.2)

5. To emulate the 2nd layer of the network model and then continue with layers 3 and 4 the SO count must be advanced after the execution of the 2nd layer. To accomplish this a new Group instruction is issued changing the state of "S" to a "01", GLDCT 1,3,1. the "I" and "U" bits are not specified so they both remain set to a "0". After the GLDCT 1,3,1 instruction is sent, the first layer neuron outputs are fed back into SVLM, FIG. 34. Since the automatic MPY instruction was specified, the second layer of neurons is executed upon receipt of Y1 and Y2, creating the second layer of neuron outputs and their derivatives, FIG. 35. After the 2nd layer is executed the SO count is advanced to 2.

Reverse communicate Y.sub.1 and Y.sub.2.

Y.sub.3 =F(W.sub.3,1 Y.sub.1 +W.sub.3,2 Y.sub.2)

Dr.sub.3 =Y.sub.3 (1-Y.sub.3)

6. This continues until all layers have been executed and the network output and their derivatives are obtained, FIGS. 36, 37, 38, and 39. Upon receipt of Y.sub.3 ' the second SO cycle is initiated which generates the third layer outputs, namely Y.sub.4, Y.sub.5, Y.sub.6, Y.sub.7 and then the SO count is advanced to 3. The third layer Y values are reverse communicated and the third SO cycle is initiated which generates the fourth layer outputs and advances the SO count to 1 as the network emulation is completed.

Third layer execution begins with the SO count equal to 2.

Reverse communicate Y.sub.3, FIG. 36.

Third layer execution, FIG. 37.

-Y.sub.4 =F(W.sub.4,3 Y.sub.3)

-Y.sub.5 =F(W.sub.5,3 Y.sub.3)

-Y.sub.6 =F(W.sub.6,3 Y.sub.3)

-Y.sub.7 =F(W.sub.7,3 Y.sub.3)

-Dr.sub.4 =Y.sub.4 (1-Y.sub.4)

-Dr.sub.5 =Y.sub.5 (1-Y.sub.5)

-Dr.sub.6 =Y.sub.6 (1-Y.sub.6)

-Dr.sub.7 =Y.sub.7 (1-Y.sub.7)

-Advance SO count to 3.

Issue GLDCT 1,3,2 to load the IA COUNT with a 2 so that the proper weights can be accessed from external memory. The "S" bits "01" and the SO COUNT =3 remain the same.

Fourth layer execution begins with the SO count equal to 3.

Reverse communicate Y.sub.4, Y.sub.5, Y.sub.6, and Y.sub.7, FIG. 38.

Fourth layer execution, FIG. 39.

-Y.sub.8 =F(W.sub.8,4 Y.sub.4 +W.sub.8,5 Y.sub.5 +W.sub.8,6 Y.sub.6 +W.sub.8,7 Y.sub.7)

-Y.sub.9 =F(W.sub.9,4 Y.sub.4 +W.sub.9,5 Y.sub.5 +W.sub.9,6 Y.sub.6 +W.sub.9,7 Y.sub.7)

-Y.sub.10 =F(W.sub.10,4 Y.sub.4 +W.sub.10,5 Y.sub.5 +W.sub.10,6 Y.sub.6 +W.sub.10,7 Y.sub.7)

-Y.sub.11 =F(W.sub.11,4 Y.sub.4 +W.sub.11,5 Y.sub.5 +W.sub.11,6 Y.sub.6 +W.sub.11,7 Y.sub.7)

-Dr.sub.8 =Y.sub.8 (1-Y.sub.8)

-Dr.sub.9 =Y.sub.9 (1-Y.sub.9)

-Dr.sub.10 =Y.sub.10 (1-Y.sub.10)

-Dr.sub.11 =Y.sub.11 (1-Y.sub.11)

-Advance SO count to 1.

7. After all 11 neuron values and their derivatives have been calculated and placed into a Y value and Y derivative array, SVLM is placed into the learning mode. For sparsely connected networks, as in this example, the IA and SO counts are used in a no clocking manner and changed explicitly by a group command instruction whenever a new IA or SO count is desired.

8. The learning processor checks the Y.sub.j s for convergence to the minimum specified error. If reached, the learning process can be stopped for pattern p. If the convergence has not been reached, the learning for pattern p continues.

ConvergenceTestY.sub.8 =.vertline.(t.sub.8 -Y.sub.8).vertline..ltoreq.Minimum Error

ConvergenceTestY.sub.9 =.vertline.(t.sub.9 -Y.sub.9).vertline..ltoreq.Minimum Error

ConvergenceTestY.sub.10 =.vertline.(t.sub.10 -Y.sub.10).vertline..ltoreq.Minimum Error

ConvergenceTestY.sub.11 =.vertline.(t.sub.11 -Y.sub.11).vertline..ltoreq.Minimum Error

9. The learning processor calculates the .delta..sub.j .sup.p for the output neurons for use in updating the weights between the output neurons and the neurons in the previous layer.

10. Load the SO and IA counts with no clocking mode specified. The data path is changed, and the error signals are then reverse communicated to their respective synapse processor elements' temporary registers, FIG. 40.

GLDCT 0,3,2 loads SO=3 and IA=2 which points to where all the weights are located in external memory and ensures both the SO and IA counters are not clocked, i.e. S=00 and I=0.

The four physical neurons change the data path by issuing PATH R4. The issuance of PATH R4 stops the automatic multiply mode specified by MPYA issued in step 3 above. The next data being received goes to the relative address R4 temporary register in the GSYPs and R3 in the DSYPs. The command path remains unchanged.

E8, E9, E10, and Ell are reverse communicated from the Y.sub.8, Y.sub.9, Y.sub.10, and Y.sub.11 source points.

11. Issue MPY instruction to start the multiply of the error signals times the appropriate weights, FIG. 41. The products are summed, creating the error summations, ER.sub.j.sup.p, to be used in the next layer back weight modification process, FIG. 42. Since the command path was not changed, i.e. top ADD tree command to bottom command register (CR2) and bottom ADD tree command to top command register (CR2), the error signals are residing in R3 the temporary register address relative to the received commands. ##EQU6## Where m=M.sub.1 +M.sub.2 +. . . M.sub.L Neurons 8, 9, 10, and 11 issue MPY R6*R3.fwdarw.ADD TREE (T), FIG. 41.

Create weighted error summations: ER.sub.4, ER.sub.5, ER.sub.6, ER.sub.7, FIG. 42.

12. The weights between layers 3 and 4 are now modified by the learning rule. .DELTA.W.sub.ij is created by .rho.Y.sub.j Ei in two instruction steps.

a. STEP 1 - MPY R5*R3.fwdarw.R4, FIG. 43

TEMPREG.sub.8,4 =Y.sub.4 E8

TEMPREG.sub.8,5 =Y.sub.5 E8

TEMPREG.sub.8,6 =Y.sub.6 E8

TEMPREG.sub.8,7 =Y.sub.7 E8

TEMPREG.sub.9,4 =Y.sub.4 E9

Continuing until:

TEMPREG.sub.11,7 =Y.sub.7 E11

b. STEP 2 - MPY R4*IMD.fwdarw.R4, FIG. 44.

.DELTA.W.sub.8,4 =.rho.TEMPREG.sub.8,4

.DELTA.W.sub.8,5 =.rho.TEMPREG.sub.8,5

.DELTA.W.sub.8,6 =.rho.TEMPREG.sub.8,6

.DELTA.W.sub.8,7 =.rho.TEMPREG.sub.8,7

.DELTA.W.sub.9,4 =.rho.TEMPREG.sub.9,4

Continuing until:

.DELTA.W.sub.11,7 =.rho.TEMPREG.sub.11,7

13. One more step creates the new weights values between layers 3 and 4. New W.sub.ij =W'.sub.ij =Old W.sub.ij +.DELTA.W.sub.ij. The new weights are stored in external memory. ADD R6+R4.fwdarw.EXT.MEM.2 use the present SO and IA counts as the address to external memory, FIG. 45.

Continuing until:

W.sub.11,7 =W.sub.11,7 +.DELTA.W.sub.11,7

14. By following this procedure, the weights can be updated for the other layers in the network. For layer 3, SO=2 and IA=1, error signals E4, E5, E6, and E7 can be created from the general equation E.sub.j =Dr.sub.j ER.sub.j in the learning processor and then the error signals can be reverse communicated in the structure. The error signal ER.sub.3 can then be created followed by the weight updating sequence for weights W.sub.4,3, W.sub.5,3, W.sub.6,3, W.sub.7,3. This continues until all weights are updated.

15. A new path command is sent in preparation for the next learning cycle, PATH R2 so that the new Y values are sent to the proper registers.

16. SVLM is placed in execution mode and the existing pattern p is applied again until the adjusted weights allow the output pattern to match the teaching pattern with a minimum specified error. Until the minimum specified error is reached SVLM will alternate between execution mode and learning mode. After convergence to the minimum specific error is reached, a new pattern can be applied and the process repeated until all teaching patterns have been applied.

A group partitioning algorithm has been presented which creates a common building block of synapse processors containing their own external memory. The processor groups are used to create a general purpose virtual learning machine which maintains complete connectivity with high performance. The synapse processor group allows a system to be scalable in virtual size and have direct execution capabilities. Internal to the processor group, the synapse processors are designed as a hybrid control flow/data flow architecture with external memory access and reduced synchronization problems.

While we have described our preferred embodiments of our inventions it will be understood that those skilled in the art, both now and in the future, upon the understanding of these discussions will make various improvements and enhancements thereto which fall within the scope of the claims which follow. These claims should be construed to maintain the proper protection for the inventions first disclosed.