New Coding Techniques for Improved Bandwidth Utilization

The introduction of parallel models that account for communication between processors has shown that interprocessor bandwidth is often the limiting factor in parallel computing. In this paper, we introduce a new coding technique for transmitting the XOR of carefully selected patterns of bits to be communicated which greatly reduces bandwidth requirements in some settings. This technique has broader applications. For example, we demonstrate that the coding technique has a surprising application to a simple I/O (Input/Output) complexity problem related to finding the transpose of a matrix. Our main results are developed in the PRAM(M) model, a limited bandwidth PRAM model where P processors communicate through a small globally shared memory of M bits. We provide new algorithms for the problems of sorting and permutation routing. For the concurrent read PRAM(M), as P grows with M held constant, our sorting algorithm outperforms any previous algorithm by /spl Omega/(log/sup c/ P) for any constant c. The combination of a known lower bound for sorting in the exclusive read PRAM(M) model and this algorithm implies that the concurrent read PRAM(M) is strictly more powerful than the exclusive read PRAM(M).

Authors

• Micah Adler

Keywords

• Bandwidth
• Sorting
• Application software
• Computer science
• Phase change random access memory
• Source Code
• Time Step
• Running Time
• Row Vector
• Binary Matrix
• Transpose Of Matrix
• Limited Bandwidth
• Public Key
• Internal Memory
• Additional Memory
• Permutation Matrix
• P Matrix
• Sorting Algorithm
• P-block
• External Memory
• Entries In Column
• N Words
• Number Of Keys
• Calculation Steps
• Complex Problems
• Canonical Order
• Random Permutations
• Cardinality
• Sorts Of Problems
• Amount Of Memory
• Single Column