Parallel processing data network of master and slave transputers controlled by a serial control network

Description Submit all comments and votes

TECHNICAL FIELD OF THE INVENTION

The present invention relates in general to parallel processing systems and in particular to the communication of commands and high density data transfer among the dynamically configurable topologies of the processing nodes of such systems.

BACKGROUND OF THE INVENTION

Large scientific data processing applications can often be partitioned such that they may be carried out by several concurrently operating (parallel) processors, each of which handles a different portion of the problem so as to reduce the total processing time required. In a concurrent parallel processing system, for a given topology, any node processor can be attributed the task of "master processor" for a given time or application. The master processor controls the distribution of tasks among the slave processors and monitors and directs their progress. The slave processors often share large volumes of data among themselves as required by the particular tasks assigned to each.

The master processor typically provides the primary user interface to the parallel processing system and as such may require rapid access to a large volume of data. These system level functional requirements in turn place the following requirements on the communication network serving the parallel processing system: (1) flexibility to support dynamic re-configuration and asynchronous communication; (2) wideband communication to support rapid transmission of high density data; and (3) real time communication of system commands and system status with reduced software transmission overhead. These requirements are independent of the parallel processing system configuration used (i.e,, fixed, dynamic, tree, mesh, cubic, hypercubic) but do become increasingly critical as the system's configuration increases in complexity. Increased communication efficiency with respect to time has been a focus of the prior art.

Prior art solutions have taken a variety of approaches to improving data communication speed in the demanding parallel processing environment. The solutions have called for trade offs between speed, flexibility, the maximum number of nodes permitted, and cost. For example, Cowley U.S. Pat. No. 4,876,641 discloses a parallel processing network with a plurality of processors located on a plurality of chips in multiple rows and columns. The processors are interconnected with a first switching of logic means (multiplexer) on each chip which interconnects the processors in parallel data paths. The processor is also interconnected with a second switching logic means (multiplexer) external to the chips which connect selective rows and columns between chips in serial data paths.

The Cowley patent system involves communications between parallel processing elements in both parallel and serial data paths. The processing elements are envisioned as simple shift registers with the multiplexer switching between serial and parallel data paths; this is considerably different from the parallel transfer controller envisioned by the present invention. There is no apparent distinction made between the types of information flowing over serial and parallel paths. There is apparently no discussion of transmitting command messages over the serial links and data information over the parallel links.

Call U.S. Pat. No. 4,891,751 patent discloses a massively parallel processing system which includes a transputer interfacing with a processing node to other processing nodes. A separate peripheral processing network of peripheral processing nodes are also interconnected to transfer data back and forth. One network may interface with the other or may bypass the other network as desired. However, data is transferred by serial link transfers between nodes rather than on fast parallel channels.

Kneib U.S. Pat. No. 4,641,238 shows a network of parallel processing nodes communicating with each other over a serial bus. The nodes also communicate over a serial bus to a central global memory which feeds to a master processor. An arbiter controls which of the nodes is to be utilized in various computations required by the master processor. Kneib shows serial interconnection between the nodes. However they communicate by parallel only indirectly through the global memory under the control of master processor and arbiter. The local nodes do not determine the transmission of data over the parallel bus. Moreover, there is no distinction between transferring control commands on the serial bus and data on the parallel bus as in the present invention.

Therefore a need exists for an efficient communication solution to support a parallel processing network having a plurality of processing nodes. The present invention meets this need through an optimized transfer of data between processing nodes over a fast parallel channel in response to control commands being sent between processing nodes over serial links. The approach of the present invention facilitates efficient reconfiguration of parallel system topology, re-distribution of tasks among the nodes, and maintains maximum data transfer rates.

SUMMARY OF THE INVENTION

The present invention is a real-time high density data communication system designed to operate efficiently in a dynamically configurable, multi-processor parallel processing environment. In a concurrent parallel processing system, for any one given topology, any one processor node can be attributed the task of "master processor" for a given time or application. The invention utilizes a serial communication network to disseminate commands from the master processor to the slave processors, to effect communication protocol to control transmission of high density data among nodes, and to monitor the status of each slave processor. In a concurrent parallel processing system, for a given topology, any node processor can be attributed the task of "master processor" for a given time or application. The invention utilizes a parallel channel communication network in conjunction with two triple port memories at each processor node (master or slaves) in the system to efficiently transmit high density data for sustained or burst intervals without having to interleave communication control messages. The reduced processing and cost overhead of this invention is an improvement over general purpose communication schemes such as Scalable Coherent Interface (SCI) and High Performance Parallel Interface (HIPPI) which may also be used to provide a communication for parallel processing systems.

Each processor node preferably includes a transputer for the purpose of accomplishing the parallel processing task assigned to it within the parallel processing system and initializing and controlling all devices associated with that node. Each processor node preferably includes a digital signal processor for the purpose of compacting, filtering the data and implementing other mathematical algorithms. Each processor node also preferably includes a parallel transfer controller for the purpose of preparing its host node to send or receive parallel data in response to control commands received or sent over the serial communication link by the host transputer from or to other nodes.

In conjunction with the parallel transfer controller and the communication data switch, the transputer directs the flow of data traffic within the node and to or from the rest of the system. Each processor node also preferably includes two triple port memories, memory x and memory y, for the purpose of storing large volumes of data for transmission and supporting read/write access by the transputer, digital signal processor, and parallel transfer controller.

The transputer determines how memory X and memory Y should be allocated to meet the memory requirements of the node. Upon the transputer's command, the parallel transfer controller allocates memory X and memory Y resources such that they may be accessed by the transputer or digital signal processor (DSP) as required by the transaction or may send or receive data to or from the fast parallel hardware channel. The parallel transfer controller also monitors (counts number of words and keeps track of starting and ending addresses) traffic over the parallel data bus connecting the node to the fast parallel transfer channel.

The system of the present invention fulfills the requirements mentioned earlier for a parallel processing system of flexibility, wide band communication and real time transmission of the system commands and status. A particular characteristic of the invention is the very low software overhead time for starting and ending the transfer of data. This characteristic of the present invention is in contrast with a SCI (scalable coherent interface) system which is more suitable for connecting processing nodes for general purpose applications and which has the disadvantage of a high software protocol overhead time (25% of each transmission is devoted to communication protocol).

The system of the present invention is extremely fast because the parallel bus segments between the processors do not need any control lines (only clock and data lines are used) and need not have arbitration, since this functionality is provided by the processors communicating over the serial links. Moreover, because the serial and parallel communication networks are each-dedicated to the transmission of control information and data respectively, the software processing of transmitted data is further reduced. The system is structured around the concept of dedicated purpose networks and as a result there is less processing time required to parse and interpret each transmission.

If desired, a parallel processing system utilizing the approach of the present invention could interface with a SCI or a HIPPI network through the assignment of a processing node in the parallel processing system to provide that interface. Exchange of communication control commands among nodes over the serial link network is controlled by transputers using a simplified software protocol which anticipates transmission or receipt of such communication control commands. One is not prevented from using the parallel processing system on the serial network with all the features provided by conventional operating systems and languages, such as OCCAM (A trademark of INMOS Group of Companies). Upon direction by the active node's transputer, data is transmitted or received by the node under the control of a parallel transfer controller utilizing a simplified protocol which is essentially a hardware protocol.

In the preferred embodiment of the present invention the fast parallel channel is dedicated solely to the transfer of data so that the hardware protocol is minimized. Likewise, the serial links are dedicated solely to the transfer of control signals so that the software protocol is minimized. As a result, the total transfer time of the data, including starting and ending protocols is minimized so that data may be transferred at very high speeds between nodes. Thus, the system of the present invention is particularly useful for image processing and pattern recognition, speech recognition, measurement correlation of different instruments at different sites, large bandwidth data acquisition systems, data correlation for trigger decisions and data acquisition/compression in high energy physics experiments.

The system is economical in that it can be implemented using standard highly advanced economical components such as commercially available processors, operating systems, higher order language compilers, serial links and cross bar switches. The system is also simple in that it can be implemented using only common digital circuits having counters and buffers, and it requires simple protocols with only one handshake to establish the necessary connections. Moreover, the command and control flow is completely separated from the data flow. The system is also versatile in that many different topologies can be realized by combining various processors and different supporting languages on a modular hardware structure. This advantage makes the invention easy to integrate with existing operating systems for parallel processing and makes possible the use of any of several conventional languages such as OCCAM, Parallel C, Pascal, and ADA.

BRIEF DESCRIPTION OF THE DRAWINGS

For a more complete understanding of the present invention, and for further details and advantages thereof, reference is now made to the following Detailed Description taken in conjunction with the accompanying drawings, in which:

FIG. 1 is a block diagram illustrating the application of the present Parallel Data Transfer Network Controlled by a Serial Network to a fixed mesh parallel processing configuration consisting of a master processor node and three slave nodes;

FIG. 2 is a block diagram illustrating the application of a Parallel Data Transfer Network Controlled by a Dynamically ReConfigurable Serial Network to a dynamically configurable parallel processing system with one master and a plurality of slave nodes;

FIG. 3 is a block diagram illustrating the configuration of a typical processing node in a fixed parallel processing system applying the Parallel Data Transfer Network Controlled by a Serial Network; and

FIG. 4 is a block diagram illustrating the configuration of a typical processing node in an N-dimensional, dynamically configurable, parallel processing system applying the Parallel Data Transfer Network Controlled by a Dynamically Re-Configurable Serial Network.

FIG. 5 is a block diagram illustrating a preferred embodiment of the parallel transfer controller.

FIG. 6 is a block diagram illustrating the transmission of communication control commands using the Simplified Communication Control Command Protocol over the Serial Communication Network to control the transmission of data between processing nodes using the Simplified Parallel Data Transfer Protocol over the Parallel Communication Network.

DETAILED DESCRIPTION OF THE DRAWINGS

The present invention relates to a method and apparatus for implementing serial control of parallel data communication in a parallel processing system which overcomes many of the disadvantages found in the prior art. The present invention maximizes high density data communication speed and yet maintains the flexibility of dynamic reconfiguration of the parallel processing network topography.

FIG. 1 illustrates a typical multiple-instruction-multiple-data (MIMD) parallel processing system consisting of a first master processor node 100 and first, second and third slave processor nodes 200, 202, 204 in a fixed mesh configuration. This configuration utilizes the novel ap