Accession Number:

ADA276411

Title:

List Ranking and List Scan on the CRAY C-90

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Report Date:

1994-02-16

Pagination or Media Count:

38.0

Abstract:

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 Ologn 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 Olog 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

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE