Article

Free access

Upper time bounds for executing PRAM-programs on the LogP-machine

Authors:

Welf Löwe,

Wolf ZimmermannAuthors Info & Claims

ICS '95: Proceedings of the 9th international conference on Supercomputing

Pages 41 - 50

https://doi.org/10.1145/224538.224543

Published: 03 July 1995 Publication History

PDF eReader

References

[1]

R.P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the A CM, pages 201 - 206, 1974.

Digital Library

Google Scholar

[2]

D. Culler, R. Karp, D. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken. LogP: Towards a realistic model of parallel computation. In dth A CM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP 93), pages 1-12, 1993. Published in SIGPLAN Notices (28)7

Digital Library

Google Scholar

[3]

B. Di Martino and G. Ianello. Parallelization of non-simultaneous iterative methods for systems of linear equations. In LNCS 85~, Parallel Processing: CONPAR '9~-VAPP VI, pages 254-264. Springer, 1994.

Digital Library

Google Scholar

[4]

A. Gerasoulis and T. 'fang. On the granularity and clustering of directed acyclic task graphs. IEEE Transactions on Parallel and Distributed Systems, 4:686-701, June 1993.

Digital Library

Google Scholar

[5]

R. M. Karp and V. Ramachandran. Parallel algorithms for shared memory machines. In J. van Leeuwen, eclitorj f-2ranclbook of Th~or~iiGc~t G'orr~put~r Sci~nc~ Vol. A, pages 871-941. MIT-Press, 1990.

Digital Library

Google Scholar

[6]

R.M. Karp, A. Sahay, E.E. Santos, and K.E. Schauser. Optimal broadcast and summation in the LogP model. A CM-Symposium on Parallel Algorithms and Architectures, 1993.

Digital Library

Google Scholar

[7]

W. Lawe. Optimization of PRAM-programs with input-dependent memory access. To appear in LNCS, Proceedings of the EUROPAR'95. Springer, 1995.

Digital Library

Google Scholar

[8]

W. L6we and W. Zimmermann. On finding optimal clusterings of task graphs. In A izu International Symposium on Parallel Algorithm/Architecture Synthesis, pages 241-247. IEEE Computer Society Press, 1995.

Digital Library

Google Scholar

[9]

W. LSwe and W. Zimmermann. Programming data-parallel -executing process-parallel. To appear in Proceedings of the Zeus'95 Workshop. 1995.

Google Scholar

[10]

M.G. Norman and P. Thanisch. Models of machines and computation for mapping in multicomputers. A CM Computing Surveys, 25(3):263-302, 1993,

Digital Library

Google Scholar

[11]

C.H. Papadimitriou and M. Yannakakis. Towards an architecture-independent analysis of parallel algorithms. SIAM Journal on Computing, 19(2):322 - 328, 1990.

Digital Library

Google Scholar

[12]

V. Sarkar. Partitioning and Scheduling Parallel Programs for Multiprocessors. MIT Press, Cambridge, Massachusetts, 1989.

Digital Library

Google Scholar

[13]

L. G. Valiant. General purpose parallel architectures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science Vol. A, pages 945-971. MIT- Press, 1990.

Digital Library

Google Scholar

[14]

W. gimmermann and H. Kumm. On the implementation of virtual shared memory. In Programming Models for Massively Parallel Computers, pages 172-178, 1995.

Google Scholar

[15]

W. Zimmermann and W. LSwe. An approach to machine-independent parallel programming. In LNCS 85d, Parallel Processing: CONPAR~9d-VAPP VI, pages 277-288. Springer, 1994.

Digital Library

Google Scholar

Cited By

View all

Andersson JEricsson MLöwe W(2019)An Adaptive High-Performance Service ArchitectureElectronic Notes in Theoretical Computer Science (ENTCS)10.5555/2773567.2773672114:C(87-102)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.5555/2773567.2773672
Löwe WZimmermann W(2018)Scheduling balanced task-graphs to LogP-machinesParallel Computing10.1016/S0167-8191(00)00030-226:9(1083-1108)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/S0167-8191%2800%2900030-2
Verriet J(2018)Scheduling outtrees of height one in the LogP modelParallel Computing10.1016/S0167-8191(00)00029-626:9(1065-1082)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/S0167-8191%2800%2900029-6
Show More Cited By

Recommendations

Improved upper bounds on sizes of codes

Let A(n,d) denote the maximum possible number of codewords in a binary code of length n and minimum Hamming distance d. For large values of n, the best known upper bound, for fixed d, is the Johnson bound. We give a new upper bound which is at least as ...
Upper Bounds on the Size of Obstructions and Intertwines

We give an exponential upper bound inp4on the size of any obstruction for path-width at mostp. We give a doubly exponential upper bound ink5 on the size of any obstruction for tree-width at mostk. We also give an upper bound on the size of any ...
Upper bounds for constant-weight codes

Let A(n,d,w) denote the maximum possible number of codewords in an (n,d,w) constant-weight binary code. We improve upon the best known upper bounds on A(n,d,w) in numerous instances for n&les;24 and d&les;12, which is the parameter range of existing ...

Comments

Information & Contributors

Information

Published In

ICS '95: Proceedings of the 9th international conference on Supercomputing

July 1995

448 pages

ISBN:0897917286

DOI:10.1145/224538

Chairman:
Mateo Valero
Univ. Polite`cnica de Catalunya

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 July 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICS95

Sponsor:

Univ Politecnica del Catalunya
SIGARCH
Oregon Graduate Institute

ICS95: 1995 International Conference on Supercomputing

July 3 - 7, 1995

Barcelona, Spain

Acceptance Rates

ICS '95 Paper Acceptance Rate 49 of 120 submissions, 41%;

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
290
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)3

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Andersson JEricsson MLöwe W(2019)An Adaptive High-Performance Service ArchitectureElectronic Notes in Theoretical Computer Science (ENTCS)10.5555/2773567.2773672114:C(87-102)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.5555/2773567.2773672
Löwe WZimmermann W(2018)Scheduling balanced task-graphs to LogP-machinesParallel Computing10.1016/S0167-8191(00)00030-226:9(1083-1108)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/S0167-8191%2800%2900030-2
Verriet J(2018)Scheduling outtrees of height one in the LogP modelParallel Computing10.1016/S0167-8191(00)00029-626:9(1065-1082)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/S0167-8191%2800%2900029-6
Drozdowski MDrozdowski M(2009)Scheduling with Communication DelaysScheduling for Parallel Processing10.1007/978-1-84882-310-5_6(209-299)Online publication date: 5-Jun-2009
https://doi.org/10.1007/978-1-84882-310-5_6
Zimmermann WMiddendorf MLöwe W(2006)On optimal k-iinear scheduling of tree-like task graphs for LogP-machinesEuro-Par’98 Parallel Processing10.1007/BFb0057870(328-336)Online publication date: 30-Jun-2006
https://doi.org/10.1007/BFb0057870
Löwe WEisenbiegler JZimmermann W(2005)Optimization of parallel programs on machines with expensive communicationEuro-Par'96 Parallel Processing10.1007/BFb0024754(602-610)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0024754
Löwe WZimmermann W(2002)On Scheduling Task-Graphs to LogP-Machines with DisturbancesEuro-Par 2002 Parallel Processing10.1007/3-540-45706-2_24(189-196)Online publication date: 20-Aug-2002
https://doi.org/10.1007/3-540-45706-2_24
Rugina RSchauser K(1998)Predicting the running times of parallel programs by simulationProceedings of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing10.1109/IPPS.1998.669996(654-660)Online publication date: 1998
https://doi.org/10.1109/IPPS.1998.669996
Zimmermann WLöwe WGottlieb J(1996)On Design and Implementation of Parallel Algorithms for Solving Inverse ProblemsParameter Identification and Inverse Problems in Hydrology, Geology and Ecology10.1007/978-94-009-1704-0_20(283-297)Online publication date: 1996
https://doi.org/10.1007/978-94-009-1704-0_20

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Improved upper bounds on sizes of codes

Upper Bounds on the Size of Obstructions and Intertwines

Upper bounds for constant-weight codes