MicroGP—An Evolutionary Assembly Program Generator

This paper describes μGP, an evolutionary approach for generating assembly programs tuned for a specific microprocessor. The approach is based on three clearly separated blocks: an evolutionary core, an instruction library and an external evaluator. The evolutionary core conducts adaptive population-based search. The instruction library is used to map individuals to valid assembly language programs. The external evaluator simulates the assembly program, providing the necessary feedback to the evolutionary core. μGP has some distinctive features that allow its use in specific contexts. This paper focuses on one such context: test program generation for design validation of microprocessors. Reported results show μGP being used to validate a complex 5-stage pipelined microprocessor. Its induced test programs outperform an exhaustive functional test and an instruction randomizer, showing that engineers are able to automatically obtain high-quality test programs.     

SLT-Resolution for the Well-Founded Semantics

Global SLS-resolution and SLG-resolution are two representative mechanisms for top-down evaluation of the well-founded semantics of general logic programs. Global SLS-resolution is linear for query evaluation but suffers from infinite loops and redundant computations. In contrast, SLG-resolution resolves infinite loops and redundant computations by means of tabling, but it is not linear. The principal disadvantage of a nonlinear approach is that it cannot be implemented by using a simple, efficient stack-based memory structure nor can it be easily extended to handle some strictly sequential operators such as cuts in Prolog. In this paper, we present a linear tabling method, called SLT-resolution, for top-down evaluation of the well-founded semantics. SLT-resolution is a substantial extension of SLDNF-resolution with tabling. Its main features are the following. First, it resolves infinite loops and redundant computations while preserving the linearity. Second, it is terminating and is sound and complete w.r.t. the well-founded semantics for programs with the bounded-term-size property with nonfloundering queries. Its time complexity is comparable with SLG-resolution and polynomial for function-free logic programs. Third, because of its linearity for query evaluation, SLT-resolution bridges the gap between the well-founded semantics and standard Prolog implementation techniques. It can be implemented by an extension to any existing Prolog abstract machines such as WAM or ATOAM.     

Latency Metric: An Experimental Method for Measuring and Evaluating Parallel Program and Architecture Scalability

Latency measures the delay caused by communication between processors and memory modules over the network in a parallel system. Using intensive measurements and simulation, we show that network latency forms a major obstacle to improving parallel computing performance and scalability. We present an experimental metric, using network latency to measure and evaluate the scalability of parallel programs and architectures. This latency metric is an extension to the isoefficiency function [Grama et al., IEEE Parallel Distrib. Technology 1, 3 (1993), 12-21] and iso-speed metric [Sun and Rover, IEEE Trans. Parallel Distrib. Systems 5, 6 (1994), 599-613]. We give a measurement method for using this latency metric, and report the experimental results of evaluating the scalabilities of several scientific computing algorithms on the KSR-1 shared-memory architecture. Our analysis and experiments show that the latency metric is a practical method to effectively predict and evaluate scalability based on measured latencies inherent in the program and the architecture.     

A separation of syntactic and nonsyntactic (1,+k)-branching programs

For (1,+k)-branching programs and read-k-times branching programs syntactic and nonsyntactic variants can be distinguished. The nonsyntactic variants correspond in a natural way to sequential computations with restrictions on reading the input while lower bound proofs are easier for the syntactic variants. In this paper it is shown that nonsyntactic (1,+k)-branching programs are really more powerful than syntactic (1,+k)-branching programs by presenting an explicitly defined function with polynomial size nonsyntactic (1,+1)-branching programs but only exponential size syntactic (1,+k)-branching programs. Another separation of these variants of branching programs is obtained by comparing the complexity of the satisfiability test for both variants. Received: July 16, 1998.     

Protected completions of first-order general logic programs

Minker and Perlis [15] have made the important observation that in certain circumstances, it might be desirable to prevent the inference of A when A is in the finite failure set of a logic program P. In this paper, we investigate the model-theoretic aspects of their proposal and develop a Fitting-style [5] declarative semantics for protected completions of general logic programs (containing function symbols). This extends the Minker-Perlis proposal which applies to function-free pure logic programs. In addition, an operational semantics is proposed and it is proven to be sound for existentially quantified positive queries and negative ground queries to general, canonical protected logic programs. Completeness issues are investigated and completeness is proved for positive existential queries and negative ground queries for the following classes of programs: (1) function-free general protected logic programs (the Minker-Perlis operational semantics apply to function-free pure protected logic programs), (2) pure protected logic programs (with function symbols) and (3) protected general logic programs that do not contain any internal variables (though they may contain function symbols).     

A debugger for parallel processes

A system for analysing and debugging parallel Fortran codes is in use on the Sun workstation. The system is composed of a parallel processing simulator mtsim, a window- and mouse-based debugging tool mtdbx, and a set of real-time display routines. The simulator mtsim, which is called from Fortran by a set of routines having the same syntax as the CRAY X-MP multitasking library, causes several concurrently active user tasks to be executed. The debugger mtdbx is based on the Sun dbxtool debugging facility. It has an enhanced command interface with functional control of parallel processes in multiple windows. The display routines offer two real-time views of multitasking synchronization primitives as they are used during execution. These three components of the debugging system afford the opportunity to analyse the behaviour of parallel processes by dynamic interaction at run-time.     

Competing for theAC-Unification Race

We describe our implementation of the unification algorithm for terms involving some associative-commutative operators plus free function symbols described by Boudetet al. The first goal of this implementation is efficiency, more precisely competing for theAC Unification Race. Although our implementation has been designed for good performance when applied to non-elementaryAC-unification problems, it is also very efficient on elementary problems. Our implementation, written in C and running on Sun workstations, is to be compared with the implementations in LISP, on Symbolics LIPS machines.     

Causing communication closure: safe program composition with reliable non-FIFO channels

A rigorous framework for analyzing safe composition of distributed programs is presented. It facilitates specifying notions of safe sequential execution of distributed programs in various models of communication. A notion of sealing is defined, where if a program P is immediately followed by a program Q that seals P then P will be —it will execute as if it runs in isolation. None of its send or receive actions will match or interact with actions outside P. The applicability of sealing is illustrated by a study of program composition when communication is reliable but not necessarily FIFO. In this model, special care must be taken to ensure that messages do not accidentally overtake one another in the composed program. In this model no program that sends or receives messages can be composed automatically with arbitrary programs without jeopardizing their intended behavior. Safety of composition becomes context-sensitive and new tools are needed for ensuring it. The investigation of sealing in this model reveals a novel connection between Lamport causality and safe composition. A characterization of sealable programs is given, as well as efficient algorithms for testing if Q seals P and for constructing a seal for a class of straight-line programs. It is shown that every sealable program can be sealed using O(n) messages. In fact, 3n − 4 messages are necessary and sufficient in the worst case, despite the fact that a sealable program may be open to interference on Ω(n ²) channels.     

High-Scalability Parallelization of a Molecular Modeling Application: Performance and Productivity Comparison Between OpenMP and MPI Implementations

Important components of molecular modeling applications are estimation and minimization of the internal energy of a molecule. For macromolecules such as proteins and amino acids, energy estimation is performed using empirical equations known as force fields. Over the past several decades, much effort has been directed towards improving the accuracy of these equations, and the resulting increased accuracy has come at the expense of greater computational complexity. For example, the interactions between a protein and surrounding water molecules have been modeled with improved accuracy using the generalized Born solvation model, which increases the computational complexity to O (n ³). Fortunately, many force-field calculations are amenable to parallel execution. This paper describes the steps that were required to transform the Born calculation from a serial program into a parallel program suitable for parallel execution in both the OpenMP and MPI environments. Measurements of the parallel performance on a symmetric multiprocessor reveal that the Born calculation scales well for up to 144 processors. In some cases the OpenMP implementation scales better than the MPI implementation, but in other cases the MPI implementation scales better than the OpenMP implementation. However, in all cases the OpenMP implementation performs better than the MPI implementation, and requires less programming effort as well. Trademark Legend Sun, Sun Microsystems, SPARC, UltraSPARC, Sun Fire, Sun Performance Library and Sun HPC Cluster Tools are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.     

Detecting Race Conditions in Parallel Programs that Use Semaphores

Abstract. We address the problem of detecting race conditions in programs that use semaphores for synchronization. Netzer and Miller showed that it is NP-complete to detect race conditions in programs that use many semaphores. We show in this paper that it remains NP-complete even if only two semaphores are used in the parallel programs. For the tractable case, i.e., using only one semaphore, we give two algorithms for detecting race conditions from the trace of executing a parallel program on p processors, where n semaphore operations are executed. The first algorithm determines in O(n) time whether a race condition exists between any two given operations. The second algorithm runs in O( np log n) time and outputs a compact representation from which one can determine in O(1) time whether a race condition exists between any two given operations. The second algorithm is near-optimal in that the running time is only O( log n) times the time required simply to write down the output.     

Consistency Property of Finite FC-Normal Logic Programs

Marek＇s forward-chaining construction is one of the important techniques for investigating the non-monotonic reasoning. By introduction of consistency property over a logic program, they proposed a class of logic programs, FC-normal programs, each of which has at least one stable model. However, it is not clear how to choose one appropriate consistency property for deciding whether or not a logic program is FC-normal. In this paper, we firstly discover that, for any finite logic programⅡ, there exists the least consistency property LCon（Ⅱ） overⅡ, which just depends onⅡitself, such that, Ⅱ is FC-normal if and only ifⅡ is FC-normal with respect to （w.r.t.） LCon（Ⅱ）. Actually, in order to determine the FC-normality of a logic program, it is sufficient to check the monotonic closed sets in LCon（Ⅱ） for all non-monotonic rules, that is LFC（Ⅱ）. Secondly, we present an algorithm for computing LFC（Ⅱ）. Finally, we reveal that the brave reasoning task and cautious reasoning task for FC-normal logic programs are of the same difficulty as that of normal logic programs.     

Towards Language-Agnostic Mobile Code

The Java Virtual Machine is primarily designed for transporting Java programs. As a consequence, when JVM bytecodes are used to transport programs in other languages, the result becomes less acceptable the more the source language diverges from Java. Microsoft's .NET transport format fares better in this respect because it has a more flexible type system and instruction set, but it is not extensible, and (for example) has no provision for supporting explicit programmer-specified parallelism. Both platforms have difficulty making transported programs run efficiently.This paper discusses first steps towards mobile code representations that are independent (in the sense that the representation can be appropriately parameterized) of the source language (e.g., Java), intermediate representation (e.g., bytecode), and target architecture (e.g., x86). We call this kind of parameterizable framework language-agnostic.We present two techniques which provide parts of the envisioned language-agnostic functionality. Compressed abstract syntax trees as a wire format provide for a very dense encoding of programs at a high level of abstraction. We show how to parameterize the compression algorithm in a modular fashion with knowledge beyond the purely syntactical level. This leads to the notion of well-formedness by construction. The second technique defines the semantics of programs by mapping from abstract syntax trees to a typed core calculus representation. Based on this representation it becomes possible to use portable definitions of security policies and to execute programs written in different source languages, even if a more efficient trusted native compiler is not available on the target platform.     

Complexities of Homomorphism and Isomorphism for Definite Logic Programs

A homomorphism (?) of logic programs from P to P' is a function mapping Atoms(P) to Atoms(P') and it preserves complements and program clauses. For each definite program clause a←a1,...,an∈P it implies that (?)(a)←(?)(a1),...,(?)(an) is a program clause of P'. A homomorphism (?) is an isomorphism if (?) is a bijection. In this paper, the complexity of the decision problems on homomorphism and isomorphism for definite logic programs is studied. It is shown that the homomorphism problem (HOM-LP) for definite logic programs is NP-complete, and the isomorphism problem (ISO-LP) is equivalent to the graph isomorphism problem (GI).     

Extended Interval Power Function

The containment set as an extension of the range of a function has been introduced in a series of white papers; see e.g. Walster, G. W.: Closed Interval Systems, Sun Microsystems, 2002, and Walster, G. W, et al.: Extended Real Intervals and the Topological Closure of Extended Real Relations, Sun Microsystems, 2002. The containment evaluation provides an exception free evaluation of functions over an arbitrary range.In this paper we discuss alternative existing implementations (C++ Interval Arithmetic Programming Reference, Sun Microsystems, 2000, and Hofschuster, W. et al.: The Interval Library fi_lib++ 2.0, Design, Features and Sample Programs, Universität Wuppertal, 2001) of the power function, introduce a new version, develop containment sets and discuss algorithms for the implementation.     

The calculation of the distribution of the Sun glitter radiance on the ocean surface by observing from a geostationary orbit

This paper presents a method for calculating the distribution of Sun glitter radiances from the ocean surface and a definition of the contour of the Sun disc image on the smooth ocean surface. Remotely sensed data were recorded from geostationary orbit and the spherical form of the Earth and shadowing effect on the rough ocean surface were taken into account. The reflected Sun radiance was calculated using the stochastically distributed facets method. The results of the calculations showed that the size of the Sun glint-affected region of ocean and also the value of the Sun glitter radiance in this region depend on both the geometry of observation and the degree of ocean surface roughness (i.e. over ocean wind speed v     

Multistage indexing algorithms for speeding prolog execution

In a previous article we proposed a new and efficient indexing technique that utilizes all the functors in the clause-heads and the goal. The salient feature of this technique is that the selected clause-head unifies (modulo nonlinearity) with the goal. As a consequence, our technique results in sharper discrimination, fewer choice points and reduced backtracking. A naïve and direct implementation of our indexing algorithms considerably slowed down the execution speeds of a wide range of programs typically seen in practice. This is because it handled deep and shallow terms, terms with few indexable arguments, small and large procedures uniformly. To beneficially extend the applicability of our algorithms we need mechanisms that are ‘sensitive’ to term structures and size and complexity of procedures. We accomplish this in the v-ALS compiler by carefully decomposing our indexing process into multiple stages. The operations performed by these stages increase in complexity ranging from first argument indexing to unification (modulo nonlinearity). Further the indexing process can be terminated at any stage if it is not beneficial to continue further. We have now completed the design and implementation of v-ALS. Using it we have enhanced the performance of a broad range of programs typically encountered in practice. Our experience strongly suggests that indexing based on unification (modulo nonlinearity) is a viable idea in practice and that a broad spectrum of useful programs can realize all of its benefits.     

Semantics of sub-probabilistic programs

The aim of this paper is to extend the probabilistic choice in probabilistic programs to sub-probabilistic choice, i.e., of the form (p)P ^⋈(q)Q where p + q ⩽ 1. It means that program P is executed with probability p and program Q is executed with probability q. Then, starting from an initial state, the execution of a sub-probabilistic program results in a sub-probability distribution. This paper presents two equivalent semantics for a sub-probabilistic while-programming language. One of these interprets programs as sub-probabilistic distributions on state spaces via denotational semantics. The other interprets programs as bounded expectation transformers via wp-semantics. This paper proposes an axiomatic systems for total logic, and proves its soundness and completeness in a classical pattern on the structure of programs.     

Coordinating components in middleware systems

Configuration and coordination are central issues in the design and implementation of middleware systems and are one of the reasons why building such systems is more complex than constructing stand‐alone sequential programs. Through configuration, the structure of the system is established—which elements it contains, where they are located and how they are interconnected. Coordination is concerned with the interaction of the various components—when an interaction takes place, which parties are involved, what protocols are followed. Its purpose is to coordinate the behaviour of the various components to meet the overall system specification. The open and adaptive nature of middleware systems makes the task of configuration and coordination particularly challenging. We propose a model that can operate in such an environment and enables the dynamic integration and coordination of components by observing and coercing their behaviour through the interception of the messages exchanged between them. Copyright © 2003 John Wiley & Sons, Ltd.