Parallel algorithms for computational geometry utilizing a fixed number of processors /
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1988.
|
| Subjects: | |
| Online Access: | ProQuest, Abstract Link to OAKTrust copy Link to ProQuest copy |
| Abstract: | As computations on sequential machines reach physical limits, the need for parallel computing arises. The spectrum of parallel approaches ranges from computation dominated systems using a few processors with limited communication to systems utilizing thousands of processors each doing limit computation with communication costs dominant. The design of algorithms for systems where both communication and computation are important is presented. Approaches to parallel computation and the underlying theoretical models are surveyed. Two models of computation are developed, both based on a divide-and-conquer strategy. The first utilizes a tree-like merge resulting in several levels of communication and computation, the total number determined by the number of processors. The second model contains a fixed number of levels independent of the number of processors. Using the notation from the survey and the models of computation, algorithms are designed for the computational geometry problems of finding the convex hull and Delaunay triangulation for a set of uniform random points in the Euclidean plane. Communication and computation timing measurements based on these algorithms are presented and analyzed. The results are then generalized to predict the behavior of expanded problems. Architectural support, partitioning issues, and limitations of this approach are discussed. Finally, conclusions are presented and areas of future research are suggested. |
|---|---|
| Item Description: | Typescript (photocopy). Vita. "Major subject: Computer Science." |
| Physical Description: | xvi, 181 leaves : illustrations ; 29 cm |
| Bibliography: | Includes bibliographical references (leaves 128-135). |