Divide-and-conquer algorithms for multiprocessors

Date
1991
Authors
Mukkavilli, Lakshmankumar
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
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.

Description
Keywords
Computer science
Citation
Source