Arrays of machines such as computers
First Claim
1. A set of at least five data handling machines in which each machine has means for communicating with respect to the other machines of the set, said set having means including a system of one-way inter-machine communication channels interconnecting the machines in the set so that any machine in the set may communicate with any other machine in the set, each inter-machine communication channel extending between a single pair of machines of the set and permitting a data transmitting machine at one end of the channel to communicate data directly to a data receiving machine at the opposite end of that channel, a root machine of the set being connected only to each of a first subset of machines of the set for direct communication therewith by corresponding outgoing inter-machine communication channels of the system, each machine of the first subset being connected only to machines of a second subset of machines of the set for direct communication therewith by corresponding outgoing inter-machine communication channels of the system, with the number of outgoing inter-machine communication channels from each machine of the first subset being equal to the number of outgoing inter-machine communication channels from the root machine, the machines of the second subset also being connected to machines of the set by outgoing inter-machine communication channels of the system, each of said subsets including at least two machines, the maximum number of inter-machine communication channels required for any machine in the set to communicate with any other machine of the set being equal to the maximum number of inter-machine communication channels required for communication between the root machine and a machine of the set that is most distant therefrom, the number of outgoing inter-machine communication channels from each machine being substantially smaller than the total number of machines in the set, each machine of the set having connected thereto as inputs outgoing inter-machine communication channels from other machines of the set so that each machine of the set may communicate with certain machines of the set directly and with the remaining machines of the set only via intermediate machines.
0 Assignments
0 Petitions
Accused Products
Abstract
Improved parallel-processor computer systems and improved data transfer systems incorporating novel networks for inter-machine communication. In a first type of communication system, tree wiring is employed in which the maximum number of outgoing inter-machine communication channels required for any machine of a set of data handling machines to communicate with any other machine of the set is equal to the maximum number of such channels required for communication between a root machine of the set and a machine of the set that is most distant therefrom. Optimum numbers of outgoing inter-machine communication channels for large sets are disclosed. In a second type of communication system, plateau distributed logarithmic wiring is employed. The machines are arranged in multi-dimensional arrays, with each array having sub-arrays and with each machine of each sub-array connected to the other machines of that sub-array and to the corresponding machine of each of the other sub-arrays for each of the dimensional directions. Optimum array side lengths are disclosed.
103 Citations
29 Claims
- 1. A set of at least five data handling machines in which each machine has means for communicating with respect to the other machines of the set, said set having means including a system of one-way inter-machine communication channels interconnecting the machines in the set so that any machine in the set may communicate with any other machine in the set, each inter-machine communication channel extending between a single pair of machines of the set and permitting a data transmitting machine at one end of the channel to communicate data directly to a data receiving machine at the opposite end of that channel, a root machine of the set being connected only to each of a first subset of machines of the set for direct communication therewith by corresponding outgoing inter-machine communication channels of the system, each machine of the first subset being connected only to machines of a second subset of machines of the set for direct communication therewith by corresponding outgoing inter-machine communication channels of the system, with the number of outgoing inter-machine communication channels from each machine of the first subset being equal to the number of outgoing inter-machine communication channels from the root machine, the machines of the second subset also being connected to machines of the set by outgoing inter-machine communication channels of the system, each of said subsets including at least two machines, the maximum number of inter-machine communication channels required for any machine in the set to communicate with any other machine of the set being equal to the maximum number of inter-machine communication channels required for communication between the root machine and a machine of the set that is most distant therefrom, the number of outgoing inter-machine communication channels from each machine being substantially smaller than the total number of machines in the set, each machine of the set having connected thereto as inputs outgoing inter-machine communication channels from other machines of the set so that each machine of the set may communicate with certain machines of the set directly and with the remaining machines of the set only via intermediate machines.
-
10. A set of data handling machines in accordance with calim 1, wherein the number of outgoing inter-machine communication channels from each machine is the same as that for every other machine in the set and wherein any machine in the set may serve as the root machine.
- 11. A multi-dimensional system of data handling machines, said system comprising at least one two-dimensional array of said machines, each machine of the array having means for communicating with respect to the other machines of the array, the array including at least sixteen machines arranged in at least four sub-arrays, each sub-array having at least four machines, each machine of each sub-array being connected by a separate inter-machine communication channel to each of the other machines of that sub-array and by a separate inter-machine communication channel to a corresponding machine of each of the other sub-arrays, said channels and said communicating means constituting a communication network in which a data transmitting machine at one end of any inter-machine communication channel may communicate data to a data receiving machine at the opposite end of that channel, the total number of inter-machine communication channels in the array being approximately equal to the sum of all of the previously recited intermachine communication channels, whereby each machine of the array may communicate with certain machines of the array directly and with the remaining machines of the array only via intermediate machines.
Specification