No Access

AN EVOLUTIONARY ALGORITHM FOR THE ALLOCATION PROBLEM IN HIGH-LEVEL SYNTHESIS

HAIDAR M. HARMANANI

Department of Computer Science, Lebanese American University, Byblos, 1401 2010, Lebanon

Search for more papers by this author

and

RONY SALIBA

ABEO, Ideal Communication, P. O. Box 11-6876, Beirut, Lebanon

Search for more papers by this author

https://doi.org/10.1142/S0218126605002362Cited by:3 (Source: Crossref)

Abstract

This paper presents an evolutionary algorithm to solve the datapath allocation problem in high-level synthesis. The method performs allocation of functional units, registers, and multiplexers in addition to controller synthesis with the objective of minimizing the cost of hardware resources. The system handles multicycle functional units as well as structural pipelining. The proposed method was implemented using C++ on a Linux workstation. We tested our method on a set of high-level synthesis benchmarks, all yielding good solutions in a short time. An integration path to Field Programmable Gate Arrays (FPGAs) is provided through VHDL.

Keywords:

References

M. McFarland, A. Parker and R. Compasano, Proc. IEEE 78, 301 (1990). Crossref, Web of Science, Google Scholar
M. Garey and D. S. Johnson , Computer and Intractability ( W. H. Freeman , 1979 ) . Google Scholar
D. Fogel , Evolutionary Computation: Toward a New Philosophy of Machine Intelligence ( IEEE Press , 1995 ) . Google Scholar
C. Gebotys and M. Elmasri, VLSI design synthesis with testability, Proc. 25th Design Automation Conf. (1988) pp. 16–21. Google Scholar
R. Jain et al. , Experience with the Adam synthesis system , Proc. 26th Design Automation Conf. ( 1989 ) . Google Scholar
J. Nestor and G. Krishnamoorthy, IEEE Trans. CAD 12, 1107 (1993). Crossref, Web of Science, Google Scholar
P. Paulin and J. P. Knight, IEEE Trans. CAD 8, 661 (1989). Crossref, Web of Science, Google Scholar
J. Rabaeyet al., Silicon Compilation, ed. D. Gajski (Addison Wesley, 1988) pp. 311–360. Google Scholar
D. E. Thomaset al., The System Architects Workbench, Proc. 25th Design Automation Conf. (1988) pp. 337–343. Google Scholar
S. Devadas and R. Newton, IEEE Trans. CAD 8, 768 (1989). Crossref, Web of Science, Google Scholar
N. Wehn, M. Held and M. Glesner, A novel scheduling/allocation approach for datapath synthesis based on genetic paradigms, Proc. TC10/W10.5 Workshop Logic and Architectural Synthesis (1990) pp. 47–56. Google Scholar
T. Ly and J. Mowchenko, IEEE Trans. CAD 12, 389 (1993). Crossref, Web of Science, Google Scholar
R. Martin and J. Knight, Genetic algorithms for optimization of integrated circuit synthesis, Proc. 5th Int. Conf. GA and Their Applications (1993) pp. 432–438. Google Scholar
M. Dhodhiet al., IEEE Trans. CAD 14, 934 (1995). Crossref, Web of Science, Google Scholar
T. Blickle, J. Teich and L. Thiele, J. Design Automation for Embedded Syst. 3, 23 (1998). Crossref, Web of Science, Google Scholar
C. Mandal, P. Chakrabarti and S. Ghose, IEEE Trans. VLSI 8, 747 (2000). Crossref, Google Scholar
G. De Micheli , Synthesis and Optimization of Digital Circuits ( McGraw Hill , 1994 ) . Google Scholar
0.35 μm CMOS digital standard cell databook, austriamicrosystems (2001) . Google Scholar
D. Gajski et al. , High-Level Synthesis: Introduction to Chip and System Design ( Kluwer Academic Publishers , 1992 ) . Crossref, Google Scholar
F. Kurdahi and A. Parker, REAL: A program for register allocation, Proc. 24th Design Automation Conf. (1987) pp. 210–215. Google Scholar
B. M. Pangrle, Splicer: A heuristic approach to connectivity binding, Proc. 25th Design Automation Conf. (1988) pp. 536–541. Google Scholar
C. Tseng and D. P. Siewiorek, IEEE Trans. CAD 5, 379 (1986). Crossref, Google Scholar
K. Kucukcakar and A. C. Parker, MABAL: A software package for module and bus allocation, Technical Report CRI-88-61, University of Southern California (1989) . Google Scholar