ACM Home Page
Please provide us with feedback. Feedback
On compile-time evaluation of process partitioning transformations for Kahn process networks
Full text PdfPdf (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 Request Permissions    Review this Article  
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.