Optimizing code parallelization through a constraint network based approach

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: Manuel Arenaz , Juan Touriño , Ramón Doallo, A GSA-based compiler infrastructure to extract parallelism from complex loops, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782842]
• 2: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 3: V. Beletskyy , R. Drazkowski , M. Liersz, An Approach to Parallelizing Non-Uniform Loops with the Omega Calculator, Proceedings of the International Conference on Parallel Computing in Electrical Engineering, p.119, September 22-25, 2002
• 4: Kiran Bondalapati, Parallelizing DSP nested loops on reconfigurable architectures using data context switching, Proceedings of the 38th conference on Design automation, p.273-276, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378483]
• 5: Weng-Long Chang , Chih-Ping Chu , Michael Ho, Exploitation of parallelism to nested loops with dependence cycles, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.12, p.729-742, December 2004 [doi>10.1016/j.sysarc.2004.06.001]
• 6: G. Chen , M. Kandemir , M. Karakoy, A Constraint Network Based Approach to Memory Layout Optimization, Proceedings of the conference on Design, Automation and Test in Europe, p.1156-1161, March 07-11, 2005 [doi>10.1109/DATE.2005.6]
• 7: Guilin Chen , O. Ozturk , M. Kandemir , I. Kolcu, Integrating loop and data optimizations for locality within a constraint network based framework, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.279-282, November 06-10, 2005, San Jose, CA
• 8: Rina Dechter, Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 9: R. Dechter , J. Pearl, Network-based heuristics for constraint-satisfaction problems, Artificial Intelligence, v.34 n.1, p.1-38, Dec. 1987 [doi>10.1016/0004-3702(87)90002-6]
• 10: Georgios Goumas , Nikolaos Drosinos , Maria Athanasaki , Nectarios Koziris, Automatic parallel code generation for tiled nested loops, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968184]
• 11: Karin Högstedt , Larry Carter , Jeanne Ferrante, On the Parallel Execution Time of Tiled Loops, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.307-321, March 2003 [doi>10.1109/TPDS.2003.1189587]
• 12: I. Kadayif , M. Kandemir , M. Karakoy, An energy saving strategy based on adaptive loop parallelization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513968]
• 13: Amy W. Lim , Gerald I. Cheong , Monica S. Lam, An affine partitioning algorithm to maximize parallelism and minimize communication, Proceedings of the 13th international conference on Supercomputing, p.228-237, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305197]
• 14: Bingfeng Mei , Serge Vernalde , Diederik Verkest , Hugo De Man , Rudy Lauwereins, Exploiting Loop-Level Parallelism on Coarse-Grained Reconfigurable Architectures Using Modulo Scheduling, Proceedings of the conference on Design, Automation and Test in Europe, p.10296, March 03-07, 2003
• 15: Angeles Navarro , Emilio Zapata , David Padua, Compiler Techniques for the Distribution of Data and Computation, IEEE Transactions on Parallel and Distributed Systems, v.14 n.6, p.545-562, June 2003 [doi>10.1109/TPDS.2003.1206503]
• 16: Laura Ricci, Automatic Loop Parallelization: An Abstract Interpretation Approach, Proceedings of the International Conference on Parallel Computing in Electrical Engineering, p.112, September 22-25, 2002
• 17: Edward Tsang, A Glimpse of Constraint Satisfaction, Artificial Intelligence Review, v.13 n.3, p.215-227, June 1999 [doi>10.1023/A:1006558104682]
• 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

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Performance

Keywords:
chip multiprocessing, compiler, constraint network