Gibbons, Alan (Alan M.) (1988) Dynamic expression evaluation in one of a class of problems which are efficiently solvable on mesh-connected computers. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Preview

PDF (Department of Computer Science Research Report) WRAP_cs-rr-131.pdf - Other - Requires a PDF viewer. Download (562Kb) | Preview

Request Changes to record.

Abstract

Let P be a recursively described and distributable problem of size n. We describe a general strategic approach which will often make an O(√n) parallel time solution of P possible on a 2-dimensional mesh-connected computer with O(n) PEs. Such a solution is time-optimal. It is likely that the class of such problems is large and will contain many that are non-trivial. We show that such a problem is dynamic expression evaluation. The methodology is easily extended to mesh-connected computers of arbitrary dimension to again obtain time-optimal solutions using O(n) processors.

Item Type:	Report
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH):	Parallel processing (Electronic computers)
Series Name:	Department of Computer Science research report
Publisher:	University of Warwick. Department of Computer Science
Official Date:	September 1988
Dates:	Date Event September 1988 Completion
Number:	Number 131
Number of Pages:	10
DOI:	CS-RR-131
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Status:	Not Peer Reviewed
Publication Status:	Unpublished
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads