
The Library
Dynamic expression evaluation in one of a class of problems which are efficiently solvable on mesh-connected computers
Tools
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)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-131.pdf - Other - Requires a PDF viewer. Download (562Kb) | Preview |
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, Engineering and Medicine > 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: |
|
||||
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: |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year