Old Dominion University
Cyclo-Static Scheduling of Large Grain Dataflow Algorithms on a Local Area ATAMM Multicomputing Testbed
Abstract
dc:description.abstractA strategy for cyclo-statically scheduling deterministic large grain dataflow (LGDF) algorithms for distributed execution on loosely coupled multicomputer architectures is presented in this research. The computational paradigm used is the ODU/NASA developed Algorithm To Architecture Mapping Model (ATAMM), which consists of marked graphs and Gantt chart representations that model the iterative execution of deterministic LGDF algorithms for different values of throughput and computation time. It is postulated that the behavior of these algorithms could be represented by the aggregate execution of an ensemble of cyclically shifted threads of a specific node sequence. Assuming the existence of one or more such sequences, a cyclo-static scheduling policy for mapping LGDF nodes onto processors for different relative iterations is proposed. A scheduling policy is classified as fully cyclo-static, block cyclo-static or static based on the relationship between nodes, iteration numbers and processors. The scheduling policy forms the basis of a distributed ATAMM Multicomputer Operating System (AMOS), which allows processors to concurrently participate in distributed dataflow and node scheduling operations. A distributed AMOS has been developed and implemented on a multicomputing testbed comprised of local area networked personal computers. Experimental results that confirm the veracity of the scheduling policy are reported. The communication overhead of the message passing mechanism of the testbed is quantitatively analyzed. Benefits claimed of this scheduling approach are, reduction in scheduling overhead, distribution of AMOS operations and the potential for using heterogeneous multicomputers.
Degree
thesis:*- Name thesis:degree_name
- Master of Science (MS)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Electrical & Computer Engineering
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Roy, Sudeepto
- Contributors dc:contributor
-
- John W. Stoughton
- Roland R. Mielke
- James F. Leathrum
Subjects
dc:subject × 6Rights
dc:rights- Statement dc:rights
-
- <p>In Copyright. URI: <a href="http://rightsstatements.org/vocab/InC/1.0/">http://rightsstatements.org/vocab/InC/1.0/</a> This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).</p>
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.odu.edu/ece_etds/499