Usefulness of compile-time restructuring of large grain data flow programs in throughput-critical applications
Cross, David M.
Shukla, Shridhar B.
MetadataShow full item record
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
Showing items related by title, author, creator and subject.
Shukla, Shridhar B.; Little, Brian S.; Zaky, Amr (Monterey, California. Naval Postgraduate School, 1992-04); NPS-EC-92-007Efficient data-flow implementation requires fast run-time mechanisms to detect and dispatch schedulable tasks. However, the inherent non-determinism in data-flow executions and the requirement of fast, and therefore, simple ...
A periodic scheduling heuristic for mapping iterative task graphs onto distributed memory multiprocessors Kasinger, Charles D. (Monterey, California. Naval Postgraduate School, 1994-09);This thesis investigates the problem of statically assigning the tasks of applications represented by repetitive task graphs (such as sonar or radar signal processing) to the processors of a distributed memory multiprocessor ...
Bower, Mark E. (Monterey, California. Naval Postgraduate School, 1995-12);This thesis used action research to make restructuring recommendations for the Director of Military Operations (Code 04), Naval Postgraduate School (NPS). The restructuring recommendations were provided to assist Code 04 ...