Skip Navigation

The Computer Journal 1990 33(4):330-336; doi:10.1093/comjnl/33.4.330
© 1990 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (2)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Burton, F. W.
Right arrow Articles by Rayward-Smith, V. J.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Applications of UET Scheduling Theory to the Implementation of Declarative Languages

F. W. Burton1 * ¶, G. P. McKeown2 § {ddagger} and V. J. Rayward-Smith2 §

1 School of Computing Sciences, Simon Fraser University, Burnaby, British Columbia, Canada, V5A 1S6, 2 School of Information Systems, University of East Anglia, Norwich, NR4 7TJ, UK

Motivated by our interest in the use of functional programming languages to write parallel programs, we have been led to consider the anomaly of more processors possibly leading to a slower execution time. After reviewing known results from the theory of list-scheduling, we introduce generalisations of the familiar breadth-first and depth-first tree-searching algorithms to arbitrary dags and consider them in a list-scheduling framework. We prove that with UET actions (corresponding to pre-emptive scheduling with integer execution times for actions), breadth-first scheduling never leads to an increase in the execution time when the number of processors is increased. We also prove that for any list-scheduling algorithm with UET actions, there is no speed-up anomaly when going from two to three processors.

Received April 1986. revised April 1987.

* School of Computing Sciences, Simon Fraser University, Burnaby, British Columbia, Canada, V5A 1S6

§ School of Information Systems, University of East Anglia, Norwich NR4 7TJ.

The work of this author was supported by the National Science Foundation under grant no. ECS-8312748 and grant no. DMC-8514946.

{ddagger} To whom correspondence should be addressed.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.