This paper describes a new technique to reduce page-faults in multiprocessing systems by supplying compile-time information about application's access patterns to the kernel. Runtime support is used to determine parameters unknown at compile-time and to summarize all this information as a marginal-loss function. Marginal loss functions describe the extra number of page faults that a process incurs when one of its pages is removed from main memory. System calls convey the marginal loss function of each active memory segment to the kernel which uses this information to determine the allocation and replacement of pages. We outline how the compiler analyzes access patterns and how the marginal loss function can be computed for common patterns. Simulation results demonstrate a significant reduction in page faults compared to typical approaches used by current operating systems.

Sparse matrix problems are difficult to parallelize efficiently on distributed memory machines since non-zero elements are unevenly scattered and are accessed via multiple levels of indirection. Distributions that achieve good load balance and locality are hard to compute and also lead to further indirection in locating distributed data. This paper evaluates alternative distribution strategies which trade off the quality of load-balance and locality for lower decomposition costs and efficient lookup. The proposed techniques are compared with previous strategies for parallelizing sparse matrix problems and the relative merits of each method is outlined. 1 Introduction Sparse matrices are used in a large number of important scientific codes, such as molecular dynamics, CFD solvers, finite element methods and climate modelling. Unfortunately, these applications are hard to parallelize efficiently, particularly using automated compiler techniques. This is because sparse matrices are repre...

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.

Article Remote queues: exposing message queues for optimization and atomicity Share on Authors: Eric A. Brewer UC Berkeley UC BerkeleyView Profile , Frederic T. Chong MIT MITView Profile , Lok T. Liu UC Berkeley UC BerkeleyView Profile , Shamik D. Sharma University of Maryland University of MarylandView Profile , John D. Kubiatowicz MIT MITView Profile Authors Info & Claims SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architecturesJuly 1995 Pages 42–53https://doi.org/10.1145/215399.215416Online:20 July 1995Publication History 50citation349DownloadsMetricsTotal Citations50Total Downloads349Last 12 Months10Last 6 weeks2 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

Abstract In many scientific applications, arrays containing data are indirectly indexed through indirection arrays. Such scientific applications are called irregular programs and are a distinct class of applications that require special techniques for parallelization. This paper presents a library called CHAOS, which helps users implement irregular programs on distributed‐memory message‐passing machines, such as the Paragon, Delta, CM‐5 and SP‐1. The CHAOS library provides efficient runtime primitives for distributing data and computation over processors; it supports efficient index translation mechanisms and provides users high‐level mechanisms for optimizing communication. CHAOS subsumes the previous PARTI library and supports a larger class of applications. In particular, it provides efficient support for parallelization of adaptive irregular programs where indirection arrays are modified during the course of computation. To demonstrate the efficacy of CHAOS, two challenging real‐life adaptive applications were parallelized using CHAOS primitives: a molecular dynamics code, CHARMM, and a particle‐in‐cell code, DSMC. Besides providing runtime support to users, CHAOS can also be used by compilers to automatically parallelize irregular applications. This paper demonstrates how CHAOS can be effectively used in such a framework. By embedding CHAOS primitives in the Syracuse Fortran 90D/HPF compiler, kernels taken from the CHARMM and DSMC codes have been automatically parallelized.

In adaptive irregular problems, data arrays are accessed via indirection arrays, and data access patterns change during computation. Parallelizing such problems on distributed memory machines requires support for dynamic data partitioning, efficient preprocessing and fast data migration. This paper describes CHAOS, a library of efficient runtime primitives that provides such support. To demonstrate the effectiveness of the runtime support, two adaptive irregular applications have been parallelized using CHAOS primitives: a molecular dynamics code (CHARMM) and a code for simulating gas flows (DSMC). We have also proposed minor extensions to Fortran D which would enable compilers to parallelize irregular for all loops in such adaptive applications by embedding calls to primitives provided by a runtime library. We have implemented our proposed extensions in the Syracuse Fortran 90D/HPF prototype compiler, and have used the compiler to parallelize kernels from two adaptive applications.>