Accession Number:

ADA218733

Title:

Locality in Parallel Computation

Descriptive Note:

Master's thesis

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1989-09-01

Pagination or Media Count:

161.0

Abstract:

This thesis explores strategies for exploiting locality in three major areas of parallel computation packet routing, graph algorithms, and network emulations. Chapter 1 describes a network-independent approach to the packet-routing problem. Our strategy is to partition the problem into two stages a path-selection stage and a scheduling stage. Chapter 2 introduces a model for parallel computation, called the distribution random-access machine DRAM, in which the communication requirements of parallel computer in which memory accesses are evaluated. A DRAM is an abstraction of a parallel computer in which memory accesses are implemented by routing messages through a communication network. Chapter 3 examines the problem of how efficiently a host network can emulate a guest network. The goal is to emulate TG steps of an NG-node guest network on an NH node host network. Chapter 4 presents an algorithm for finding a minimum-cost spanning tree of an N-node graph on an N x N mesh-connected computer. The algorithm has the same ON running time as the previous algorithms, but it is much simpler. Keywords Fixed connection networks Area universal networks Fat trees Distributed random-access machines Theses.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE