Parallelizing irregular and pointer-based computations automatically: Perspectives from logic and constraint programming

Irregular computations pose some of the most interesting and challenging pr oblems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such compu tations often use dynamic data structures, which make heavy use of pointers . This complicates all the steps of a parallelizing compiler, from independ ence detection to task partitioning and placement. Starting in the mid 80s there has been significant progress in the development of parallelizing com pilers for logic programming land more recently, constraint programming) re sulting in quite capable parallelizers. The typical applications of these p aradigms frequently involve irregular computations, and make heavy use of d ynamic data structures with pointers, since logical variables represent in practice a well-behaved form of pointers. This arguably makes the technique s used in these compilers potentially interesting. In this paper, we introd uce in a tutorial way, some of the problems faced by parallelizing compiler s for logic and constraint programs and provide pointers to some of the sig nificant progress made in the area. In particular, this work has resulted i n a series of achievements in the areas of inter-procedural pointer aliasin g analysis for independence detection, cost models and cost analysis, cactu s-stack memory management, techniques for managing speculative and irregula r computations through task granularity control and dynamic task allocation (such as work-stealing schedulers), etc. (C) 2000 Elsevier Science B.V. Al l rights reserved.