Skip to main content
SpringerLink
Log in

Methods and Tools for Mapping Process Networks onto Multi-Processor Systems-On-Chip

  • Chapter
  • First Online:
Handbook of Signal Processing Systems

Abstract

Applications based on the Kahn process network (KPN) model of computation are determinate, modular, and based on FIFO communication for inter-process communication. While these properties allow KPN applications to efficiently execute on multi-processor systems-on-chip (MPSoC), they also enable the automation of the design process. This chapter focuses on the second aspect and gives an overview of methods for automating the design process of KPN applications implemented on MPSoCs. Whereas previous chapters mainly introduced techniques that apply to restricted classes of process networks, this overview will be dealing with general Kahn process networks.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
Â¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 22879
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
JPY 28599
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Kienhuis, B., Deprettere, E., Vissers, K., van der Wolf, P.: An Approach for Quantitative Analysis of Application-Specific Dataflow Architectures. In: Proc. Int’l Conf. on Application- Specific Systems, Architectures and Processors (ASAP), Washington, DC, USA (July 1997) 338–349

    Google Scholar 

  2. Densmore, D., Sangiovanni-Vincentelli, A., Passerone, R.: A Platform-Based Taxonomy for ESL Design. IEEE Design & Test of Computers 23(5) (May 2006) 359–374

    Article  Google Scholar 

  3. Kahn, G.: The Semantics of a Simple Language for Parallel Programming. In: Proc. IFIP Congress, Stockholm, Sweden (August 1974) 471–475

    Google Scholar 

  4. Ptolemy Web Site. http://ptolemy.eecs.berkeley.edu

  5. Balarin, F., Watanabe, Y., Hsieh, H., Lavagno, L., Passerone, C., Sangiovanni-Vincentelli, A.: Metropolis: An Integrated Electronic System Design Environment. Computer 36(4) (April 2003) 45–52

    Article  Google Scholar 

  6. MathWorks Real-Time Workshop. http://www.mathworks.com/products/rtw/

  7. NI LabVIEW Microprocessor SDK. http://www.ni.com/labview/microprocessor_sdk.htm

  8. Keinert, J., Streubühr, M., Schlichter, T., Falk, J., Gladigau, J., Haubelt, C., Teich, J., Meredith, M.: System Co Designer — An Automatic ESL Synthesis Approach by Design Space Exploration and Behavioral Synthesis for Streaming Applications. ACM Trans. on Design Automation of Electronic Systems 14(1) (January 2009) 1:1–1:23

    Article  Google Scholar 

  9. Ha, S., Kim, S., Lee, C., Yi, Y., Kwon, S., Joo, Y.P.: Pea CE: A Hardware-Software Codesign Environment for Multimedia Embedded Systems. ACM Trans. on Design Automation of Electronic Systems 12(3) (August 2007) 1–25

    Google Scholar 

  10. Pimentel, A.D., Erbas, C., Polstra, S.: A Systematic Approach to Exploring Embedded System Architectures at Multiple Abstraction Levels. IEEE Trans. on Computers 55(2) (February 2006) 99–112

    Article  Google Scholar 

  11. Thiele, L., Bacivarov, I., Haid, W., Huang, K.: Mapping Applications to Tiled Multiprocessor Embedded Systems. In: Proc. Int’l Conf. on Application of Concurrency to System Design (ACSD), Bratislava, Slovak Republic (July 2007) 29–40

    Google Scholar 

  12. Nikolov, H., Stefanov, T., Deprettere, E.: Systematic and Automated Multiprocessor System Design, Programming, and Implementation. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 27(3) (March 2008) 542–555

    Article  Google Scholar 

  13. Kangas, T., Kukkala, P., Orsila, H., Salminen, E., Hännikäinen, M., Hämäläinen, T.D.: UMLBased Multiprocessor So C Design Framework. ACM Trans. on Embedded Computing Systems 5(2) (May 2006) 281–320

    Article  Google Scholar 

  14. Kumar, A., Fernando, S., Ha, Y., Mesman, B., Corporaal, H.: Multiprocessor Systems Synthesis for Multiple Use-Cases of Multiple Applications on FPGA. ACM Trans. on Design Automation of Electronic Systems 31(3) (July 2008) 40:1–40:27

    Article  Google Scholar 

  15. Bhattacharyya, S.S., Brebner, G., Janneck, J.W., Eker, J., von Platen, C., Mattavelli, M., Raulet, M.: OpenDF — A Dataflow Toolset for Reconfigurable Hardware and Multicore Systems. In: First Swedish Workshop on Multi-Core Computing (MCC), Uppsala, Sweden (November 2008)

    Google Scholar 

  16. Edwards, S.A., Tardieu, O.: SHIM: A Deterministic Model for Heterogeneous Embedded Systems. IEEE Trans. on VLSI Systems 14(8) (August 2006) 854–867

    Article  Google Scholar 

  17. Gordon, M.I., Thies, W., Amarasinghe, S.: Exploiting Coarse-Grained Task, Data, and Pipeline Parallelism in Stream Programs. In: Proc. Int’l Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), San Jose, CA, USA (October 2006) 151–162

    Google Scholar 

  18. Kienhuis, B., Rijpkema, E., Deprettere, E.: Compaan: Deriving Process Networks from Matlab for Embedded Signal Processing Architectures. In: Proc. of the Int’l Workshop on Hardware/ Software Codesign (CODES), San Diego, CA, USA (May 2000) 13–17

    Google Scholar 

  19. Verdoolaege, S., Nikolov, H., Stefanov, T.: PN: A Tool for Improved Derivation of Process Networks. EURASIP Journal on Embedded Systems 2007 (2007)

    Article  Google Scholar 

  20. Pimentel, A.D.: The Artemis Workbench for System-Level Performance Evaluation of Embedded Systems. Int. J. Embedded Systems 3(3) (2008) 181–196

    Article  Google Scholar 

  21. Janneck, J.W., Miller, I.D., Parlour, D.B., Roquier, G., Wipliez, M., Raulet, M.: Synthesizing Hardware from Dataflow Programs: An MPEG-4 Simple Profile Decoder Case Study. In: IEEE Workshop on Signal Processing Systems (SiPS), Washington, D.C., USA (October 2008) 287–292

    Google Scholar 

  22. Vasudevan, N., Edwards, S.A.: Celling SHIM: Compiling Deterministic Concurrency to a Heterogeneous Multicore. In: Proc. ACM Symposium on Applied Computing (SAC), Honolulu, HI, USA (March 2009) 1626–1631

    Google Scholar 

  23. Gelernter, D., Carriero, N.: Coordination Languages and Their Significance. Commun. ACM 35(2) (February 1992) 97–107

    Article  Google Scholar 

  24. Parks, T.M.: Bounded Scheduling of Process Networks. PhD thesis, University of California, Berkeley (December 1995)

    Google Scholar 

  25. IBM SDK for Multicore Acceleration. http://www-128.ibm.com/developerworks/power/cell/

  26. González Harbour, M., Gutiérrez García, J.J., Palencia Gutiérrez, J.C., Drake Moyano, J.M.: MAST: Modeling and Analysis Suite for Real Time Applications. In: Proc. Euromicro Conference on Real-Time Systems, Delft, The Netherlands (June 2001) 125–134

    Google Scholar 

  27. Chakraborty, S., Künzli, S., Thiele, L.: A General Framework for Analyzing System Properties in Platform-Based Embedded System Design. In: Proc. Design, Automation and Test in Europe (DATE), Munich, Germany (March 2003) 190–195

    Google Scholar 

  28. Henia, R., Hamann, A., Jersak, M., Racu, R., Richter, K., Ernst, R.: System Level Performance Analysis — The SymTA/S Approach. IEE Proceedings Computers and Digital Techniques 152(2) (March 2005) 148–166

    Article  Google Scholar 

  29. Alur, R., Dill, D.L.: A Theory of Timed Automata. Theoretical Computer Science 126(2) (April 1994) 183–235

    Article  MATH  MathSciNet  Google Scholar 

  30. Hendriks, M., Verhoef, M.: Timed Automata Based Analysis of Embedded System Architectures. In: Workshop on Parallel and Distributed Real-Time Systems, Rhodes, Greece (April 2006)

    Google Scholar 

  31. Perathoner, S., Wandeler, E., Thiele, L., Hamann, A., Schliecker, S., Henia, R., Racu, R., Ernst, R., González Harbour, M.: Influence of Different System Abstractions on the Performance Analysis of Distributed Real-Time Systems. In: Proc. Int’l Conf. on Embedded Software (EMSOFT), Salzburg, Austria (October 2007) 193–202

    Google Scholar 

  32. Wandeler, E., Thiele, L.: Optimal TDMA Time Slot and Cycle Length Allocation for Hard Real-Time Systems. In: Proc. Asia and South Pacific Conf. on Design Automation (ASPDAC), Yokohama, Japan (January 2006) 479–484

    Google Scholar 

  33. Hamann, A., Racu, R., Ernst, R.: Multi-Dimensional Robustness Optimization in Heterogeneous Distributed Embedded Systems. In: Proc. Real Time and Embedded Technology and Applications Symposium (RTAS), Bellevue, WA, United States (April 2007) 269–280

    Google Scholar 

  34. Kraemer, S., Gao, L., Weinstock, J., Leupers, R., Ascheid, G., Meyr, H.: HySim: A Fast Simulation Framework for Embedded Software Development. In: Proc. Int’l Conf. on Hardware/ Software Codesign and System Synthesis (CODES+ISSS), Salzburg, Austria (October 2007) 75–80

    Google Scholar 

  35. Schliecker, S., Stein, S., Ernst, R.: Performance Analysis of Complex Systems by Integration of Dataflow Graphs and Compositional Performance Analysis. In: Proc. Design, Automation and Test in Europe (DATE). (March 2007) 273–278

    Google Scholar 

  36. Künzli, S., Hamann, A., Ernst, R., Thiele, L.: Combined Approach to System Level Performance Analysis of Embedded Systems. In: Proc. Int’l Conf. on Hardware/Software Codesign and System Synthesis (CODES/ISSS), Salzburg, Austria (October 2007) 63–68

    Google Scholar 

  37. Künzli, S., Poletti, F., Benini, L., Thiele, L.: Combining Simulation and Formal Methods for System-Level Performance Analysis. In: Proc. Design, Automation and Test in Europe (DATE). (March 2006) 236–241

    Google Scholar 

  38. Gries, M.: Methods for Evaluating and Covering the Design Space during Early Design Development. Integration, the VLSI Journal 38(2) (December 2004) 131–183

    Article  Google Scholar 

  39. de Kock, E.A., Essink, G., Smits, W.J.M., van der Wolf, P., Brunel, J.Y., Kruijtzer, W.M., Lieverse, P., Vissers, K.A.: YAPI: Application Modeling for Signal Processing Systems. In: Proc. Design Automation Conference (DAC), Los Angeles, CA, USA (June 2000) 402–405

    Google Scholar 

  40. Edwards, S.A., Vadudevan, N., Tardieu, O.: Programming Shared Memory Multiprocessors with Deterministic Message-Passing Concurrency: Compiling SHIM to Pthreads. In: Proc. Design, Automation and Test in Europe (DATE), Munich, Germany (March 2008) 1498–1503

    Google Scholar 

  41. Pham, D.C., Aipperspach, T., Boerstler, D., Bolliger, M., Chaudhry, R., Cox, D., Harvey, P., Harvey, P.M., Hofstee, H.P., Johns, C., Kahle, J., Kameyama, A., Keaty, J., Masubuchi, Y., Pham, M., Pille, J., Posluszny, S., Riley, M., Stasiak, D.L., Suzuoki, M., Takahashi, O., Warnock, J., Weitzel, S., Wendel, D., Yazawa, K.: Overview of the Architecture, Circuit Design, and Physical Implementation of a First-Generation Cell Processor. IEEE Journal of Solid-State Circuits 41(1) (January 2006) 179–196

    Article  Google Scholar 

  42. Paolucci, P.S., Jerraya, A.A., Leupers, R., Thiele, L., Vicini, P.: SHAPES: A Tiled Scalable Software Hardware Architecture Platform for Embedded Systems. In: Proc. Int’l Conf. on Hardware/Software Codesign and System Synthesis (CODES+ISSS), Seoul, South Korea (October 2006) 167–172

    Google Scholar 

  43. Benini, L., Bertozzi, D., Alessandro, B., Menichelli, F., Olivieri, M.: MPARM: Exploring the Multi-Processor So C Design Space with System C. The Journal of VLSI Signal Processing 41 (September 2005) 169–182(14)

    Google Scholar 

  44. RTEMS Home Page. http://www.rtems.com

  45. Haid, W., Schor, L., Huang, K., Bacivarov, I., Thiele, L.: Efficient Execution of Kahn Process Networks on Multi-Processor Systems Using Protothreads and Windowed FIFOs. In: Proc. IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTI Media), Grenoble, France (October 2009) 35–44

    Google Scholar 

  46. Edwards, S., Lavagno, L., Lee, E.A., Sangiovanni-Vincentelli, A.: Design of Embedded Systems: FormalModels, Validation, and Synthesis. Proceedings of the IEEE 85(3) (March 1997) 366–390

    Article  Google Scholar 

  47. Kopetz, H., Bauer, G.: The Time-Triggered Architecture. Proceedings of the IEEE 91(1) (January 2003) 112–126

    Article  Google Scholar 

  48. Henzinger, T.A., Horowitz, B., Kirsch, C.M.: Giotto: A Time-Triggered Language for Embedded Programming. Proceedings of the IEEE 91(1) (January 2003) 84–99

    Article  Google Scholar 

  49. Benveniste, A., Caspi, P., Edwards, S.A., Halbwachs, N., Le Guernic, P., De Simone, R.: The Synchronous Languages 12 Years Later. Proceedings of the IEEE 91(1) (January 2003) 64–83

    Article  Google Scholar 

  50. Wandeler, E., Thiele, L., Verhoef, M., Lieverse, P.: System Architecture Evaluation Using Modular Performance Analysis: A Case Study. Int’l Journal on Software Tools for Technology Transfer (STTT) 8(6) (November 2006) 649–667

    Article  Google Scholar 

  51. Thiele, L., Chakraborty, S., Naedele, M.: Real-Time Calculus for Scheduling Hard Real-Time Systems. In: Proc. Int’l Symposium on Circuits and Systems (ISCAS). Volume 4., Geneva, Switzerland (March 2000) 101–104

    Google Scholar 

  52. Cruz, R.L.: A Calculus for Network Delay, Part I: Network Elements in Isolation. IEEE Trans. Inf. Theory 37(1) (January 1991) 114–131

    Article  MATH  MathSciNet  Google Scholar 

  53. Le Boudec, J.Y., Thiran, P.: Network Calculus—A Theory of Deterministic Queuing Systems for the Internet. Volume 2050 of Lecture Notes in Computer Science. Springer Verlag (2001)

    Google Scholar 

  54. Wandeler, E., Thiele, L.: Real-Time Calculus (RTC) Toolbox. http://www.mpa.ethz.ch/Rtctoolbox (2006)

  55. Haid,W., Keller, M., Huang, K., Bacivarov, I., Thiele, L.: Generation and Calibration of Compositional Performance Analysis Models forMulti-Processor Systems. In: Proc. Int’l Conf. on Systems, Architectures, Modeling and Simulation (IC-SAMOS), Samos, Greece (July 2009) 92–99

    Google Scholar 

  56. Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckmann, R., Mitra, T., Mueller, F., Puaut, I., Puschner, P., Staschulat, J., Stenström, P.: The Worst-Case Execution Time Problem —Overview of Methods and Survey of Tools. ACM Trans. on Embedded Computing Systems 7(3) (April 2008) 36:1–36:53

    Article  Google Scholar 

  57. Pimentel, A.D., Thompson, M., Polstra, S., Erbas, C.: Calibration of Abstract Performance Models for System System-Level Design Space Exploration. Journal of Signal Processing Systems 50(2) (February 2008) 99–114

    Article  Google Scholar 

  58. Zitzler, E., Thiele, L.: Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Trans. on Evolutionary Computation 3(4) (November 1999) 257–271

    Article  Google Scholar 

  59. Zitzler, E., Thiele, L., Bader, J.: SPAM: Set Preference Algorithm for Multiobjective Optimization. In: Conf. on Parallel Problem Solving From Nature (PPSN), Dortmund, Germany (September 2008) 847–858

    Google Scholar 

  60. Thiele, L., Chakraborty, S., Gries, M., Künzli, S.: A Framework for Evaluating Design Tradeoffs in Packet Processing Architectures. In: Proc. Design Automation Conference (DAC), New Orleans, LA, USA (June 2002) 880–885

    Google Scholar 

  61. Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization. In: Proc. Evolutionary Methods for Design, Optimisation, and Control (EUROGEN), Athens, Greece (2001) 95–100

    Google Scholar 

  62. Bleuler, S., Laumanns, M., Thiele, L., Zitzler, E.: PISA - A Platform and Programming Language Independent Interface for Search Algorithms. In: Int’l Conf. on Evolutionary Multi- Criterion Optimization (EMO), Faro, Portugal (April 2003) 494–508

    Google Scholar 

  63. Wallace, G.K.: The JPEG Still Picture Compression Standard. IEEE Trans. on Consumer Electronics 38(1) (Feb 1992) 18–34

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Engineering and Networks Laboratory, ETH Zurich, Zurich, Switzerland

    Iuliana Bacivarov, Wolfgang Haid, Kai Huang & Lothar Thiele

Authors
  1. Iuliana Bacivarov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wolfgang Haid
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kai Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lothar Thiele
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Iuliana Bacivarov .

Editor information

Editors and Affiliations

  1. , Dept. of Electrical and, University of Maryland, A. V. Williams Bldg. 2311, College Park, 20742, Maryland, USA

    Shuvra S. Bhattacharyya

  2. Leiden Inst. Advanced Computer Science, Leiden Embedded Research Center, Leiden University, Niels Bohrweg 1, Leiden, 2333 CA, Netherlands

    Ed F. Deprettere

  3. RWTH Aachen University, Templergraben 55, Aachen, 52056, Germany

    Rainer Leupers

  4. , Department of Computer Systems, Tampere University of Technology, Korkeakoulunkatu 1, Tampere, 33720, Finland

    Jarmo Takala

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer Science+Business Media, LLC

About this chapter

Cite this chapter

Bacivarov, I., Haid, W., Huang, K., Thiele, L. (2010). Methods and Tools for Mapping Process Networks onto Multi-Processor Systems-On-Chip. In: Bhattacharyya, S., Deprettere, E., Leupers, R., Takala, J. (eds) Handbook of Signal Processing Systems. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-6345-1_35

Download citation

  • DOI: https://doi.org/10.1007/978-1-4419-6345-1_35

  • Published:

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4419-6344-4

  • Online ISBN: 978-1-4419-6345-1

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation