A language for the specification and representation of programs in a data flow model of computation
Sang Yong Han · 1983
This dissertation defines and analyzes a functional data flow language which can be efficiently executed on the Texas Reconfiguable Array Computer (TRAC). The major issues which must be considered in the design and implementation of a data flow programming system are the representation and specification of parallel structures by a data flow language, the time of binding, the specification of computation units and the attainment of maximum parallelism. The research embodied in this dissertation consists of analyzing each of the solution options for these issues in the context of the TRAC architecture and selection of the appropriate solutions. The data flow language designed explores the representation capabilities of a data flow model for parallelism to specify total data flow language system. The data flow language is for function level parallelism. Thus the execution unit size is a function. The language can not only specify various types of parallelism but also be efficiently implemented on the TRAC. Given a data flow model and a data flow language, binding of values, processors and memory system can be done during compile time, load-time or run-time. It is shown that binding time is an architecture dependent factor, and there are several ways to construct queues associated with binding schemes. For the TRAC load-time binding is chosen. To maximize asynchrony and preserve the correct execution of data flow programs, values are tagged by time-stamps. Nondeterminacy can be viewed as an inevitable element of asynchrony. Implementation of nondeterminacy is shown in terms of colored Petri nets and guarded commands. Cycles in data dependencies can decrease the asynchrony due to the seqential execution of computations. By selecting proper timing point for acknowledgement signalling, it is possible to help maximize asynchrony, and at the same time, guarantee the safe execution of computations.