Back to search

Old Dominion University

Cyclo-Static Scheduling of Large Grain Dataflow Algorithms on a Local Area ATAMM Multicomputing Testbed

Abstract

dc:description.abstract

A 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 × 6

Rights

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

Chain of custody

source
Harvested from
Old Dominion University
Base URL
digitalcommons.odu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Roy, Sudeepto. Cyclo-Static Scheduling of Large Grain Dataflow Algorithms on a Local Area ATAMM Multicomputing Testbed. Thesis thesis, https://digitalcommons.odu.edu/ece_etds/499