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

Request Changes to record.

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 (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:	pdf
Extent:	[5], 147 leaves : illustrations
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads