Parberry, Ian (1984) A complexity theory of parallel computation. PhD thesis, University of Warwick.
Preview |
PDF
WRAP_Theses_Parberry_1984.pdf - Submitted Version - Requires a PDF viewer. Download (5MB) | Preview |
Abstract
Parallel complexity theory is currently one of the fastest growing fields of theoretical computer science. This rapid growth has led to a proliferation of parallel machine models and theoretical frameworks. Our aim is to construct a unified theory of parallel computation based on a network model. We claim that the network paradigm is fundamental to the understanding of parallel computation. and support this claim by providing new and Improved theoretical results, and new approaches to old questions concerning "reasonable" and "practical" models.
This thesis is made up of eight chapters. Chapter 1 contains the introduction. In chapter 2 we define the basic model, and justify our choice of a unit- cost measure of time, a uniform assignment of programs to processors, and simultaneous processor activation. Chapter 3 compares the network model to a variety of others, including ' fixed-structure networks and shared-memory machines. We explore the concepts of "reasonableness” and "practicality" in parallel machine models, and show that even "reasonable" parallel computers are much taster than sequential ones.
Chapter 4 is devoted to programming techniques for a "practical” network model, (which we call a feasible network), covering interconnection patterns, useful algorithms, and some processor-saving theorems. In chapter 5 we find efficient simulations of the general network model on more practical machines, including a universal feasible network, and uniform circuits.
Chapter 6 extends the network model, and defines a new resource, that of arity. Although increasing arity Increases computing power, some efficient constant-arity universal machines are found. Chapter 7 takes a final look at universal networks, concentrating on lower-bounds and the conditions under which they hold. Chapter 6 contains the conclusion.
| Item Type: | Thesis [via Doctoral College] (PhD) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Library of Congress Subject Headings (LCSH): | Computational complexity, Parallel processing (Electronic computers) |
| Official Date: | May 1984 |
| Dates: | Date Event May 1984 UNSPECIFIED |
| Institution: | University of Warwick |
| Theses Department: | Department of Computer Science |
| Thesis Type: | PhD |
| Publication Status: | Unpublished |
| Supervisor(s)/Advisor: | Paterson, Michael S. |
| Sponsors: | Commonwealth Scholarship Commission in the United Kingdom |
| Format of File: | |
| Extent: | [5], 147 leaves : illustrations |
| Language: | eng |
| URI: | https://wrap.warwick.ac.uk/112008/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |