Degree Type

Dissertation

Date of Award

1991

Degree Name

Doctor of Philosophy

Department

Computer Science

First Advisor

Gurpur M. Prabhu

Abstract

During the past decade there has been a tremendous surge in understanding the nature of parallel computation. A number of parallel computers are commercially available. However, there are some problems in developing application programs on these computers;This dissertation considers various issues involved in implementing parallel algorithms on Multiple Instruction Multiple Data (MIMD) machines with a bounded number of processors. Strategies for implementing divide-and-conquer algorithms on MIMD machines are proposed. Results linking time complexity, communication complexity and the complexity of divide-and-combine functions of divide-and-conquer algorithms are analyzed. An efficient criterion for partitioning a parallel program is proposed and a method for obtaining a closed form expression for time complexity of a parallel program in terms of problem size and number of processors is developed.

DOI

https://doi.org/10.31274/rtd-180813-9233

Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu/

Copyright Owner

Lakshmankumar Mukkavilli

Language

en

Proquest ID

AAI9126227

File Format

application/pdf

File Size

95 pages

Share

COinS