Experiences with non-numeric applications on multithreaded architectures
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
[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).
[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).
[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.
[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).
[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).
[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.
[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.
[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.
[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).
[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.
[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.
[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).
[19]
SERBEDZIJA, N. B. Simulating artificial neural networks on parallel machines. {EEE Computer (March 1996).
[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).
[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).
Index Terms
- Experiences with non-numeric applications on multithreaded architectures
Recommendations
Experiences with non-numeric applications on multithreaded architectures
PPOPP '97: Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programmingDistributed-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
July 1997
287 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/263767
- Chairmen:
- Rob Schreiber,
- Keshav Pingali,
- Editor:
- A. Michael Berman
June 1997287 pages
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]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 June 1997
Published in SIGPLAN Volume 32, Issue 7
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations8Total Citations
- 396Total Downloads
- Downloads (Last 12 months)80
- Downloads (Last 6 weeks)8
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in