Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Using Abstraction in Explicitly Parallel Programs Katherine A. Yelick MIT Laboratory for Computer Science It is well-known that writing parallel programs that are both fast and correct is significantly harder than writing sequential ones. In this thesis we introduce a transition-based approach to the design and implementation of parallel programs. This approach is aimed at applications whose complex data and control structures make them hard to parallelize by conventional means. It is based on a programming model with explicit parallelism, and it incorporates data and process parallelism within a uniform framework. The transition-based approach addresses the problem of program synthesis by breaking the development process into four distinct phases, each with explicit correctness and performance requirements. Module interfaces are well-defined so that rigorous correctness arguments can be made when desired. Application-specific scheduling is used to enhance performance, and significant performance tuning of the scheduler can be done in the last phase of development. Programs designed with this approach rely on data abstractions whose operations behave serially, but have highly concurrent implementations. Specifications and implementations of several such abstractions are presented. Some of the implementations are notable in that they allow access to shared variables without explicit synchronization, thereby exploiting the full power of sequentially consistent shared memory. To define correct behavior, we consider correctness notions in the literature and present two new notions that address performance concerns. First, we liberalize the notion of safety property of linearizability by incorporating interference specifications, which make assertions about operations should not be run concurrently. Second, we define a relatively weak liveness property, non-stopping, that makes efficient implementations possible. We apply our programming method to two example programs, matching of terms and completion of rewriting systems. Both programs are designed and performance tuned using the transition-based approach. Their implementations make use of highly concurrent types that meet our correctness conditions, and they perform well on a small shared-memory multiprocessor. The completion program is interesting in its own right, as it is the first parallel solution to an important and much studied problem. Keywords: Parallel Programming, Multiprocessor, Programming Methodology, Specification, Refinement, Concurrent Object, Linearizability, Sequential Consistency, Scheduling, Completion of Term Rewriting Systems, Term Matching, Interference Specifications, Transition-Based Development