article

Free access

Using data partitioning to implement a parallel assembler

Author:

Howard P. KatseffAuthors Info & Claims

ACM SIGPLAN Notices, Volume 23, Issue 9

Pages 66 - 76

https://doi.org/10.1145/62116.62123

Published: 01 January 1988 Publication History

PDF eReader

Abstract

A technique for implementing algorithms on a multiprocessor computer system is data partitioning, in which input data for a problem is partitioned among many processors that cooperate to solve the problem. This paper demonstrates that data partitioning is a good method for implementing an assembler on a message-passing multiprocessor system: it yields a speedup exceeding a factor of 6 with eight processors. We compare several alternative methods for distributing program text and sharing global information among the processors executing the assembler: operations that are important for a variety of applications implemented with data partitioning.

References

[1]

Enslow, P. H., "Mttltiprocessor Organization-a survey," ACM Comput. Surveys, 1, 1977, 103- 129.

Digital Library

Google Scholar

[2]

Miekunas, M. D., and Sehell, R. M., "Parallel Compilation in a Multiprocessor Environment," Proc. ACM 1978 Annual Conference, December 1978, 241-246.

Digital Library

Google Scholar

[3]

Cohen, J., Hickey, T., and Katcoff, J., "Upper Bounds for Speedup in Parallel Parsing," J. ACM, 29,2, April 1982, 408-428.

Digital Library

Google Scholar

[4]

Kolodner, S. and Cohen, J., "Estimating the Speedup in Parallel Parsing," IEEE Trans. on Software Engineering SE-III, January 1985, 114-124.

Google Scholar

[5]

Boehm, H. and Zwaenpoel, W., "Parallel Attribute Grammar Evaluation," Technical Report COMP TR86-39, Rice University, Houston, May, 1986.

Google Scholar

[6]

Dowsing, R. D., and Sanderson, M. T., "Writing Concurrent Assemblers-A Case Study in Path Pascal," Software Pract. Exper. 16,12, December 1986, 1117-1135.

Digital Library

Google Scholar

[7]

Feldman, S. I., "Make: A Program for Maintaining Computer Programs," Software Pract. Exper. 9,4, April 1979, 255-265.

Crossref

Google Scholar

[8]

"M ake," D YNIX Programmer's Manual, Sequent Computer Systems, Inc., December, 1985.

Google Scholar

[9]

Gaglianello, R. D. and Katseff, H. P., "Meglos: An Operating System for a Multiprocessor Environment," Proc. Fifth Internat. Conf. on Distributed Comput. Syst., Denver, May, 1985, 35-42.

Google Scholar

[10]

Ahuja, S. R., "S/NET: A High Speed Interconnect for Multiple Computers," IEEE J. on Selected Areas in Communications SAC-l, 5, November, 1983.

Google Scholar

[11]

London, T. B., Ahuja, S. R., and Katseff, H. P., "Performance of an Interconnected Microprocessor System Designed for Fast User-level Communications," IFIP WG 10.3 Workshop on Hardware Supported Implementation of Concurrent Languages in Distributed Systems, University of Bristol, U. K., March, 1984, 125- 134.

Digital Library

Google Scholar

[12]

Gaglianello, R. D. and Katseff, H. P., "Communications in Meglos," Software Pract. Exper. 16,10, October, 1986, 945-963.

Digital Library

Google Scholar

Cited By

View all

Voetter RHuijben MRietveld KSterpone LBartolini AButko A(2022)Compilation on the GPU?Proceedings of the 19th ACM International Conference on Computing Frontiers10.1145/3528416.3530249(230-236)Online publication date: 17-May-2022
https://dl.acm.org/doi/10.1145/3528416.3530249
Collberg C(2005)Distributed high-level module binding for flexible encapsulation and fast inter-modular optimizationProgramming Languages and System Architectures10.1007/3-540-57840-4_37(282-297)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57840-4_37
Klein EKoskimies K(2005)Parallel one-pass compilationAttribute Grammars and their Applications10.1007/3-540-53101-7_6(76-90)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-53101-7_6
Show More Cited By

Index Terms

Using data partitioning to implement a parallel assembler
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Multiple instruction, multiple data
2. Software and its engineering
  1. Software notations and tools

Recommendations

Using data partitioning to implement a parallel assembler
PPEALS '88: Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems

A technique for implementing algorithms on a multiprocessor computer system is data partitioning, in which input data for a problem is partitioned among many processors that cooperate to solve the problem. This paper demonstrates that data partitioning ...
Parallel graph partitioning on multicore architectures
LCPC'10: Proceedings of the 23rd international conference on Languages and compilers for parallel computing

Graph partitioning is a common and frequent preprocessing step in many high-performance parallel applications on distributed-and shared-memory architectures. It is used to distribute graphs across memory and to improve spatial locality. There are ...
Partitioning in parallel processing of production systems

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 23, Issue 9

Proceedings of the ACM/SIGPLAN PPEALS 1988

Sept. 1988

246 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/62116

Editor:
Richard L. Wexelblat
Philips Labs., Briarcliff Manor, NY

Issue’s Table of Contents

PPEALS '88: Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems
January 1988
246 pages
ISBN:0897912764
DOI:10.1145/62115
Editor:
Richard L. Wexelblat
Philips Labs., Briarcliff Manor, NY

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: 01 January 1988

Published in SIGPLAN Volume 23, Issue 9

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
340
Total Downloads

Downloads (Last 12 months)45
Downloads (Last 6 weeks)16

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Voetter RHuijben MRietveld KSterpone LBartolini AButko A(2022)Compilation on the GPU?Proceedings of the 19th ACM International Conference on Computing Frontiers10.1145/3528416.3530249(230-236)Online publication date: 17-May-2022
https://dl.acm.org/doi/10.1145/3528416.3530249
Collberg C(2005)Distributed high-level module binding for flexible encapsulation and fast inter-modular optimizationProgramming Languages and System Architectures10.1007/3-540-57840-4_37(282-297)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57840-4_37
Klein EKoskimies K(2005)Parallel one-pass compilationAttribute Grammars and their Applications10.1007/3-540-53101-7_6(76-90)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-53101-7_6
Zedan H(1990)Key references in distributed computer systems 1959–1989Distributed Computer Systems10.1016/B978-0-408-02938-4.50016-4(193-295)Online publication date: 1990
https://doi.org/10.1016/B978-0-408-02938-4.50016-4
Fleckenstein CHemmendinger DRiehl A(1989)A parallel `make' utility based on Linda's tuple-spaceProceedings of the 17th conference on ACM Annual Computer Science Conference10.1145/75427.75454(216-220)Online publication date: 21-Feb-1989
https://dl.acm.org/doi/10.1145/75427.75454
Gross TSobel AZolg M(1989)Parallel compilation for a parallel machineACM SIGPLAN Notices10.1145/74818.7482624:7(91-100)Online publication date: 21-Jun-1989
https://dl.acm.org/doi/10.1145/74818.74826
Gross TSobel AZolg M(1989)Parallel compilation for a parallel machineProceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation10.1145/73141.74826(91-100)Online publication date: 21-Jun-1989
https://dl.acm.org/doi/10.1145/73141.74826
Gozillon AHaeri SRiordan JKeir P(2024)Performance Analysis of Compiler Support for Parallel Evaluation of C++ Constant ExpressionsSoftware, System, and Service Engineering10.1007/978-3-031-51075-5_6(129-152)Online publication date: 3-Jan-2024
https://doi.org/10.1007/978-3-031-51075-5_6
Head MGovindaraju MKranzlmüller DBode AHegering HCasanova HGerndt M(2009)Performance enhancement with speculative execution based parallelism for processing large-scale xml-based application dataProceedings of the 18th ACM international symposium on High performance distributed computing10.1145/1551609.1551615(21-30)Online publication date: 11-Jun-2009
https://dl.acm.org/doi/10.1145/1551609.1551615
Head MGovindaraju M(2008)Parallel Processing of Large-Scale XML-Based Application Documents on Multi-core Architectures with PiXiMaLProceedings of the 2008 Fourth IEEE International Conference on eScience10.1109/eScience.2008.77(261-268)Online publication date: 7-Dec-2008
https://dl.acm.org/doi/10.1109/eScience.2008.77
Show More Cited By

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.

Abstract

References

Cited By

Index Terms

Recommendations