Patent Document ID: 5513371
Application ID: 08378981
Patent Flag: 1

Claim One:
1. For implementing an Ascend algorithm having 2.sup.n data items, each of which has a unique integer ID having a value between 0 and 2.sup.n -1 inclusive, where n is an integer, wherein said Ascend algorithm has n stages, 0 through n-1, and further wherein at each state i, 0.ltoreq.i.ltoreq.n-1, processing is performed on each pair of data items with IDs whose binary representation differ only in bit position i, on an Hierarchical Shuffle-Exchange (HSE) computer having 2.sup.n processors, each of which has a unique ID having a value between 0 and 2.sup.n -1, inclusive wherein said HSE computer includes 2.sup.n-m packaging modules, where m is an integer and n&gt;m, said method comprising the steps of: (a) storing each data item j, where j is an integer having a value between 0 and 2.sup.n -1 inclusive, in processor j; (b) performing the first m stages of said Ascend algorithm by utilizing exchange connections and local unshuffle connections of said HSE computer, the exchange connections being connections between each given one of the processors and a respective other one of the processors having an ID identical to that of the given one of the processors, except for a least significant bit opposite to that of the given one of the processors, the local unshuffle connections being connections between each given one of the processors and a respective other one of the processors having an ID identical to that of the given one of the processors, except that the m lowest significance bits of the ID of the other one of the processors, are those of the given one of the processors, subjected to a right rotate; (c) repositioning the data items by utilizing global unshuffle connections of said HSE computer, the global unshuffle connections being connections between each given one of the processors and a respective other one of the processors having an ID identical to that of the given one of the processors, except that the bits of the ID of the other one of the processors are those of the given one of the processors, wherein the n-m most significant bits are in the n-m least significant bit positions, and the m least significant bits are in the m most significant bit positions; and (d) repeating steps (b) and (c) until all the n stages of the Ascend algorithm have been completed.