Array SSA for Explicitly Parallel Programs
The SSA framework has been separately extended to parallel programs and to sequential programs with arrays. This paper proposes an Array SSA form for parallel programs with either weak or strong memory consistency, with event-based synchronization or mutu
- PDF / 212,568 Bytes
- 8 Pages / 431 x 666 pts Page_size
- 65 Downloads / 220 Views
Abstract. The SSA framework has been separately extended to parallel programs and to sequential programs with arrays. This paper proposes an Array SSA form for parallel programs with either weak or strong memory consistency, with event-based synchronization or mutual exclusion, with parallel sections or indexed parallel constructs.
1
Introduction and Related Work
Extending reaching definition analyses (RDAs) and SSA to parallel programs has been a very active area of research. Reaching definition analyses (RDAs) for parallel programs were proposed in [4, 5, 2]. SSAs for various kinds of parallel language models were proposed in [8, 7, 9]. Several issues make comparing related papers a tricky task. Questions that arise include: (1) Does the paper apply element-wise to arrays? (Most papers apply to scalars only or to arrays considered as atomic variables, except for [2, 6]). (2) Does the paper consider both the weak and the strong model of memory consistency? (Most papers apply to only one of them) (3) Does the paper allow shared variables? (E.g., [5] doesn’t.) (4) Are event-based and mutual-exclusion synchronizations allowed? (5) Are indexed parallel constructs (parallel loops) and parallel sections allowed? Except for [2], related papers apply to parallel sections only. This paper answers Yes to all of these questions. This paper extends the RDA in [2] to handle strong consistency, event-based synchronization and mutual exclusion. Arrays are considered element-wise, and any array subscript is allowed [1]. We then derive a precise Parallel Array SSA form.
2
Problem Position
In Array SSA [6], each array is assigned by at most one statement. Converting a program to Array SSA form requires, therefore, to rename the original arrays. As in the sequential case, two issues threaten to modify the program’s data-flow while converting: Unpredictable control flow, due to e.g. ifs, and array subscripts too intricate to be understood by the static analysis. Classically, restoring the data-flow is then done using “value-merging” φ-functions [3]. ?
Partially supported by INRIA A3 and the German-French Procope Program
P. Amestoy et al. (Eds.): Euro-Par’99, LNCS 1685, pp. 383–390, 1999. c Springer-Verlag Berlin Heidelberg 1999
384
Jean-Fran¸cois Collard
However, a third problem occurs in parallel programs only. Consider the parallel sections in Fig. 1.(a). Since the two sections execute in any order, the value read in the last statement is not determined. Now consider the Parallel Array SSA version in Fig. 1.(b). Because arrays are renamed, an auxiliary function is inserted to restore the flow of data. As in [7], this function is called a π-function, to be formally defined in Section 3.3. par section a1(1) = ... end section section a2(1) = ... end section end par a3(1) = π (a1(1),a2(1)) .. = a3(1)
par section a(1) = ... end section section a(1) = ... end section end par .. = a(1)
(a) Original program
(b) Parallel Array SSA form (This paper)
do i = 1, n par section 1 x = ... end section section 2 ... = x 3 x = ... end
Data Loading...
