Celling SHIM

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Celling SHIM: compiling deterministic concurrency to a heterogeneous multicore

Full text

Pdf (291 KB)

Source

Symposium on Applied Computing archive
Proceedings of the 2009 ACM symposium on Applied Computing table of contents

Honolulu, Hawaii

SESSION: Embedded systems track table of contents

Pages 1626-1631

Year of Publication: 2009

ISBN:978-1-60558-166-8

Authors

Nalini Vasudevan	Columbia University, New York, New York
Stephen A. Edwards	Columbia University, New York, New York

Sponsor

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 42, 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/1529282.1529649 What is a DOI?

ABSTRACT

Parallel architectures are the way of the future, but are notoriously difficult to program. In addition to the low-level constructs they often present (e.g., locks, DMA, and non-sequential memory models), most parallel programming environments admit data races: the environment may make nondeterministic scheduling choices that can change the function of the program.

We believe the solution is model-based design, where the programmer is presented with a constrained higher-level language that prevents certain unwanted behavior. In this paper, we describe a compiler for the SHIM scheduling-independent concurrent language that generates code for the Cell Broadband heterogeneous multicore processor. The complexity of the code our compiler generates relative to the source illustrates how difficult it is to manually write code for the Cell.

We demonstrate the efficacy of our compiler on two examples. While the SHIM language is (by design) not ideal for every algorithm, it works well for certain applications and simplifies the parallel programming process, especially on the Cell architecture.

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	Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
	2	Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
	3	Thomas William Ainsworth , Timothy Mark Pinkston, Characterizing the Cell EIB On-Chip Network, IEEE Micro, v.27 n.5, p.6-14, September 2007 [doi>10.1109/MM.2007.81]
	4	Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
	5	A. C. Chow et al. A programming example: Large FFT on the Cell Broadband Engine. In Global Signal Processing Expo (GSPx), Santa Clara, CA, Oct. 2005. (from IBM)
	6	Stephen A. Edwards , Olivier Tardieu, SHIM: a deterministic model for heterogeneous embedded systems, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA [doi>10.1145/1086228.1086277]
	7	Stephen A. Edwards , Nalini Vasudevan , Olivier Tardieu, Programming shared memory multiprocessors with deterministic message-passing concurrency: compiling SHIM to Pthreads, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany [doi>10.1145/1403375.1403735]
	8	A. E. Eichenberger , J. K. O'Brien , K. M. O'Brien , P. Wu , T. Chen , P. H. Oden , D. A. Prener , J. C. Shepherd , B. So , Z. Sura , A. Wang , T. Zhang , P. Zhao , M. K. Gschwind , R. Archambault , Y. Gao , R. Koo, Using advanced compiler technology to exploit the performance of the Cell Broadband Engine^TM architecture, IBM Systems Journal, v.45 n.1, p.59-84, January 2006
	9	Alexandre E. Eichenberger , Kathryn O'Brien , Kevin O'Brien , Peng Wu , Tong Chen , Peter H. Oden , Daniel A. Prener , Janice C. Shepherd , Byoungro So , Zehra Sura , Amy Wang , Tao Zhang , Peng Zhao , Michael Gschwind, Optimizing Compiler for the CELL Processor, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.161-172, September 17-21, 2005 [doi>10.1109/PACT.2005.33]
	10	Kayvon Fatahalian , Daniel Reiter Horn , Timothy J. Knight , Larkhoon Leem , Mike Houston , Ji Young Park , Mattan Erez , Manman Ren , Alex Aiken , William J. Dally , Pat Hanrahan, Sequoia: programming the memory hierarchy, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188543]
	11	Buǧra Gedik , Rajesh R. Bordawekar , Philip S. Yu, CellSort: high performance sorting on the cell processor, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	12	C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
	13	IBM. Cell Broadband Engine Architecture v1.02, Oct. 2007.
	14	IBM. Example Library API Reference v3.0, Sept. 2007.
	15	J. A. Kahle , M. N. Day , H. P. Hofstee , C. R. Johns , T. R. Maeurer , D. Shippy, Introduction to the cell multiprocessor, IBM Journal of Research and Development, v.49 n.4/5, p.589-604, July 2005
	16	G. Kahn. The semantics of a simple language for parallel programming. In Information Processing 74: IFIP Congress 74, pages 471--475, Stockholm, Sweden, Aug. 1974.
	17	Michael Kistler , Michael Perrone , Fabrizio Petrini, Cell Multiprocessor Communication Network: Built for Speed, IEEE Micro, v.26 n.3, p.10-23, May 2006 [doi>10.1109/MM.2006.49]
	18	E. A. Lee and D. G. Messerschmitt. Synchronous data flow. Proc. IEEE, 75(9):1235--1245, Sept. 1987.
	19	The Message Passing Interface Forum. MPI: A Message-Passing Interface Standard, June 1995. Version 1.1.
	20	M. Ohara , H. Inoue , Y. Sohda , H. Komatsu , T. Nakatani, MPI Microtask for programming the cell broadband engine^TM processor, IBM Systems Journal, v.45 n.1, p.85-102, January 2006
	21	OpenMP Arch. Review Board, www.openmp.org. OpenMP C and C++ Application Program Interface, 2002. Ver. 2.0.
	22	F. Petrini et al. Multicore surprises: Lessons learned from optimizing Sweep3D on the Cell Broadband Engine. In Intl. Parallel and Distributed Processing Symposium (IPDPS), pages 1--10, Long Beach, CA, Mar. 2007.
	23	D. Pham et al. The design and implementation of a first-generation Cell processor. In Solid-State Cir. Conf. (ISSCC), v. 1, pp. 184--185, San Francisco, CA, Feb. 2005.
	24	Tarik Saidani , Stéphane Piskorski , Lionel Lacassagne , Samir Bouaziz, Parallelization schemes for memory optimization on the cell processor: a case study of image processing algorithm, Proceedings of the 2007 workshop on MEmory performance: DEaling with Applications, systems and architecture, p.9-16, September 16-16, 2007, Brasov, Romania [doi>10.1145/1327171.1327172]
	25	Olivier Tardieu , Stephen A. Edwards, Scheduling-independent threads and exceptions in SHIM, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176887.1176908]
	26	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
	27	N. Vasudevan and S. A. Edwards. Static deadlock detection for the SHIM concurrent language. In Formal Methods and Models for Codesign, Anaheim, CA, June 2008.