More Web Proxy on the site http://driver.im/

article

Free access

pn: a tool for improved derivation of process networks

Authors:

Sven Verdoolaege,

Hristo Nikolov,

Todor StefanovAuthors Info & Claims

EURASIP Journal on Embedded Systems, Volume 2007, Issue 1

Page 19

https://doi.org/10.1155/2007/75947

Published: 01 January 2007 Publication History

Abstract

Current emerging embedded System-on-Chip platforms are increasingly becoming multiprocessor architectures. System designers experience significant difficulties in programming these platforms. The applications are typically specified as sequential programs that do not reveal the available parallelism in an application, thereby hindering the effcient mapping of an application onto a parallel multiprocessor platform. In this paper, we present our compiler techniques for facilitating the migration from a sequential application specification to a parallel application specification using the process network model of computation. Our work is inspired by a previous research project called Compaan. With our techniques we address optimization issues such as the generation of process networks with simplified topology and communication without sacrificing the process networks' performance. Moreover, we describe a technique for compile-time memory requirement estimation which we consider as an important contribution of this paper. We demonstrate the usefulness of our techniques on several examples.

References

[1]

{1} A. Darte, R. Schreiber, and G. Villard, "Lattice-based memory allocation," IEEE Transactions on Computers, vol. 54, pp. 1242-1257, 2005.

Digital Library

[2]

{2} E. A. Lee and A. Sangiovanni-Vincentelli, "A framework for comparing models of computation," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 12, pp. 1217-1229, 1998.

Digital Library

[3]

{3} J. Davis, R. Galicia, M. Goel, et al., "PtolemyII: heterogeneous concurrent modeling and design in java," Tech. Rep. UCB/ERL M99/40, University of California, Berkeley, Calif, USA, 1999.

[4]

{4} G. Kahn, "The semantics of a simple language for parallel programming," in Proceedings of the IFIP Congress, pp. 471-475, North-Holland, Stockholm, Sweden, August 1974.

[5]

{5} E. A. de Kock, G. Essink, W. J. M. Smits, et al., "YAPI: application modeling for signal processing systems," in Proceedings of the 37th Design Automation Conference (DAC'00), pp. 402-405, Los Angeles, Calif, USA, June 2000.

[6]

{6} E. A. de Kock, "Multiprocessor mapping of process networks: a JPEG decoding case study," in Proceedings of the 15th International Symposium on System Synthesis (ISSS'02), pp. 68-73, Kyoto, Japan, October 2002.

[7]

{7} B. K. Dwivedi, A. Kumar, and M. Balakrishnan, "Automatic synthesis of system on chip multiprocessor architectures for process networks," in Proceedings of the 2nd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and Systems Synthesis, (CODES+ISSS'04), pp. 60-65, IEEE Computer Society, Stockholm, Sweden, September 2004.

[8]

{8} K. Goossens, J. Dielissen, J. van Meerbergen, et al., "Guaranteeing the quality of services in networks on chip," in Networks on Chip, pp. 61-82, Kluwer Academic Publishers, Hingham, Mass, USA, 2003.

[9]

{9} P. Lieverse, T. Stefanov, P. van der Wolf, and E. Deprettere, "System level design with SPADE: an M-JPEG case study," in Proceedings of the International Conference on Computer-Aided Design (ICCAD'01), pp. 31-38, San Jose, Calif, USA, November 2001.

[10]

{10} A. Nieuwland, J. Kang, O. P. Gangwal, et al., C-HEAP: A Heterogeneous Multi-Processor Architecture Template and Scalable and Flexible Protocol for the Design of Embedded Signal Processing Systems, Kluwer Academic Publishers, Norwell, Mass, USA, 2002.

[11]

{11} H. Nikolov, T. Stefanov, and E. Deprettere, "Multi-processor system design with ESPAM," in Proceedings of the 4th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'06), pp. 211-216, Seoul, Korea, October 2006.

[12]

{12} A. D. Pimentel, C. Erbas, and S. Polstra, "A systematic approach to exploring embedded system architectures at multiple abstraction levels," IEEE Transactions on Computers, vol. 55, no. 2, pp. 99-112, 2006.

Digital Library

[13]

{13} T. Stefanov, C. Zissulescu, A. Turjan, B. Kienhuis, and E. Deprettere, "System design using Kahn process networks: the Compaan/Laura approach," in Proceedings of Conference Design, Automation and Test in Europe (DATE'04), vol. 1, pp. 340-345, Paris, France, February 2004.

[14]

{14} P. van der Wolf, P. Lieverse, M. Goel, D. La Hei, and K. Vissers, "MPEG-2 decoder case study as a driver for a system level design methodology," in Proceedings of the 7th International Workshop on Hardware/Software Codesign (CODES'99), pp. 33-37, Rome, Italy, May 1999.

[15]

{15} B. Kienhuis, E. Rijpkema, and E. Deprettere, "Compaan: deriving process networks from matlab for embedded signal processing architectures," in Proceedings of the 8th International Workshop Hardware/Software Codesign (CODES'00), pp. 13-17, ACM Press, San Diego, Calif, USA, May 2000.

[16]

{16} E. Rijpkema, E. F. Deprettere, and B. Kienhuis, "Deriving process networks from nested loop algorithms," Parallel Processing Letters, vol. 10, no. 2, pp. 165-176, 2000.

[17]

{17} A. Turjan, B. Kienhuis, and E. Deprettere, "Translating affne nested-loop programs to process networks," in Proceedings of International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES'04), pp. 220-229, Washington, DC, USA, September 2004.

[18]

{18} A. Darte, R. Schreiber, and G. Villard, "Lattice-based memory allocation," in Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES'03), pp. 298-308, ACM Press, San Jose, Calif, USA, October-November 2003.

[19]

{19} K. Beyls and E. H. D'Hollander, "Generating cache hints for improved program effciency," Journal of Systems Architecture, vol. 51, no. 4, pp. 223-250, 2005.

Digital Library

[20]

{20} T. Vander Aa, M. Jayapala, F. Barat, H. Corporaal, F. Catthoor, and G. Deconinck, "A high-level memory energy estimator based on reuse distance," in Proceedings of the 3rd Workshop on Optimizations for DSP and Embedded Systems (ODES'05), San Jose, Calif, USA, March 2005.

[21]

{21} P. Vanbroekhoven, G. Janssens, M. Bruynooghe, H. Corporaal, and F. Catthoor, "Advanced copy propagation for arrays," in Proceedings of the ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'03), U. Kremer, Ed., pp. 24-33, ACM Press, San Diego, Calif, USA, June 2003.

[22]

{22} P. Feautrier, "Automatic parallelization in the polytope model," in The Data Parallel Programming Model, vol. 1132 of Lecture Notes in Computer Science, pp. 79-103, Springer, London, UK, 1996.

[23]

{23} P. Feautrier, "Parametric integer programming," Operationnelle/Operations Research, vol. 22, no. 3, pp. 243-268, 1988.

[24]

{24} S. Verdoolaege, R. Seghir, K. Beyls, V. Loechner, and M. Bruynooghe, "Analytical computation of Ehrhart polynomials: enabling more compiler analyses and optimizations," in Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES'04), pp. 248-258, Washington, DC, USA, September 2004.

[25]

{25} P. Clauss, F. J. Fernández, D. Gabervetsky, and S. Verdoolaege, "Symbolic polynomial maximization over convex sets and its application to memory requirement estimation," ICPS Research Reports 06-04, Université Louis Pasteur, Strasbourg, France, 2006, http://icps.u-strasbg.fr/ upload/icps-2006-173.pdf.

[26]

{26} P. Feautrier, "Dataflow analysis of array and scalar references," International Journal of Parallel Programming, vol. 20, no. 1, pp. 23-53, 1991.

Digital Library

[27]

{27} C. Bastoul, "Code generation in the polyhedral model is easier than you think," in Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques (PACT'04), pp. 7-16, IEEE Computer Society, Antibes Juanles-Pins, France, September 2004.

[28]

{28} S. Verdoolaege, M. Bruynooghe, G. Janssens, and F. Catthoor, "Multi-dimensional incremental loop fusion for data locality," in Proceedings of the 14th IEEE International Conference on Application-Specific Systems, Architectures, and Processors (ASAP'03), D. Martin, Ed., pp. 17-27, The Hague, The Netherlands, June 2003.

[29]

{29} S. Verdoolaege, K. Danckaert, F. Catthoor, M. Bruynooghe, and G. Janssens, "An access regularity criterion and regularity improvement heuristics for data transfer optimization by global loop transformations," in Proceedings of the 1st Workshop on Optimization for DSP and Embedded Systems (ODES'03), San Francisco, Calif, USA, March 2003.

[30]

{30} I. Daubechies and W. Sweldens, "Factoring wavelet transforms into lifting steps," Journal of Fourier Analysis and Applications, vol. 4, no. 3, pp. 247-269, 1998.

Cited By

Riebler HVaz GKenter TPlessl C(2019)Transparent Acceleration for Heterogeneous Platforms With Compilation to OpenCLACM Transactions on Architecture and Code Optimization10.1145/331942316:2(1-26)Online publication date: 18-Apr-2019
https://dl.acm.org/doi/10.1145/3319423
Aguilar MEusse JRay PLeupers RAscheid GSheng WSharma P(2017)Towards Parallelism Extraction for Heterogeneous Multicore Android DevicesInternational Journal of Parallel Programming10.1007/s10766-016-0479-545:6(1592-1624)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s10766-016-0479-5
Corre YDiguet JHeller DBlouin DLagadec L(2016)TBESACM Transactions on Embedded Computing Systems10.1145/281681715:1(1-27)Online publication date: 13-Jan-2016
https://dl.acm.org/doi/10.1145/2816817
Show More Cited By

Index Terms

pn: a tool for improved derivation of process networks

Recommendations

Flattened Butterfly Topology for On-Chip Networks

With the trend towards increasing number of cores in a multicore processors, the on-chip network that connects the cores needs to scale efficiently. In this work, we propose the use of high-radix networks in on-chip networks and describe how the ...
Silicon-photonic network architectures for scalable, power-efficient multi-chip systems
ISCA '10

Scaling trends of logic, memories, and interconnect networks lead towards dense many-core chips. Unfortunately, process yields and reticle sizes limit the scalability of large single-chip systems. Multi-chip systems break free of these areal limits, but ...
Scalable high-radix router microarchitecture using a network switch organization

As the system size of supercomputers and datacenters increases, cost-efficient networks become critical in achieving good scalability on those systems. High-radix routers reduce network cost by lowering the network diameter while providing a high ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image EURASIP Journal on Embedded Systems

EURASIP Journal on Embedded Systems Volume 2007, Issue 1

January 2007

474 pages

ISSN:1687-3955

EISSN:1687-3963

Issue’s Table of Contents

Publisher

Hindawi Limited

London, United Kingdom

Publication History

Published: 01 January 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
210
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)9

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Riebler HVaz GKenter TPlessl C(2019)Transparent Acceleration for Heterogeneous Platforms With Compilation to OpenCLACM Transactions on Architecture and Code Optimization10.1145/331942316:2(1-26)Online publication date: 18-Apr-2019
https://dl.acm.org/doi/10.1145/3319423
Aguilar MEusse JRay PLeupers RAscheid GSheng WSharma P(2017)Towards Parallelism Extraction for Heterogeneous Multicore Android DevicesInternational Journal of Parallel Programming10.1007/s10766-016-0479-545:6(1592-1624)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s10766-016-0479-5
Corre YDiguet JHeller DBlouin DLagadec L(2016)TBESACM Transactions on Embedded Computing Systems10.1145/281681715:1(1-27)Online publication date: 13-Jan-2016
https://dl.acm.org/doi/10.1145/2816817
Aguilar MLeupers RAscheid GKavvadias NCorporaal HStuijk S(2015)A Toolflow for Parallelization of Embedded Software in Multicore DSP PlatformsProceedings of the 18th International Workshop on Software and Compilers for Embedded Systems10.1145/2764967.2771936(76-79)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1145/2764967.2771936
Zhang PHuang MXiao BHuang HCong J(2015)CMOSTProceedings of the 52nd Annual Design Automation Conference10.1145/2744769.2744807(1-6)Online publication date: 7-Jun-2015
https://dl.acm.org/doi/10.1145/2744769.2744807
Cilardo AGallo L(2015)Improving Multibank Memory Access Parallelism with Lattice-Based PartitioningACM Transactions on Architecture and Code Optimization10.1145/267535911:4(1-25)Online publication date: 9-Jan-2015
https://dl.acm.org/doi/10.1145/2675359
Cong JLi PXiao BZhang P(2014)An Optimal Microarchitecture for Stencil Computation Acceleration Based on Non-Uniform Partitioning of Data Reuse BuffersProceedings of the 51st Annual Design Automation Conference10.1145/2593069.2593090(1-6)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1145/2593069.2593090
Sheng WSchürmans SOdendahl MBertsch MVolevach VLeupers RAscheid G(2014)A compiler infrastructure for embedded heterogeneous MPSoCsParallel Computing10.1016/j.parco.2013.11.00740:2(51-68)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1016/j.parco.2013.11.007
(2013)Automated extraction of scenario sequences from disciplined dataflow networksProceedings of the Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign10.5555/3041405.3041483(47-56)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.5555/3041405.3041483
Schor LYang HBacivarov IThiele LRabbah RRaghunathan A(2013)Expandable process networks to efficiently specify and explore task, data, and pipeline parallelismProceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems10.5555/2555729.2555734(1-10)Online publication date: 29-Sep-2013
https://dl.acm.org/doi/10.5555/2555729.2555734
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents