Memory Analysis and Optimized Allocation of Dataflow Applications on Shared-Memory MPSoCs

详细信息    查看全文

• 作者：Karol Desnos ; Maxime Pelcat ; Jean-Fran?ois Nezan…
• 关键词：Memory allocation ; Multiprocessor system ; on ; chip ; Stereo vision ; Synchronous dataflow
• 刊名：The Journal of VLSI Signal Processing
• 出版年：2015
• 出版时间：July 2015
• 年：2015
• 卷：80
• 期：1
• 页码：19-37
• 全文大小：2,318 KB
• 参考文献：1. Arndt, O., Becker, D., Banz, C., Blume, H. (2013). Parallel implementation of real-time semi-global matching on embedded multi-core architectures. In / Embedded computer systems: architectures, modeling, and simulation (SAMOS XIII).
  2. Benazouz, M., Marchetti, O., Munier-Kordon, A., Urard, P. (2010). A new approach for minimizing buffer capacities with throughput constraint for embedded system design. In / Computer systems and applications (AICCSA), 2010 IEEE/ACS.
  3. Bodin, B., Munier-Kordon, A., de Dinechin, B. (2012). K-periodic schedules for evaluating the maximum throughput of a synchronous dataflow graph. In / Embedded computer systems (SAMOS).
  4. Bouchard, M., Angalovi?, M., Hertz, A. About equivalent interval colorings of weighted graphs. Discrete Appl. Math. doi:10.1016/j.dam.2009.04.015 .
  5. Boutellier, J. (2009). / Quasi-static scheduling for fine-grained embedded multiprocessing. Ph.D.thesis.
  6. Desnos, K., Pelcat, M., Nezan, J., Aridhi, S. (2012). Memory bounds for the distributed execution of a hierarchical synchronous data-flow graph. In / International conference on embedded computer systems (SAMOS).
  7. Desnos, K., Pelcat, M., Nezan, J.F., Aridhi, S. (2013). Pre-and post-scheduling memory allocation strategies on mpsocs. In / Electronic system level synthesis conference (ESLsyn).
  8. Desnos, K., & Zhang, J. (2013). Preesm project - stereo matching. svn://svn.code.sf.net/p/preesm/code/trunk/tests/stereo.
  9. El Assad, S., & Noura, H. (2013). Generator of chaotic sequences and corresponding generating system. EP Patent App. EP20,110,720,313. http://www.google.com/patents/EP2553567A1?cl=en.
  10. Electronic Systems Group TU Eindhoven (2013). Sdf for free (sdf3). http://www.es.ele.tue.nl/sdf3/.
  11. Embedded Vision Alliance (2013). Embedded vision alliance. http://www.embedded-vision.com.
  12. Fabri, J. (1979). / Automatic storage optimization. Courant Institute of Mathematical Sciences, New York University.
  13. Fischaber, S., Woods, R., McAllister, J. (2007). Soc memory hierarchy derivation from dataflow graphs. In / IEEE workshop on signal processing systems (pp. 469-74). doi: 10.1109/SIPS.2007.4387593 10.1109/SIPS.2007.4387593 .
  14. Greef, E.D., Catthoor, F., Man, H.D. (1997). Array placement for storage size reduction in embedded multimedia systems. ASAP.
  15. Intel (2013). i7-3610qm processor product page. http://ark.intel.com/products/64899/.
  16. Johnson, D.S. (1973). / Near-optimal bin packing algorithms. Ph.D. thesis, Massachusetts Institute of Technology.
  17. Kalray (2013). Many-core processors -dataflow. http://www.kalray.eu/technology/dataflow/.
  18. Lee, E, Messerschmitt, D (1987) Synchronous data flow. Proceedings of the IEEE 75: pp. 1235-1245 CrossRef
  19. Lee, EA, Parks, TM (1995) Dataflow process networks. Proceedings of the IEEE 83: pp. 773-801 CrossRef
  20. Malamas, EN, Petrakis, EG, Zervakis, M, Petit, L, Legat, JD (2003) A survey on industrial vision systems, applications and tools. Image and vision computing 21: pp. 171-188 CrossRef
  21. Murthy, P., & Bhattacharyya, S. (2000). Shared memory implementations of synchronous dataflow specifications. In / Proceedings of the design, automation and test in Europe conference and exhibition.
  22. Murthy, P.K.,& Bhattacharyya, S.S. (2010). / Memory management for synthesis of DSP software. CRC Press.
  23. ?sterg?rd, P.R.J. (2001). A new algorithm for the maximum-weight clique problem. / Nordic Journal of Computing, 8(4), 424-36.
  24. Parks, T.M. (1995). / Bounded scheduling of process networks. Ph.D. thesis, University of California.
  25. Pelcat, M., Aridhi, S., Piat, J., Nezan, J.F. (2012). / Physical layer multi-core prototyping: a dataflow-based approach for LTE eNodeB. Springer.
  26. Pelcat, M., Nezan, J.F., Piat, J., Croizer, J., Aridhi, S. (2009). / A System-Level architecture model for rapid prototyping of heterogeneous multicore embedded systems. DASIP.
  27. Roy, S (1999) Stereo without epipolar lines: a ma
• 刊物类别：Engineering
• 刊物主题：Electrical Engineering
  Circuits and Systems
  Computer Imaging, Vision, Pattern Recognition and Graphics
  Computer Systems Organization and Communication Networks
  Signal,Image and Speech Processing
  Mathematics of Computing
  
• 出版者：Springer New York
• ISSN：1939-8115

文摘

The majority of applications, ranging from the low complexity to very multifaceted entities requiring dedicated hardware accelerators, are very well suited for Multiprocessor Systems-on-Chips (MPSoCs). It is critical to understand the general characteristics of a given embedded application: its behavior and its requirements in terms of MPSoC resources. This paper presents a complete method to study the important aspect of memory characteristic of an application. This method spans the theoretical, architecture-independent memory characterization to the quasi optimal static memory allocation of an application on a real shared-memory MPSoCs. The application is modeled as an Synchronous Dataflow (SDF) graph which is used to derive a Memory Exclusion Graph (MEG) essential for the analysis and allocation techniques. Practical considerations, such as cache coherence and memory broadcasting, are extensively treated. Memory footprint optimization is demonstrated using the example of a stereo matching algorithm from the computer vision domain. Experimental results show a reduction of the memory footprint by up to 43 % compared to a state-of-the-art minimization technique, a throughput improvement of 33 % over dynamic allocation, and the introduction of a tradeoff between multicore scheduling flexibility and memory footprint.