Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-06T07:48:39.519Z Has data issue: false hasContentIssue false

4 - Hardware synthesis

Published online by Cambridge University Press:  03 May 2010

Ryan Kastner ,
Anup Hosangadi  and
Farzan Fallah
Ryan Kastner
Affiliation:
University of California, San Diego
Anup Hosangadi
Affiliation:
University of California, Santa Barbara
Farzan Fallah
Affiliation:
Stanford University, California
Get access

Summary

Chapter overview

This chapter provides a brief summary of the stages in the hardware synthesis design flow. It is designed to give unfamiliar readers a high-level understanding of the hardware design process. The material in subsequent chapters describes different hardware implementations of polynomial expressions and linear systems. Therefore, we feel that it is important, though not necessarily essential, to have an understanding of the hardware synthesis process.

The chapter starts with a high-level description of the hardware synthesis design flow. It then proceeds to discuss the various components of this design flow. These include the input system specification, the program representation, algorithmic optimizations, resource allocation, operation scheduling, and resource binding. The chapter concludes with a case study using an FIR filter. This provides a step-by-step example of the hardware synthesis process. Additionally, it gives insight into the hardware optimization techniques presented in the following chapters.

Hardware synthesis design flow

The initial stages of a hardware design flow are quite similar to the frontend of a software compiler. One of the biggest differences is that the input system specification languages are different. Hardware description languages must deal with many features that are unnecessary in software, which for the most part model execution in a serial fashion. Such features include the need to model concurrent execution of the underlying resources, define a variety of different data types specifically for different bit widths, and introduce some notion of time into the language.Figure 4.1 gives a high-level view of the different stages of hardware compilation.

Type
Chapter
Information
Arithmetic Optimization Techniques for Hardware and Software Design , pp. 35 - 67
Publisher: Cambridge University Press
Print publication year: 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Micheli, G., Synthesis and Optimization of Digital Circuits. New York, NY: McGraw-Hill, 1994.Google Scholar
Sarrafzadeh, M. and Wong, C. K., An Introduction to VLSI Physical Design. New York, NY: McGraw Hill, 1996.Google Scholar
Gajski, D. D., Zhu, J., Dömer, R., Gerstlauser, A., and Zhoa, S., Spec C: Specification Language and Methodology. Boston, MA: Kluwer Academic Publishers, 2000.CrossRefGoogle Scholar
Liao, S. Y., Towards a new standard for system-level design, in International Workshop on Hardware/Software Codesign San Diego, 2000, pp. 2–6. New York, NY: ACM, 2000.Google Scholar
Page, I., Constructing hardware-software systems from a single description, Journal of VLSI Signal Processing, 12, 87–107, 1996.CrossRefGoogle Scholar
Chao, H., Ravi, S., Raghunathan, A., and Jha, N. K., High-level synthesis of distributed logic-memory architectures, IEEE/ACM International Conference on Computer Aided Design San Jose, 2002. IEEE/ACM Digest of Technical Papers (Cat. No.02CH37391). pp. 564–71. New York, NY: ACM, 2002.CrossRefGoogle Scholar
Diniz, P. and Park, J., Automatic synthesis of data storage and control structures for FPGA-based computing engines, IEEE Symposium on Field-Programmable Custom Computing Machines, Napa Valley, 2000, pp. 91–100. Washington, DC: IEEE Computer Society, 2000.CrossRefGoogle Scholar
Semeria, L., Sato, K., and Micheli, G., Synthesis of hardware models in C with pointers and complex data structures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 9, 743–56, 2001.CrossRefGoogle Scholar
Mathworks Website, http://www.mathworks.com/
Synplicity Synplify DSP Website, http://www.synplicity.com/products/synplifydsp/
Aho, A. V., Ravi, S., and Ullman, J. D., Compilers: Principles, Techniques and Tools. Boston, MA: Addison-Wesley, 1986.Google Scholar
Muchnick, S. S., Advanced Compiler Design and Implementation. San Francisco, CA: Morgan Kaufmann Publishers, 1997.Google Scholar
Hecht, M. S., Flow Analysis of Computer Programs. New York, NY: Elsevier, 1977.Google Scholar
Pohlmann, K. C., Principles of Digital Audio. New York, NY: McGraw-Hill Professional, 2000.Google Scholar
Briggs, P., Harvey, T., and Simpson, L., Static Single Assignment Construction, Technical Report, Rice University, 1995.
Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., and Zadeck, F. K., Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems, 13, 451–90, 1991.CrossRefGoogle Scholar
Kastner, R., Gong, W., Hao, X., et al., Layout driven data communication optimization for high level synthesis, Design, Automation and Test in Europe, Munich, 2006, p. 6. Leuven: European Design and Automation Association.Google Scholar
Kaplan, A., Brisk, P., and Kastner, R., Data communication estimation and reduction for reconfigurable systems, in Design Automation Conference, Anaheim, 2003, pp. 616–21. New York, NY: ACM, 2003.
Ferrante, J., Ottenstein, K. J., and Warren, J. D., The program dependence graph and its use in optimization, ACM Transactions on Programming Languages & Systems, 9, 319–49, 1987.CrossRefGoogle Scholar
Gong, W., Wang, G., and Kastner, R., A high performance intermediate representation for reconfigurable systems, in International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA), Las Vegas 2004. CSREA Press, 2004.Google Scholar
Edwards, S. A., An Esterel compiler for large control-dominated systems, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21, 169–83, 2002.CrossRefGoogle Scholar
Ramasubramanian, N., Subramanian, R., and Pande, S., Automatic analysis of loops to exploit operator parallelism on reconfigurable systems, in International Workshop on Languages and Compilers for Parallel Computing, 1998, pp. 305–22. Springer Verlag, 1998.Google Scholar
Mano, M. M. and Kime, C., Logic and Computer Design Fundamentals, second edition Englewood Cliffs, NJ: Prentice Hall, 1999.Google Scholar
Elliott, J. P., Understanding Behavioral Synthesis: A Practical Guide to High-Level Design. Norwell, MA: Kluwer Academic Publishers, 1999.CrossRefGoogle Scholar
Virtex-II Pro Platform FPGA Data Sheet, Xilinx Inc. 2003.
Topcuoglu, H., Hariri, S., and Min-You, W., Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE Transactions on Parallel and Distributed Systems, 13, 260–74, 2002.CrossRefGoogle Scholar
Schutten, J. M. J., List Scheduling Revisited, Operation Research Letters, 18, 167–70, 1996.CrossRefGoogle Scholar
Poplavko, P., Eijk, C. A. J. v., and Basten, T., Constraint analysis and heuristic scheduling methods, Workshop on Circuits, Systems and Signal Processing, Veldhoven 2000, pp. 447–53. Utrecht: STW Technology Foundation, 2000.Google Scholar
Kolisch, R. and Hartmann, S., Project scheduling: recent models, algorithms and applications, Heuristic Algorithms for Solving the Resource-Constrained Project Scheduling Problem. Amsterdam: KluwerAcademic Publishers, 1999.Google Scholar
Sweany, P. H. and Beaty, S. J., Instruction scheduling using simulated annealing, International Conference on Massively Parallel Computing Systems, Colorado 1998. Los Amitos, CA: IEEE Computer Society Press, 1998.Google Scholar
Adam, T. L., Chandy, K. M., and Dickson, J. R., A comparison of list schedules for parallel processing systems, Communications of the ACM, 17, 685–90, 1974.CrossRefGoogle Scholar
Auyeung, A., Gondra, I., and Dai, H. K., Advances in Soft Computing: Intelligent Systems Design and Applications, Integrating Random Ordering into Multi-Heuristic List Scheduling Genetic Algorithm. Berlin: Springer Verlag, 2003.CrossRefGoogle Scholar
Grajcar, M., Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system, Design Automation Conference, New Orleans 1999, pp. 280–85. New York, NY: ACM, 1999.Google Scholar
Wang, G., Gong, W., DeRenzi, B., and Kastner, R., Ant colony optimizations for resource- and timing-constrained operation scheduling, IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems, 26, 1010–29, 2007.CrossRefGoogle Scholar
Paulin, P. G. and Knight, J. P., Force-directed scheduling for the behavioral synthesis of ASICs, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 8, 661–79, 1989.CrossRefGoogle Scholar
David, B., Michael, R., and Izidor, G., On the complexity of scheduling problems for parallel/pipelined machines, IEEE Transactions on Computers, 38, 1308–13, 1989.Google Scholar
Kent, W., Jack, L., and Mark, H., Optimal instruction scheduling using integer programming, SIGPLAN Notices, 35, 121–33, 2000.Google Scholar
Verhaegh, W. F. J., Aarts, E. H. L., Korst, J. H. M., and Lippens, P. E. R., Improved force-directed scheduling, Conference on European Design Automation, Amsterdam, 1991. Los Amitos. Washington, DC: IEEE Computer Society.Google Scholar
Verhaegh, W. F. J., Lippens, P. E. R., Aarts, E. H. L., et al., Efficiency improvements for force-directed scheduling, in IEEE/ACM International Conference on Computer-Aided Design, Santa Clara, 1992, pp. 286–291. New York, NY: ACM, 1992.CrossRefGoogle Scholar
Kernighan, B. W. and Lin, S., An efficient heuristic procedure for partitioning graphs, The Bell System Technical Journal, 49, 291–307, 1970.CrossRefGoogle Scholar
Heijligers, M. and Jess, J., High-level synthesis scheduling and allocation using genetic algorithms based on constructive topological scheduling techniques, International Conference on Evolutionary Computation, 1995, pp. 56–61. Piscataway, NJ: IEEE Press, 1995.Google Scholar
Sharma, A. and Jain, R., InSyn: integrated scheduling for DSP applications, IEEE Transactions on Signal Processing, 43, 1966–77, 1995.CrossRefGoogle Scholar
Adam, T. L., Chandy, K. M., and Dickson, J. R., A comparison of list schedules for parallel processing systems, Communications of the ACM, 17, 685–90, 1974.CrossRefGoogle Scholar
Beaty, S. J., Genetic algorithms versus Tabu search for instruction scheduling, International Conference on Artificial Neural Nets and Genetic Algorithms, 1993, pp. 496–501. New York, NY: Springer, 1993.CrossRefGoogle Scholar
Aleta, A., Codina, J. M., Sanchez, J., and Gonzalez, A., Graph-partitioning based instruction scheduling for clustered processors, ACM/IEEE International Symposium on Microarchitecture, Austin, 2001, pp. 150–59. Washington, DC: IEEE Computer Society, 2001.Google Scholar
Memik, S. Ogrenci, Bozorgzadeh, E., Kastner, R., and Sarrafzadeh, M., A super-scheduler for embedded reconfigurable systems, IEEE/ACM International Conference on Computer Aided Design, San Jose, 2001, pp. 391–94. Piscataway, NJ: IEEE Press, 2001.Google Scholar
Stutzle, T. and Hoos, H. H., MAX-MIN Ant System, Future Generations Computer Systems, 16, 889–914, 2000.CrossRefGoogle Scholar
Wang, G., Gong, W., Derenzi, B., and Kastner, R., Exploring time/resource trade-offs by solving dual scheduling problems with the ant colony optimization, ACM Transactions on Design Automation for Electronic Systems, 12, 46, 2007.CrossRefGoogle Scholar
Musoll, E. and Cortadella, J., “Scheduling and resource binding for low power,” Proceedings of the 8th International Symposium on System Synthesis Cannes, 1995. New York, NY: ACM, 1995.Google Scholar
Mentor Graphics Catapult C Synthesis Webpage, http://www.mentor.com/products/esl/high_level_synthesis/catapult_synthesis/
Park, I.-C. and Kyung, C. M., “Fast and near optimal scheduling in automatic datapath synthesis,” in Proceedings of the IEEE/ACM 28th Conference on Design Automation, San Francisco, 1991, pp. 680–81. New York, NY: 1991.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • Hardware synthesis
  • Ryan Kastner, University of California, San Diego, Anup Hosangadi, University of California, Santa Barbara, Farzan Fallah, Stanford University, California
  • Book: Arithmetic Optimization Techniques for Hardware and Software Design
  • Online publication: 03 May 2010
  • Chapter DOI: https://doi.org/10.1017/CBO9780511712180.005
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • Hardware synthesis
  • Ryan Kastner, University of California, San Diego, Anup Hosangadi, University of California, Santa Barbara, Farzan Fallah, Stanford University, California
  • Book: Arithmetic Optimization Techniques for Hardware and Software Design
  • Online publication: 03 May 2010
  • Chapter DOI: https://doi.org/10.1017/CBO9780511712180.005
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • Hardware synthesis
  • Ryan Kastner, University of California, San Diego, Anup Hosangadi, University of California, Santa Barbara, Farzan Fallah, Stanford University, California
  • Book: Arithmetic Optimization Techniques for Hardware and Software Design
  • Online publication: 03 May 2010
  • Chapter DOI: https://doi.org/10.1017/CBO9780511712180.005
Available formats
×