JPH09190421A - Data communication system for computer - Google Patents

Abstract

PROBLEM TO BE SOLVED: To make arithmetic processing and inter-processor communication processing independent from each other by providing a communication control part with specific number of bi-directional input/output ports. SOLUTION: This system is provided with a network control part NC operating independent from each mechanism for original data processing at an element processor PE, and the input/output port of the network control part NC is provided with the input port of a shift register r... of each 18 bits of four stages and the output port of the shift register r... of four stages. Consequently all the packets of four-word form can be stored in an input port or an output port as they are. Then a network system torus-connecting many processors is adopted and each processor is provided with a communication control part mainly for inter-processor communication in addition to a data processing part. Thus, four input/output ports inputting/outputting between with adjacent processors in four directions are respectively provided with a pair of input/ output registers with the basic information quantity of communication data, namely one packet of information quantity.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a computer, and more particularly to a data communication system of a data driven computer.

[0002]

2. Description of the Related Art In recent years, research has been advanced toward the realization of a practical parallel processing computer, and the inventor of the present application has already completed the development of a data driven computer and its language processing system software and their evaluation. ing.

[Tanaka et al .: "Prototype of Data Driven Computer SPM", Proc. Of the 36th National Conference of Information Processing Society of Japan, 7B-
5.

Nishikawa et al., "Compiler for Data Driven Computer SPM," 7B-6.

Tanaka et al .: "Performance Evaluation of Data Driven Computer SPM (1)" Proceedings of the 37th National Conference of Information Processing Society of Japan 1N-4.

Okamoto et al., "Performance Evaluation of Data Driven Computer SPM (2)," 1N-5. ] In general, a data driven computer executes a data flow graph in which various instructions are connected by arcs indicating the flow of data as a program. In other words, "processes are executed from processable data". According to such a non-Neumann type idea, arithmetic processing is performed by a simple execution rule.

Such a data-driven computer is mainly composed of three components, that is, a data pair detecting mechanism, an arithmetic processing mechanism and a program storing mechanism. The outline of the execution processing is as follows.

First, in a data driven computer, a set of data called a packet is used as a unit, and the packet is composed of data to be processed, connection information (node number) of data flow graph, and instruction code. It

In this data pair detection mechanism, a set of operand packets that can be operated is detected and output. Then, the detected set of operand packets is processed by the arithmetic processing unit. As a result, the packet is given a new node number in the program storage mechanism and sent to the data pair detection mechanism.
A series of processes is performed by repeating such processes.

The inventor of the present application is currently in charge of a highly parallel data driven computer EDDE in which the processor architecture of the data flow computer as described above is improved.
We are developing N (Enhanced Data Driven ENgine).

In this EDDEN, one-chip CMOS
-Maximum of 10 element processors realized by LSI
Aiming to operate a large-scale data-driven computer with 24 units connected, and with a flexible configuration such as a small-scale system with several PEs and a medium-scale system with several tens of PEs, signal processing, image processing, graphics, The goal is to be applied to a wide range of fields such as various simulations and CAD.

[0012]

As described above, in order to construct a system in which a large number of element processors are connected, independence of arithmetic processing and inter-processor communication processing in each element processor, and inter-processor communication Optimization of the network system and so on are required, and high performance computers can be obtained by realizing these.

[0013]

In a computer data communication system according to the present invention, a plurality of processors are arranged in rows and columns, and a plurality of vertical communication lines for cyclically coupling each vertical processor row and each horizontal processor. In a data communication system of a computer that performs data communication between processors with a plurality of horizontal communication lines that cyclically connect rows, each processor has a data processing unit that performs data processing, and a row direction and a column direction. And a communication controller having four bidirectional input / output ports for coupling with adjacent processors, and each of the input / output ports has a storage capacity corresponding to the information amount of one packet. An input register and an output register, five output control registers of the input / output ports and five merge control circuit units provided corresponding to the input sides of the data processing units, and the input / output ports of the input / output ports. Force register and five branch control circuit units provided respectively corresponding to the output side of the data processing unit, and the communication control unit inputs from the input register sent to the branch control circuit unit. Controlled communication data or processing data obtained from the processor to be sent to the merge control circuit unit, the communication control unit, the processing data sent to the merge control circuit unit to the output register, Alternatively, the communication data sent to the merge control circuit unit is controlled to be sent to the output register or the data processing unit.

In particular, the inside of the communication control unit operates in a self-synchronous manner.

[0015]

1 shows a system of a highly parallel data driven computer as an embodiment of the present invention, and FIG. 2 shows the configuration of an element processor.

First, the element processor (PE) shown in FIG.
Basically, the program storage (PS), the firing control / color management unit (FCCM), the instruction execution unit (EXE), and the queue memory (Q) are connected in a cyclic pipeline (ring) structure.

The program storage (PS) updates the node number, assigns a constant, and copies the result. The firing control / color management unit (FCCM) manages firing control and acquisition / release of colors by a two-stage queuing storage system. The instruction execution unit (EXE) executes instructions such as floating point / integer arithmetic, condition determination, branching, and simple constant generation, and their composite instructions.

Queue (Q) is a buffer memory that absorbs any data flow fluctuations on the ring. Buffer storage is needed when copying, forced input to the ring, output delay from the ring, waiting list search in (FCCM), etc. The element processor (PE) is provided with a function of dynamically changing the operation modes of to according to the data stay amount of the queue (Q), thereby controlling the parallelism.

Further, when the queue (Q) inevitably overflows, an external queue is formed on the external data memory (EDM) to absorb the external queue and continue program execution.

The network control unit (NC) holds communication ports of four systems of north, south, east, west and performs routing control based on a torus connection network of up to 1024 processors (PE). The vector operation controller (VC) controls execution of vector operation related instructions and normal memory access instructions. A bypass line for structure (vector) communication is provided between the control unit (VC) and the input control unit (IC) and the output control unit (OC). External data memory (EDM)
Is a data memory for storing structures and the like, and has a capacity of 5
It is about 12 KBytes (128 K words × 32 bits). The clock system is a synchronous system, but the inside of the network control unit (NC) operates in a self-synchronous system.

The basic configuration of EDDEN using a large number of such element processors (PE) is n × n as shown in FIG.
The basic principle is to connect the element processors of the stand by the torus connection network. In the torus connection network, a large number of processors are arranged in a matrix, and each processor is arranged in the vertical direction, that is, in the north-south direction (N <->
S) a plurality of vertical communication lines that cyclically connect the processor columns and a plurality of horizontal communication lines that cyclically connect the processor rows in each lateral direction, that is, the east-west direction (W <-> E), to any processor. It enables data communication between them.

In the system of the present embodiment, data is exchanged with the network by connecting the network interface (NI) to an arbitrary communication link in the north-south direction (N <-> S).
F) by inserting. The interface (NIF) and 16 to 64 element processors are mounted on one processor board, and a torus connection link is formed on a printed circuit board.

As the configuration of the small / medium-scale system, a general-purpose EWS or personal computer is used as a host computer and is connected to a network interface (NIF) via the bus interface thereof. The mounting form is 1
~ 4 processor boards and 1 bus interface board will be directly inserted into a rack such as EWS.

As the configuration of the large-scale system, the following two types of configuration methods can be considered depending on the application field.

Cluster Connection Using the processor boards described above as one cluster, the clusters are connected via a cluster interface. The cluster interface manages the collection and distribution of data in each cluster.

Large Torus Connection 1024 (32 × 32) element processors are connected by a torus connection network. As a mounting form, 32 element processors in the north-south (N <-> S) direction and the NIF are mounted on one printed circuit board, and the east-west (W <->
Links in the E) direction are formed on the motherboard.

The data packets used in the data-driven computer having the above-described configuration are roughly classified into execution packets used for program execution and non-execution packets used for other than program execution. Examples thereof are shown in FIGS. 4 and 5. Is shown. The packet format has a fixed length except for the packet holding the structure body, and employs a structure of 33 bits × 2 words on the pipeline in the processor (PE) and 18 bits × 4 words on the network. .

The contents of each field in the packet formats of FIGS. 4 and 5 are shown below.

HD (1 bit): 1 for a 2-word packet
Identifier of the second word (header) and second word (tail). "1" for header.

EX (1 bit): A flag for identifying a packet output from the pipeline ring to the outside of the PE.

MODE (2 bits): Identification code for identifying the type of packet such as execution packet and non-execution packet.

S-CODE (3 bits): An identification code that defines processing for a packet together with MODE.

OPCODE-M (5 bits): Main instruction code. Specifies the type of instruction in the instruction execution unit (EXE). It also holds the number of data items to be synchronized during nssync.

OPCODE-S (6 bits): Sub instruction code. The command specified by the main command code is specified in more detail.

NODE # (up to 11 bits): Node number of the data flow graph.

COLOR (4 bits): Color identifier.
Identification number that identifies the environment when multiple executions of the same data flow graph are performed, such as program sharing by subroutine calls and processing for time-based data.

PE # (10 bit): PE number. Up to 1
An identification number for identifying 024 PEs.

DATA (32 bit): 32-bit integer or floating point number.

HT (1 bit): It is "1" in the case of a flag header or tail that distinguishes the header and tail from the intermediate word in the packet having four or more words.

RQ (1 bit): A flag added to a packet transferred on the network. The value is inverted every time one word is transferred on the network, so that the existence of the word can be recognized. Further, the inversion of the value becomes the transfer request signal for transferring the packet forward. Also, the header and tail can be identified together with the HT flag.

ADDRESS (16 bits): A memory address is stored at the time of loading / dumping data in each memory.

The characteristic configuration of the computer of the embodiment of the present invention having the above basic configuration is that the network control unit (NC) operates independently of each mechanism for original data processing in the element processor (PE). )It is in.

The network control unit (NC) is shown in FIG.
A packet as shown in (c) and FIG. 5 (e) is received from the processor (PE) concerned or from another processor (PE) and the first word [PE
#] Is detected. Since the processor number (X, Y) of the destination in the matrix number format of the destination processor to which the packet is to be transferred is written in this [PE #], this value and the number (x, y) of the relevant processor are written. Compare with.

By this comparison process, for example, unless X = x, the packet is transferred from west (W) to east (E) or east (E) to west (W).

If X = x, then packets are forwarded from south (S) to north (N) or north (N) to south (S) unless Y = y.

Then, when X = x and Y = y, this packet is provided for data processing in the processor.

Therefore, the data packet is first transferred in the east-west direction and then transferred in the north-south direction among a large number of torus-coupled matrix processors, thereby realizing the self-routing of the shortest distance transfer. ing.

FIG. 3 schematically shows a data system of a network control unit (NC) for realizing self-routing on the torus network as described above, and its routing algorithm is shown according to FIG. FIG.
In the above, (RNI) and (RNO) are an input shift register and an output shift register which form a north input / output port, and are composed of four stages of registers (r). Similarly (RSI)
(RSO) constitutes a south input / output port, (RWI) (RWO) constitutes a west input / output port, and (REI) (REO) constitutes an east input / output port. In addition, “◯” indicates confluence and “⊚” indicates branching.

The routing algorithm is as follows. I. My PE number is (x, y), network is px
The torus of q (p: N-> S direction, q: W-> E direction), the destination PE number of the packet is (X, Y),

[0050]

[Equation 1]

Assume that II. The PE numbers are y = 0, 1, 2, ... In the direction from N to S, and p = 0, 1, 2, ..., q in the direction from pW to E. III. MODE means the value of the MODE field of the tag of the packet. (MODE = 00 is a packet to the host.) (1) When R1 Δy = 0, output the packet to P. When Δy ≠ 0, output the packet to S. (2) When R2 Δx ≠ 0, send the packet to W. Output When Δx = 0 and Δy> 0 output the packet to S When Δx = 0 and Δy = 0 and MODE ≠ 00 output the packet to P When Δx = 0 and Δy = 0 and MODE = 00 send the packet to N Output When Δx = 0 and Δy <0, output packet to N (3) When R3 Δx ≠ 0, output packet to E When Δx = 0 and Δy> 0, output packet to S Δx = 0 and Δy = 0 When MODE ≠ 00, the packet is output to P. When Δx = 0 and Δy = 0 and MODE = 00, the packet is output to N. When Δx = 0 and Δy <0, the packet is output to N. (4) R4 Δy = 0 And if MODE ≠ 00 Output packet to P Output packet to N when Δy ≠ 0 or MODE = 00 (5) Output packet to E when R5 Δx> 0 Output packet to S when Δx = 0 and Δy> 0 Δx = 0 And when Δy ≦ 0, the packet is output to N. When Δx <0, the packet is output to W. IV. Routing is performed when the packet header arrives, and subsequent data is output to the same route until the packet tail arrives. V. The PE number (x, y) and the size of the network can be set in advance. However, p and q are limited to powers of two. In addition, when calculating Δx and Δy, the mode that does not take Mogello (corresponding to the grid network)
It is also possible. VI. Even when PEs are connected in a ring shape, routing can be performed by the above routing algorithm by connecting NS.

The above is one example of the self-routing algorithm, but the present invention is not limited to this.

On the other hand, the network control unit (NC) of FIG.
As shown in the figure, the configuration of the input / output port of 4 is provided with input ports of four stages of 18-bit shift registers (r). Therefore, it is possible to store all of the 4-word format packets of FIGS. 4C and 5E in the input port or the output port. This means that on a two-way communication path such as a torus network that requires two-way communication, even if packet transfer in this direction is stopped while packets are being used before one direction, the packet unit is the port unit. This will eliminate one of the causes of the deadlock of interrupting and stopping. That is, for example, one packet is completely stored in the input side or the output side of the input / output port, so that the processor can transfer other packets in the other direction.

In this embodiment, a network system in which a large number of processors are connected in a torus is adopted, and each processor is provided with a communication control unit mainly for interprocessor communication independently of the data processing unit. Therefore, when implementing a processor LSI, the number of pins can be reduced and a uniform structure can be achieved by the torus connection, and the system can be made smaller and the cost can be reduced by incorporating the LSI with the communication controller independent. Can be expected.

Further, in this embodiment, four bidirectional input / output ports are provided for coupling with adjacent processors in four directions in each of the row direction and the column direction, and each port corresponds to the basic information amount of communication data. It has an input register and an output register having a storage capacity of

As described above, in this embodiment, the four input / output ports for inputting / outputting from / to the adjacent processors on the four sides are provided with input registers each having a basic information amount of communication data, that is, an information amount for one packet. Since the output register is provided as a pair, the data transfer between the processors can always be completed in packet units for each data transfer. Therefore, since the data transfer does not stagnate in the middle of the packet unit, it is possible to avoid the deadlock phenomenon that the stagnation data hinders the communication of other data.

Further, the present embodiment is a data communication method for transmitting and receiving communication data between a plurality of data flow type processors which are associated with a matrix number and are matrix-connected, and the communication data includes a transmission destination. The matrix number associated with the processor is written as the destination matrix number, and each processor compares the matrix number of the processor itself with the destination matrix number of the communication data transferred to the processor. , The communication data when both numbers match is processed by the processor, and the communication data when the numbers do not match are transferred to the adjacent processor.

As described above, in this embodiment, since the destination processor number (corresponding matrix number) is written in the communication data, the data internally generated in each processor or transferred from another processor. By detecting the destination processor number of the incoming data, the processor itself can determine which of the four adjacent processors the data should be transferred to. Therefore, self-routing can be realized in which data can be communicated to the destination processor by the shortest route by the transfer operation of each processor.

[0059]

According to the present invention, in order to reduce the size and cost of the entire system, a communication control mechanism can be built in the PE chip, and the number of pins of the chip can be limited depending on the basic connection state of the processor. It is possible to realize a data communication system having a small inter-processor distance, a uniform structure, avoiding deadlock, and easy to implement.

[Brief description of the drawings]

FIG. 1 is a system diagram showing a data communication system according to an embodiment of the present invention.

FIG. 2 is a block diagram showing a schematic configuration of a processor according to an embodiment of the present invention.

FIG. 3 is a schematic diagram of a main-part gate configuration of the processor according to the embodiment of the present invention.

FIG. 4 is a packet configuration diagram.

FIG. 5 is a packet configuration diagram.

[Explanation of symbols]

 PE element processor EXE instruction execution unit EDM external data memory NC network control unit

Claims (2)

[Claims] 1. A plurality of processors are arranged in rows and columns, and a plurality of vertical communication lines that cyclically connect each vertical processor column and a plurality of horizontal communication lines that cyclically connect each horizontal processor row are provided. In a data communication system of a computer that performs data communication between processors, each processor has four bidirectional connections for connecting a data processing unit that performs data processing and adjacent processors in four rows and four columns. A communication control unit having an input / output port of
And an input register and an output register each having a storage capacity corresponding to the information amount of one packet in each of the input / output ports, and an output register of each of the input / output ports and an input side of the data processing unit. And 5 branching control circuit sections provided corresponding to the input registers of the input / output ports and the output side of the data processing section, respectively. The communication control unit controls to send the communication data input from the input register or the processing data obtained from the processor, which is sent to the branch control circuit unit, to the merge control circuit unit, and the communication control unit. Is the processing data sent to the merge control circuit unit to the output register,
Alternatively, a computer data communication system is characterized in that the communication data sent to the merge control circuit unit is controlled to be sent to the output register or the data processing unit. 2. The data communication system for a computer according to claim 1, wherein the inside of the communication control unit operates in a self-synchronous manner.