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.
