Back to search

Monterey, California. Naval Postgraduate School

Usefulness of compile-time restructuring of large grain data flow programs in throughput-critical applications

Abstract

dc:description.abstract

In this thesis, Large Grain Data Flow (LGDF) representation of parallelism is applied to throughout-critical applications that process periodically arriving data. The applications are represented by directed acyclic graphs in which a vertex represents an indivisible node program execution and an arc represents data flow from its source node to sink node. The machine and graph parameters are assumed to be such that the time to transfer one unit of data is comparable to the time to execute one operation at a processor. The machine model consists of a set of processors connected to a set of memory modules by a cross-bar interconnection network Execution of LGDF graphs on such machines either requires a run-time mechanism to dispatch executable nodes on available processors or a compile-time static scheduling of nodes to processors. The former approach, although flexible and robust, suffers from contention- related overhead and the latter, although capable of eliminating contention, is rigid and computationally intensive. It is shown by simulation that throughput can be improved when compile-time graph restructuring is coupled with simple first-come-first-serve dispatching. The restructuring is based on selectively adding control dependencies between graph nodes. This technique, called the revolving cylinder analysis, is shown to be an effective framework for achieving communication/computation overlap and reducing memory contention

Degree

thesis:*
Name thesis:degree_name
M.S. in Electrical Engineering
Level thesis:degree_level
Masters
Discipline thesis:degree_discipline
Electrical Engineering
Department dc:contributor.department
Electrical Engineering
College dc:contributor.school
Naval Postgraduate School
Grantor dc:publisher
Monterey, California. Naval Postgraduate School
Year dc:date.issued
1993

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cross, David M.
Advisors dc:contributor.advisor
  • Shukla, Shridhar B.
  • Zaky, Amr

Rights

dc:rights
Statement dc:rights
  • Approved for public release; distribution is unlimited.

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10945/26318

Chain of custody

source
Harvested from
Naval Postgraduate School
Base URL
calhoun.nps.edu/server/oai/request
Last updated
2026-11-20
Source record
OAI-PMH GetRecord
related terms
citation

Cross, David M.. Usefulness of compile-time restructuring of large grain data flow programs in throughput-critical applications. Masters thesis, Monterey, California. Naval Postgraduate School, 1993. https://hdl.handle.net/10945/26318