# Patent

## Title
System and method for establishing sufficient virtual channel performance in a parallel computing network

## Abstract

A method for interconnecting multiple computational devices in a parallel computing network including a plurality of serially associated pairs of nodes, wherein each of the pairs of nodes is interconnected via at least one physical communication channel. A sufficient virtual channel rate required to provide a predetermined amount of Amdahl scaling is first determined. The maximum number of virtual channels, each having a transmission rate at least equal to the sufficient virtual channel rate, that can be implemented over each physical communication channel is then determined. The physical communication channel between each of the nodes is then subdivided into the determined maximum number of virtual channels.

## Background
RELATED APPLICATIONS
The present application claims priority to U.S. Provisional Application Ser. No. 61/165,301 filed Mar. 31, 2009, and U.S. Provisional Application Ser. No. 61/166,630, filed Apr. 3, 2009, contents of both of which are hereby incorporated by reference, including their appendices.
This application is also a continuation-in-part of U.S. patent application Ser. No. 12/197,881, filed Aug. 25, 2008, now U.S. Pat. No. 7,730,121, which is a divisional application of U.S. patent application Ser. No. 10/340,524, filed Jan. 10, 2003 (now U.S. Pat. No. 7,418,470), which claims priority to U.S. Patent Application 60/347,325, filed Jan. 10, 2002 and is a continuation-in-part of U.S. patent application Ser. No. 09/603,020, filed on Jun. 26, 2000 (now U.S. Pat. No. 6,857,004), all of which are incorporated herein by reference.


BACKGROUND
As first shown by Dr. Gene Amdahl in his 1967 paper “Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities” connecting together multiple parallel processing computational devices has long been a problem for the High Performance Computer community. To solve this problem the industry has introduced faster and faster communication channels and connection models. However, communication speed, otherwise known as bandwidth, represents only part of the communication/system-scaling problem. In parallel processing there are five components: the processing time for the algorithmically relevant portions of some computer program, the processing time for non-algorithmically relevant portions of some computer program (computational overhead), data transmission bandwidth, the transmission of non-required/redundant data, and data transmission latency. If there is no non-required/redundant data transmitted, the total processing time (algorithmically relevant and irrelevant processing time) and bandwidth are fixed then the overhead of data transmission latency time still remains.
SUMMARY
The presently described method of ‘sufficient channel performance’ directly addresses latency issues and provides improved efficiency in parallel processing networks. A system and method is described for interconnecting multiple computational devices in a parallel computing network including a plurality of serially associated pairs of nodes, wherein each of the pairs of nodes is interconnected via at least one physical communication channel. A ‘sufficient virtual channel rate’ required to provide a predetermined amount of Amdahl scaling is first determined. The maximum number of virtual channels, each having a transmission rate at least equal to the sufficient virtual channel rate, that can be implemented over each physical communication channel is then determined. The physical communication channel between each of the nodes is then subdivided into the determined maximum number of virtual channels.



BRIEF DESCRIPTION OF THE DRAWINGS
FIGS. 1A and 1B are diagrams showing two examples of channel use in the prior art;
FIG. 2A is an exemplary diagram showing a Howard Cascade structure using a single virtual channel;
FIG. 2B is an exemplary diagram showing a Howard Cascade structure using dual virtual channels;
FIG. 3 is a diagram showing an exemplary parallel processing system;
FIG. 4 is a diagram showing an exemplary multi-level single sufficient virtual channel type I Howard Cascade;
FIG. 5 is a diagram showing an exemplary multi-level duo-sufficient virtual channel type I Howard Cascade; and
FIG. 6 is a diagram showing exemplary steps performed in interconnecting multiple computational devices in a parallel computing network.



DETAILED DESCRIPTION
Sufficient Communication Channel Rate
Given a pair of computational elements working on the same problem in parallel such that they must communicate some data to one another before they can complete their respective portion of the problem, if that pair is connected via a communication channel and if the required Amdahl scaling between that pair is some selected multiplier of the average pair performance, then a sufficient communication channel rate accomplishes this scaling.
This ‘sufficient channel performance’ concept dictates that rather than continuously increasing channel speed (as is the normal case in the industry) there needs only to be sufficient channel performance to provide Amdahl scaling between pair-wise connected nodes. Thus, rather than looking at Amdahl's law as indicating serial versus parallel performance, it is employed in the present method/system to determine a pair-wise performance. This is the inverse of how things are presently done in the industry.
Since the present method is concerned with virtual, as opposed to physical, communication channels, the virtual channel performance can be manipulated such that it provides only enough performance for a particular need. Therefore, the rest of the physical channel capacity can be used to generate other virtual channels that may be used by other algorithms. Data transmission performance is thus considered sufficient if a particular required Amdahl multiplier value S is met for the linked computational elements over some parallel algorithm X.

Amdahl's law: Sp(X)=((1−f)+fp−1)−1 

Where f=Percent of the time spent acting in parallel,
p=number of computational elements, and
Sp(X)=Multiplier effect for ‘p’ computational elements over algorithm X.
If a 1.9 Amdahl speedup for a pair of computational elements is required, then:

S2(X)≧1.90f≅0.95

Thus, the maximum amount of time allowed for all serial operations, including exposed data transmission time and latency, is given by:

fs=1−f=0.05 or 5%

If “f” represents the acceptable parallel activity of a sufficiently performing computational pair then “(1−f)/n” represents the acceptable serial activity of “n” serialized, sufficiently performing computational pairs of nodes. This changes the example to the following:
If a 1.9 Amdahl speedup for three (working in pairs) serialized computational elements is required then:

S3(X)≧1.90f≅0.975

Thus, fs=0.025 or 2.5%,

which means that the Amdahl scaling is maintained even with an efficiency of only 97.5% when the industry might require a much more difficult to obtain (and thus more expensive) 99% efficiency to obtain the same results.

The method of the present concept means that only the maximum number of serially associated pairs of nodes (within a data exchange) need be calculated and the channel speed sufficiency over just those pairs ensures that the exchange will scale, regardless of how many other nodes are part of the exchange. For the purpose of the present description, a node may be any computational device, such as a server, a processor, a processor core, or a cluster of servers.
The binary tree (or if only one channel is used, the Howard Cascade) sequence, 1, 3, 7, 15 may be used as an example. A (Type I) Howard Cascade computational element count given the communication channel count per computation element is shown below:

Pφ=ψ((ν+1)φ−1)ν−1; iffφ≧0

Pφ0;iffφ<0

Where:
ψ≡# of communication channels at the generate computational element
ν≡# of communication channels at the tree computational element
φ≡# of time steps
Rather than applying Amdahl's law to 15 nodes (as the law states and as it is used currently) the present method applies it to only 3 serialized pairs of nodes (or 2 pairs for 7 nodes, or 1 pair for 3 nodes). Also, rather than calculating the scaling provided, the virtual channel performance required for the pairs to scale is calculated. Since the pairs represent the only exposed serialism, this means that these pairs represent only the actual performance required. This is fundamentally important, as (a) it allows the system efficiency to be calculated prior to running a particular job (which is not presently possible with current technology), (b) it provides the minimum channel performance required to meet the scaling requirements, and (c) it provides a method for manipulating virtual channels that is scaling-centric versus capacity-centric.
The above ‘sufficient communication channel rate’ computation need be performed only for the single set of nodes that represents the ‘long-pole’ of (i.e., the longest computational path through) the computational pairs. For example, if 3×3 nodes are arranged in a square (as shown below in Table 1), with the inter-nodal communication occurring from top to bottom, then only the two pair-wise exchanges representing the ‘long-pole’ need be calculated.









TABLE 1







1
2
3


4
5
6


7
8
9









That is, if data is moved from 1 to 4 to 7 and from 2 to 6 to 8 and from 3 to 6 to 9, then, since each path is the same length in terms of communication number, only the channel performance of one of the groups, for example, 1 to 4 to 7, need be calculated. This will guarantee that the same scaling will occur for all three groups. This minimum calculation aspect greatly decreases the efficiency requirements of the present system/method over a raw use of Amdahl's law.
Virtual Channel Bonding
Channel bonding occurs when two or more physical communication channels are used to move the same dataset such that the data transmission time decreases as a function of the number of bonded channels. Inter-channel data skew (because of timing issues across physical devices) limits the effectiveness of physical channel bonding. Virtual channel bonding occurs when a single physical channel is subdivided into multiple discrete virtual channels with two or more of those virtual channels combined such that the data transmission time decreases as a function of the number of bonded channels. Unlike physical channel-bonding techniques, virtual channel bonding does not have data skew, as all communication takes place across the same physical device.
If the virtual channel performance is set to the lowest transmission rate acceptable on the physical channel, then faster performance is available on demand by bonding together multiple virtual channels until the desired transmission rate is reached. Since the present system requires that pair-wise connected nodes scale to some required level, using virtual channel bonding to dynamically change the channel performance to provide the required minimum transmission rate maximizes the number of virtual channels that can be used with any particular algorithm. Maximizing the number of virtual channels non-linearly maximizes the system scaling.
Sufficient Virtual Channels
Since communication channels can be constructed using different transmission frequencies, pulse widths, and phase angles, multiple communication channels can travel using the same physical interconnect, as is well known, such as, multi-rail and virtual channels. The physical channel can be decomposed (subdivided) into as many virtual channels as remain sufficient to scale at the pair-wise level, allowing an increase in the number of computational elements that are in communication while maintaining the scaling of the group of elements processing a single problem in parallel.
If a pair of computational devices running some shared algorithm have an Amdahl scaling factor S that is sufficient (as much as required) at some communication bandwidth X and some latency Y then increasing the bandwidth has no practical effect on that pair's scaling.
Therefore:

X+Y=S and

aX+Y=S; for all practical purposes; where a=some bandwidth multiplier

FIG. 1A shows a segment of a prior art system having a channel bandwidth of 2× bits/sec, wherein Processor1 [102(1)] communicates with Processor2 [102(2)] in a first time step 121, and communicates with Processor3 [102(3)] in a second time step 122. FIG. 1B shows a segment of a prior art system having a channel bandwidth of X bits/sec, wherein Processor1 [102(1)] communicates with Processor2 [102(2)] and Processor3 [102(3)] in a single time step.
In the current practice, the processing in both FIGS. 1A and 1B is treated as equivalent when the channel bandwidth in FIG. 1A has twice the bandwidth as the channel bandwidth in FIG. 1B. However, this is untrue as the latency in FIG. 1A is twice that of FIG. 1B. Therefore, creating multiple virtual sufficient channels out of a particular physical channel bandwidth offers a latency advantage over using the full bandwidth of a single channel. This advantage remains even in the case where all of the physical channel bandwidth is not consumed.
Using multiple virtual sufficient channels in either a Howard Cascade or other tree-like structure offers additional advantages, as can be observed from a comparison of FIGS. 2A and 2B, both of which employ an exemplary Howard Cascade structure. FIGS. 2A and 2B both show inter-processor communication taking place in two time steps 221/222, and 223/224, respectively. In FIG. 2A, only a single virtual channel is used, whereas in FIG. 2B, two virtual channels are employed. Even if the channel in FIG. 2A has twice the bandwidth of that in FIG. 2B, it may not be able to scale as well if the communication is latency bound. If latency is the deciding factor, then FIG. 2A will scale with 3 nodes in two time-steps versus the 8 nodes FIG. 2B would scale to.
Multi-server, Multi-processor, Multi-Core Sufficient Virtual Channel Type I Howard Cascade
FIG. 3 is a diagram showing an exemplary parallel processing system 300 in a Howard Cascade structure with which the present method may be employed. As shown in FIG. 3, three servers are defined, an Hnode or home node (scheduling node) 111 and two Cnodes or computational nodes, Cnode1 [110(1)] and Cnode2 [110(2)]. In an exemplary embodiment, each Cnode 110 includes a dual-processor machine comprising processors 102(1) and 102(2), each of which have two cores 103 and cache memory 107. Each Cnode server 110 also includes a NIC (Network Interface Card) 105, a PCIe (Peripheral Component Interconnect Express) bus 106, DMA (Direct Memory Access) controller 108, and RAM (Random Access Memory) 104. Cnodes 110(1) and 110(2) are connected via physical cabling 306/307 to switch 114 which is connected via cabling 305 to Hnode 111.
Sufficient Channel Types
There are two possible types of sufficient channels—ones constructed using bandwidth limiting across a network and ones constructed using multiple PCIe bus lanes. Bandwidth limiting is typically used by network providers to manage oversubscribed network bandwidth. This means that multiple virtual communication channels can be created. If a virtual channel is created which connects a core in one server with a core in another server and if the performance of that virtual channel is such that the performance of the two cores is within some requested scaling factor, then that virtual channel shall be considered a sufficient virtual channel.
Multiple PCIe bus lanes 115 can also be accessed together to increase the bandwidth used to access RAM 104, DMA controller 108, or NIC 105. If the number of PCIe bus lanes used have an aggregate channel rate which equals or exceeds the performance of the sufficient virtual channel, then the group of PCIe bus lanes can be considered an extension of the sufficient virtual channel, or alternatively, can be considered to be a separate sufficient virtual channel.
FIG. 4 is a diagram showing an exemplary multi-level single sufficient virtual channel type I Howard Cascade. In FIG. 4, a sufficient virtual channel consisting of a bandwidth limited virtual channel is indicated by a solid line, and a sufficient virtual channel comprising one or more PCIe lanes 115 is indicated by a dashed line. FIG. 4 shows 3 successive time-steps 1-3 [blocks 411-413]. A time-step signifies that one or more sufficient virtual channels are engaged in a simultaneous data transfer. The list below describes an exemplary single sufficient virtual channel 7-core Howard Cascade, shown in FIG. 4, using the hardware configuration shown in FIG. 3, with the following notational assumptions:
Core1, Processor1, Hnode=N0 
Core1, Processor1, Cnode1=N1 
Core2, Processor1, Cnode1=N2 
Core1, Processor2, Cnode1=N3 
Core2, Processor2, Cnode1=N4 
Core1, Processor1, Cnode2=N5 
Core2, Processor1, Cnode2=N6 
Core1, Processor2, Cnode2=N7 
Core2, Processor2, Cnode2=N8 
In FIG. 4, the above notational assumptions provide a simplified graphic view of Example 1 below, showing only the data movement and the cores involved.
EXAMPLE 1
Multi-Level Single Sufficient Virtual Channel Type I Howard Cascade
(1) As shown in FIG. 4, in time-step 1 [block 411], node N0 creates a sufficient virtual channel 401 on port1 connecting Hnode 111 to Node N1 Node N0 also creates another sufficient virtual channel 402 on port2 connecting Node N0 to Node N5, and finally it creates another sufficient virtual channel 403 on port3 connecting Node N0 to Node N7.
(2) Node N0 allocates a portion of its server's RAM 104 as an output message holding buffer. Nodes N1 through N7 allocate a portion of their respective servers' RAM 104 as an input message holding buffer.
(3) Node N0 creates a message in its output message holding buffer. Node N1 opens port1 and awaits a message. Node N5 opens port2 and awaits a message. Node N7 opens port3 and awaits a message.
(4) Node N0 opens port1 to node NI, between its NIC 105 and the NIC 105 of node N1 through switch 114.
(5) Node N0 creates a DMA connection between its allocated output message holding buffer and its NIC 105, transmitting the created message to node N1, which upon receiving the message, has its DMA controller 108 store the received message in its allocated input message holding buffer.
(6) In time-step 2 [block 412], once the message has been transmitted by node N0 via port1, node N0 closes port1, then opens port2 between its NIC and the NIC of node N5, through switch 114. Node N0 creates a DMA connection between its allocated output message holding buffer and its NIC, transmitting the created message to node N5, which upon receiving the message, has its DMA controller store the received message in its allocated input message holding buffer. Node N1 creates a message with its received data and performs a memory-to-memory data copy of this message into the allocated input message holding buffer of node N2, using sufficient virtual channel 404.
(7) In time-step 3 [block 413], once the message has been transmitted by node N0 via port2, node N0 closes port2, then opens port3 between its NIC and the NIC of node N7 through switch 114. Node N0 creates a DMA connection between its allocated output message holding buffer and its NIC, transmitting the created message to node N7, which upon receiving the message, has its DMA controller store the received message in its allocated input message holding buffer. Node N5 creates a message with its received data and performs a memory-to-memory data copy of this message into the allocated input message holding buffer of node N6, using sufficient virtual channel 405. Even though channels 404, 405, and 406 are effectively extensions of channels 401/402, they are technically different channels as they are constructed using the physical PCIe bus structure rather than using the physical Ethernet wire. Node N1 creates a message with its received data and performs a memory-to-memory data copy of this message into the allocated input message holding buffer of node N3, using sufficient virtual channel 404. Node N2 creates a message with its received data and performs a memory-to-memory data copy of this message into the allocated input message holding buffer of node N4, using sufficient virtual channel 406.
In an exemplary embodiment, data transfers via virtual channels 404-406 are conducted via PCIe bus lanes 115, as indicated by corresponding dashed lines in FIG. 4.
FIG. 5 is a diagram showing an exemplary multi-level dual sufficient virtual channel type I Howard Cascade, wherein each node uses two sufficient virtual channels, each one in communication with a respective node in the next Cascade level. FIG. 5 is a simplified graphic view of Example 2, below, showing only the data movement and the cores involved. In FIG. 5, a sufficient virtual channel consisting of a bandwidth limited virtual channel is indicated by a solid line, and a sufficient virtual channel consisting of one or more PCIe lanes 115 is indicated by a dashed line.
EXAMPLE 2
Multi-Level Duo-Sufficient Virtual Channel Type I Howard Cascade
(1) As shown in FIG. 5, in time-step 1 [block 511], node N0 creates sufficient virtual channels 501 on port1 and 502 on port2 connecting Hnode 111 to nodes N1 and N3, respectively, and also creates sufficient virtual channels 503 on port3 and 504 on port4 connecting node N0 to nodes N7 and Ng. Node N2 creates sufficient virtual channels 505 on port5 and 506 on port6 connecting node N2 to nodes N5 and N7.
(2) Node N0 allocates a portion of its server's RAM as an output message holding buffer. Nodes N1 through Ng each allocates a portion of their server's RAM as an input message holding buffer. Node N3 allocates a portion of its server's RAM as an output message holding buffer.
(3) Node N0 creates a message in its output message holding buffer. Node N1 opens port1 and awaits a message. Node N3 opens port2 and awaits a message. Node N7 opens port3 and awaits a message. Node Ng opens port4 and awaits a message.
(4) Node N0 opens port1 and port2 between its NIC and the NIC of nodes N1 and N3 through switch 114.
(5) Node N0 creates a DMA connection between its allocated output message holding buffer and its NIC, transmitting the created message to nodes N1 and N3, using sufficient virtual channels 501 and 502, which upon receiving the messages, have their DMA controllers store the received messages in their allocated input message holding buffers.
(6) In time-step 2 [block 512], once the messages have been transmitted by node N0 via port1 and port2, then node N0 closes port1 and port2, and then opens port3 and port4 between its NIC and the NIC of nodes N7 and Ng through switch 114. Node N1 creates a message with its received data and performs a memory-to-memory data copy of this message into the allocated input message holding buffers of both nodes N2 and N4, using sufficient virtual channels 507 and 508, respectively. Node N3 opens ports and port6, creates a message into its allocated output message holding buffer with its received data and performs a DMA transfer between its allocated output message holding buffer and its NIC, transmitting the created message, via virtual channels 505/506, to nodes N6 and N6, respectively, which upon receiving the messages, have their DMA controllers store the received message in their allocated input message holding buffers.
(7) Node N0 creates a DMA connection between its allocated output message holding buffer and its NIC, transmitting the created message to nodes N7 and N8, which upon receiving the messages, have their DMA controllers store the received messages in their allocated input message holding buffer.
(8) Once the message has been transmitted by node N0 via port3 and port4, node N0 closes port3 and port4. Once the message has been transmitted by node N3 via port5 and port6, it then closes port5 and port6.
In an exemplary embodiment, data transfers via virtual channels 507 and 508 are conducted via PCIe bus lanes 115, as indicated by corresponding dashed lines in FIG. 5.
FIG. 6 is a diagram showing exemplary steps performed in interconnecting multiple computational devices in a parallel computing network including a plurality of serially associated pairs of nodes, wherein each of the nodes is interconnected via at least one physical communication channel. As shown in FIG. 6, at step 605, a sufficient virtual channel rate required to provide a predetermined amount of Amdahl scaling is determined in accordance with Amdahl's law. At step 610, the physical communication channel rate (the average physical channel rate) is divided by the sufficient virtual channel rate to determine the maximum whole number of virtual channels that can be implemented over each physical communication channel, with each virtual channel having a transmission rate at least equal to the sufficient virtual channel rate. At step 615, the physical communication channel between each of the nodes is subdivided into the determined maximum number of virtual channels.
Certain changes may be made in the above methods and systems without departing from the scope of that which is described herein. It is to be noted that all matter contained in the above description or shown in the accompanying drawings is to be interpreted as illustrative and not in a limiting sense. The elements and steps shown in the present drawings may be modified in accordance with the methods described herein, without departing from the spirit of the system thus described. The following claims are intended to cover all generic and specific features described herein, as well as all statements of the scope of the present method, system and structure, which, as a matter of language, might be said to fall therebetween.

## Claims

1. A method for interconnecting multiple computational devices in a parallel computing network including a plurality of serially associated pairs of computational nodes, wherein each of the pairs of nodes is interconnected via at least one physical communication channel, the method comprising:
determining, in accordance with Amdahl's law, an acceptable amount of serialism for a predetermined level of parallel speedup for an algorithm executed on a pair of said nodes;
determining a channel rate required to generate the acceptable amount of serialism;
using the ratio of the determined channel speed and a predetermined required maximum serialism to calculate a sufficient virtual channel rate required to provide a predetermined amount of Amdahl scaling which is sufficient at a predetermined channel speed and a predetermined latency;
determining a maximum number of virtual channels, each having a transmission rate at least equal to the sufficient virtual channel rate, that can be implemented over each physical communication channel; and
subdividing the bandwidth of each of the physical communication channels into the determined maximum number of virtual channels, each of which is used to interconnect an associated pair of the computational devices.

2. The method of claim 1, wherein each said physical channel is subdivided into multiple discrete virtual channels with two or more of the virtual channels combined until the sufficient virtual channel rate is attained.

3. The method of claim 1, wherein the number of virtual channels implemented over each physical communication channel is dynamically changed to provide the determined sufficient virtual channel rate to optimize the number of virtual channels that can be used with a particular algorithm.

4. The method of claim 1, including subdividing the physical channel into as many virtual channels as remain sufficient to scale at a pair-wise node level, to thereby allow an increase in the number of computational elements that are in communication while maintaining the scaling of a group of computational elements processing a single problem in parallel.

5. A parallel computing network comprising:
a plurality of serially associated pairs of computational nodes, each of the nodes including at least one processor having at least one core, wherein each pair of the nodes is interconnected via a physical communication channel;
wherein each core in each computational node is interconnected with each other core therein via a bus coupled to processor memory;
wherein the bandwidth of the physical communication channel between each of the nodes is subdivided into a plurality of sufficient virtual channels;
wherein, in accordance with Amdahl's law, an acceptable amount of serialism for a predetermined level of parallel speedup for an algorithm executed on a pair of said nodes is determined, a channel rate required to generate the acceptable amount of serialism is determined, and the ratio of the determined channel speed and a predetermined required maximum serialism is used to calculate a sufficient virtual channel rate, for each of the sufficient virtual channels, required to provide a predetermined amount of Amdahl scaling which is sufficient at a predetermined said channel rate and a predetermined latency.

6. The method of claim 5, wherein at least one of the sufficient virtual channels is created between one of the cores in one node and one of the cores in another node.

7. The method of claim 5, wherein the bus comprises a plurality of PCIe bus lanes, and the sufficient virtual channel is created by using a number of the PCIe bus lanes whose aggregate rate is at least equal to the sufficient virtual channel rate.

8. The method of claim 7, wherein a portion of the associated nodes are interconnected via a bandwidth limited sufficient virtual channel, and a portion of the associated nodes are interconnected via a sufficient virtual channel consisting of one or more of the PCIe bus lanes.

9. A parallel computing network comprising:
a Howard Cascade including a physical communication channel connecting each of the nodes in the Cascade, wherein each node therein is coupled to an associated node via a single sufficient virtual channel;
wherein, in accordance with Amdahl's law, an acceptable amount of serialism for a predetermined level of parallel speedup for an algorithm executed on a pair of said nodes is determined, a channel rate required to generate the acceptable amount of serialism is determined, and the ratio of the determined channel speed and a predetermined required maximum serialism is used to calculate a sufficient virtual channel rate, for each said single sufficient virtual channel, required to provide a predetermined amount of Amdahl scaling which is sufficient at a predetermined said channel rate and a predetermined latency;
wherein the bandwidth of the physical communication channel between each of the nodes is subdivided into a plurality of said sufficient virtual channels, each of which is used to interconnect an associated pair of the nodes.

10. The method of claim 9, wherein a portion of the associated nodes are interconnected via a bandwidth limited sufficient virtual channel, and a portion of the associated nodes are interconnected via a sufficient virtual channel consisting of one or more PCIe bus lanes.

11. A parallel computing network including a plurality of pair-wise associated nodes comprising:
a Howard Cascade including a physical communication channel between each of the nodes in the Cascade,
wherein each of the nodes in a given level of the Cascade communicates with each of two associated nodes in a successive level of the Cascade via one of two respective sufficient virtual channels;
wherein, in accordance with Amdahl's law, an acceptable amount of serialism for a predetermined level of parallel speedup for an algorithm executed on a pair of said nodes is determined, a channel rate required to generate the acceptable amount of serialism is determined, and the ratio of the determined channel speed and a predetermined required maximum serialism is used to calculate a sufficient virtual channel rate, for each of the sufficient virtual channels required to provide a predetermined amount of Amdahl scaling which is sufficient at a predetermined said channel rate and a predetermined latency.

12. The method of claim 11, wherein a portion of the associated nodes are interconnected via a bandwidth limited sufficient virtual channel, and a portion of the associated nodes are interconnected via a sufficient virtual channel consisting of one or more PCIe bus lanes.

13. A method for determining a minimum number of serially associated pairs of nodes required to provide a predetermined amount of Amdahl scaling in a network including a plurality of said nodes and at least an equal number of computational elements, wherein each of the nodes is interconnected via at least one physical communication channel, the method comprising:
determining, in accordance with Amdahl's law, a sufficient communication channel rate required to provide the predetermined amount of Amdahl scaling; and
calculating a required minimum number of said nodes based on the determined sufficient communication channel rate and the average bandwidth of each said communication channel;
wherein, in accordance with Amdahl's law, an acceptable amount of serialism for a predetermined level of parallel speedup for an algorithm executed on a pair of said nodes is determined, a channel rate required to generate the acceptable amount of serialism is determined, and the ratio of the determined channel speed and a predetermined required maximum serialism is used to calculate the sufficient communication channel rate, for each of the sufficient virtual channels, required to provide a predetermined amount of Amdahl scaling which is sufficient at a predetermined said channel rate and a predetermined latency.

14. The method of claim 13, wherein each of the serially associated pairs of nodes is interconnected via at least one virtual communication channel, which is a subdivision of the physical communication channel.

15. The method of claim 13, wherein the maximum number of the pairs required to effect the predetermined amount of Amdahl scaling for any number of associated nodes is equal to the number of pairs in the longest path of serially associated pairs of the nodes in the network.