Parallel processing algorithms take advantage of multi-processing computer architectures by distributing portions of the data among a plurality of processing elements. Algorithmic processing takes place until the system state reaches a point in which the necessary data becomes non-local to the processing elements. Hence, a re-distribution of data must be carried out prior to the next stage of algorithmic computation. Depending on the required state of data re-distribution, this operation can be very challenging to the communication system that ties the processing elements together.
Data re-distribution in system memory can pose additional challenges. System memory access is typically defined for a fixed set of increments and optimized for particular access patterns. As an example, a memory interface may only permit accesses of 64 or 128 bytes, and though system memory permits random access, it is understood by those skilled in the art that accessing contiguous address space is most efficient. Depending on the distribution of data within the multi-processor, and the required staging for the next phase of computation, a given processing element may require a large number of non-contiguous data accesses which are smaller than the allowable memory access sizes.
Current multi-processor performance suffers under the scenario where a small amount of data is scattered among several processing or storage elements. An example of a challenging data re-distribution occurs when a large number of unique data values must be distributed among a plurality of processing or memory elements for real time processing. A reverse situation occurs when many processing or memory elements must each individually send a small amount of data to a single location on the multi-processor.