Title

Scalable parallel algorithms for random data accesses and shared-memory simulation

Date of Award

1996

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Sanjay Ranka

Keywords

Computer science

Subject Categories

Computer Sciences

Abstract

This dissertation focuses on scalable parallel algorithms for irregular communication, random data accesses, and shared memory simulation on a coarse-grained parallel machine. It contains the first deterministic, optimal and communication-efficient algorithm, the transportation algorithm, for dealing with irregular communication. The transportation algorithm forms the basis for performing dynamic permutations (one-to-one random data accesses) and random data accesses with hot spots (one-to-many and many-to-one accesses). These results are expected to be of interest to researchers in parallel algorithms, in the design of scalable runtime libraries for parallel languages such as High Performance Fortran, and in the building of parallel applications in a relatively architecture-independent fashion. The final part of this dissertation uses the results of the irregular communication and random data access algorithms in the simulation of shared memory on a distributed memory parallel machine. The simulation algorithms are further extended to deal with content-addressable shared memory.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=740243281&sid=2&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS