Cited By
View all- Monteiro PMonteiro MGuerra E(2012)Documenting patterns with business process modelsProceedings of the 19th Conference on Pattern Languages of Programs10.5555/2821679.2831285(1-16)Online publication date: 19-Oct-2012
Parallelizing irregular algorithms: a pattern language
Article No.: 3, Pages 1 - 18
Abstract
Outside of the high-performance computing domain, many applications are irregular in the sense that opportunities to exploit parallelism change throughout the computation, due to the use of complex, pointer-based data structures such as lists and graphs. However, the parallel programming community has relatively little experience in parallelizing irregular applications, and we presently lack a deep understanding of the structure of parallelism and locality in the algorithms that underlie these applications. In this context, irregular algorithms pose a challenging problem to current parallelization methods and techniques.
In recent years, the Galois project has proposed an approach for parallelizing irregular algorithms and applications that is based on a small set of simple abstractions. In this paper, we describe the Galois approach by means of a pattern language for parallel programming, thereby highlighting the key features of this approach, and elucidating more generally the concurrency patterns in irregular algorithms.
References
[1]
Asenjo, R., Corbera, F., Gutiérrez, E., et al., Optimization techniques for irregular and pointer-based programs. in, (2004), 2--13.
[2]
Bai, T., Shen, X., Zhang, C., et al. A key-based adaptive transactional memory executor International Parallel & Distributed Processing Symposium, IPDPS 2007, Long Beach, CA, 2007, 1--8.
[3]
Biswas, R., Oliker, L. and Shan, H. Parallel computing strategies for irregular algorithms. Annual Review of Scalable Computing.
[4]
Buschmann, F., Meunier, R., Rohnert, H., et al. A system of patterns: Pattern-oriented software architecture, Wiley New York, 1996.
[5]
Chamberlain, B., Choi, S., Lewis, E., et al. ZPL: A machine independent programming language for parallel computers. IEEE T. Software Eng., 26 (3). 197.
[6]
Chandra, S., Parashar, M. and Ray, J. Dynamic structured partitioning for parallel scientific applications with pointwise varying workloads Proc. 20th IEEE/ACM International Parallel and Distributed Processing Symposium, Rhodes Island, Greece, 2006.
[7]
Chrisochoides, N., Lee, C. and Lowekamp, B. Mesh generation and optimistic computation on the grid. in Performance analysis and grid computing, Kluwer Academic Publishers, 2004, 231--250.
[8]
Codrescu, L., Wills, D. and Meindl, J. Architecture of the Atlas chip-multiprocessor: Dynamically parallelizing irregular applications. IEEE T. Comput., 50 (1). 67--82.
[9]
Cormen, T. H., Leiserson, C. E. and Rivest, R. L. Introduction to algorithms. MIT Press, Cambridge,Mass.; London, 1990.
[10]
Dally, W. A VLSI architecture for concurrent data structures. Kluwer Academic Publishers, 1987.
[11]
Das, S., Adaptive protocols for parallel discrete event simulation. in, (1996), IEEE Computer Society Washington, DC, USA, 186--193.
[12]
Diaconescu, R. and Zima, H. An approach to data distributions in Chapel. Int. J. High. Perform. C, 21 (3). 313.
[13]
N-Body Pattern Language, http://parlab.eecs.berkeley.edu/wiki/patterns/n-body_methods, February, 2010
[14]
Elsner, U. Graph partitioning: a survey Tech. Rep. 97--27, Technische Universität Chemnitz, Chemnitz, Germany, 1997.
[15]
Even, S. Graph algorithms. WH Freeman & Co. New York, NY, USA, 1979.
[16]
Fisher, J. A. Very Long Instruction Word architectures and the ELI-512 Proc. 10th annual international symposium on Computer architecture, ACM, Stockholm, Sweden, 1983, 140--150.
[17]
Fjallstrom, P. Algorithms for graph partitioning: A survey. Computer and Information Science, 3 (10).
[18]
Fonlupt, C., Marquet, P. and Dekeyser, J. Data-parallel load balancing strategies. Parallel Computing, 24 (11). 1665--1684.
[19]
Gamma, E., Helm, R., Johnson, R., et al. Design Patterns: Elements of Reusable Object-Oriented.
[20]
Gelernter, D. Generative communication in Linda. ACM T. Progr. Lang. Sys., 7 (1). 80--112.
[21]
Gendron, B. and Crainic, T. Parallel branch-and-bound algorithms: survey and synthesis. Operations Research, 42 (6). 1042--1066.
[22]
Gupta, M. and Nim, R. Techniques for speculative run-time parallelization of loops Proc. ACM/IEEE conference on Supercomputing, IEEE Computer Society, San Jose, CA, 1998, 1--12.
[23]
Gutierrez, E., Asenjo, R., Plata, O., et al. Automatic parallelization of irregular applications. Parallel Comp., 26 (13--14). 1709--1738.
[24]
Hennessy, J., Patterson, D., Goldberg, D., et al. Computer architecture: a quantitative approach. Morgan Kaufmann, 2003.
[25]
Herlihy, M. and Moss, J., Transactional memory: Architectural support for lock-free data structures. in, (1993), ACM, 300.
[26]
Jefferson, D. Virtual time. ACM T. Progr. Lang. Sys., 7 (3). 425.
[27]
Jha, R., Kamrad, J. and Cornhill, D. Ada program partitioning language: A notation for distributing Ada programs. IEEE T. Software Eng., 15 (3). 271--280.
[28]
Karypis, G. and Kumar, V. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J. Sci. Comput., 20 (1). 359--392.
[29]
Keutzer, K. and Mattson, T. Our Pattern Language (OPL): A Design Pattern Language for Engineering (Parallel) Software ParaPLoP, 2009.
[30]
Knopp, J. and Reich, M., A Workpool Model for Parallel Computing. in First International Workshop on High Level Programming Models and Supportive Environments (HIPS), (Honolulu, HI, USA, 1996), IEEE Computer Press.
[31]
Koffman, E. and Wolfgang, P. Objects, abstraction, data structures and design using C++.
[32]
Krishnan, V. and Torrellas, J. A chip-multiprocessor architecture with speculative multithreading. Computers, IEEE Transactions on, 48 (9). 866--880.
[33]
Kulkarni, M. The Galois System: Optimistic Parallelization of Irregular Programs, Cornell University, 2008.
[34]
Kulkarni, M., Burtscher, M., Pingali, K., et al., Lonestar: A suite of parallel irregular programs. in IEEE International Symposium on Performance Analysis of Systems and Software, (2009), 65--76.
[35]
Kulkarni, M., Carribault, P., Pingali, K., et al., Scheduling strategies for optimistic parallel execution of irregular programs. in, (2008), ACM, 217--228.
[36]
Kulkarni, M., Pingali, K., Walter, B., et al. Optimistic parallelism requires abstractions. Commun. ACM, 52 (9). 89--97.
[37]
Kumar, S., Hughes, C. J. and Nguyen, A. Carbon: architectural support for fine-grained parallelism on chip multiprocessors Proc. 34th International Symposium on Computer architecture, ACM, San Diego, California, USA, 2007, 162--173.
[38]
Lamport, L. Time, clocks, and the ordering of events in a distributed system. in Commun. ACM, ACM, 1978, 558--565.
[39]
Leung, J. Handbook of scheduling: algorithms, models, and performance analysis. Chapman & Hall, 2004.
[40]
Lim, J. and Johnson, R. The heart of object-oriented concurrent programming. ACM SIGPLAN Notices, 24 (4). 167.
[41]
Liu, Z. Dynamic scheduling of parallel computations. Theor. Comput. Sci., 246 (1--2). 239--252.
[42]
Loveman, D. B. High Performance Fortran. IEEE Parallel Distrib. Technol., 1 (1). 25--42.
[43]
Lublinerman, R., Chaudhuri, S. and Cerny, P. Parallel programming with object assemblies Proc. 24th ACM SIGPLAN Conference on Object Oriented programming systems languages and applications, ACM, Orlando, Florida, USA, 2009, 61--80.
[44]
Marcuello, P. and González, A., Control and data dependence speculation in multithreaded processors. in Proc. Workshop on Multithreaded Execution, Architecture and Compilation, (1998), 98--102.
[45]
Marcuello, P. and González, A. A Quantitative Assessment of Thread-Level Speculation Techniques Proc.14th International Symposium on Parallel and Distributed Processing, IEEE Computer Society, 2000, 595.
[46]
Mattson, T., Sanders, B. and Massingill, B. Patterns for parallel programming. Addison-Wesley Professional, 2004.
[47]
Méndez-Lojo, M., Nguyen, D., Prountzos, D., et al. Structure-driven optimizations for amorphous data-parallel programs Proc. 15th ACM SIGPLAN symposium on Principles and practice of parallel programming, ACM, Bangalore, India, 2010, 3--14.
[48]
Model, S. Programming in the Partitioned Global Address Space Model. Tutorial at Supercomputing.
[49]
Monteiro, P. and Monteiro, M. A Pattern Language for Parallelizing Irregular Algorithms 2nd Annual Conference on Parallel Programming Patterns (ParaPLoP), Carefree, Arizona, 2010.
[50]
Navabi, A., Zhang, X. and Jagannathan, S. Quasi-static scheduling for safe futures Proc. 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, ACM, Salt Lake City, UT, USA, 2008, 23--32.
[51]
Oplinger, J., Heine, D., Liao, S., et al. Software and hardware for exploiting speculative parallelism with a multiprocessor. Computer Systems Laboratory Tech. Rep. CSL-TR-97-715, Stanford University.
[52]
Pancake, C. and Bergmark, D. Do parallel languages respond to the needs of scientific programmers? IEEE Computer, 23 (12). 13--23.
[53]
Pingali, K., Kulkarni, M., Nguyen, D., et al. Amorphous Data-parallelism in Irregular Algorithms, The University of Texas at Austin, Department of Computer Sciences, Austin, TX, USA, 2009.
[54]
Pingali, K., Nguyen, D., Kulkarni, M., et al. The tao of parallelism in algorithms. SIGPLAN Not., 46 (6). 12--25.
[55]
Rauchwerger, L. and Padua, D., The LRPD test: Speculative run-time parallelization of loops with privatization and reduction parallelization. in Proc. Programming Language Design and Implementation, (1995), ACM New York, NY, USA, 218--232.
[56]
Reinders, J. Intel Threaded Building Blocks, O'Reilly Press, 2007.
[57]
Rünger, G. and Schwind, M., Parallelization Strategies for Mixed Regular-Irregular Applications on Multicore-Systems. in Proc. 8th International Symposium on Advanced Parallel Processing Technologies, (Rapperswil, Switzerland, 2009), Springer-Verlag, 375--388.
[58]
Schmidt, D., Stal, M., Rohnert, H., et al. Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, Volume 2. Wiley, 2000.
[59]
Shewchuk, J. Delaunay refinement algorithms for triangular mesh generation. Comp. Geom.-Theor. Appl., 22 (1--3). 21--74.
[60]
Sinnen, O. Task scheduling for parallel systems. Wiley-Blackwell, 2007.
[61]
Steffan, J., Colohan, C., Zhai, A., et al. A scalable approach to thread-level speculation. ACM Comp. Ar., 28 (2). 1--12.
[62]
Sugerman, J., Fatahalian, K., Boulos, S., et al. GRAMPS: A programming model for graphics pipelines. ACM T. Graphic, 28 (1). 4.
[63]
Sui, X., Nguyen, D., Burtscher, M., et al. Parallel graph partitioning on multicore architectures. Languages and Compilers for Parallel Computing. 246--260.
[64]
Tomasulo, R. An efficient algorithm for exploiting multiple arithmetic units. IBM J. Res. Dev., 11 (1). 25--33.
[65]
Verma, C. Multithreaded Delaunay Triangulation. College of William and Mary, Williamsburg, VA.
[66]
von Praun, C., Ceze, L. and Cascaval, C. Implicit parallelism with ordered transactions Proc. ACM SIGPLAN symposium on Principles and practice of parallel programming, ACM, San Jose, California, USA, 2007, 79--89.
[67]
Wirth, N. Algorithms + Data Structures=programs. Prentice Hall Englewood Cliffs, New Jersey, 1985.
Index Terms
- Parallelizing irregular algorithms: a pattern language
Recommendations
Flattening and parallelizing irregular, recurrent loop nests
PPOPP '95: Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programmingIrregular loop nests in which the loop bounds are determined dynamically by indexed arrays are difficult to compile into expressive parallel constructs, such as segmented scans and reductions. In this paper, we describe a suite of transformations to ...
Flattening and parallelizing irregular, recurrent loop nests
Irregular loop nests in which the loop bounds are determined dynamically by indexed arrays are difficult to compile into expressive parallel constructs, such as segmented scans and reductions. In this paper, we describe a suite of transformations to ...
A pattern language for parallelizing irregular algorithms
ParaPLoP '10: Proceedings of the 2010 Workshop on Parallel Programming PatternsIn irregular algorithms, data set's dependences and distributions cannot be statically predicted. This class of algorithms tends to organize computations in terms of data locality instead of parallelizing control in multiple threads. Thus, opportunities ...
Comments
Information & Contributors
Information
Published In
Copyright © 2011 Owner/Author.
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
- Hillside Group: Hillside Group
- ACM: Association for Computing Machinery
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 October 2011
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
PLoP 11
Sponsor:
- Hillside Group
- ACM
Acceptance Rates
Overall Acceptance Rate 28 of 36 submissions, 78%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 108Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)1
Reflects downloads up to 03 Nov 2024
Other Metrics
Citations
Cited By
View all- Monteiro PMonteiro MGuerra E(2012)Documenting patterns with business process modelsProceedings of the 19th Conference on Pattern Languages of Programs10.5555/2821679.2831285(1-16)Online publication date: 19-Oct-2012
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in