Downloads & Free Reading Options - Results

This document presents a language and graph representation designed to aid in the partitioning of large signal processing applications into tasks to run on a multiprocessor. This language compiles directly into a program graph upon which optimizations are performed to find the optimal task configuration. The optimal task configuration is one in which computation-to-communication is minimized while throughput is maximized. The language and graph are designed to express coarse-grain parallelism so that large communication delays and task overhead do not outweigh the speedup achieved by exploiting the parallelism in the application. The data flow model underlying the graph representation is based on a distributed, loosely-coupled multiprocessor concept which supports tagged data flow at the operating system level. The approach utilized in the graph and language is to insert specific, data, routing operators into the data flow graph defined by the application. These operators shape and route data through the application and express all the coarse-grain parallelism which is exploitable in the model. Data routing operators are parameterized to reflect the degree of parallelism, i.e., the number of parallel tasks in a partition of the application. The graph constructs also contain sufficient information to describe fully the task structure of the application. Given the characteristics of the partition, the programmer can define a standard by which the 'goodness' of the partition is evaluated. Given this standard, algorithms to perform the evaluation can be developed. The ultimate goal is the development of algorithms to perform the entire partitioning process automatically.