JPH0635874A - Parallel processor - Google Patents

Abstract

PURPOSE: To provide a generalized and hypercube topology having superior connectivity, a high band performance and a low waiting time on a processor having parallel architectures realizing a high output processing through the use of multiple central processing units CPU. CONSTITUTION: The processor is provided with plural processing elements arranged D-dimensionally and divided into sub-sets 11. Each processing element in the sub-set has a bus 13 and it can communicate with one another. Each processing element is the member of one sub-set 11 in the respective dimensions. The respective processing elements in one sub-set 11 are connected in the sub-set by an output means. They transmit messages to the other processing elements in the pertinent sub-set. They have individual input means for the respective processing elements in the sub-set and they receive the messages from the other processing elements on the input stages.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION The present invention relates to a number of central processing units (C
PU) to achieve high power processing with a parallel architecture.

[0002]

2. Description of the Related Art Increasing the processing performance by using a multi-stage CPU in which the number of stages is as many as possible has been widely discussed in recent years. This requirement is now expanding into the academic and commercial fields and is being applied to VLSI microprocessors at the system level on a small scale. However, at least 2 in terms of wide acceptance and large scale
There are two major obstacles.

First, it is very difficult to design and build the multifunctional and powerful communication required by a highly parallel general-purpose computer. Second, it is not entirely clear how to program such a computer once built. Very important work has already been carried out in a new programming paradigm based on functional object-oriented models and dataflow models (see: Bronnenberg WJHJ, Nijman).
L, Odjik, EAM, van Twist R
AH: “Doom; a decentralized”
object-oriented machine "
IEEE Micro Vol 7 No 5 (Oct
1987) _pp 547-553, Watson,
I, et al: “Flagship: aparale”
l architecturefor declara
"Tive programming" in Proce
sings of 15th Annual Sym
Posium on Computer Archit
ecture IEEE Comp Soc Pres
s (1988) _pp 124-130, Veen A
H, "Dataflow machine archit
electure "ACM ComputingSurve
ys, Vol 18 No 4 (Dec 1986)
_pp 365-396).

The purpose of a subnet is to be able to make communication connections to host elements (processing nodes and suitable memory). Ideally, these communication connections should have the following properties: a) High bandwidth. This allows large amounts of data to be transferred between host elements whenever required. b) Low latency. This ensures that any process sending a message and requesting a reply does not have to wait an excessive period of time.

Subnets can contribute most to low latency, especially when there are many switching levels to negotiate.

Moreover, regardless of the relative physical location of the correspondent (metric symmetry) and activity elsewhere in the network, the subnet must maintain the connection to a uniform tolerance of bandwidth and rotational latency. I won't. Finally, if the interconnect topology does not work on medium and large Mighty computers, it has favorable architectural properties (latency, latency, etc.) over a wide range of possible network sizes.
Bandwidth, symmetry, independence) is required.

A conventional architecture for parallel processors is Larry D Wittie: "Communi".
Cation Structures for Lar
geNetworks of Microcomput
ers, IEEE, 1981.

[0008]

Problem to be Solved by the Invention Binary hypercube (hyp
ercube) has low metric symmetry because one processor takes a significant amount of time to reach from one point to another. Also, the waiting time inherently varies greatly. further. Although the hypercube is good in bandwidth, doubling the number of processors increases the diameter by one, causing the worst delay in larger assemblies.

A general purpose in this area is to achieve an architecture with high inter-node connectivity, so that messages can reach their destination via a minimum number of nodes. The ultimate limitation of interconnects is the physically supportable wiring density or other means of communication between nodes (eg, optical bus, free endurance injector (fr).
ee-standing optical trans
fuser) or other means).

[0010]

According to the present invention, there are provided a plurality of processing elements arranged in dimension D and divided into a plurality of subsets, all processing elements in a subset being in between. In a processor having one bus for communication, each said processing element being a member of one subset in each dimension, each processing element of one subset is connected by output means to the bus of that subset, Send messages to multiple other processing elements in
A parallel processor is provided, characterized in that a separate input means corresponds to each other processing element of the subset and receives messages from said other processing element on each corresponding input means.

A processing element cannot send a message to a number of other elements at the same time, but this is the theoretical total interconnect on the input / output lines between every element and every other element. It has been found that the optimized configuration does not degrade performance. Therefore, the performance is almost the same as the theoretical optimum performance, but the internal wiring density is substantially reduced.

In the preferred embodiment, the processing elements in a subset are arranged in a line, the processing elements located between the ends of the line sending messages along the line to other processing elements on one side. And one separate output means for sending a message along the line to the other processing element on the other side. This means that the processing elements located between the ends of the line can simultaneously send messages to the left and right along the line, but the critical wire density does not increase. That is, the wiring density is greatest at the crossover point between the bus of one line and the bus of an orthogonal line (in any case, one processing element may be the other element within that subset and another subset). Messages can be sent simultaneously to other elements (the processing elements being members of which).

In the simplest configuration, the processor comprises a two-dimensional array of processing elements, each row of which forms a subset and each column of which forms a subset. The processing elements at the intersections of rows and columns perform the task of communicating between the two subsets. Hereinafter, the expression "cluster" will be used for subsets.

The advantages according to the invention are essentially measurable, modular, highly connected, capable of supporting an unlimited number of processing elements (PEs) linked by a symmetrical low latency network, It is an architecture that has the same cost performance as a binary hypercube.

The degree of metric asymmetry is accepted by clustering the processing elements (PEs) in tightly connected gluers and concatenating these groups also using high bandwidth links and the option of repeating the process. It

[0016]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT Referring to FIG. 1, each cluster contains a maximum of w multiple nodes. This value w, that is, the net width, is a fixed characteristic of the device (however, it is variable within the architecture). Each node has its own non-directional bus, which connects each node to other selected elements in the same cluster. Other elements are w
It can mean that one can select from one and the same input link. Each line is electrically driven by only one output device, which causes a limiting phenomenon associated with sharing, a so-called wired-OR sudden failure that limits speed.
tch) (Gustavason D B, Theus
J: "Wire-Or logic trans
"Mission lines" IEEE Micro
Vol3 NO. 3 (June 1983), _pp 5
1-55) can be prevented. Here, this sudden breakdown changes the ownership of the bus or even the directionality of the signals. Data transfer is done by individual receivers,
Alternatively, the communication is carried out through whole communication or communication for each crust. The architecture strictly depends on the cluster interconnection method. The entire system is a D-dimensional lattice formed by taking the Dth Cartesian product of the cluster graph topology. This has the effect of imposing a cluster configuration in each dimension, an iteratively formed configuration known as a generalized hypercube. FIG. 1 shows a two-dimensional example forming a 2D hyperplane, where each node belongs to two independent orthogonal clusters. This approach can be extended to higher dimensions. That is, an N-dimensional hypercube in which each node is equally composed of N clusters is composed of w N-1 dimensional hyperplanes connected by w (N-1) cluster links. This configuration of overlapping orthogonal clusters provides the requisite high-band interconnect for the entire message passage.

Unlike a simple binary hypercube system, D
Will only use low values (eg 2 or 3) even for large devices. For example, for w = 32, the number achieved, the three-dimensional structure, would include 32K processing elements (PEs).

Due to the low latency of the connection, the hardware can provide shared memory with the passage of messages. A processor attempting to access a shared location sends a short request message to the node having that location and receives a response (containing data if the request was a read) when the request was processed. To minimize latency, remote memory management hardware can read and write the entire memory independent of the processor. In many cases, the sanctions for such contention-free access to memory will be more than double that for local RAM.

FIG. 1 shows a processor with an array of 6 × 6 processing elements 10, each element forming a node of the array. Each row of elements constitutes a cluster 11, and each column of elements constitutes a cluster 12. Arrays can be extended to more than two dimensions. In the three-dimensional case, the array is built in 6 layers, each layer being identical to that shown in FIG. 1, with each column forming a cluster. The same principle of symmetry applies to the extended dimension of the system. For example, the fourth dimension can be generated by replacing each element with a cluster of 6 elements.

The six elements of the cluster are connected by a bus 13, which will be described later with reference to FIG.

FIG. 2 shows the structure of the element 10. This element comprises a host element 20 which comprises one or more microprocessors 21, for example Motorola M8800 microprocessors. Also,
The host element is the memory 22 and the communication element 23.
Is included. A network element 24 is attached to the host element 20, and the network element 24 is a cluster interface unit (CIU) for each dimension for interfacing a node.
25 are provided. However, in FIG.
Three CIUs are shown as 7,28. A unique host interface unit (HIU) 29 is provided for exchanging information with the host element 20. The network element 24 includes a network element management unit 30.

Referring to FIG. 3, four elements 10
Clusters of elements are shown, each element being given the reference numeral 10a, 10b, 10c, 10d. These elements are connected to a bus 13, which is in turn made up of four buses, each consisting of 16 lines. One bus is connected from each network element for output. 1
The output from one network is connected to the input of each other network in the cluster. Therefore, each network will have one output and three inputs.
Each host element corresponds to another dimension of the array,
It will also have an output and an input for each other bus connected to it. Thus, width w = 4
3D array will have 3 outputs and 12 inputs for each network element. Each line of the bus 13 is electrically driven by a unique output device,
Prevents sudden failure due to wired OR. Such an arrangement has the disadvantage that the host element can send only one message at a time to other elements in its cluster. However, this is not a major drawback. This is because the host element is in any case a serial device (or some limited number of serial devices), and in any case it can simultaneously send messages to other elements in orthogonal clusters.

One of the limiting factors in the density and interconnection of one array described above is the wiring density. The wiring density limitation takes a plurality of forms depending on whether the bus 13 is a hard wire, a microwave link, an optical link, a wireless link, or the like. The area of maximum wiring density is the crossover point between orthogonal buses. FIG. 4 shows a configuration in which the internal connectivity of the elements in the cluster is increased without increasing the wiring density at the crossover point. In this configuration, each element 10b, 10c across the bus has two outputs, an output extending to the left and an output extending to the right. Each element can simultaneously send messages to the left and right sides along the bus. The only increase in wiring density is found at the output of the network element. This is not an important area.

The operation of the device is as follows. When one network element sends data or a command to another network element, the data or command constitutes a packet in the communication element 23 which addresses the receiving element. This packet is sent out via the host interface unit 29 and further through the appropriate cluster interface unit 26, 27 or 28 corresponding to the receiving element. Receiving element Of course, it may not be in the same cluster as the originating element, so it must be sent to the node located at the intersection of the originating cluster and the receiving cluster. There may also be intermediate steps. For a D-dimensional array, the maximum number of steps will be D. The network element management unit 30 determines the route by which the packet is sent to the destination. For example, in restrictive routing, messages that need to be sent in the southwest direction are sent west and then south, thereby avoiding collisions with messages arriving from the southwest direction. The latter message is sent east and then north. Other routing protocols can be considered. When the message reaches the bus 13 of the receiving cluster, the message is recognized by the address of the receiving element and is received by the cluster interface unit of the receiving element.

When the packet is received, the packet is buffered in the buffer memory of the network element 24. The network element 24 can receive multiple packets at the same time and either process it on its host element or send it to the orthogonal cluster. An arbitration circuit is provided in each of the cluster interface units 26, 27, 28 to buffer packets that arrive at the same time and process them efficiently in time. If the packet is sourced by the element itself, this packet is a HIU
It is sent to the communication element 23 via 29 and processed by the processing element 21 or stored in the memory element 22.

As an example, the operation (a + b) × (c +
d) can be executed by parallel processing as follows. If all parameters are variable, operation a + b
Is performed on the first element of the array, and operation c
+ D is executed in the second element. The first and second elements send a packet containing the results of these operations to the third element, and the third element performs the multiplication operation on the results of these operations.

The preferred method of routing messages for a network is a variation of warm hole routing (Daily W J, Seitz CL: Multi).
icons: message-passin
g current computers ", I
EEE Computer, Vol 21, No. 8
(Aug 1988), _pp 9-23). Each worm consists of only one head, which will be referred to as a packet hereinafter.

The processing elements described above are connected in clusters of width w in each variable dimension. In the cluster to which the processing element belongs,
A node can send a packet to one of the other (w-1) nodes containing the cluster by having a non-directional line, or at the same time communicate the packet to these subgroups. A packet that reaches a node has two basic forms. a) Intra-cluster: The tours on the last link (preferably one link) of these journeys are propagated locally. b) Inter-cluster: Go to the orthogonal cluster after being received by the current node.

Packets arriving are buffered,
Then, it waits for selection by the CIU. The CIU selects from its (w-1) sources using a fast round robin algorithm. The selected packet is treated differently depending on these formats. Intercluster packets are HI
Proceed to the host element via U and finally written directly to a predetermined area of the local buffer memory. Intra-cluster packets go directly to the CIU of the next orthogonal cluster on these routes. The packet follows the minimum distance path to the receiver unless it is defective. Even large systems (> 10 ⁴ nodes) have a diameter of at most 3
, The routing is essentially negligible over the entire feasible size spectrum. Deadlocks can be easily avoided by limiting routing or by introducing built-in buffer management. By reducing the diameter, the performance drawbacks of these strategies can be minimized.

In addition to packets with data, the network layer is network control packets (NC packets).
It recognizes a special packet called "." And passes the control information between network elements. This control information is used for housekeeping (ho
information, automatic functions performed by the CIU. However, control packets are used by the network element management unit, which manages network activity, load balancing (if applicable) and strategic congestion control.

About Links Communication between network elements within a cluster is by high bandwidth links. There are great advantages in link separation and network functionality. In particular, features that are highly dependent on link device technology can be isolated. In fact, cluster links can be recognized in several ways. For example, a short broad active back (sh
ort broad active backplan
e), demultiplexed points-point links,
It can be recognized as a multi-stage optical star configuration or a set of ULSI devices. Transfer rates up to 1 G Byte / s can be achieved with active backplanes or demultiplexed star distributors. Different link protocols are suitable for these different techniques. For example, the protocol used on parallel bus devices differs from that required by serial optical cables.

A 16-bit non-directional bus device has been adopted with an accompanying parallel bus link protocol. Unlike typical LAN or WAN protocols, the link layer is not intended to provide error control or flow control (both performed by the network layer), preserving packet boundaries, transparency on the physical link. , And for multi-drop addressing.

The global memory packet structure is designed to support shared access global memory. Obviously, due to the possible size of the system, 32-bit addressing does not allow uniform access across the global address space. The basic process uses a 32-bit virtual address, which is translated into a 32-bit physical address by the local MMU. Global memory is organized in logical addressing units or superpages. Each superpage is interleaved across hyperplanes of dimension H (≤D). Thus, in a two-dimensional system, the entire global memory can be fully interleaved across all host elements (H = 2), or only local clusters (H = 1), or work together in different ways. Can be divided into common areas used by the processing.
This provides a great deal of flexibility over a wide range of shared memory applications.

Short accesses to global memory are forwarded with unique CLP priority and are treated like unhindered packets to minimize latency.

Host Element The host element configuration is shown in FIG. This architecture does not preclude the use of specialized nodes designed for paradigms such as data flow.
The memory element (ME) 22 directly makes a request to and a response from the global memory. The communication element (CE) 23 also includes a direct memory access control circuit (DMAC) 50 that directly transfers data to the local memory 51 of the processing element (PE) 21. This DMAC50
Can optimize message transfer for the software paradigm in use, and also maintains a message descriptor that indicates the memory length and location of the message to be transferred.

The function of the shared memory element (ME) 22 is coordinated by a built-in hardware module called a global memory control circuit (GMC). GMC consists of the following two sub-modules. a) Global memory management unit (GMMU) 54.
It traps a range of physical addresses under the control of karnal and uses a special global memory guarantor (qua).
A packet is generated in the (lifer). The GMMU can interpret the interleaved format currently in use on the address generated for active processing. b) Global memory access unit (GMAU) 5
5. It receives the memory access packets passed by the communication element (CE). See also GMAU55
Can generate single or block DMA access to the global memory segment. further,
The GMAU 55 can be used to perform higher level operations including synchronization, list handling, garbage collection.

Shared memory access can occur at the system level or the user level. In the former case, the user process is not always directly addressed (on the RAM disk)
Instead, look at global memory as a shared structure. When access is required, a blocking or non-blocking system call is initiated, in response to which the local kernel notifies the GMMU of the request. This approach can be used by the process of prefetching data before it is actually needed. True user level access is generated directly by the user process, translated by the local memory management unit (MMU), GMM
Trapped by U. The access process can be delayed if the waiting time is short enough, or can be suspended if necessary.

Network Element As shown in FIG. 6, each CIU consists of three distinct functional units (note that these functional divisions should not be construed as limited by the package location in the VLSI of the network element). a) Transmission unit 60. It sends messages to other nodes within a common cluster. b) Receiving unit 61. This is to select a message arriving from another node in the common cluster by using an appropriate arbitration mechanism and locally transfer or route it to another CIU. c) CIU control unit 60. This is to monitor the use status of the buffer of each of the possible receiving sources that exchanges NC packets with the corresponding CIU control units as needed.

The transmitting unit 60 is an integral automaton (that is, a finite state machine) called a link control unit.
Is used to transfer packets on the cluster link. Such packets can originate from the HIU if they originate locally or if they originate directly from any of the NE receiving units (intra-cluster messages).

The receiving unit 61 comprises several buffered input multiplexers, each multiplexer having a round robin arbitration circuit for source selection. If the different types of packets are for local or non-local transfer, the packets are buffered separately. However, given any category,
There is space for only one packet at each multiplexer input, so the total buffer requirement is adequate. The receive buffer space is monitored by the CIU control unit, that is, regardless of the data currently being transferred, the CIU control unit generates an NC packet, which is directly transferred to the local transmission unit to serve as a control frame immediately. It When a packet arrives at one input, the arbitration circuit associated with this input will receive the transmission request as long as it can be transferred to the next node. The packet selected by the arbitration circuit is immediately sent to these receivers. There are four main cases: a) The packet is sent to the PE via the HIU and CE, and is directly written in the buffer memory associated with the processing of the receiving side. b) The packet is sent to the sending unit in another CIU (intra-cluster traffic). c) The packet is sent to the global memory access unit via the HIU. The global memory request packet is sent to the GMAU and the CMAU issues a DMA to its associated global memory module. d) The packet is sent again to the global memory management unit via the HIU. For example, a global memory request packet with read data is sent to the GMMU where it is matched with pending requests.

Signal definitions are not standardized across the implementations of the architecture, as they are modified appropriately by the technique. These physical definitions are decoupled from the higher layers of the architecture and can be changed without affecting the design of modules other than transmitter and receiver units.

The required bus lines are: a) D15-D0: For data b) DELIM (Warm delimiter): Indicates that the worm has started or ended (the frame flag is not used to avoid complication of transparency). c) CS (control strobe): indicates a control frame. d) DS (Data Strobe): indicates the presence of valid data words on the link.

The control frame is used to control the communication level between the transmitting unit and the receiving unit. The control frame has, for example, a one-word length or a two-word length, and has information as a reception buffer state. Packet first
Word can interpret the routing information by the receiving NC and includes the cluster addressing information as well as the information. At the receiving unit, this word is removed and ignored, i.e. new routing information will be present before the packet.

The HIU receives the packet for local transfer directly from the CIU, sends it directly from the CIU, reverses the function, and demultiplexes the packet from the HE to the appropriate CIU. Within the management unit / HIU assembly is a system clock register (not shown) that maintains system time. By carefully minimizing the skew, only one global lock signal can be distributed throughout the system. Global time, if appropriate, can be used to synchronize HE operations and also to stamp packets.

One of the most difficult problems in multi-computer design is the choice of interconnect strategy, which provides truly general support for parallel applications in machines based on many powerful processing elements. You must have enough flexibility to provide.

[0046]

According to the present invention, it is possible to provide a generalized hypercube topology having excellent connectivity, high bandwidth, and low latency. Importantly, this architecture is possible for a very large number of processors and is suitable for both fine and crude programming techniques 10 ³ -1.
Allows the construction of MIMD machines with 0. ⁵ processing elements.

[Brief description of drawings]

FIG. 1 is a block circuit diagram showing a two-dimensional parallel processor according to the present invention.

FIG. 2 is a block circuit diagram showing a configuration of a node in FIG.

FIG. 3 is a block circuit diagram showing an internal configuration of the cluster shown in FIG.

FIG. 4 is a block circuit diagram showing a modified example of FIG.

5 is a block circuit diagram showing details of the host element of FIG. 1. FIG.

FIG. 6 is a block circuit diagram showing the details of the CIU of FIG.

[Explanation of symbols]

10 Proxing Element (PE) 11, 12 Cluster (Subset) 13 Bus 20 Host Element (HE) 21 Proxing Element 22 Memory Element 23 Communication Element 24 Network Element (NE) 25, 26, 27, 28 Cluster Interface Element (CIU) ) 29 host interface unit (HIU) 30 network element management unit 54 global memory management unit (GMMU) 55 global memory access unit (GMAU) 61 reception unit 62 CIU control unit 63 transmission unit

 ─────────────────────────────────────────────────── ───Continued from the front page (72) Inventor Louis McLean McKenzie, Glasgow, Munten Street, England 18 G49 AX (72) Inventor Robert John Sutherland England, Glasgow, Lancaster・ Terrace 2 G 120 U

Claims (8)

[Claims] 1. Comprising a plurality of processing elements (10) arranged in a dimension D and divided into a plurality of subsets, all processing elements in a subset being one bus (1) for communication between them.
3), wherein each said processing element is a member of one subset in each dimension, each processing element of one subset is connected to the bus of that subset by output means and A parallel arrangement, characterized in that it sends a message to a processing element, a separate input means corresponding to each other processing element of the subset and receiving a message from said other processing element on each corresponding input means. Processor. 2. The processing elements in one subset are arranged in one line, the processing elements located between the ends of the line sending one message along the line to the other processing element on one side. A processor according to claim 1, comprising means and separate output means for sending a message along the line to other processing elements on the other side. 3. Each processing element comprises a communication means for generating a message packet and sending it to another element, said communication means generating an address indicating whether the source of the packet is the same subset or another subset. The processor according to claim 1, further comprising: 4. Each processing element comprises one
Means for receiving a message packet from another element in a cluster on one bus, means for recognizing whether a packet source is the same cluster or different orthogonal clusters, and a packet source when the packet source is the same cluster Means for writing in memory within the element and retransmitting the packet to a different orthogonal bus when the sources of the packet are in different clusters.
Processor described in. 5. The processing element further comprises means for receiving a message packet, means for changing an address in the message packet, and means for retransmitting the message packet. The processor according to any one of 1. 6. The processing element further comprises means for generating a message packet and sending it to another element, each message packet comprising a unique address part and at least a unique command part and a unique data part. 6. A processor according to any one of claims 1 to 5, including one. 7. A processor as claimed in any one of the preceding claims, in which a bus of a subset is electrically driven by an output device of only one element connected to the subset. 8. A processor as claimed in any one of the preceding claims, in between two and three dimensions.