JP2840294B2 - Data communication system for parallel computer - Google Patents

Description

The present invention relates to a data communication system for a computer, and more particularly to a parallel computer for transmitting and receiving data between a plurality of processors in accordance with a processor number given to each processor. The present invention relates to a data communication system.

(B) Conventional technology In recent years, research has been conducted toward the realization of a practical parallel processing computer. In particular, with the advance of semiconductor technology, a combination of a communication control unit and a data processing unit has been integrated into one chip. Of this element processor LSI
Many studies have been conducted to realize a parallel processing processor by connecting a large number of devices.

For example, in the parallel processing computer disclosed on page 181 to page 218 of Nikkei Electronics published on April 9, 1984, a plurality of one-chip element processors called Impp are connected in a ring. Thus, a data communication system for transmitting and receiving data is configured.

In addition, as disclosed in the 38th (Early 1989) Transactions of Information Processing Society of Japan 2T-2, the inventor of the present application has proposed a large-scale parallel data drive system in which a maximum of 1024 one-chip element processors are connected. Computer EDDEN (Enhanced Data Driven ENgi
ne) is under development.

(C) Problems to be Solved by the Invention In the above-mentioned parallel computer, each element processor is identified by assigning a processor number, and the destination processor number is added to the communication data, and each processor arrives. A method is often used in which the communication data is selectively input to its own data processing unit by comparing the processor number of the communication data thus obtained with its own processor number. In addition, it is necessary to have a function of outputting the result data processed in the parallel computer to the outside of the parallel computer and passing it to another data processing device such as a host computer. In order to realize such a function, a processor number is assigned to each processor and a unique processor number is also assigned to the host computer, and the processor number of the host computer is added as a destination number to the above-described result data. In general, a method is used to identify that the data is external to the parallel computer.

For example, in the above-mentioned processor called Impp, as shown in the Nikkei Electronics page 206, the module number “0” is allocated to the host computer among the module numbers (16 types) represented by 4 bits. Then, in the interface unit inserted into the ring bus, a method of detecting the data of the module number “0” and outputting it to the host computer is adopted.

However, in a computer that interconnects a number of element processors by a connection network having a two-dimensional or three-dimensional geometric topology like the EDDEN described above, if a processor number is assigned to the host computer in this way, Some of the topologies that should be configured with a uniform processor will be missing, reducing the processing power of the parallel computer and making the parallel computer extremely difficult to program.

Further, in a computer such as EDDEN, when result data is transferred from each element processor to the host computer, there are many types of paths, and the result data destined for the host computer is transferred to the shortest path. It is desirable to be able to transfer by.

Therefore, an object of the present invention is to provide a data communication system of a parallel computer which can control transfer of result data to the host computer via the shortest path without disturbing the processor connection topology of the parallel computer. It is.

(D) Means for Solving the Problems The present invention relates to a data communication of a parallel computer which performs data communication between element processors by connecting a plurality of processors having a plurality of communication ports for connection with an adjacent processor. In the system, each processor is identified by a unique processor number,
The communication data has at least a processor number of a destination of the data and an external flag indicating whether the data should be output to the outside of the parallel computer or processed inside the parallel computer. When the communication data arrives via any of the plurality of communication ports, the destination processor number held by the communication data is compared with its own processor number. If the two processor numbers do not match, the data is compared. The data is selectively output to any one of the plurality of communication ports so that the data arrives at the destination processor in the shortest time. When the data indicates that it should be processed inside a parallel computer, the data is processed in its own processor. When the two processor numbers match and the external flag held by the data indicates that the data is to be output to the outside of the parallel processing computer, the data is processed by its own processor. Communication data to be output to a predetermined communication port among the plurality of communication ports without data processing, and to be output to the outside of the parallel processing computer, the data should be output to the outside of the parallel computer. And a processor number of a processor closest to the outside of the parallel computer as a destination processor number.

(E) Function According to the data communication system of the present invention, when the result data is output from each element processor of the parallel computer to the host computer, at the source element processor,
The result data may be transmitted with the processor number of the element processor closest to the host computer and an external flag indicating that the data is to be output to the outside of the parallel computer. Such a result data packet is:
A processor in the middle of the route does not match its own processor number with the processor number of the packet, so the packet is sent to one of the communication ports so that the packet can reach the processor with the processor number held by the packet over the shortest distance. Selectively output. Thus, when the result data packet arrives at the processor having the processor number held by the packet, the condition that the processor number of the packet matches the processor number of the packet and the external flag indicates outbound is detected. The result data packet is output to a predetermined communication port of the processor. Therefore, if the host computer is output to the predetermined communication port of the processor via an output interface or the like, the result data packet is output to the host computer.

In this way, the result data packet issued from any element processor is transferred to the host computer at the shortest distance and without being input to the data processing unit of any of the processors on the way.

Further, since the result data packet is identified by an external flag different from the processor number, the connection topology of the parallel computer is not disturbed.

Also, from the above description, data packets other than the result data packet are transferred via the shortest path until reaching the destination processor, as in the case of the result data packet.
In the destination processor, the data is input to the data processing unit and subjected to data processing.

(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 an element processor.

First, the element processor (PE) in Fig. 2 basically consists of a program storage (PS), a firing control and color management unit (FCC).
M), an instruction execution unit (EXE), and a queue memory (Q) are connected in a cyclic pipeline (ring) structure.

The program storage (PS) updates the node numbers, assigns constants, and copies the results. The firing control and color management unit (FCCM) manages the queuing of left and right opinoids and the acquisition and release of colors. The instruction execution unit (EXE) executes instructions such as floating-point / integer operation, condition determination, and branching. The queue (Q) is a buffer memory that absorbs any data flow fluctuations on the ring.

The vector operation control unit (VC) controls execution of a vector operation related instruction and an external data memory access instruction. The external data memory (EDM) is a memory for storing structures, vector data, and the like.

The communication control unit (NC) has four communication ports of north, south, east and west, and performs routing control based on a torus connection network of up to 1024 processors (PE). The input control unit (IC) performs a process of inputting a data packet from the communication control unit to the ring. The output control unit (OC) performs a process of outputting a data packet from the ring to the communication control unit. A bypass line for structure (vector) data communication is provided between the vector operation control unit (VC), the input control unit (IC), and the output control unit (OC).

The basic configuration of an EDDEN using a large number of such element processors (PE) is based on the connection of n × n element processors by a torus connection network as shown in FIG. With the torus connection network, a large number of processors are arranged in a matrix,
A plurality of vertical communication lines that cyclically connect each vertical processor group and a plurality of horizontal communication lines that cyclically connect each horizontal processor group enable data communication between arbitrary processors. is there.

In such a system, the exchange of data between the network and the outside uses a network interface (NI
F).

The data packets used in the data driven computer having the above configuration are roughly classified into an execution packet used for program execution and a non-execution packet used for other than program execution. FIGS. 4A to 4E show examples. Is shown. The packet format is fixed length except for the packet holding the structure data, and is 33 bits x 2 words on the pipeline in the processor (PE) and 18 bits x 4 words on the network (communication control unit). is there.

The contents of each field in the packet format of FIG. 4 will be described below.

HD (1 bit): an identifier of the first word (header) and the second word (tail) in a two-word packet, and “1” in the case of a header.

EX (1 bit): A flag for identifying a packet to be output from the pipeline ring to the communication control unit.

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

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

OPCODE-M (5 bits) and OPCODE-S (6 bits): Instruction codes for identifying the type of instruction.

NODE # (11bit): Node number of data flow graph.

COLOR (4bit): Color. Identification number for identifying the environment when executing the same data flow graph multiple times, such as program sharing by subroutine calls.

DATA (32bit): Numeric data such as integers and floating point numbers.

HT (1 bit): A flag for identifying a header, a tail and an intermediate word in a packet on the network.

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

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

The input control unit (IC) on the pipeline ring has a processor number register for storing its own processor number. FIG. 6 shows the configuration of the processor number register. The PE number X in the figure is a horizontal (east-west) PE number (column number), and the PE number Y is a vertical (north-south) PE number (row number). Together, the processor numbers uniquely identify each processor. A flag bit called PEACT in the figure is a flag indicating whether or not the processor number has already been set, and is "0" if not set, and "1" when set.

The communication control unit (NC) receives a packet as shown in FIGS. 4C and 4E via a communication port.

In the special operation mode (PEACT = 0), the communication control unit regards all data packets input from all ports in the east, west, north and south as packets to itself, inputs them to the pipeline ring, and is indicated by the identification code. A predetermined process is performed. At this time, when a non-executable packet having an identification code shown in FIG. 6 and indicating the loading into the processor number register arrives at one of the east, west, north and south ports, the communication control unit transmits this to the input control unit on the pipeline ring. (IC), where the processor number register is loaded with the specified processor number and PEACT
The flag is set to "1". When the PEACT flag is set to "1" in this manner, the communication control unit (NC) of the processor operates in the normal operation mode.

In the normal operation mode (PEACT = 1), the communication control unit sets the PE # (the destination processor number of the packet) in the first word of the arriving packet and the own processor number set in the own processor number register. The packet is input to the pipeline ring only when the two match, and when the two do not match, the packet is output to one of the east, west, north, south and north ports in accordance with a predetermined routing algorithm to be directed to the adjacent processor. Transfer.

FIG. 5 shows the type of packet identified by MODE. As shown in FIG. 5, a packet holding MODE = 00 is identified as a result packet output to the host computer.

The main feature of the computer system of the present invention is that the communication control unit of each processor performs processing according to each case depending on whether or not the MODE identifier is MODE = 00.

To explain this, the operation of the communication control unit will be described in more detail. FIG. 3 schematically shows the configuration of the communication control unit (NC). In the figure, (RWI) and (RWO) are a self-synchronous input shift register and an output shift register constituting the west (W) input / output port, and are composed of four stages of 18-bit registers. Similarly, (REI) (REO) means east (E)
The input / output port, (RNI) (RNO) constitutes a north (N) input / output port, and (RSI) (RSO) constitutes a south (S) input / output port. ○ indicates a merging circuit, and 、 indicates a branch circuit.

The routing algorithm in the communication control unit will be described with reference to FIG. Each of M1 to M5 is a packet merging circuit that assigns a priority in the order of the numbers shown in the figure and merges arriving packets (number 1 has the highest priority). R1 to R5 are packet branch circuits, respectively, which perform processing according to the following algorithm.

§I. Change my processor number (row number, column number) to (y,
x), the array size of the network is p × q (p: vertical direction,
q: horizontal direction), specify the destination processor number of the packet as (Y,
X), and Δx≡ (X−x) mod q, | Δx | ≦ q / 2 Δy≡ (Y−y) mod p, | Δy | ≦ p / 2. (Mod indicates a modulo operation.) §II. Processor numbers are arranged in the order from N to S. y = 0, 1, 2,..., P In order from W to E, x = 0, 1, 2 ,... Q.

§III.MODE means the value of the MODE field of the packet,
MODE = 00 means that the packet is destined for the host computer.

 The branch condition is as follows.

(1) When R1 MODE ≠ 00 and (PEACT = 0 or Δy = 0), output the packet to P.

When MODE = 00, PEACT = 1 and Δy = 0, output the packet to E.

 Otherwise, output the packet to S.

(2) .R2 MODE ≠ 00 and (PEACT = 0 or (Δx = 0 and Δy
= 0)), the packet is output to P.

When PEACT = 1, Δx = 0 and Δy> 0, output the packet to S.

When PEACT = 1, Δx = 0 and Δy <0, the packet is output to N.

 Otherwise, output the packet to W.

(3) .R3 MODE ≠ 00 and (PEACT = 0 or (Δx = 0 and Δy
= 0)), the packet is output to P.

When PEACT = 1, Δx = 0 and Δy> 0, output the packet to S.

When PEACT = 1, Δx = 0 and Δy <0, the packet is output to N.

 Otherwise, output the packet to E.

(4) When R4 MODE ≠ 00 and (PEACT = 0 or Δy = 0), output the packet to P.

When MODE = 00, PEACT = 1 and Δy = 0, output the packet to E.

 Otherwise, output the packet to N.

(5) .R5 When Δx = 0 and Δy> 0, output the packet to S.

 When Δx = 0 and Δy <0, output the packet to N.

 When Δx <0, output the packet to W.

 Otherwise, output the packet to E.

As can be seen from the above description, in the normal operation mode in which PEACT = 1, each processor communication control unit determines that when the destination of the packet = (Y, X) and the processor number of each processor = (y, x), X = X unless W = x
From E to E or from E to W. If X = x, forward the packet from N to S or from S to N unless Y = y. Further, when transferring a packet from a port of W or E to a port of N or S, or transferring a packet from the inside of the pipeline ring to any port of W, E, N, or S, a modulo operation is performed by the processor. The direction in which the distance becomes smaller is selected, and the packet communication control function (self-routing function) at the shortest distance is always realized.

Further, the packet arrives at the destination processor, and Δ
When x = Δy = 0 is detected, if MODE ≠ 00, it is input to the pipeline of the destination processor and processed,
If the packet is destined for the host computer of MODE = 00, the packet is not input to the pipeline ring but is output to a specific communication port (all packets except the packet arriving at E are output to the E port).

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

Next, FIG. 7 shows an example of the overall configuration of a computer EDDEN in which element processors (PE) each having a communication control unit as described above are connected in an array of 4 × 4 (p = q = 4). A more detailed description of embodiments of the invention will be given.

In FIG. 7, the data output from the host computer is converted into the format shown in FIG. 4C or FIG.
N), 4x via network interface (NIF)
The data is input to a group of four processors.

When the power supply of the computer shown in the figure is turned on, the value of the processor number register of each PE is undefined. Next, when the hardware reset signal (RST) is supplied to all the PEs, the PEACT flags of all the PEs are cleared to 0, and the operation modes of the communication control units of all the PEs are set to the special operation mode.
Next, a load packet (data value = 0) from the host computer to the processor number register through the above-described route.
0) is issued, the packet is placed in the upper left (1 row, 1 column) P
Reach E W port. The branch circuit R3 in the communication control unit of the PE detects the condition of PEACT = 0 and converts the packet to P.
(In the pipeline ring), the number 00 is set in the processor number register of the PE, and the
Is set to "1". Thereafter, the PE
It is identified as E00 (the numbers are row numbers on the left and column numbers on the right). Next, when a load packet (PE # = 01, data value = 01) to the processor number register is issued, the packet similarly reaches the W port of PEOO, but the processor has PEACT = 1. Therefore, this time, since Δx ≠ 0 at R3 of PE00, the packet is output to the E port and reaches the W port of the PE in the first row and the second column. 1 row, 2 columns
In the PE, since PEACT = 0, the number 01 is set in the PE and PEACT = 1. Similarly, PE02 is set by the load packet (PE # = 02, data value 02), and PE03 is set by the load packet (PE # = 03, data value 03). Next, load packet (PE #
= 10, data value 10) reaches the W port of PE00,
In R3 of the PE, the condition of Δx = 0 and Δy> 0 is detected, the packet is output to the S port, and the PE of 2 rows and 1 column is output.
Is set to PE10. Similarly, PE11, PE12, ... PE33
When the numbers are set to all the PEs, the PEACT flags of all the PEs are set to “1”, and the entire computer operates in the normal operation mode.

In the subsequent normal operation mode, the result packet indicating the end of the program execution and the result packet output to the host computer, such as the result packet obtained by dumping each part of the processor, include the destination processor number 03 in the transmission source processor. MODE = 00 is retained and output.

As can be seen from the above algorithm, this result packet is first forwarded to PE03 over the shortest distance. When the result packet arrives at PE03, Δx = Δy = 0 and MO
The condition of DE = 00 is satisfied.

Therefore, all the result packets arriving at the W port, N port, or S port of PE03 are output to the E port of PE03 and input to the network interface (NIF). Also, the result packet going to the E port of PE03 via the W port of PE00 is input to the network interface (NIF) before arriving at PE03.

The network interface (NIF) constantly monitors the MODE field of an incoming packet.
If it is ≠ 00, it is passed from right to left or left to right in the figure. On the other hand, if MODE = 00, the incoming packet is output to the host computer via the output line (OUT).

With the above functions, the result packet issued from any element processor is transferred to the host computer over the shortest distance and output. Further, it can be seen that such a function is realized without disturbing the processor connection topology of a parallel computer called lattice connection (torus connection).

(G) Effects of the present invention As is apparent from the above description, according to the present invention, without disturbing the processor connection topology of the parallel computer,
Transfer of result data to the host computer can be controlled by the shortest path to the host computer.

[Brief description of the drawings]

1 is a system diagram showing a data communication system of the present invention, FIG. 2 is a block diagram showing a schematic configuration of a processor of the present invention, FIG. 3 is a schematic diagram of a main part of the processor of the present invention,
4 (a) to 4 (e) are diagrams showing the structure of a packet, FIG. 5 is a diagram showing a part of the identification code of the packet, FIG. FIG. 7 is a more detailed system diagram showing the data communication system of the present invention. (PE) ... Processor, (PS) ... Program storage,
(EXE) Command execution unit, (NC) Communication control unit, (NI
F)… Network interface.

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-62-187958 (JP, A) JP-A-63-240663 (JP, A) JP-A-63-113659 (JP, A) JP-A 61-18759 208561 (JP, A) JP-A-60-241155 (JP, A) IPSJ 38th (Early 1988) National Convention Lecture Papers (III) p 1408-1409 (58) Int.Cl. ⁶ , DB name) G06F 15/16 G06F 15/80 JICST Science and Technology Literature Database

Claims (2)

(57) [Claims] 1. A data communication system of a parallel computer for performing data communication between element processors by connecting a plurality of processors having a plurality of communication ports for connection with an adjacent processor, wherein each processor is a unique processor. The communication data is identified by a number, and holds at least a processor number of a destination of the data and an external flag indicating whether the data should be output to the outside of the parallel computer or processed inside the parallel computer. When the communication data arrives at each processor via any of the plurality of communication ports, the destination processor number held by the communication data is compared with its own processor number, and if the two processor numbers do not match. For example, the data is transmitted to the plurality of communication ports so that the data arrives at the destination processor in the shortest time. When the two processor numbers match and the external flag held by the data indicates that the data is to be processed inside the parallel computer. Indicates that the data is to be processed by its own processor, the two processor numbers match, and an external flag held by the data indicates that the data is to be output outside the parallel processing computer. Is output to the specified communication port of the plurality of communication ports without performing data processing by its own processor, and the communication data output to the outside of the parallel processing computer is It has an external flag indicating that data should be output outside the parallel computer, and has the processor number of the processor closest to the outside of the parallel computer. Parallel computer data communication system characterized by having as can destination processor number. 2. A plurality of processors are arranged in rows and columns, and a plurality of vertical communication lines cyclically connecting each vertical processor row and a plurality of horizontal communication lines cyclically connecting each horizontal processor row. A parallel computer that performs data communication between the processors,
In a data communication system of a parallel computer, which is inserted into at least one of the plurality of vertical communication lines or the plurality of horizontal communication lines and has an input / output interface for transmitting and receiving data to and from the outside of the parallel computer, Each of the processors includes at least a data processing unit and a communication control unit. The communication control unit includes four adjacent communication ports for connection with four adjacent processors in each of the row direction and the column direction, and a connection between the data processing unit and the four communication ports. When communication data arrives at the communication control unit of each processor via any of the communication ports, the communication control unit includes:
The destination processor number of the communication data is compared with its own processor number. If the two processor numbers do not match, the data is converted so that the distance to the destination processor is shortest among the four adjacent communication ports. When the two processor numbers match, and the external flag held by the data indicates that the data is to be processed inside the parallel computer, The data is input to the data processing unit of its own processor through the internal communication port for data processing, and the two processor numbers match, and the external flag held by the data indicates that the data is external to the parallel computer. When the data is to be output to the four adjacent communication ports without processing the data with its own processor data. And when communication data arrives at the input / output interface, an external flag held by the data indicates that the data should be processed inside the parallel computer. At the time, the data is passed as it is, and when the external flag held by the data indicates that the data is to be output to the outside of the parallel computer, the data is sent to the outside of the parallel computer. The communication data to be output and output to the outside of the parallel computer has an external flag indicating that the data is to be output to the outside of the parallel computer, and is the closest to the outside of the parallel computer. A data communication system for a parallel computer, comprising a processor and a processor number as a destination processor number.