Harnessing parallelism in multicore clusters with the all-pairs and wavefront abstractions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Harnessing parallelism in multicore clusters with the all-pairs and wavefront abstractions

Full text

Pdf (455 KB)

Source

High Performance Distributed Computing archive
Proceedings of the 18th ACM international symposium on High performance distributed computing table of contents

Garching, Germany

SESSION: Parallel algorithms and applications table of contents

Pages 1-10

Year of Publication: 2009

ISBN:978-1-60558-587-1

Authors

Li Yi	University of Notre Dame, Notre Dame, IN, USA
Christopher Moretti	University of Notre Dame, Notre Dame, IN, USA
Scott Emrich	University of Notre Dame, Notre Dame, IN, USA
Kenneth Judd	Stanford University, Stanford, CA, USA
Douglas Thain	University of Notre Dame, Notre Dame, IN, USA

Sponsors

ACM: Association for Computing Machinery
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 88, 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/1551609.1551613 What is a DOI?

ABSTRACT

Both distributed systems and multicore computers are difficult programming environments. Although the expert programmer may be able to tune distributed and multicore computers to achieve high performance, the non-expert may struggle to achieve a program that even functions correctly.

We argue that high level abstractions are an effective way of making parallel computing accessible to the non-expert. An abstraction is a regularly structured framework into which a user may plug in simple sequential programs to create very large parallel programs. By virtue of a regular structure and declarative specification, abstractions may be materialized on distributed, multicore, and distributed multicore systems with robust performance across a wide range of problem sizes. In previous work, we presented the All-Pairs abstraction for computing on distributed systems of single CPUs. In this paper, we extend All-Pairs to multicore systems, and introduce Wavefront, which represents a number of problems in economics and bioinformatics. We demonstrate good scaling of both abstractions up to 32-cores on one machine and hundreds of cores in a distributed system.

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	D. Bakken and R. Schlichting. Tolerating failures in the bag-of-tasks programming paradigm. In IEEE International Symposium on Fault Tolerant Computing, June 1991.
	2	T. Cheatham , A. Fahmy , D. C. Stefanescu , L. G. Valiant, Bulk synchronous parallel computing-a paradigm for transportable software, Proceedings of the 28th Hawaii International Conference on System Sciences, p.268, January 04-07, 1995
	3	D. da Silva, W. Cirne, and F. Brasilero. Trading cycles for information: Using replication to schedule bag-of-tasks applications on computational grids. In Euro-Par, 2003.
	4	Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
	5	Ewa Deelman , Gurmeet Singh , Mei-Hui Su , James Blythe , Yolanda Gil , Carl Kesselman , Gaurang Mehta , Karan Vahi , G. Bruce Berriman , John Good , Anastasia Laity , Joseph C. Jacob , Daniel S. Katz, Pegasus: A framework for mapping complex scientific workflows onto distributed systems, Scientific Programming, v.13 n.3, p.219-237, July 2005
	6	U. Doraszelski. An R&D race with knowledge accumulation. Bell Journal of Economics, 34:19--41, 2003.
	7	Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
	8	W. Gentzsch (Sun Microsystems), Sun Grid Engine: Towards Creating a Compute Power Grid, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.35, May 15-18, 2001
	9	P. Ghemawat and A. M. Spence. Learning curve spillovers and market performance. The Quarterly Journal of Economics, 100:839--852, 1985.
	10	Michael Isard , Mihai Budiu , Yuan Yu , Andrew Birrell , Dennis Fetterly, Dryad: distributed data-parallel programs from sequential building blocks, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
	11	H. T. Kung, Why Systolic Architectures?, Computer, v.15 n.1, p.37-46, January 1982 [doi>10.1109/MC.1982.1653825]
	12	C. Moretti, J. Bulosan, P. Flynn, and D. Thain. All-pairs: An abstraction for data intensive cloud computing. In International Parallel and Distributed Processing Symposium (IPDPS), 2008.
	13	Christopher Moretti , Karsten Steinhaeuser , Douglas Thain , Nitesh V. Chawla, Scaling up Classifiers to Cloud Computers, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.472-481, December 15-19, 2008 [doi>10.1109/ICDM.2008.99]
	14	S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in amino acid sequence of two proteins. Journal of Molecular Biology, 48:443--453, 1970.
	15	Tim Oliver , Bertil Schmidt , Darran Nathan , Ralf Clemens , Douglas Maskell, Using reconfigurable hardware to accelerate multiple sequence alignment with ClustalW, Bioinformatics, v.21 n.16, p.3431-3432, August 2005 [doi>10.1093/bioinformatics/bti508]
	16	Ioan Raicu , Yong Zhao , Catalin Dumitrescu , Ian Foster , Mike Wilde, Falkon: a Fast and Light-weight tasK executiON framework, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362680]
	17	Stjepan Rajko , Srinivas Aluru, Space and Time Optimal Parallel Sequence Alignments, IEEE Transactions on Parallel and Distributed Systems, v.15 n.12, p.1070-1081, December 2004 [doi>10.1109/TPDS.2004.86]
	18	J. Reinganum. Dynamic games of innovation. Journal of Economic Theory, 25:21--41, 1981.
	19	J. Reinganum. A dynamic game of R&D: Patent protection and competitive behavior. Econometrica, 50:671--688, 1982.
	20	J. Reinganum. Corrigendum. Journal of Economic Theory, 35:196--197, 1985.
	21	J. Reinganum and N. Stokey. Oligopoly extraction of a common property natural resource: The importance of the period of commitment in dynamic games. International Economic Review, 26:161--174, 1985.
	22	A. Sarje and S. Aluru. Parallel biological sequence alignments on the cell broadband engine. In International Parallel and Distributed Processing Symposium (IPDPS), 2008.
	23	A. M. Spence. The learning curve and competition. Bell Journal of Economics, 12:49--70, 1981.
	24	A. M. Spence. Cost reduction, competition, and industry performance. Econometrica, 52:101--121, 1984.
	25	D. Thain, T. Tannenbaum, and M. Livny. Condor and the grid. In F. Berman, G. Fox, and T. Hey, editors, Grid Computing: Making the Global Infrastructure a Reality. John Wiley, 2003.
	26	Kevin B. Theobald , Guang R. Gao, An efficient parallel algorithm for all pairs examination, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.742-753, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126175]
	27	Yong Zhao , Jed Dobson , Ian Foster , Luc Moreau , Michael Wilde, A notation and system for expressing and executing cleanly typed workflows on messy scientific data, ACM SIGMOD Record, v.34 n.3, September 2005 [doi>10.1145/1084805.1084813]