List Ranking and List Scan on the CRAY C-90

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...

Full description

Saved in:
Bibliographic Details
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
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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