Throughput-driven synthesis of embedded software for pipelined execution on multicore architectures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Throughput-driven synthesis of embedded software for pipelined execution on multicore architectures

Full text

Pdf (1.62 MB)

Source

ACM Transactions on Embedded Computing Systems (TECS) archive
Volume 8 , Issue 2 (January 2009) table of contents

Article No. 11

Year of Publication: 2009

ISSN:1539-9087

Authors

Matin Hashemi	University of California, Davis
Soheil Ghiasi	University of California, Davis

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references index terms collaborative colleagues

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/1457255.1457258 What is a DOI?

ABSTRACT

We present a methodology for pipelined software synthesis of streaming applications. First, we develop a versatile task assignment algorithm capable of optimizing realistically-arbitrary cost functions for two cores. The algorithm is exact (i.e., theoretically optimal) contrary to existing heuristics. Second, our approximation technique provides an adjustable knob to trade solution quality with algorithm runtime and memory. Third, we develop a recursive heuristic for more cores. FPGA-based emulated experiments validate our theoretical results. The exact algorithm yields 1.7 × throughput improvement. The approximation method offers a range of tradeoff points (e.g., 3 × faster with 20 × less memory) while degrading the throughput only 1% to 5%.

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	Lyudmil Aleksandrov , Hristo Djidjev , Hua Guo , Anil Maheshwari, Partitioning planar graphs with costs and weights, Journal of Experimental Algorithmics (JEA), 11, 2006 [doi>10.1145/1187436.1210588]
	2	Alur, R. 2003. Formal analysis of hierarchical state machines. In Verifcation Theory and Practice. Springer, Berlin, Germany, 42--66.
	3	Rajeev Alur , Costas Courcoubetis , Thomas A. Henzinger , Pei-Hsin Ho, Hybrid Automata: An Algorithmic Approach to the Specification and Verification of Hybrid Systems, Hybrid Systems, p.209-229, January 1993
	4	Angelini, P., Di Battista, G., and Patrignani, M. 2007. Computing a minimum-depth planar graph embedding in O(n4) time. Lecture Notes in Computer Science, vol. 4619, 287.
	5	Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th annual Design Automation Conference, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
	6	Felice Balarin , Yosinori Watanabe , Harry Hsieh , Luciano Lavagno , Claudio Passerone , Alberto Sangiovanni-Vincentelli, Metropolis: An Integrated Electronic System Design Environment, Computer, v.36 n.4, p.45-52, April 2003 [doi>10.1109/MC.2003.1193228]
	7	Benveniste, A., Carloni, L. P., Caspi, P., and Sangiovanni-Vincentelli, A. L. 2003. Heterogeneous reactive systems modeling and correct-by-construction deployment. In Proceedings of the International Conference on Embedded Software (EMSOFT). Springer, Berlin, Germany, 35--50.
	8	Alvise Bonivento , Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Rialto: a bridge between description and implementation of control algorithms for wireless sensor networks, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA [doi>10.1145/1086228.1086262]
	9	Thang Nguyen Bui , Andrew Peck, Partitioning planar graphs, SIAM Journal on Computing, v.21 n.2, p.203-215, April 1992 [doi>10.1137/0221016]
	10	Jason Cong , Guoling Han , Wei Jiang, Synthesis of an application-specific soft multiprocessor system, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216934]
	11	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	12	Erbas, C., Erbas, S. C., and Pimentel, A. D. 2006. Multiobjective optimization and evolutionary algorithms for the application mapping problem in multiprocessor system-on-chip design. IEEE Trans. Evolut. Comput. 10, 3, 358--374.
	13	Uriel Feige , Robert Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, SIAM Journal on Computing, v.31 n.4, p.1090-1118, 2002 [doi>10.1137/S0097539701387660]
	14	Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
	15	Naveen Garg , Huzur Saran , Vijay V. Vazirani, Finding Separator Cuts in Planar Graphs within Twice the Optimal, SIAM Journal on Computing, v.29 n.1, p.159-179, Feb. 2000 [doi>10.1137/S0097539794271692]
	16	Michael I. Gordon , William Thies , Saman Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
	17	Thomas A. Henzinger , Zohar Manna , Amir Pnueli, Towards Refining Temporal Specifications into Hybrid Systems, Hybrid Systems, p.60-76, January 1993
	18	Thomas A. Henzinger , Xavier Nicollin , Joseph Sifakis , Sergio Yovine, Symbolic model checking for real-time systems, Information and Computation, v.111 n.2, p.193-244, June 1994 [doi>10.1006/inco.1994.1045]
	19	Thomas A. Henzinger , Shaz Qadeer , Sriram K. Rajamani, You Assume, We Guarantee: Methodology and Case Studies, Proceedings of the 10th International Conference on Computer Aided Verification, p.440-451, June 28-July 02, 1998
	20	Henzinger, T. A. and Sifakis, J. 2006. The embedded systems design challenge. In Proceedings of the 14th International Symposium on Formal Methods. Springer, Berlin, Germany, 1--15.
	21	Hu, J. and Marculescu, R. 2005. Energy- and performance-aware mapping for regular noc architectures. IEEE Trans. Comput. Aid. Des. Integr. Circ. Syst. 24, 4.
	22	Kahn, G. 1974. The semantics of simple language for parallel programming. In Proceedings of the International Federation for Information Processing (IFIP) Congress. 471--475.
	23	Marek Karpinski, Approximability of the Minimum Bisection Problem: An Algorithmic Challenge, Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, p.59-67, August 26-30, 2002
	24	Lee, E. A. 2005. Building unreliable systems out of reliable components: The real time story. Tech. rep. UCB/EECS-2005-5, EECS Department, University of California, Berkeley.
	25	Edward A. Lee, The Problem with Threads, Computer, v.39 n.5, p.33-42, May 2006 [doi>10.1109/MC.2006.180]
	26	Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987 [doi>10.1109/TC.1987.5009446]
	27	Lee, E. A. and Messerschmitt, D. G. 1987b. Synchronous data ow. Proc. IEEE 75, 9, 1235--1245.
	28	Lipton, R. J. and Tarjan, R. E. 1979. A separator theorem for planar graphs. SIAM J. Applied Mathematics 36, 177--189.
	29	Zhe Ma , Francky Catthoor , Johan Vounckx, Hierarchical task scheduler for interleaving subtasks on heterogeneous multiprocessor platforms, Proceedings of the 2005 Asia and South Pacific Design Automation Conference, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120765]
	30	Meeting. 2006. Joint United States-European Union-TEKES workshop: Long term challenges in high con_dence composable embedded systems. http://www.truststc.org/euus/wiki/Euus/HelsinkiMeeting.
	31	Michael I. Gordon , William Thies , Michal Karczmarek , Jasper Lin , Ali S. Meli , Andrew A. Lamb , Chris Leger , Jeremy Wong , Henry Hoffmann , David Maze , Saman Amarasinghe, A stream compiler for communication-exposed architectures, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
	32	John D. Owens , William J. Dally , Ujval J. Kapasi , Scott Rixner , Peter Mattson , Ben Mowery, Polygon rendering on a stream architecture, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.23-32, August 21-22, 2000, Interlaken, Switzerland [doi>10.1145/346876.346883]
	33	Ben Serebrin, Media Processing Applications on the Imagine Stream Processor, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.295, September 16-18, 2002
	34	James K. Park , Cynthia A. Phillips, Finding minimum-quotient cuts in planar graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.766-775, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167284]
	35	Andy D. Pimentel , Louis O. Hertzberger , Paul Lieverse , Pieter van der Wolf , Ed F. Deprettere, Exploring Embedded-Systems Architectures with Artemis, Computer, v.34 n.11, p.57-63, November 2001 [doi>10.1109/2.963445]
	36	José Luis Pino , Soonhoi Ha , Edward A. Lee , Joseph T. Buck, Software synthesis for DSP using Ptolemy, Journal of VLSI Signal Processing Systems, v.9 n.1-2, p.7-21, Jan. 1995 [doi>10.1007/BF02406468]
	37	Alessandro Pinto , Alvise Bonivento , Allberto L. Sangiovanni-Vincentelli , Roberto Passerone , Marco Sgroi, System level design paradigms: Platform-based design and communication synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.537-563, July 2006
	38	Ram Rangan , Neil Vachharajani , Adam Stoler , Guilherme Ottoni , David I. August , George Z. N. Cai, Support for High-Frequency Streaming in CMPs, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.259-272, December 09-13, 2006 [doi>10.1109/MICRO.2006.47]
	39	Eyal Amir , Robert Krauthgamer , Satish Rao, Constant factor approximation of vertex-cuts in planar graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780557]
	40	Satish B. Rao, Faster algorithms for finding small edge cuts in planar graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.229-240, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129735]
	41	Stankovic, J. A. 2007. Keynote speech: Control challenges in wireless sensor networks. In Proceedings of the 10th International Conference on Hybrid Systems: Computation and Control. Springer, Berlin, Germany, 2.
	42	S. Stuijk , T. Basten, Analyzing concurrency in streaming applications, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.1-2, p.124-144, January, 2008 [doi>10.1016/j.sysarc.2007.05.002]
	43	S. Stuijk , T. Basten , M. C. W. Geilen , H. Corporaal, Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs, Proceedings of the 44th annual Design Automation Conference, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278674]
	44	Sander Stuijk , Marc Geilen , Twan Basten, Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs, Proceedings of the 43rd annual Design Automation Conference, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147138]
	45	Janos Sztipanovits , John Glossner , Trevor Mudge , Chris Rowen , Alberto Sangiovanni-Vincentelli , Wayne Wolf , Feng Zhao, Grand challenges in embedded systems, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA [doi>10.1145/1086228.1086296]
	46	Michael Bedford Taylor , Walter Lee , Jason Miller , David Wentzlaff , Ian Bratt , Ben Greenwald , Henry Hoffmann , Paul Johnson , Jason Kim , James Psota , Arvind Saraf , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, Evaluation of the Raw Microprocessor: An Exposed-Wire-Delay Architecture for ILP and Streams, Proceedings of the 31st annual international symposium on Computer architecture, p.2, June 19-23, 2004, München, Germany
	47	William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
	48	Thies, W., Lin, J., and Amarasinghe, S. 2003. Partitioning a structured stream graph using dynamic programming. Tech. rep., CS Department, Massachusetts Institute of Technology.
	49	Filip Thoen , Francky Catthoor, Modeling, Verification, and Exploration of Task-Level Concurrency of Real-Time Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 2000
	50	Jia Yu , Jingnan Yao , Laxmi Bhuyan , Jun Yang, Program mapping onto network processors by recursive bipartitioning and refining, Proceedings of the 44th annual Design Automation Conference, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278681]
	51	Yu, Z., Meeuwsen, M., Apperson, R., Sattari, O., Lai, M., Webb, J., Work, E., Mohsenin, T., Singh, M., and Baas, B. M. 2006. An asynchronous array of simple processors for DSP applications. In Proceedings of the IEEE International Solid-State Circuits Conference (ISSCC). IEEE, Los Alamitos, CA.
	52	Gang Zhou , Man-Kit Leung , Edward A. Lee, A Code Generation Framework for Actor-Oriented Models with Partial Evaluation, Proceedings of the 3rd international conference on Embedded Software and Systems, May 14-16, 2007, Daegu, Korea [doi>10.1007/978-3-540-72685-2_19]