Bidirectional systolic ring network
First Claim
1. A parallel processor interconnection and communication apparatus comprising a plurality of nodes, at least one of which is provided with a processing element, and a local memory element, for program and data storage, together with:
- A. a first means providing a ring-structured interconnect, supporting synchronous, bidirectional, point-to-point transfers, between adjacent said nodes, comprising;
a bidirectional, pipelined data bus;
a bidirectional, pipelined selection bus;
a direction-indicating signal; and
a clock signal defining clock events for synchronous elements;
C. a second means, provided to each of said nodes, for determining, at each such said clock event, on the basis of the selection value presented in said selection bus, whether one of several node selection varieties is signalled, wherein such said value does not uniquely select a particular node but rather signals selection of two or more nodes, and wherein different varieties of selection are permitted among such selected nodes;
D. a third means, provided to at least one of said nodes, for responding to a first such said selection variety as a transmitter, by injecting a datum into said data bus, in the direction specified by said bussed direction-indicating signal, by inhibiting, and effectively overwriting, a datum forwarded via said data bus, wherein said injected datum is obtained by reading said local memory element;
E. a fourth means, provided to at least one of said nodes, for responding to a second such said node selection variety as a receiver, by sampling a datum from said data bus and writing it into said local memory element;
F. a fifth means, provided to a specialized controller node, for injecting a repeating sequence of values into said selection bus, at successive said clock events, proceeding in the direction determined by said direction-indicating signal;
wherein, with each particular value within said repeating sequence of selection values there is associated;
i. a transmitting subset of said plurality of nodes, such that each member node responds to said particular value as an instance of said first such said selection variety of said second means;
ii. a receiving subset of said plurality of nodes, positioned in an interleaved manner among the nodes of said transmitting subset, so that each node in said receiving subset is paired with a node in said transmitting subset and situated so as to be able to receive its transmissions, wherein each member node of said receiving subset responds to said particular value as an instance of said second such said selection variety of said second means;
thus inducing data transfers of a concurrent pipelined nature, that is to say systolic data transfers, within said data bus, and in the direction determined by said direction-indicating signal, between said paired nodes.
0 Assignments
0 Petitions
Accused Products
Abstract
A ring-structured network allowing bidirectional, point-to-point, communications between a plurality of nodes (200A-E), some of them equipped with a computing element (210) and a local memory element (221), and others, possibly, serving as input/output devices. In addition to clocks and miscellaneous signals, the network is divided cross-sectionally into two pipelined busses, or pipes: one (995A-B) to signal node selection, and another (996A-B) to convey data. Values, termed tags, sent over the selection pipe are interpreted, as they arrive, at the nodes, by means of lookup tables. Several varieties of selection can be represented in these tables, some, e.g., signalling read or write transfers between the data pipe and local memory element (221). Other varieties may signal the loading of local memory address pointers (223, 224, or 225) from the data pipe. Tags are generated by a specialized node (100), which thus serves as a traffic controller. A key feature of this network is that individual tags may signal selection of a plurality of nodes, some perhaps for reading, and others possibly for writing. In this way, concurrent transfers between multiple pairs of nodes are induced on the network, in a systolic manner. Such transfers can be organized to effect a variety of statically-routed communications, including those between adjacent partitions in embedded two-dimensional rectilinear and hexagonal grids. Extensions to support dynamically-routed communications are also disclosed.
-
Citations
17 Claims
-
1. A parallel processor interconnection and communication apparatus comprising a plurality of nodes, at least one of which is provided with a processing element, and a local memory element, for program and data storage, together with:
-
A. a first means providing a ring-structured interconnect, supporting synchronous, bidirectional, point-to-point transfers, between adjacent said nodes, comprising;
a bidirectional, pipelined data bus;
a bidirectional, pipelined selection bus;
a direction-indicating signal; and
a clock signal defining clock events for synchronous elements;C. a second means, provided to each of said nodes, for determining, at each such said clock event, on the basis of the selection value presented in said selection bus, whether one of several node selection varieties is signalled, wherein such said value does not uniquely select a particular node but rather signals selection of two or more nodes, and wherein different varieties of selection are permitted among such selected nodes; D. a third means, provided to at least one of said nodes, for responding to a first such said selection variety as a transmitter, by injecting a datum into said data bus, in the direction specified by said bussed direction-indicating signal, by inhibiting, and effectively overwriting, a datum forwarded via said data bus, wherein said injected datum is obtained by reading said local memory element; E. a fourth means, provided to at least one of said nodes, for responding to a second such said node selection variety as a receiver, by sampling a datum from said data bus and writing it into said local memory element; F. a fifth means, provided to a specialized controller node, for injecting a repeating sequence of values into said selection bus, at successive said clock events, proceeding in the direction determined by said direction-indicating signal; wherein, with each particular value within said repeating sequence of selection values there is associated; i. a transmitting subset of said plurality of nodes, such that each member node responds to said particular value as an instance of said first such said selection variety of said second means; ii. a receiving subset of said plurality of nodes, positioned in an interleaved manner among the nodes of said transmitting subset, so that each node in said receiving subset is paired with a node in said transmitting subset and situated so as to be able to receive its transmissions, wherein each member node of said receiving subset responds to said particular value as an instance of said second such said selection variety of said second means; thus inducing data transfers of a concurrent pipelined nature, that is to say systolic data transfers, within said data bus, and in the direction determined by said direction-indicating signal, between said paired nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
Specification