title: Higher-Order Behavioural Conformances via Fibrations

abstract: Coinduction is a widely used technique for establishing behavioural equivalence of programs in higher-order languages. In recent years, the rise of languages with quantitative (e.g. probabilistic) features has led to extensions of coinductive methods to more refined types of behavioural conformances, most notably notions of behavioural distance. To guarantee soundness of coinductive reasoning, one needs to show that the behavioural conformance at hand forms a program congruence, i.e. it is suitably compatible with the operations of the language. This is usually achieved by a complex proof technique known as Howe’s method, which needs to be carefully adapted to both the specific language and the targeted notion of behavioural conformance. We develop a uniform categorical approach to Howe’s method that features two orthogonal dimensions of abstraction: (1) the underlying higher-order language is modelled by an abstract higher-order specification (AHOS), a novel and very general categorical account of operational semantics, and (2) notions of behavioural conformance (such as relations or metrics) are modelled via fibrations over the base category of an AHOS. Our main result is a fundamental congruence theorem at this level of generality: Under natural conditions on the categorical ingredients and the operational rules of a language modelled by an AHOS, the greatest behavioural (bi)conformance on its operational model forms a congruence. We illustrate our theory by deriving congruence of bisimilarity and behavioural pseudometrics for probabilistic higher-order languages.


venue: popl

title: Compiling to Linear Neurons

authors:
Joey Velez-Ginorio
Nada Amin
Konrad P. Kording
Steve Zdancewic

abstract: We don’t program neural networks directly. Instead, we rely on an indirect style where learning algorithms, like gradient descent, determine a neural network’s function by learning from data. This indirect style is often a virtue; it empowers us to solve problems that were previously impossible. But it lacks discrete structure. We can’t compile most algorithms into a neural network—even if these algorithms could help the network learn. This limitation occurs because discrete algorithms are not obviously differentiable, making them incompatible with the gradient-based learning algorithms that determine a neural network’s function. To address this, we introduce Cajal: a typed, higher-order and linear programming language intended to be a minimal vehicle for exploring a direct style of programming neural networks. We prove Cajal programs compile to linear neurons, allowing discrete algorithms to be expressed in a differentiable form compatible with gradient-based learning. With our implementation of Cajal, we conduct several experiments where we link these linear neurons against other neural networks to determine part of their function prior to learning. Linking with these neurons allows networks to learn faster, with greater data-efficiency, and in a way that’s easier to debug. A key lesson is that linear programming languages provide a path towards directly programming neural networks, enabling a rich interplay between learning and the discrete structures of ordinary programming.


title: A Relational Separation Logic for Effect Handlers

authors:
Paulo Emílio de Vilhena
Simcha van Collem
Ines Wright
Robbert Krebbers

abstract: Effect handlers offer a powerful and relatively simple mechanism for controlling a program's flow of execution. Since their introduction, an impressive array of verification tools for effect handlers has been developed. However, to this day, no framework can express and prove relational properties about programs that use effect handlers in languages such as OCaml and Links, where programming features like mutable state and concurrency are readily available. To this end, we introduce blaze, the first relational separation logic for effect handlers. We build blaze on top of the Rocq implementation of the Iris separation logic, thereby enjoying the rigour of a mechanised theory and all the reasoning properties of a modern fully-fledged concurrent separation logic, such as modular reasoning about stateful concurrent programs and the ability to introduce user-defined ghost state. In addition to familiar reasoning rules, such as the bind rule and the frame rule, blaze offers rules to reason modularly about programs that perform and handle effects. Significantly, when verifying that two programs are related, blaze does not require that effects and handlers from one program be in correspondence with effects and handlers from the other. To assess this flexibility, we conduct a number of case studies: most noticeably, we show how different implementations of an asynchronous-programming library using effects are related to truly concurrent implementations. As side contributions, we introduce two new, simple, and general reasoning rules for concurrent relational separation logic that are independent of effects: a logical-fork rule that allows one to reason about an arbitrary program phrase as if it had been spawned as a thread and a thread-swap rule that allows one to reason about how threads are scheduled.


title: Stateful Differential Operators for Incremental Computing

authors:
Runqing Xu
Sebastian Erdweg

abstract: Differential operators map input changes to output changes and form the building blocks of efficient incremental computations. For example, differential operators for relational algebra are used to perform live view maintenance in database systems. However, few differential operators are known and it is unclear how to develop and verify new efficient operators. In particular, we found that differential operators often need to use internal state to selectively cache relevant information, which is not supported by prior work. To this end, we designed a specification for stateful differential operators that allows custom state, yet places sufficient constraints to ensure correctness. We model our specification in Rocq and show that the specification not only guides the design of novel differential operators, but also can capture some of the most sophisticated existing differential operators: database join and Datalog aggregation. We show how to describe complex incremental computations in OCaml by composing stateful differential operators, which we have extracted from Rocq.


title: Network Change Validation with Relational NetKAT

authors:
Han Xu
Zachary Kincaid
Ratul Mahajan
David Walker

abstract: Relational NetKAT (RN) is a new specification language for network change validation. Engineers use RN to specify intended changes by providing a trace relation R, which maps existing packet traces in the pre-change network to intended packet traces in the post-change network. The intended set of traces may then be checked against the actual post-change traces to uncover errors in implementation. Trace relations are constructed compositionally from a language of combinators that include trace insertion, trace deletion, and packet transformation, as well as regular operators for concatenation, union, and iteration of relations. We provide algorithms for converting trace relations into a new form of NetKAT transducer and also for constructing an automaton that recognizes the image of a NetKAT automaton under a NetKAT transducer. These algorithms, together with existing decision procedures for NetKAT automaton equivalence, suffice for validating network changes. We provide a denotational semantics for our specification language, prove our compilation algorithms correct, implement a tool for network change validation, and evaluate it on a set of benchmarks drawn from a production network and Amazon’s Batfish toolkit.


title: Local Contextual Type Inference

authors:
Xu Xue
Chen Cui
Shengyi Jiang
Bruno C. d. S. Oliveira

abstract:
Type inference is essential for programming languages, yet complete and global inference quickly becomes undecidable in the presence of rich type systems like System F. Pierce and Turner proposed local type inference (LTI) as a scalable, partially annotated alternative by relying on information local to applications. While LTI has been widely adopted in practice, there are significant gaps between theory and practice, with its theory being underdeveloped and specifications for LTI being complex and restrictive.

We propose Local Contextual Type Inference, a principled redesign of LTI grounded in contextual typing—a recent formalism which captures type information flow. We present Contextual System F (Fc), a variant of System F with implicit and first-class polymorphism. We formalize Fc using a declarative type system, prove soundness, completeness, and decidability, and introduce matching subtyping as a bridge between declarative and algorithmic inference. This work offers the first mechanized treatment of LTI, while at the same time removing important practical restrictions and also demonstrating the power of contextual typing in designing robust, extensible and simple to implement type inference algorithms.


title: Piecewise Analysis of Probabilistic Programs via 𝑘-Induction

authors:
Tengshun Yang
Shenghua Feng
Hongfei Fu
Naijun Zhan
Jingyu Ke
Shiyang Wu

abstract: In probabilistic program analysis, quantitative analysis aims at deriving tight numerical bounds for probabilistic properties such as expectation and assertion probability. Most previous works consider numerical bounds over the whole program state space monolithically and do not consider piecewise bounds. Not surprisingly, monolithic bounds are either conservative, or not expressive and succinct enough in general. To derive better bounds, we propose a novel approach for synthesizing piecewise bounds over probabilistic programs. First, we show how to extract useful piecewise information from latticed k-induction operators, and combine the piecewise information with Optional Stopping Theorem to obtain a general approach to derive piecewise bounds over probabilistic programs. Second, we develop algorithms to synthesize piecewise polynomial bounds, and show that the synthesis can be reduced to bilinear programming in the linear case, and soundly relaxed to semidefinite programming in the polynomial case. Experimental results show that our approach generates tight piecewise bounds for a wide range of benchmarks when compared with the state of the art.


title: Handling Higher-Order Effectful Operations with Judgemental Monadic Laws

authors:
Zhixuan Yang
Nicolas Wu

abstract: This paper studies the design of programming languages with handlers of higher-order effectful operations – effectful operations that may take in computations as arguments or return computations as output. We present and analyse a core calculus with higher-kinded impredicative polymorphism, handlers of higher-order effectful operations, and optionally general recursion. The distinctive design choice of this calculus is that handlers are carried by lawless raw monads, while the computation judgements still satisfy the monadic laws judgementally. We present the calculus with a logical framework and give denotational models of the calculus using realizability semantics. We prove closed-term canonicity and parametricity for the recursion-free fragment of the language using synthetic Tait computability and a novel form of the ⊤⊤-lifting technique.


title: Accelerating Syntax-Guided Program Synthesis by Optimizing Domain-Specific Languages

authors:
Zhentao Ye
Ruyi Ji
Yingfei Xiong
Xin Zhang

abstract: Syntax-guided program synthesis relies on domain-specific languages (DSLs) to constrain the search space and improve efficiency. However, manually designing optimal DSLs is challenging and often results in suboptimal performance. In this paper, we propose AMaze, a novel framework that automatically optimizes DSLs to accelerate synthesis. AMaze iteratively refines a DSL by identifying key program fragments, termed feature components, whose enumeration ranks correlate with synthesis time. Using a dynamic-programming-based algorithm to calculate enumeration ranks of feature components and a machine learning model based on them, AMaze estimates synthesis cost instead of directly invoking the synthesizer, which is impractical due to high computational cost. We evaluate AMaze on state-of-the-art synthesizers, including DryadSynth, Duet, Polygen, and EUsolver, across multiple domains. Empirical results demonstrate that AMaze achieves up to 4.35X speedup, effectively reducing synthesis time while maintaining expressiveness.


title: Fuzzing Guided by Bayesian Program Analysis

authors:
Yifan Zhang
Xin Zhang

abstract: We propose a novel approach that leverages Bayesian program analysis to guide large-scale target-guided greybox fuzzing (LTGF). LTGF prioritizes program locations (targets) that are likely to contain bugs and applies directed mutation towards high-priority targets. However, existing LTGF approaches suffer from coarse and heuristic target prioritization strategies, and lack a systematic design to fully exploit feedback from the fuzzing process. We systematically define this prioritization process as the reachable fuzzing targets problem. Bayesian program analysis attaches probabilities to analysis rules and transforms the analysis results into a Bayesian model. By redefining the semantics of Bayesian program analysis, we enable the prediction of whether each target is reachable by the fuzzer, and dynamically adjust the predictions based on fuzzer feedback. On the one hand, Bayesian program analysis builds Bayesian models based on program semantics, enabling systematic and fine-grained prioritization. On the other hand, Bayesian program analysis systematically learns feedback from the fuzzing process, making its guidance adaptive. Moreover, this combination extends the application of Bayesian program analysis from alarm ranking to fully automated bug discovery. We implement our approach and evaluate it against several state-of-the-art fuzzers. On a suite of real-world programs, our approach discovers 3.25 × to 13 × more unique bugs compared to baselines. In addition, our approach identifies 39 previously unknown bugs in well-tested programs, 30 of which have been assigned CVEs.


title: Probabilistic Concurrent Reasoning in Outcome Logic: Independence, Conditioning, and Invariants

authors:
Noam Zilberstein
Alexandra Silva
Joseph Tassarotti

abstract: Although randomization has long been used in distributed computing, formal methods for reasoning about probabilistic concurrent programs have lagged behind. No existing program logics can express specifications about the full distributions of outcomes resulting from programs that are both probabilistic and concurrent. To address this, we introduce Probabilistic Concurrent Outcome Logic (pcOL), which incorporates ideas from concurrent and probabilistic separation logics into Outcome Logic to introduce new compositional reasoning principles. At its core, pcOL reinterprets the rules of Concurrent Separation Logic in a setting where separation models probabilistic independence, so as to compositionally describe joint distributions over variables in concurrent threads. Reasoning about outcomes also proves crucial, as case analysis is often necessary to derive precise information about threads that rely on randomized shared state. We demonstrate pcOL on a variety of examples, including to prove almost sure termination of unbounded loops.


title: Let Generalization, Polymorphic Recursion, and Variable Minimization in Boolean-Kinded Type Systems

abstract: Recent research has demonstrated the effectiveness of extending the Hindley-Milner (HM) type system with Boolean kinds to support type inference for a wide variety of features. However, the means to support classic type system provisions such as local let generalization and polymorphic recursion is either limited or unknown for such extensions. This paper contributes procedures for equational generalization and semiunification in arbitrary Boolean rings, enabling let generalization and polymorphic recursion in Boolean-kinded type inference. Additionally, methods to minimize the number of bound Boolean type variables are developed to keep types small in these systems. Boolean-kinded HM extensions are exemplified with nullable reference types, and how to use the developed procedures to support let generalization and polymorphic recursion is outlined.


venue: ppopp

title: Design and Distributed Implementation of the Parallel Logic Language Shared Prolog

authors:
Vincenzo Ambriola
Paolo Ciancarini
Marco Danelutto

abstract: The parallel logic language Shared Prolog embeds Prolog as its sequential component. A program is Shared Prolog is composed of a set of logic agents, i.e. Prolog programs, that communicate associatively via a shared workspace called blackboard.


title: Munin: Distributed Shared Memory Based on Type-Specific Memory Coherence

authors:
John K. Bennett
John B. Carter
Willy Zwaenepoel

abstract: We are developing Munin, a system that allows programs written for shared memory multiprocessors to be executed efficiently on distributed memory machines. Munin attempts to overcome the architectural limitations of shared memory machines, while maintaining their advantages in terms of ease of programming. Our system is unique in its use of loosely coherent memory, based on the partial order specified by a shared memory parallel program, and in its use of type-specific memory coherence. Instead of a single memory coherence mechanism for all shared data objects, Munin employs several different mechanisms, each appropriate for a different class of shared data object. These type-specific mechanisms are part of a runtime system that accepts hints from the user or the compiler to determine the coherence mechanism to be used for each object. This paper focuses on the design and use of Munin's memory coherence mechanisms, and compares our approach to previous work in this area.


title: Analysis of Event Synchronization in A Parallel Programming Tool

authors:
David Callahan
Ken Kennedy
Jaspal Subhlok

abstract: Understanding synchronization is important for a parallel programming tool that uses dependence analysis as the basis for advising programmers on the correctness of parallel constructs. This paper discusses static analysis methods that can be applied to parallel programs with event variable synchronization. The objective is to be able to predict potential data races in a parallel program. The focus is on how dependencies and synchronization statements inside loops can be used to analyze complete programs with parallel loop and parallel case style parallelism.


title: An Implementation of a Barotropic Numerical Weather Prediction Model in the Functional Language SISAL

authors:
Pau S. Chang
Gregory K. Egan

abstract: Numerical Weather Prediction (NWP) is acknowledged as being of vital importance to economy. The demand that NWP places on computing system performance has increased dramatically since the introduction of computer systems and is still growing. This paper describes the implementation of a one-level barotropic spectral NWP model using the high level functional language SISAL. Our initial approach was a direct transliteration from FORTRAN to SISAL, the result of which was a large amount of array copying and loss of parallelism. The algorithm of the model was then rearranged to enable effective exploitation of parallelism by an optimizing SISAL compiler. The parallel implementation technique and its potential for modeling with larger model sizes are discussed, and the improved results for an Encore Multimax multiprocessor are presented.


title: Concurrent Aggregates (CA)

authors:
Andrew A. Chien
William J. Dally

abstract: To program massively concurrent MIMD machines, programmers need tools for managing complexity.One important tool that has been used in the sequential programming world is hierarchies of abstractions.Unfortunately, most concurrent object-oriented languages construct hierarchical abstractions from objects that serialize -serializing the abstractions.In machines with tens of thousands of processors, unnecessary serialization of this sort can cause significant loss of concurrency.Concurrent Aggregates (CA) is an object-oriented language that allows programmers to build unserialized hierarchies of abstractions by using aggregates.An aggregate in CA is a homogeneous collection of objects (called representatives) that are grouped together and may be referenced by a single aggregate name.Aggregates are integrated into the object model, allowing them to be used wherever an object could be used.Concurrent Aggregates also incorporates several innovative language features that facilitate programming with aggregates.Intra-aggregate addressing aids cooperation between parts of an aggregate.Delegation allows programmers to compose an concurrent aggregate behavior from a number of objects or aggregates.Messages in CA are first class objects that can be used to create message handling abstractions (they handle messages as data).Such abstractions facilitate concurrent operations on aggregates.Continuations are also first class objects.In addition, programmers can construct continuations and use them just like system continuations.User constructed continuations can implement synchronization structures such as a barrier synchronization.


title: An Empirical Comparison of Monitoring Algorithms for Access Anomaly Detection

authors:
Anne Dinning
Edith Schonberg

abstract: One of the major disadvantages of parallel programming with shared memory is the nondeterministic behavior caused by uncoordinated access to shared variables, known as access anomalies. Monitoring program execution to detect access anomalies is a promising and relatively unexplored approach to this problem. We present a new algorithm, referred to as task recycling, for detecting anomalies, and compare it to an existing algorithm. Empirical results indicate several significant conclusions: (i) While space requirements are bounded by O(T × V), where T is the maximum number of threads that may potentially execute in parallel and V is the number of variable monitored, for typical programs space requirements are on average O(V). (ii) Task recycling is more efficient in terms of space requirements and often in performance. (iii) The general approach of monitoring to detect access anomalies is practical.


title: The Process Trellis Architectur for Real-Time Monitors

abstract: The process trellis is a parallel software architecture for building heuristic real-time monitors. These programs, for example Intelligent Cardiovascular Monitors, must process massive quantities of data in real time. It is natural to turn to parallelism to meet these computational requirements. The process trellis software architecture is intended to simplify the creation and maintenance of heuristic real-time monitors. To do this it must be 1) modular, 2) efficient and 3) predictable.


title: A Multi-Level Load Balancing Scheme for OR-Parallel Exhaustive Search Programs on the Multi-PSI

authors:
Masakazu Furuichi
Kazuo Taki
Nobuyuki Ichiyoshi

abstract: Good load balancing is the key to deriving maximal performance from multiprocessors. Several successful dynamic load balancing techniques on tightly-coupled multiprocessors have been developed. However, load balancing is more difficult on loosely-coupled multiprocessors because inter-processor communication overheads cost more. Dynamic load balancing techniques have been employed in a few programs on loosely-coupled multiprocessors, but they are tightly built into the particular programs and not much attention is paid to scalability. We have developed a dynamic load balancing scheme which is applicable to OR-parallel programs in general. Processors are grouped, and work loads of groups and processors are balanced hierarchically. Moreover, it is scalable to any number of processors because of this multi-level hierarchical structure. The scheme is tested for the all-solution exhaustive search Pentomino program on the mesh-connected loosely-coupled multiprocessor Multi-PSI, and speedups of 28.4 times with 32 processors and 50 times with 64 processors have been attained.


title: Employing Register Channels for the Exploitation of Instruction Level Parallelism

abstract: A multiprocessor system capable of exploiting fine-grained parallelism must support efficient synchronization and data passing mechanisms. This paper demonstrates the use of shared register channels as the communication mechanism among processors in a multiprocessor chip. A register channel is provided with a synchronization bit that is used to ensure that a processor succeeds in reading a channel only after the channel has been written to. In contrast to a VLIW machine a system with channels does not require strict lockstep operation of its processors. This reduces the delays caused by unpredictable events such as memory bank conflicts. Providing channels accessible at the speed of registers constraints the number of channels that can be supported in hardware. This paper presents compile-time techniques that efficiently allocate the channels and successfully exploit the fine-grained parallelism using a small number of channels. The scheduling of operations is carried out in a manner that reduces communication among the processors and hence the number of channels required. Redundant synchronizations subsumed by other synchronizations are eliminated and channels are reused whenever possible. Results of experiments demonstrating the effectiveness of the techniques in utilizing a small number of channels are presented.


title: The Effectiveness of Task-Level Parallelism for High-Level Vision

authors:
Wilson A. Harvey
Dirk Kalp
Milind Tambe
David M. McKeown
Allen Newell

abstract: Large production systems (rule-based systems) continue to suffer from extremely slow execution which limits their utility in practical applications as well as in research settings. Most investigations in speeding up these systems have focused on match (or knowledge-search) parallelism. Although good speed-ups have been achieved in this process, these investigations have revealed the limitations on the total speed-up available from this source. This limited speed-up is insufficient to alleviate the problem of slow execution in large-scale production system implementations. Such large-scale systems are expected to increase as researchers develop increasingly more competent production systems.


title: A Methodology for Implementing Highly Concurrent Data Structures

abstract: A concurrent object is a data structure shared by concurrent processes. Conventional techniques for implementing concurrent objects typically rely on critical sections: ensuring that only one process at a time can operate on the object. Nevertheless, critical sections are poorly suited for asynchronous systems: if one process is halted or delayed in a critical section, other, non-faulty processes will be unable to progress. By contrast, a concurrent object implementation is non-blocking if it always guarantees that some process will complete an operation in a finite number of steps, and it is wait-free if it guarantees that each process will complete an operation in a finite number of steps. This paper proposes a new methodology for constructing non-blocking and wait-free implementations of concurrent objects. The object's representation and operations are written as stylized sequential programs, with no explicit synchronization. Each sequential operation is automatically transformed into a non-blocking or wait-free operation using novel synchronization and memory management algorithms. These algorithms are presented for a multiple instruction/multiple data (MIMD) architecture in which n processes communicate by applying read, write, and compare&swap operations to a shared memory.


title: Continuations and Concurrency

authors:
Robert Hieb
R. Kent Dybvig

abstract: Continuations have proven to be useful for implementing a variety of control structures, including exception handling facilities and breadth-first searching algorithms. However, traditional continuations are not useful in the presence of concurrency, because the notion of the rest of the computation represented by a continuation does not in general make sense. This paper presents a new type of continuation, called a process continuation, that may be used to control tree-structured concurrency. Just as a traditional continuation represents the rest of a computation from a given point in the computation, a process continuation represents the rest of a subcomputation, or process, from a given point in the subcomputation. Process continuations allow nonlocal exits to arbitrary points in the process tree and allow the capture of a subtree of a computation as a composable continuation for later use. Even in the absence of multiple processes, the precise control achievable with process continuations makes them more useful than traditional continuations.


title: Modeling Concurrency in Parallel Debugging

authors:
Wenwey Hseush
Gail E. Kaiser

abstract: We propose a description language, Data Path Expressions (DPEs), for modeling the behavior of parallel programs. We have designed DPEs as a high-level debugging language, where the debugging paradigm is for the programmer to describe the expected program behavior and for the debugger to compare the actual program behavior during execution to detect program errors. We classify DPEs into five subclasses according to syntactic criteria, and characterize their semantics in terms of a hierarchy of extended Petri Net models. The characterization demonstrates the power of DPEs for modeling (true) concurrency. We also present predecessor automata as a mechanism for implementing the third subclass of DPEs, which expresses bounded parallelism. Predecessor automata extend finite state automata to recognize or generate partial ordering graphs as well as strings, and provide efficient event recognizers for parallel debugging. We briefly describe the application of DPEs race conditions, deadlock and starvation.


title: The Evolution of HPC/VORX

authors:
Howard P. Katseff
Robert D. Gaglianello
Bethany S. Robinson

abstract: HPC/VORX is a computing system that provides closely coupled computing between large numbers of processors. It also supports the connection of many host workstations which may be geographically distributed within the area of a large building and allows a single applications to span many processors and many workstations. We relate some of the lessons that were learned while building and using HPC/VORX and in the transition to HPC/VORX from a smaller, less capable system. The problems that we encountered included difficulties in scaling resource managers and human interfaces to large numbers of processors, the design of communications primitives and protocols, and the implementation of programming abstractions.


title: Supporting Shared Data Structures on Distributed Memory Architectures

authors:
Charles Koelbel
Piyush Mehrotra
John Van Rosendale

abstract: Programming nonshared memory systems is more difficult than programming shared memory systems, since there is no support for shared data structures. Current programming languages for distributed memory architectures force the user to decompose all data structures into separate pieces, with each piece “owned” by one of the processors in the machine, and with all communication explicitly specified by low-level message-passing primitives. This paper presents a new programming environment for distributed memory architectures, providing a global name space and allowing direct access to remote parts of data values. We describe the analysis and program transformations required to implement this environment, and present the efficiency of the resulting code on the NCUBE/7 and IPSC/2 hypercubes.


title: Real-Time, Concurrent Checkpoint for Parallel Programs

authors:
Kai Li
Jeffrey F. Naughton
James S. Plank

abstract: We have developed and implemented a checkpointing and restart algorithm for parallel programs running on commercial uniprocessors and shared-memory multiprocessors. The algorithm runs concurrently with the target program, interrupts the target program for small, fixed amounts of time and is transparent to the checkpointed program and its compiler. The algorithm achieves its efficiency through a novel use of address translation hardware that allows the most time-consuming operations of the checkpoint to be overlapped with the running of the program being checkpointed.


title: Analysis of Synchronization in Massively Parallel Discrete-Event Sumulations

abstract: article Free Access Share on Analysis of synchronization in massively parallel discrete-event simulations Author: D. M. Nicol Department of Computer Science, College of William and Mary, Williamsburg, VA Department of Computer Science, College of William and Mary, Williamsburg, VAView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 25Issue 3Mar. 1990 pp 89–98https://doi.org/10.1145/99164.99174Online:01 February 1990Publication History 7citation318DownloadsMetricsTotal Citations7Total Downloads318Last 12 Months6Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF


title: A Chare Kernel Implementation of a Parallel Prolog Compiler

authors:
Balkrishna Ramkumar
Laxmikant V. Kalé

abstract: We have designed and implemented a compiler for the parallel execution of Prolog programs as a machine independent application on top of a run time environment for parallel programming called the Chare Kernel. The compiler is based on the Reduce-OR process model for the AND and OR parallel execution of Prolog programs and hence exploits both OR and independent AND parallelism found in Prolog programs. We describe the salient features of the parallel Prolog compiler from the viewpoint of its implementation as a Chare Kernel application. The responsibilities of process creation, load balancing, queueing strategies for work pool management, memory management and interprocess communication are all assumed by the Chare Kernel thereby eliminating these concerns at the application level. We discuss the effectiveness of this separation for a large application like the parallel Prolog compiler. The machine independence property makes the compiler easy to port on all machines, both shared and nonshared, that support the Chare Kernel. The compiler has been implemented on a variety of machines, including the Encore Multimax, the Sequent Symmetry, the Intel iPSC/2 hypercube and the Alliant FX/8. We briefly discuss its performance on a range of benchmarks exhibiting AND, OR and AND/OR parallelism on two of these machines. The speedups obtained are linear, demonstrating the effectiveness of the Chare Kernel as a simple, elegant, yet powerful environment for parallel programming.


title: Multi-Model Parallel Programming in Psyche

authors:
Michael L. Scott
Thomas J. LeBlanc
Brian D. Marsh

abstract: Many different parallel programming models, including lightweight processes that communicate with shared memory and heavyweight processes that communicate with messages, have been used to implement parallel applications. Unfortunately, operating systems and languages designed for parallel programming typically support only one model. Multi-model parallel programming is the simultaneous use of several different models, both across programs and within a single program. This paper describes multi-model parallel programming in the Psyche multiprocessor operating system. We explain why multi-model programming is desirable and present an operating system interface designed to support it. Through a series of three examples, we illustrate how the Psyche operating system supports different models of parallelism and how the different models are able to interact.


title: Programming Techniques for Efficiently Exploiting Parallelism in Logic Programming Languages

authors:
Evan Tick
Nobuyuki Ichiyoshi

abstract: Granularity collecting (e.g., in OR-parallel Prolog) and removal of synchronization points (e.g., in AND-parallel committed-choice languages), are in general useful techniques for speeding up parallel logic programs. In this paper we explain these techniques with a unifying example: the Semigroup Problem, the calculation of the members of a semigroup given an initial set of generators. Performance measurements on a Sequent Symmetry multiprocessor are presented as evidence of the utility of the paradigms.


title: An Approach to Ordering Optimizing Transformations

authors:
Deborah Whitfield
Mary Lou Soffa

abstract: As an approach to deriving an application order of optimizing transformations, a framework is developed for examining the interactions of the transformations. The framework is based on an axiomatic specification technique and includes both pre-conditions and post conditions that must exist before and after applying optimizations. For a selected set of optimizations, the framework is used to determine those interactions among the optimizations that can create conditions and those that can destroy conditions for applying other optimizations. From these interactions, an application order is derived to obtain the potential benefits of the optimizations that can be applied to a program. In some cases, the ordering of a pair of optimizations is unambiguous in that one optimization can either create or destroy the conditions for the other. In the few cases where there is a cyclic interaction, the ordering is resolved based on the perceived importance of the two optimizations.


title: Scanning Polyhedra with DO Loops

authors:
Corinne Ancourt
François Irigoin

abstract: Supercompilers perform complex program transformations which often result in new loop bounds. This paper shows that, under the usual assumptions in automatic parallelization, most transformations on loop nests can be expressed as affine transformations on integer sets de ned by polyhedra and that the new loop bounds can be computed with algorithms using Fourier's pairwise elimination method although it is not exact for integer sets. Sufficient conditions to use pairwise elimination on integer sets and to extend it to pseudo-linear constraints are also given. A tradeo has to be made between dynamic overhead due to some bound slackness and compilation complexity but the resulting code is always correct. These algorithms can be used to interchange or block loops regardless of the loop bounds or the blocking strategy and to safely exchange array parts between two levels of a memory hierarchy or between neighboring processors in a distributed memory machine.


title: Optimistic Parallelization of Communicating Sequential Processes

authors:
David F. Bacon
Robert E. Strom

abstract: We present a transparent program transformation which converts a sequential execution of S1 ; S2 by a process in a multiprocess environment into an optimistic parallel execution of S1 and S2 . Such a transformation is valuable in the case where S1 and S2 cannot be parallelized by static analysis either because S2 reads a value from S1 or because S1 and S2 each interact with an external process. The optimistic transformation works under a weaker set of conditions: (1) if the value S2 reads from S1 can usually, but not always, be correctly guessed ahead of time, and (2) if S1 and S2 interact with an external process, conflicts which violate the ordering of S1 and S2 are possible but rare. Practical applications of this approach include executing the likely outcome of a test in parallel with making the test, and converting sequences of calls into streams of asynchronous sends. We analyze the problem using the framework of guarded computations, in which each computation is tagged with th...


title: Mapping Concurrent Programs to VLIW Processors

authors:
Hester Bakewell
Donna J. Quammen
Pearl Y. Wang


title: A Static Performance Estimator to Guide Data Partitioning Decisions

authors:
Vasanth Balasundaram
Geoffrey C. Fox
Ken Kennedy
Ulrich Kremer

abstract: The choice of the data domain partitioning scheme is an important factor in determining the available parallelism and hence the performance of an application on a distributed memory multiprocessor.In this paper, we present a performance estimator for statically evaluating the relative efficiency of different data partitioning schemes for any given program on any given distributed memory multiprocessor.Our methlod is not based on a theoretical machine model, but ixnstead uses a set of kernel routinea to "train" the estimator for each target machine.We also describe a prototype implementation of this technique and discuss an experimental evaluation of its accuracy.


title: Race Frontier: Reproducing Data Races in Parallel-Program Debugging

authors:
Jong-Deok Choi
Sang Lyul Min

abstract: Races in describes a mechanism to debug unintended data races


title: Andorra-I: A Parallel Prolog System that Transparently Exploits both And- and Or-Parallelism

authors:
Vítor Santos Costa
David H. D. Warren
Rong Yang

abstract: article Andorra I: a parallel Prolog system that transparently exploits both And-and or-parallelism Share on Authors: Vítor Santos Costa View Profile , David H. D. Warren View Profile , Rong Yang View Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 7July 1991 pp 83–93https://doi.org/10.1145/109626.109635Online:01 April 1991Publication History 48citation350DownloadsMetricsTotal Citations48Total Downloads350Last 12 Months8Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access


title: Dynamic Node Reconfiguration in a Parallel-Distributed Environment

authors:
Michael J. Feeley
Brian N. Bershad
Jeffrey S. Chase
Henry M. Levy

abstract: Idle workstationsin a network represent a significant computing potential.In particular, their processing power can be used by parallel-distributed programs that treat the network as a loosely-coupled multiprocessor.Our experiments with Amber show that node reconfiguration can be implemented easily and efficiently in a runtime library.work speed will substantially reduce the cost


title: A Production-Quality C* Compiler for Hypercube Multicomputers

authors:
Philip J. Hatcher
Anthony J. Lapadula
Robert R. Jones
Michael J. Quinn
Ray J. Anderson

abstract: article Free Access Share on A production-quality C* compiler for Hypercube multicomputers Authors: Philip J. Hatcher View Profile , Anthony J. Lapadula View Profile , Robert R. Jones View Profile , Michael J. Quinn View Profile , Ray J. Anderson View Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 7July 1991 pp 73–82https://doi.org/10.1145/109626.109634Online:01 April 1991Publication History 24citation249DownloadsMetricsTotal Citations24Total Downloads249Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF


title: The Integration of Application and System Based Metrics in a Parallel Program Performance Tool

authors:
Jeffrey K. Hollingsworth
R. Bruce Irvin
Barton P. Miller

abstract: The IPS-2 parallel program measurement tools pro-vide performance data from application programs, the operating system, hardware, network, and other sources. Previous versions of IPS-2 allowed programmers to collect information about an application based only on what could be collected by software instrumentation inserted into the program (and system call libraries). We have developed an open interface, called the “external time histogram”, pro-viding a graceful way to include external data from many sources. The user can tell IPS-2 of new sources of perfor-mance data through an extensible metric description language. The data from these external sources is automat-ically collected when the application program is run. IPS-2 provides a library to simplify constructing the external data collectors. The new version of IPS-2 can measure shared-memory and message-passing parallel programs running on a heterogeneous collection of machines. Data from C or Fortran programs, and data from simulations ean be pro-cessed by the same tool. As a result of including the new external performance data, IPS-2 now can report on a whole new set of performance problems. We describe the results of using IPS-2 on two real applications: a shared-memory database join utility, and a multi-processor interconnection network simulator. Even though these applications previously went through careful tuning, we were able to precisely identify performance problems and extract additional performance improvements of about 30%.


title: Exploitation of APL Data Parallelism on a Shared-memory MIMD Machine

authors:
Dz-Ching Ju
Wai-Mee Ching

abstract: Programs written m APL implicitly contain data parallelism because the high level APL primitives denoting array o erations may be executed in parallel.Our experiment $ APL/C compiler translates ordinary APL programs into the C language with additional parallel constmcts for synchronization support.We target the RP3, a shared-memory MIMD machine built at IBM T.J. WatsonResearch Center, running the Mach operating system.The compiler uses Mach kernel prirmtives to build a parallel run-time environment to reduce the run-time overhead.We have developed a novel method for dynamically determining the required number of processors for a primitive function.The compiler can further apply a form of the loop fusion technique to groups of scalar primitive functions to gain additional improvement.


title: Removal of Redundant Dependences in DOACROSS Lops with Constant Dependences

authors:
V. Prasad Krothapalli
P. Sadayappan

abstract: article Free Access Share on Removal of redundant dependences in DOACROSS loops with constant dependences Authors: V. P. Krothapalli View Profile , P. Sadayappan View Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 7July 1991 pp 51–60https://doi.org/10.1145/109626.109632Online:01 April 1991Publication History 12citation195DownloadsMetricsTotal Citations12Total Downloads195Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF


title: Parallelizing a New Class of Large Applications over High-speed Networks

authors:
H. T. Kung
Peter Steenkiste
Marco Dimas Gubitoso
Manpreet Khaira

abstract: Several large applicationshave been paralleli,zed on Nectar, a network-based multicomputer recently developed by Carnegie Mellon.These applications were previously either too large or too complex to be easily implemented on distributed memory parallel systems.Parallelizing these applications was made possible by the cooperative use of many existing general-purpose computers over high-speed networks, and by an implementation methodology based on a clean separation between applicatiionspecific and system-specific code.We illustrate these points using our experience with parallelizing three real-world applications.The success in these applications clearly points out a new direction in parallel processing.The Nectar system [1] developed by Carnegie Mellon is intended to provide general support for parallelizing large applications.The system is a multicomputer built around a high-speed network.The use of existing general-purpose computers as its nodes and the highbandwidth and low-latency network makes the system inherently suited for large applications.The system has allowed us to parallelize applications that were previously either tm complex or too communicationintensive to be suited for parallel processing.This paper describes the Nectar implementation of three applications: (1) COSMOS [4], a switch-level circuit simulator developed by Randy Bryant and his associates at Carnegie Mellon; (2) NOODLES [7], a solid modeling package developed by Professor


title: Exploiting Operating System Support for Dynamic Page Placement on a NUMA Shared Memory Multiprocessor

authors:
Richard P. LaRowe Jr.
James T. Wilkes
Carla Schlatter Ellis

abstract: Shared memory multiprocessors are attractive because they are programmed in a manner similar to uniprocessors. The UMA class of shared memory multiprocessors is the most attractive, from the programmer's point of view, since the programmer need not be concerned with the placement of code and data in the physical memory hierarchy. Scalable shared memory multiprocessors, on the other hand, tend to present at least some degree of non-uniformity of memory access to the programmer, making the NUMA class an important one to consider. In this paper, we investigate the role that DUnX, an operating system supporting dynamic page placement on a BBN GP1000, might play in simplifying the memory model presented to the applications programmer. We consider a case study of psolu, a real scientific application originally targeted for a NUMA architecture. We find that dynamic page placement can dramatically improve the performance of a simpler implementation of psolu targeted for an UMA memory architec...


title: Coarse-Grain Parallel Programming in Jade

authors:
Monica S. Lam
Martin C. Rinard

abstract: This paper presents Jade, a language which allows a programmer to easily express dynamic coarse-grain parallelism. Starting with a sequential program, a programmer augments those sections of code to be parallelized with abstract data usage information. The compiler and run-time system use this information to concurrently execute the program while respecting the program's data dependence constraints. Using Jade can significantly reduce the time and effort required to develop and maintain a parallel version of an imperative application with serial semantics. The paper introduces the basic principles of the language, compares Jade with other existing languages, and presents the performance of a sparse matrix Cholesky factorization algorithm implemented in Jade.


title: A Unified Framework for Systemic Loop Transformation

abstract: This paper presents a formal mathematical framework which unifies the existing loop transformations.This framework also includes more general classes of loop transformations, which can extract more parallelism from a class of programs than the existing techniques.We classify schedules into three classes: unij'orm, subdomainvariant, and statement-variant.Viewing from the degree of parallelism to be gained by loop transformation, the schedules can also be classified as single-sequential level, multiple-sequential level, and mited schedules.We also illustrate the usefulness of the more general loop transformation with an example program.


title: Event-Based Performance Perturbation: A Case Study

abstract: Determiningthe performance behavior of parallel computations requires some form of intrusive tracing measurement.The greater the need for detailed performance data, the more intrusion the measurement will cause.Recovering actual execution performance jfrom perturbed performance measurements using eventbased perturbation analysis is the topic of this paper.We show that the measurement and subsequent analysis of synchronization operations (particularly, advance and await) can produce, in practice, accurate approximations to actual performance behavior.We use as testcases three Lawrence Livermore loops that execute as parallel DOACROSS loops on an Alliant FX/80.The results of our experiments suggest that a systematic application of performance perturbation analysis techniques will allow more detailed, accurate instrumentation than traditionally believed possible.1


title: Parallelization and Performance of Conjugate Gradient Algorithms on the Cedar Hierarchical-Memory Multiprocessor

authors:
Ulrike Meier
Rudolf Eigenmann

abstract: We analyze the computational structure of the Conjugate Gradient algorithm and we describe its parallel implement ation on the Cedar hierarchicalmemory multiprocessor.The analysis will cover both explicit manual parallelization and automatic compilation.We report performance measurements taken on Cedar, which allow us a number of conclusions about the Cedar architecture, the programming methodology for hierarchical computer structures, and the contrast of manual vs automatic parallelization.


title: Scalable Reader-Writer Synchronization for Shared-Memory Multiprocessors

authors:
John M. Mellor-Crummey
Michael L. Scott

abstract: Reader-writer synchronization relaxes the constraints of mutual exclusion to permit more than one process to inspect a shared object concurrently, as long as none of them changes its value.On uniprocessors, mutual exclusion and readercessor demonstrate that our algorithms provide low latency and excellent scalability.


title: Improving the Accuracy of Data Race Detection

authors:
Robert H. B. Netzer
Barton P. Miller

abstract: For shared-memory parallel programs that use explicit synchronization, data race detection is an important part of debugging. A data race exists when concurrently executing sections of code access common shared variables. In programs intended to be data race free, they are sources of nondeterminism usually considered bugs. Previous methods for detecting data races in executions of parallel programs can determine when races occurred, but can report many data races that are artifacts of others and not direct manifestations of program bugs. Artifacts exist because some races can cause others and can also make false races appear real. Such artifacts can overwhelm the programmer with information irrelevant for debugging. This paper presents results showing how to identify nonartifact data races by validation and ordering. Data race validation attempts to determine which races involve events that either did execute concurrently or could have (called feasible data races). We show how each de...


title: Optimal Schedules for Parallel Prefix Computation with Bounded Resources

authors:
Alexandru Nicolau
Haigeng Wang

abstract: Given x 1 ; . . . ; xN , parallel prefix computes x 1 ffi x 2 ffi . . . ffi x k , for 1 k N , with associative operation ffi. We show optimal schedules for parallel prefix computation with a fixed number of resources p 2 for a prefix of size N p(p + 1)=2 . The time of the optimal schedules with p resources is d2N=(p + 1)e for N p(p + 1)=2, which we prove to be the strict lower bound(i.e., which is what can be achieved maximally). We then present a pipelined form of optimal schedules with d2N=(p + 1)e + d(p 0 1)=2e 0 1 time, which takes a constant overhead of d(p 0 1)=2e time more than the optimal schedules. Parallel prefix is an important common operation in many algorithms including the evaluation of polynomials, general Hornor expressions, carry look-ahead circuits and ranking and packing problems. A most important application of parallel prefix is loop parallelizing transformation. 1 Introduction Given x 1 ; . . . ; xN , parallel prefix computes x 1 ffi x 2 ffi . . . ffi x...


title: Parallel-Program Transformation Using A Metalanguage

authors:
J. Allan Yang
Young-il Choo

abstract: Article Free Access Share on Parallel-program transformation using a metalanguage Authors: J. Allan Yang View Profile , Young-il Choo View Profile Authors Info & Claims PPOPP '91: Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programmingApril 1991 Pages 11–20https://doi.org/10.1145/109625.109628Published:01 April 1991Publication History 10citation2,955DownloadsMetricsTotal Citations10Total Downloads2,955Last 12 Months18Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF


title: ActorSpaces: An Open Distributed Programming Paradigm

authors:
Gul Agha
Christian J. Callsen

abstract: We present a new programming paradigm called ActorSpace. ActorSpace provides a new communication model based on destination patterns. An actorSpace is a computationally passive container of actors which acts as a context for matching patterns. Patterns are matched against listed attributes of actors and actorSpaces that are visible in the actorSpace. Both visibility and attributes are dynamic. Messages may be sent to one or all members of a group defined by a pattern. The paradigm provides powerful support for component-based construction of massively parallel and distributed applications. In particular, it supports open interfaces to servers and pattern-directed access to software repositories.


title: Explicit Data Placement (XDP): A Methodology for Explicit Compile-Time Representation and Optimization

authors:
Vasanth Bala
Jeanne Ferrante
Larry Carter

abstract: The ability to represent, manipulate and optimize data movement between devices such as processors in a distributed memory machine, or between global memory and processors in a shared memory machine, is crucial in generating efficient code for such machines. In this paper we describe a methodology for representing and manipulating data movement explicitly in a compiler. Our methodology, called Explicit Data Placement (XDP), consists of extensions to the compiler's intermediate program language, as well as run-time structures that allow certain operations to be performed efficiently. We also illustrate one of the unique features of the XDP methodology: the ability to manipulate the run-time transfer of data ownership between processors.


title: Implementation of a Portable Nested Data-Parallel Language

authors:
Guy E. Blelloch
Siddhartha Chatterjee
Jonathan C. Hardwick
Jay Sipelstein
Marco Zagha

abstract: This paper gives an overview of the implementation of NESL, a portable nested data-parallel language. This language and its implementation are the first to fully support nested data structures as well as nested data-parallel function calls. These features allow the concise description of parallel algorithms on irregular data, such as sparse matrices and graphs. In addition, they maintain the advantages of data-parallel languages: a simple programming model and portability. The current NESL implementation is based on an intermediate language called VCODE and a library of vector routines called CVL. It runs on the Connection Machine CM-2, the Cray Y-MP C90, and serial machines. We compare initial benchmark results of NESL with those of machine-specific code on these machines for three algorithms: least-squares line-fitting, median finding, and a sparse-matrix vector product. These results show that NESL's performance is competitive with that of machine-specific codes for regular dense data, and is often superior for irregular data.


title: Implementing an Irregular Application on a Distributed Memory Multiprocessor

authors:
Soumen Chakrabarti
Katherine A. Yelick

abstract: Parallelism with irregular patterns of data, communication and computation is hard to manage efficiently. In this paper we present a case study of the Gro¨bner basis problem, a symbolic algebra application. We developed an efficient parallel implementation using the following techniques. First, a sequential algorithm was rewritten in a transition axiom style, in which computation proceeds by non-deterministic invocations of guarded statements at multiple processors. Next, the algebraic properties of the problem were studied to modify the algorithm to ensure correctness in spite of locally inconsistent views of the share data structures. This was used to design data structures with very little overhead for maintaining consistency. Finally, an application-specific scheduler was designed and tuned to get good performance. Our distributed memory implementation achieves impressive speedups.


title: Data Locality and Load Balancing in COOL

authors:
Rohit Chandra
Anoop Gupta
John L. Hennessy

abstract: Large-scale shared memory multiprocessors typically support a multilevel memory hierarchy consisting of per-processor caches, a local portion of shared memory, and remote shared memory. On such machines, the performance of parallel programs is often limited by the high latency of remote memory references. In this paper we explore how knowledge of the underlying memory hierarchy can be used to schedule computation and distribute data structures, and thereby improve data locality. Our study is done in the context of COOL, a concurrent object-oriented language developed at Stanford. We develop abstractions for the programmer to supply optional information about the data reference patterns of the program. This information is used by the runtime system to distribute tasks and objects so that the tasks execute close (in the memory hierarchy) to the objects they reference.


title: High Performance Fortran Without Templates: An Alternative Model for Distribution and Alignment

authors:
Barbara M. Chapman
Piyush Mehrotra
Hans P. Zima

abstract: article High performance Fortran without templates: an alternative model for distribution and alignment. Share on Authors: Barbara M. Chapman View Profile , Piyush Mehrotra View Profile , Hans P. Zima View Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 28Issue 7July 1993 pp 92–101https://doi.org/10.1145/173284.155342Online:01 July 1993Publication History 8citation192DownloadsMetricsTotal Citations8Total Downloads192Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access


title: Generating Local Address and Communication Sets for Data-Parallel Programs

authors:
Siddhartha Chatterjee
John R. Gilbert
Fred J. E. Long
Robert Schreiber
Shang-Hua Teng

abstract: Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance Fortran. We show that for an array A affinely aligned to a template that is distributed across p processors with a cyclic(k) distribution, and a computation involving the regular section A(l:h:s), the local memory access sequence for any processor is characterized by a finite state machine of at most k states. We present fast algorithms for computing the essential information about these state machines, and extend the framework to handle multidimensional arrays. We also show how to generate communication sets using the state machine approach. Performance results show that this solution requires very little runtime overhead and acceptable preprocessing time.


title: LogP: Towards a Realistic Model of Parallel Computation

authors:
David E. Culler
Richard M. Karp
David A. Patterson
Abhijit Sahay
Klaus E. Schauser
Eunice E. Santos
Ramesh Subramonian
Thorsten von Eicken

abstract: A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real world. Both kinds of models encourage exploitation of formal loopholes, rather than rewarding development of techniques that yield performance across a range of current and future parallel machines. This paper offers a new parallel machine model, called LogP, that reflects the critical technology trends underlying parallel computers. it is intended to serve as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine designers. Such a model must strike a balance between detail and simplicity in order to reveal important bottlenecks without making analysis of interesting problems intractable. The model is based on four parameters that specify abstractly the computing bandwidth, the communication bandwidth, the communication delay, and the efficiency of coupling communication and computation. Portable parallel algorithms typically adapt to the machine configuration, in terms of these parameters. The utility of the model is demonstrated through examples that are implemented on the CM-5.


title: Data Flow Equations for Explicitly Parallel Programs

authors:
Dirk Grunwald
Harini Srinivasan

abstract: We present a solution to the reaching definitions problem for programs with explicit lexically specified parallel constructs, such as cobegin/coend or parallel_sections, both with and without explicit synchronization operations, such as Post, Wait or Advance. The reaching definitions information for sequential programs is used to solve many standard optimization problems. In parallel programs, this information can also be used to explicitly direct communication and data ownership. Although work has been done on analyzing parallel programs to detect data races, little work has been done on optimizing such programs.


title: Experiences Using the ParaScope Editor: an Interactive Parallel Programming Tool

authors:
Mary W. Hall
Timothy J. Harvey
Ken Kennedy
Nathaniel McIntosh
Kathryn S. McKinley
Jeffrey D. Oldham
Michael H. Paleczny
Gerald Roth

abstract: The ParaScope Editor is an interactive parallel programming tool that assists knowledgeable users in developing scientific Fortran programs. It displays the results of sophisticated program analyses, provides a set of powerful interactive transformations, and supports program editing. This paper summarizes experiences of scientific programmers and tool designers using the ParaScope Editor. We evaluate existing features and describe enhancements in three key areas: user interface, analysis, and transformation. many existing features prove crucial to successful program parallelization. They include interprocedural array side-effect analysis and program and dependence view filtering. Desirable functionality includes improved program navigation based on performance estimation, incorporating user assertions in analysis and more guidance in selecting transformations. These results offer insights for the authors of a variety of programming tools and parallelizing compilers.


title: Computation Migration: Enhancing Locality for Distributed-Memory Parallel Systems

authors:
Wilson C. Hsieh
Paul Wang
William E. Weihl

abstract: We describe computation migration, a new technique that is based on compile-time program transformations, for accesing remote data in a distributed-memory parallel system. In contrast with RPC-style access, where the access is performed remotely, and with data migration, where the data is moved so that it is local, computation migration moves part of the current thread to the processor where the data resides. The access is performed at the remote processor, and the migrated thread portion continues to run on that same processor; this makes subsequent accesses in the thread portion local.


title: A Concurrent Copying Garbage Collector for Languages that Distinguish (Im)mutable Data

authors:
Lorenz Huelsbergen
James R. Larus

abstract: This paper describes the design and implementation of a concurrent compacting garbage collector for languages that distinguish mutable data from immutable data (e.g., ML) as well for languages that manipulate only immutable data (e.g., pure functional languages such as Haskell). The collector runs on shared-memory parallel computers and requires minimal mutator/collector synchronization. No special hardware or operating system support is required.


title: Using Scheduler Information to Achieve Optimal Barrier Synchronization Performance

authors:
Leonidas I. Kontothanassis
Robert W. Wisniewski

abstract: Parallel programs frequently use barriers to synchronize successive steps in an algorithm. In the presence of multiprogramming the choice of spinning versus blocking barriers can have a significant impact on performance. We demonstrate how competitive spinning techniques previously designed for locks can be extended to barriers, and we evaluate their performance. We design an additional competitive spinning technique that adapts more quickly in a dynamic environment. We then propose and evaluate a new method that obtains better peformance than previous techniques by using scheduler information to decide between spinning and blocking. The scheduler information technique makes optimal choices incurring little overhead.


title: Integrating Message-Passing and Shared-Memory: Early Experience

authors:
David A. Kranz
Kirk L. Johnson
Anant Agarwal
John Kubiatowicz
Beng-Hong Lim

abstract: This paper discusses some of the issues involved in implementing a shared-address space programming model on large-scale, distributed-memory multiprocessors. While such a programming model can be implemented on both shared-memory and message-passing architectures, we argue that the transparent, coherent caching of global data provided by many shared-memory architectures is of crucial importance. Because message-passing mechanisms ar much more efficient than shared-memory loads and stores for certain types of interprocessor communication and synchronization operations, hwoever, we argue for building multiprocessors that efficiently support both shared-memory and message-passing mechnisms. We describe an architecture, Alewife, that integrates support for shared-memory and message-passing through a simple interface; we expect the compiler and runtime system to cooperate in using appropriate hardware mechanisms that are most efficient for specific operations. We report on both integrated and exclusively shared-memory implementations of our runtime system and two applications. The integrated runtime system drastically cuts down the cost of communication incurred by the scheduling, load balancing, and certain synchronization operations. We also present preliminary performance results comparing the two systems.


title: Improving the Performance of Runtime Parallelization

authors:
Shun-Tak Leung
John Zahorjan

abstract: When the inter-iteration dependency pattern of the iterations of a loop cannot be determined statically, compile time parallelization of the loop is not possible. In these cases, runtime parallelization [8] is the only alternative. The idea is to transform the loop into two code fragements: the inspector and the executor. When the program is run, the inspector examines the iteration dependencies and constructs a parallel schedule. The executor subsequently uses that schedule to carry out the actual computation in parallel.


title: Non-concurrency Analysis

authors:
Stephen P. Masticola
Barbara G. Ryder

abstract: Non-concurrency analysis is a set of techniques for statically identifying pairs (or sets) of statements in a concurrent program which can never happen together. This information aids programmers in debugging and manually optimizing programs, improves the precision of data flow analysis, enables optimized translation of rendezvous, facilitates dead code elimination and other automatic optimizations, and allows anomaly detection in explicitly parallel programs. We present a framework for non-concurrency analysis, capable of incorporating previous analysis algorithms [CS88, DS92] and improving upon them. We show general theoretical results which are useful in estimating non-concurrency, and examples of non-concurrency analysis frameworks for two synchronization primitives: the Ada rendezvous and binary semaphores. Both of these frameworks have a low-order polynomial bound on worst-case solution time. We provide experimental evidence that static non-concurrency analysis of Ada programs can be accomplished in a reasonable time, and is generally quite accurate. Our framework, and the set of refinement components we develop, also exhibits dramatic accuracy improvements over [DS91], when the latter is used as a stand-alone algorithm, as demonstrated by our experiments.


title: Procs and Locks: A Portable Multiprocessing Platform for Standard ML of New Jersey

authors:
J. Gregory Morrisett
Andrew P. Tolmach

abstract: We have built a portable platform for running Standard ML of New Jersey programs on multiprocessors. It can be used to implement user-level thread packages for multiprocessors within the ML language with first-class continuations. The platform supports experimentation with different thread scheduling policies and synchronization constructs. it has been used to construct a Modula-3 style thread package and a version of Concurrent ML, and has been ported to three different multiprocessors running variants of Unix. This paper describes the platform's design, implementation, and performance.


title: Transforming High-Level Data-Parallel Programs into Vector Operations

authors:
Jan F. Prins
Daniel W. Palmer

abstract: Efficient parallel execution of a high-level data-parallel language based on nested sequences, higher order functions and generalized iterators can be realized in the vector model using a suitable representation of nested sequences and a small set of transformational rules to distribute iterators through the constructs of the language.


title: An Equational Language for Data-Parallelism

authors:
Pushpa Rao
Clifford Walinsky

abstract: Data-parallelism provides a clean conceptual framework for parallel programming. We are developing two programming languages: a high level equational language, called EL*, and a low-level implementation language. Both languages exploit data-parallelism instead of control-parallelism. EL* is a declarative data-parallel language. EL* programs are high-level equational specifications that use extensive pattern-matching and recursion. The language's syntax and semantics are intended to be clear and simple. Recursive forms are restricted to enable translation to efficient data-parallel operations. EL* programs are compiled into FP*, a variant of Backus's FP, where parallel operations are more explicit and low-level. The target language has a rich set of functions for performing communication, and computation. It also has a powerful set of combining forms that generate large highly-parallel functions from smaller program units. Prototype compilers have been implemented for both languages, and they demonstrate good performance. Several linear algebra and non-numeric problems have been programmed with relative ease using EL*. We are currently developing compilation techniques for a wider range of scientific problems that have more complex parallel solutions, and are continuing to expand the language's scope.


title: The Shared Regions Approach to Software Cache Coherence on Multiprocessors

authors:
Harjinder S. Sandhu
Benjamin Gamsa
Songnian Zhou

abstract: The effective management of caches is critical to the performance of applications on shared-memory multiprocessors. In this paper, we discuss a technique for software cache coherence tht is based upon the integration of a program-level abstraction for shared data with software cache management . The program-level abstraction, called Shared Regions, explicitly relates synchronization objects with the data they protect. Cache coherence algorithms are presented which use the information provided by shared region primitives, and ensure that shared regions are always cacheable by the processors accessing them. Measurements and experiments of the Shared Region approach on a shared-memory multiprocessors accessing them. Measurements and experiments of the Shared Region approach on a shared-memory multiprocessor are shown. Comparisons with other software based coherence strategies, including a user-controlled strategy and an operating system-based strategy, show that this approach is able to deliver better performance, with relatively low corresponding overhead and only a small increase in the programming effort. Compared to a compiler-based coherence strategy, the Shared Regions approach still performs better than a compiler that can achieve 90% accuracy in allowing cacheing, as long as the regions are a few hundred bytes or larger, or they are re-used a few times in the cache.


title: Perturbation Analysis of High Level Instrumentation for SPMD Programs

authors:
Sekhar R. Sarukkai
Allen D. Malony

abstract: The process of instrumenting a program to study its behavior can lead to perturbations in the program's execution. These perturbations can become severe for large parallel systems or problem sizes, even when one captures only high level events. In this paper, we address the important issue of eliminating execution perturbations caused by high-level instrumentation of SPMD programs. We will describe perturbation analysis techniques for common computation and communication measurements, and show examples which demonstrate the effectiveness of these techniques in practice.


title: Parallelizing Algorithms for Symbolic Computation using ||MAPLE||

abstract: ||MAPLE|| (speak: parallel Maple) is a portable system for parallel symbolic computation. The system is built as an interface between the parallel declarative programming language Strand and the sequential computer algebra system Maple, thus providing the elegance of Strand and the power of the existing sequential algorithms in Maple. The implementation of different parallel programming paradigms shows that it is fairly easy to parallelize even complex algebraic algorithms using this system. Sample applications (among them algorithms solving multivariate nonlinear equation systems) are implemented on various parallel architectures. For example a straightforward parallelization of the complex and important problem of real root isolation has been parallelized using a generic Strand program of fewer than 20 lines of code and a slight modification of 5 lines in the original sequential Maple source. Even with such a simple modification we gained a speed-up of 5 times, that is better than thos...


title: Programming Task and Data Parallelism on a Multicomputer

authors:
Jaspal Subhlok
James M. Stichnoth
David R. O'Hallaron
Thomas R. Gross

abstract: For many applications, achieving good performance on a private memory parallel computer requires exploiting data parallelism as well as task parallelism. Depending on the size of the input data set and the number of nodes (i.e., processors), different tradeoffs between task and data parallelism are appropriate for a parallel system. Most existing compilers focus on only one of data parallelism and task parallelism. Therefore, to achieve the desired results, the programmer must separately program the data and task parallelism. We have taken a unified approach to exploiting both kinds of parallelism in a single framework with an existing language. This approach eases the task of programming and exposes the tradeoffs between data and task parallelism to the compiler. We have implemented a parallelizing Fortran compiler for the iWarp system based on this approach. We discuss the design of our compiler, and present performance results to validate our approach. 1 Introduction Many applicati...


title: An Efficient Implementation Scheme of Concurrent Object-Oriented Languages on Stock Multicomputers

authors:
Kenjiro Taura
Satoshi Matsuoka
Akinori Yonezawa

abstract: Several novel techniques for efficient implementtion of concurrent object-oriented languages on general purpose, stock multicomputers are presented. These techniques have been developed in implementing our concurrent object-oriented language ABCL on a Fujitsu Laboratory's experimental multicomputer AP1000 consisting of 512 SPARC chips. The propsed intra-node scheduling mechanism reduces the cost of local message passing. The cost of intra-node asynchronous message passing is about 20 SPARC instructions in the bst case, including locality checking, dynamic method lookup, and scheduling. The minimum latency of asynchronous internode message passing is about 9μs, or about 120 instructions, employing the self-dispatching mechanism independently proposed by Eicken et al. A large scale benchmark which involves 9,000,000 message passings shows 440 times speedup on the 512 nodes system compared to the sequential version of the same algorithm. We rely on simple hardware support for message passing and use no specialized architectural supports for object-oriented computing. Thus, we are able to enjoy the benefits of future progress in standard processor technology. Our result shows that concurrent object-oriented languages can be implemented efficiently on conventional multicomputers.


title: Leapfrogging: A Portable Technique for Implementing Efficient Futures

authors:
David B. Wagner
Brad Calder

abstract: A future is a language construct that allows programmers to expose parallelism in applicative languages such as MultiLisp [5] with minimal effort. In this paper we describe a technique for implementing futures, which we call leapfrogging, that reduces blocking due to load imbalance. The utility of leapfrogging is enhanced by the fact that it is completely platform-independent, is free from deadlock, and places a bound on stack sizes that is at most a small constant times the maximum stack size encountered during a sequential execution of the same computation. We demonstrate the performance of leapfrogging using a prototype implementation written in C++.


title: Experience with Fine-Grain Synchronization in MIMD Machines for Preconditioned Conjugate Gradient

authors:
Donald Yeung
Anant Agarwal

abstract: This paper discusses our experience with fine-grain synchronization for a variant of the preconditioned conjugate gradient method. This algorithm represents a large class of algorithms that have been widely used but traditionally difficult to implement efficiently on vector and parallel machines. Through a series of experiments conducted using a simulator of a distributed shared-memory multiprocessor, this paper addresses two major questions related to fine-grain synchronization in the context of this application. First, what is the overall impact of fine-grain synchronization on performance? Second, what are the individual contributions of the following three mechanisms typically provided to support fine-grain synchronization: language-level support, full-empty bits for compact storage and communication of synchronization state, and efficient processor operations on the state bits?


title: Data and Computation Transformations for Multiprocessors

authors:
Jennifer-Ann M. Anderson
Saman P. Amarasinghe
Monica S. Lam

abstract: Effective memory hierarchy utilization is critical to the performance of modern multiprocessor architectures. We havedeveloped the first compiler system that fully automatically parallelizes sequential programs and changes the original array layouts to improve memory system performance. Our optimization algorithm consists of two steps. The first step chooses the parallelization and computation assignment such that synchronization and data sharing are minimized. The second step then restructures the layout of the data in the shared address space with an algorithm that is based on a new data transformation framework. We ran our compiler on a set of application programs and measured their performance on the Stanford DASH multiprocessor. Our results show that the compiler can effectively optimize parallelism in conjunction with memory subsystem performance. 1 Introduction In the last decade, microprocessor speeds have been steadily improving at a rate of 50% to 100% every year[16]. Meanwh...


title: Generating Parallel Code from Object Oriented Mathematical Models

authors:
Niclas Andersson
Peter Fritzson

abstract: For a long time efficient use of parallel computers has been hindered by dependencies introduced in software through low-level implementation practice. In this paper we present a programming environment and language called Object-Math (Object oriented Mathematical language for scientific computing), which aims at eliminating this problem by allowing the user to represent mathematical equation-based models directly in the system. The system performs analysis of mathematical models to extract parallelism and automatically generates parallel code for numerical solution.


title: Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study (Extended Abstract)

authors:
David A. Bader
Joseph F. JáJá

abstract: This paper presents efficient and portable implementations of two useful primitives in image processing algorithms, histogramming and connected components. Our general framework is a single-address space, distributed memory programming model. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. Our connected components algorithm uses a novel approach for parallel merging which performs drastically limited updating during iterative steps, and concludes with a total consistency update at the final step. The algorithms have been coded in Split-C and run on a variety of platforms. Our experimental results are consistent with the theoretical analysis and provide the best known execution times for these two primitives, even when compared with machine-specific implementations. More efficient implementations of Split-C will likely result in even faster execution times.


title: Cilk: An Efficient Multithreaded Runtime System

authors:
Robert D. Blumofe
Christopher F. Joerg
Bradley C. Kuszmaul
Charles E. Leiserson
Keith H. Randall
Yuli Zhou

abstract: Cilk (pronounced “silk”) is a C-based runtime system for multi-threaded parallel programming. In this paper, we document the efficiency of the Cilk work-stealing scheduler, both empirically and analytically. We show that on real and synthetic applications, the “work” and “critical path” of a Cilk computation can be used to accurately model performance. Consequently, a Cilk programmer can focus on reducing the work and critical path of his computation, insulated from load balancing and other runtime scheduling issues. We also prove that for the class of “fully strict” (well-structured) programs, the Cilk scheduler achieves space, time and communication bounds all within a constant factor of optimal.


title: A Model and Compilation Strategy for Out-of-Core Data Parallel Programs

authors:
Rajesh Bordawekar
Alok N. Choudhary
Ken Kennedy
Charles Koelbel
Michael H. Paleczny

abstract: It is widely acknowledged in high-performance computing circles that parallel input/output needs substantial improvement in order to make scalable computers truly usable. We present a data storage model that allows processors independent access to their own data and a corresponding compilation strategy that integrates data-parallel computation with data distribution for out-of-core problems. Our results compare several communication methods and I/O optimizations using two out-of-core problems, Jacobi iteration and LU factorization.


title: High-Level Optimization via Automated Statistical Modeling

abstract: We develop the use of statistical modeling for portable high-level optimizations such as data layout and algorithm selection. We build the models automatically from profiling information, which ensures robust and accurate models that reflect all aspects of the target platform.


title: Software Caching and Computation Migration in Olden

authors:
Martin C. Carlisle
Anne Rogers

abstract: The goal of the Olden project is to build a system that provides parallelism for general purpose C programs with minimal programmer annotations. We focus on programs using dynamic structures such as trees, lists, and DAGs. We demonstrate that providing both software caching and computation migration can improve the performance of these programs, and provide a compile-time heuristic that selects between them for each pointer dereference. We have implemented a prototype system on the Thinking Machines CM-5. We describe our implementation and report on experiments with ten benchmarks.


title: Distributed Data Access in AC

authors:
William W. Carlson
Jesse M. Draper

abstract: We have modified the C language to support a programming model based on a shared address space with physically distributed memory. With this model users can write programs in which the nodes of a massively parallel processor can access remote memory without message passing. AC provides support for distributed arrays as well as pointers to distributed data. Simple array references and pointer dereferencing are sufficient to generate low-overhead remote reads and writes. We have implemented these ideas in a compiler based on the GNU C compiler and targeted at Cray Research's T3D. Initial performance measurements show that AC generates code for remote accesses which is considerably faster than that of the native compiler for structures up to about 16 words in size and virtually equivalent for larger transfers.


title: Fuzzy Array Dataflow Analysis

authors:
Jean-Francois Collard
Denis Barthou
Paul Feautrier

abstract: Exact array dataflow analysis can be achieved in the general case if the only control structures are do-loops and structural ifs, and if loop counter bounds and array subscripts are affine expressions of englobing loop counters and possibly some integer constants. In this paper, we begin the study of dataflow analysis of dynamic control programs, where arbitrary ifs and whiles are allowed. In the general case, this dataflow analysis can only be fuzzy.


title: Parallel Skeletons for Structured Composition

authors:
John Darlington
Yike Guo
Hing Wing To
Jin Yang

abstract: In this paper, we propose a straightforward solution to the problems of compositional parallel programming by using skeletons as the uniform mechanism for structured composition. In our approach parallel programs are constructed by composing procedures in a conventional base language using a set of high-level, pre-defined, functional, parallel computational forms known as skeletons. The ability to compose skeletons provides us with the essential tools for building further and more complex application-oriented skeletons specifying important aspects of parallel computation. Compared with the process network based composition approach, such as PCN, the skeleton approach abstracts away the fine details of connecting communication ports to the higher level mechanism of making data distributions conform, thus avoiding the complexity of using lower level ports as the means of interaction. Thus, the framework provides a natural integration of the compositional programming approach with the data parallel programming paradigm.


title: Flattening and Parallelizing Irregular, Recurrent Loop Nests

authors:
Anwar M. Ghuloum
Allan L. Fisher

abstract: Irregular loop nests in which the loop bounds are determined dynamically by indexed arrays are difficult to compile into expressive parallel constructs, such as segmented scans and reductions. In this paper, we describe a suite of transformations to automatically parallelize such irregular loop nests, even in the presence of recurrences. We describe a simple, general loop flattening transformation, along with new optimizations which make it a viable compiler transformation. A robust recurrence parallelization technique is coupled to the loop flattening transformation, allowing parallelization of segmented reductions, scans, and combining-sends over arbitrary associative operators. We discuss the implementation and performance results of the transformations in a parallelizing Fortran 77 compiler for the Cray C90 supercomputer. In particular, we focus on important sparse matrix-vector multiplication kernels, for one of which we are able to automatically derive an algorithm used by one of the fastest library routines available.


title: pC++/streams: a Library for I/O on Complex Distributed Data Structures

authors:
Jacob Gotwals
Suresh Srinivas
Dennis Gannon

abstract: The design and implementation of portable, efficient, and expressive mechanisms for I/O on complex distributed data structures—such as found in adaptive parallel applications—is a challenging problem that we address in this paper.We describe the design, programmer interface, implementation, and performance of pC++/streams, a library that provides an expressive mechanism for I/O on distributed arrays of variable-sized objects in pC++, an object-parallel language. pC++/streams is intended for developers of parallel programs requiring efficient high-level I/O abstractions for checkpointing, scientific visualization, and debugging.pC++/streams is an implementation of d/streams, a language-independent abstraction for buffered I/O on distributed data structures. We describe the d/streams abstraction and present performance results on the Intel Paragon and SGI Challenge showing that d/streams can be implemented efficiently and portably.


title: An Array Operation Synthesis Scheme to Optimize Fortran 90 Programs

authors:
Gwan-Hwan Hwang
Jenq Kuen Lee
Roy Dz-Ching Ju

abstract: An increasing number of programming languages, such as Fortran 90 and APL, are providing a rich set of intrinsic array functions and array expressions. These constructs which constitute an important part of data parallel languages provide excellent opportunities for compiler optimizations. In this paper, we present a new approach to combine consecutive data access patterns of array constructs into a composite access function to the source arrays. Our scheme is based on the composition of access functions, which is similar to a composition of mathematic functions. Our new scheme can handle not only data movements of arrays of different numbers of dimensions and segmented array operations but also masked array expressions and multiple sources array operations. As a result, our proposed scheme is the first synthesis scheme which can synthesize Fortran 90 RESHAPE, EOSHIFT, MERGE, and WHERE constructs together. Experimental results show speedups from 1.21 to 2.95 for code fragments from real applications on a Sequent multiprocessor machine by incorporating the proposed optimizations.


title: Reducing False Sharing on Shared Memory Multiprocessors through Compile Time Data Transformations

authors:
Tor E. Jeremiassen
Susan J. Eggers

abstract: We have developed compiler algorithms that analyze explicitly parallel programs and restructure their shared data to reduce the number of false sharing misses. The algorithms analyze per-process shared data accesses, pinpoint the data structures that are susceptible to false sharing and choose an appropriate transformation to reduce it. The transformations either group data that is accessed by the same processor or separate individual data items that are shared.


title: A Linear-Time Algorithm for Computing the Memory Access Sequence in Data-Parallel Programs

authors:
Ken Kennedy
Nenad Nedeljkovic
Ajay Sethi

abstract: Data-parallel languages, such as High Performance Fortran, are widely regarded as a promising means for writing portable programs for distributed-memory machines. Novel features of these languages call for the development of new techniques in both compilers and run-time systems. In this paper, we present an improved algorithm for finding the local memory access sequence in computations involving regular sections of arrays with cyclic(k) distributions. After establishing the fact that regular section indices correspond to elements of an integer lattice, we show how to find a lattice basis that allows for simple and fast enumeration of memory accesses. The complexity of our algorithm is shown to be lower than that of the previous solution for the same problem. In addition, the experimental results demonstrate the efficiency of our method in practice.


title: Efficient Support for Irregular Applications on Distributed-Memory Machines

authors:
Shubhendu S. Mukherjee
Shamik D. Sharma
Mark D. Hill
James R. Larus
Anne Rogers
Joel H. Saltz

abstract: Irregular computation problems underlie many important scientific applications. Although these problems are computationally expensive, and so would seem appropriate for parallel machines, their irregular and unpredictable run-time behavior makes this type of parallel program difficult to write and adversely affects run-time performance.


title: Automatic Alignment of Array Data and Processes to Reduce Communication Time on DMPPs

abstract: This paper investigates the problem of aligning data and processes in a distributed-memory implementation. We present complete algorithms for compile-time analysis, the necessary program restructuring, and subsequent code-generation, and discuss their complexity. We finally evaluate the practical usefulness by quantitative experimentation. The technique presented analyzes complete programs, including branches, loops, and nested parallelism. Alignment is determined with respect to offset, stride, and general axis relations. Both placement of data and processes are computed in a unifying framework based on an extended preference graph and its analysis. Furthermore, dynamic redistribution and replication are considered in the same technique. The experimental results are very encouraging. The optimization algorithms implemented in the Modula-2* compiler improved the execution times of the programs by over 40% on a MasPar MP-1 with 16384 processors. This paper appeared in: Proceedings of th...