JPH0652126A - Message passing device of interconnected node network and computer system thereof - Google Patents

Abstract

PURPOSE: To rapidly transmit an I/O message passing between the inter-connection processing elements of a large scale parallel computer system. CONSTITUTION: A mechanism removing the setting processing of I/O constitution and the using of a memory band width to pass by storing an output message from the main memory of a node without using the processing asset of the node is provided and a control and communication route dynamically connecting an input/output data route is given to allow a message to pass the node by using the dynamically connected input/output route without using a processing, a memory band width or the storage asset of the node, and the node 20 allow the message to pass the dynamically connected input/output route when there is not a memory and the request of input data and provide a function simultaneously processes the memory and input data by using the full memory band width of the node.

Description

Detailed Description of the Invention

[0001]

FIELD OF THE INVENTION This invention relates to multi- or multi-processor parallel computing systems, and more particularly to architectures having the ability to rapidly transfer I / O messages between densely parallel processors and processing elements. The present invention provides single instruction multiple data (SIMD) and multiple instruction multiple data (MIM).
It has the ability to dynamically switch between modes D).

[0002]

Cross Reference Patent Applications This application is a continuation-in-part of the following related patent application and claims its priority. "Parallel associative processor system"
19 by Jay Defenderfa et al.
US Patent Application 611,59 filed November 13, 1990
No. 4. 199 by P.M.C., Called "Dynamic Multi-Mode Parallel Processor Array Architecture"
US Patent Application 798,788 filed Nov. 27, 1
issue.

Further, the present application is related to the following patent applications co-filed with the present application. May 1992 by P.A. Wilkinson et al., Entitled "Instructions in SIMD Processing Elements".
US patent application filed on March 22. US patent application filed on May 22, 1992 by P.A. Wilkinson et al., Entitled "Floating Point Realization on SIMD Machines". P's called "SIMD Picket Grouping"
US patent application filed May 22, 1992 by A. Wilkinson et al. US patent application filed May 22, 1992 by P.A. Wilkinson et al., Entitled "Slide Network for Array Processors". US patent application filed on May 22, 1992 by P.A. Wilkinson et al., Entitled "Picket Autonomy in SIMD Machines". A P-system called "H-DOTS-based Array Processor Communication Network"
US patent application filed May 22, 1992 by A. Wilkinson et al. US patent application filed May 22, 1992 by Earl Earl Richardson et al., Which is called "Control Function for SIMD / MIMD Machines".

Further, the present application is related to the following patent applications.
US patent application filed May 22, 1992 by Tea Barker et al., Entitled "Extended Parallel Array Processor". US patent application filed May 22, 1992 by Tea Barker et al., Entitled "SIMD / MIMD Processed Memory Element". US patent application filed May 22, 1992 by Tea Barker et al., Entitled "PME Storage and Transfer / Circuit Switching Mode." May 1992 by Tea Barka et al.
US patent application filed on March 22. US patent application filed May 22, 1992 by Tea Barker et al., Referred to as "N-dimensional modified hypercode".

May 2, 1992 by M. Dup et al., Entitled "Extended Parallel Processor Array Director".
US patent application filed on the 2nd. May 2, 1992 by M Dup et al., Named "APAP Mechanical Package".
US patent application filed on the 2nd. US patent application filed on May 22, 1992 by M Dup et al., Named "APAP I / O Programmable Router". "APA
U.S. patent application filed in March 1992 by T. Barker et al., Entitled "PI / O Zipper Connection".

This application and the above-noted pending patent applications are assigned and owned by International Business Machines Corporation of Armonk, NY. The description of the above-filed patent applications is incorporated herein by reference.

Other Cross-Reference Patent Applications The cross-reference patent applications assigned to the same assignee as the present application and owned at the time of filing this application include: September 2, 1988
Submitted on the 7th, now called "SIMD Array Processor" by James El Teira 1990
Continuation Application No. 07/519, filed May 4, 2014,
US patent application Ser. No. 07 / 250,595, which was abandoned to benefit 332 (EPO on May 3, 1989).
It was first disclosed as application No. 8807855 / 88-A).

US Patent Application No. 07, filed May 13, 1988 by H. Lee, entitled "Circuits and Methods for Realizing Arbitrary Graphs on Polymorphic Meshes".
/ 193,990. U.S. patent application Ser. No. 07 / 426,140 filed Oct. 24, 1989 by Earl Jaffe et al., Entitled "Two-Dimensional Input / Output Method for Massively Parallel SIMD Computers". U.S. patent application Ser. No. 07, filed Nov. 21, 1989 by W. C. Dietrick, Jr. et al., Entitled "Memory Protected Operation Performing Apparatus and Method in Parallel Processor Systems".
/ 439,758.

1991 by David B. Rolf, entitled "Interconnect Processing Element System and Interconnect Method".
US patent application Ser. No. 07 / 698,8 filed May 13, 2013
No. 66. All of the above referenced patent applications pending are all assigned to International Business Machines
Transferred to and owned by Corporation. The description of the above patent application is incorporated herein by reference.

Glossary of Terms ALU is an arithmetic logic unit of a processor. Array Indicates one-dimensional or more-dimensional component or array of components. An array contains an ordered group of data items (array elements) identified by a single name in languages such as Hotlan. In other languages, the names of such ordered data items all refer to data elements or ordered sets that all have the same attributes.

Program arrays generally have a dimension specified by a number or dimension attribute. The array declarator can also specify the size of each dimension of the array for a language. In some languages, an array is an array of table elements. In the hardware sense, an array is a collection of globally identical structures (functional elements) in a massively parallel architecture. An array element in a data parallel operation is an element that can be assigned a parallel operation when the parallel operations are independent and the requested operation can be executed in parallel. In general, an array can be thought of as a grid of processing elements. Each part of the array can be assigned partial data so that the partial data can move around a regular grid pattern. However, the data can be allocated or assigned to any location in the array.

Array Director A device programmed as a controller for the array. The array director performs the function of a master controller (or controller) for the grouping of functional elements arranged in an array.

Array Processors There are two main types of array processors. Part 1
One is a multiple instruction multiple data (MIMD) array processor, and the other is a single instruction multiple data (SIMD) array processor. In MIMD array processors, the processing elements of the array are limited to the same instruction via a common instruction stream, but the data associated with each processing element is unique. The preferred array processor of this invention has other characteristics. It is called the Extended Array Processor and uses the acronym APAP.

Asynchronous There is no regular time relationship. The performance of one function cannot predict the performance of the other function. That is, it occurs without having a regular or predictable time relationship with the performance of the other function. Under control conditions, when the controller is waiting for data to address an idle element, the controller specifies a location to yield control. This maintains the sequence of operations but does not coincide with the time of occurrence of other events.

BOPS / GOPS BOPS or GOPS is an acronym that has the same meaning as a large number (billions) of operations per second. GOPS
reference.

Circuit switching / memory transfer These terms refer to data through a node network
Two mechanisms for moving packets are shown. Store transfer involves each intermediate node receiving a data packet, storing it in its memory, and forwarding it to its destination. Circuit switching involves logically connecting the input port of an intermediate node to an output port so that the data packet does not enter the intermediate node memory but passes through the node directly to the destination. It is a mechanism for commanding.

Cluster A cluster is a station (or terminal, functional device) consisting of a control device (cluster controller) and the hardware (which may be a terminal functional device or virtual component) connected to it. The cluster of the present application includes an array of PMEs, also referred to as a node array. Usually, the cluster has 512 PMEs. The entire PME node array of the present application consists of clusters, each supported by a cluster controller (CC).

Cluster Controller A cluster controller is a device that controls input / output (I / O) operations to one or more devices or functional units connected thereto. The cluster controller is usually controlled by a program stored in the IBM 3601 financial institution communications controller, if present on the device, and executed by the IBM 3272.
If present in the controller, it may be entirely controlled by hardware.

Cluster Synchronizer The Cluster Synchronizer is a functional unit that manages the operation of some or all of the clusters to maintain the synchronized operation of the components. This functional unit maintains a specific time relationship with the execution of the program.

Controller A controller is a device that controls the transmission of data and instructions via the links of the interconnection network. The operation is controlled by a program executed by the processor to which the controller is connected or by a program executed in the device.

CMOS CMOS is an acronym for complementary metal oxide semiconductor technology. It is commonly used in the manufacture of dynamic random access memory (DRAM). NMOS is DRAM
Is another technique used in the manufacture of. Although CMOS is preferred, the technology used to manufacture APAP should not be limited to the scope of semiconductor technology currently in use.

Dotting refers to connecting three or more leads by physically connecting them together. Most back panel buses share this connection method. This term also refers to elapsed time OR DOT, but is used here to identify multiple data sources that can be combined into a bus by a very simple protocol.

The concept of I / O zippers (Zipper, described below) in the present invention implements the concept that a port entering a node can be driven by a port exiting the node or by data coming from the system bus. Can be used. Conversely, data exiting a node is available both as an input to other nodes and to the system bus. Data output to both the system bus and other nodes does not occur at the same time and is a separate cycle.

Dotting is for 2-port PE or PME
Or H when pickets can be used in arrays of various formations by utilizing dotting
-Used in DOT studies. 2D and 3D mesh,
Several topologies are considered, including radix-2N-cubic (or three-dimensional), sparse radix-4N-cubic, and sparse-radix-8N-cubic.

DRAM DRAM is an acronym for Dynamic Random Access Memory and is commonly used as a storage device for the main memory of computers. The term DRAM is a cache,
It also applies to use as memory that is not main memory.

Floating point (FLOATING-POINT) A floating point number is represented in two parts. They are,
It is a fixed point or fractional part, and an exponent part for some assumed radix or base (radix, base). The index is 10
Indicates the actual placement of the decimal point. As a typical floating point representation, for example, the real number 0.0001234 is 0.12.
It is represented as 34-3. In that case, 0.1234 is a fixed point part and -3 is an exponent.

In this example, the floating point radix or base is 10. This 10 is larger than the unit and is either expressed explicitly by the exponent of the floating point display or raised to the power indicated by the characteristic of the floating point display, and then multiplied by the fixed point part to determine the display of the real number. Represents the radix of an implicitly fixed positive integer. Numeric literals can be represented in floating point notation as well as real numbers.

FLOPS This term refers to floating point instructions per second. Floating point calculations are addition (ADD), subtraction (SUB), multiplication (M
PY), division (DIV) and many others. The parameters of floating point instructions per second are calculated using often add or multiply instructions and can be generally estimated to have a 50/50 ratio mixture. This calculation involves the generation of exponents, decimals, and all necessary fractional normalizations. In the present example, a 32-bit or 48-bit floating point format can be addressed (in the present case it was not counted in the case of mixing, but can be longer). Floating point calculations require multiply instructions when performed by fixed point instructions. Some use a 10 to 1 ratio when numerically displaying results, but 6.25 is a more appropriate use in certain studies.
The ratio is shown. Various architectures have different ratios.

Functional device A functional device is hardware capable of achieving the purpose,
Software, or both entities or entities.

G bytes G bytes indicate 1 billion (10 ⁹ ) bytes.
Gbytes / s represents 1 billion bytes per second.

GIGAFLOPS This term means (10) ^** 9 floating point instructions per second.

GOPS and PETAOPS GOPS and BOPS have the same meaning and are 10 per second.
⁹ means operation. PETAOPS is 10 ¹² per second
It means the capacity of the current machine called operation. That of the APAP machine according to this embodiment is exactly the same as BIP / GIP which means 10 ⁹ instructions per second. On some machines, the instruction is more than one operation (ie
Additions and multiplications), the invention does not. Instead, many instructions may be used to perform one operation. For example, the present invention uses multiple instructions to perform 64-bit operations. However, when counting the operations in the present invention, the counting of log operations was not selected. GOPS may be preferred for use in displaying outcomes or performance, but the displayed usage is not consistent. Some encounter MIPS / MOPS, then BIPS / BOPS, and Mega
FLOPS / Giga (Giga) FLOPS / Tera (Terra) FL
Encounter OPS / Teta FLOPS.

ISA ISA stands for Instruction Set Architecture.

Link A link is physical or logical and is an element or component. A physical link is a physical connection that connects components or devices, but in computer programming, a link is an instruction or address that passes control and parameters between remote parts of a program. In multiple systems, a link is a connection between two systems that can be specified by a link identifying program code that can be identified by a real or virtual address. Thus, in general, a link includes both physical and physical protocols, both logically and physically, and associated devices and programming.

MFLOPS This term refers to (10) ^** 6 floating point instructions per second.

MIMD MIMD is used to refer to the processor array architecture. Thus, each processor in the array has its own instruction stream, i.e., multiple instruction streams, one for each processing element.
Carry out a stream.

Module A module is a discrete and identifiable program unit or unit of hardware or functional unit or unit of hardware designed for use with other components. A group of PEs included in a single electronic chip is also called a module.

Node A node is generally a junction or junction of links. One PE of a general PE array can be a node. A node can also include a collection of PEs, also called a module. In this embodiment, the nodes form an array of PMEs, and the set of PMEs is called a node. Node is 8 PE
It is preferably M.

Node Array A collection of modules made up of PMEs is often referred to as a node array, which is an array of nodes made up of modules. A node array usually includes more than a few PMEs, but the term node array encompasses the plural.

PDE PDE indicates a partial differential equation.

PDE relaxation solution method The PDE relaxation solution method is a method for solving a PDE (partial differential equation). The PDE solution uses most of the known general-purpose supercomputer powers and may therefore be a good example of a relaxation process.
There are many ways to solve the PDE equation, and numerical methods greater than one include relaxation methods. For example, by the finite component method, PDE
The relaxation method consumes a large amount of computer time when solving.

Now consider an example in the world of heat conduction. If hot gas is inside the chimney and cold wind is blowing outside, how will the temperature gradient in the chimney brick be formed? By assuming each brick as a small segment and expressing the equation of how the heat flows between each segment as a function of temperature difference, the heat transfer PDE can be transformed into a finite element problem. Therefore, it is necessary to determine the start of relaxation assuming that the boundary segments are the hot gas temperature and the cold air temperature, while all the elements except the inside and outside are room temperature.

The computer program models time by updating the temperature variable for each segment based on the amount of heat entering or exiting that segment.
It then takes many cycles to process all the segments of the model until the temperature variables across the chimney are relaxed to give the actual temperature distribution that occurs in the physical chimney.

If the goal is to model the gas cooling of a chimney, the components must extend to the gas equation and the boundary conditions inside the chimney can be linked to other finite link models and processed. Or continue the process. Note that the heat flow depends on the temperature difference between the segment and its neighbors. An inter-PE communication path is used to distribute the temperature variables. This is this adjacent communication pattern, or PD
It is a property that makes the E relationship highly applicable to parallel computing.

Picket A picket is an element of an array of components that make up an array processor. Data flow (ALU R
EGS), memory, control, part of the communication matrix associated with the element. The device shows a 1 / nth array processor consisting of parallel processors and memory elements with their control and array intercommunication parts. Pickets are in the form of processor memory elements or PMEs. The PME chip design processor logic according to the present invention can implement the picket logic of the related application, with the logic for the processor array formed as nodes.

The term picket is generally similar to the array term PE for used processing elements and is a component of a processing array that processes bit parallel information bytes in one clock cycle, preferably consisting of a combination of processing elements and local memory. Is. This preferred embodiment, consisting of a byte wide data flow processor and 32 kbytes or more of memory,
Essentially controls and connects to other pickets.

The term picket is functionally a military picket.
The analogy of the line seems to fit fairly well, but its etymology comes from Tom Sawyer and his white fence.

Picket Chip A picket chip contains multiple pickets on a single silicon chip.

Picket Processor System (or Subsystem) A picket processor is an array of pickets, a communications network, an input / output (I / O) system, and a microprocessor, scan routine processor, and micro-running array. It consists of a SIMD controller.

Picket Architecture Picket Architecture is a SIMD that has the ability to adapt to a number of different types of problems, including:
2 is a preferred embodiment for the architecture. − Set associative processing − Parallel numerical centralized processing − Image-like physical array processing

Picket Array A picket array is a regular array of pickets arranged in a geometric order.

PME or processor memory element The PME is used for the processor memory element. The term PME refers to a unit that forms a single processor, memory, and input / output (I / O) capable system element or parallel array processor according to the present invention. Processor memory element is a term that encompasses pickets.
The processor memory element comprises a processor, its associated memory, a control interface, and a part of the array communication network facility, the 1 / nth processor
It is an array. This element can have a processor memory element with the normal array connectivity, such as in a picket processor or as part of a sub-array, or in a multi-processor memory element node as described herein.

Routing The routing is the designation of the physical route through which the message reaches the recipient. Routing has a source or source and a destination. These elements or addresses have a temporary relationship or affinity. Message routing is based on keys obtained by reference to a table often. In a network, the recipient may be any terminal, station, or network addressable device that is addressed as the recipient of information sent according to a routing address that identifies the link. The recipient field is placed in the message header and its recipient code identifies the recipient.

SIMD SIMD is a processor array architecture in which all processors in the array are commanded from a single instruction stream to perform multiple data streams, one per processing element.

SIMD MIMD or SIMD / MIMD This term has the dual function of being able to switch from MIMD to SIMD during the processing of certain complex instructions.
That is, it is a term indicating a machine having two modes. The Thinking Machines model CM-2 is MI
When placed as the front or rear end of an MD machine, it allows operations to perform different modes (often referred to as dual mode) to accomplish different problem parts.

These machines have existed since Illiac and used buses that interconnect the master CPU and other processors. The master control processor has the ability to interrupt the processing of other CPUs. Other CPUs can run independent program code. There must be a function that contributes to the checkpoint function during interruption (closing and saving the current state of the controlled processor).

SIMIMD This term is a processor array architecture in which all processors in the array are commanded from a single instruction stream to perform multiple data streams, one arranged per processing element. Within this structure, the data dependent operations within each picket that specify instruction performance are controlled by the SIMD instruction stream.

This is a single instruction stream machine with the sequential capability of multiple instruction streams (one per picket) to operate multiple data streams (one per picket) using the SIMD instruction stream.

SISD SISD is an acronym for single instruction, single data.

Swapping Swapping is the exchange of the data content of one storage area with the data content of another storage area.

Synchronous operation The synchronous operation of a MIMD machine is a mode of operation in which each activity is associated with an event (usually a clock). It can be a designated event that normally occurs in the program sequence. Operations are dispatched to multiple PEs to perform their functions independently. Control is not returned to the controller until the operation is complete. If there is an operation instruction on an array of functional units, the request is issued by the controller for each array element that must complete those operations until control is returned to the controller.

TERAFLOPS This term is a combination of TERA and FLOPS (described above), meaning (10) ^** 12 floating point memory per second.

VLSI VLSI is an acronym for Very Large Scale Integration when used for integrated circuits.

-Zipper A zipper is a newly added function. It allows for links to be connected from devices outside the regular interconnect of the array structure. Glossary of terms (additional) circuit switching: Data transfer method between array PMEs.
Therefore, the intermediate PME logically connects the input port to the output port so as to pass the message to the final destination through the intermediate PME without any processing in the intermediate PME.

Storage and Transfer: A method of transferring data between PMEs of an array. The intermediate PME must then receive each message and retransmit it to its final recipient.

Input transfer end interrupt: I / O message
P that occurs when a word is received with a transfer end tag
ME program context switching request.

Direct Memory Access (DMA): I
A mechanism to directly connect the / O port to a computer memory system and self-managed data transfer.

Break-in: A mechanism that puts the processor into a transparent context switch and uses the processor for data flow and control routing to self-managed data transfer functions.

Execution Time Software: Software executed by the processing elements. Operating system, executive program, application program,
Includes services and programs.

Memory Reflection: An essential feature of Dynamic RAM (DRAM) technology that suspends the use of memory while the current information is being rewritten.

Waypoint PME: A PME in a message path through a network of PMEs that is neither the originator nor recipient of the message.

Background Art In an endless quest for faster computers, hundreds and thousands of low cost microprocessors are concatenated in parallel to overcome the complex problems that plague today's machines. Has created a super computer. Such machines are called massively parallel. To create a massively parallel system, the inventor created a new method. For many of the improvements made by the inventor, many other performance backgrounds must be considered.

References were made to other applications in the Technical Summary. In this regard, the present inventors have proposed a parallel associative processor system (US Patent Application No. 601,5).
No. 94) and an advanced parallel array processor (APAP)
See the related application for. System replacement is required to select the architecture that best fits a particular application, but no single solution has been satisfactory. And the idea of the inventor made it easy to provide a solution.

[0074]

The above-mentioned prior art does not propose the use of transparent intermediate nodes in the data path, and the connection structure is not only very complicated, but also in each node. It was necessary to separate processing and communication.

Accordingly, it is an object of the present invention to provide a massively parallel computer system having the ability to pass messages through an interconnect node network of computer systems that can be used for massively parallel applications. .

[0076]

The inventor has created a new method for creating massively parallel processors and other computer systems by creating a system and a new "chip" designed according to the novel concept. did. The present application is directed to such a system. Various concepts to be disclosed in the present application and related applications can be found in those applications. The components described in each application can be combined into this system to form a new system. They can also be combined with current technology.

In the present application and related applications, we have devised a picket processor called the Enhanced Parallel Array Processor (APAP). It should be noted that the picket processor can use the PME. Picket processors may be particularly useful in military applications where a very compact array processor is desired. In that regard, this picket processor is somewhat similar to the Advanced Parallel Array Processor (APA) of this application.
It may be different from the preferred embodiment for P). However, there is commonality and certain aspects and features of this embodiment can be applied to different machines.

The term picket includes the first / nth element of an array processor consisting of a processor and memory and the communication elements contained therein, which are applicable to inter-array communication. The concept of picket is also the 1st / nth A
It is also applicable to PAP processing arrays.

The concept of picket is as follows: data width, memory
Although pickets may differ from APAP in size and number of registers, pickets are configured to be connectable to the 1 / nth regular array in the massively parallel embodiment, which is an alternative to APAP. APAP PMEs differ in that they are part of a sub-array. Both systems can perform SIMIMD, but since the picket processor is configured as a SIMD machine having PE MIMD, it can directly perform SIMIMD, while the MIMD APAP structure implements SIMD. Perform SIMIMD by using the MIMD PE controlled to simulate. Also, both machines use PME.

Both systems can be configured as parallel array processors and consist of array processing units for arrays with "N" elements interconnected with the array communication network. The 1 / Nth processor array consists of a processing element, its associated memory, a control bus interface, and part of an array communication network.

The parallel array processor has dual operation mode capability, where the processor is commanded in either or two modes and is free to move between these two modes for SIMD and MIMD operations. can do. SIM
If D is the mode of the organization, the processor is SI
If the MIMD is capable of directing each element to perform its command in the MIMD mode, and the MIMD is the implementation mode for the organization of the processor, then the processor is chosen in the array to simulate the performance of the MIMD. Has the ability to synchronize elements (this is called MIMD-SIMD).

The parallel array processors of both arrays provide an array communication network with paths for passing and passing information between the elements of the arrays. Information transfer is 2
It can be controlled in any of two ways. In the first method, the mobile data does not specify the destination and all messages are moved simultaneously and in the same direction.
Instructed by the controller. The second method is that each message has a header that defines the recipient at its start and self-routes.

An array segment of a plurality of array processors has a plurality of copies of a processing unit provided on a single semiconductor chip, each copy of the array segment expanding the array communication network. It includes a portion of an array communication network that is connected to segments and buffers, drivers, multiplexers, and controls that allow the array segment to be integrally connected to other segments of the array. A control bus or path from the controller is arranged in each processor to extend to the control functions of each element of the array and their activities.

Each processing element segment of the parallel array contains multiple copies of the processor memory element, which are contained within the limits of a single semiconductor chip, and the array segment controls the array segments contained on the chip. It includes a portion of the array control bus and register buffers to support communication of functions.

Both mesh movements or routing movements can be realized. APAP typically implements a dual interconnect structure with eight elements on one chip that are interrelated in one way, and the chips are otherwise interrelated.
Programmable routing of chips is generally described in P above.
This is done by setting a link between the MEs, but the nodes may be connected in other ways and are usually connected in other ways. On chip, the canonical APAP structure is essentially a 2x2 mesh and its node interconnects can be routed sparse octal N-cubes (3D). PE that enables the matrix to be configured with point-to-point paths in both systems
There is an interconnection path between PEs between (PME).

Further, in order to solve the above-mentioned problems, the present invention is constructed as described below. A massively parallel computer system according to the present invention has the ability to send (or transparent) messages through an interconnected network of computer systems that can be used in massively parallel operations.

It provides a mechanism for sending output messages from the main memory of each node, and a mechanism for memory, without using the node's asset processing, except for the I / O structure setup process and the use of main memory bandwidth. To have. A data path is then provided in the communication path and controls one of the input data paths of the node to be dynamically and logically connected to one of its output paths. The system uses dynamically and logically connected input and output paths without the use of node storage assets, memory bandwidth, or processing,
Pass or pass a message through a node.

A node has the ability to process memory and input data at the same time, using all of the node's memory bandwidth, but messages use memory or the path through which the processing of input data is logically connected. Pass the message through dynamically connected input and output paths unless requested. The invention then recognizes the end of the message on the logically connected input and output paths. Future input messages along the path will dynamically and logically disconnect the connected input path from the output path so that the node's processing resources and storage can be used.

[0089]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT A preferred embodiment of the present invention will now be described in detail with reference to the accompanying drawings. First, the "Parallel Associative Processor System" related to the present application (US Patent Application No. 611,5).
No. 94) will be described. It describes the idea of computer memory integration and control logic within a single chip, replication of combinations within a chip, and construction of a processor system consisting of a single chip replication. Although this method extends or enhances execution performance by reducing chip boundaries and wire lengths, it does provide a system that provides massive parallel processing capabilities at the expense of single chip type development and manufacturing. be introduced.

The above-referenced US patent application Ser. No. 611,594 describes the use of a one-dimensional I / O structure with multiple SIMD processing memory elements (PMEs) connected to that structure in a chip. The invention is characterized by extending the concept to a dimension greater than one and by elaborating it to include a complete I / O system with both data transfer and program interrupts.

The related US applications, in different respects, extend and elaborate on the earlier invention. The embodiment of the invention described below is eight SIMD / MIM per chip.
The four-dimensional I / O structure with DPME explains
It can be extended to more dimensions and more PMEs than its description.

The present invention allows external input / output from inter-processor communication.
In addition to extending the inventive concept to output functionality, it also provides the interfaces and elements needed to control the processing array. In summary, these three types of I / O are:
(B) between processors, (b) processors to (or from) the outside, and (c) broadcast communication / control.
Large-scale parallel processing systems use I / O of all these types.
It requires O bandwidth and balances processor computing power.

These requirements within the array are
, A 16-bit instruction set architecture augmented with very fast interrupt state swapping capabilities.
It can be satisfied by computer duplication.
The characteristics of PME do not exist in the processing elements of other massively parallel processors. The machine according to the invention is used for processing, routing, storing,
And I / O operations can be fully distributed. This property does not exist in any of the other designs.

Next, details will be described with reference to FIG. FIG. 1 specifically illustrates the "Extended Parallel Array Processor" (APA
P) is a block diagram of the APAP showing the main elements of one of the above-referenced US patent applications and the APAP interface to the host processor. In FIG. 1, 1
Is the host processor to which this APAP is attached,
Data and commands are issued by the program execution of this host processor. An array director application program interface (API) 3 receives and interprets these data and commands.

The API passes data and commands up to the cluster 6 via the cluster synchronizer 4 and the cluster controller 5. The cluster provides APAP memory and parallel processing. Functions provided by the cluster synchronizer and cluster controller route data and commands to the appropriate clusters,
To give a balanced load between the clusters. A more detailed description of the array director is found in the U.S. patent application entitled "Extended Parallel Processor Array Director."

A cluster consists of multiple PMEs interconnected as a modified hypercube. Each cell in the hypercube can be addressed such that the address of any cell next to it is different at any single bit position. Any cell in the ring can be addressed as two adjacent cells whose addresses differ by ± 1. The modified hypercube used for APAP combines these approaches by building the hypercube outside the ring. The intersection of the rings is defined as a node.

Next, a preferred embodiment of the present invention will be described in detail with reference to FIG. The node of the preferred embodiment illustrated in FIG. 2 is a 2n PME2 in the U.S. patent application entitled "SIMD / MIMD Processing Memory Element".
0 and broadcast communication and control interface (BCI) unit 2
It consists of 1. The PME is organized within the node as a 2xn array. The ring or dimensionality of the array that characterizes the array is represented by "n", the number of I / O ports on the chip,
Therefore, although limited by the physical chip package, n = 4 in this embodiment. Improvements in chip technology allow higher dimensions of the array within the chip as "n" increases.

6 and 7 show the evolution from PME to array. Eight PMEs are interconnected to form node 151. The eight node groups are interconnected by an X-dimensional ring (16PME) and the eight overlapping node groups are interconnected by a Y-dimensional ring 152. This is an 8x8 array of nodes (512 PM
E) form a single two-dimensional cluster with.

The clusters are combined up to an 8 × 8 array to form a four dimensional array element 153. Each group of eight nodes across the array element are interconnected in both the W and Z dimensions. The interconnection path for all single nodes in four dimensions is shown at 154. It should be noted that the array need not be either regular or right angle. A particular application or configuration can redefine the number of nodes in all or in any dimension.

Each PME exists only on one ring 26 of the node (FIG. 2). The rings are designated W, X, Y, and Z. The PMEs 20 in the chip are paired so that one moves data clockwise along the ring of nodes (i.e., + W, -W). Others move data counterclockwise externally along the ring 23, 26 of the node and connect the PME to the external port of each node. The two PMEs of each ring have their external I / O ports (+ W, -W, + X, -X, + Y, -Y, + Z,-).
Z). Within the node there are also two rings 22 interconnecting 4 + n PMEs and 4-n PMEs.

These inner rings provide a path for moving messages between outer rings. The APAP is considered a four-dimensional orthogonal array 151-154 so that the inner ring can move messages through the array in all dimensions. This allows any PME to step the message towards the destination by addressing the PME of the node's own ring or a neighboring PME within that node.

FIG. 8 is a block diagram of a transfer interface showing a circuit switching path. In FIG. 8, each PME has 4 input ports and 4 output ports (left 85, 9).
2, right 86,95, vertical 93,94, and external 80,8
1). The three input ports and three output ports provide full-duplex point-to-point connections to the other PMEs on the chip. The fourth port provides a full-duplex point-to-point connection for the off-chip PME. Due to the pin and power limitations of the physical package of this preferred embodiment, the actual I / O interface is a PME-to-PME data word 9 as illustrated in FIG.
4 bit wide paths 97, 98, 99 used to multiplex 4 nibbles of 6,100.

Each PME has its 4 input ports 80, 8
One of 5,86,93 is the main data flow of PME 8
It has an I / O circuit switching mode in which data can be directly switched to one of the four output ports 81, 92, 94, and 95 without inputting data to 7, 88, 89. The selection of the transmission source 162 and the reception destination 161 (FIG. 4) in the circuit switching is performed by the control performed by the software of the PME. The other three input ports continue to access the PME's main memory while the fourth input is switched to the output port.

The data at the PME input port can be predetermined to point to the local PME or to the PME further down the ring. PME further down the ring
Data is stored in the local PME main memory and then transferred from the local PME to the target PME (store and transfer) 84, 87, 88, 89, 90, 91. You can Or, the local input port is a local PME whose data is on the way to the target PME.
It can be logically connected to a particular local output port (circuit switch) for "transparent" passage through 84,90.

The local PME software dynamically controls whether the local PME is in store and transfer mode for either 4 inputs and 4 outputs or in circuit switching mode (170). In circuit switching mode, the PME simultaneously handles all functions except those related to circuit switching. In the store and transfer mode, the PME suspends all other processing functions and begins the I / O transfer process.

In this preferred embodiment, the PME I
The / O design offers three I / O operating modes:

1. Regular mode: 2 adjacent PMEs
Used for data transfer between. The transfer of this data is initiated by the PME software. Adjacent PME
Predetermined data for PMEs other than is the adjacent PM
After being received by E, it must transmit as if it originated from its neighbor PME. For example, +
Binary hypercube 151 data originating at W and predetermined for -X is transferred from + W to + Z.
Then it is transferred from + Z to + X. Finally,
It is transferred from + W to + Z. This process applies to both PMEs within a node and PMEs of different nodes.

2. Circuit switching mode: P for data and control
The ME can be passed across. This enables high-speed communication between PMEs that are not immediate. Above 1.
In the example, + W requests the circuit switching path for -X and sends a message to + Z. + Z forwards the message to + X and then sets the circuit switch connected to the + W input to the + X output.

+ X sets the circuit switching path connected to the + Z input to the -X output. So + W transfers the data directly to -X through + Z. FIG. 7 shows this state. In FIG. 8, + X PME connects the left (LEFT) input 85 to the vertical (VERTICAL) output 94 via multiplexer (MUX) 84, MUX 90, and demultiplexer (DEMUX) 91. + Z PME sets up a path similar to the above except that it connects the left input 85 to the right output 95.

This method or process applies equally to intra-node and inter-node transfers. Switching transfer of the circuit between nodes is performed by the output buffers in the two passing nodes.
It is slightly slower than the intra-node circuit switch transfer because it requires an additional clock cycle at each node traversed due to the need to load register 83 and input buffer register 82. However, the diameter of the network is still reduced from that for each circuit-switched PME.

3. Zipper mode: This mode is the I / O transfer mode used by the array controller to read or load data from the nodes of the cluster. Zipper mode uses standard functions and circuit switching modes to rapidly transfer data to and from an array of PMEs in a cluster card. The preferred zipper according to this embodiment is the zipper shown in the US patent application entitled "APAP I / O Zipper Connection".

In addition to the three basic modes of I / O transfer mode, normal mode, and circuit switching mode, a splitter submode is provided. When the data path is set in the regular data transfer submode, all the data is transferred from the source 162 to the single designated receiver 161 (FIG. 4). In the splitter submode, both the primary 161 and alternate 167 destinations are designated as well as the word count 168. The data word of the message is forwarded to the elementary destination until the splitter word count reaches zero. The splitter then switches to the alternate destination, transfers the next group of data words until the splitter word count reaches zero again, and then returns to the primary destination. This process continues until the entire message has been sent.

Conceptually, data is transferred from the main memory of the originating PME to the main memory of the receiving PME. In this embodiment, two locations of memory for each interface are allocated to contain the starting address of output data block 230 and the number of words contained in block 231. Besides, PME control register 1
(FIG. 4) controls the mode of data output and the receiver.

PME runtime software loads the allocated memory location to define the output data block and loads PME control register 1 to split word count 168, if present, and receiver 1
61, nodes 163 and 165, and an alternate receiver 167 to define whether the defined block has terminated the message, and the data block that the PME has terminated before continuing its runtime program 165. Specifies whether to transfer. P to perform the output operation
The ME execution time software loads the first address and count into the designated memory location. Next, the software loads the PME control register 1, and finally the software performs an output command to start the data transmission sequence.

To send each data word, the send sequence decrements the count 231 and returns the start address 23
Increment zero and read the data word from memory 41. The data word is loaded into the transmit registers 47,96 and transmitted to the selected PME 97,161. The transmission sequence enters the regular PME process and the memory 41
And cycle access to ALU 42, update I / O address and count fields, and load transmit registers 47, 96. The CX bit 165 of the PME control register 1 determines whether the PME process continues to interleave the instructions during the transmit sequence or is idle until the transmit sequence ends. This sequence continues until the count reaches zero.

Since the data transfer interface is 4 bits wide 97, each 16 bit data word 220
Are transmitted in 4-bit pieces (nibbles). Also, the tag nibble 221 and the parity nibble 222 are transmitted with the data. 223 shows a transfer format.

FIG. 11 shows the format of the transfer sequence. The sending PME of the interface issues a request 225 to the receiving PME. Upon receipt of the Acknowledgment 226, the transmitting PME may initiate data transmission and generate the next transmission sequence. The next transmission sequence will not be issued until receipt of the acknowledgment.

TC tag in PME control register 1
When bit 164 is set, TC bit 224 is set in the tag field of the last data word transferred. This bit is a bit that informs the receiving PME that the data transfer is completed.

In the normal mode, PME is L85,
Data can be received from V93, R86, and X80 interfaces. By the time the PME is able to receive data from the interface,
You must set up an input buffer in memory for that interface. Two memory locations are allocated to contain the starting address of each input data buffer 232 and the number of words contained in buffer 233. In addition, PME control register 2 includes a mask bit that is responsible for both the enabling of input interface 173 and the allowing of I / O interrupt 172.

The PME runtime software loads the allocated memory location to define the output data block and loads the PME control register 2 to enable the input data transfer. Once the input buffer is defined and enabled, the PME runtime software continues with other processing tasks and waits for I / O interrupts.

When one of the interfaces detects the request 240, the receiving PME sends a confirmation of receipt 241 and loads the data into the input register 87. There, the receive sequence begins, fetching count 233, decrementing, fetching input buffer address 232, incrementing and storing the data word in PME memory 41. The receive sequence is similar to the transmit sequence. The reception sequence enters the regular PME process, and the memory 41
And ALU 42 cycle steal access, update I / O address and count fields, and load input data word into memory 41.

The PME processor uses the PME control register 1
The instructions continue to be interleaved during the receive sequence regardless of the state of the CX bit 165 of the. This sequence is either a count reaching 0 or a TC tag is received, so that the corresponding input interrupt register bit indicates an "input buffer full" or "transfer end" interrupt code. Continue until 171 set by 190.

The PME generates an acknowledgment 226 in response to the request if the following conditions are met. 1. The input registers 87 and 100 are free. 2. The request is not barred 174. 3. Interrupt 182 is not pending for request input. 4. The request input is not switched. 5. The request input has the highest priority over any of the current requests.

The input registers 87 and 100 are used for receiving confirmation 2
From the time 26 occurs, the receive sequence is in use until the data word is stored in memory. Acknowledgment is prohibited if the input register is in use. In the busy state, overwrites to the input registers are prevented until the receive sequence occurs (because the receive sequence delays memory refresh or other PME operation).

If the TC tag bit 224 is sent from the transmit PME, the I / O interrupt latch is set 171 for that interface. No further acknowledgment 226 for that interface will occur until the interrupt latch is reset by the PME runtime software. All other interfaces are kept active. For example, if the TC tag bit 224 is set for a data transfer from the left interface 85, further requests from the left will be inhibited until the L interrupt is taken and the L interrupt latch is reset. .
Request 225 from V93, R86, X80 can be taken normally.

Since there is a single path 84,99 to the common input register 87,100, the acknowledgment 226 priority is as follows:

When the receiving PME issues an Acknowledge 226, the input multiplexers 84, 99 are set to the correct input source. At the end of the word transfer, the input registers 87,100 are locked. The input register remains locked until the receive sequence occurs and the data is transferred to the correct memory buffer. During this time, the input register is in use and all reception confirmations are prohibited.

The data word is transferred with the TC tag 224 bit set, and when the receiving PME is in normal mode, an I / O interrupt is generated 171 to the associated interface. Moreover, the buffer count goes to 0 until the TC tag is sent from the sending PME, and I / O interrupts are generated for the interface associated with the interrupt code set to reflect the overflow of the input buffer.

A legitimate process or operation is a neighbor PME.
Used for data transfer between. The PME runtime software protocol inserts information in the header of the message that indicates to the receiving PME software whether it is the final destination for the data or just the waypoint. If the PME runtime software determines that it is a waypoint, the send sequence must be set up to move the data towards its final destination.

This process is known as store and transfer.
Store and transfer moves the data to its final destination. However, this data movement uses PME memory bandwidth to incur I / O overhead for both loading and unloading the I / O buffer area at each waypoint, processing header information, and handling PMEs. CPU for initializing the transmission sequence for each message passing through
Increases processing overhead.

In the circuit switching mode, the source PME
The run-time software and final destination PME run-time software use regular processes or operations. The circuit switching mechanism is invoked by the waypoint PME runtime software in response to software protocol messages (in normal mode) sent from the originating PME through each waypoint PME to the final destination PME.

The waypoint PME cannot invoke circuit switching mode, but it does store and forward protocol and data messages. Waypoint P that remains on the receiving side of waypoint PME for storing and transferring
The ME invokes circuit switching mode when it receives the software protocol message.

The circuit switching path is dynamically controlled by the local PME runtime software. The execution time PME software determines whether the PME has already executed the circuit switch 191 and loaded the PME control register 1 shown in FIG. This circuit switching is possible with CS170,
Input source is selected by RA162, output destination is TA
161 is selected. In addition, the software may enable splitter submode 166, select an alternate receiver 167, and use splitter word count 168.

The circuit switching path is such that the PME input paths 82, 85, 86, 93 are directly output paths 83, 92, without passing through the intervening PME processing or main memory assets 87, 88, 89.
Connect to 94 and 95. This circuit switching passes through the tag 221, the data 220, and the tag 222. Waypoint PM
E monitors the tag for control tag TC224.

When the PME detects the control tag TC, it sets the appropriate interrupt request 171. Execution time PM
When the E software interrupts, it handles the required software protocol such as resetting circuit switch 170 and split 166, and alternate destination path 1
67 to send a message to the other waypoint PME
The circuit switching for is ended.

While the PME is in the circuit switching mode, it cannot initiate a data transfer because the output multiplexer MUX90 is in the circuit switching path. However, the data can be received from any input except the circuit switching input 99, and the memory 41 and the ALU4 can be received.
0, or any of the other processing functions 88 do not use the circuit switching path, so that all processing that does not require immediate data output can be performed.

For example, L85 input has 4 outputs 81, 92,
When the circuit is switched to one of 94, 95, the transfer of input data can be received from the V93, R86, or X80 input. The transfer of these input data causes a sequence of loading the input data from the receiving sequencer to the PME memory. Moreover, the calculation process in the PME is continued while the circuit switching mode is enabled.

The advantage of circuit switching for the source and destination PMEs is that the delay time associated with waypoint PMEs that store, process and retransmit data messages can be eliminated. This is because the communication diameter of the array can be effectively reduced by eliminating the delay time for each waypoint PME operating in circuit switching mode.

The advantage of circuit switching over the waypoint PME is that it stores the data passing through the waypoint PME,
It means that the I / O of the waypoint PME does not use the memory bandwidth because of the retransmission. Also, the intermediate point PM
E runtime software does not have the overhead required to retransmit a data message. The essential effect of circuit switching lies in the higher processing bandwidth for the waypoint PME and the shorter communication diameter for the source and destination PMEs.

Although the preferred embodiment of the present invention has been described in detail above, it is obvious that the present invention is not limited to this, and can be further improved, changed and expanded within the scope of the present invention in the present and future. .

[0141]

The present invention is constructed as described above and dynamically connects messages to pass through the input and output paths and the full memory bandwidth of the node unless memory and input data require it. By providing a function for simultaneously processing a memory and input data using a parallel processor, it is possible to provide a multi-processor parallel computer system capable of rapidly transferring an I / O message between parallel processors and processing elements. it can.

[Brief description of drawings]

FIG. 1 is a functional block diagram of a typical APAP showing, among other things, the main elements of an enhanced parallel array processor APAP and the APAP interface to a host processor.

FIG. 2 is a functional block diagram of an embodiment of a processing memory element node according to the present invention, showing in particular the interconnection of the various elements making up such a node.

FIG. 3 is a block diagram illustrating a data flow according to an embodiment of a processing memory element (PME), with a basic portion of the data flow including main memory, general purpose registers, ALUs and registers, and a portion of an interconnection mesh.

FIG. 4 is a block diagram illustrating a PME control register that supports the implementation of interrupt and interconnect networks.

FIG. 5 is a block diagram showing PME status register and interrupt level priority assignment.

FIG. 6 is a block diagram illustrating a modified binary hypercube.

FIG. 7 is a block diagram illustrating a modified binary hypercube.

FIG. 8 is a data flow diagram of a transfer interface showing a circuit switching path.

FIG. 9 is a block diagram illustrating PE I / O data flow and tying to an interconnection network.

FIG. 10 is a block diagram illustrating tags, parity, and data words transferred between PME I / Os.

FIG. 11 is a block diagram illustrating an output interface ordered between PME I / Os.

FIG. 12 is a block diagram illustrating an input interface ordered among PME I / Os.

FIG. 13 is a configuration diagram showing reserved storage locations for interrupt and I / O processing.

[Explanation of symbols]

 1 Host Processor 2 Host Memory 3 Application Processor Interface 4 Cluster Synchronizer 5 Cluster Controller 6 Cluster 20 Processing Memory Element (PME) 21 Broadcast and Control Interface (BCI) 41 Main Memory 42 ALU 47 Transmission Register

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Mitchell Charles Dapp United States 13760, New York, Endwell, Ivon Avenue, 1130 (72) Inventor James Warren Defenderfa United States 13827, Ogo, New York , Front Street, 396 (72) Inventor Donald Mitchell Resmista United States 13850, New York, Vestal, Collins Hill Road, 108 Aye (72) Inventor Richard Edward Nieer United States 13732, New York, Appalachin, Forest Hill Road, Address 109 (72) Inventor Eric Eugene Letter United States of America 18 851, Pennsylvania, Warren Center, Box 29, Box 34, H.C. 34 (72) Inventor Robert Least Richardson United States 13850, New York, Vestal, Box 81, Marson Rod, Earl. Dee. # 2 (No Address) (72) Inventor Vincent Joan Smallal 812, Skirain Terrace, Endwell, Endwell, New York, USA 13760

Claims (10)

[Claims] 1. A message passing device for passing a message through a network including nodes connected to each other, wherein an input message is stored in a main memory of each node, and
Except for the setup process of the O structure and the use of main memory bandwidth, it provides a means to send output messages from each node's main memory without using the node's processing assets and one of the node's input data paths A means to dynamically and logically connect to one of its output paths and to use the input and output paths that are dynamically and logically connected without using the processing, memory bandwidth or storage assets of the node. Means for passing messages through the node, and as long as the process does not require the use of memory or input data logically connected paths, through the dynamically connected input and output paths. A means by which a node can simultaneously process memory and input data using the full node memory bandwidth while a message is passing, and logically connected inputs and outputs. Means for recognizing the end of a message in the input path, and means for dynamically and logically disconnecting the connected input path from the output path along the path so that future incoming messages will use the node's storage and processing assets. A message passing device comprising: 2. The message passing device according to claim 1, wherein the logical connection of the input path to the output path reduces the network communication diameter by 1 for each node of such a configuration. 3. The message passing device is further configured such that the first n-word message is passed to R and the next n-word is S.
R, S, so that the next n words pass through T, the next n words pass through U, and the next n words pass through R.
2. The message passing device according to claim 1, further comprising means for substituting an output route among a plurality of closest routes such as T and U. 4. The node is a processing memory element (PM).
The message passing device according to claim 1, which is E). 5. A plurality of multi-processing memory elements (PMEs) comprising means for internal data flow and control, means for data and control communication, a significant amount of local storage, and circuit switching modes and storage and transfer modes. ), The PME to PME communication network passing data and distributing control among the multi-processing memory elements. 6. The computer system further comprises:
6. The computer of claim 5, including means for dynamically switching within the processing memory element between SIMD and MIMD operation modes for storage and transfer / circuit switching functions that enable transfer of messages and data. ·system. 7. The memory of each said processing memory element comprises:
When blocking is not occurring, a circuit switching mode is provided to provide either a targeted message in the processing memory element or a message moved in the store and transfer mode, and a specific processing memory element directly to the requested output port. The computer system of claim 5, providing a data recipient for messages that are not targeted to be sent. 8. The memory of each processing memory element comprises:
When blocking is not occurring, a circuit switching mode is provided to provide either a targeted message in the processing memory element or a message moved in the store and transfer mode, and a specific processing memory element directly to the requested output port. Provide a data destination for untargeted messages to be transmitted, and software control of the processing memory element is a path for the selected transmission mode by dynamically selecting a circuit switching mode and a storage and transfer mode. 6. The computer system according to claim 5, wherein execution of designation and determination is controlled. 9. The processing memory element is a direct memory
A clock that supports addressing and communication of dynamic selection between circuit switching mode and store and transfer mode, and the data present in circuits switched to internal output ports allows for single cycle data transfer. 6. The computer system according to claim 5, wherein the computer system is adapted to detect the occurrence of a chip crossing by transferring the data in a chip regardless of the above. 10. The processing memory element supports direct memory addressing and communication of dynamic selection between circuit switching mode and storage and transfer mode, data transfer operating in transparent mode, and direct memory. To use forward and backward data paths for all to provide means to probe through several stages to detect acknowledgments from processing memory elements performing addressing and off-chip transfers The computer system according to claim 5, characterized in that