Abstract:
A method using for performing a scatter-type data distribution among a cluster of computational devices. A number of nodes (equal to a value Cg, the number of tree generator channels) are initially generated, each connected to an initial generator, to create respective initial root nodes of an initial tree structure. Data is transmitted from the initial generator to each of the initial root nodes. Cg root nodes, each connected to a respective new generator, are generated to create respective roots of Cg newly generated tree structures. Each of the tree structures is expanded by generating Ct (the number of communication channels per node in each tree structure) new nodes connected to each node generated in each previous step. Data is then transmitted to each of the new nodes from an immediately preceding one of the nodes, and from each new generator to an associated root node.

Description:
RELATED APPLICATIONS 
     This application claims priority to U.S. Patent Application Ser. No. 61/165,301, filed Mar. 31, 2009 and U.S. Patent Application Ser. No. 61/166,630, filed Apr. 3, 2009, both of which are incorporated herein by reference. 
     This application is also a continuation-in-part of U.S. patent application Ser. No. 12/197,881, “Parallel Processing Systems and Method”, filed Aug. 25, 2008 now U.S. Pat. No. 7,730,121, and incorporated herein by reference. 
    
    
     BACKGROUND 
     Two of the most important types of data movement for a parallel processing system are the scatter exchange and the gather exchange. A scatter exchange moves data from one or more locations specified by the user in a single direction away from the starting location(s) such that dispersed computational elements in the system gain access to the data. This is analogous to the scattering of seeds across a field to ensure that the widest seed dispersal is accomplished. A gather exchange is the opposite, wherein data is gathered from the dispersed computational elements and sent back to a user defined location or locations. 
     The two standard methods of performing a scatter exchange are the true broadcast and the tree broadcast. The true broadcast transmits the data all at the same time from some central location to all computational elements in a group. The problem with a true broadcast is that in order to provide reliable data transmission it must use an error correcting code (the simplest being a single dimensional checksum, which is subject to double bit errors) of sufficient length, given the channel fault rate. Alternatively, if no error detection/correction is employed, data transmission errors will inevitably occur at some point. 
     Error correction cannot guarantee that the transmitted data is correct, rather only that it is ‘statistically’ correct; thus additional data must be transmitted, effectively degrading the performance of the communication channel. For example, a Reed-Solomon ECC adds 8 percent overhead to a code while being able to handle up to a 4 percent data error rate (e.g., standard 188 data bytes transmitted plus 16 redundant bytes). 
     True broadcasts cannot use a faster method which employs a bi-directional communication channel that moves the first from the sender to the receiver and from the receiver back to the sender (which insures that the data is correct). This is because there are multiple receivers and only one sender, greatly increasing the safe data transmission time, thus eliminating the advantage of broadcasting the data. 
     Because of these issues, modern parallel computer systems typically use a tree broadcast, in which data is sent from one computational element to another using a binomial tree arrangement of computational elements. This binary tree solution allows a series of pair-wise exchanges rather than a single broadcast, making it possible to have safe data transmission. Instead of taking (dataset size)/(transmission time) time, as is the case with a true broadcast, a tree broadcast instead takes [(dataset size)*Ig 2 (number of computational elements)]/(transmission time) time. 
     The approach, described herein, of using a mathematical forest (multiple parallel trees) consisting of binomial (or other function) trees has the advantage of a safe broadcast with a minimum performance that is twice that of the industry standard tree-broadcast. Gather exchanges always use a tree-broadcast model, but in reverse. The present approach is equally advantageous for a gather exchange. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a diagram showing an exemplary set of steps in a (prior art) binomial tree expansion; 
         FIG. 2  is a diagram showing an exemplary set of steps in a (prior art) perfect binary tree expansion; 
         FIG. 3  is a diagram showing an exemplary set of steps performed in expansion of a binomial-based Type I Howard cascade, with a single channel generator and single channel trees; 
         FIG. 4  is a diagram showing an exemplary set of steps performed in expansion of a binomial-based Type I Howard Cascade, with duo-channel generator and duo-channel trees; 
         FIG. 5  is a diagram showing an exemplary set of steps performed in expansion of a binomial Howard Cascade using sum Fibonacci instead of sum root-level expansions; 
         FIG. 6  is a diagram showing an exemplary set of steps performed in expansion of a Type I Howard Cascade with multiple n-nomial tree-level basis functions; 
         FIG. 7  is a diagram showing an exemplary set of steps performed in expansion of a Type I Howard Cascade with non-N-nomial trees; 
         FIG. 8  is a diagram showing an exemplary set of steps performed in expansion of a variable rate monotonic Type I Howard Cascade using communication channels; 
         FIG. 9  is a diagram showing an exemplary set of steps performed in expansion of a variable rate Type I Howard Cascade using communication channels; 
         FIG. 10  is an exemplary diagram showing a processing network having unbalanced performance; 
         FIG. 11  is an exemplary diagram showing the use of a variable rate monotonic Howard Cascade to balance the system performance of the network shown in  FIG. 10 ; 
         FIGS. 12A and 12B  are diagrams showing an exemplary method of balancing communication channel performance using a variable rate monotonic Howard Cascade; 
         FIGS. 13A and 13B  are diagrams showing an exemplary method of balancing computational element performance using a Howard Cascade with mixed Fibonacci and binomial basis; 
         FIGS. 14A and 14B  are diagrams showing an exemplary method using root-level contraction and mixed basis to select the computational element count; and 
         FIGS. 15A and 15B  are diagrams showing an exemplary method using mixed transformation, root expansion, and channel count. 
     
    
    
     DETAILED DESCRIPTION 
     Type I Howard Cascade Generation 
     A type I Howard Cascade (Cascade) superficially resembles a tree structure, but it is not a tree structure. The differences among a binomial tree (which the standard Cascade most resembles), a perfect binary tree, and a binomial-based Howard Cascade lie in how each is generated and the number of communication channels used in their expansion. These three types of tree and tree-like functions are respectively depicted in  FIGS. 1-3 . 
     Each of the figures (diagrams) described herein is partitioned into a sequential series of time steps, as indicated by the numbers at the bottom of each diagram and the corresponding sections of each diagram separated by vertical dashed lines. The top section of each diagram includes a generator, which generates the tree structure(s) below the horizontal dashed line. In each time step, one or more arrows indicate communication channels between an existing node and one or more nodes that are generated in that particular time step. Each node may represent a computational element or device, such as a processor or other computing entity. 
       FIG. 1  is a flowchart showing an exemplary set of steps in a (prior art) binomial tree expansion. As shown in  FIG. 1 , in time step  1 , generator  101  generates root node  102  of a binary tree  100 . The binomial tree is said to be generated, which means that there is some function—the generator function—that initiates the construction of the tree. Note that the generator function is not part of the tree; it only creates the root of the tree. In a binomial tree expansion, shown in  FIG. 1 , only a single tree is generated for a binomial tree. After initial generation of a root (the beginning of the tree), the tree starts dividing. At each subsequent time step, as indicated in time steps  2  and  3 , each portion of the binomial tree again divides, using a single communication channel per node. Thus, as shown in  FIG. 2 , node  103  is generated in time step  2 , and nodes  104  and  105  are generated in time step  3 . The growth sequence of generated nodes is {1, 2, 4, . . . , 2 n }, where n=(time step)−1. If the number of communication channels at the tree level is increased from one to two, and each node is allowed to expand only once, then a perfect binary tree is created, as shown in  FIG. 2 . 
       FIG. 2  is a diagram showing an exemplary set of steps in a (prior art) perfect binary tree expansion. As with the binomial tree, only a single tree is generated for the perfect binary tree  200 . As shown in  FIG. 2 , at each time step, each node uses two channels  201  to generates two new nodes. The sequence of generated nodes for a perfect binary tree is {1, 3, 7, . . . , 2 n −1}, where n=(time step). 
       FIG. 3  is a diagram showing an exemplary set of steps in expansion of a binomial-based Type I Howard cascade, with a single channel generator  301  and single channel trees. Instead of increasing the number of channels and limiting the expansion per node to one, a binomial-tree-based Type I Howard Cascade continuously generates additional trees. For example, trees  303 ,  304  and  305  are initially generated in time steps  1 ,  2 , and  3 , respectively, and each tree expands using a single communication channel (indicated by each of the arrows in  FIG. 3 ) while allowing each node to generate at least one additional node at each time step. 
     The sequence of generated nodes for the Cascade is {1, 3, 7, . . . , 2 n −1}, where n=(time step). Even though the sequence of generated nodes superficially resembles a perfect binary tree, the Cascade is not one. In parallel processing applications, a Cascade has almost twice the efficiency of a binomial tree, yet uses one half of the communication pathways of a perfect binary tree. Rather than representing a tree, the Cascade shown in  FIG. 3  represents a mathematical forest of time-ordered binomial trees. The generator level and the tree level can have more than a single communication channel, as shown in  FIG. 3 . 
     Scattering/Gathering 
     In parallel computing, a data scatter operation sends data from one processing node to all other processing nodes within a particular group. 
     Agglomeration refers to (a) the gathering of individual results from each processing node and (b) the formatting of these results into a complete solution. Each processing node sends its results to the processing node that is directly upstream. The flow of results thereby occurs in reverse sequence order of the initial expansion within a Cascade. 
     A direct result of agglomeration is that the results from each node maintain the same ordered relationship as the decomposition of the initial dataset. Each processing node knows how many downstream processing nodes it has; and the subsequent downstream results, from the downstream nodes, form a contiguous block of data. Each of the processing nodes has its results data, and the location and size information that enables the upstream processing node to properly position the results, when received. As the results are sent upstream through a Cascade, the size of the result information expands contiguously until the entire result block is assembled at a home node. 
       FIG. 4  is a diagram showing an exemplary set of steps performed in expansion of a binomial-based Type I Howard Cascade, with duo-channel generator and duo-channel trees. The general equation for a Standard Type I Howard Cascade with an arbitrary number of generator and tree communication channels is given in Equation 1: 
     Standard Type I Howard Cascade
 
 P   φ =ψΣ 1   φ (ν+1) φ−1   ; iff φ&gt; 0
 
 P   φ =0;  iff φ≦ 0  Equation 1
 
     Where:
         ψ≡number of generator level communication channels   ν≡number of tree level communication channels   φ≡number of time steps       

     The term (ν+1) φ  takes the place of 2 n . Therefore, a single tree-level communication channel gives (ν+1) φ =(1+1) φ =2 φ =2 n . The term 2 n  creates the sequence for a binomial tree. Similarly, two communication channels gives 3 φ  (the sequence of the trinomial), and the general case gives all n-nomial trees. Thus, the standard Type I Howard Cascade can be based upon any single n-nomial tree. 
     Type I Howard Cascades with Controlled Tree Generation 
     The generation of the trees found in Type I Howard Cascades can be directly manipulated using Equation 1 above. This equation shows that multiple summed “(ν+1) φ ” terms can be used together to produce a Cascade. The type of summation used directly affects the number of trees generated. The summation index position represents which tree is activated by the generator as well as the order of tree activation. Replacing the symbol for summation with the sum function and the term (ν+1) φ−1  with a binomial-tree node-count calculating function changes Equation 1 to the following: 
     Type I Howard Cascade Alternative Equation
 
 P   φ =ψ(SUM−(φ, f ((φ−1),ψ,ν)));  iff φ&gt; 0
 
 P   φ =0;  iff φ≦ 0  Equation 2
         where SUM−(, f((φ(φ−1), ψ, ν))≡a decrementing sum: the value of φ decreases at each time step, while the calculated binomial counts are summed together.   f((φ−1), ψ, ν)≡binomial-tree node-count calculating function       

     There are an enormous number of SUM functions available for use in a Cascade, allowing for different patterns of tree creation to occur. It can be seen that selecting the active generation pattern is really selecting which function is summed upon. For example, using a Fibonacci SUM sequence rather than a decrement sum gives the following as a Cascade: 
     Sum Sequence={0, 1, 2, 3, 4, 5, . . . } 
     Fibonacci Sequence={0, 1, 1, 2, 3, 5, . . . } 
       FIG. 5  is a diagram showing an exemplary set of steps performed in expansion of a binomial Howard Cascade using sum Fibonacci instead of sum root-level expansions. Note the skipped computational elements  501 ,  502 , and  503 , relative to the sum root-level expansion. The expansion of each tree of the Cascade is, thus, given by the binomial tree pattern, leading to an important observation: each tree within a Cascade represents its own separate series expansion, entirely independent from the other Cascade trees and can be represented by its own n-nomial tree equation. 
     Type I Howard Cascades with Multiple Different Trees 
     A Cascade strip is a single tree in the forest of trees in a Cascade. Each tree is numbered from 1-n where the number is the time step used to generate the tree. Using the n-nomial tree pattern described above allows each Cascade strip to be shown as: 
     N-Nomial Tree Series
 
 P   φ =(ν+1) φ +(ν+1) φ−1 +(ν+1) φ−2 + . . . +(ν+1) 0   Equation 3
 
     Next, the n-nomial series is converted to its constituent series expansion, noting that this is the number of connections made at each level of a binomial series. 
     Binomial Connection Terms as Series
 
Connections≡{0,1,2,4,8,16, . . . ,Σ φ−1   n=0  2 φ }  Equation 4
 
     Since the trinomial is 2× the binomial and the 4-nomial is 3× the binomial, n-nomial is given by: 
     N-Nomial Connection Terms as Series
 
 P   s =νΣ φ−1   n=0 2 φ =Σ φ−1   n=0 ν(2 φ )  Equation 5
 
     The possible expansions used at the Cascade strip level can now be explicitly shown, depending upon ν:
 
 P   S =Σ φ   n=0 Binomial,  P   S =Σ φ   n=0 Trinomial, . . .  P   S =Σ φ   n=0 Polynomial
 
     By allowing a different value of ν at each time step, the tree type can be changed at each time step, giving: 
     Use of Variable Sum Function in Type I Howard Cascade
 
 P   φ =ψ(SUM−( I ,SUM X,φ (ν I ,φ−1,ψ,ν)))  Equation 6
 
     Where
         ν I ≡Value of ν at time step index   I≡Current position of the outer sum   SUM X,φ ≡Type of n-nomial sum function (x) at time step φ       

       FIG. 6  is a diagram showing an exemplary set of steps performed in expansion of a Type I Howard Cascade with multiple n-nomial tree-level basis functions. Due to the time-ordered nature of a Type I Howard Cascade, it is possible for the last node(s) that receive data to take an inordinately long time processing that data, because the processing had to wait on the receipt of the dataset. There are two methods of handling this problem—either decrease the dataset size as a function of the order that the data is received by the nodes, or increase the processing performance as a function of the order that the data is received.  FIG. 6  shows a method for continuously increasing the amount of processing power used to process a given dataset as a function of the order that the nodes receive their data. 
     Use of Non-N-nomial Trees in a Type I Howard Cascade 
     Since each tree can be created differently by substituting the inner loop sum, a non-n-nomial rooted tree can be substituted for an n-nomial tree at any time step of the Cascade. The only difference is the type of sum that is used at a particular time step. This changes the meaning of SUM x,φ  found in Equation 6 to any rooted tree sum function. 
       FIG. 7  is a diagram showing an exemplary set of steps performed in expansion of a Type I Howard Cascade with non-N-nomial trees. In  FIG. 7 , tree  701  is a Fibonacci series-based tree, tree  703  is a binomial tree, and tree  705  is a trinomial tree. Note that node  702  is skipped, that is, the node is not actually generated, in the expansion of tree  701  in time step  3 . 
     Using Type I Howard Cascade Effects to Balance Computational Element Performance within a Cluster 
     Monotonic Type I Howard Cascades 
     As described above, it is possible to construct a Type I Howard Cascade using multiple, different tree functions. If the tree functions of a Cascade are such that at each expansion step the number of channels per node is either continuously increasing or continuously decreasing, then that Cascade is said to be monotonic. 
       FIG. 8  is a diagram showing an exemplary set of steps performed in expansion of a variable rate monotonic Type I Howard Cascade using communication channels to interconnect the nodes in each tree, as indicated by the arrows. The structure of a Cascade remains monotonic if the number of channels follows the expansion rate. The monotonic Cascade shown in  FIG. 8  generates the nine nodes shown in time step  3  in three expansion steps rather than the standard seven nodes. The rate of increase/decrease accelerates per expansion time step using this method. There can be any group of rooted trees forming the basis of the monotonic Cascade, as long as the monotonicity is maintained. 
     Variable Rate Monotonic Howard Cascades 
     If the basis functions of a Cascade are such that, at each expansion step, the number of channels per node varies but the number of channels does not continuously increase or decrease, then that Cascade is a variable rate Cascade. 
       FIG. 9  is a diagram showing an exemplary set of steps performed in expansion of a variable rate Type I Howard Cascade using communication channels to interconnect the nodes in each tree, as indicated by the arrows. Note that  FIG. 9  shows that each node generated at a particular time step contains the same number of channels. This is called a variable rate monotonic Howard Cascade. If the synchronization of channels per time step is not maintained then neither the time-aligned basis of a Cascade nor the non-data collision basis without a synchronization signal requirement of a Cascade is maintained; thus, such a Cascade cannot exist as it does not meet the requirements. 
     Cluster Computational Element Imbalances 
     Slow Processing Imbalance 
     In a generally homogeneous computational element processing performance environment, if the processing performance of a computational element is slower than the average speed of all of the processors working on the same job due to slow processors, lower than average core counts and/or slow communication channels, then the following process can be used to rebalance the performance. 
     Slow Processing Rebalancing Process:
         1) Using the standard (target) computational element performance and the standard (target) communication channel performance compare the performance of each computational element.   2) Any computational element not within a predefined performance tolerance causes the computational element directly upstream (when agglomerating) or directly downstream (when data scattering) to generate (or if already generated, to use) a virtual channel to another computational element.   3) The performance of the new computational element can be matched to produce the required aggregate performance by changing the clock speed of the new computational element prior to its use. Alternatively, the new computational element can take the place of the old one, if its performance is within the predefined tolerance of the target computational element performance rate.   4) Any computational element whose communication performance is out of tolerance will cause the computational element directly upstream (when agglomerating) or directly downstream (when scattering) to generate (or if already generated, to use) an additional communication channel to/from the low channel performing computational element.   5) The performance of the new channels can either be used to increase the total bandwidth such that it matches the target channel performance, or the new channel can take the place of the old virtual communication channel if the new communication channel performs at the target rate.       

       FIG. 10  is an exemplary diagram showing a processing network having unbalanced performance, and  FIG. 11  is an exemplary diagram showing the use of a variable rate monotonic Howard Cascade to balance the system performance of the computing network shown in  FIG. 10 . 
     Example 1 
     If processors on computational elements  6  and  7  shown in  FIG. 10  and  FIG. 11  generate one-half of the average performance of the other computational elements working on some problem, then connecting those computational elements together with a variable rate monotonic Howard Cascade connected via virtual channels allows the performance to be balanced. 
     As shown in  FIGS. 10 and 11 , the channel performance of a system whereby a computational element (element  6 ) has one half the average performance can be re-balanced by having sub-element  4 , 1  detect (or compute) the performance deficit and using the required number of virtual channels needed to access sufficient computational elements to make up the performance deficit, invoking element  7  (which has approximately the same performance as element  6 ). The work that element  6  would have performed is then evenly shared between element  6  and element  7 . 
       FIGS. 12A and 12B  are diagrams showing an exemplary method of balancing communication channel performance using a variable rate monotonic Howard Cascade. 
     Example 2 
     If channels on computational element  6  shown in  FIG. 12A  generate one-half of the average performance of all computational element channels working on the same problem, then another channel that also generates one-half the average channel performance can be added to rebalance the channel performance. This may be accomplished with the use of virtual channels and a variable rate monotonic extension to an existing Howard Cascade. 
     As shown in  FIG. 12B , the channel performance of the system shown in  FIG. 12A , wherein computational element (element  6 ) has one half the average channel performance, can be rebalanced, by sub-element  4 , 1  detecting (or computing) the performance deficit and using the required number of virtual channels, invoking an additional channel  1202  which has the same performance as the original element  6 . 
     Fast Processor Imbalance 
     In a generally homogeneous computational-element processing-performance environment, if the processing performance of a computational element is faster than the average speed of all of the processors working on the same job due to faster processors, higher than average core counts and/or fast communication channels, then the method described below with respect to  FIGS. 13A and 13B  can be used to rebalance the system performance. 
       FIGS. 13A and 13B  are diagrams showing an exemplary method of balancing computational element performance using a Howard Cascade with mixed Fibonacci and binomial basis.  FIG. 12A  shows an initial system configuration which includes binomial trees  1301 ,  1302 , and  1303 . 
     Example 3 
     If the processors on Cascade strip  1  (block  1301 A) in  FIG. 13A  are, for example, ˜43 percent faster than the average of all computational elements in the system, then the steps shown in  FIG. 13B  may be performed to relieve the system performance imbalance. As shown in  FIG. 13B , A Fibonacci tree  1201 B is substituted for binomial tree  1301 A, thus causing nodes (computational elements)  1304  and  1305  to be skipped, which balances the system performance in view of the relatively slower processors in binomial trees  1302  and  1303 . 
       FIGS. 14A and 14B  are diagrams showing an exemplary method using root-level contraction and mixed basis to select the computational element count.  FIG. 14A  shows incremental expansion and contraction of three binomial trees, while  FIG. 14B  shows expansion and contraction of a Fibonacci tree  1401  which replaces the corresponding (first) binomial tree (in  FIG. 14A ), and also shows (additional) skipped computational elements  1402  in the second binomial tree. 
     Example 4 
     When the number of computational elements generated is the maximum possible given an n-nomial expansion, the current number of time steps, and the number of communication channels, the result is called a Type I Cascade sweet spot. Using both the root-level expansion and mixed basis to select a non-sweet spot computational-element count shows the selection of four computational elements in  FIG. 14B  as opposed to the seven elements in the initial configuration of  FIG. 14A . Note that any number of computational elements can be generated by changing the basis functions. Thus, even though a standard single channel Type I Cascade cannot generate 4 nodes, changing the basis function nevertheless allows non-sweet spot node counts. As can be seen in the present example, mixing root level with basis changes allows for a wide range of effects, as shown in  FIGS. 14A and 14B . 
     Mixed Conditions 
       FIGS. 15A and 15B  are diagrams showing an exemplary method using mixed transformation, root expansion, and channel count. A mixed condition occurs when the number of channels in one part of the system and the expansion model of another part of the system must be changed, allowing for maximum variation when configuring a system. 
     Example 5 
     A mixed condition is shown in  FIGS. 15A and 15B , where computational element  6  requires twice the number of channels, since it has one-half the average channel performance; hence the addition of channel  1502  in  FIG. 15B . In this example, expansion and contraction of a Fibonacci tree occurs in a manner analogous to that of Example 14, and likewise, computational elements  1503  are skipped to further balance the system performance. Being able to change the generation of both the type and number and order of trees provides the flexibility required to generate any node count. 
     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, and the steps shown therein may be sequenced in other configurations 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 there between.