Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
2000-08-29
2002-04-02
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S014000, C712S016000, C712S017000, C712S020000, C712S021000, C712S022000, C710S120000, C710S120000, C710S120000
Reexamination Certificate
active
06366997
ABSTRACT:
FIELD OF INVENTION
The present invention relates generally to improvements to manifold array (“ManArray”) processing, and more particularly to processing element (PE)-PE switch control to effect different communication patterns or to achieve various processing effects such as an array transpose, hypercomplement operation or the like.
BACKGROUND OF INVENTION
The ManArray processor or architecture consists generally of a topology of Processing Elements (PEs) and a controller Sequence Processor (SP) which dispatches instructions to the PEs, i.e. a single instruction stream, to effect parallel multiple data operations in the array of PEs. In addition, the ManArray is a scalable array that uses unique PE labels and scalable decoding and control logic to achieve a set of useful communication patterns, lower latency of communications, and lower switch and bus implementation costs than other approaches which support the same or similar set of communication patterns.
In more detail, the ManArray organization of PEs contains a cluster switch external to groups of PEs (PE Clusters) that is made up of a set of multiplexers which provide the North, South, East, West, hypercube, as well as non-traditional transpose and hypercomplement communications and other paths between different PEs. During program execution, it is desirable to control the multiplexer paths of the ManArray collectively referred to as the switching network or switch to achieve desirable processing effects such as an array transpose or hypercomplement. Since the ManArray organization supports virtual PE identities or labels, multiple organizations of PEs, such as torus and hypercube, and their associated connectivity patterns can be easily obtained. In addition, to support Synchronous MIMD operations, where PEs can independently execute different instructions in synchronism, the Receive Model for communications is used. The Receive Model specifies that the input data path to a PE is controlled by that PE, while the data output from a PE is made available to the network cluster switch or multiplexers. There is a distinct difference between the concept of sending data to a neighboring PE and the concept of receiving data from a neighboring PE. The difference is how the paths between the PEs are controlled and the operations that are possible without hazards occurring. The ManArray supports computational autonomy in its Processing Elements (PEs), as described in Provisional Application Serial No. 60/064,619 entitled Methods and Apparatus for Efficient Synchronous MIMD VLIW Communications. In the Receive Model, each PE controls the multiplexers that select the data paths from PEs within its own cluster of PEs and from orthogonal clusters of PEs. Since the PE controls the multiplexers associated with the path it selects to receive data from, there can be no communications hazard. Alternatively, in the Send Model, communications hazards can occur since multiple PEs can target the same PE for sending data to. With Synchronous MIMD VLIW communications, the PEs are programmed to cooperate in receiving and making data available. The ManArray Receive Model specifies the data each PE is to make available at the multiplexer inputs within its cluster of PEs. Cooperating PEs are a pair of PEs that have operations defined between them. In addition, multiple sets of cooperating PEs can have Receive Instructions in operation at the same time. The source PE of a cooperating pair makes the instruction-specified-data available, and the target PE of the pair provides the proper multiplexer control to receive the specified-data made available by the cooperating PE. For some PE to PE communications, a partner PE is required. A partner PE is an intermediary PE that provides the connecting link between two cooperating PEs located in two clusters of PEs.
SUMMARY OF THE INVENTION
One problem addressed by the present invention may be stated as follows. Given an array of Processing Elements (PEs), a set of connectivity patterns, and PE labelings associated with different organizations of PEs in the array, how do you logically control the communication operations between PEs with an efficient programming mechanism that minimizes the latency of communications and results in a simple control apparatus? The solution to this problem should desirably support single-cycle register-to-register communications, Synchronous Multiple Instruction Multiple Data stream (synchronous-MIMD) operations, PE broadcast, and classical Single Instruction Multiple Data stream (SIMD) communication patterns such as North, South, East, West, hypercube, as well as non-traditional transpose and hypercomplement communications among others.
The present invention provides novel solutions to this problem by using the ManArray methods and apparatus for PE-PE switch control as described further below. In addition, the present invention provides a variety of novel multiplexer control arrangements as also discussed in greater detail below.
Each ManArray PE is preferably defined as requiring only a single transmit/receive port independent of the implemented topology requirements. For example, the 4-neighborhood torus topology is typically implemented with each PE having four ports, one for each neighborhood direction, while the ManArray requires only a single port per PE. In the ManArray organization of PEs, when a communication operation is desired, the programmer encodes a communication instruction with the information necessary to specify the communication operation that is to occur. For example, the source and destination registers as well as the type of operation (register swap operations between pairs of PEs, transpose, Hypercomplement, etc.) are encoded in the communication instruction. This instruction is then dispatched by the SP controller to the PEs. In the PEs, the transformation of ManArray communication instruction encoding to cluster switch multiplexer controls is dependent upon the specific PE label, the type of communication model that is used, and the ManArray multiplexer switch design. By controlling the multiplexers that route the data, it is possible to effect different communication topologies. One of the novel capabilities with this control mechanism is the ability of PEs to broadcast to other PEs in the topology. The PE broadcast capability becomes feasible using the communication network of cluster switches/multiplexers without requiring any additional buses. In the ManArray, the PE broadcast can suitably be a SIMD instruction since all PEs receive the same instruction and they all control their cluster switch multiplexers appropriately to select a single specified PE path for data to be received from.
Specifically, communication occurs between processing elements which are connected in a regular topology consisting of a hierarchy of clusters. A cluster consists of one or more processing elements (PEs) which have at least one bidirectional communication path. Multiple clusters may be grouped to form a cluster at the next level of the hierarchy. In the ManArray, the beginning cluster is a 2×2 array although larger and smaller number of PEs in a cluster are not precluded. The PEs are connected with cluster switch multiplexers.
These cluster switch multiplexers are controlled by an apparatus that transforms two inputs into the output multiplexer control bits. The first input is the set of encoded bits received from a communication instruction that describe the communication pattern desired. The second input is the identity of the PE. The problem is to determine how to advantageously control these multiplexers or switching network. Four transformation methods are discussed.
Register Mode Control Method
A register method in accordance with the present invention provides a simple hardware implementation for controlling the cluster switch multiplexers. In this transformation apparatus, the first input is the set of encoded bits received from a communication instruction that describes the communication pattern desired. The second identity-of-the-PE input is no
Barry Edwin F.
Drabenstott Thomas L.
Morris Grayson
Pechanek Gerald G.
Pitsianis Nikos P.
BOPS, Inc.
Pan Daniel H.
Priest & Goldstein PLLC
LandOfFree
Methods and apparatus for manarray PE-PE switch control does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for manarray PE-PE switch control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for manarray PE-PE switch control will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2848442