Divide-and-conquer algorithms for multiprocessors

Thumbnail Image
Date
1991
Authors
Mukkavilli, Lakshmankumar
Major Professor
Advisor
Gurpur M. Prabhu
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
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.

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
dissertation
Comments
Rights Statement
Copyright
Tue Jan 01 00:00:00 UTC 1991
Funding
Subject Categories
Supplemental Resources
Source