Accession Number:

ADA326070

Title:

Efficient Computation on Sparse Interconnection Networks.

Descriptive Note:

Doctoral thesis,

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Plaxton, C. G.

Report Date:

1989-09-08

Pagination or Media Count:

121.0

Abstract:

This thesis presents fast hypercube and shuffle-exchange algorithms for certain load balancing, selection and sorting problems. Non-trivial lower bounds are established for load balancing and selection. In addition, efficient network implementations of the parallel prefix operation and of the elementary Boolean matrix multiplication algorithm are described.

Descriptors:

• *ALGORITHMS
• *COMPUTER COMMUNICATIONS
• *PARALLEL PROCESSING
• OPTIMIZATION
• COMPUTATIONS
• DATA MANAGEMENT
• INFORMATION EXCHANGE
• DISTRIBUTED DATA PROCESSING
• THESES
• MULTIPROCESSORS
• COMPUTER NETWORKS

Subject Categories:

• Computer Systems
• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE