Article

Free access

Experiences with non-numeric applications on multithreaded architectures

Authors:

Olivier Maquelin,

Jens-Uwe Schultz,

Xin-Min TianAuthors Info & Claims

PPOPP '97: Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming

Pages 124 - 135

https://doi.org/10.1145/263764.263782

Published: 21 June 1997 Publication History

Abstract

Distributed-memory machines have proved successful for many challenging numerical programs that can be split into largely independent computation-intensive subtasks requiring little data exchange (although the amount of exchanged data may be large). However, many irregular applications---e.g. in the AI field --- have a fairly tight data coupling that often results from the use of shared data structures, making them in many cases not amenable to parallelization on distributed-memory machines. EARTH is an efficient multithreaded architecture that supports in particular large numbers of small data exchanges by means of low start-up times and the ability of tolerance of even small latencies. In this paper, we show the benefits provided by EARTH for applications of this sort by presenting experimental results from several AI applications run on the MANNA machine, which is a distributed-memory machine with a very high-performance communicantion network. EARTH-MANNA is shown to extend the range of programs that can be parallelized and run effectively on distributed-memory machines.

References

[1]

AMRHEIN, B., GLOOR, O., AND KiJCHLIN, W. A case study of multi-threaded GrSbner Basis completion. In Proc. ISSAC'96 (internat. Symposium on Symbolic and Algebraic Computation) (Ziirich/Switzerland, July

Digital Library

[2]

BASAK, D., PANDA, D. K., AND BANIKAZEMI, M. Benefits of processor clustering in designing large parallel systems: When and how? in Proc. Tnternat. Parallel Processing Symposit#m (Hawaii, April 1996).

Digital Library

[3]

BLUMHOFE, R. D., JOERG, C. F., KUSZMAUL, B. C., LEIERSEN, C. E., RANDALL, K. H., AND ZHOU, Y. Cilk: An emcient multithreaded runtime system. In Proc. 5th A CM S#mposium on Principles and Practice of Parallel Programming (PPoPP '95} (August 1995).

Digital Library

[4]

BRiJNING, U., GILOI, W. K., AND SCHR6DEa- PrtEIKSCHAT, W. Latency hiding in message-passing architectures. In Proc. 8th lnternat. Parallel Processing Symposium (Cancun/Mexico, 1994), IEEE Computer Society, pp. 704-709.

Digital Library

[5]

CHAKRAnArrrl, S., ASD YELIC#, K. implementing an irregular application on a distributed memory multiprocessor. In Proc. Symposium on Principles and Practice of Parallel Programming (PPoPP '95) (San Diego/USA, 1993).

Digital Library

[6]

CORDSEN. J., }')OHL. H.-W. AND SCHR{)DER- PREIKSCHAT: #~. Performance considerations in software multicast. In Proc. 1 l th A CM International Conference on Supercornputing (ICS '97) (1997).

Digital Library

[7]

CULLER, D. E. Multithreading: Fundamental limits, potential gains, and alternatives, in Multithreaded Computer Architecture . A Summary of the State of the Art (1994), R. A. Iannucci, G. R. Gao, R. H. Halstead, and B. Smith, Eds., Kluwer Academic Publishers, Boston/London/Dortrecht, pp. 97-138.

[8]

FOSTER, I., KESSFLMAN, C., AND TUECKE, S. The Nexus approach to integrating multithreading and communication. Journal of Parallel and Distributed Systems 37 (1996), 70--82.

Digital Library

[9]

GILOI, W. K., BRUNING, U., AND SCHRODER- PREIKSCHAT: W. }kIANNA: Prototype of a distributed memory architecture with maximized sustained performance. In Proc. Euromicro PDP96 Workshop (1996), IEEE-CS Press.

Digital Library

[10]

HAINES, M., AND BOEHM, W. On the design of distributed memory Sisal. Journal of Programming Languages, fall issue (1993), 209-240.

[11]

HAMMOND, K. Parallel functional programming: An introduction. In Proc. PASCO (Linz/Austria, 1994).

[12]

HC.NDREN, L. J., GAO, G. R., TANG, X., ZHU, Y., XUE, X., CAI, H. AND OUELLET, P. Compiling C for the EARTH multithreaded architecture, in Proc. Internat. Conf. on Parallel Architectures and Compilation Techniques (PACT '96} (Boston/USA, October 1996), pp. 12-23.

Digital Library

[13]

HUM, H. H., MAQUELIN, O., THEOBALD, K. B., TXAN, X.-M., AND ET At. A design study of the EARTH multiprocessor. In Proc. Internat. Conf. on Parallel Architectures and Compilation Techniques (PACT '95) (Limassol/Cyprus, 1995).

Digital Library

[14]

Jo#.aG, C. F., AND KUSZMAUL, B. C. Massively parallel chess, in Third. DIMA CS Parallel Implementation Challenge at Rutgers University (October 1994).

[15]

KocK, G., ENr)LER, M., GUBrTOSI, M. D., AND SONG, S. W. Towards transparent parallelization of connectionist systems. In Proc. 9th Internat. Conf. on Par. allel and Distributed Computing Systems (PDCS '96) (Dijon/Prance 1996).

[16]

KUMAR, V., GRAMA, A., GUPTA, A., AND KARYPIS, G. Introduction to Parallel Computing. Design and Analysis of Algorithms. Benjamin/Cummings Publ. Company, 1994.

Digital Library

[17]

LECvN, Y., BOSEa, B., DEm(ER, J. S., HENDERSON, D., HOWARD, R. E., HUBBARD, W., AND JACKEL, L. D. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1 (1989), 541-551.

Digital Library

[18]

MAQUELIN, O., GAO, G. R., HUM, H. H. J., THEOBALD, K. B., AND TIAN, X.-M. Polling watchdog: Combining polling and interrupts for efficient message handling. In Proc. #3rd An. lnternat. Sympo. slum on Computer Architedure (ISCA '96) (Philadelphia/USA, May 1996).

Digital Library

[19]

SERBEDZIJA, N. B. Simulating artificial neural networks on parallel machines. {EEE Computer (March 1996).

Digital Library

[20]

SODAN, A. Mapping Symbolzc Programs with Dynamic Tree Structure to Parallel Machines. Oldenbourg- Verlag, Miinchen/Wien, 1996.

[21]

TIAN, X.-M., NEMAWARKAR, S., GAO, G. R., HUM, H., MAQUELIN, O., SODAN, A., AND THEOBALD, K. Quantitative studies of data locality sensitivity on the EARTH multithreaded architecture: Preliminary results. In Proc. HiPC'96 (3rd lnternat. Conf. on High Performance Computing) (Trivandrum/India, December 1996).

Digital Library

[22]

YELICK, K., CHAKRABARTI, S., DEPRIT, E., JONES, J., KRISHNAMURTHY# A., AND WEN, C.-P. Parallel data structures for symbolic computation. In Workshop on Parallel Symbolic Languages and Systems (October 1995).

Cited By

Hu XTang XHua BTorrellas JChatterjee S(2006)High-performance IPv6 forwarding algorithm for multi-core and multithreaded network processorProceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/1122971.1122998(168-177)Online publication date: 29-Mar-2006
https://dl.acm.org/doi/10.1145/1122971.1122998
Gao GTheobald KGovindarajan RLeung CZiang Hu Haiping Wu Jizhu Lu del Cuvillo JJacquet AJanot VSterling T(2003)Programming models and system software for future high-end computing systems: work-in-progressProceedings International Parallel and Distributed Processing Symposium10.1109/IPDPS.2003.1213378(8)Online publication date: 2003
https://doi.org/10.1109/IPDPS.2003.1213378
Gao GTheobald KHu ZWu HLu JPingali KStodghill PSterling TStevens RHereld M(2002)Next Generation System Software for Future High-End Computing SystemsProceedings of the 16th International Parallel and Distributed Processing Symposium10.5555/645610.661889Online publication date: 15-Apr-2002
https://dl.acm.org/doi/10.5555/645610.661889
Show More Cited By

Index Terms

Experiences with non-numeric applications on multithreaded architectures
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
  2. Machine learning
    1. Machine learning approaches
      1. Neural networks
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Data types and structures
      2. Language types
        Concurrent programming languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Distributed memory

Recommendations

Experiences with non-numeric applications on multithreaded architectures

Distributed-memory machines have proved successful for many challenging numerical programs that can be split into largely independent computation-intensive subtasks requiring little data exchange (although the amount of exchanged data may be large). ...
Exploring the performance of massively multithreaded architectures

We present a new scheme for evaluating the performance of multithreaded computers and demonstrate its application to the Cray MTA-2 and XMT supercomputers. Our scheme is based on the concept of clock cycles per element, \documentclass{article}\footskip=...
Generating Fine-Grain Multithreaded Applications Using a Multigrain Approach

The recent evolution in hardware landscape, aimed at producing high-performance computing systems capable of reaching extreme-scale performance, has reignited the interest in fine-grain multithreading, particularly at the intranode level. Indeed, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPOPP '97: Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming

June 1997

287 pages

ISBN:0897919068

DOI:10.1145/263764

Chairmen:
Rob Schreiber
Hewlett-Packard Labs, Palo Alto, CA
,
Keshav Pingali
Cornell Univ., Ithaca, NY
,
Editor:
Michael A. Berman

ACM SIGPLAN Notices Volume 32, Issue 7
July 1997
287 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/263767
Chairmen:
Rob Schreiber
Hewlett-Packard Labs, Palo Alto, CA
,
Keshav Pingali
Cornell Univ., Ithaca, NY
,
Editor:
A. Michael Berman
Issue’s Table of Contents

Copyright © 1997 ACM.

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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 June 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PPoPP97

Sponsor:

SIGPLAN

PPoPP97: Principles & Practices of Parallel Programming

June 18 - 21, 1997

Nevada, Las Vegas, USA

Acceptance Rates

PPOPP '97 Paper Acceptance Rate 26 of 86 submissions, 30%;

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
428
Total Downloads

Downloads (Last 12 months)104
Downloads (Last 6 weeks)15

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hu XTang XHua BTorrellas JChatterjee S(2006)High-performance IPv6 forwarding algorithm for multi-core and multithreaded network processorProceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/1122971.1122998(168-177)Online publication date: 29-Mar-2006
https://dl.acm.org/doi/10.1145/1122971.1122998
Gao GTheobald KGovindarajan RLeung CZiang Hu Haiping Wu Jizhu Lu del Cuvillo JJacquet AJanot VSterling T(2003)Programming models and system software for future high-end computing systems: work-in-progressProceedings International Parallel and Distributed Processing Symposium10.1109/IPDPS.2003.1213378(8)Online publication date: 2003
https://doi.org/10.1109/IPDPS.2003.1213378
Gao GTheobald KHu ZWu HLu JPingali KStodghill PSterling TStevens RHereld M(2002)Next Generation System Software for Future High-End Computing SystemsProceedings of the 16th International Parallel and Distributed Processing Symposium10.5555/645610.661889Online publication date: 15-Apr-2002
https://dl.acm.org/doi/10.5555/645610.661889
Gao GTheobald KZiang Hu Haiping Wu Jizhu Lu Sterling TPingali KStodghill PStevens RHereld M(2002)Next generation system software for future high-end computing systemsProceedings 16th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2002.1016578(8 pp)Online publication date: 2002
https://doi.org/10.1109/IPDPS.2002.1016578
Sodan A(2002)Applications on a multithreaded architectureParallel Computing10.1016/S0167-8191(01)00127-228:1(3-33)Online publication date: 7-Jan-2002
https://dl.acm.org/doi/10.1016/S0167-8191%2801%2900127-2
Goudreau MLang KNarlikar GRao SMiller GRamachandran V(1999)BOS is bossProceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures10.1145/305619.305632(115-125)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1145/305619.305632
Sodan ATorra VBryant BLamont GHaddad HCarroll J(1999)Hierarchical fuzzy configuration of implementation strategiesProceedings of the 1999 ACM symposium on Applied computing10.1145/298151.298343(250-259)Online publication date: 28-Feb-1999
https://dl.acm.org/doi/10.1145/298151.298343
Sodan A(1999)Examples of Fuzziness in Compilers and Runtime SystemsCollaboration between Human and Artificial Societies10.1007/10703260_3(43-61)Online publication date: 1999
https://doi.org/10.1007/10703260_3

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten