High-Level Abstractions for Symbolic Parallel Programming (Parallel Lisp Hacking Made Easy) Kinson Ho Report No. UCB//CSD-94-816 June 1994 Computer Science Division (EECS) University of California Berkeley, California 94720 High-Level Abstractions for Symbolic Parallel Programming (Parallel Lisp Hacking Made Easy) by Kinson Ho B.S. (Carnegie-Mellon University) 1985 M.S. (University of California at Berkeley) 1989 A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Computer Science in the GRADUATE DIVISION of the UNIVERSITY of CALIFORNIA at BERKELEY Committee in charge: Professor Paul N. Hil(cid:12)nger, Chair Professor David E. Culler Professor Philip Colella 1994 The dissertation of Kinson Ho is approved: Chair Date Date Date University of California at Berkeley 1994 High-Level Abstractions for Symbolic Parallel Programming (Parallel Lisp Hacking Made Easy) Copyright (cid:13)c 1994 by Kinson Ho This research was supported in part by NSF Grant CCR-84-51213. 1 Abstract High-Level Abstractions for Symbolic Parallel Programming (Parallel Lisp Hacking Made Easy) by Kinson Ho Doctor of Philosophy in Computer Science University of California at Berkeley Professor Paul N. Hil(cid:12)nger, Chair Symbolicapplications are characterizedby irregular and data-dependent patterns of control (cid:13)ow and data structure accesses. In this dissertation I propose a toolbox approach for writing parallel symbolic applications, including those with side e(cid:11)ects. Programs written using the high-level abstractions in this toolbox may be executed without modi(cid:12)cation on uniprocessors and multiprocessors. The toolbox is designed and implementedby parallelprogrammingexperts, and isintended for noviceparallel programmers. Most of the parallel programming issues are hidden from the program- mer. Each tool of the toolbox provides a stylized sequential interface, and programs that use these tools may be parallelized by using the parallel implementation of the toolbox. These tools are divided into parallelism abstractions and data-sharing ab- stractions. Parallelism abstractions represent common, time-consuming operations that o(cid:11)er good speedup potentials for parallel implementations. Data-sharing ab- stractions support common side-e(cid:11)ecting operations on shared objects, simplifying the coding of a large class of algorithms that modify shared data structures in a par- allel implementation. The thesis of this research is that a small toolbox is su(cid:14)cient for a large class of symbolic applications, and that there are e(cid:14)cient (sequential and parallel) implementations of the toolbox. To evaluate the feasibility of the toolbox approach for symbolic parallel program- ming, I constructed a prototype toolbox of commonly used abstractions, and con- verted two signi(cid:12)cant applications to use the toolbox. The applications include a 2 constraint satisfaction system and a type analysis system. These applications have been developed by other authors, and contain approximately 8,000 lines of Common Lisp each. They are much larger than what other researchers have typically used to evaluate their symbolic parallel programming systems. My experience with these two applications suggests that the toolbox approach for symbolic parallel programming is indeed successful. Many toolbox abstractions are common to the applications, and the toolbox version of either application may be ported between uniprocessors and multiprocessors without modi(cid:12)cation. Further- more, the toolbox may be used by novice parallel programmers to parallelize an application relatively easily, since all the low-level parallel programming details are hidden by the parallel toolbox implementation. An unexpected discovery from this research is an optimistic method for imple- menting discrete relaxation in parallel, in problem domains where monotonicity is a necessary correctness condition. This scheme is developed in the context of paral- lelizing the constraint application, but is applicable to discrete relaxation in general. iii Contents List of Figures vii List of Tables ix 1 Introduction 1 I Abstractions 11 2 Parallelism Abstractions 13 2.1 Fixed-Point Computations : : : : : : : : : : : : : : : : : : : : : : : : 14 2.1.1 Formulation of Fixed-Point Computation : : : : : : : : : : : : 18 2.1.2 General Use of Fixed-Point : : : : : : : : : : : : : : : : : : : 19 2.1.3 Basic Use of Fixed-Point Library : : : : : : : : : : : : : : : : 19 2.1.4 Application-Speci(cid:12)c Scheduling : : : : : : : : : : : : : : : : : 21 2.1.5 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 2.2 Traversals of Directed Acyclic Graphs : : : : : : : : : : : : : : : : : : 25 2.2.1 Dag-Traversal : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 2.2.2 Dag-Traversal for Fixed-Point Computation : : : : : : : : : : 26 2.2.3 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29 2.3 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 31 3 Data-Sharing Abstractions 32 3.1 Side E(cid:11)ects on Shared Data : : : : : : : : : : : : : : : : : : : : : : : 32 3.2 Writing Parallel Code: Shared Data Accesses : : : : : : : : : : : : : : 35 3.3 Simple Concurrent Datatype : : : : : : : : : : : : : : : : : : : : : : : 36 3.3.1 Example Simple Concurrent Datatype: Counter : : : : : : : : 37 3.3.2 Conditional Update for Concurrent Datatypes : : : : : : : : : 37 3.4 Dictionary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38 3.4.1 Dictionary Interface: : : : : : : : : : : : : : : : : : : : : : : : 39 3.4.2 Sample Use of Dictionary : : : : : : : : : : : : : : : : : : : : 40 3.4.3 Split-fn implementation in Common Lisp : : : : : : : : : : : : 41 iv 3.5 Autolock : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 45 3.5.1 Autolock Interface : : : : : : : : : : : : : : : : : : : : : : : : 46 3.5.2 Sample Use of Autolocks : : : : : : : : : : : : : : : : : : : : : 48 3.6 Optimistic Read-Modify-Write : : : : : : : : : : : : : : : : : : : : : : 48 3.6.1 Optimistic Read-Modify-Write Interface : : : : : : : : : : : : 50 3.6.2 Sample Uses of ORMW : : : : : : : : : : : : : : : : : : : : : : : 52 3.7 Per-Thread Location : : : : : : : : : : : : : : : : : : : : : : : : : : : 53 3.7.1 False Sharing : : : : : : : : : : : : : : : : : : : : : : : : : : : 53 3.7.2 False Sharing in Shared Structures : : : : : : : : : : : : : : : 54 3.7.3 Pdefstruct Interface : : : : : : : : : : : : : : : : : : : : : : : : 55 3.7.4 Sample Use of Pdefstruct: A Unique-Id Generator : : : : : : : 57 3.8 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 58 II Sample Applications 61 4 Application: CONSAT 64 4.1 CONSAT Overview : : : : : : : : : : : : : : : : : : : : : : : : : : : : 64 4.2 CONSAT as a Parallel Application : : : : : : : : : : : : : : : : : : : 72 4.3 Parallelizing CONSAT : : : : : : : : : : : : : : : : : : : : : : : : : : 73 4.3.1 Sequential CONSAT : : : : : : : : : : : : : : : : : : : : : : : 73 4.3.2 Introducing Parallelism : : : : : : : : : : : : : : : : : : : : : : 73 4.3.3 Application-Speci(cid:12)c Scheduling : : : : : : : : : : : : : : : : : 75 4.3.4 Shared Data Accesses : : : : : : : : : : : : : : : : : : : : : : : 75 4.4 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 77 5 Optimistic Parallel Discrete Relaxation 81 5.1 Discrete Relaxation : : : : : : : : : : : : : : : : : : : : : : : : : : : : 82 5.2 Discrete Relaxation and Fixed-Point Computations : : : : : : : : : : 87 5.3 CONSAT as Discrete Relaxation : : : : : : : : : : : : : : : : : : : : 87 5.4 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 88 6 Application: RC 89 6.1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 89 6.2 RC Overview : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 89 6.3 RC as a Fixed-Point Computation : : : : : : : : : : : : : : : : : : : : 93 6.3.1 Notation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 93 6.3.2 Fixed-Point Computation : : : : : : : : : : : : : : : : : : : : 93 6.3.3 Introducing Parallelism : : : : : : : : : : : : : : : : : : : : : : 94 6.3.4 RC as a Dag Traversal : : : : : : : : : : : : : : : : : : : : : : 95 6.4 Shared Data Accesses : : : : : : : : : : : : : : : : : : : : : : : : : : : 96 6.4.1 P-sets : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 97 v 6.4.2 Interning Productions and Nonterminals : : : : : : : : : : : : 99 6.4.3 False Sharing in RC : : : : : : : : : : : : : : : : : : : : : : : 99 6.5 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 100 III Immplementation and Evaluation 103 7 Toolbox Implementation 105 7.1 Multiprocessing SPUR Lisp : : : : : : : : : : : : : : : : : : : : : : : 105 7.2 CLiP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 106 7.3 Parallel Lisp Features Used : : : : : : : : : : : : : : : : : : : : : : : 106 7.4 Changes made to CLiP : : : : : : : : : : : : : : : : : : : : : : : : : : 107 7.5 CLiP Allocation Bottlenecks : : : : : : : : : : : : : : : : : : : : : : : 108 7.6 User-Level Object Allocation : : : : : : : : : : : : : : : : : : : : : : : 108 7.7 Future Improvements to CLiP : : : : : : : : : : : : : : : : : : : : : : 110 8 Performance Tuning 114 8.1 Locating Performance Bottlenecks : : : : : : : : : : : : : : : : : : : : 114 8.1.1 Why is a Parallel Program Slow? : : : : : : : : : : : : : : : : 114 8.1.2 Locating Performance Bottlenecks : : : : : : : : : : : : : : : : 115 8.2 Removing Performance Bottlenecks : : : : : : : : : : : : : : : : : : : 117 8.3 Speedup and Garbage Collection : : : : : : : : : : : : : : : : : : : : 119 8.4 Multiprocessor Used : : : : : : : : : : : : : : : : : : : : : : : : : : : 119 8.4.1 Measurement Conditions : : : : : : : : : : : : : : : : : : : : : 119 9 Evaluation 121 9.1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 121 9.2 The Toolbox Experience : : : : : : : : : : : : : : : : : : : : : : : : : 123 9.2.1 CONSAT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 123 9.2.2 RC : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 125 9.3 CONSAT Performance : : : : : : : : : : : : : : : : : : : : : : : : : : 127 9.3.1 Sample Constraint Network : : : : : : : : : : : : : : : : : : : 127 9.3.2 Uniprocessor Performance : : : : : : : : : : : : : : : : : : : : 127 9.3.3 Multiprocessor Performance : : : : : : : : : : : : : : : : : : : 127 9.4 RC Performance: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 130 9.4.1 Sample Input Program : : : : : : : : : : : : : : : : : : : : : : 130 9.4.2 Uniprocessor Performance : : : : : : : : : : : : : : : : : : : : 130 9.4.3 Multiprocessor Performance : : : : : : : : : : : : : : : : : : : 130 10 Related Work 132 10.1 Explicitly Parallel Programming Systems : : : : : : : : : : : : : : : : 133 10.2 Parallelism Abstractions : : : : : : : : : : : : : : : : : : : : : : : : : 136 10.2.1 Fixed-Point : : : : : : : : : : : : : : : : : : : : : : : : : : : : 136 vi 10.2.2 Dag-Traversal : : : : : : : : : : : : : : : : : : : : : : : : : : : 138 10.3 Data-Sharing Abstractions : : : : : : : : : : : : : : : : : : : : : : : : 138 10.3.1 Other Approaches to Concurrent Accesses : : : : : : : : : : : 138 10.3.2 Per-Component Comparisons : : : : : : : : : : : : : : : : : : 142 10.3.3 Architectural Support for Data-Sharing Abstractions : : : : : 147 10.4 Asynchronous Iterations : : : : : : : : : : : : : : : : : : : : : : : : : 148 10.5 Parallel Constraint Satisfaction : : : : : : : : : : : : : : : : : : : : : 149 10.6 Dag-Traversal : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 150 10.6.1 Circular Grammar Evaluator : : : : : : : : : : : : : : : : : : 150 10.6.2 Hybrid Data(cid:13)ow Analysis Algorithms : : : : : : : : : : : : : : 150 11 Conclusion 151 11.1 Contributions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 151 11.2 Future Directions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 155 Bibliography 156