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

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