bluuebunny/crossref_metadata_2025 huggingface dataset:
Compositional parallel programming languages
Authors: Foster Ian
Published: October 2002

In task-parallel programs, diversee activities can take place concurrently, and communication and synchronization patterns are complex and not easily predictable. Previous work has identifiedcompositionalityas an important design principle for task-parallel programs. In this article, we discuss alternative approaches to the realization of this principle, which holds that properties of program components should be preserved when those co ponents are composed in parallel with other program components. We review two programming languages, Strand and Program Composition Notation, that support compositionality via a small number of simple concepts, namely, monotone operations on shared opbects, a uniform addressing mechanism, and parallel composition. Both languages have been used extensively for large-scale application development, allowing us to provide an informed assessment of both their strengths and their weaknesses. We observe that while compositionality simplifies development of complex applications, the use of specialized languages hinders reuse of existing code and tools and the specification of domain decomposition strategies. This suggests an alternative approach based on small extensions to existing sequential languages. We conclude the article with a discussion of two languages that realized this strategy.
Implementing signatures for C++
Authors: Baumgartner Gerald , Russo Vincent F.
Published: October 2002

We outline the design and detail the implementation of a language extension for abstracting types and for decoupling subtyping and inheritance in C++. This extension gives the user more of the flexibility of dynamic typing while retaining the efficiency and security of static typing. After a brief discussion of syntax and semantics of this language extension and examples of its use, we present and analyze three different implementation techniques: a preprocessor to a C++ compiler, an implementation in the front end of a C++ compiler, and a low-level implementation with back-end support. We follow with an analysis of the performance of the three implementation techniques and show that our extension actually allows subtype polymorphism to be implemented more efficiently than with virtual functions. We conclude with a discussion of the lessons we learned for future programming language design.
An axiomatic treatment of exception handling in an expression-oriented language
Authors: Yemini Shaula , Berry Daniel M.
Published: October 2002

An axiomatic semantic definition is given of the replacement model of exception handling in an expression-oriented language. These semantics require only two new proof rules for the most general case. An example is given of a program fragment using this model of exception handling, and these rules are used to verify the consistency of the fragment and its specification.
Nesting of reducible and irreducible loops
Authors: Havlak Paul
Published: October 2002

Recognizing and transforming loops are essential steps in any attempt to improve the running time of a program. Aggressive restructuring techniques have been developed for single-entry (reducible) loops, but restructurers and the dataflow and dependence analysis they rely on often give up in the presence of multientry (irreducible) loops. Thus one irreducible loop can prevent the improvement of all loops in a procedure. This article give an algorithm to build a loop nesting tree for a procedure with arbitrary control flow. The algorithm uses definitions of reducible and irreducible loops which allow either kind of loop to be nested in the other. The tree construction algorithm, an extension of Tarjan's algorithm for testing reducibility, runs in almost linear time. In the presence of irreducible loops, the loop nesting tree can depend on the depth-first spanning tree used to build it. In particular, the header node representing a reducible loop in one version of the loop nesting tree can be the representative of an irreducible loop in another. We give a normalization method that maximizes the set of reducible loops discovered, independent of the depth-first spanning tree used. The normalization require the insertion of at most one node and one edge per reducible loop.
A refinement calculus for the synthesis of verified hardware descriptions in VHDL
Authors: Breuer Peter T. , Delgado Carlos Kloos , Marín Andrés López , Martínez Madrid Natividad , Sánchez Fernández Luis
Published: October 2002

A formal refinement calculus targeted at system-level descriptions in the IEEE standard hardware description language VHDL is described here. Refinement can be used to develop hardware description code that is “correct by construction”. the calculus is closely related to a Hoare-style programming logic for VHDL and real-time systems in general. That logic and a semantics for a core subset of VHDL are described. The programming logic and the associated refinement calculus are shown to be
complete.
This means that if there is a code that can be shown to implement a given specification, then it will be derivable from the specification via the calculus.
A practical framework for demand-driven interprocedural data flow analysis
Authors: Duesterwald Evelyn , Gupta Rajiv , Soffa Mary Lou
Published: October 2002

The high cost and growing importance of interprocedural data flow analysis have led to an increased interest in demand-driven algorithms. In this article, we present a general framework for developing demand-driven interprocedural data flow analyzers and report our experience in evaluating the performance of this approach. A demand for data flow information is modeled as a set of queries. The framework includes a generic demand-driven algorithm that determines the response to query by iteratively applying a system of query propagation rules. The propagation rules yield precise responses for the class of distributive finite data flow problems. We also describe a two-phase framework variation to accurately handle nondistributive problems. A performance evaluation of our demand-driven approach is presented for two data flow problems, namely, reaching-definitions and copy constant propagation. Our experiments show that demand-driven analysis performs well in practice, reducing both time and space requirements when compared with exhaustive analysis.
Equality-based flow analysis versus recursive types
Authors: Palsberg Jens
Published: October 2002

Equality-based control-flow analysis has been studied by Henglein, Bondorf and Jørgensen, DeFouw, Grove, and Chambers, and others. It is faster than the subset-based-0-CFA, but also more approximate. Heintze asserted in 1995 that a program can be safety checked with an equality-based control-flow analysis if and only if it can be typed with recursive types. In this article we falsify Heintze's assertion, and we present a type system equivalent to equality-based control-flow analysis. The new type system contains both recursive types and an unusual notion of subtyping. We have
s
≤
t
if
s
and
t
unfold to the same regular tree, and we have ⊥≤t≤⊤ where
t
is a function type. In particular, there is no nontrivial subtyping between function types.
Graph translation schemes to generate compiler parts
Authors: Sonnenschein Michael
Published: October 2002

Graph translation schemes (GTSs) are a generalization of attribute grammars and of some ideas in Koster's language CDL2 They are specially designed to support a compiler writer in defining parts of the back-end of his compiler, but they can also be useful for the specification of the analysis pass of a compiler. GTSs combine elements of functional and of algorithmic specification techniques to allow iterative attribute evaluation and attributing of program graphs. GTSs consist of only a few syntactical elements. We present operational semantics and discuss improvements in the efficiency of the proposed implementation of GTSs.
A generalized iterative construct and its semantics
Authors: Anson Ed
Published: October 2002

A new programming language construct, called DOupon, subsumes Dijkstra's selective (IF) and iterative (DO) constructs. DOupon has a predicate transformer approximately equivalent in complexity to that for DO. In addition, it simplifies a wide variety of algorithms, in form as well as in discovery and proof. Several theorems are demonstrated that are useful for correctness proofs and for optimization and that are not applicable to DO or IF. The general usefulness of DOupon derives from a separation of the concerns of invariance, through iteration, from those of termination.
Embedding continuations in procedural objects
Authors: Haynes Christopher T. , Friedman Daniel P.
Published: October 2002

Continuations, when available as first-class objects, provide a general control abstraction in programming languages. They liberate the programmer from specific control structures, increasing programming language extensibility. Such continuations may be extended by embedding them in procedural objects. This technique is first used to restore a fluid environment when a continuation object is invoked. We then consider techniques for constraining the power of continuations in the interest of security and efficiency. Domain mechanisms, which create dynamic barriers for enclosing control, are implemented using fluids. Domains are then used to implement an unwind-protect facility in the presence of first-class continuations. Finally, we present two mechanisms, wind-unwind and dynamic-wind, that generalize unwind-protect.
Identifying loops in almost linear time
Authors: Ramalingam G.
Published: October 2002

Loop identification is an essential step in performing various loop optimizations and transformations. The classical algorithm for identifying loops is Tarjan's interval-finding algorithm, which is restricted to reducible graphs. More recently, serveral people have proposed extensions to Tarjan's algortihm to deal with irreducible graphs. Havlak presents one such extension, which constructs a loop-nesting forest for an arbitrary flow graph. We show that the running time of this algorithm is quadratic in the worst-case, and not almost linear as claimed. We then show how to modify the algorithm to make it run in almost linear time. We next consider the quadratic algorithm presented by Sreedhar et al. which constructs a loop-nesting forest different from the one constructed by Havlak algorithm. We show that this algorithm too can be adapted to run in almost linear time. We finally consider an algorithm due to Steensgaard, which constructs yet antoher loop-nesting forest. We show how this algorithm can be made more efficient by borrowing ideas from the other algorithms discussed earlier.
Compact Encodings of List Structure
Authors: Bobrow Daniel G. , Clark Douglas W.
Published: October 2002

List structures provide a general mechanism for representing easily changed structured data, but can introduce inefficiencies in the use of space when fields of uniform size are used to contain pointers to data and to link the structure. Empirically determined regularity can be exploited to provide more space-efficient encodings without losing the flexibility inherent in list structures. The basic scheme is to provide compact pointer fields big enough to accommodate most values that occur in them and to provide “escape” mechanisms for exceptional cases. Several examples of encoding designs are presented and evaluated, including two designs currently used in Lisp machines. Alternative escape mechanisms are described, and various questions of cost and implementation are discussed. In order to extrapolate our results to larger systems than those measured, we propose a model for the generation of list pointers and we test the model against data from two programs. We show that according to our model, list structures with compact
cdr
fields will, as address space grows, continue to be compacted well with a fixed-width small field. Our conclusion is that with a microcodable processor, about a factor of two gain in space efficiency for list structure can be had for little or no cost in processing time.
An Axiomatic Approach to Information Flow in Programs
Authors: Andrews Gregory R. , Reitman Richard P.
Published: October 2002

A new approach to information flow in sequential and parallel programs is presented. Flow proof rules that capture the information flow semantics of a variety of statements are given and used to construct program flow proofs. The method is illustrated by examples. The applications of flow proofs to certifying information flow policies and to solving the confinement problem are considered. It is also shown that flow rules and correctness rules can be combined to form an even more powerful proof system.
Chaining Span-Dependent Jump Instructions
Authors: Leverett Bruce W. , Szymanski Thomas G.
Published: October 2002

The assembled length of a span-dependent jump instruction depends on the distance between the instruction and its target. Such instructions are found on many computers and typically have two forms, long and short. We consider the problem of minimizing object program length for such machines by chaining together jumps with the same target. Although the problem is NP-complete in its most general form, several mildly restricted forms of the problem exist that are of practical importance and have efficient solutions.
Type elaboration and subtype completion for Java bytecode
Authors: Knoblock Todd B. , Rehof Jakob
Published: October 2002

Java source code is strongly typed, but the translation from Java source to bytecode omits much of the type information originally contained within methods. Type elaboration is a technique for reconstructing strongly typed programs from incompletely typed bytecode by inferring types for local variables. There are situations where, technically, there are not enough types in the original type hierarchy to type a bytecode program. Subtype completion is a technique for adding necessary types to an arbitrary type hierarchy to make type elaboration possible for all verifiable Java bytecode. Type elaboration with subtype completion has been implemented as part of the Marmot Java compiler.
Program abstraction and instantiation
Authors: Dershowitz Nachum
Published: October 2002

Our goal is to develop formal methods for abstracting a given set of programs into a program schema
and for instantiating a given schema to satisfy concrete specifications. Abstraction and instantiation
are two important phases in software development which allow programmers to apply knowledge
learned in the solutions of past problems when faced with new situations. For example, from two
programs using a linear (or binary) search technique, an abstract schema can be derived that embodies
the shared idea and that can be instantiated to solve similar new problems. Along similar lines, the
development and application of program transformations are considered.

We suggest the formulation of analogies as a basic tool in program abstraction. An analogy is first
sought between the specifications of the given programs; this yields an abstract specification that
may be instantiated to any of the given concrete specifications. The analogy is then used as a basis
for transforming the existing programs into an abstract schema that represents the embedded
technique, with the invariant assertions and correctness proofs of the given programs helping to
verify and complete the analogy. A given concrete specification of a new problem may then be
compared with the abstract specification of the schema to suggest an instantiation of the schema
that yields a correct program.
Abstract interaction tools: a language for user interface management systems
Authors: Van Den Bos Jan
Published: October 2002

A language model is presented for the specification of User Interface Management Systems. The model, called the Abstract Interaction Tool (AIT) model, offers a tree-like hierarchy of interaction objects. Each object represents a subtree and can be considered as an abstract input device containing a syntax-like specification of the required input pattern. The hierarchy of specifications amounts to a system of syntactical productions with multiple control. Terminal nodes of the AIT tree represent the interface to the physical interaction devices. The AIT model features hierarchical output resource management. At the higher, more abstract, level the input-output is loosely coupled. At lower levels the coupling becomes increasingly tight. At the upper levels, AITs model the functions (what) required by the user, whereas at the lower levels the way to accomplish them (how) is stressed. The AIT model has modes for multithread and multiple-device user interaction. There are facilities for context-dependent prompting, echoing, feedback, error correction, and expertise levels. A special section in the AIT provides for links to application modules. As a model for general interactive systems, AITs can be applied to graphics, process control, dialogue, and real-time systems. AITs can also be used to define controlled production rules in knowledge-based systems. In addition the model can provide tools for the software engineering phases specification and prototyping.
An Ada package for dimensional analysis
Authors: Hilfinger Paul N.
Published: October 2002

This paper illustrates the use of Ada's abstraction facilities—notably, operator overloading and type parameterization—to define an oft-requested feature: a way to attribute units of measure to variables and values. The definition given allows the programmer to specify units of measure for variables, constants, and parameters; checks uses of these entities for dimensional consistency; allows arithmetic between them, where legal; and provides scale conversions between commensurate units. It is not constrained to a particular system of measurement (such as the metric or English systems). Although the definition is in standard Ada and requires nothing special of the compiler, certain reasonable design choices in the compiler, discussed here at some length, can make its implementation particularly efficient.
A solution to a problem with Morel and Renvoise's “Global optimization by suppression of partial redundancies”
Authors: Drechsler Karl-Heinz , Stadel Manfred P.
Published: October 2002

Morel and Renvoise have previously described a method for global optimization and code motion by suppression of partial redundancies [l]. Morel and Renvoise use data flow analysis to determine expression computations that should be inserted at the end of certain basic blocks and to determine redundant computations that can be eliminated. The execution of these techniques results in the movement of loop invariant expressions out of the loop. In addition to [l] Morel and Renvoise's techniques can also be applied to subexpressions of larger expressions. Then, however, in certain special cases these optimization techniques move expressions to places where some of its subexpressions are neither available nor moved together with the expression. In this paper we present a modification of Morel and Renvoise's algorithm that avoids the above described situations.
Error repair with validation in LR-based parsing
Authors: Kim Ik-Soon , Choe Kwang-Moo
Published: October 2002

When the compiler encounters an error symbol in an erroneous input, the local error-repair method repairs the input by either inserting a repair string before the error symbol or deleting the error symbol. Although the extended FMQ of Fischer et al. and the method of McKenzie et al. report the improved quality of diagnostic messages, they suffer from redundant parse stack configurations.This article proposes an efficient LR error-recovery method, with validation-removing repairs that give the same validation result as a previously considered, lower-cost repair. Moreover, its execution speed is proportional to the length of the stack configuration. The algorithm is implemented on a Bison, GNU LALR(1), parser generating system. Experimental results are presented.
Parallel execution of prolog programs
Authors: Gupta Gopal , Pontelli Enrico , Ali Khayri A.M. , Carlsson Mats , Hermenegildo Manuel V.
Published: October 2002

Since the early days of logic programming, researchers in the field realized the potential for exploitation of parallelism present in the execution of logic programs. Their high-level nature, the presence of nondeterminism, and their referential transparency, among other characteristics, make logic programs interesting candidates for obtaining speedups through parallel execution. At the same time, the fact that the typical applications of logic programming frequently involve irregular computations, make heavy use of dynamic data structures with logical variables, and involve search and speculation, makes the techniques used in the corresponding parallelizing compilers and run-time systems potentially interesting even outside the field. The objective of this article is to provide a comprehensive survey of the issues arising in parallel execution of logic programming languages along with the most relevant approaches explored to date in the field. Focus is mostly given to the challenges emerging from the parallel execution of Prolog programs. The article describes the major techniques used for shared memory implementation of Or-parallelism, And-parallelism, and combinations of the two. We also explore some related issues, such as memory management, compile-time analysis, and execution visualization.
Automatic verification of finite-state concurrent systems using temporal logic specifications
Authors: Clarke E. M. , Emerson E. A. , Sistla A. P.
Published: October 2002

We give an efficient procedure for verifying that a finite-state concurrent system meets a specification expressed in a (propositional, branching-time) temporal logic. Our algorithm has complexity linear in both the size of the specification and the size of the global state graph for the concurrent system. We also show how this approach can be adapted to handle fairness. We argue that our technique can provide a practical alternative to manual proof construction or use of a mechanical theorem prover for verifying many finite-state concurrent systems. Experimental results show that state machines with several hundred states can be checked in a matter of seconds.
Emotion & design
Authors: Norman Don
Published: October 2002

The following is a preview of Don Norman's forthcoming book, which has a working title of Emotion and Design.
Efficient simulation of a tandem Jackson network
Authors: Kroese Dirk P. , Nicola Victor F.
Published: October 2002

The two-node tandem Jackson network serves as a convenient reference model for the analysis and testing of different methodologies and techniques in rare event simulation. In this paper we consider a new approach to efficiently estimate the probability that the content of the second buffer exceeds some high level
L
before it becomes empty, starting from a given state. The approach is based on a Markov additive process representation of the buffer processes, leading to an exponential change of measure to be used in an importance sampling procedure. Unlike changes of measures proposed and studied in recent literature, the one derived here is a function of the content of the first buffer. We prove that when the first buffer is finite, this method yields asymptotically efficient simulation for any set of arrival and service rates. In fact, the relative error is bounded independent of the level
L
; a new result which is not established for any other known method. When the first buffer is infinite, we propose a natural extension of the exponential change of measure for the finite buffer case. In this case, the relative error is shown to be bounded (independent of
L
) only when the second server is the bottleneck; a result which is known to hold for some other methods derived through large deviations analysis. When the first server is the bottleneck, experimental results using our method seem to suggest that the relative error is bounded linearly in
L
.
Fast bilateral filtering for the display of high-dynamic-range images
Authors: Durand Frédo , Dorsey Julie
Published: October 2002

We present a new technique for the display of high-dynamic-range images, which reduces the contrast while preserving detail. It is based on a two-scale decomposition of the image into a base layer, encoding large-scale variations, and a detail layer. Only the base layer has its contrast reduced, thereby preserving detail. The base layer is obtained using an edge-preserving filter called the
bilateral filter.
This is a non-linear filter, where the weight of each pixel is computed using a Gaussian in the spatial domain multiplied by an influence function in the intensity domain that decreases the weight of pixels with large intensity differences. We express bilateral filtering in the framework of robust statistics and show how it relates to anisotropic diffusion. We then accelerate bilateral filtering by using a piecewise-linear approximation in the intensity domain and appropriate subsampling. This results in a speed-up of two orders of magnitude. The method is fast and requires no parameter setting.
Transferring color to greyscale images
Authors: Welsh Tomihisa , Ashikhmin Michael , Mueller Klaus
Published: October 2002

We introduce a general technique for "colorizing" greyscale images by transferring color between a source, color image and a destination, greyscale image. Although the general problem of adding chromatic values to a greyscale image has no exact, objective solution, the current approach attempts to provide a method to help minimize the amount of human labor required for this task. Rather than choosing RGB colors from a palette to color individual components, we transfer the entire color "mood" of the source to the target image by matching luminance and texture information between the images. We choose to transfer only chromatic information and retain the original luminance values of the target image. Further, the procedure is enhanced by allowing the user to match areas of the two images with rectangular swatches. We show that this simple technique can be successfully applied to a variety of images and video, provided that texture and luminance are sufficiently distinct. The images generated demonstrate the potential and utility of our technique in a diverse set of application domains.
Interactive motion generation from examples
Authors: Arikan Okan , Forsyth D. A.
Published: October 2002

There are many applications that demand large quantities of natural looking motion. It is difficult to synthesize motion that looks natural, particularly when it is people who must move. In this paper, we present a framework that generates human motions by cutting and pasting motion capture data. Selecting a collection of clips that yields an acceptable motion is a combinatorial problem that we manage as a randomized search of a hierarchy of graphs. This approach can generate motion sequences that satisfy a variety of constraints automatically. The motions are smooth and human-looking. They are generated in real time so that we can author complex motions interactively. The algorithm generates multiple motions that satisfy a given set of constraints, allowing a variety of choices for the animator. It can easily synthesize multiple motions that interact with each other using constraints. This framework allows the extensive re-use of motion capture data for new purposes.
Interactive control of avatars animated with human motion data
Authors: Lee Jehee , Chai Jinxiang , Reitsma Paul S. A. , Hodgins Jessica K. , Pollard Nancy S.
Published: October 2002

Real-time control of three-dimensional avatars is an important problem in the context of computer games and virtual environments. Avatar animation and control is difficult, however, because a large repertoire of avatar behaviors must be made available, and the user must be able to select from this set of behaviors, possibly with a low-dimensional input device. One appealing approach to obtaining a rich set of avatar behaviors is to collect an extended, unlabeled sequence of motion data appropriate to the application. In this paper, we show that such a motion database can be preprocessed for flexibility in behavior and efficient search and exploited for real-time avatar control. Flexibility is created by identifying plausible transitions between motion segments, and efficient search through the resulting graph structure is obtained through clustering. Three interface techniques are demonstrated for controlling avatar motion using this data structure: the user selects from a set of available choices, sketches a path through an environment, or acts out a desired motion in front of a video camera. We demonstrate the flexibility of the approach through four different applications and compare the avatar motion to directly recorded human motion.
Stable but responsive cloth
Authors: Choi Kwang-Jin , Ko Hyeong-Seok
Published: October 2002

We present a semi-implicit cloth simulation technique that is very stable yet also responsive. The stability of the technique allows the use of a large fixed time step when simulating all types of fabrics and character motions. The animations generated using this technique are strikingly realistic. Wrinkles form and disappear in a quite natural way, which is the feature that most distinguishes textile fabrics from other sheet materials. Significant improvements in both the stability and realism were made possible by overcoming the
post-buckling instability
as well as the numerical instability. The instability caused by buckling arises from a structural instability and therefore cannot be avoided by simply employing a semi-implicit method. Addition of a damping force may help to avoid instabilities; however, it can significantly degrade the realism of the cloth motion. The method presented here uses a particle-based physical model to handle the instability in the post-buckling response without introducing any fictitious damping.
Painting and rendering textures on unparameterized models
Authors: DeBry David (grue) , Gibbs Jonathan , Petty Devorah DeLeon , Robins Nate
Published: October 2002

This paper presents a solution for texture mapping unparameterized models. The quality of a texture on a model is often limited by the model's parameterization into a 2D texture space. For models with complex topologies or complex distributions of structural detail, finding this parameterization can be very difficult and usually must be performed manually through a slow iterative process between the modeler and texture painter. This is especially true of models which carry no natural parameterizations, such as subdivision surfaces or models acquired from 3D scanners. Instead, we remove the 2D parameterization and store the texture in 3D space as a sparse, adaptive octree. Because no parameterization is necessary, textures can be painted on any surface that can be rendered. No mappings between disparate topologies are used, so texture artifacts such as seams and stretching do not exist. Because this method is adaptive, detail is created in the map only where required by the texture painter, conserving memory usage.
Understanding human reactivites and relationships
Authors: Shneiderman Ben
Published: October 2002

"These notes reveal the intimate tie in Leonardo's thinking between… phenomena in general and the need to put such information to practical use."--- A. Richard Turner,
Inventing Leonardo
, 1994, p 184
Automatic derivation of compiler machine descriptions
Authors: Collberg Christian S.
Published: October 2002

We describe a method designed to significantly reduce the effort required to retarget a compiler to a new architecture, while at the same time producing fast and effective compilers. The basic idea is to use the native C compiler at compiler construction time to discover architectural features of the new architecture. From this information a formal machine description is produced. Given this machine description, a native code-generator can be generated by a back-end generator such as BEG or burg. A prototype automatic Architecture Discovery Tool (called ADT) has been implemented. This tool is completely automatic and requires minimal input from the user. Given the Internet address of the target machine and the command-lines by which the native C compiler, assembler, and linker are invoked, ADT will generate a BEG machine specification containing the register set, addressing modes, instruction set, and instruction timings for the architecture. The current version of ADT is general enough to produce machine descriptions for the integer instruction sets of common RISC and CISC architectures such as the Sun SPARC, Digital Alpha, MIPS, DEC VAX, and Intel x86.
Cultural differences in the online behavior of consumers
Authors: Chau Patrick Y. K. , Cole Melissa , Massey Anne P. , Montoya-Weiss Mitzi , O'Keefe Robert M.
Published: October 2002

Understanding how different cultures use the Net---as well as perceive the same Web sites---can translate to truly global e-commerce.
Neural methods for dynamic branch prediction
Authors: Jiménez Daniel A. , Lin Calvin
Published: October 2002

This article presents a new and highly accurate method for branch prediction. The key idea is to use one of the simplest possible neural methods, the perceptron, as an alternative to the commonly used two-bit counters. The source of our predictor's accuracy is its ability to use long history lengths, because the hardware resources for our method scale linearly, rather than exponentially, with the history length. We describe two versions of perceptron predictors, and we evaluate these predictors with respect to five well-known predictors. We show that for a 4 KB hardware budget, a simple version of our method that uses a global history achieves a misprediction rate of 4.6% on the SPEC 2000 integer benchmarks, an improvement of 26% over
gshare
. We also introduce a global/local version of our predictor that is 14% more accurate than the McFarling-style hybrid predictor of the Alpha 21264. We show that for hardware budgets of up to 256 KB, this global/local perceptron predictor is more accurate than Evers' multicomponent predictor, so we conclude that ours is the most accurate dynamic predictor currently available. To explore the feasibility of our ideas, we provide a circuit-level design of the perceptron predictor and describe techniques that allow our complex predictor to operate quickly. Finally, we show how the relatively complex perceptron predictor can be used in modern CPUs by having it override a simpler, quicker Smith predictor, providing IPC improvements of 15.8% over
gshare
and 5.7% over the McFarling hybrid predictor.
Smart recompilation
Authors: Tichy Walter F.
Published: October 2002

With current compiler technology, changing a single line in a large software system may trigger massive recompilations. If the change occurs in a file with shared declarations, all compilation units depending upon that file must be recompiled to assure consistency. However, many of those recompilations may be redundant, because the change may affect only a small fraction of the overall system.

Smart recompilation is a method for reducing the set of modules that must be recompiled after a change. The method determines whether recompilation is necessary by isolating the differences among program modules and analyzing the effect of changes. The method is applicable to languages with and without overloading. A prototype demonstrates that the method is efficient and can be added with modest effort to existing compilers.
Uniform self-stabilizing rings
Authors: Burns J. E. , Pachl Jan K.
Published: October 2002

A
self-stabilizing system
has the property that, no matter how it is perturbed, it eventually returns to a legitimate configuration. Dijkstra originally introduced the self-stabilization problem and gave several solutions for a ring of processors in his 1974
Communications of the ACM
paper. His solutions use a distinguished processor in the ring, which effectively acts as a controlling element to drive the system toward stability. Dijkstra has observed that a distinguished processor is essential if the number of processors in the ring is composite. We show, by presenting a protocol and proving its correctness, that there is a self-stabilizing system with no distinguished processor if the size of the ring is prime. The basic protocol uses Θ (
n
2
) states in each processor when
n
is the size of the ring. We modify the basic protocol to obtain one that uses Θ (
n
2
/ln
n
) states.
On Lamport's interprocessor communication model
Authors: Anger Frank D.
Published: October 2002

Leslie Lamport presented a set of axioms in 1979 that capture the essential properties of the temporal relationships between complex and perhaps unspecified activities within any system, and proceeded to use this axiom system to prove the correctness of sophisticated algorithms for reliable communication and mutual exclusion in systems without shared memory. As a step toward a more complete metatheory of Lamport's axiom system, this paper determines the extent to which that system differs from systems based on “atomic,” or indivisible, actions. Theorem 1 shows that only very weak conditions need be satisfied in addition to the given axioms to guarantee the existence of an atomic “model,” while Proposition 1 gives sufficient conditions under which any such model must be a “faithful” representation. Finally, Theorem 2 restates a result of Lamport showing exactly when a system can be thought of as made up of a set of atomic events that can be totally ordered temporally. A new constructive proof is offered for this result.
Functional computations in logic programs
Authors: Debray Saumya K. , Warren David S.
Published: October 2002

Although the ability to simulate nondeterminism and to compute multiple solutions for a single query is a powerful and attractive feature of logic programming languages, it is expensive in both time and space. Since programs in such languages are very often functional, that is, they do not produce more than one distinct solution for a single input, this overhead is especially undesirable. This paper describes how programs may be analyzed statically to determine which literals and predicates are functional, and how the program may then be optimized using this information. Our notion of “functionality” subsumes the notion of “determinacy” that has been considered by various researchers. Our algorithm is less reliant on language features such as the cut, and thus extends more easily to parallel execution strategies, than others that have been proposed.
Some comments on “A solution to a problem with Morel and Renvoise's 'Global optimization by suppression of partial redundancies'”
Authors: Sorkin Arthur
Published: October 2002

Abstract: Drechsler and Stadel presented a solution to a problem with Morel and Renvoise's “Global Optimization by Suppression of Partial Redundancies.” We cite some earlier generalizations of Morel and Renvoise's algorithm that solve the same problem, and we comment on their applicability.
On the productivity of recursive list definitions
Authors: Sijtsma Ben A.
Published: October 2002

Several related notions of the productivity are presented for functional languages with lazy evaluation. The notion of productivity captures the idea of computability, of progress of infinite-list programs. If an infinite-list program is
productive
, then every element of the list can be computed in finite “time.” These notions are used to study recursive list definitions, that is, lists defined by
l
where
l
=
fl
. Sufficient conditions are given in terms of the function
f
that either guarantee the productivity of the list or its unproductivity. Furthermore, a calculus is developed that can be used in verifying that lists defined by
l
where
l
=
f I
are productive. The power and the usefulness of our theory are demonstrated by several nontrivial examples. Several observations are given in conclusion.
A denotational semantics for Prolog
Authors: Nicholson Tim , Foo Norman
Published: October 2002

A denotational semantics is presented for the language Pro.og. Metapredicates are not considered. Conventional control sequencing is assumed for Prolog's execution. The semantics is nonstandard, and goal continuations are used to explicate the sequencing.
A distributed deadlock detection algorithm for CSP-like communication
Authors: Huang S. -T.
Published: October 2002

An algorithm for detecting deadlocks in distributed systems with CSP-like communication is proposed. Unlike previous work, the proposed algorithm avoids
periodically
sending deadlock-detecting messages by the processes and requires no local storage for the processes with size predetermined by the number of processes in the system. The algorithm is proven to have the following properties: (0) it never detects
false
deadlocks; (1) it has only one process in a
knot
report the deadlock; and (2) it detects every
true
deadlock in finite time.
Ionic Mechanisms of Acquired QT Prolongation and Torsades de Pointes in Rabbits With Chronic Complete Atrioventricular Block
Authors: Tsuji Yukiomi , Opthof Tobias , Yasui Kenji , Inden Yasuya , Takemura Haruki , Niwa Noriko , Lu Zhibo , Lee Jong-Kook , Honjo Haruo , Kamiya Kaichiro , Kodama Itsuo
Published: October 2002

Background—

The ionic basis of acquired QT prolongation and torsade de pointes (TdP) unrelated to drugs is not fully understood.

Methods and Results—

We created a rabbit model with chronic complete atrioventricular block (AVB) (n=34), which showed prominent QT prolongation (by 120%), high incidence of spontaneous TdP (71%), and cardiac hypertrophy. Patch-clamp experiments were performed in left ventricular myocytes from 9 rabbits (8 with TdP, 1 without TdP) at ≈21 days of AVB and from 8 sham-operated controls with sinus rhythm. Action potential duration was prolonged in AVB myocytes compared with control (+61% at 0.5 Hz, +21% at 3 Hz). Both rapidly and slowly activating components of the delayed rectifier K
+
current (
I
Kr
and
I
Ks
) in AVB myocytes were significantly smaller than in control by 50% and 55%, respectively. There was no significant difference in Ca
2+
-independent transient outward current (
I
to1
). L-type Ca
2+
current (
I
Ca,L
) in control and AVB myocytes was similar in peak amplitude, but the half voltage for activation was shifted to the negative direction (5.9 mV) in AVB myocytes. Voltage dependence of
I
Ca,L
inactivation was not different in control and AVB myocytes. The inward rectifier K
+
current (
I
K1
) significantly increased in AVB myocytes compared with control.

Conclusions—

In the rabbit, chronic AVB leads to prominent QT prolongation and high incidence of spontaneous TdP. Downregulation of both
I
Kr
and
I
Ks
in association with altered
I
Ca,L
activation kinetics may underlie the arrhythmogenic ventricular remodeling.
Repair of Infarcted Myocardium by Autologous Intracoronary Mononuclear Bone Marrow Cell Transplantation in Humans
Authors: Strauer Bodo E. , Brehm Michael , Zeus Tobias , Köstering Matthias , Hernandez Anna , Sorg Rüdiger V. , Kögler Gesine , Wernet Peter
Published: October 2002

Background—

Experimental data suggest that bone marrow–derived cells may contribute to the healing of myocardial infarction (MI). For this reason, we analyzed 10 patients who were treated by intracoronary transplantation of autologous, mononuclear bone marrow cells (BMCs) in addition to standard therapy after MI.

Methods and Results—

After standard therapy for acute MI, 10 patients were transplanted with autologous mononuclear BMCs via a balloon catheter placed into the infarct-related artery during balloon dilatation (percutaneous transluminal coronary angioplasty). Another 10 patients with acute MI were treated by standard therapy alone. After 3 months of follow-up, the infarct region (determined by left ventriculography) had decreased significantly within the cell therapy group (from 30±13 to 12±7%,
P
=0.005) and was also significantly smaller compared with the standard therapy group (
P
=0.04). Likewise, infarction wall movement velocity increased significantly only in the cell therapy group (from 2.0±1.1 to 4.0±2.6 cm/s,
P
=0.028). Further cardiac examinations (dobutamine stress echocardiography, radionuclide ventriculography, and catheterization of the right heart) were performed for the cell therapy group and showed significant improvement in stroke volume index, left ventricular end-systolic volume and contractility (ratio of systolic pressure and end-systolic volume), and myocardial perfusion of the infarct region.

Conclusions—

These results demonstrate for the first time that selective intracoronary transplantation of autologous, mononuclear BMCs is safe and seems to be effective under clinical conditions. The marked therapeutic effect may be attributed to BMC-associated myocardial regeneration and neovascularization.
Time in Process Philosophy
Authors: Griffin David Ray
Published: October 2002

After contrasting process philosophy's pantemporalism with the two other possibilities — nontemporalism and dualism — I argue the following points:The great negative virtue of J.T.Fraser's version of emergent dualism is that it explicitly brings out the paradoxes that must be faced if pantemporalism is denied. Its great positive virtue,especially when read in conjunction with Grünbaum's position, is that it brings out the fact that time (in the full-fledged sense) requires experience.These two virtues combined suggest the truth of both pantemporalism and panexperientialism, which are mutually implicatory.Pantemporalism, or even the weaker conviction, shared by almost everyone, that time has existed at least since the origin of our universe, conflicts with another belief that initially seems equally well grounded — the belief in an ontological dualism between experiencing and nonexperiencing things. But this latter conviction belongs at best only to soft-core, not hard-core, common sense, so it can be given up without selfcontradiction. Because panexperientialism, like pantemporalism, solves a host of philosophical problems, a pantemporalisticpanexperientialist worldview can be defended in terms of selfconsistency and adequacy to the facts, including the facts of hard-core common sense.
The Peculiar Temporality of Violence: a Source of Perplexity about Social Power
Authors: Thornton Robert
Published: October 2002

Most national myths of origin begin with some transcendent or sacrificial story of violent revolution, warfare or liberation. This is also true of many origin myths of ethnic, tribal or other forms of social identity. This makes it appear that some act of violence is the cause of their coming into being. This paper argues that this is an artefact of the temporal 'peculiarity' of violence. Violent events, it is argued, are essentially unpredictable even when statistically probable. This means that violence is only 'visible' after the fact, and rarely before and that plausible causal models can rarely be constructed in advance. Violence is always seen in retrospect, then, and where it has caused significant death and destruction, it requires that we begin to make sense of what caused it. Unlike other planned or and emotionally charged social interactions (such as eating, sexuality, ritual) acts of violence interrupt (disrupt, breach, rupture, break, etc.) and terminate parts or all of previous social relations. Since the cause of violence can only be assigned retrospectively, this means that we must (re-)construct the past in a way that allows us to make sense of it. Where some violent event is followed by the eventual emergence of a new identity, the new identity is often explained as having 'originated' in violence. This implies that violence caused the new social identity in some way, and that it functions as a political instrument. But violence can only create a void, and is chaotic. After violence, we require the (re-)telling of the past in a new way. This makes violence appear at the beginning of narratives of origin, but does not imply that violence caused these identities. Since large scale violence leads cultural loss and to large scale social (re)construction, narratives of identity tend to begin at these moments in time. This account of violence seeks, therefore, to undermine the notion that violence is an efficient or final cause of social forms.