Usefulness of compile-time restructuring of large grain data flow   programs in throughput-critical applications
By:  David M. Cross
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1993
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 47
Description: 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.
Notes: Thesis advisor(s): Shridhar B. Shukla ; Amr Zaky.

"September 1993."

Cover title: Usefulness of  ... of LGDF programs ...

Thesis (M.S. in Electrical Engineering and M.S. in Computer Science) Naval Postgraduate School, September 1993.

Includes bibliographical references.

Approved for public release; distribution unlimited.

Also available online.

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

US Army (USA) author.