JPH02240765A - Data communication system for computer - Google Patents

Abstract

PURPOSE:To improve the performance of a data communication system by transferring selectively the processed data obtained from a data processing part to the processors set in the direction of a vertical or horizontal line via a communication control part. CONSTITUTION:A network control part NC receives a packet from a processor PE or another PE and detects the PE* included in the first word of the packet. The processor numbers X and Y showing the addresses of matrix number forms of the processors in the address that receives the packet are written into the PE*. Thus the value of the PE* is compared with the processor numbers (x) and (y). Then the packet is sent to the east E from the west W or vice versa as long as X = x is not satisfied. Then the packet is sent to the north N from the south S or vice versa when X = x is satisfied and unless Y = y is satisfied. Then the packet is used when the data are processed in a processor if X = x and Y = y are satisfied. As a result, a self-routing is attained for transfer of data in the least distance.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to a data communication system for a computer, particularly a data-driven computer, a processor used in the system, and a data communication method.

(b) Conventional technology In recent years, research has been progressing toward the realization of practical parallel processing computers, and the inventor has already completed the development and evaluation of a data-driven computer and its language processing software. are doing.

[Tanaka et al.: "Prototype of data-driven computer SPM", Information Processing Society of Japan 36th Annual Conference Proceedings 7B-5゜Nishiyo et al. = "Compiler for data-driven computer SPM",
7B-6゜Tanaka et al.: “Performance evaluation of data-driven computer SPM (1)
"Information Processing Society of Japan 37th National Conference Proceedings lN-4゜Okamoto et al.: "Performance evaluation of data-driven computer SPM (2)
] In general, a data-driven computer executes as a program a data graph in which various instructions are connected by arcs indicating the flow of data. Arithmetic processing is performed according to simple execution rules in accordance with the non-Neumann-type philosophy of "executing processing."

Such a data-driven computer mainly consists of three components: a data pair detection mechanism, an arithmetic processing mechanism, and a program storage mechanism, and the outline of its execution processing is as follows.

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

This data pair detection mechanism detects and outputs a set of operand packets that can be operated on. The detected set of operand packets is then processed by the arithmetic processing mechanism.The resultant packet is given a new node number in the program storage mechanism and sent to the data pair detection mechanism.By continuing to repeat this process, A series of processing is executed.

The inventor of the present application is currently developing a highly parallel data-driven computer E D D E N in which various improvements have been made to the above-mentioned data flow computer, especially its processor architecture.
(Enhanced Data Driven
ine) is currently being developed. In this EDDEN, l
We aim to operate a large-scale data-driven computer that connects up to 124 IT element processors realized by C\105-LSI chips, and we also aim to operate flexible systems such as small-scale systems with several PEs and medium-scale systems with several dozen PEs. The goal is to make it configurable and apply it to a wide range of fields such as signal processing, image processing, graphics, various simulations, and CAD.

(c) Problems to be solved by the invention - As mentioned in h, in order to construct a system in which a large number of element processors are connected, it is necessary to make the arithmetic processing in each element processor and the communication processing between processors independent, and Optimization of network systems for inter-processor communication is required, and by realizing these optimizations, high-performance computers can be obtained.

(d) Means for Solving the Problems The data communication system of the present invention arranges a large number of processors in rows and columns, and has a plurality of vertical communication lines that cyclically connect each vertical processor column and each horizontal processor row. A data communication system for a computer that performs data communication between processors using a plurality of horizontal communication lines that cyclically connect the data. Communication control that selectively transfers processing data obtained from a processing unit to a processor in either a vertical line or a horizontal line, and the communication control unit transfers processing data from an adjacent processor to a vertical line or a horizontal line. It is in charge of communication control for supplying data obtained through the processor to the data processing section of the processor, or selectively transferring data to the processor in either the vertical direction or the horizontal direction.

The processor of the data communication system of the present invention is equipped with four bidirectional input/output ports for connection with four adjacent processors in each row direction and column direction, and each port corresponds to the basic information amount of communication data. It is equipped with an input register and an output register with a storage capacity of

The data communication method of the present invention is a data communication method in which communication data is transmitted and received between a plurality of data flow type processors that are matrix-coupled in association with matrix numbers, and the communication data includes The associated column number is written as the destination column number, and each processor compares its own column number with the destination column number of the communication data transferred to the processor, and Communication data when the numbers match are processed by the processor, and communication data when the numbers do not match is transferred to an adjacent processor.

(e) Operation According to the data communication system of the present invention, a network system in which a large number of processors are connected in a torus is adopted, and each processor has a communication control unit mainly for inter-processor communication as a data processing unit. Since these are provided independently, when realizing the processor as an LSI, it is possible to reduce the number of bins by connecting the upper and lower torus, and to create a --like structure. , the entire system can be made smaller and lower in price.

In addition, the processor of the system of the present invention has an input register and an output register each having a basic information amount of communication data, that is, an information amount of one packet, at four input/output ports that perform input/output with neighboring processors on four sides. Since the processors are provided as a pair, data transfer between processors can be completed in packet units every time data is transferred. Therefore, since data transfer does not stall in the middle of a packet, it is possible to avoid a deadlock phenomenon in which stalled data interferes with communication of other data.

Furthermore, according to the data communication method of the present invention, the destination processor number (corresponding matrix number) is written in the communication data, so each processor uses internally generated data or data transferred from other processors. By detecting the destination processor number of the incoming data, the processor itself can determine which processor among the four adjacent processors this data should be transferred to. Therefore, self-routing can be realized in which data can be communicated to the destination processor through the shortest route by the transfer operation of each processor.

(f) Embodiment FIG. 1 shows a highly parallel data-driven computer system as an embodiment of the present invention, and FIG. 2 shows the configuration of element processors.

First, the element processor (PE) shown in Fig. 2 basically consists of a program storage (PS), a firing control/color management section (FC
CM), instruction execution unit (EXE), and queue memory (Q
) are connected in a circular pipeline (ring) structure.

The program storage (PS) updates node numbers, assigns constants, and copies results. Ignition control/color management department (
FCCM) performs firing control and management of color acquisition and release using the above-mentioned two-stage queue storage method. The instruction execution unit (EXE) executes instructions such as floating point/integer arithmetic, condition determination, branching, and simple constant generation, and composite instructions thereof.

The queue (Q) is a buffer that absorbs any data flow fluctuations on the ring. Buffer memory is required because ■
This is when copying, (1) forced input to the ring, (2) delay in output from the ring, (2) search of waiting list in (FCCM), etc. occur. This elemental processor (PE) includes:
A function is added to dynamically change the operation modes of ① to ② according to the amount of data retained in the queue (Q), thereby controlling the degree of parallelism.

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

The network control unit (NC) maintains four communication ports for north, south, east, and west, and performs routing control based on a torus connection network of a maximum of 1024 processors (PE). A vector calculation control unit (VC) controls the execution of vector calculation related instructions and normal memory access instructions. The control section (VC), the input control section (IC) and the output control section (OC)
) is provided with a bypass line for structure (vector) communication. External data memory (EDM) is a data memory that stores structures, etc., and has a capacity of 512 KB (1
28 words x 32 bits). Although the tarock system is a synchronous system, it is assumed that the inside of the network control section (NC) operates in a self-discovery system.

EDDE using many such element processors (1'E)
The basic configuration of N is based on connecting nXn element processors in a torus connection network, as shown in FIG. The torus connection network is a network in which a large number of processors are arranged in rows and columns, and a plurality of vertical communication lines cyclically connect processor rows in each vertical direction, that is, north-south direction (N-5), and each horizontal direction, that is, east-west direction (N-5). Data communication between arbitrary processors is possible using a plurality of horizontal communication lines that cyclically connect the processor rows of W-E).

In the system of this embodiment, data exchange with the network is performed by inserting a network interface (NIF) into any communication terminal in the north-south direction (N-5). The interface (NIF) and 16 to 64 element processors are mounted on one processor port, and a torus connection link is formed on a printed circuit board.

The configuration of a small/medium-sized system uses a general-purpose EWS or a personal computer as the host computer, and a network interface (N
IF). In terms of implementation, one to four processor boards and one bus interface board are mounted on an E.
We will insert it directly into the rack of WS etc.

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

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

■ Large torus connection 1024 (32 x 32) element processors are connected by a torus connection network. As a mounting form, 32 elements Brose-Nosa and NIF are mounted in the north-south (N-5) direction on one printed circuit board, and links in the east-west (W-E) direction are formed on the motherboard 1.

The data packets used in the data-driven computer configured as described above can be roughly divided into execution packets used for program execution and non-execution packets used for purposes other than program execution. An example of this is shown. The packet format is a fixed length except for the packet that holds the structure body, and is 33 bits x 2 words on the pipeline ring in the processor (PE) and 18 bits x 4 words on the network. .

The contents of each field in the packet format of FIG. 4 are shown below.

HD (lbit) Identifier of the first word (header) and second word (tail) in the case of 285 packets per month.If it is a header, 1"EX
(lbit Flag 5IODE for identifying packets output from the pipeline ring to the outside of the PE (2bit Identification code 5-CODE (3 bits) for identifying the type of packet such as execution packet, non-execution packet, etc.: ~ Combined with l0DE Identification code OPCODE-M (5 bits): Main instruction code. Specifies the type of instruction in the instruction execution unit (EXE). Also holds the number of data to be synchronously processed during n5ync. .

0PCODE-5 (6 bits): Sub instruction code. The commands defined by the main instruction code will be defined in more detail.

ODE* (maximum 11 bits): Data flow graph node number C0LOR (4 bits): Color identifier. A job number that identifies the environment when sharing programs through subroutine calls, processing time-based data, and executing the same data flow graph multiple times.

PH1 (LObit): PE number. Maximum of 1024 P
Identification number for identifying E.

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

HT (1 bit) When the number of two words is 4 or more words,
A flag that identifies headers, tails, and intermediate words is °l for headers or tails.

RQ (1 bit): A flag added to packets transferred on the network. The existence of the word can be recognized because the value is inverted each time it is transferred. Furthermore, inversion of the value becomes a transfer request signal for forwarding the packet. In addition, the header and tail can be identified together with the HT flag.

ADDRESS (16bit): Stores the memory address when loading/dumping data in each memory.

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

The network control unit (NC) receives the packets shown in FIGS. 4(c) and 4(e) from the processor (PE) or from another processor (PE),
Detects (PE@I at the first beginning of the packet.

This [PE number] is the destination processor number (x
, y) have been written, this value is compared with the number (x, y) of the processor in question.

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

If X=x, the packet is sent to city(S) unless y=y
Transfer from north (N) to south (S) or from north (N) to south (S).

Then, when X=x and Y=y, this packet is subjected to data processing within the processor.

Therefore, data packets are transferred between a large number of torus-coupled matrix processors, first in the east-west direction, and then in the north-south direction, thereby realizing self-routing with minimum path distance transfer. .

Figure 3 shows the network control unit (NC) for realizing self-routing on the torus network as described above.
) is schematically shown, and its routing algorithm is shown according to the same figure. In addition, in Figure 3,
(RNI) (RNO) is an input shift register and an output shift register that constitute a hole input/output port, and consists of four stages of registers (r). Similarly (R5I) (R5O
) constitutes the critical output port, (RWl) (R^゛0) constitutes the four-person output port, and (REI) (REO) constitutes the east input/output port. Further, "OJ" indicates a confluence, and "◎" indicates a branch.

The routing algorithm is as follows.

■, your PE number (x, y), network pX
The torus of q (q: N-*S direction, q: W-4E direction), the destination PE number of the packet is (x, y), and △Xmi (X - x ) mod q l△x1≦q/2
Δymi(Y-1) modp lΔy1≦p/2.

11. The PE numbers are y=o, 1.
2,... p Let x=O1l, 2,..., q in the direction from W to E.

11■, \l0DE means the value of the \l0DE field of the tag of the packet. (~l0DE-(10 is the packet to the host.) (1) R1 When △y=Q, output the packet to P. When Δy≠0., output the packet to S. (2) R2 When △X≠0. When △x=O and △y>0, output the packet to S. When △x=0 and △y=Q and MODE≠, 00, output the packet to P. △x = O and △y=0. When MODE=00, output the packet to N. When Δx=0 and △y〉O, output the packet to N. (3) R3 When Δx+Q, output the packet to E. When Δx=0 and △y〉0, output the packet to N. Outputs the packet to S when Δx=O or L y = O and MOD E≠00 Outputs the packet to P when ΔX=O and Δy=Q and!+l0 When DE=00, outputs the packet to N・Input/output Δx When =O and △y〈0, output the packet to N (4) R4 When Δ~==0 and MODE≠00, output the packet to P. When ≠0 or MODE=00, output the packet to N.
Output to (5) R5 When △x>O, output the packet to E. When △x=O and △y>0, output the packet to S. When △x=O and Δ)r≦O, output the packet to N. When Δx<0, output the packet to W.■, Routing is performed when the header of the packet arrives, and subsequent data is output to the same route until the tail of the packet arrives.

V, PE number (X, Y) and network size are:
It shall be possible to set it in advance. However, p, (1 is limited to a power of 2. Also, when calculating △X and △y, it is possible to use a mode that does not take the modulus (corresponding to a lattice network).

When connecting Vl and I'E in a ring, N
If -S is connected, routing can be performed using the above routing algorithm.

The following is an example of a self-routing algorithm, but it is not limited thereto.

On the other hand, the configuration of the input/output ports of the network control unit (NC) in FIG. 3 is as shown in the diagram. r)..., so the four-word format packets shown in FIGS. 14(c) and (e) can all be stored as they are in the input port or output port. This means that on a two-way communication path that requires two-way communication, such as a torus network, even if a packet is stuck in front of one direction and packet transfer in that direction is stopped, the packet unit is transferred to the port. This eliminates one of the causes of deadlock, which is when the process is interrupted and stopped. That is, for example, since one set of packets is completely stored on the input or output side of the input/output port, the processor can transfer other packets in other directions.

(G) Effects of the Invention According to the present invention, in order to reduce the size and cost of the entire system, a communication control mechanism can also be built into the PE chip, and the number of pins on the chip is limited by the basic connection state of the processor. ,
It is possible to realize a data communication system in which the distance between processors is small, self-routing is possible, a block structure is possible, deadlock can be avoided, and implementation is easy, a processor therefor, and a data communication method.

[Brief explanation of drawings]

FIG. 1 is a system diagram showing the data communication system of the present invention, FIG. 2 is a block diagram showing the schematic configuration of the processor of the present invention, FIG. 3 is a schematic diagram of the main gate configuration of the processor of the present invention, and FIG. Figures (a) to (e) are packet configuration diagrams. (PE)...Element processor, (EXE)...Instruction execution unit, (ED~1)...External data memory, (NC
)...Network system 911 part.

Claims (3)

[Claims] (1) A large number of processors are arranged in rows and columns, and multiple vertical communication lines cyclically connect each vertical processor row and multiple horizontal communication lines cyclically connect each horizontal processor row. In a data communication system for a computer that performs data communication, each processor includes at least a data processing section and a communication control section, and the communication control section converts processed data obtained from the data processing section into vertical lines or Communication control that selectively transfers data to a processor in either direction of a horizontal line, and the communication control unit transfers data obtained from an adjacent processor via a vertical line or a horizontal line to a data processing unit of the processor. 1. A data communication system for a computer, characterized in that it manages communication control for supplying or selectively transferring data to a processor in either a vertical line or a horizontal line. (2) In the processor of the data communication system for a computer according to claim 1, the processor is provided with four bidirectional input/output ports for coupling with four adjacent processors in each of the row and column directions, and each port A processor comprising an input register and an output register having a storage capacity corresponding to the basic amount of communication data. (3) In a data communication method in which communication data is sent and received between multiple data flow type processors that are matrix-coupled in association with matrix numbers, the above communication data includes information that is associated with a destination processor. The row number is written as the destination row number, and each processor compares its own row number with the destination row number of the communication data transferred to the processor, and if both numbers match. A data communication method in which communication data at a time is processed by the processor, and communication data at a time when there is a mismatch is transferred to an adjacent processor.