Due to the massive complexity of contemporary embedded applications and integrated systems, long effort has been invested in high-level synthesis (HLS) and electronic system level (ESL) methodologies to automatically produce correct implementations from high-level, abstract, and executable specifications written in program code. If the HLS transformations that are applied on the source code are formal, then the generated implementation is correct-by-construction. The focus in this work is on application-specific design, which can deliver optimal, and customized implementations, as opposed to platform or IP-based design, which is bound by the limits and constraints of the preexisting architecture. This work surveys and reviews past and current research in the area of ESL and HLS. Then, a prototype HLS compiler tool that has been developed by the author is presented, which utilizes compiler-generators and logic programming to turn the synthesis into a formal process. The scheduler PARCS and the formal compilation of the system are tested with a number of benchmarks and real-world applications. This demonstrates the usability and applicability of the presented method. 1. Introduction During the last 3-4 decades, the advances on chip integration capability have increased the complexity of embedded and other custom VLSI systems to such a level that sometimes their spec-to-product development time exceeds even their product lifetime in the market. Because of this, and in combination with the high design cost and development effort required for the delivery of such products, they often even miss their market window. This problem generates competitive disadvantages for the relevant industries that design and develop these complex computing products. The current practice in the used design and engineering flows, for the development of such systems and applications, includes to a large extent approaches which are semimanual, ad-hoc, nonautomatically communicants from one level of the design flow to the next, and with a lot of design iterations caused by the discovery of functional and timing bugs, as well as specification to product requirements mismatches later in the development process. All of these issues have motivated industry and academia to invest in suitable methodologies and tools to achieve higher automation in the design of contemporary systems. Nowadays, a higher level of code abstraction is pursued as input to automated E-CAD tools. Furthermore, methodologies and tools such as high-level synthesis (HLS) and electronic system level (ESL) design
References
[1]
B. M. Pangrle and D. D. Gajski, “Design tools for intelligent silicon compilation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 6, no. 6, pp. 1098–1112, 1986.
[2]
E. F. Girczyc, R. J. A. Buhr, and J. P. Knight, “Applicability of a subset of Ada as an algorithmic hardware description language for graph-based hardware compilation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 4, no. 2, pp. 134–142, 1985.
[3]
P. G. Paulin and J. P. Knight, “Force-directed scheduling for the behavioral synthesis of ASIC's,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, no. 6, pp. 661–679, 1989.
[4]
I. C. Park and C. M. Kyung, “Fast and near optimal scheduling in automatic data path synthesis,” in Proceedings of the 28th ACM/IEEE Design Automation Conference, pp. 680–685, June 1991.
[5]
N. Park and A. C. Parker, “Sehwa: a software package for synthesis of pipelined data path from behavioral specification,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 7, no. 3, pp. 356–370, 1988.
[6]
E. F. Girczyc, “Loop winding—a data flow approach to functional pipelining,” in Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 382–385, 1987.
[7]
C. J. Tseng and D. P. Siewiorek, “Automatic synthesis of data path on digital systems,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 5, no. 3, pp. 379–395, 1986.
[8]
F. J. Kurdahi and A. C. Parker, “REAL: a program for register allocation,” in Proceedings of Design Automation Conference (DAC '87), pp. 210–215, Miami Beach, Fla, USA, 1987.
[9]
C. Y. Huang, Y. S. Chen, Y. L. Lin, and Y. C. Hsu, “Data path allocation based on bipartite weighted matching,” in Proceedings of the 27th ACM/IEEE Design Automation Conference, pp. 499–504, June 1990.
[10]
F. S. Tsay and Y. C. Hsu, “Data path construction and refinement. Digest of Technical papers,” in Proceedings of the The International Conference on Computer-Aided Design (ICCAD '90), pp. 308–311, Santa Clara, Calif, USA, 1990.
[11]
R. Camposano and W. Rosenstiel, “Synthesizing circuits from behavioral descriptions,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, no. 2, pp. 171–180, 1989.
[12]
S. D. Johnson, Synthesis of Digital Designs from Recursion Equations, MIT Press, Cambridge, Mass, USA, 1984.
[13]
M. R. Barbacci, G. E. Barnes, R. G. Cattell, and D. P. Siewiorek, “The ISPS computer description language,” Tech. Rep. CMU-CS-79-137, School of Computer Science, Carnegie Mellon University, 1979.
[14]
P. Marwedel, “The MIMOLA design system: tools for the design of digital processors,” in Proceedings of the 21st Design Automation Conference, pp. 587–593, 1984.
[15]
A. E. Casavant, M. A. d'Abreu, M. Dragomirecky et al., “Synthesis environment for designing DSP systems,” IEEE Design and Test of Computers, vol. 6, no. 2, pp. 35–44, 1989.
[16]
P. G. Paulin and J. P. Knight, “Algorithms for high-level synthesis,” IEEE Design and Test of Computers, vol. 6, no. 6, pp. 18–31, 1989.
[17]
D. D. Gajski and L. Ramachandran, “Introduction to high-level synthesis,” IEEE Design and Test of Computers, vol. 11, no. 4, pp. 44–54, 1994.
[18]
R. A. Walker and S. Chaudhuri, “Introduction to the scheduling problem,” IEEE Design and Test of Computers, vol. 12, no. 2, pp. 60–69, 1995.
[19]
V. Berstis, “V compiler: automating hardware design,” IEEE Design and Test of Computers, vol. 6, no. 2, pp. 8–17, 1989.
[20]
J. A. Fisher, “Trace Scheduling: a technique for global microcode compaction,” IEEE Transactions on Computers, vol. 30, no. 7, pp. 478–490, 1981.
[21]
A. Kuehlmann and R. A. Bergamaschi, “Timing analysis in high-level synthesis,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '92), pp. 349–354, November 1992.
[22]
T. C. Wilson, N. Mukherjee, M. K. Garg, and D. K. Banerji, “ILP solution for optimum scheduling, module and register allocation, and operation binding in datapath synthesis,” VLSI Design, vol. 3, no. 1, pp. 21–36, 1995.
[23]
C. A. Papachristou and H. Konuk, “A linear program driven scheduling and allocation method followed by an interconnect optimization algorithm,” in Proceedings of the 27th ACM/IEEE Design Automation Conference, pp. 77–83, June 1990.
[24]
J. Biesenack, M. Koster, A. Langmaier et al., “Siemens high-level synthesis system CALLAS,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 1, no. 3, pp. 244–252, 1993.
[25]
The Electronic Design Interchange Format, Wikipedia, the free encyclopedia, 2011, http://en.wikipedia.org/wiki/EDIF.
[26]
M. S. Rubin, “Computer Aids for VLSI Design. Appendix D: Electronic Design Interchange Format,” 2011, http://www.rulabinsky.com/cavd/text/chapd.html.
[27]
T. Filkorn, “A method for symbolic verification of synchronous circuits,” in Proceedings of the Computer Hardware Description Languages and their Applications (CHDL '91), pp. 229–239, Marseille, France, 1991.
[28]
A. Kalavade and E. A. Lee, “A hardware-software codesign methodology for DSP applications,” IEEE Design and Test of Computers, vol. 10, no. 3, pp. 16–28, 1993.
[29]
R. Ernst, J. Henkel, and T. Benner, “Hardware-software cosynthesis for microcontrollers,” IEEE Design and Test of Computers, vol. 10, no. 4, pp. 64–75, 1993.
[30]
G. De Micheli, D. Ku, F. Mailhot, and T. Truong, “The Olympus synthesis system,” IEEE Design and Test of Computers, vol. 7, no. 5, pp. 37–53, 1990.
[31]
A. Jerraya, I. Park, and K. O'Brien, “AMICAL: an interactive high level synthesis environment,” in Proceedings of the 4th European Conference on Design Automation with the European Event in ASIC, pp. 58–62, 1993.
[32]
D. E. Thomas, J. K. Adams, and H. Schmit, “A model and methodology for hardware-software codesign,” IEEE Design and Test of Computers, vol. 10, no. 3, pp. 6–15, 1993.
[33]
C. A. R. Hoare, Communicating Sequential Processes, Prentice-Hall, Englewood Cliffs, NJ, USA, 1985.
[34]
R. K. Gupta and G. De Micheli, “Hardware-software cosynthesis for digital systems,” IEEE Design and Test of Computers, vol. 10, no. 3, pp. 29–41, 1993.
[35]
I. Bolsens, H. J. De Man, B. Lin, K. Van Rompaey, S. Vercauteren, and D. Verkest, “Hardware/software co-design of digital telecommunication systems,” Proceedings of the IEEE, vol. 85, no. 3, pp. 391–417, 1997.
[36]
D. Genin, P. Hilfinger, J. Rabaey, C. Scheers, and H. De Man, “DSP specification using the Silage language,” in Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, pp. 1057–1060, April 1990.
[37]
P. Willekens, “Algorithm specification in DSP station using data flow language,” DSP Applications, vol. 3, no. 1, pp. 8–16, 1994.
[38]
N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud, “The synchronous data flow programming language LUSTRE,” Proceedings of the IEEE, vol. 79, no. 9, pp. 1305–1320, 1991.
[39]
M. Van Canneyt, “Specification, simulation and implementation of a GSM speech codec with DSP station,” DSP and Multimedia Technology, vol. 3, no. 5, pp. 6–15, 1994.
[40]
J. T. Buck, “PTOLEMY: a framework for simulating and prototyping heterogeneous systems,” International Journal in Computer Simulation, pp. 1–34, 1992.
[41]
R. Lauwereins, M. Engels, M. Ade, and J. A. Peperstraete, “Grape-II: a system-level prototyping environment for DSP applications,” Computer, vol. 28, no. 2, pp. 35–43, 1995.
[42]
M. S. Rafie, “Rapid design and prototyping of a direct sequence spread-spectrum ASIC over a wireless link,” DSP and Multimedia Technology, vol. 3, no. 6, pp. 6–12, 1994.
[43]
L. Séméria, K. Sato, and G. De Micheli, “Synthesis of hardware models in C with pointers and complex data structures,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 9, no. 6, pp. 743–756, 2001.
[44]
R. P. Wilson, “Suif: an infrastructure for research on parallelizing and optimizing compilers,” ACM SIPLAN Notices, vol. 28, no. 9, pp. 67–70, 1994.
[45]
A. A. Kountouris and C. Wolinski, “Efficient scheduling of conditional behaviors for high-level synthesis,” ACM Transactions on Design Automation of Electronic Systems, vol. 7, no. 3, pp. 380–412, 2002.
[46]
S. Gupta, R. K. Gupta, N. D. Dutt, and A. Nicolau, “Coordinated parallelizing compiler optimizations and high-level synthesis,” ACM Transactions on Design Automation of Electronic Systems, vol. 9, no. 4, pp. 441–470, 2004.
[47]
W. Wang and T. K. Tan, “A comprehensive high-level synthesis system for control-flow intensive behaviors,” in Proceedings of the 13th ACM Great Lakes symppsium on VLSI (GLSVLSI '03), pp. 11–14, 2003.
[48]
Z. P. Gu, J. Wang, R. P. Dick, and H. Zhou, “Incremental exploration of the combined physical and behavioral design space,” in Proceedings of the 42nd Design Automation Conference (DAC '05), pp. 208–213, 2005.
[49]
L. Zhong and N. K. Jha, “Interconnect-aware high-level synthesis for low power,” in Proceedings of the IEEE/ACM International Conference on Computer Aided Design (ICCAD '02), pp. 110–117, November 2002.
[50]
C. Huang, S. Ravi, A. Raghunathan, and N. K. Jha, “Generation of heterogeneous distributed architectures for memory-intensive applications through high-level synthesis,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 15, no. 11, pp. 1191–1203, 2007.
[51]
K. Wakabayashi, “C-based synthesis experiences with a behavior synthesizer, “Cyber”,” in Proceedings of the Design, Automation and Test in Europe, pp. 390–393, 1999.
[52]
W. Wang, A. Raghunathan, N. K. Jha, and S. Dey, “High-level synthesis of multi-process behavioral descriptions,” in Proceedings of the 16th IEEE International Conference on VLSI Design (VLSI ’03), pp. 467–473, 2003.
[53]
B. Le Gal, E. Casseau, and S. Huet, “Dynamic memory access management for high-performance DSP applications using high-level synthesis,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 16, no. 11, pp. 1454–1464, 2008.
[54]
K. Wakabayashi and H. Tanaka, “Global scheduling independent of control dependencies based on condition vectors,” in Proceedings of the 29th ACM/IEEE Design Automation Conference, pp. 112–115, June 1992.
[55]
S. Gupta, N. Dutt, R. Gupta, and A. Nicolau, “Dynamically increasing the scope of code motions during the high-level synthesis of digital circuits,” IEE Proceedings, vol. 150, no. 5, pp. 330–337, 2003.
[56]
E. Martin, O. Santieys, and J. Philippe, “GAUT, an architecture synthesis tool for dedicated signal processors,” in Proceedings of the IEEE International European Design Automation Conference (Euro-DAC '93), pp. 14–19, Hamburg, Germany, 1993.
[57]
M. C. Molina, R. Ruiz-Sautua, P. García-Repetto, and R. Hermida, “Frequent-pattern-guided multilevel decomposition of behavioral specifications,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 1, pp. 60–73, 2009.
[58]
K. Avnit, V. D'Silva, A. Sowmya, S. Ramesh, and S. Parameswaran, “Provably correct on-chip communication: a formal approach to automatic protocol converter synthesis,” ACM Transactions on Design Automation of Electronic Systems, vol. 14, no. 2, article 19, 2009.
[59]
J. Keinert, M. Streubuhr, T. Schlichter et al., “SystemCoDesigneran—automatic ESL synthesis approach by design space exploration and behavioral synthesis for streaming applications,” ACM Transactions on Design Automation of Electronic Systems, vol. 14, no. 1, article 1, 2009.
[60]
J. Falk, C. Haubelt, and J. Teich, “Efficient representation and simulation of model-based designs in SystemC,” in Proceedings of the Forum on Design Languages, pp. 129–134, Darmstadt, Germany, 2006.
[61]
S. Kundu, S. Lerner, and R. K. Gupta, “Translation validation of high-level synthesis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 4, pp. 566–579, 2010.
[62]
S. Paik, I. Shin, T. Kim, and Y. Shin, “HLS-1: a high-level synthesis framework for latch-based architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 5, pp. 657–670, 2010.
[63]
M. Rim and R. Jain, “Lower-bound performance estimation for high-level synthesis scheduling problem,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, no. 4, pp. 451–458, 1994.
[64]
S. Chaudhuri and R. A. Walker, “Computing lower bounds on functional units before scheduling,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 4, no. 2, pp. 273–279, 1996.
[65]
H. Mecha, M. Fernandez, F. Tirado, J. Septien, D. Mozos, and K. Olcoz, “Method for area estimation of data-path in high level synthesis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 2, pp. 258–265, 1996.
[66]
Y. M. Fang and D. F. Wong, “Simultaneous functional-unit binding and floorplanning. Digest of Technical Papers,” in Proceedings of the International Conference on Computer-Aided Design (ICCAD '94), pp. 317–321, Santa Clara, Calif, USA, 1994.
[67]
M. Munch, N. Wehn, and M. Glesner, “Optimum simultaneous placement and binding for bit-slice architectures,” in Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC '95), pp. 735–742, September 1995.
[68]
A. Ahmadi and M. Zwolinski, “Multiple-width bus partitioning approach to datapath synthesis,” in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS '07), pp. 2994–2997, May 2007.
[69]
R. Gupta and M. A. Breuer, “Partial scan design of register-transfer level circuits,” Journal of Electronic Testing, vol. 7, no. 1-2, pp. 25–46, 1995.
[70]
M. L. Flottes, D. Hammad, and B. Rouzeyre, “High level synthesis for easy testability,” in Proceedings of the European Design and Test Conference, pp. 198–206, Paris, France, 1995.
[71]
M. K. Dhodhi, F. H. Hielscher, R. H. Storer, and J. Bhasker, “Datapath synthesis using a problem-space genetic algorithm,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, no. 8, pp. 934–944, 1995.
[72]
A. Mujumdar, R. Jain, and K. Saluja, “Incorporating testability considerations in high-level synthesis,” Journal of Electronic Testing, vol. 5, no. 1, pp. 43–55, 1994.
[73]
M. Potkonjak, S. Dey, and R. K. Roy, “Synthesis-for-testability using transformations,” in Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC '95), pp. 485–490, September 1995.
[74]
F. F. Hsu, E. M. Rudnick, and J. H. Patel, “Enhancing high-level control-flow for improved testability. Digest of Technical Papers,” in Proceedings of the International Conference on Computer-Aided Design (ICCAD '96), pp. 322–328, San Jose, Calif, USA, 1996.
[75]
A. Raghunathan, S. Dey, and N. K. Jha, “Register-transfer level estimation techniques for switching activity and power consumption,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 158–165, November 1996.
[76]
J. Rabaey, L. Guerra, and R. Mehra, “Design guidance in the power dimension,” in Proceedings of the 1995 20th International Conference on Acoustics, Speech, and Signal Processing, pp. 2837–2840, May 1995.
[77]
R. Mehra and J. Rabaey, “Exploiting regularity for low-power design,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 166–172, November 1996.
[78]
A. Raghunathan and N. K. Jha, “Behavioral synthesis for low power,” in Proceedings of the IEEE International Conference on Computer Design, pp. 318–322, October 1994.
[79]
L. Goodby, A. Orailoglu, and P. M. Chau, “Microarchitectural synthesis of performance-constrained, low-power VLSI designs,” in Proceedings of the IEEE International Conference on Computer Design, pp. 323–326, October 1994.
[80]
E. Musoll and J. Cortadella, “Scheduling and resource binding for low power,” in Proceedings of the 8th International Symposium on System Synthesis, pp. 104–109, September 1995.
[81]
N. Kumar, S. Katkoori, L. Rader, and R. Vemuri, “Profile-driven behavioral synthesis for low-power VLSI systems,” IEEE Design and Test of Computers, vol. 12, no. 3, pp. 70–84, 1995.
[82]
R. San Martin and J. P. Knight, “Power-profiler: optimizing ASICs power consumption at the behavioral level,” in Proceedings of the 32nd Design Automation Conference, pp. 42–47, June 1995.
[83]
C. Trabelsi, R. Ben Atitallah, S. Meftali, J. L. Dekeyser, and A. Jemai, “A model-driven approach for hybrid power estimation in embedded systems design,” Eurasip Journal on Embedded Systems, vol. 2011, Article ID 569031, 2011.
[84]
I. Issenin, E. Brockmeyer, B. Durinck, and N. D. Dutt, “Data-reuse-driven energy-aware cosynthesis of scratch pad memory and hierarchical bus-based communication architecture for multiprocessor streaming applications,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 8, pp. 1439–1452, 2008.
[85]
D. S. Rao and F. J. Kurdahi, “Controller and datapath trade-offs in hierarchical RT-level synthesis,” in Proceedings of the 7th International Symposium on High-Level Synthesis, pp. 152–157, May 1994.
[86]
S. C. Y. Huang and W. H. Wolf, “How datapath allocation affects controller delay,” in Proceedings of the 7th International Symposium on High-Level Synthesis, pp. 158–163, May 1994.
[87]
UML 2.0, 2012, http://www.omg.org/spec/UML/2.0/.
[88]
Model Transformation Framework, 2012, http://www.alphaworks.ibm.com/tech/mtf.
[89]
UML MARTE, 2012, http://www.omgwiki.org/marte/.
[90]
MARTE specification version 1.0., 2012, http://www.omg.org/spec/MARTE/1.0/PDF/.
[91]
The Eclipse Software, 2012, http://en.wikipedia.org/wiki/Eclipse_(software).
M. Dossis, “Intermediate predicate format for design automation tools,” Journal of Next Generation Information Technology, vol. 1, no. 1, pp. 100–117, 2010.
[94]
U. Nilsson and J. Maluszynski, Logic Programming and Prolog, John Wiley & Sons, 2nd edition, 1995.
