Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays

Regular arrays of processing elements in VLSI have proved to be suitable for high-speed execution of many matrix operations . To execute an arbitrary computational algorithm on such processing arrays, it has been suggested mapping the given algorithm directly onto a regular array . The computational algorithm is represented by a data-flow graph whose nodes are to be mapped onto processors in the VLSI array . This study examines the complexity of mapping data-flow graphs onto square and hexagonal arrays of processors . We specifically consider the problem of routing data from processors in a given (source) sequence to another (target) sequence . We show that under certain conditions, the above problem is equivalent to the one of finding a minimum-diameter cyclic arrangement . The complexity of the latter problem is analyzed and upper and lower bounds on the number of intermediate rows of processors (between the source and target rows) are derived .