A parallel ant colony optimization to globally optimize area in high-level synthesis. (c2011)

Abstract

Data path synthesis is still regarded by researchers as one of the hardest problems in high level synthesis, the process of transforming a hardware descriptive language model, which describes the behavior of a given design to an actual register-transfer level or structural design. Despite the progress that has been achieved in this field of research, there is still an inevitable necessity for new techniques that achieve better area, timing, and power results for this NP-hard problem. In contrast with previous approaches which divide the high-level synthesis problem into sub-tasks and optimize each task independently in an attempt to reduce its complexity, this work proposes a novel technique using the ant colony optimization, which respects this division but establishes efficient communication between these different interdependent tasks. Substantial modifications are added to the ant colony optimization, most importantly a perturbation factor allowing the ants to visit previously unexplored solutions due to the nature of the binding problem. To test the efficiency of the proposed technique, specific resource bags were designed for a large set of benchmarks of different complexities. The proposed approach yielded an overall average of 6.8% improvement in area for all tested benchmarks and allows an easy transition to a parallel programming paradigm which benefits from the concept of parallel agents present in the ant colony optimization. The parallel execution makes the proposed technique an appealing solution, easily mappable to and well-suited for the omnipresent multi-core and multi-processing computing platforms. A parallel implementation using message passing in java was developed to prove the effectiveness of the proposed parallel model. Rigorous testing of this model on an 8-core machine, showed more than eighty four percent utilization of the parallel environment allowing the proposed technique to run 6.7 times faster than the single-threaded approach.