Area optimization of dataflow-graph mappings
B. Robič, P. Kolbezen, J. Šilc
Parallel Computing, 1992, 18(3): 297-311
The problem of area efficient mapping of dataflow program graph onto a data-driven hexagonally connected array is examined. A particular mapping scheme is analyzed to show that, in general, it results in a low area utilization. An optimization method for reducing the hosting area, called graph compaction, is introduced. The method was inspired by dynamic physical systems. Two possible implementations, based on Iterative Improvement and Simulated Annealing algorithms are given. Several measures are defined for evaluating the quality of the graph compaction. Using basic mapping scheme augmented with graph compaction, bigger graphs can be mapped on a given array and the communication delay is reduced. The experimental results justify the use of graph compaction as an improvement of the main mapping scheme.
BIBTEX copied to Clipboard