Modeling the benefits of mixed data and task parallelism

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Modeling the benefits of mixed data and task parallelism

Full text

Pdf (1.13 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures table of contents

Santa Barbara, California, United States

Pages: 74 - 83

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

Soumen Chakrabarti	Computer Science Division, U. C. Berkeley, CA
James Demmel	Computer Science Division and Mathematics Department, U. C. Berkeley, CA
Katherine Yelick	Computer Science Division, U. C. Berkeley, CA

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 31, Citation Count: 15

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/215399.215423 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Remzi H. Arpaci , David E. Culler , Arvind Krishnamurthy , Steve G. Steinberg , Katherine Yelick, Empirical evaluation of the CRAY-T3D: a compiler perspective, Proceedings of the 22nd annual international symposium on Computer architecture, p.320-331, June 22-24, 1995, S. Margherita Ligure, Italy
	2	Scott B. Baden, Programming abstractions for dynamically partitioning and coordinating localized scientific calculations running on multiprocessors, SIAM Journal on Scientific and Statistical Computing, v.12 n.1, p.145-157, Jan. 1991 [doi>10.1137/0912008]
	3	Z. Bat and J. Demmel. Design of a parallel nonsymmetric eigenroutine toolbox, Part I. In Proceedings of the Sixth SIAM Conference on Parallel Proceesmg for Scientific Computing. SIAM, 1993.
	4	K. BelkhaIe and P. Banerjee. An approximate algorithm for the partitionable independent task scheduling problem. in International Conference on Parallel Processing (ICPP). IEEE, August 1990. Full version in technical reports UILU-ENG-90-2253 and CRHC-90-15, University of illinois, Urbana.
	5	C. Bischof, S. Huss-Lederman, X. Sun, A. Tsao, and T. TurnbulI. Parallel performance of a symmetric eigensolver based on the invariant subspace decomposition approach. In Scalable High Performance Computing Conference, pages 32-39, Knoxville, TN, May 1994. IEEE.
	6	S. Chatterjee. Compiling data-parallel programs for efficient execution on shared-memory multiprocessors. Technical Report CMU-CS-91-189, CMU, Pittsburgh, PA 15213, October 1991.
	7	J. Cuppen. A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math., 36:177-195, 1981.
	8	J. Demmel, J. Dongarra, R. van de Geijn, and D. Walker. LAPACK for distributed memory machines: the next generation. In Proceedings of the Sixth SIAM Conference on Parallel Proceesing for Scientific Computing. SIAM, 1993.
	9	J. Demmel and K. Stanley. The performance of finding eigenvalues and eigenvectors of dense symmetric matrices on distributed memory computers. In Proceedings of the Seventh SIAM Conference on Parallel Proceesing .for Scientific Computing. SIAM, 1994.
	10	F. Desprez , B. Tourancheau , J. J. Dongarra, LAPACK Working Note 67: Performance Complexity of LU Factorization with Efficient Pipelining and Overlap on a Multiprocessor, University of Tennessee, Knoxville, TN, 1993
	11	Anja Feldmann , Jiří Sgall , Shang-Hua Teng, Dynamic scheduling on parallel machines, Proceedings of the 32nd annual symposium on Foundations of computer science, p.111-120, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185355]
	12	I. Foster, M. Xu, B. Avalani, and A. Chowdhary. A compilation system that integrates high performance Fortran and Fortran M. in Scalable High Performance Computing Conference, pages 293-300. IEEE, 1994.
	13	Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
	14	J. R. Gilbert , R. E. Tarjan, The analysis of a nested dissection algorithm, Numerische Mathematik, v.50 n.4, p.377-404, FEB. 1987 [doi>10.1007/BF01396660]
	15	Xining Li , He Huang, On the Concurrency of C++, Proceedings of the Fifth International Conference on Computing and Information, p.215-219, May 27-29, 1993
	16	Joseph W. H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review, v.34 n.1, p.82-109, March 1992 [doi>10.1137/1034004]
	17	Walter Ludwig , Prasoon Tiwari, Scheduling malleable and nonmalleable parallel tasks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.167-176, January 23-25, 1994, Arlington, Virginia, United States
	18	Stephen S. Luna, Implementing an Efficient Portable Global Memory Layer on, University of California at Berkeley, Berkeley, CA, 1994
	19	C. R. Mechoso, C.-C. Ma, J. Farrara, J. A. Spahr, and R. W. Moore. Parallelization and distribution of a coupled atmosphere-ocean general circulation model. Monthly Weather Review, 121(7):2062-2076, 1993.
	20	S. Ramaswamy, S. Sapatnekar, and P. Banerjee. A convex programming approach for exploiting data and functional parallelism on distributed memory multiprocessors. In International Conference on Parallel Processing (ICPP). IEEE, 1994.
	21	J. P#utter. A serial implementation of Cuppen's divide and conquer algorithm for the symmetric eigenvalue problem. Mathematics Dept. Master's Thesis available by anonymous ftp to tr-ftp.cs.berkeley.edu, directory pub/techreports/cs/csd-94-799, file all.ps, University of California, 1994.
	22	Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
	23	K. Stanley and J. Demmel. Modeling the performance of linear systems solvers on distributed memory multiprocessots. Technical report, University of California, Berkeley, CA 94720, 1994. In preparation.
	24	Jaspal Subhlok , James M. Stichnoth , David R. O'Hallaron , Thomas Gross, Exploiting task and data parallelism on a multicomputer, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.13-22, May 19-22, 1993, San Diego, California, United States
	25	John Turek , Joel L. Wolf , Philip S. Yu, Approximate algorithms scheduling parallelizable tasks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.323-332, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141909]
	26	Chih-Po Wen , Katherine A. Yelick, Parallel timing simulation on a distributed memory multiprocessor, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.130-135, November 07-11, 1993, Santa Clara, California, United States
	27	R. C Whaley, LAPACK Working Note 73: Basic Linear Algebra Communication Subprograms: Analysis and Implementation Across Multiple Parallel Architectures, University of Tennessee, Knoxville, TN, 1994

CITED BY 15

	Saniya Ben Hassen , Henri E. Bal , Ceriel J. H. Jacobs, A task- and data-parallel programming language based on shared objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1131-1170, Nov. 1998
	Jaspar Subhlok , Gary Vondran, Optimal latency-throughput tradeoffs for data parallel pipelines, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.62-71, June 24-26, 1996, Padua, Italy
	Laura Susan Blackford , J. Choi , A. Cleary , A. Petitet , R. C. Whaley , J. Demmel , I. Dhillon , K. Stanley , J. Dongarra , S. Hammarling , G. Henry , D. Walker, ScaLAPACK: a portable linear algebra library for distributed memory computers - design issues and performance, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.5-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
	Saniya Ben Hassen , Henri Bal, Integrating task and data parallelism using shared objects, Proceedings of the 10th international conference on Supercomputing, p.317-324, May 25-28, 1996, Philadelphia, Pennsylvania, United States
	Cong Fu , Tao Yang, Space and time efficient execution of parallel irregular computations, ACM SIGPLAN Notices, v.32 n.7, p.57-68, July 1997
	Thomas Rauber , Gudula Rünger, Library support for hierarchical multi-processor tasks, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-10, November 16, 2002, Baltimore, Maryland
	Tao Yang , Cong Fu, Space/time-efficient scheduling and execution of parallel irregular computations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1195-1222, Nov. 1998
	Thomas Rauber , Gudula Rünger, Tlib: a library to support programming with hierarchical multi-processor tasks, Journal of Parallel and Distributed Computing, v.65 n.3, p.347-360, March 2005
	Savina Bansal , Padam Kumar , Kuldip Singh, An improved two-step algorithm for task and data parallel scheduling in distributed memory machines, Parallel Computing, v.32 n.10, p.759-774, November, 2006
	Kento Aida , Henri Casanova, Scheduling mixed-parallel applications with advance reservations, Proceedings of the 17th international symposium on High performance distributed computing, June 23-27, 2008, Boston, MA, USA
	Yihua Bai , Robert C. Ward, A parallel symmetric block-tridiagonal divide-and-conquer algorithm, ACM Transactions on Mathematical Software (TOMS), v.33 n.4, p.25-es, August 2007
	Thomas Rauber , Gudula Rünger, Mixed task and data parallel executions in general linear methods, Scientific Programming, v.15 n.3, p.137-155, August 2007
	Frederic Suter, Scheduling ?-Critical Tasks in mixed-parallel applications on a national grid, Proceedings of the 8th IEEE/ACM International Conference on Grid Computing, p.2-9, September 19-21, 2007
	Mohammad Zalfany Urfianto , Tsuyoshi Isshiki , Arif Ullah Khan , Dongju Li , Hiroaki Kunieda, Decomposition of Task-Level Concurrency on C Programs Applied to the Design of Multiprocessor SoC, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.7, p.1748-1756, July 2008
	Kento Aida , Henri Casanova, Scheduling mixed-parallel applications with advance reservations, Cluster Computing, v.12 n.2, p.205-220, June 2009