14329383
STeP: The Stanford Temporal Prover
We describe the Stanford Temporal Prover (STeP), a system being developed to support the computer-aided formal verification of concurrent and reactive systems based on temporal specifications. Unlike systems based on model-checking, STeP is not restricted to finite-state systems. It combines model checking and deductive methods to allow the verification of a broad class of systems, including programs with infinite data domains, N-process programs, and N-component circuit designs, for arbitrary N. In short, STeP has been designed with the objective of combining the expressiveness of deductive methods with the simplicity of model checking. The verification process is for the most part automatic. User interaction occurs mostly at the highest, most intuitive level, primarily through a graphical proof language of verification diagrams. Efficient simplification methods, decision procedures, and invariant generation techniques are then invoked automatically to prove resulting first-order verification conditions with minimal assistance. We describe the performance of the system when applied to several examples, including the N-process dining philosopher''s program, Szymanski''s N-process mutual exclusion algorithm, and a distributed N-way arbiter circuit.
43332794
Hiding Relaxed Memory Consistency with a Compiler
18425238
A compiler for multiple memory models
The design of consistency models for both hardware and software is a difficult task. For a programming language, it is particularly difficult because the target audience for a high-level programming language is much wider than the target audience for a machine language, making usability a more important criterion. Exacerbating this problem is the reality that the programming language community has little experience designing programming language consistency models, and therefore each new attempt is very much a voyage into uncharted territory. A concrete example of the difficulties of the task is the current Java Memory Model. Although designed to be easy to use by Java programmers, it is poorly understood and at least one common idiom (the ‘double check idiom’) to exploit the model is unsafe. In this paper, we describe the design of an optimizing Java compiler that will accept either as input or as an interface implementation a consistency model for the code to be compiled. The compiler will use Shasha and Snir's delay set analysis, and our CSSA program representation to provide a canonical representation for the effects of different consistency models on optimizations and analysis. The compiler will serve as a testbed to prototype new memory models, and to measure the effects of different memory models on program performance. Copyright © 2004 John Wiley & Sons, Ltd.
6606959
Adaptively Mapping Code in an Intelligent Memory Architecture
This paper presents an algorithm to authomatically map code to a generic Processor-In-Memory (PIM) system that consists of a host processor and a much simpler memory processor. To achieve high performance with this type of architecture, code needs to be partitioned and scheduled such that each section is assigned to the processor on which it runs most efficiently. In addition, processors should overlap their execution as much as possible. 
 
Our algorithm is embeded in a compiler and run-time system and maps applications fully automatically using both static and dynamic information. Using a set of applications and a simulated architecture, we show average speedups of 1.7 over a single host with plain memory. The speedups are very close and often higher than ideal speedups on a more expensive multiprocessor system composed of two identical host processors. Our work shows that heterogeneity can be cost-effectively exploited, and represents one step toward effectively mapping code to more advanced PIM systems.
14452578
Automatically mapping code on an intelligent memory architecture
This paper presents an algorithm to automatically map code on a generic intelligent memory system that consists of a host processor and a simpler memory processor. To achieve high performance with this type of architecture, code needs to be partitioned and scheduled such that each section is assigned to the processor on which it runs most efficiently. In addition, the two processors should overlap their execution as much as possible. With our algorithm, applications are mapped fully automatically using both static and dynamic information. Using a set of standard applications and a simulated architecture, we show average speedups of 1.7 for numerical applications and 1.3 for nonnumerical applications over a single host with plain memory. The speedups are very close and often higher than ideal speedups on a more expensive multiprocessor system composed of two identical host processors. Our work shows that heterogeneity can be cost-effectively exploited and represents one step toward effectively mapping code on intelligent memory systems.
45872187
Parallel Programming with Polaris
Parallel programming tools are limited, making effective parallel programming difficult and cumbersome. Compilers that translate conventional sequential programs into parallel form would liberate programmers from the complexities of explicit, machine oriented parallel programming. The paper discusses parallel programming with Polaris, an experimental translator of conventional Fortran programs that target machines such as the Cray T3D.
19612327
Instruction level redundant number computations for fast data intensive processing in asynchronous processors
Instruction level parallelism (ILP) is strictly limited by various dependencies. In particular, data dependency is a major performance bottleneck of data intensive applications. In this paper we address acceleration of the execution of instruction codes serialized by data dependencies. We propose a new computer architecture supporting a redundant number computation at the instruction level. To design and implement the scheme, an extended data-path and additional instructions are also proposed. The architectural exploitation of instruction level redundant number computations (IL-RNC) makes it possible to eliminate carry propagations. As a result execution of instructions which are serialized due to inherent data dependencies is accelerated. Simulations have been performed with data intensive processing benchmarks and the proposed architecture shows about a 1.2-1.35 fold speedup over a conventional counterpart. The proposed architecture model can be used effectively for data intensive processing in a microprocessor, a digital signal processor and a multimedia processor.
948007
A Microeconomic Approach to Intelligent Resource Sharing in Multiagent Systems
Abstract : We have analyzed characteristics of sharable resources and developed techniques for intelligently sharing resources specifically, communication channels among agents in multiagent systems. Our techniques allow agents to nearly optimize their communication behavior in a self-organizing and distributed fashion, involving the use of a microeconomic pricing system based on economic laws of supply and demand and trading among agents in real-time. Our analyses are based on three measures of performance: fairness of resource allocation, waiting time for resources, and utilization of resources. Our initial analysis indicates that fairness and utilization are conflicting, in that the best utilization with a fair allocation is equivalent to the worst utilization with an unfair resource allocation, assuming the allocation policy is statically defined. To strike a balance in performance, we have developed mechanisms that establish an artificial economy, where agents can dynamically reallocate goods (resource access) using a competitive market pricing mechanism. However, unlike more common market-oriented methods, our approach does not demand convergence to equilibrium, but permits more rapid, heuristic trading, leading to near optimal performance where both buyers and sellers of resources can benefit. Our studies show that agents employing our mechanisms can dramatically improve utilization while still providing fair access to the resources.
17246831
Use of Case-Based Reasoning in the Domain of Building Regulations
In traditional legal decision support systems, it has been regarded as natural to represent statutes in terms of decision rules and to link these to a separate case-based reasoning system for handling precedent. Statutory legal rules used in these systems are formal and prescriptive. Building regulations in Scotland are part of statute law and constitute part of a legal system together with case histories. In recent years, the regulations have been becoming less prescriptive and more emphasis has been put onto the interpretive use of the regulations. In developing a system which can assist domain experts in interpreting the regulations, this trend has presented us with difficulties in employing this traditional approach and has led us to a unified case-based model of the regulations and case histories. In this paper, we first describe the characteristics of the regulations and the activities involved in this domain. Second, we explain the reason why we abandoned the traditional approach. Third, we describe the system which has been developed using this case-based model.
1712871
Quasi-interpolants Based Multilevel B-Spline Surface Reconstruction from Scattered Data
This paper presents a new fast and local method of 3D surface reconstruction for scattered data. The algorithm makes use of quasi-interpolants to compute the control points from a coarse to fine hierarchy to generate a sequence of bicubic B-spline functions whose sum approaches to the desired interpolation function. Quasi-interpolants gives a procedure for deriving local spline approximation methods where a B-spline coefficient only depends on data points taken from the neighborhood of the support corresponding B-spline. Experimental results demonstrate that high-fidelity reconstruction is possible from a selected set of irregular samples.
3175252
Predicate-based caching in mobile clients for con tinuous partial match queries
This paper proposes a cache management scheme for continuous partial match queries in mobile computing systems. Conventional cache management methods for mobile clients are record ID-based ones. However, since the partial match query is a content-based retrieval, the conventional record ID-based approach cannot properly manage the cache consistency. We show the pr edicate- based approach is an effective cache management in mobile environments.