List Ranking and List Scan on the CRAY C-90

• Main Authors: Reid-Miller, Margaret, Blelloch, Guy E
• Format: Report
• Language: English
• Subjects: ACCESS; ALGORITHMS; Computer Hardware; CONSTANTS; CONTRAST; DATA PROCESSING; DYNAMICS; EFFICIENCY; EQUATIONS; GRAIN SIZE; GRAPHS; LOOPS; MACHINES; MULTIPROCESSORS; OPERATION; OPTIMIZATION; PARALLEL PROCESSING; RANKING; SCANNERS; SUPERCONDUCTORS; TEST AND EVALUATION; TIME; TREES; VECTOR ANALYSIS

List ranking and list scan are two primitive operations used in many parallel algorithms that use list, trees, and graph data structures. But vectorizing and parallelizing list ranking is a challenge because it is highly communication intensive and dynamic. In addition, the serial algorithm is very simple and has very small constants. In order to compete a parallel algorithm must also be simple and have small constants. A parallel algorithm due to Wyllie is such an algorithm, but it is not work efficient-its performance degrades for longer and longer linked lists. In contrast, work efficient PRAM algorithms developed to date have very large constants. We introduce a new fully vectorized and parallelized algorithm that both is work efficient and has small constants. However, it does not achieve O(logn) running time. But we contend that work efficiency and small constants is more important, given that vector and multiprocessor machines are used for problems that are much larger than the number of processors and, therefore, the O(log n) time is never achieved in practice. In particular, to the best of our knowledge our implementation of list ranking and list scan on the CRAY C-90 is the fastest implementation to date. In addition, it is the first implementation of which we are aware that outperforms fast workstations. List ranking, List scan, Prescan, Prefix-sum, Bulk synchronous processor (BSP) model, Parallel algorithm, Vector algorithm, Linked list, Load balancing, Randomized algorithm, Vector multiprocessor, CRAY Y-MPC-90