bluuebunny/crossref_metadata_2025 huggingface dataset:
Language support for Morton-order matrices
Authors: Wise David S. , Frens Jeremy D. , Gu Yuhong , Alexander Gregory A.
Published: November 2005

The uniform representation of 2-dimensional arrays serially in Morton order (or {\eee} order) supports both their iterative scan with cartesian indices and their divide-and-conquer manipulation as quaternary trees. This data structure is important because it relaxes serious problems of locality and latency, and the tree helps to schedule multi-processing. Results here show how it facilitates algorithms that avoid cache misses and page faults at all levels in hierarchical memory, independently of a specific runtime environment.

We have built a rudimentary C-to-C translator that implements matrices in Morton-order from source that presumes a row-major implementation. Early performance from LAPACK's reference implementation of \texttt{dgesv} (linear solver), and all its supporting routines (including \texttt{dgemm} matrix-multiplication) form a successful research demonstration. Its performance predicts improvements from new algebra in back-end optimizers.

We also present results from a more stylish \texttt{dgemm} algorithm that takes better advantage of this representation. With only routine back-end optimizations inserted by hand (unfolding the base case and passing arguments in registers), we achieve machine performance exceeding that of the manufacturer-crafted {\tt dgemm} running at 67% of peak flops. And the same code performs similarly on several machines.

Together, these results show how existing codes and future block-recursive algorithms can work well together on this matrix representation. Locality is key to future performance, and the new representation has a remarkable impact.
Contention elimination by replication of sequential sections in distributed shared memory programs
Authors: Lu Honghui , Cox Alan L. , Zwaenepoel Willy
Published: November 2005

In shared memory programs contention often occurs at the transition between a sequential and a parallel section of the code. As all threads start executing the parallel section, they often access data just modified by the thread that executed the sequential section, causing a flurry of data requests to converge on that processor.

We address this problem in a software distributed shared memory system by
replicating
the execution of the sequential sections on all processors. Communication during this replicated sequential execution is reduced by using multicast.

We have implemented replicated sequential execution with multicast support in OpenMP/NOW, a version of of OpenMP that runs on networks of workstations. We do not rely on compile-time data analysis, and therefore we can handle irregular and pointer-based applications. We show significant improvement for two pointer-based applications that suffer from severe contention without replicated sequential execution.
Accurate data redistribution cost estimation in software distributed shared memory systems
Authors: Morris Donald G. , Lowenthal David K.
Published: November 2005

Distributing data is one of the key problems in implementing efficient distributed-memory parallel programs. The problem becomes more difficult in programs where data redistribution between computational phases is considered. The
global data distribution
problem is to find the optimal distribution in multi-phase parallel programs. Solving this problem requires accurate knowledge of data redistribution cost.

We are investigating this problem in the context of a software distributed shared memory (SDSM) system, in which obtaining accurate redistribution cost estimates is difficult. This is because SDSM communication is implicit: It depends on access patterns, page locations, and the SDSM consistency protocol.

We have developed integrated compile- and run-time analysis for SDSM systems to determine accurate redistribution cost estimates with low overhead. Our resulting system, SUIF-Adapt, can efficiently and accurately estimate execution time, including redistribution, to within 5% of the actual time in all of our test cases and is often much closer. These precise costs enable SUIF-Adapt to find efficient global data distributions in multiple-phase programs.
Source-level global optimizations for fine-grain distributed shared memory systems
Authors: Veldema R. , Hofman R. F. H. , Bhoedjang R. A. F. , Jacobs C. J. H. , Bal H. E.
Published: November 2005

This paper describes and evaluates the use of aggressive static analysis in Jackal, a fine-grain Distributed Shared Memory (DSM) system for Java. Jackal uses an optimizing,
source-level
compiler rather than the binary rewriting techniques employed by most other fine-grain DSM systems. Source-level analysis makes existing access-check optimizations (e.g., access-check batching) more effective and enables two novel fine-grain DSM optimizations:
object-graph aggregation
and
automatic computation migration
.

The compiler detects situations where an access to a
root object
is followed by accesses to subobjects. Jackal attempts to aggregate all access checks on objects in such
object graphs
into a single check on the graph's root object. If this check fails, the entire graph is fetched. Object-graph aggregation can reduce the number of network roundtrips and, since it is an advanced form of access-check batching, improves sequential performance.

Computation migration (or function shipping) is used to optimize critical sections in which a single processor owns both the shared data that is accessed and the lock that protects the data. It is usually more efficient to execute such critical sections on the processor that holds the lock and the data than to incur multiple roundtrips for acquiring the lock, fetching the data, writing the data back, and releasing the lock. Jackal's compiler detects such critical sections and optimizes them by generating single-roundtrip
computation-migration
code rather than standard data-shipping code.

Jackal's optimizations improve both sequential and parallel application performance. On average, sequential execution times of instrumented, optimized programs are within 10% of those of uninstrumented programs. Application speedups usually improve significantly and several Jackal applications perform as well as hand-optimized message-passing programs.
Blocking and array contraction across arbitrarily nested loops using affine partitioning
Authors: Lim Amy W. , Liao Shih-Wei , Lam Monica S.
Published: November 2005

Applicable to arbitrary sequences and nests of loops, affine partitioning is a program transformation framework that unifies many previously proposed loop transformations, including unimodular transforms, fusion, fission, reindexing, scaling and statement reordering. Algorithms based on affine partitioning have been shown to be effective for parallelization and communication minimization. This paper presents algorithms that improve data locality using affine partitioning.

Blocking and array contraction are two important optimizations that have been shown to be useful for data locality. Blocking creates a set of inner loops so that data brought into the faster levels of the memory hierarchy can be reused. Array contraction reduces an array to a scalar variable and thereby reduces the number of memory operations executed and the memory footprint. Loop transforms are often necessary to make blocking and array contraction possible.

By bringing the full generality of affine partitioning to bear on the problem, our locality algorithm can find more contractable arrays than previously possible. This paper also generalizes the concept of blocking and shows that affine partitioning allows the benefits of blocking be realized in arbitrarily nested loops. Experimental results on a number of benchmarks and a complete multigrid application in aeronautics indicates that affine partitioning is effective in practice.
Efficiency vs. portability in cluster-based network servers
Authors: Carrera Enrique V. , Bianchini Ricardo
Published: November 2005

Efficiency and portability are conflicting objectives for cluster-based network servers that distribute the clients' requests across the cluster based on the actual content requested. Our work is based on the observation that this efficiency vs. portability tradeoff has not been fully evaluated in the literature. To fill this gap, in this paper we use modeling and experimentation to study this tradeoff in the context of an interesting class of content-based network servers, the locality-conscious servers, under different inter-node communication subsystems. Based on our results, our main conclusion is that portability should be promoted in cluster-based network servers with low processor overhead, given its relatively low cost ($\leq$ 16%) in terms of throughput performance. For clusters with high processor overhead communication, efficiency should be the overriding concern, as the cost of portability can be very high (as high as 107% on 96 nodes). We also conclude that user-level communication can be useful even for non-scientific applications such as network servers.
Retargetable cross compilation techniques
Authors: Guilan Dai , Jinlan Tian , Suqin Zhang , Weidu Jiang , Jun Dai
Published: November 2005

Both GCC and Zephyr are representative complier infrastructures. The paper explores the basic questions that need to be resolved to develop compilers for the support of multiple source languages and targets analyses and compares their architectures and key retargetable cross compilation techniques, summarizes the merits and shortcomings, respectively, and draws a conclusion that the Zephyr infrastructure has the advantage over GCC to an extent.
Analysis of object interaction during the enterprise javabeans lifecycle using formal specification technique
Authors: Lee Ji-Hyun , Yoo Cheol-Jung , Chang Ok-Bae
Published: November 2005

Today's many software projects are based on integration of independently designed software components that are acquired on the market, rather than developed within the projects as a whole. Such a component-based development is an architectural design that permits flexible composition of components into applications. EJB is a good example of these components architecture. Sometimes we misunderstand how EJB operates precisely, because EJB specification is documented in informal language. This paper presents a rigorous analysis of object interaction during the Enterprise JavaBeans lifecycle which is documented informally in EJB specification and shows how a formal specification language can be used to define this. There are a number of different formal languages for software specification including Z and VDM. We have chosen to use Z notation for the reasons that Z has a large variety of notation and it is based on the set theory that forms an adequate basis for building more complex data structures.
Asynchronous communication on Occam
Authors: Serbedzija N. B.
Published: November 2005

In this paper primitives for asynchronous process communication are defined and added to the programming language Occam. Most of the existing concurrent programming concepts have synchronization mechanisms built-in the communication primitives degrading process independency and restricting the parallelism they are trying to provide. Asynchronous process communication provides more freedom in programming concurrent systems allowing non-blocking semantics for both send and receive primitives. Messages are buffered and a number of operations over buffered but not yet received messages are defined, allowing programmer to set or dynamically change the communication discipline needed for the particular application. The goal of the work presented is to relax strict process communication discipline and to make Occam more convenient for expressing concurrency needed for real-time applications. Although Occam is based on the synchronous communication model, its low level facilities provide a possibility to create the semantics of concurrency completely different from the one initially offered.
A paradigm for programming style research
Authors: Oman P. W. , Cook C. R.
Published: November 2005

Programming style guidelines and automated coding style analyzers have been developed without a solid experimental or theoretical basis. In this paper we make a distinction between typographic style characteristics and underlying structural style content and show that this distinction aids in assessing the influence of style factors. This distinction permits straightforward identification of specific style factors and a better understanding of their effect on program comprehension. The results of our studies have a direct impact on automated coding style assessment programs, programming standards, program maintainability, and code formatting tools.
Iteration for applicative languages
Authors: Furtado A. L. , Velosa P. A. S.
Published: November 2005

The mathematical notion of function exponentiation is used to introduce an iteration construct suitable to applicative languages. The elements of the construct are explained as well as its evaluation. A prototype Prolog implementation is included to illustrate the discussion.
Opportunistic garbage collection
Authors: Wilson P. R.
Published: November 2005

Opportunistic garbage collection
is a non-incremental generation-based garbage collection system. It attempts to minimize the probability of disruptive pauses by careful scheduling of scavenges. Scavenge pauses are hidden in pauses created by the running program or by the user; they are also shortened by scheduling them at low points in the stack height, where live data tend to be at a minimum. These heuristics can be surprisingly simple and cheap to implement --- user input primitives provide an effective hook from which to invoke the scheduling routine, since they tend to correspond both to local stack minima and to computational pause boundaries.An additional mechanism is proposed to detect times when it is safe to scavenge an intermediate generation, based on the amount of data surviving from a new-generation scavenge. This mechanism can be used reliably in certain cases, or heuristically in a larger class of cases.
Adding regular expressions to Pascal
Authors: Sharpe D.
Published: November 2005

One generally praiseworthy characteristic of Pascal is that it allows the programmer to define new data types. However, not all operations that can be performed on indigenous types can also be performed on programmer-defined types. I/O is an example. This paper proposes an extension to Pascal that allows generalized input of enumerated types. Syntax is defined which lets the programmer use regular expressions to exercise considerable control over the translation of strings of input characters into the internal representation used for enumerated types.
Efficient full LR(I) parser generation
Authors: Spector D.
Published: November 2005

This paper proposes that full LR(1) parser generators are easier to use than the LALR(1) parser generators commonly in use, and that minimal-state full LR(1) tables are not much larger than LALR(1) tables. A method is presented for the automatic construction of minimal-state full LR(1) parser tables. The method is fast and accurate because it starts with the LR(0) table and resolves lookahead ambiguities as necessary by tracing the LR(0) table and splitting the minimum number of states, and because there is no need for generalized set manipulation.
Packrat parsing:
Authors: Ford Bryan
Published: November 2005

Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language. A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees linear parse time. Any language defined by an LL(
k
) or LR(
k
) grammar can be recognized by a packrat parser, in addition to many languages that conventional linear-time algorithms do not support. This additional power simplifies the handling of common syntactic idioms such as the widespread but troublesome longest-match rule, enables the use of sophisticated disambiguation strategies such as syntactic and semantic predicates, provides better grammar composition properties, and allows lexical analysis to be integrated seamlessly into parsing. Yet despite its power, packrat parsing shares the same simplicity and elegance as recursive descent parsing; in fact converting a backtracking recursive descent parser into a linear-time packrat parser often involves only a fairly straightforward structural change. This paper describes packrat parsing informally with emphasis on its use in practical applications, and explores its advantages and disadvantages with respect to the more conventional alternatives.
Composable and compilable macros:
Authors: Flatt Matthew
Published: November 2005

Many macro systems, especially for Lisp and Scheme, allow macro transformers to perform general computation. Moreover, the language for implementing compile-time macro transformers is usually the same as the language for implementing run-time functions. As a side effect of this sharing, implementations tend to allow the mingling of compile-time values and run-time values, as well as values from separate compilations. Such mingling breaks programming tools that must parse code without executing it. Macro implementors avoid harmful mingling by obeying certain macro-definition protocols and by inserting phase-distinguishing annotations into the code. However, the annotations are fragile, the protocols are not enforced, and programmers can only reason about the result in terms of the compiler's implementation. MzScheme---the language of the PLT Scheme tool suite---addresses the problem through a macro system that separates compilation without sacrificing the expressiveness of macros.
Functional formal methods
Authors: Moore J Strother
Published: November 2005

Some functional programming languages are also mathematical logics. One can reason formally, traditionally, and directly about programs in such languages. This is driving a new application area for functional programming: modeling microarchitectures, hardware design languages, and imperative programming languages. Such models serve the dual purposes of simulation and formal analysis.ACL2, "A Computational Logic for Applicative Common Lisp," is a functional programming language that is also a first-order mathematical logic supported by a Boyer-Moore style mechanical theorem prover [5]. It is being used to model and verify artifacts of commercial and industrial interest.

The register-transfer level circuit descriptions for the elementary floating-point arithmetic on the AMD Athlon microprocessor were modeled in ACL2. These models were tested on millions of floating-point test vectors as part of the Athlon validation. In addition, the models were mechanically proved to satisfy the IEEE floating-point specifications. Bugs were found before fabrication. The Athlon that you buy has verified floating-point circuitry in it [7].

Avionics microprocessors produced by Rockwell Collins have been modeled in ACL2. Those models have been used as pre-fabrication simulation test benches. In addition, theorems relating various microprocessor models have been proved mechanically [3].

An executable pipeline-level model of the Motorola CAP digital signal processor was proved to implement a sequential microcode engine and microcoded DSP programs were verified [2].

An executable model of the Java Virtual Machine has been used to prove functional correctness of some simple Java classes, including a safety property for a multi-threaded class [6].

.Other examples are reported in [4].Execution efficiency for industrial-scale simulators, in combination with adherence to an axiomatic semantics, has forced some novel implementation features [1]. In addition, the ACL2 theorem prover is coded in ACL2 and so represents a significant application of functional programming.
Shortcut fusion for accumulating parameters & zip-like functions
Authors: Svenningsson Josef
Published: November 2005

We present an alternative approach to shortcut fusion based on the function
unfoldr,
. Despite its simplicity the technique can remove intermediate lists in examples which are known to be difficult. We show that it can remove all lists from definitions involving
zip
-like functions and functions using accumulating parameters.
Creating and preserving locality of java applications at allocation and garbage collection times
Authors: Shuf Yefim , Gupta Manish , Franke Hubertus , Appel Andrew , Singh Jaswinder Pal
Published: November 2005

The growing gap between processor and memory speeds is motivating the need for optimization strategies that improve data locality. A major challenge is to devise techniques suitable for pointer-intensive applications. This paper presents two techniques aimed at improving the memory behavior of pointer-intensive applications with dynamic memory allocation, such as those written in Java. First, we present an allocation time object placement technique based on the recently introduced notion of
prolific
(frequently instantiated) types. We attempt to co-locate, at allocation time, objects of prolific types that are connected via object references. Then, we present a novel locality based graph traversal technique. The benefits of this technique, when applied to garbage collection (GC), are twofold: (i) it improves the performance of GC due to better locality during a heap traversal and (ii) it restructures surviving objects in a way that enhances locality. On multiprocessors, this technique can further reduce overhead due to synchronization and false sharing. The experimental results, on a well-known suite of Java benchmarks (SPECjvm98 [26], SPECjbb2000 [27], and jOlden [4]), from an implementation of these techniques in the Jikes RVM [1], are very encouraging. The object co-allocation technique improves application performance by up to 21% (10% on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector. The locality-based traversal technique reduces GC times by up to 20% (10% on average) and improves the performance of applications by up to 14% (6% on average) in the Jikes RVM configured with a copying semi-space collector. Both techniques combined can improve application performance by up to 22% (10% on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector.
Integrating independent components with on-demand remodularization
Authors: Mezini Mira , Ostermann Klaus
Published: November 2005

This paper proposes language concepts that facilitate the separation of an application into independent reusable building blocks and the integration of pre-build generic software components into applications that have been developed by third party vendors. A key element of our approach are
on-demand remodularizations
, meaning that the abstractions and vocabulary of an existing code base are translated into the vocabulary understood by a set of components that are connected by a common
collaboration interface
. This general concept allows us to mix-and-match remodularizations and components on demand.
Lock reservation
Authors: Kawachiya Kiyokuni , Koseki Akira , Onodera Tamiya
Published: November 2005

Because of the built-in support for multi-threaded programming, Java programs perform many lock operations. Although the overhead has been significantly reduced in the recent virtual machines, One or more atomic operations are required for acquiring and releasing an object's lock even in the fastest cases.This paper presents a novel algorithm called
lock reservation
. It exploits
thread locality
of Java locks, which claims that the locking sequence of a Java lock contains a very long repetition of a specific thread. The algorithm allows locks to be reserved for threads. When a thread attempts to acquire a lock, it can do without any atomic operation if the lock is reserved for the thread. Otherwise, it cancels the reservation and falls back to a conventional locking algorithm.We have evaluated an implementation of lock reservation in IBM's production virtual machine and compiler. The results show that it achieved performance improvements up to 53% in real Java programs.
Ownership types for safe programming
Authors: Boyapati Chandrasekhar , Lee Robert , Rinard Martin
Published: November 2005

This paper presents a new static type system for multithreaded programs; well-typed programs in our system are guaranteed to be free of data races and deadlocks. Our type system allows programmers to partition the locks into a fixed number of equivalence classes and specify a partial order among the equivalence classes. The type checker then statically verifies that whenever a thread holds more than one lock, the thread acquires the locks in the descending order.Our system also allows programmers to use recursive tree-based data structures to describe the partial order. For example, programmers can specify that nodes in a tree must be locked in the
tree order
. Our system allows mutations to the data structure that change the partial order at runtime. The type checker statically verifies that the mutations do not introduce cycles in the partial order, and that the changing of the partial order does not lead to deadlocks. We do not know of any other sound static system for preventing deadlocks that allows changes to the partial order at runtime.Our system uses a variant of ownership types to prevent data races and deadlocks. Ownership types provide a statically enforceable way of specifying object encapsulation. Ownership types are useful for preventing data races and deadlocks because the lock that protects an object can also protect its encapsulated objects. This paper describes how to use our type system to statically enforce object encapsulation as well as prevent data races and deadlocks. The paper also contains a detailed discussion of different ownership type systems and the encapsulation guarantees they provide.
Sifting out the mud
Authors: De Sutter Bjorn , De Bus Bruno , De Bosschere Koen
Published: November 2005

More and more computers are being incorporated in devices where the available amount of memory is limited. This contrasts with the increasing need for additional functionality and the need for rapid application development. While object-oriented programming languages, providing mechanisms such as inheritance and templates, allow fast development of complex applications, they have a detrimental effect on program size. This paper introduces new techniques to reuse the code of whole procedures at the binary level and a supporting technique for data reuse. These techniques benefit specifically from program properties originating from the use of templates and inheritance. Together with our previous work on code abstraction at lower levels of granularity, they achieve additional code size reductions of up to 38% on already highly optimized and compacted binaries, without sacrificing execution speed. We have incorporated these techniques in
Squeeze++
, a prototype link-time binary rewriter for the Alpha architecture, and extensively evaluate them on a suite of 8 real-life C++ applications. The total code size reductions achieved post link-time (i.e. without requiring any change to the compiler) range from 27 to 70%, averaging at around 43%.
Towards a formalization for COM part i
Authors: Pucella Riccardo
Published: November 2005

We introduce in this paper a typed calculus intended to capture the execution model of COM. The innovation of this calculus is to model very low-level aspects of the COM framework, specifically the notion of interface pointers. This is handled by specifying an allocation semantics for the calculus, thereby modeling heap allocation of interfaces explicitly. Having an explicit way of talking about interface pointers allows us to model in a reasonable way the notions of interface sharing and object identity. We introduce a type system that can be used to disambiguate between specification and implementation of interfaces. The type system moreover can capture a notion of COM conformance, that is, the legality of COM components. We discuss extensions of the calculus to handle subtyping of interfaces, dynamic interface negotiation and aggregation.
GCspy
Authors: Printezis Tony , Jones Richard
Published: November 2005

GCspy is an architectural framework for the collection, transmission, storage and replay of memory management behaviour. It makes new contributions to the understanding of the dynamic memory behaviour of programming languages (and especially object-oriented languages that make heavy demands on the performance of memory managers). GCspy's architecture allows easy incorporation into
any
memory management system: it is not limited to garbage-collected languages. It requires only small changes to the system in which it is incorporated but provides a simple to use yet powerful data-gathering API. GCspy scales to allow very large heaps to be visualised effectively and efficiently. It allows already-running, local or remote systems to be visualised and those systems to run at full speed outside the points at which data is gathered. GCspy's visualisation tool presents this information in a number of novel ways.Deep understanding of program behaviour is essential to the design of the next generation of garbage collectors and explicit allocators. Until now, no satisfactory tools have been available to assist the implementer in gaining an understanding of heap behaviour. GCspy has been demonstrated to be a practical solution to this dilemma. It has been used to analyse production Java virtual machines running applications of realistic sizes. Its use has revealed important insights into the interaction between application program and JVM and has led to the development of better garbage collectors.
Programming dynamically reconfigurable open systems with SALSA
Authors: Varela Carlos , Agha Gul
Published: November 2005

Applications running on the Internet, or on limited-resource devices, need to be able to adapt to changes in their execution environment at run-time. Current languages and systems fall short of enabling developers to migrate and reconfigure application sub-components at program-execution time.In this paper, we describe essential aspects of the design and implementation of SALSA, an actor-based language for mobile and Internet computing. SALSA simplifies programming dynamically reconfigurable, open applications by providing universal names, active objects, and migration. Moreover, SALSA introduces three language mechanisms to help programmers coordinate asynchronous, mobile computations: token-passing continuations, join continuations and first-class continuations.We provide some examples which illustrate how SALSA programs are not only dynamically reconfigurable and open, but also much more concise and easier to follow than comparable Java code. Furthermore, we provide empirical results which show SALSA's performance to be better than Java code using an actor library, and which illustrate the difference between local, local area, and wide area communication and migration. Finally, we discuss the implementation of our preprocessor which translates SALSA code into Java.
Dependence analysis for recursive java programs
Authors: Xu Baowen , Chen Zhenqiang
Published: November 2005

Dependence analysis is an important approach to analyzing, understanding, testing and maintaining programs. This paper develops a new kind of dependence analysis method for recursive Java programs. In our method, the program dependence graph (PDG) of a Java program consists of a set of PDGs that are not connected. They interact with each other by dependences among parameters. Thus, he inter-function dependence analysis is transformed to intra-function dependence analysis. Based on this model, we develop a new approach to analyze dependences of a direct or indirect recursive Java program by simulating its execution.
How many trivial getter methods does java have?
Authors: Hughes Elliott
Published: November 2005

A recent SIGPLAN Notice [5] repeated a claim [4] that "accessor methods used to obtain the value of a field (getter methods) account for about one fourth of the total number of methods in the standard java.* package source classes". This article examines that claim, and examines the variety of methods that are nowadays considered getter methods.
E-path_PRE
Authors: Dhamdhere Dhananjay M.
Published: November 2005

Partial redundancy elimination (PRE) subsumes the classical optimizations of loop invariant movement and common subexpression elimination. The original formulation of PRE involved complex bi-directional data flows and had two major deficiencies---missed optimization opportunities and redundant code movement. To eliminate redundant code movement, most current PRE approaches use a hoisting-followed-by-sinking approach. Unfortunately, this approach has a high conceptual complexity and requires complicated correctness proofs.We show that optimization by partial redundancy elimination is simpler than it has been made out to be. Its essence is the concept of
eliminatability
of an expression. We show that E-path_PRE, a formulation of PRE based on the concept of eliminatability paths (E-paths), is easy to understand and simple to prove correct. It uses only well-known data flow concepts of available expressions and anticipatable (i.e. very-busy) expressions to directly identify code insertion points which avoid redundant code movement. These features reduce the conceptual complexity of PRE considerably. Interestingly, performance studies show that E-path_PRE is also less expensive to perform than the closest equivalent approach to PRE. This is a sheer bonus.
Detection of information leak by data flow analysis
Authors: Doh Kyung Goo , Shin Seung Cheol
Published: November 2005

This paper uses the standard technique of data flow analysis to statically find information leaks in simple imperative programs. The correctness of the analysis is discussed and the proof is sketched.
Transactional lock-free execution of lock-based programs
Authors: Rajwar Ravi , Goodman James R.
Published: November 2005

This paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access to shared data. To ensure correctness programmers often rely on conservative locking at the expense of performance. The resulting serialization of threads is a performance bottleneck. Locks also interact poorly with thread scheduling and faults, resulting in poor system performance.We seek to improve multithreaded programming trade-offs by providing architectural support for optimistic lock-free execution. In a lock-free execution, shared objects are never locked when accessed by various threads. We propose
Transactional Lock Removal
(TLR) and show how a program that uses lock-based synchronization can be executed by the hardware in a lock-free manner, even in the presence of conflicts, without programmer support or software changes. TLR uses timestamps for conflict resolution, modest hardware, and features already present in many modern computer systems.TLR's benefits include improved programmability, stability, and performance. Programmers can obtain benefits of lock-free data structures, such as non-blocking behavior and wait-freedom, while using lock-protected critical sections for writing programs.
Enhancing software reliability with speculative threads
Authors: Oplinger Jeffrey , Lam Monica S.
Published: November 2005

This paper advocates the use of a monitor-and-recover programming paradigm to enhance the reliability of software, and proposes an architectural design that allows software and hardware to cooperate in making this paradigm more efficient and easier to program.We propose that programmers write monitoring functions assuming simple sequential execution semantics. Our architecture speeds up the computation by executing the monitoring functions speculatively in parallel with the main computation. For recovery, programmers can define fine-grain transactions whose side effects, including all register modifications and memory writes, can either be committed or aborted under program control. Transactions are implemented efficiently by treating them as speculative threads.Our experimental results suggest that monitored execution is more amenable to parallelization than regular program execution. Code monitoring is sped up by a factor of 1.5 by exploiting single-thread instruction-level parallelism, and by an additional factor of 1.6 using thread-level speculation. This results in an overall improvement of 2.5 times and a sustained 5.4 instructions-per-cycle performance. A monitored execution that used to be 2.5 times slower executes with a degradation of only 12% when compared to the performance on the baseline machine. We also show that the concept of fine-grain transactional programming is useful in catching buffer overrun errors through a number of real-life examples.
A stateless, content-directed data prefetching mechanism
Authors: Cooksey Robert , Jourdan Stephan , Grunwald Dirk
Published: November 2005

Although central processor speeds continues to improve, improvements in overall system performance are increasingly hampered by memory latency, especially for pointer-intensive applications. To counter this loss of performance, numerous data and instruction prefetch mechanisms have been proposed. Recently, several proposals have posited a
memory-side
prefetcher; typically, these prefetchers involve a distinct processor that executes a program slice that would effectively prefetch data needed by the primary program. Alternative designs embody large state tables that learn the miss reference behavior of the processor and attempt to prefetch likely misses.This paper proposes
Content-Directed Data Prefetching,
a data prefetching architecture that exploits the memory allocation used by operating systems and runtime systems to improve the performance of pointer-intensive applications constructed using modern language systems. This technique is modeled after conservative garbage collection, and prefetches "likely" virtual addresses observed in memory references. This prefetching mechanism uses the underlying data of the application, and provides an 11.3% speedup using
no additional processor state.
By adding less than ½% space overhead to the second level cache, performance can be further increased to 12.6% across a range of "real world" applications.
On the return types of virtual functions
Authors: Panizzi Emanuele , Pastorelli Bernardo
Published: November 2005

In this paper a problem raising in the static type checking of C++ virtual functions is presented. C++ allows a certain degree of freedom in the specialization of the return type of virtual functions. As to the actual draft standard, this freedom can lead to run-time errors and, for this reason, it must be used carefully or compiler support must be added to prevent inconsistencies.
The complexity of formal specifications - assessments by α - metric
Authors: Kokol Peter , Podgorelec Vili , Habrias Henri , Rabia Nassim Hadj
Published: November 2005

This paper presents the use of α -- metrics in analysing and comparison of various formal specification languages.
Expressing opposition in the object model, first step towards negation
Authors: Anquetil Nicolas , Vaucher Jean
Published: November 2005

Although seemingly simple and intuitive, the object model still contains ambiguous notions. For example, inheritance has been proved to convey two different meanings depending on whether it is behavior or implementation that is inherited. Another conceptually simple notion, multiple inheritance, has not yet been clearly formalized.In this paper, we start by looking at relationships between sibling classes (two immediate subclasses of a common parent). Siblings can be combined through multiple inheritance, or on the contrary, they can be mutually exclusive. We call the relation between incompatible siblings
opposition
, and show how it could help in formalizing object models.We then consider widening the explicit use of negation in object models. We argue that negative assertions could be used to validate the creation of new classes to ensure they are compatible with the intended uses of existing classes. Negation leads us to consider the implicit assumption behind object models, we propose to shift from the closed world assumption to the open world assumption.
Unloading Java classes that contain static fields
Authors: McDowell C. E. , Baldwin E. A.
Published: November 2005

In Java, the definition of a "program" is a bit fuzzy. A Java applet is essentially a Java application (i.e. program) that can be executed by a Java enabled Web browser (i.e. an OS). An applet running inside of a browser was intended to be analogous to a conventional application running under on OS, hence the netcentric "browser is your OS" model. However, as currently implemented, this analogy breaks down with regard to the system resources allocated for classes and in particular for static fields in classes (i.e. class variables) when the class was loaded as part of an applet.Without class unloading, a long running Java application such as a browser is like an OS that does not release memory resources allocated for application code space when the application terminates. With class unloading, as currently implemented, the semantics of static fields in classes are broken. In this paper we detail the problem and provide a solution. The solution combines restricting when classes can be unloaded, with a greater use of non-default class loaders.
On Dart-Zobel Algorithm for testing regular type inclusion
Authors: Lu Lunjin
Published: November 2005

This paper answers open questions about the correctness and the completeness of Dart-Zobel algorithm for testing the inclusion relation between two regular types. We show that the algorithm is complete but incorrect for regular types.
A framework design of workflow management system with Java RMI
Authors: Shaofeng Wang , Jiaguang Sun
Published: November 2005

In this paper, we study the issues of the design of the Java RMI-based workflow management systems (JWfMS). In JWfMS, Java RMI is used as the underlying infrastructure technology. The strengths and weaknesses of some typical distributed object technologies such as CORBA, DCOM, and Java RMI are discussed. We present a method of using Java RMI to transport the objects dynamically between the server and client in JWfMS, thus making it possible to transport the only needed objects and require lower network transport load during run time. We discuss the framework design of this method in details and show that Java RMI is suitable for designing complicated distributed applications such as JWfMS.
A user interface toolkit based on graphical objects and constraints
Authors: Szekely Pedro , Myers Brad
Published: November 2005

One of the most difficult aspects of creating graphical, direct manipulation user interfaces is managing the relationships between the graphical objects on the screen and the application data structures that they represent. Coral (Constraint-based Object-oriented Relations And Language) is a new user interface toolkit under development that uses efficiently-implemented constraints to support these relationships. Using Coral, user interface designers can construct interaction techniques such as menus and scroll bars. More importantly, Coral makes it easy to construct direct-manipulation user interfaces specialized to particular applications. Unlike previous constraint-based toolkits, Coral supports defining constraints in the abstract, and then applying them to different object instances. In addition, it provides iteration constructs where lists of items (such as those used in menus) can be constrained as a group. Coral has two interfaces: a declarative interface that provides a convenient way to specify the desired constraints, and a procedural interface that will allow a graphical user interface management system (UIMS) to automatically create Coral calls.
Building a backtracking facility in smalltalk without kernel support
Authors: LaLonde Wilf R. , Gulik Mark Van
Published: November 2005

Languages like Snobol, Prolog, and Icon were designed with backtracking facilities from the outset and these facilities are deeply intertwined with the implementation. Retrofitting a backtracking facility in a language that wasn't designed for it has never been achieved. We report on an experiment to retrofit Smalltalk with a backtracking facility. The facility is provided through a small number of primitives written in the language (no modifications to the kernel were made). The ability to do this is a direct result of the power provided by the objectification of contexts.
An interactive environment for object-oriented music composition and sound synthesis
Authors: Scaletti C. A. , Johnson R. E.
Published: November 2005

Kyma is an object-oriented environment for music composition written in Smalltalk-80, which, in conjunction with a microprogrammable digital signal processor called the Platypus, provides the composer with a means for creating and manipulating Sound objects graphically with real-time sonic feedback via software synthesis. Kyma draws no distinctions between the materials and the structure of a composition; both are Sound objects. When a Sound object receives a message to play, it transforms itself into a microSound object, i.e. an object representation of itself in the microcode of the Platypus. Thus an object paradigm is used not only in the representation of Sound objects in Smalltalk-80 but also in the microcode representation of those Sound objects on the Platypus
.
An object-oriented framework of pattern recognition systems
Authors: Yoshida Norihiko , Hino Kouji
Published: November 2005

In this paper, we describe a purely object-oriented framework of pattern recognition systems. Its aim is in dealing with knowledge representation issues in pattern recognition. In our approach, everything works in an entirely autonomous and decentralized manner. Even a search procedure for sample-concept matching is distributed onto every concept object itself by being implemented in what we introduced as the recursive agent-blackboard model. We developed an experimental prototype of character recognition systems in Smalltalk-80, which proved the ability of the object-oriented framework and the cooperative search procedure.
Using tuple space communication in distributed object-oriented languages
Authors: Matsuoka Satoshi , Kawai Satoru
Published: November 2005

When Object-Oriented languages are applied to distributed problem solving, the form of communication restricted to direct message sending is not flexible enough to naturally express complex interactions among the objects. We transformed the
Tuple Space Communication Model
[29] for better affinity with Object-Oriented computation, and integrated it as an alternative method of communication among the distributed objects. To avoid the danger of potential bottleneck, we formulated an algorithm that makes concurrent pattern matching activities within the Tuple Space possible.