Using Maude and Its Strategies for Defining a Framework for Analyzing Eden Semantics

Eden is a parallel extension of the functional language Haskell. On behalf of parallelism Eden overrides Haskell's pure lazy approach, combining a non-strict functional application with eager process creation and eager communication. We desire to investigate alternative semantics for Eden in order to analyze the consequences of some of the decisions adopted during the language design. In this paper we show how to implement in Maude the operational semantics of Eden in such a way that semantic rules can be modified easily. Moreover, other semantic features can be implemented by means of parameterized modules that allow to instantiate in different ways several parameters of the semantics but without modifying the semantic rules.     

Algebraic Correctness Proofs for Compiling Recursive Function Definitions with Strictness Information

Adding appropriate strictness information to recursive function definitions we achieve a uniform treatment of lazy and eager evaluation strategies. By restriction to first-order functions over basic types we develop a pure stack implementation that avoids a heap even for lazy arguments. We present algebraic definitions of denotational, operational, and stack-machine semantics and prove their equivalence by means of structural induction.     

Reducing the overhead of dynamic compilation

The execution model for mobile, dynamically‐linked, object‐oriented programs has evolved from fast interpretation to a mix of interpreted and dynamically compiled execution. The primary motivation for dynamic compilation is that compiled code executes significantly faster than interpreted code. However, dynamic compilation, which is performed while the application is running, introduces execution delay. In this paper we present two dynamic compilation techniques that enable high performance execution while reducing the effect of this compilation overhead. These techniques can be classified as (1) decreasing the amount of compilation performed, and (2) overlapping compilation with execution. We first present and evaluate lazy compilation, an approach used in most dynamic compilation systems in which individual methods are compiled on‐demand upon their first invocation. This is in contrast to eager compilation, in which all methods in a class are compiled when a new class is loaded. In this work, we describe our experience with eager compilation, as well as the implementation and transition to lazy compilation. We empirically detail the effectiveness of this decision. Our experimental results using the SpecJVM Java benchmarks and the Jalapeño JVM show that, compared to eager compilation, lazy compilation results in 57% fewer methods being compiled and reductions in total time of 14 to 26%. Total time in this context is compilation plus execution time. Next, we present profile‐driven, background compilation, a technique that augments lazy compilation by using idle cycles in multiprocessor systems to overlap compilation with application execution. With this approach, compilation occurs on a thread separate from that of application threads so as to reduce intermittent, and possibly substantial, delay in execution. Profile information is used to prioritize methods as candidates for background compilation. Methods are compiled according to this priority scheme so that performance‐critical methods are invoked using optimized code as soon as possible. Our results indicate that background compilation can achieve the performance of off‐line compiled applications and masks almost all compilation overhead. We show significant reductions in total time of 14 to 71% over lazy compilation. Copyright © 2001 John Wiley & Sons, Ltd.     

An Evaluation of Software-Based Release Consistent Protocols

This paper presents an evaluation of three software implementations of release consistency. Release consistent protocols allow data communication to be aggregated and allow multiple writers to simultaneously modify a single page. We evaluated an eager invalidate protocol that enforces consistency when synchronization variables are released, a lazy invalidate protocol that enforces consistency when synchronization variables are acquired, and a lazy hybrid protocol that selectively uses update to reduce access misses. Our evaluation is based on implementations running on DECstation-5000/240s connected by an ATM LAN and on an execution-driven simulator that allows us to vary network parameters. Our results show that the lazy protocols consistently outperform the eager protocol for all but one application and that the lazy hybrid performs the best overall. However, the relative performance of the implementations is highly dependent on the relative speeds of the network, processor, and communication software. Lower bandwidths and high per-byte software communication costs favor the lazy invalidate protocol, while high bandwidths and low per-byte costs favor the hybrid. Performance of the eager protocol approaches that of the lazy protocols only when communication becomes essentially free.     

Adapting combinator and SECD machines to display snapshots of functional computations

A functional computation involves substituting for function applications in an expression until that expression is reduced to normal form. The views of computations presented by the sequence- and state-oriented debugging tools of imperative systems are inappropriate for use with functional computations. New debugging tools are needed to aid the development of functional programs, especially in the context of lazy evaluation. After surveying previously reported debugging tools, we discuss a new debugging tool. Its implementation involves changing the reduction rules of the machine. The new reduction rules are applied to an interrupted computation to give a snapshot of that computation in source-level terms. We have implemented tools to produce snapshots for eager SECD and lazy combinator reduction machines. Example snapshots are shown from each. The implementation for an eager SECD machine is relatively straightforward, so we confine discussion of this to a brief sketch. A more detailed account is given of the implementation for a lazy combinator reduction machine, as this offers one solution to well-known problems with debugging functional programs in the context of lazy evaluation and combinator code.     

Comparing lazy and eager learning models for water level forecasting in river-reservoir basins of inundation regions

This study developed a methodology for formulating water level models to forecast river stages during typhoons, comparing various models by using lazy and eager learning approaches. Two lazy learning models were introduced: the locally weighted regression (LWR) and the k-nearest neighbor (kNN) models. Their efficacy was compared with that of three eager learning models, namely, the artificial neural network (ANN), support vector regression (SVR), and linear regression (REG). These models were employed to analyze the Tanshui River Basin in Taiwan. The data collected comprised 50 historical typhoon events and relevant hourly hydrological data from the river basin during 1996–2007. The forecasting horizon ranged from 1 h to 4 h. Various statistical measures were calculated, including the correlation coefficient, mean absolute error, and root mean square error. Moreover, significance, computation efficiency, and Akaike information criterion were evaluated. The results indicated that (a) among the eager learning models, ANN and SVR yielded more favorable results than REG (based on statistical analyses and significance tests). Although ANN, SVR, and REG were categorized as eager learning models, their predictive abilities varied according to various global learning optimizers. (b) Regarding the lazy learning models, LWR performed more favorably than kNN. Although LWR and kNN were categorized as lazy learning models, their predictive abilities were based on diverse local learning optimizers. (c) A comparison of eager and lazy learning models indicated that neither were effective or yielded favorable results, because the distinct approximators of models that can be categorized as either eager or lazy learning models caused the performance to be dependent on individual models.     

Adaptive Consensus of Non-Strict Feedback Switched Multi-Agent Systems With Input Saturations

This paper considers the leader-following consensus for a class of nonlinear switched multi-agent systems (MASs) with non-strict feedback forms and input saturations under unknown switching mechanisms. First, in virtue of Gaussian error functions, the saturation nonlinearities are represented by asymmetric saturation models. Second, neural networks are utilized to approximate some unknown packaged functions, and the structural property of Gaussian basis functions is introduced to handle the non-strict feedback terms. Third, by using the backstepping process, a common Lyapunov function is constructed for all the subsystems of the followers. At last, we propose an adaptive consensus protocol, under which the tracking error under arbitrary switching converges to a small neighborhood of the origin. The effectiveness of the proposed protocol is illustrated by a simulation example.      

Non-Strict Execution in Parallel and Distributed Computing

This paper surveys and demonstrates the power of non-strict evaluation in applications executed on distributed architectures. We present the design, implementation, and experimental evaluation of single assignment, incomplete data structures in a distributed memory architecture and Abstract Network Machine (ANM). Incremental Structures (IS), Incremental Structure Software Cache (ISSC), and Dynamic Incremental Structures (DIS) provide non-strict data access and fully asynchronous operations that make them highly suited for the exploitation of fine-grain parallelism in distributed memory systems. We focus on split-phase memory operations and non-strict information processing under a distributed address space to improve the overall system performance. A novel technique of optimization at the communication level is proposed and described. We use partial evaluation of local and remote memory accesses not only to remove much of the excess overhead of message passing, but also to reduce the number of messages when some information about the input or part of the input is known. We show that split-phase transactions of IS, together with the ability of deferring reads, allow partial evaluation of distributed programs without losing determinacy. Our experimental evaluation indicates that commodity PC clusters with both IS and a caching mechanism, ISSC, are more robust. The system can deliver speedup for both regular and irregular applications. We also show that partial evaluation of memory accesses decreases the traffic in the interconnection network and improves the performance of MPI IS and MPI ISSC applications.     

Building Interpreters with Rewriting Strategies

Programming language semantics based on pure rewrite rules suffers from the gap between the rewriting strategy implemented in rewriting engines and the intended evaluation strategy. This paper shows how programmable rewriting strategies can be used to implement interpreters for programming languages based on rewrite rules. The advantage of this approach is that reduction rules are first class entities that can be reused in different strategies, even in other kinds of program transformations such as optimizers. The approach is illustrated with several interpreters for the lambda calculus based on implicit and explicit (parallel) substitution, different strategies including normalization, eager evaluation, lazy evaluation, and lazy evaluation with updates. An extension with pattern matching and choice shows that such interpreters can easily be extended.     

Using Discrete Event Simulation to Analyze Contention Managers

Understanding the behavior and benefits of contention managers is important for designing transactional memory implementations. Contention manager design is closely tied to other design decisions in a transaction memory implementation, and therefore experiments to compare the behaviors of contention managers are difficult. This paper presents a discrete event simulator that allows researchers to explore the behavior of contention managers and even to perform experiments that compare lazy conflict detection without contention management to eager detection combined with a contention manager. For our benchmarks, we found that lazy conflict detection was competitive with the best contention managers. Our experiments confirm that contention management design is critical for transactional memories that use eager validation. We used the simulator to explore new tiered contention managers that combine livelock-prone contention managers with livelock-free contention managers to provide the benefits of the livelock-prone contention manager while avoiding its pathological behaviors under contention.