On compile-time evaluation of process partitioning transformations for Kahn process networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On compile-time evaluation of process partitioning transformations for Kahn process networks

Full text

Pdf (458 KB)

Source

International Conference on Hardware Software Codesign archive
Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis table of contents

Grenoble, France

SESSION: Tools for embedded software design table of contents

Pages 31-40

Year of Publication: 2009

ISBN:978-1-60558-628-1

Authors

Sjoerd Meijer	Leiden University, Leiden, Netherlands
Hristo Nikolov	Leiden University, Leiden, Netherlands
Todor Stefanov	Leiden University, Leiden , Netherlands

Sponsors

ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 21, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629435.1629441 What is a DOI?

ABSTRACT

Kahn Process Networks is an appealing model of computation for programming and mapping applications onto multi-processor platforms. Autonomous processes communicate through unbounded FIFO channels in absence of a global scheduler. We derive Kahn process networks from sequential applications using the pn compiler, but the derived networks do not necessarily meet the performance requirements. Process partitioning transformations can achieve a more balanced network improving the performance results significantly. There are a number of process partitioning transformations that can be used, but no hints are given to the designer which transformation should be applied to minimize, for example, the execution time. Therefore, we investigate a compile-time approach for selecting the best transformation candidate and show results on a Xilinx Virtex 2 FPGA and the Cell BE processor.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E. de Kock, G. Essink, W. Smits, P. van der Wolf, J.-Y. Brunel, W. Kruijtzer, P. Lieverse, and K. Vissers. YAPI: Application modeling for signal processing systems. In Proc. 37th Design Automation Conference (DAC'2000), pages 402--405, Los Angeles, CA, June 5-9 2000.
	2	P. Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20, 1991.
	3	M. Gschwind, H. P. Hofstee, B. Flachs, M. Hopkins, Y. Watanabe, and T. Yamazaki. Synergistic processing in cell's multicore architecture. IEEE Micro, 26(2):10--24, 2006.
	4	E. Lee et al. PtolemyII: Heterogeneous Concurrent Modeling and Design in Java. Technical report, University of California at Berkeley, 1999. UCB/ERL M99/40.
	5	S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, Inc., 1997.
	6	D. Nadezhkin, S. Meijer, T. Stefanov, and E. Deprettere. Realizing fifo communication when mapping kahn process networks onto cell. In SAMOS IX: International Symposium on Systems, Architectures, MOdeling and Simulation, 2009.
	7	H. Nikolov, T. Stefanov, and E. Deprettere. Multi-processor system design with espam. In CODES+ISSS '06: Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, pages 211--216, New York, NY, USA, 2006. ACM.
	8	H. Nikolov, T. Stefanov, and E. Deprettere. Systematic and automated multiprocessor system design, programming, and implementation. IEEE Transactions on Computer--Aided Design of Integrated Circuits and Systems, 27(3):542--555, 2008.
	9	H. Nikolov, M. Thompson, T. Stefanov, A. Pimentel, S. Polstra, R. Bose, C. Zissulescu, and E. Deprettere. Daedalus: toward composable multimedia mpsoc design. In DAC '08: Proceedings of the 45th annual conference on Design automation, pages 574--579, New York, NY, USA, 2008. ACM.
	10	K. K. Parhi and D. G. Messerschmitt. Static Rate-Optimal Scheduling of Iterative Data-Flow Programs via Optimum Unfolding. IEEE Transaction on Computers, 40(2):178--195, Feb. 1991.
	11	S. Sriram and S. Bhattacharyya. Embedded Multiprocessors: Scheduling and Synchronization. Marcel Dekker, Inc., 2000.
	12	T. Stefanov, B. Kienhuis, and E. Deprettere. Algorithmic transformation techniques for efficient exploration of alternative application instances. In CODES '02: Proceedings of the tenth international symposium on Hardware/software codesign, pages 7--12, New York, NY, USA, 2002. ACM.
	13	J. Teich and L. Thiele. Exact Partitioning of Affine Dependence Algorithms. Lecture Notes in Computer Science (LNCS), Springer, 2268:133--151, 2002.
	14	A. Turjan. Compiling nested loop programs to process networks, 2007. PhD thesis, Leiden University, The Netherlands.
	15	S. Verdoolaege, H. Nikolov, and T. Stefanov. pn: a tool for improved derivation of process networks. EURASIP J. Embedded Syst., 2007(1):19--19, 2007.