research-article

Adaptive Parallelism and Piranha

Authors:

Nicholas Carriero,

Eric Freeman,

David Gelernter,

David KaminskyAuthors Info & Claims

Computer, Volume 28, Issue 1

Pages 40 - 49

https://doi.org/10.1109/2.362631

Published: 01 January 1995 Publication History

Publisher Site

Abstract

Desktop computers are idle much of the time. Ongoing trends make aggregate LAN "waste"--idle compute cycles--an increasingly attractive target for recycling. Piranha, a software implementation of adaptive parallelism, allows these waste cycles to be recaptured by putting them to work running parallel applications. Most parallel processing is static: Programs execute on a fixed set of processors throughout a computation. Adaptive parallelism allows for dynamic processor sets, which means that the number of processors working on a computation may vary, depending on availability. With adaptive parallelism, instead of parceling out jobs to idle workstations, a single job is distributed over many workstations. Adaptive parallelism is potentially valuable on dedicated multiprocessors as well, particularly on massively parallel processors. One key Piranha advantage is that task descriptors, not processes, are the basic movable, remappable computation unit. The task descriptor approach supports strong heterogeneity. A process image representing a task in midcomputation can't be moved to a machine of a different type, but a task descriptor can be. Thus, a task begun on a Sun computer can be completed by an IBM machine. The authors show that adaptive parallelism has the potential to integrate heterogeneous platforms seamlessly into a unified computing resource and to permit more efficient sharing of traditional parallel processors than is possible with current systems.

References

[1]

M. Litzkow and M. Livny, “Experience with the Condor Distributed Batch System,” Proc. IEEE Workshop on Experimental Distributed Systems, IEEE Service Center, Piscataway, N.J., Oct. 1990.

Crossref

Google Scholar

[2]

D.A. Nichols, Multiprocessing in a Network of Workstations, doctoral dissertation, Carnegie Mellon University, Pittsburgh, 1990.

Crossref

Google Scholar

[3]

J.K. Ousterhout, et al., “The Sprite Network Operating System,” Computer, Vol. 21 No. 2 Feb. 1988, pp. 23-36.

Digital Library

Google Scholar

[4]

A.K. Lenstra and M. Manasse, “Factoring by Electronic Mail,” Proc. Eurocrypt 89, No. 173 in Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1990.

Crossref

Google Scholar

[5]

G. Agha, Actors: A Model of Concurrent Computation in Distributed Systems, MIT Press, Cambridge, Mass., 1986.

Digital Library

Google Scholar

[6]

J.S. Chase, et al., “The Amber System: Parallel Programming on a Network of Multiprocessors,” Proc. 12th ACM Symp. Operating Systems Principles, ACM, New York, 1989, pp. 147-158.

Digital Library

Google Scholar

[7]

N. Carriero and D. Gelernter, How to Write Parallel Programs: A First Course, MIT Press, Cambridge, Mass., 1990.

Crossref

Google Scholar

[8]

N. Carriero E. Freeman and D. Gelernter, “Adaptive Parallelism on Multiprocessors: Preliminary Experience with Piranha on the CM-5,” Proc. Sixth Annual Workshop on Languages and Compilers for Parallel Computing, No. 768 in Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1994, pp. 139-151.

Crossref

Google Scholar

[9]

D. Gelernter and D. Kaminsky, “Supercomputing Out of Recycled Garbage: Preliminary Experience with Piranha,” Proc. Sixth ACM Int’l Conf. Supercomputing, ACM, New York, 1991, pp. 417-427.

Crossref

Google Scholar

[10]

D.L. Kaminsky, Adaptive Parallelism with Piranha, doctoral dissertation, Yale Univ., New Haven, Conn., 1994.

Crossref

Google Scholar

[11]

E. Freeman, “Piranha on the Connection Machine CM-5,” Tech. Report YALE/DCS/RR-1011, Yale Univ., New Haven, Conn., Feb. 1994.

Google Scholar

[12]

S. Ahmed and D. Gelernter, “A CASE Environment for Parallel Programming,” Proc. Fifth Int’l Workshop Computer-Aided Software Eng., 1992, pp. 214-224.

Crossref

Google Scholar

Cited By

View all

Emani MO'Boyle M(2015)Celebrating diversity: a mixture of experts approach for runtime mapping in dynamic environmentsACM SIGPLAN Notices10.1145/2813885.273799950:6(499-508)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2813885.2737999
Emani MO'Boyle MGrove DBlackburn S(2015)Celebrating diversity: a mixture of experts approach for runtime mapping in dynamic environmentsProceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2737924.2737999(499-508)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2737924.2737999
Han SRatnasamy SManiatis P(2013)Large-scale computation not at the cost of expressivenessProceedings of the 14th USENIX conference on Hot Topics in Operating Systems10.5555/2490483.2490494(11-11)Online publication date: 13-May-2013
https://dl.acm.org/doi/10.5555/2490483.2490494
Show More Cited By

Adaptive Parallelism and Piranha
1. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

Adaptive Parallelism for OpenMP Task Parallel Programs
LCR '00: Selected Papers from the 5th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers

We present a system that allows task parallel OpenMP programs to execute on a network of workstations (NOW) with a variable number of nodes. Such adaptivity, generally called adaptive parallelism, is important in a multi-user NOW environment, enabling ...
Adaptive parallelism with Piranha
Adaptive work stealing with parallelism feedback
PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming

We present an adaptive work-stealing thread scheduler, A-Steal, for fork-join multithreaded jobs, like those written using the Cilk multithreaded language or the Hood work-stealing library. The A-Steal algorithm is appropriate for large parallel servers ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Computer Volume 28, Issue 1

January 1995

95 pages

ISSN:0018-9162

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 January 1995

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Emani MO'Boyle M(2015)Celebrating diversity: a mixture of experts approach for runtime mapping in dynamic environmentsACM SIGPLAN Notices10.1145/2813885.273799950:6(499-508)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2813885.2737999
Emani MO'Boyle MGrove DBlackburn S(2015)Celebrating diversity: a mixture of experts approach for runtime mapping in dynamic environmentsProceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2737924.2737999(499-508)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2737924.2737999
Han SRatnasamy SManiatis P(2013)Large-scale computation not at the cost of expressivenessProceedings of the 14th USENIX conference on Hot Topics in Operating Systems10.5555/2490483.2490494(11-11)Online publication date: 13-May-2013
https://dl.acm.org/doi/10.5555/2490483.2490494
Rosinha RGeyer CVargas PSchulze BRana OMyers JCirne W(2007)WSPEProceedings of the 5th international workshop on Middleware for grid computing: held at the ACM/IFIP/USENIX 8th International Middleware Conference10.1145/1376849.1376855(1-6)Online publication date: 26-Nov-2007
https://dl.acm.org/doi/10.1145/1376849.1376855
Giné FSolsona FHanzich MHernández PLuque E(2007)Cooperating coschedulingJournal of Computer Science and Technology10.1007/s11390-007-9082-y22:5(695-710)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1007/s11390-007-9082-y
Ram DSrinivas ARani P(2004)A model for parallel programming over CORBAJournal of Parallel and Distributed Computing10.1016/j.jpdc.2004.06.00264:11(1256-1269)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2004.06.002
Keren ABarak A(2003)Opportunity Cost Algorithms for Reduction of I/O and Interprocess Communication Overhead in a Computing ClusterIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2003.116736914:1(39-50)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1109/TPDS.2003.1167369
Weissman JAbburi LEngland D(2003)Integrated schedulingJournal of Parallel and Distributed Computing10.1016/S0743-7315(03)00013-363:6(649-668)Online publication date: 1-Jun-2003
https://dl.acm.org/doi/10.1016/S0743-7315%2803%2900013-3
Surdeanu MMoldovan DHarabagiu S(2002)Performance Analysis of a Distributed Question/Answering SystemIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2002.101141313:6(579-596)Online publication date: 1-Jun-2002
https://dl.acm.org/doi/10.1109/TPDS.2002.1011413
Weissman J(2002)Predicting the Cost and Benefit of Adapting Data Parallel Applications in ClustersJournal of Parallel and Distributed Computing10.1006/jpdc.2002.183862:8(1248-1271)Online publication date: 1-Aug-2002
https://dl.acm.org/doi/10.1006/jpdc.2002.1838
Show More Cited By

Abstract

References

Cited By

Recommendations

Adaptive Parallelism for OpenMP Task Parallel Programs

Adaptive parallelism with Piranha

Adaptive work stealing with parallelism feedback

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations