US3582899A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for routing data among processing elements of an array computer
Assignee: Unisys Corp
•
Filing: 1968-03-21
•
Granted: 1971-06-01
•
Expires: 1988-03-21
Abstract
Abstract An interconnection scheme for routing data word information among the processing elements of an array computer is described wherein the word length is larger than, equal to, or smaller than the number of processing elements in the array. When the word length is equal to the number of processing elements, each processing element first transmits all but one of the bits of the word stored in its routing register to the corresponding bit positions of the routing register of the correspondingly numbered processing elements, one bit per processing element. Next the contents of the routing registers of all the processing elements are shifted by the routing amount. In the last step, the first step is repeated. In situations in which the word length is smaller than the number of processing elements hardware is added to some of the processing elements or the processing elements may be grouped into a plurality of subarrays. If the word length is larger than the number of processing elements the bits are grouped so that the number of groups is equal to the number of processing elements.
Inventors
- 👤 Carl F Semmelhaack
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 13:07
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17381
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
280 words
Apparatus for routing M-bit words among processing elements of a processing element array, said array being composed of a plurality of subarrays, said subarrays each having a number of processing elements M, where each processing element of a subarray is coupled to correspondingly numbered processing elements in the other subarrays, said apparatus comprising: register means within each of the processing elements for storing the word to be routed to another processing element and for then storing the word received from another processing element during a route, said register means in at least M of said processing elements, in each subarray, being at least as long as the number of processing elements in the subarray, means for transferring the words that cross to the next higher or lower number subarray during a routing operation to the register means of the corresponding processing element in the transferee subarray in the case of a negative route, and to the register means of the processing element which is the corresponding distance from the end of the transferee subarray in the case of a positive route, means for transferring, within said subarrays, all but one of the bits from a processing element''s register means to receiving bit positions in the other processing elements''register means in the corresponding subarray, each of said receiving bit positions having a significance in the receiving register means corresponding to the number in the processing element subarray of the transferor processing element, and means within M of said processing elements in each subarray for shifting, subsequent to a transfer, the bits in each register means by an amount corresponding to the processing element, to which, said bits are to be routed.
Claim 2
Dependent Claim
280 words
Apparatus for routing M-bit words among processing elements of a processing element array, said array being composed of a plurality of subarrays, said subarrays each having a number of processing elements M, where each processing element of a subarray is coupled to correspondingly numbered processing elements in the other subarrays, said apparatus comprising: register means within each of the processing elements for storing the word to be routed to another processing element and for then storing the word received from another processing element during a route, said register means in at least M of said processing elements, in each subarray, being at least as long as the number of processing elements in the subarray, means for transferring the words that cross to the next higher or lower number subarray during a routing operation to the register means of the corresponding processing element in the transferee subarray in the case of a negative route, and to the register means of the processing element which is the corresponding distance from the end of the transferee subarray in the case of a positive route, means for transferring, within said subarrays, all but one of the bits from a processing element''s register means to receiving bit positions in the other processing elements''register means in the corresponding subarray, each of said receiving bit positions having a significance in the receiving register means corresponding to the number in the processing element subarray of the transferor processing element, and means within M of said processing elements in each subarray for shifting, subsequent to a transfer, the bits in each register means by an amount corresponding to the processing element, to which, said bits are to be routed.
Claim 3
Dependent Claim
161 words
Apparatus for routing M-bit words among processing elements of an N processing element array where M N comprising: register means in each of said processing elements for storing words to be routed to another processing element and then for storing the word received from another processing element during a routing operation, means for transferring all groups of bits, except one group, from each of the processing elements'' register means to receiving group positions in the other processing elements'' register means, each of said receiving group positions having a significance in the receiving register means corresponding to the number in the processing element array of the transferor processiNg element, and means within said processing elements for shifting, subsequent to a transfer, the bits in said register means by a multiple of N times an amount corresponding to the processing element, to which, said bits are to be routed, said multiple being equal to the number of bits in each of said groups.
Claim 4
Dependent Claim
161 words
Apparatus for routing M-bit words among processing elements of an N processing element array where M N comprising: register means in each of said processing elements for storing words to be routed to another processing element and then for storing the word received from another processing element during a routing operation, means for transferring all groups of bits, except one group, from each of the processing elements'' register means to receiving group positions in the other processing elements'' register means, each of said receiving group positions having a significance in the receiving register means corresponding to the number in the processing element array of the transferor processiNg element, and means within said processing elements for shifting, subsequent to a transfer, the bits in said register means by a multiple of N times an amount corresponding to the processing element, to which, said bits are to be routed, said multiple being equal to the number of bits in each of said groups.
Claim 5
Independent Claim
240 words
A method for routing M-bit words from register means in each processing element of a processing element array, by a selected uniform number of processing elements to the register means of a higher or lower numbered processing element in the array, said array being composed of a plurality of subarrays, said subarrays each having a number of processing elements M where each processing element of a subarray is coupled to correspondingly numbered processing elements in the other subarrays, said method, comprising the steps of: transferring the words that cross to the next higher or lower numbered subarray during the routing operation to the register means of the corresponding processing element in the transferee subarray in the case of a negative route, and to the register means of the processing element which is the corresponding distance from the end of the transferee subarray in the case of a positive route, transferring, within said subarrays, all but one of the bits from a processing element''s register means to receiving bit positions in the other processing elements'' register means in the corresponding subarray, each of said receiving bit positions having a significance in the receiving register means corresponding to the number in the processing element subarray of the transferor processing element, subsequently shifting the bits of each register means by an amount corresponding to the processing element, to which, said bits are to be routed, and repeating the second step of the method.
Claim 6
Independent Claim
240 words
A method for routing M-bit words from register means in each processing element of a processing element array, by a selected uniform number of processing elements to the register means of a higher or lower numbered processing element in the array, said array being composed of a plurality of subarrays, said subarrays each having a number of processing elements M where each processing element of a subarray is coupled to correspondingly numbered processing elements in the other subarrays, said method, comprising the steps of: transferring the words that cross to the next higher or lower numbered subarray during the routing operation to the register means of the corresponding processing element in the transferee subarray in the case of a negative route, and to the register means of the processing element which is the corresponding distance from the end of the transferee subarray in the case of a positive route, transferring, within said subarrays, all but one of the bits from a processing element''s register means to receiving bit positions in the other processing elements'' register means in the corresponding subarray, each of said receiving bit positions having a significance in the receiving register means corresponding to the number in the processing element subarray of the transferor processing element, subsequently shifting the bits of each register means by an amount corresponding to the processing element, to which, said bits are to be routed, and repeating the second step of the method.
References Cited (Backward Citations)
US3228005A
Cited
US3374468A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1974-05-31 | 1974-11-30 | 1975-06-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1978-05-31 | 1978-11-30 | 1979-06-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1982-05-31 | 1982-11-30 | 1983-06-01 | $7700.00 | Window Closed / Lapsed |