Optimizing code parallelization through a constraint network based approach
Pages 863 - 688
Abstract
Increasing employment of chip multiprocessors in embedded computing platforms requires a fresh look at conventional code parallelization schemes. In particular, any compiler-based parallelization scheme for chip multiprocessors should account for the fact that interprocessor communication is cheaper than off-chip memory accesses in these architectures. Based on this observation, this paper proposes a constraint network based approach to code parallelization for chip multiprocessors. Constraint networks have proven to be a useful mechanism for modeling and solving computationally intensive tasks in artificial intelligence. They operate by expressing a problem as a set of variables, variable domains and constraints and define a search procedure that tries to satisfy the constraints (an acceptable subset of them) by assigning values to variables from their specified domains. This paper demonstrates that it is possible to use a constraint network based formulation for the problem of code parallelization for chip multiprocessors. Our experimental evaluation shows that not only a constraint network based approach is feasible for our problem but also highly desirable since it outperforms all other parallelization schemes tested in our experiments.
References
[1]
M. Arenaz, J. Tourino, and R. Doallo. A gsa-based compiler infrastructure to extract parallelism from complex loops. In Proc. of the 17th Annual International Conference on Supercomputing, pages 193--204, 2003.
[2]
T. Austin, E. Larson, and D. Ernst. Simplescalar: An infrastructure for computer system modeling. IEEE Computer, 35(2):59--67, 2002.
[3]
V. Beletskyy, R. Drazkowski, and M. Liersz. An approach to parallelizing non-uniform loops with the omega calculator. In Proc. of the International Conference on Parallel Computing in Electrical Engineering, 2002.
[4]
K. Bondalapati. Parallelizing dsp nested loops on reconfigurable architectures using data context switching. In Proc. of the 38th Design Automation Conference, pages 273--276, 2001.
[5]
W.-L. Chang, C.-P. Chu, and M. Ho. Exploitation of parallelism to nested loops with dependence cycles. Journal on System Architecture, 50(12):729--742, 2004.
[6]
G. Chen, M. Kandemir, and M. Karakoy. A constraint network based approach to memory layout optimization. In Proc. of the Conference on Design, Automation and Test in Europe, pages 1156--1161, 2005.
[7]
G. Chen, O. Ozturk, M. Kandemir, and I. Kolcu. Integrating loop and data optimizations for locality within a constraint network based framework. In Proc. of International Conference on Computer-Aided Design, 2005.
[8]
R. Dechter. Constraint Processing. Morgan Kaufmann Publishers Inc., 2003.
[9]
R. Dechter and J. Pearl. Network-based heuristics for constraint-satisfaction problems. Artificial Intelligence, 34(1):1--38, 1987.
[10]
G. Goumas, N. Drosinos, M. Athanasaki, and N. Koziris. Automatic parallel code generation for tiled nested loops. In Proc. of the ACM Symposium on Applied Computing, pages 1412--1419, 2004.
[11]
K. Hogstedt, L. Carter, and J. Ferrante. On the parallel execution time of tiled loops. IEEE Transactions on Parallel Distributed Systems, 14(3):307--321, 2003.
[12]
I. Kadayif, M. Kandemir, and M. Karakoy. An energy saving strategy based on adaptive loop parallelization. In Proc. of the 39th Design Automation Conference, pages 195--200, 2002.
[13]
A. W. Lim, G. I. Cheong, and M. S. Lam. An affine partitioning algorithm to maximize parallelism and minimize communication. In Proc. of the 13th International Conference on Supercomputing, pages 228--237, 1999.
[14]
B. Mei, S. Vernalde, D. Verkest, H. D. Man, and R. Lauwereins. Exploiting loop-level parallelism on coarse-grained reconfigurable architectures using modulo scheduling. In Proc. of the Conference on Design, Automation and Test in Europe, pages 10296--10301, 2003.
[15]
A. Navarro, E. Zapata, and D. Padua. Compiler techniques for the distribution of data and computation. IEEE Transactions on Parallel Distributed Systems, 14(6):545--562, 2003.
[16]
L. Ricci. Automatic loop parallelization: an abstract interpretation approach. In Proc. of the International Conference on Parallel Computing in Electrical Engineering, pages 112--118, 2002.
[17]
E. Tsang. A glimpse of constraint satisfaction. Artificial Intelligence Review, 13(3):215--227, 1999.
[18]
Y. Yu and E. H. D'Hollander. Loop parallelization using the 3d iteration space visualizer. Journal of Visual Languages and Computing, 12(2):163--181, 2001.
Index Terms
- Optimizing code parallelization through a constraint network based approach
Recommendations
Transparent Parallelization of Constraint Programming
The availability of commodity multicore and multiprocessor machines and the inherent parallelism in constraint programming search offer significant opportunities for constraint programming. These opportunities also present a fundamental challenge: how ...
Boosting MUC extraction in unsatisfiable constraint networks
One very fertile domain of applied Artificial Intelligence is constraint solving technologies. Especially, constraint networks that concern problems that can be represented using discrete variables, together with constraints on allowed instantiation ...
Automatically selecting and optimizing constraint solver procedures for object-constraint languages
MODULARITY Companion 2016: Companion Proceedings of the 15th International Conference on ModularityObject-constraint programming provides a design to integrate constraints with dynamic, object-oriented programming languages. It allows developers to encode multi-way constraints over objects and object collections using existing, object-oriented ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2006 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 July 2006
Check for updates
Author Tags
Qualifiers
- Article
Conference
Acceptance Rates
Overall Acceptance Rate 1,770 of 5,499 submissions, 32%
Upcoming Conference
DAC '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 189Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Nov 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