bluuebunny/crossref_metadata_2025 huggingface dataset:
A CaMK cascade activates CRE‐mediated transcription in neurons of Caenorhabditis elegans
Authors: Kimura Yoshishige , Corcoran Ethan E , Eto Koh , Gengyo‐Ando Keiko , Muramatsu Masa‐aki , Kobayashi Ryoji , Freedman Jonathan H , Mitani Shohei , Hagiwara Masatoshi , Means Anthony R , Tokumitsu Hiroshi
Published: October 2002

Calcium (Ca2+) signals regulate a diverse set of cellular responses, from proliferation to muscular contraction and neuro‐endocrine secretion. The ubiquitous Ca2+ sensor, calmodulin (CaM), translates changes in local intracellular Ca2+ concentrations into changes in enzyme activities. Among its targets, the Ca2+/CaM‐dependent protein kinases I and IV (CaMKs) are capable of transducing intraneuronal signals, and these kinases are implicated in neuronal gene regulation that mediates synaptic plasticity in mammals. Recently, the cyclic AMP response element binding protein (CREB) has been proposed as a target for a CaMK cascade involving not only CaMKI or CaMKIV, but also an upstream kinase kinase that is also CaM regulated (CaMKK). Here, we report that all components of this pathway are coexpressed in head neurons of Caenorhabditis elegans. Utilizing a transgenic approach to visualize CREB‐dependent transcription in vivo, we show that this CaMK cascade regulates CRE‐mediated transcription in a subset of head neurons in living nematodes.
Comparative Analysis of Multiple Genome-Scale Data Sets
Authors: Werner-Washburne Margaret , Wylie Brian , Boyack Kevin , Fuge Edwina , Galbraith Judith , Weber Jose , Davidson George
Published: October 2002

The ongoing analyses of published genome-scale data sets is evidence that different approaches are required to completely mine this data. We report the use of novel tools for both visualization and data set comparison to analyze yeast gene-expression (cell cycle and exit from stationary phase/G0) and protein-interaction studies. This analysis led to new insights about each data set. For example, G1-regulated genes are not co-regulated during exit from stationary phase, indicating that the cells are not synchronized. The tight clustering of other genes during exit from stationary-phase data set further indicates the physiological responses during G0exit are separable from cell-cycle events. Comparison of the two data sets showed that ribosomal-protein genes cluster tightly during exit from stationary phase, but are found in three significantly different clusters in the cell-cycle data set. Two protein-interaction data sets were also compared with the gene-expression data. Visual analysis of the complete data sets showed no clear correlation between co-expression of genes and protein interactions, in contrast to published reports examining subsets of the protein-interaction data. Neither two-hybrid study identified a large number of interactions between ribosomal proteins, consistent with recent structural data, indicating that for both data sets, the identification of false-positive interactions may be lower than previously thought.

[Supplemental material is available online athttp://www.genome.org and athttp://biology.unm.edu/biology/maggieww/Public_Html/Visualcomparison.htm, including data sets and download information for VxInsight.]
Mammalian Retroelements
Authors: Deininger Prescott L. , Batzer Mark A.
Published: October 2002

The eukaryotic genome has undergone a series of epidemics of amplification of mobile elements that have resulted in most eukaryotic genomes containing much more of this ‘junk’ DNA than actual coding DNA. The majority of these elements utilize an RNA intermediate and are termed retroelements. Most of these retroelements appear to amplify in evolutionary waves that insert in the genome and then gradually diverge. In humans, almost half of the genome is recognizably derived from retroelements, with the two elements that are currently actively amplifying, L1 and Alu, making up about 25% of the genome and contributing extensively to disease. The mechanisms of this amplification process are beginning to be understood, although there are still more questions than answers. Insertion of new retroelements may directly damage the genome, and the presence of multiple copies of these elements throughout the genome has longer-term influences on recombination events in the genome and more subtle influences on gene expression.
Mechanics of Tether Formation in Liposomes
Authors: Calladine C. R. , Greenwood J. A.
Published: October 2002

It is well-known that a “tether” may be drawn out from a pressurized liposome by means of a suitably applied radial-outward force applied locally to the lipid bilayer. The tether is a narrow, uniform cylindrical tube, which joins the main vesicle in a short “transition region.” A first-order energy analysis establishes the broad relationship between the force F needed to draw the tether, the radius R0 of the tether, the bending-stiffness constant B for the lipid bilayer and the membrane tension T in the pressurized liposome. The aim of the present paper is to study in detail the “transition region” between the tether and the main vesicle, by means of a careful application of the engineering theory of axisymmetric shell structures. It turns out that the well-known textbook “thin-shell” theory is inadequate for this purpose, because the tether is evidently an example of a thick-walled shell; and a novel ingredient of the present study is the introduction of elastic constitutive relations that are appropriate to the thick-shell situation. The governing equations are set up in dimensionless form, and are solved by means of a “shooting” technique, starting with a single disposable parameter at a point on the meridian in the tether, which can be adjusted until the boundary conditions at the far “equator” of the main vessel are satisfied. It turns out that the “transition region” between the tether and the main vessel is well characterized by only a few parameters, while the tether and main vessel themselves are described by very simple equations. Introduction of the thick-shell constitutive relation makes little difference to the conformation of, and stress-resultants in, the main vessel; but it makes a great deal of difference in the tether itself. Indeed, a kind of phase-change appears to take place in the “transition region” between these two zones of the liposome.
Linking the sounds of dolphins to their locations and behavior using video and multichannel acoustic recordings
Authors: Thomas Rebecca E. , Fristrup Kurt M. , Tyack Peter L.
Published: October 2002

It is difficult to attribute underwater animal sounds to the individuals producing them. This paper presents a system developed to solve this problem for dolphins by linking acoustic locations of the sounds of captive bottlenose dolphins with an overhead video image. A time-delay beamforming algorithm localized dolphin sounds obtained from an array of hydrophones dispersed around a lagoon. The localized positions of vocalizing dolphins were projected onto video images. The performance of the system was measured for artificial calibration signals as well as for dolphin sounds. The performance of the system for calibration signals was analyzed in terms of acoustic localization error, video projection error, and combined acoustic localization and video error. The 95% confidence bounds for these were 1.5, 2.1, and 2.1 m, respectively. Performance of the system was analyzed for three types of dolphin sounds: echolocation clicks, whistles, and burst-pulsed sounds. The mean errors for these were 0.8, 1.3, and 1.3 m, respectively. The 95% confidence bound for all vocalizations was 2.8 m, roughly the length of an adult bottlenose dolphin. This system represents a significant advance for studying the function of vocalizations of marine animals in relation to their context, as the sounds can be identified to the vocalizing dolphin and linked to its concurrent behavior.
Collecting interpretations of expressions
Authors: Hudak Paul , Young Jonathan
Published: October 2002

A
collecting interpretation of expressions
is an interpretation of a program that allows one to answer questions of the sort: “What are all possible values to which an expression might evaluate during program execution?” Answering such questions in a denotational framework is akin to traditional data flow analysis and, when used in the context of abstract interpretation, allows one to infer properties that approximate the run-time behavior of expression evaluation.

Exact collecting interpretations of expressions are developed for three abstract functional languages: a strict first-order language, a nonstrict first-order language, and a nonstrict higher order language (the full untyped lambda calculus with constants). It is argued that the method is simple (in particular, no powerdomains are needed), Natural (it captures the intuitive operational behavior of a cache), yet more expressive than existing methods (it is the first exact collecting interpretation for either nonstrict higher order languages). Correctness of the interpretations with respect to the standard semantics is shown via a generalization of the notion of strictness. It is further shown how to form abstractions of these exact interpretations, using as an example a collecting strictness analysis which yields compile-time information not previously captured by conventional strictness analyses.
Efficient construction of LR(
k
) states and tables
Authors: Anicona M. , Dodero G. , Gianuzzi V. , Morgavi M.
Published: October 2002

A new method for building LR(
k
) states and parsing tables is presented. The method aims at giving a feasible construction of a collection of LR(
k
) parsing tables, especially when
k
> 1. for nontrivial grammars. To this purpose, the algorithm first attempts to build a set of
normal states
for the given grammar, each one associated to a single parsing action in {
accept, reduce, shift
}. When such an action cannot be uniquely determined, that is, when up to
k
input symbols have to be examined (inadequacy), further states, belonging to a new type, called
look-ahead
states, are computed. The action associated with inadequate states is a new parsing action,
look
. States are built without actual computation of the FIRST

k

and EFF

k

functions; that is, nonterminals are kept in the context string of items composing each state, and their expansion to terminals is deferred until indispensable to solve inadequacy. The aforementioned method is illustrated; then the canonical collection of states and the canonical tables are compared with those obtained from the proposed method. A sufficient condition is stated, by which the size of parsing tables, obtained by applying this new method, is smaller than that of canonical tables. Experimental results show that such a condition is verified by the grammars of several programming languagues and that significant speed is gained by avoiding the computation of the FIRST

k

function.
The derivation of distributed termination detection algorithms from garbage collection schemes
Authors: Tel Gerard , Mattern Friedemann
Published: October 2002

It is shown that the termination detection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the termination detection problem are obtained by applying transformations to garbage collection algorithms. The transformation can be applied to collectors of the “mark-and-sweep” type as well as to reference-counting protocol of Lermen and Maurer, the weighted-reference-counting protocol, the local-reference-counting protocol, and Ben-Ari's mark-and-sweep collector into termination detection algorithms. Known termination detection algorithms as well as new variants are obtained.
An alternative solution to a problem on self-stabilization
Authors: Ghosh Sukumar
Published: October 2002

Dijkstra [4, 5] introduced the problem of self-stabilization in distributed systems as an interesting exercise for achieving global convergence through local actions. In [4] he presented three solutions to a specific version of the self-stabilization problem, one of which was proved in [6]. This paper presents an alternative solution of his self-stabilization problem with four-state machines.
Powerlist: a structure for parallel recursion
Authors: Misra Jayadev
Published: October 2002

Many data-parallel algorithms—Fast Fourier Transform, Batcher's sorting schemes, and the prefix-sum—exhibit recursive structure. We propose a data structure called
powerlist
that permits succinct descriptions of such algorithms, highlighting the roles of both parallelism and recursion. Simple algebraic properties of this data structure can be explotied to derive properties of these algorithms and to establish equivalence of different algorithms that solve the same problem.
Safe
Authors: Aiken Alexander , Williams John H. , Wimmers Edward L.
Published: October 2002

Language designers and implementors have avoided specifying and preserving the meaning of programs that produce errors. This is apparently because being forced to preserve error behavior limits severely the scope of program optimization, even for correct programs. However, error behavior preservation is desirable for debugging, and error behavior must be preserved in any language that permits user-generated errors (i.e., exceptions).

This article presents a technique for expressing general program transformations for languages that possess a rich collection of distinguishable error values. This is accomplished by defining a higher-order function called
Safe
, which can be used to annotate those portions of a program that are guaranteed not to produce errors. It is shown that this facilitates the expression of very general program transformations, effectively giving program transformations in a language with many error values the same power and generality as program transformations in a language with only a single error value.

Using the semantic properties of
Safe
, it is possible to provide some useful sufficient conditions for establishing the correctness of transformations in the presence of errors. In particular, a Substitutability theorem is proven, which can be used to justify “in-context” optimizations: transformations that alter the meanings of subexpressions without changing the meaning of the whole program. Finally, the effectiveness of the technique is demonstrated by some examples of its use in an optimizing compiler.
Covariance and contravariance
Authors: Castagna Giuseppe
Published: October 2002

In type-theoretic research on object-oriented programming, the issue of “covariance versus contravariance” is a topic of continuing debate. In this short note we argue that covariance and contravariance appropriately characterize two distinct and independent mechanisms. The so-called contravariance rule correctly captures thesubtypingrelation (that relation which establishes which sets of functions can replace another given set inevery context). A covariant relation, instead, characterizes thespecializationof code (i.e., the definition of new code which replaces old definitionsin some particular cases). Therefore, covariance and contravariance are not opposing views, but distinct concepts that each have their place in object-oriented systems. Both can (and should) be integrated in a type-safe manner in object-oriented languages. We also show that the independence of the two mechanisms is not characteristic of a particular model but is valid in general, since covariant specialization is present in record-based models, although it is hidden by a deficiency of all existing calculi that realize this model. As an aside, we show that the λ&-calculus can be taken as the basic calculus for both an overloading-based and a record-based model. Using this approach, one not only obtains a more uniform vision of object-oriented type theories, but in the case of the record-based approach, one also gains multiple dispatching, a feature that existing record-based models do not capture
Parsing and compiling using Prolog
Authors: Cohen Jacques , Hickey Timothy J.
Published: October 2002

This paper presents the material needed for exposing the reader to the advantages of using Prolog as a language for describing succinctly most of the algorithms needed in prototyping and implementing compilers or producing tools that facilitate this task. The available published material on the subject describes one particular approach in implementing compilers using Prolog. It consists of coupling actions to recursive descent parsers to produce syntax-trees which are subsequently utilized in guiding the generation of assembly language code. Although this remains a worthwhile approach, there is a host of possibilities for Prolog usage in compiler construction. The primary aim of this paper is to demonstrate the use of Prolog in parsing and compiling. A second, but equally important, goal of this paper is to show that Prolog is a labor-saving tool in prototyping and implementing many non-numerical algorithms which arise in compiling, and whose description using Prolog is not available in the literature. The paper discusses the use of unification and nondeterminism in compiler writing as well as means to bypass these (costly) features when they are deemed unnecessary. Topics covered include bottom-up and top-down parsers, syntax-directed translation, grammar properties, parser generation, code generation, and optimizations. Newly proposed features that are useful in compiler construction are also discussed. A knowledge of Prolog is assumed.
Total correctness by local improvement in the transformation of functional programs
Authors: Sands David
Published: October 2002

The goal of program transformation is to improve efficiency while preserving meaning. One of the best-known transformation techniques is Burstall and Darlington's unfold-fold method. Unfortunately the unfold-fold method itself guarantees neither improvement in efficiency nor total correctness. The correctness problem for unfold-fold is an instance of a strictly more general problem: transformation by locally equivalence-preserving steps does not necessarily preserve (global) equivalence. This article presents a condition for the total correctness of transformations on recursive programs, which, for the first time, deals with higher-order functional languages (both strict and nonstrict) including lazy data structures. The main technical result is an
improvement theorem
which says that if the local transformation steps are guided by certain optimization concerns (a fairly natural condition for a transformation), then correctness of the transformation follows. The improvement theorem makes essential use of a formalized improvement theory; as a rather pleasing corollary it also guarantees that the transformed program is a formal improvement over the original. The theorem has immediate practical consequences: it is a powerful tool for proving the correctness of existing transformation methods for higher-order functional programs, without having to ignore crucial factors such as
memoization
or
folding
, and it yields a simple syntactic method for guiding and constraining the unfold-fold method in the general case so that total correctness (and improvement) is always guaranteed.
Improving data locality with loop transformations
Authors: McKinley Kathryn S. , Carr Steve , Tseng Chau-Wen
Published: October 2002

In the past decade, processor speed has become significantly faster than memory speed. Small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit
data locality
. In the this article, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. The model computes both
temporal
and
spatial
reuse of cache lines to find desirable loop organizations. The cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. To validate our optimization strategy, we implemented our algorithms and ran experiments on a large collection of scientific programs and kernels. Experiments illustrate that for kernels our model and algorithm can select and achieve the best loop structure for a nest. For over 30 complete applications, we executed the original and transformed versions and simulated cache hit rates. We collected statistics about the inherent characteristics of these programs and our ability to improve their data locality. To our knowledge, these studies are the first of such breadth and depth. We found performance improvements were difficult to achieve bacause benchmark programs typically have high hit rates even for small data caches; however, our optimizations significanty improved several programs.
A distributed alternative to finite-state-machine specifications
Authors: Zave Pamela
Published: October 2002

A specification technique, formally equivalent to finite-state machines, is offered as an alternative because it is inherently distributed and more comprehensible. When applied to modules whose complexity is dominated by control, the technique guides the analyst to an effective decomposition of complexity, encourages well-structured error handling, and offers an opportunity for parallel computation. When applied to distributed protocols, the technique provides a unique perspective and facilitates automatic detection of some classes of error. These applications are illustrated by a controller for a distributed telephone system and the full-duplex alternating-bit protocol for data communication. Several schemes are presented for executing the resulting specifications.
Generative communication in Linda
Authors: Gelernter David
Published: October 2002

Generative communication is the basis of a new distributed programming langauge that is intended for systems programming in distributed settings generally and on integrated network computers in particular. It differs from previous interprocess communication models in specifying that messages be added in tuple-structured form to the computation environment, where they exist as named, independent entities until some process chooses to receive them. Generative communication results in a number of distinguishing properties in the new language, Linda, that is built around it. Linda is fully distributed in space and distributed in time; it allows distributed sharing, continuation passing, and structured naming. We discuss these properties and their implications, then give a series of examples. Linda presents novel implementation problems that we discuss in Part II. We are particularly concerned with implementation of the dynamic global name space that the generative communication model requires.
Formal derivation of efficient parallel programs by construction of list homomorphisms
Authors: Hu Zhenjiang , Iwasaki Hideya , Takechi Masato
Published: October 2002

It has been attracting much attention to make use of list homomorphisms in parallel programming because they ideally suit the divide-and-conquer parallel paradigm. However, they have been usually treated rather informally and ad hoc in the development of efficient parallel programs. What is worse is that some interesting functions, e.g., the maximum segment sum problem, are basically not list homomorphisms. In this article, we propose a systematic and formal way for the construction of a list homomorphism for a given problem so that an efficient parallel program is derived. We show, with several well-known but nontrivial problems, how a straightforward, and “obviously” correct, but quite inefficient solution to the problem can be successfully turned into a semantically equivalent “almost list homomorphism.” The derivation is based on two transformations, namely tupling and fusion, which are defined according to the specific recursive structures of list homomorphisms.
Parallelizing nonnumerical code with selective scheduling and software pipelining
Authors: Moon Soo-Mook , Ebcioğlu Kemal
Published: October 2002

Instruction-level parallelism (ILP) in nonnumerical code is regarded as scarce and hard to exploit due to its irregularity. In this article, we introduce a new code-scheduling technique for irregular ILP called “selective scheduling” which can be used as a component for superscalar and VLIW compilers. Selective scheduling can compute a wide set of independent operations acrossallexecution paths based on renaming and forward-substitution and can compute available operations across loop iterations if combined with software pipelining. This scheduling approach has better heuristics for determining the usefulness of moving one operation versus moving another and can successfully find useful code motions without resorting to branch profiling. The compile-time overhead of selective scheduling is low due to its incremental computation technique and its controlled code duplication. We parallelized the SPEC integer benchmarks and five AIX utilities without using branch probabilities. The experiments indicate that a fivefold speedup is achievable on realistic resources with a reasonable overhead in compilation time and code expansion and that a solid speedup increase is also obtainable on machines with fewer resources. These results improve previously known characteristics of irregular ILP.
Static caching for incremental computation
Authors: Liu Yanhong A. , Stoller Scott D. , Teitelbaum Tim
Published: October 2002

A systematic approach is given for deriving incremental programs that exploit caching. The
cache-and-prune
method presented in the article consists of three stages: (I) the original program is extended to cache the results of all its intermediate subcomputations as well as the final result, (II)) the extended program is incrementalized so that computation on a new input can use all intermediate results on an old input, and (III) unused results cached by the extended program and maintained by the incremental program are pruned away, leaving a pruned extended program that caches only useful intermediate results and a pruned incremental program that uses and maintains only useful results. All three stages utilize static analyses and semantics-preserving transformations. Stages I and III are simple, clean, and fully automatable. The overall method has a kind of optimality with respect to the techniques used in Stage II. The method can be applied straightfowardly to provide a systematic approach to program improvement via caching.
Partial evaluation of functional logic programs
Authors: Alpuente María , Falaschi Moreno , Vidal Germán
Published: October 2002

Languages that integrate functional and logic programming with a complete operational semantics are based on narrowing, a unification-based goal-solving mechanism which subsumes the reduction principle of functional languages and the resolution principle of logic languages. In this article, we present a partial evaluation scheme for functional logic languages based on an automatic unfolding algorithm which builds narrowing trees. The method is formalized within the theoretical framework established by Lloyd and Shepherdson for the partial deduction of logic programs, which we have generalized for dealing with functional computations. A generic specialization algorithm is proposed which does not depend on the eager or lazy nature of the narrower being used. To the best of our knowledge, this is the first generic algorithm for the specialization of functional logic programs. We also discuss the relation to work on partial evaluation in functional programming, term-rewriting systems, and logic programming. Finally, we present some experimental results with an implementation of the algorithm which show in practice that the narrowing-driven partial evaluator effectively combines the propagation of partial data structures (by means of logical variables and unification) with better opportunities for optimization (thanks to the functional dimension).
Space/time-efficient scheduling and execution of parallel irregular computations
Authors: Yang Tao , Fu Cong
Published: October 2002

In this article we investigate the trade-off between time and space efficiency in scheduling and executing parallel irregular computations on distributed-memory machines. We employ acyclic task dependence graphs to model irregular parallelism with mixed granularity, and we use direct remote memory access to support fast communication. We propose new scheduling techniques and a run-time active memory management scheme to improve memory utilization while retaining good time efficiency, and we provide a theoretical analysis on correctness and performance. This work is implemented in the context of the RAPID system which uses an inspector/executor approach to parallelize irregular computations at run-ti me. We demostrate the effectiveness of the proposed techniques on several irregular applications such as sparse matrix code and the fast multipole method for particle simulation. Our experimental results on Cray-T3E show that problems large sizes can be solved under limited space capacity, and that the loss of execution efficiency caused by the extra memory management overhead is reasonable.
Cost-optimal code motion
Authors: Hailperin Max
Published: October 2002

We generalize Knoop et al.'s Lazy Code Motion (LCM) algorithm for partial redundancy elimination so that the generalized version also performs strength reduction. Although Knoop et al. have themselves extended LCM to strength reduction with their Lazy Strength Reduction algorithm, our approach differs substantially from theirs and results in a broader class of candidate expressions, stronger safety guarantees, and the elimination of the potential for performance loss instead of gain. Also, our general framework is not limited to traditional strength reduction, but rather can also handle a wide variety of optimizations in which data-flow information enables the replacement of a computation with a less expensive one. As a simple example, computations can be hoisted to points where they are constant foldable. Another example we sketch is the hoisting of polymorphic operations to points where type analysis provides leverage for optimization. Our general approach consists of placing computations so as to minimize their cost, rather than merely their number. So long as the cost differences between flowgraph nodes obey a certain natural constraint, a cost-optimal code motion transformation that does not unnecessarily prolong the lifetime of temporary varibles can be found using techniques completely analogous to LCM. Specifically, the cost differences can be discovered using a wide variety of forward data-flow analyses in a manner which we describe.
On failure of the pruning technique in “Error repair in shift-reduce parsers”
Authors: Bertsch Eberhard , Nederhof Mark-Jan
Published: October 2002

A previous article presented a technique to compute the least-cost
error repair by incrementally generating configurations that result from inserting and deleting tokens a syntactically incorrect input. An additional mechanism to improve the run-time efficiency of this algorithm by pruning some of the configurations was discussed as well. In this communication we show that the pruning mechanism may lead to suboptimal repairs or may block
all
repairs. Certain grammatical errors in a common construct of the Java programming language also lead to the above kind of failure.
Techniques for the translation of MATLAB programs into Fortran 90
Authors: De Rose Luiz , Padua David
Published: October 2002

This article describes the main techiques developed for FALCON's MATLAB-to-Fortran 90 compiler. FALCON is a programming environment for the development of high-performance scientific programs. It combines static and dynamic inference methods to translate MATLAB programs into Fortran 90. The static inference is supported with advanced value propagation techniques and symbolic algorithms for subscript analysis. Experiments show that FALCON's MATLAB translator can generate code that performs more than 1000 times faster than the interpreted version of MATLAB and substantially faster than commercially available MATLAB compilers on one processor of an SGI Power Challenge. Futhermore, in most cases we have tested, the compiler-generated code is as fast as corresponding hand-written programs.
Cache miss equations
Authors: Ghosh Somnath , Martonosi Margaret , Malik Sharad
Published: October 2002

With the ever-widening performance gap between processors and main memory, cache memory, which is used to bridge this gap, is becoming more and more significant. Caches work well for programs that exhibit sufficient locality. Other programs, however, have reference patterns that fail to exploit the cache, thereby suffering heavily from high memory latency. In order to get high cache efficiency and achieve good program performance, efficient memory accessing behavior is necessary. In fact, for many programs, program transformations or source-code changes can radically alter memory access patterns, significantly improving cache performance. Both hand-tuning and compiler optimization techniques are often used to transform codes to improve cache utilization. Unfortunately, cache conflicts are difficult to predict and estimate, precluding effective transformations. Hence, effective transformations require detailed knowledge about the frequency and causes of cache misses in the code. This article describes methods for generating and solving Cache Miss Equations (CMEs) that give a detailed representation of cache behavior, including conflict misses, in loop-oriented scientific code. Implemented within the SUIF compiler framework, our approach extends traditional compiler reuse analysis to generate linear Diophantine equations that summarize each loop's memory behavior. While solving these equations is in general difficult, we show that is also unnecessary, as mathematical techniques for manipulating Diophantine equations allow us to relatively easily compute and/or reduce the number of possible solutions, where each solution corresponds to a potential cache miss. The mathematical precision of CMEs allows us to find true optimal solutions for transformations such as blocking or padding. The generality of CMEs also allows us to reason about interactions between transformations applied in concert. The article also gives examples of their use to determine array padding

and offset amounts that minimize cache misses, and to determine optimal blocking factors for tiled code. Overall, these equations represent an analysis framework that offers the generality and precision needed for detailed compiler optimizations.
Implementation of resilient, atomic data types
Authors: Weihl William , Liskov Barbara
Published: October 2002

A major issue in many applications is how to preserve the consistency of data in the presence of concurrency and hardware failures. We suggest addressing this problem by implementing applications in terms of abstract data types with two properties: Their objects are atomic (they provide serializability and recoverability for activities using them) and resilient (they survive hardware failures with acceptably high probability). We define what it means for abstract data types to be atomic and resilient. We also discuss issues that arise in implementing such types, and describe a particular linguistic mechanism provided in the Argus programming language.
Compiler techniques for code compaction
Authors: Debray Saumya K. , Evans William , Muth Robert , De Sutter Bjorn
Published: October 2002

In recent years there has been an increasing trend toward the incorpor ation of computers into a variety of devices where the amount of memory available is limited. This makes it desirable to try to reduce the size of applications where possible. This article explores the use of compiler techniques to accomplish code compaction to yield smaller executables. The main contribution of this article is to show that careful, aggressive, interprocedural optimization, together with procedural abstraction of repeated code fragments, can yield significantly better reductions in code size than previous approaches, which have generally focused on abstraction of repeated instruction sequences. We also show how “equivalent” code fragments can be detected and factored out using conventional compiler techniques, and without having to resort to purely linear treatments of code sequences as in suffix-tree-based approaches, thereby setting up a framework for code compaction that can be more flexible in its treatment of what code fragments are considered equivalent. Our ideas have been implemented in the form of a binary-rewriting tool that reduces the size of executables by about 30% on the average.
Automated data-member layout of heap objects to improve memory-hierarchy performance
Authors: Kistler Thomas , Franz Michael
Published: October 2002

We present and evaluate a simple, yet efficient optimization technique that improves memory-hierarchy performance for pointer-centric applications by up to 24% and reduces cache misses by up to 35%. This is achieved by selecting an improved ordering for the data members of pointer-based data structures. Our optimization is applicable to all type-safe programming languages that completely abstract from physical storage layout; examples of such languages are Java and Oberon. Our technique does not involve programmers in the optimization process, but runs fully automatically, guided by dynamic profiling information that captures which paths through the program are taken with that frequencey. The algorithm first strives to cluster data members that are accessed closely after one another onto the same cache line, increasing spatial locality. Then, the data members that have been mapped to a particular cache line are ordered to minimize load latency in case of a cache miss.
A New Approach to Proving the Correctness of Multiprocess Programs
Authors: Lamport Leslie
Published: October 2002

A new, nonassertional approach to proving multiprocess program correctness is described by proving the correctness of a new algorithm to solve the mutual exclusion problem. The algorithm is an improved version of the bakery algorithm. It is specified and proved correct without being decomposed into indivisible, atomic operations. This allows two different implementations for a conventional, nondistributed system. Moreover, the approach provides a sufficiently general specification of the algorithm to allow nontrivial implementations for a distributed system as well.
Use of a Nonprocedural Specification Language and Associated Program Generator in Software Development
Authors: Prywes N. S. , S. Shastry Amir and
Published: October 2002

The Model II language and the associated program generator are used to explain and illustrate the use of very high level nonprocedural languages for computer programming. The effect of a very high level language is obtained in Model II through the elimination of procedural and control facilities that exist in high level programming languages such as PL/I or Cobol. In particular, the statements may be given in any order and there are no control constructs such as input/output, iterations, and memory allocation. The task of ordering the statements for execution and providing control statements is performed by the automatic program generator. The specification of a program is therefore much shorter (approximately one-fifth) than the equivalent high level procedural language program. Most important, a user need not regard the task of specifying a program as defining a process but rather as describing data and relations. This point of view greatly reduces the computer programming proficiency required of a user.

The paper focuses on an example of the
use
of the language in business data processing, its advantages, and its novelty. It only briefly reviews the methodology incorporated in the existing program generator, a detailed description of which may be found in the references.
Output Guards and Nondeterminism in “Communicating Sequential Processes”
Authors: Bernstein Arthur
Published: October 2002

In a recent paper C.A.R. Hoare outlined a language for concurrent programming. Guarded commands and nondeterminism are two features of the language. This paper points out two problems that arise in connection with these features and addresses one of them.
An Abstract Type for Statistics Collection in Simula
Authors: Landwehr Carl E.
Published: October 2002

Although the use of abstract types has been widely advocated as a specification and implementation technique, their use has often been associated with programming languages that are not widely available, and examples published to date are rarely taken from actual applications. SIMULA is a widely available language that supports the use of abstract types. The purposes of this paper are (1) to demonstrate the application of the concepts of data abstraction to a common problem; (2) to demonstrate the use of data abstraction in a widely available language; and (3) to provide a portable facility for statistics collection that may make the use of SIMULA more attractive. A discussion of the background of and requirements for an abstract type for statistics collection is presented, followed by a specification for the type using traces. A SIMULA implementation, with examples of its use, is given. Finally, implementation of the abstract type in other languages is discussed.
Syntactic type abstraction
Authors: Grossman Dan , Morrisett Greg , Zdancewic Steve
Published: October 2002

Software developers often structure programs in such a way that different pieces of code constitute distinct
principals
. Types help define the protocol by which these principals interact. In particular,
abstract types
allow a principal to make strong assumptions about how well-typed clients use the facilities that it provides. We show how the notions of principals and type abstraction can be formalized within a language. Different principals can know the implementation of different abstract types. We use additional syntax to track the flow of values with abstract types during the evaluation of a program and demonstrate how this framework supports syntactic proofs (in the sytle of subject reduction) for type-abstraction properties. Such properties have traditionally required semantic arguments; using syntax aboids the need to build a model and recursive typesfor the language. We present various typed lambda calculi with principals, including versions that have mutable state and recursive types.
Proving liveness for networks of communicating finite state machines
Authors: Gouda Mohammed G. , Chang Chung-Kuo
Published: October 2002

Consider a network of communicating finite state machines that exchange messages over unbounded FIFO channels. Each machine in the network can be defined by a directed graph whose nodes represent the machine states and whose edges represent its transitions. In general, for a node in one of the machines to be live (i.e., encountered infinitely often during the course of communication), each machine in the network should progress in some fair fashion. We define three graduated notions of fair progress (namely, node fairness, edge fairness, and network fairness), and on this basis we define three corresponding degrees of node liveness. We discuss techniques to verify that a given node is live under each of these fairness assumptions. These techniques can be automated; and they are effective even if the network under consideration has an infinite number of reachable states. We use our techniques to establish the liveness of some practical communication protocols; these include an unbounded start-stop protocol, an unbounded alternating bit protocol, and a simplified version of the CSMA/CD protocol for local area networks.
Operator strength reduction
Authors: Cooper Keith D. , Simpson L. Taylor , Vick Christopher A.
Published: October 2002

Operator strength reduction is a technique that improves compiler-generated code by reformulating certain costly computations in terms of less expensive ones. A common case arises in array addressing expressions used in loops. The compiler can replace the sequence of multiplies generated by a direct translation of the address expression with an equivalent sequence of additions. When combined with linear function test replacement, strength reduction can speed up the execution of loops containing array references. The improvement comes from two sources: a reduction in the number of operations needed to implement the loop and the use of less costly operations.This paper presents a new algorithm for operator strength reduction, called OSR. OSR improves upon an earlier algorithm of Allen, Cocke, and Kennedy [Allen et al. 1981]. OSR operates on the static single assignment (SSA) form of a procedure [Cytron et al. 1991]. By taking advantage of the properties of SSA form, we have derived an algorithm that is simple to understand, quick to implement, and, in practice, fast to run. Its asymptotic complexity is, in the worst case, the same as the Allen, Cocke,and Kennedy algorithm (ACK). OSR achieves optimization results that are equivalent to those obtained with the ACK algorithm. OSR has been implemented in several research and production compilers.
Video matting of complex scenes
Authors: Chuang Yung-Yu , Agarwala Aseem , Curless Brian , Salesin David H. , Szeliski Richard
Published: October 2002

This paper describes a new framework for
video matting,
the process of pulling a high-quality alpha matte and foreground from a video sequence. The framework builds upon techniques in natural image matting, optical flow computation, and background estimation. User interaction is comprised of garbage matte specification if background estimation is needed, and hand-drawn keyframe segmentations into "foreground," "background" and "unknown". The segmentations, called
trimaps,
are interpolated across the video volume using forward and backward optical flow. Competing flow estimates are combined based on information about where flow is likely to be accurate. A Bayesian matting technique uses the flowed trimaps to yield high-quality mattes of moving foreground elements with complex boundaries filmed by a moving camera. A novel technique for smoke matte extraction is also demonstrated.
Level set surface editing operators
Authors: Museth Ken , Breen David E. , Whitaker Ross T. , Barr Alan H.
Published: October 2002

We present a level set framework for implementing editing operators for surfaces. Level set models are deformable implicit surfaces where the deformation of the surface is controlled by a speed function in the level set partial differential equation. In this paper we define a collection of speed functions that produce a set of surface editing operators. The speed functions describe the velocity at each point on the evolving surface in the direction of the surface normal. All of the information needed to deform a surface is encapsulated in the speed function, providing a simple, unified computational framework. The user combines pre-defined building blocks to create the desired speed function. The surface editing operators are quickly computed and may be applied both regionally and globally. The level set framework offers several advantages. 1) By construction, self-intersection cannot occur, which guarantees the generation of physically-realizable, simple, closed surfaces. 2) Level set models easily change topological genus, and 3) are free of the edge connectivity and mesh quality problems associated with mesh models. We present five examples of surface editing operators: blending, smoothing, sharpening, openings/closings and embossing. We demonstrate their effectiveness on several scanned objects and scan-converted models.