bluuebunny/crossref_metadata_2025 huggingface dataset:
Enhanced code compression for embedded RISC processors
Authors: Cooper Keith D. , McIntosh Nathaniel
Published: November 2005

This paper explores compiler techniques for reducing the memory needed to load and run program executables. In embedded systems, where economic incentives to reduce both RAM and ROM are strong, the size of compiled code is increasingly important. Similarly, in mobile and network computing, the need to transmit an executable before running it places a premium on code size. Our work focuses on reducing the size of a program's code segment, using pattern-matching techniques to identify and coalesce together repeated instruction sequences. In contrast to other methods, our framework preserves the ability to run program executables directly, without an intervening decompression stage. Our compression framework is integrated into an industrial-strength optimizing compiler, which allows us to explore the interaction between code compression and classical code optimization techniques, and requires that we contend with the difficulties of compressing previously optimized code. The specific contributions in this paper include a comprehensive experimental evaluation of code compression for a RISC-like architecture, a more powerful pattern-matching scheme for improved identification of repeated code fragments, and a new form of profile-driven code compression that reduces the speed penalty arising from compression.
New tiling techniques to improve cache temporal locality
Authors: Song Yonghong , Li Zhiyuan
Published: November 2005

Tiling is a well-known loop transformation to improve temporal locality of nested loops. Current compiler algorithms for tiling are limited to loops which are perfectly nested or can be transformed, in trivial ways, into a perfect nest. This paper presents a number of program transformations to enable tiling for a class of nontrivial imperfectly-nested loops such that cache locality is improved. We define a program model for such loops and develop compiler algorithms for their tiling. We propose to adopt
odd-even variable duplication
to break anti- and output dependences without unduly increasing the working-set size, and to adopt
speculative execution
to enable tiling of loops which may terminate prematurely due to, e.g. convergence tests in iterative algorithms. We have implemented these techniques in a research compiler, Panorama. Initial experiments with several benchmark programs are performed on SGI workstations based on MIPS R5K and R10K processors. Overall, the transformed programs run faster by 9% to 164%.
Whole program paths
Authors: Larus James R.
Published: November 2005

Whole program paths (WPP)
are a new approach to capturing and representing a program's dynamic---actually executed---control flow. Unlike other path profiling techniques, which record intraprocedural or acyclic paths, WPPs produce a single, compact description of a program's entire control flow, including loop iteration and interprocedural paths.This paper explains how to collect and represent WPPs. It also shows how to use WPPs to find
hot subpaths
, which are the heavily executed sequences of code that should be the focus of performance tuning and compiler optimization.
Literate programming and the “Spaniel“ method
Authors: Hatzigeorgiu Nick , Syropoulos Apostolos
Published: November 2005

Software has to be well structured and well documented in order to be reusable and maintainable. Literate programs have both properties. Unfortunately, even today many programmers write program without proper documentation. We propose a technique by which one can relatively easily transform a well structured program into a literate one. We exemplify the technique by means of an example and we conclude with the presentation of some related work and ideas.
Functional programming and the fragile base class problem
Authors: Budd Timothy A.
Published: November 2005

A fact of life is that software changes over time. It has been observed that while object-oriented programs and functional programs both facilitate changes of a certain variety, they also make it difficult to permit changes of another type. Object-oriented languages make it easy to add new data types, but difficult to add new functionality to an existing data type (the so-called fragile base class problem). Functional programs make it easy to add new behavior to existing data types, but make it difficult to add new types of data values that are variations on existing types. In this paper we argue that a multiparadigm language, that permits both styles of development, provides the best of both worlds.
Declarative peephole optimization using string pattern matching
Authors: Spinellis Diomidis
Published: November 2005

Peephole optimisation as a last step of a compilation sequence capitalises on significant opportunities for removing low level code slackness left over by the code generation process. We have designed a peephole optimiser that operates using a declarative specification of the optimisations to be performed. The optimiser's implementation is based on string pattern matching using regular expressions. We used this approach to prototype an optimiser to convert target machine instruction sequences containing conditional execution of instructions inside loop bodies into code that adaptively executes the optimum branch instructions according to the program's branch behaviour.
A type system of logic objects
Authors: Xu Dianxiang
Published: November 2005

This paper describes the declaration and inference based type system in an object-oriented logic framework, where logic objects are viewed as typed abstractions with state, constraints, behaviors and non-monotonic inheritance. Types are built by ordered constructors with subtyping relationships. As base types, the classes can be applied to complex type construction. Objects are classified according to their method signatures, and subtyping is independent of inheritance.
A secure dynamic copy protocol in real-time secure database systems
Authors: Lee Sungyoung , Jeong Byeong-Soo , Seung Hyon-Woo
Published: November 2005

Concurrency control for real-time secure database systems must satisfy not only logical data consistency but also timing constraints and security requirements associated with transactions. These conflicting natures between timing constraints and security requirements are often resolved by maintaining several versions (or secondary copies) on the same data items. In this paper, we propose a new lock-based concurrency control protocol, Secure Dynamic Copy Protocol, ensuring both conflicting requirements. Our protocol aims for reducing the storage overhead of maintaining secondary copies and minimizing the processing overhead of update history. The main idea of our protocol is to keep a secondary copy only when it is needed to resolve the conflicting read/write operations in real time secure database systems. For doing this, a secondary copy is dynamically created and removed during a transaction's read/write operations. While comparing the existing real-time security protocol, we have also examined the performance characteristics of our protocol through simulation under different workloads. The results show that our protocol consumed less storage and decreased the deadline missing transactions.
Objects, classes and modules in Objective Caml (invited lecture, abstract only)
Authors: Leroy Xavier
Published: November 2005

In a programming language with procedures and assignments, it is often important to isolate uses of state to particular program fragments. The frameworks of type, region, and effect inference, and monadic state are technologies that have been used to state and enforce the property that an expression has no visible side-effects. This property has been exploited to justify the deallocation of memory regions despite the presence of dangling pointers.Starting from an idea developed in the context of monadic state in Haskell, we develop an ML-like language with full assignments and an operator that enforces the encapsulation of effects. Using this language, we formalize and prove the folklore connection between effect masking and monadic encapsulation. Then, by employing a novel set of reductions to deal with dangling pointers, we establish the soundness of the type-based encapsulation with a proof based on a standard subject reduction argument.
Interlanguage working without tears
Authors: Benton Nick , Kennedy Andrew
Published: November 2005

A good foreign-language interface is crucial for the success of any modern programming language implementation. Although all serious compilers for functional languages have some facility for interlanguage working, these are often limited and awkward to use.This article describes the features for bidirectional interlanguage working with Java that are built into the latest version of the MLj compiler. Because the MLj foreign interface is to another high-level typed language which shares a garbage collector with compiled ML code, and because we are willing to extend the ML language, we are able to provide unusually powerful, safe and easy to use interlanguage working features. Indeed, rather then being a traditional foreign
interface
, our language extensions are more a partial
integration
of Java features into SML.We describe this integration of Standard ML and Java, first informally with example program fragments, and then formally in the notation used by The Definition of Standard ML.
Static interpretation of modules
Authors: Elsman Martin
Published: November 2005

This paper presents a technique for compiling Standard ML Modules into typed intermediate language fragments, which may be compiled separately and linked using traditional linking technology to form executable code. The technique is called
static interpretation
and allows compile-time implementation details to propagate across module boundaries. Static interpretation eliminates all module-level code at compile time.The technique scales to full Standard ML and is used in the ML Kit with Regions compiler. A framework for smart recompilation makes the technique useful for compiling large programs.
Transparent modules with fully syntatic signatures
Authors: Shao Zhong
Published: November 2005

ML-style modules are valuable in the development and maintenance of large software systems, unfortunately, none of the existing languages support them in a fully satisfactory manner. The Official SML'97 Definition does not allow higher-order functors, so a module that refers to externally defined functors cannot accurately describe its import interface. MacQueen and Tofte [26] extended SML'97 with fully transparent higher-order functors, but their system does not have a type-theoretic semantics thus fails to support fully syntactic signatures. The systems of manifest types [19, 20] and translucent sums [12] support fully syntactic signatures but they may propagate fewer type equalities than fully transparent functors. This paper presents a module calculus that supports both fully transparent higher-order functors and fully syntactic signatures (and thus true separate compilation). We give a simple type-theoretic semantics to our calculus and show how to compile it into an F
ω
-like λ-calculus extended with existential types.
Specialization of inductively sequential functional logic programs
Authors: Alpuente María , Hanus Michael , Lucas Salvador , Vidal Germán
Published: November 2005

Functional logic languages combine the operational principles of the most important declarative programming paradigms, namely functional and logic programming. Inductively sequential programs admit the definition of optimal computation strategies and are the basis of several recent (lazy) functional logic languages. In this paper, we define a partial evaluator for inductively sequential functional logic programs. We prove strong correctness of this partial evaluator and show that the nice properties of inductively sequential programs carry over to the specialization process and the specialized programs. In particular, the structure of the programs is preserved by the specialization process. This is in contrast to other partial evaluation methods for functional logic programs which can destroy the original program structure. Finally, we present some experiments which highlight the practical advantages of our approach.
Escape analysis for Java
Authors: Choi Jong-Deok , Gupta Manish , Serrano Mauricio , Sreedhar Vugranam C. , Midkiff Sam
Published: November 2005

This paper presents a simple and efficient data flow algorithm for escape analysis of objects in Java programs to determine (i) if an object can be allocated on the stack; (ii) if an object is accessed only by a single thread during its lifetime, so that synchronization operations on that object can be removed. We introduce a new program abstraction for escape analysis, the
connection graph
, that is used to establish reachability relationships between objects and object references. We show that the connection graph can be summarized for each method such that the same summary information may be used effectively in different calling contexts. We present an interprocedural algorithm that uses the above property to efficiently compute the connection graph and identify the non-escaping objects for methods and threads. The experimental results, from a prototype implementation of our framework in the IBM High Performance Compiler for Java, are very promising. The percentage of objects that may be allocated on the stack exceeds 70% of all dynamically created objects in three out of the ten benchmarks (with a median of 19%), 11% to 92% of all lock operations are eliminated in those ten programs (with a median of 51%), and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333 MHz PowerPC workstation with 128 MB memory.
Removing unnecessary synchronization in Java
Authors: Bogda Jeff , Hölzle Urs
Published: November 2005

Java programs perform many synchronization operations on data structures. Some of these synchronization are unnecessary; in particular, if an object is reachable only by a single thread, concurrent access is impossible and no synchronization is needed. We describe an interprocedural, flow- and context-insensitive dataflow analysis that finds such situations. A global optimizing transformation then eliminates synchronizations on these objects. For every program in our suite of ten Java benchmarks consisting of SPECjvm98 and others, our system optimizes over 90% of the alias sets containing at least one synchronized object. As a result, the dynamic frequency of synchronizations is reduced by up to 99%. For two benchmarks that perform synchronizations very frequently, this optimization leads to speedups of 36% and 20%.
Confined types
Authors: Vitek Jan , Bokowski Boris
Published: November 2005

Sharing and transfer of object references is difficult to control in object-oriented languages. Unconstrained sharing poses serious problems for writing secure components in object-oriented languages. In this paper, we present a set of inexpensive syntactic constraints that strengthen encapsulation in object-oriented programs and facilitate the implementation of secure systems. We introduce two mechanisms:
confined types
to impose static scoping on dynamic object references and, for technical reasons,
anonymous methods
which are methods that do not reveal the identity of the current instance (this). Confined types protect objects from use by untrusted code, while anonymous methods allow standard classes to be reused from confined classes. We have implemented a verifier which performs a modular analysis of Java programs and provides a static guarantee that confinement is respected. We present security related programming examples.
Compositional pointer and escape analysis for Java programs
Authors: Whaley John , Rinard Martin
Published: November 2005

This paper presents a combined pointer and escape analysis algorithm for Java programs. The algorithm is based on the abstraction of points-to escape graphs, which characterize how local variables and fields in objects refer to other objects. Each points-to escape graph also contains escape information, which characterizes how objects allocated in one region of the program can escape to be accessed by another region. The algorithm is designed to analyze arbitrary regions of complete or incomplete programs, obtaining complete information for objects that do not escape the analyzed regions.

We have developed an implementation that uses the escape information to eliminate synchronization for objects that are accessed by only one thread and to allocate objects on the stack instead of in the heap. Our experimental results are encouraging. We were able to analyze programs tens of thousands of lines long. For our benchmark programs, our algorithms enable the elimination of between 24% and 67% of the synchronization operations. They also enable the stack allocation of between 22% and 95% of the objects.
Practical experience with an application extractor for Java
Authors: Tip Frank , Laffra Chris , Sweeney Peter F. , Streeter David
Published: November 2005

Java programs are routinely transmitted over low-bandwidth network connections as compressed class file archives (i.e., zip files and jar files). Since archive size is directly proportional to download time, it is desirable for applications to be as small as possible. This paper is concerned with the use of program transformations such as removal of dead methods and fields, inlining of method calls, and simplification of the class hierarchy for reducing application size. Such “extraction” techniques are generally believed to be especially useful for applications that use class libraries, since typically only a small fraction of a library's functionality is used. By “pruning away” unused library functionality, application size can be reduced dramatically. We implemented a number of application extraction techniques in Jax, an application extractor for Java, and evaluate their effectiveness on a set of realistic benchmarks ranging from 27 to 2,332 classes (with archives ranging from 56,796 to 3,810,120 bytes). We report archive size reductions ranging from 13.4% to 90.2% (48.7% on average).
Implementing jalapeño in Java
Authors: Alpern Bowen , Attanasio C. R. , Cocchi Anthony , Lieber Derek , Smith Stephen , Ngo Ton , Barton John J. , Hummel Susan Flynn , Sheperd Janice C. , Mergen Mark
Published: November 2005

Jalapeño is a virtual machine for Java™ servers written in Java.

A running Java program involves four layers of functionality: the user code, the virtual-machine, the operating system, and the hardware. By drawing the Java / non-Java boundary below the virtual machine rather than above it, Jalapeño reduces the boundary-crossing overhead and opens up more opportunities for optimization.

To get Jalapeño started, a
boot image
of a working Jalapeño virtual machine is concocted and written to a file. Later, this file can be loaded into memory and executed. Because the boot image consists entirely of Java objects, it can be concocted by a Java program that runs in
any
JVM. This program uses reflection to convert the boot image into Jalapeño's object format.

A special MAGIC class allows unsafe casts and direct access to the hardware. Methods of this class are recognized by Jalapeño's three compilers, which ignore their bytecodes and emit special-purpose machine code. User code will not be allowed to call MAGIC methods so Java's integrity is preserved.

A small non-Java program is used to start up a boot image and as an interface to the operating system.

Java's programming features — object orientation, type safety, automatic memory management — greatly facilitated development of Jalapeño. However, we also discovered some of the language's limitations.
Mostly-copying reachability-based orthogonal persistence
Authors: Hosking Antony L. , Chen Jiawan
Published: November 2005

We describe how reachability-based orthogonal persistence can be supported even in uncooperative implementations of languages such as C++ and Modula-3, and without modification to the compiler. Our scheme extends Bartlett's mostly-copying garbage collector to manage both transient objects and resident persistent objects, and to compute the reachability closure necessary for stabilization of the persistent heap. It has been implemented in our prototype of reachability-based persistence for Modula-3, yielding performance competitive with that of comparable, but non-orthogonal, persistent variants of C++. Experimental results, using the 007 object database benchmarks, reveal that the mostly-copying approach offers a straightforward path to efficient orthogonal persistence in these uncooperative environments. The results also characterize the performance of persistence implementations based on virtual memory protection primitives.
A note introducing syntax through semantic routines
Authors: Ruf J. A.
Published: November 2005

Historically, semantic routines have been treated within the confines of code generation rather than as an issue in grammar construction. The point of this paper is to illustrate when and how semantic routine placement within a grammar changes from a semantic construction to a syntactical construction.
Online-and-offline partial evaluation (extended abstract)
Authors: Sumii Eijiro , Kobayashi Naoki
Published: November 2005

This paper presents a hybrid method of partial evaluation (PE), which combines the power of online PE and the efficiency of offline PE, for a typed strict functional language. We begin with a naive online partial evaluator, and make it efficient without sacrificing its power. To this end, we (1) use state (instead of continuation) for let-insertion, (2) take a so-called cogen approach, and (3) decrease unnecessary computations—such as unnecessary let-insertions and unused values/expressions—with a type-based use analysis, which subsumes various monovariant binding-time analyses. Our method yields the same residual programs as the naive online partial evaluator, modulo inlining of redundant let-bindings. We implemented and compared our method and existing methods, both online and offline. Experiments show that our method is at least twice as fast as any other method (e.g., more than 7 times as fast as Thiemann's cogen approach to offline PE in the specialization of the power function, thanks to the reduction of unnecessary let-insertions) when they yield equivalent residual programs.
A sound reduction semantics for untyped CBN multi-stage computation. Or, the theory of MetaML is non-trival
Authors: Taha Walid
Published: November 2005

A multi-stage computation is one involving more than one stage of execution. MetaML is a language for programming multi-stage computations. Previous studies presented big-step semantics, categorical semantics, and sound type systems for MetaML. In this paper, we report on a confluent and sound reduction semantics for untyped call-by name (CBN) MetaML. The reduction semantics can be used to formally justify some optimization performed by a CBN MetaML implementation. The reduction semantics demonstrates that non-trivial equalities hold for object-code, even in the untyped setting. The paper also emphasizes that adding intensional analysis (that is, taking-apart object programs) to MetaML remains an interesting open problem.
Operating systems specialization (invited talk) (abstract only)
Authors: Walpole Jonathan
Published: November 2005

This talk will present a systems-centric view of the opportunities, effectiveness, and challenges of applying specialization techniques to operating systems. The first part of the talk will focus on our experiences using manual and then tool-assisted specialization in the systematic optimization of legacy operating systems software. These experiences were gained in the Synthetix project which explored the use of static, dynamic and incremental optimistic specialization in a variety of operating system contexts, including file system calls in HP-UX, Linux signal delivery, Berkeley packet filter processing, and Sun RPC. The second part of the talk will focus on the lessons learned in Synthetix, the implications for systems, and the key opportunities and challenges for future research.

Jonathan Walpole is a Professor in the Computer Science and Engineering Department at Oregon Graduate Institute. His research interests are in the area of adaptive systems software and its application in distributed, mobile, multimedia computing environments. His work has focused on quality of service specification, adaptive resource management and dynamic specialization for enhanced performance, survivability and evolvability of large software systems.
Program analysis with partial transfer functions
Authors: Murphy Brian R. , Lam Monica S.
Published: November 2005

Program analyses used in compilers commonly use a transfer function (TF) to summarize the input/output behavior of a procedure or region, speeding convergence of analysis of the surrounding region or program. A partial transfer function (PTF) summarizes input/output behavior for only a subset of the possible inputs. In many cases, an exact characterization of input/output behavior is possible for the contexts occurring in a given program, even when a concise and exact total summary would not be feasible. In other cases, an approximate PTF can be used which, while not exact, is more precise than would be possible with a total approximation.

As demonstrated by prior work in a flow- and context-sensitive pointer alias analysis, PTFs are effective in speeding the convergence of program analysis involving higher-order functions and complex transfer functions that cannot easily be summarized.

This paper presents a formal definition of partial transfer functions and introduces a general framework that enables data flow systems with complex transfer functions to be decomposed into simpler partial transfer functions. This paper provides a foundation that will allow the further development of the PTF concept, as well as enabling application to many more program analyses.
Basic compiler algorithms for parallel programs
Authors: Lee Jaejin , Padua David A. , Midkiff Samuel P.
Published: November 2005

Traditional compiler techniques developed for sequential programs do not guarantee the correctness (sequential consistency) of compiler transformations when applied to parallel programs. This is because traditional compilers for sequential programs do not account for the updates to a shared variable by different threads. We present a concurrent static single assignment (CSSA) form for parallel programs containing cobegin/coend and parallel do constructs and post/wait synchronization primitives. Based on the CSSA form, we present copy propagation and dead code elimination techniques. Also, a global value numbering technique that detects equivalent variables in parallel programs is presented. By using global value numbering and the CSSA form, we extend classical common subexpression elimination, redundant load/store elimination, and loop invariant detection to parallel programs without violating sequential consistency. These optimization techniques are the most commonly used techniques for sequential programs. By extending these techniques to parallel programs, we can guarantee the correctness of the optimized program and maintain single processor performance in a multiprocessor environment.
SUIF Explorer
Authors: Liao Shih-Wei , Diwan Amer , Bosch Robert P. , Ghuloum Anwar , Lam Monica S.
Published: November 2005

The SUIF Explorer is an interactive parallelization tool that is more effective than previous systems in minimizing the number of lines of code that require programmer assistance. First, the interprocedural analyses in the SUIF system is successful in parallelizing many coarse-grain loops, thus minimizing the number of spurious dependences requiring attention. Second, the system uses dynamic execution analyzers to identify those important loops that are likely to be parallelizable. Third, the SUIF Explorer is the first to apply program slicing to aid programmers in interactive parallelization. The system guides the programmer in the parallelization process using a set of sophisticated visualization techniques.This paper demonstrates the effectiveness of the SUIF Explorer with three case studies. The programmer was able to speed up all three programs by examining only a small fraction of the program and privatizing a few variables.
Evaluation of predicated array data-flow analysis for automatic parallelization
Authors: Moon Sungdo , Hall Mary W.
Published: November 2005

This paper presents an evaluation of a new analysis for parallelizing compilers called
predicated array data-flow analysis
. This analysis extends array data-flow analysis for parallelization and privatization to associate predicates with data-flow values. These predicates can be used to derive conditions under which dependences can be eliminated or privatization is possible. These conditions can be used both to enhance compile-time analysis and to introduce run-time tests that guard safe execution of a parallelized version of a computation.As compared to previous work that combines predicates with array data-flow analysis, our approach is distinguished by two features: (1) it derives low-cost, run-time parallelization tests; and, (2) it incorporates
predicate embedding
and
predicate extraction
, which translate between the domain of predicates and data-flow values to derive more precise analysis results. We present extensive experimental results across three benchmark suites and one additional program, demonstrating that predicated array data-flow analysis parallelizes more than 40% of the remaining inherently parallel loops left unparallelized by the SUIF compiler and that it yields improved speedups for 5 programs.
MagPIe
Authors: Kielmann Thilo , Hofman Rutger F. H. , Bal Henri E. , Plaat Aske , Bhoedjang Raoul A. F.
Published: November 2005

Writing parallel applications for computational grids is a challenging task. To achieve good performance, algorithms designed for local area networks must be adapted to the differences in link speeds. An important class of algorithms are collective operations, such as broadcast and reduce. We have developed M
AG
PI
E
, a library of collective communication operations optimized for wide area systems. M
AG
PI
E
's algorithms send the minimal amount of data over the slow wide area links, and only incur a single wide area latency. Using our system, existing MPI applications can be run unmodified on geographically distributed systems. On moderate cluster sizes, using a wide area latency of 10 milliseconds and a bandwidth of 1 MByte/s, M
AG
PI
E
executes operations up to 10 times faster than MPICH, a widely used MPI implementation; application kernels improve by up to a factor of 4. Due to the structure of our algorithms, M
AG
PI
E
's advantage increases for higher wide area latencies.
Using Java reflection to automate extension language parsing
Authors: Parson Dale
Published: November 2005

An extension language is an interpreted programming language designed to be embedded in a domain-specific framework. The addition of domain-specific primitive operations to an embedded extension language transforms that vanilla extension language into a domain-specific language. The LUxWORKS processor simulator and debugger from Lucent uses Tcl as its extension language. After an overview of extension language embedding and LUxWORKS experience, this paper looks at using Java reflection and related mechanisms to solve three limitations in extension language - domain framework interaction. The three limitations are gradual accumulation of ad hoc interface code connecting an extension language to a domain framework, over-coupling of a domain framework to a specific extension language, and inefficient command interpretation.

Java reflection consists of a set of programming interfaces through which a software module in a Java system can discover the structure of classes, methods and their associations in the system. Java reflection and a naming convention for primitive domain operations eliminate ad hoc interface code by supporting recursive inspection of a domain command interface and translation of extension language objects into domain objects. Java reflection, name-based dynamic class loading, and a language-neutral extension language abstraction eliminate language over-coupling by transforming the specific extension language into a runtime parameter. Java reflection and command objects eliminate inefficiency by bypassing the extension language interpreter for stereotyped commands. Overall, Java reflection helps to eliminate these limitations by supporting reorganization and elimination of handwritten code, and by streamlining interpretation.
Declarative specification of data-intensive Web sites
Authors: Fernández Mary , Suciu Dan , Tatarinov Igor
Published: November 2005

Integrated information systems are often realized as
data-intensive Web sites,
which integrate data from multiple data sources. We present a system, called STRUDEL, for specifying and generating data-intensive Web sites. STRUDEL separates the tasks of accessing and integrating a site's data sources, building its structure, and generating its HTML representation. STRUDEL's declarative query language, called StruQL, supports the first two tasks. Unlike ad-hoc database queries, a StruQL query is a software artifact that must be extensible and reusable To support more modular and reusable site definition queries, we extend StruQL with functions and describe how the new language, FunStruQL, better supports common site-engineering tasks, such as choosing a strategy for generating the site's pages dynamically and/or statically To substantiate STRUDEL's benefits, we describe the re-engineering of a production Web site using FunStruQL and show that the new site is smaller, more reusable, and unlike the original site, can be analyzed and optimized.
BlurFit
Authors: McClain D.
Published: November 2005

Functional languages offer numerous advantages when applied to scientific programming. Significant reductions in the complexity of the problem expression are possible. The speed of execution is competitive with native C code. The use of a functional programming style allows the investigator to concentrate more on the scientific problem and less on its expression in a computer language. These characteristics were clearly demonstrated in our version of the
BlurFit
algorithm written in the OCaml language.
Codebugger
Authors: Xie Gaoyan , Xu Yongsen , Li Yu , Li Qian
Published: November 2005

Debugging of large-scale systems are essentially cooperative and need collaboration of group developers. However, most existing debugging tools are for single developer. With single-user tools, only one developer can operate the debugging process while others are frequently requested to gather before the screen of a single computer on solving problems, which makes error location and correction so inconvenient and inefficient. We developed Codebugger---a cooperative debugging tool for Java that supports group developers to participate in one debugging session and cooperate on solving problems at the same time. This paper introduces principles of cooperative software tools, the architecture of Codebugger and discusses some technical issues concerning its implementation.
Curriculum 2001 draft found lacking in programming languages
Authors: Bruce Kim B.
Published: November 2005

In March, 2000, the ACM-IEEE CS Curriculum 2001 committee released a "strawman" version of their proposed curricular recommendations. Those recommendations give short shrift to programming languages compared to previous curricula, and the material on programming language is also significantly reduced from the Programming Languages Knowledge Area Focus Group's recommendations. This document reports on the recommendations of the focus group and the curriculum committee's proposals on programming languages. We urge those interested in undergraduate computing curricula to write to us and the full Curriculum 2001 Committee to present their views on what programming languages material should be required of all undergraduates. The curriculum report will be finalized by the end of the year, so prompt action is necessary to have an impact on the process.
Quicksilver
Authors: Serrano Mauricio , Bordawekar Rajesh , Midkiff Sam , Gupta Manish
Published: November 2005

This paper presents the design and implementation of the Quicksilver
1
quasi-static compiler for Java. Quasi-static compilation is a new approach that combines the benefits of static and dynamic compilation, while maintaining compliance with the Java standard, including support of its dynamic features. A quasi-static compiler relies on the generation and reuse of persistent code images to reduce the overhead of compilation during program execution, and to provide identical, testable and reliable binaries over different program executions. At runtime, the quasi-static compiler adapts pre-compiled binaries to the current JVM instance, and uses dynamic compilation of the code when necessary to support dynamic Java features. Our system allows interprocedural program optimizations to be performed while maintaining binary compatibility. Experimental data obtained using a preliminary implementation of a quasi-static compiler in the Jalapeño JVM clearly demonstrates the benefits of our approach: we achieve a runtime compilation cost comparable to that of baseline (fast, non-optimizing) compilation, and deliver the runtime program performance of the highest optimization level supported by the Jalapeño optimizing compiler. For the SPECjvm98 benchmark suite, we obtain a factor of 104 to 158 reduction in the runtime compilation overhead relative to the Jalapeño optimizing compiler. Relative to the
better
of the baseline and the optimizing Jalapeño compilers, the overall performance (taking into account both runtime compilation and execution costs) is increased by 9.2% to 91.4% for the SPECjvm98 benchmarks with size 100, and by 54% to 356% for the (shorter running) SPECjvm98 benchmarks with size 10.
Sealed calls in Java packages
Authors: Zaks Ayal , Feldman Vitaly , Aizikowitz Nava
Published: November 2005

Determining the potential targets of virtual method invocations is essential for inter-procedural optimizations of object-oriented programs. It is generally hard to determine such targets accurately. The problem is especially difficult for dynamic languages such as Java, because additional targets of virtual calls may appear at runtime. Current mechanisms that enable inter-procedural optimizations for dynamic languages, repeatedly validate the optimizations at runtime. This paper addresses this predicament by proposing a novel technique for conservative devirtualization analysis, which applies to a significant number of virtual calls in Java programs. Unlike previous work, our technique requires neither whole program analysis nor runtime information, and incurs no runtime overhead. Our solution is very efficient to compute and is based on a newly introduced, seemingly unrelated security feature of Java file archives. On average, our analysis "seals" (safely devirtualizes) about 39% of the virtual calls (to non-final methods) that appear in SPECjvm98 programs, and about 29% of the calls invoked while executing these programs. In the runtime library rt.jar, about 10% of the packages contain a significant percentage (20--60%) of sealed calls, with a total average of about 8.5%. Most of these calls are also shown to be monomorphic, a fact which can be safely exploited by aggressive inter-procedural optimizations such as direct inlining. These results indicate that our technique has a strong potential for enhancing the analysis and optimization of Java programs.
Scalable propagation-based call graph construction algorithms
Authors: Tip Frank , Palsberg Jens
Published: November 2005

Propagation-based call graph construction algorithms have been studied intensively in the 199Os, and differ primarily in the number of sets that are used to approximate run-time values of expressions. In practice, algorithms such as RTA that use a single set for the whole program scale well. The scalability of algorithms such as 0-CFA that use one set per expression remains doubtful.In this paper, we investigate the design space between RTA and 0-CFA. We have implemented various novel algorithms in the context of
Jax
, an application extractor for Java, and shown that they all scale to a 325,000-line program. A key property of these algorithms is that they do not analyze values on the run-time stack, which makes them efficient and easy to implement. Surprisingly, for detecting unreachable methods, the inexpensive RTA algorithm does almost as well as the seemingly more powerful algorithms. However, for determining call sites with a single target, one of our new algorithms obtains the current best tradeoff between speed and precision.
An efficient class and object encoding
Authors: Glew Neal
Published: November 2005

An object encoding translates a language with object primitives to one without. Similarly, a class encoding translates classes into other primitives. Both are important theoretically for comparing the expressive power of languages and for transferring results from traditional languages to those with objects and classes. Both are also important foundations for the implementation of object-oriented languages as compilers typically include a phase that performs these translations.This paper describes a language with a primitive notion of classes and objects and presents an encoding of this language into one with records and functions. The encoding uses two techniques often used in compilers for single-inheritance class-based object-oriented languages: the self-application semantics and the method-table technique. To type the output of the encoding, the encoding uses a new formulation of self quantifiers that is more powerful than previous approaches.
An Aristotelian understanding of object-oriented programming
Authors: Rayside Derek , Campbell Gerard T.
Published: November 2005

The folklore of the object-oriented programming community at times maintains that object-oriented programming has drawn inspiration from philosophy, specifically that of Aristotle. We investigate this relation, first of all, in the hope of attaining a better understanding of object-oriented programming and, secondly, to explain aspects of Aristotelian logic to the computer science research community (since it differs from first order predicate calculus in a number of important ways). In both respects we endeavour to contribute to the theory of objects, albeit in a more philosophical than mathematical fashion.
An object-oriented programming language for developing distributed software
Authors: Lujun Shang , Zhongxiu Sun
Published: November 2005

CLUSTER 86 is an object-oriented programming language. Everything in CLUSTER 86 falls into the category of object concepts. Objects are defined in two abstraction levels -- the cluster level and the type level. A type defines a set of objects whereas a cluster specifies a collection of types, and clusters are described in a tree structure.The language finds its justification in developing distributed operating systems. The language itself does not introduce any facilities for distributed programming, but it has the ability of specifing all kinds of distributed activity models. Thus the language users may build their integrated distributed environments out of scratch from the specifications of various hardware resources, to the specifications of miscellaneous high level models that pertain to their research fields and cater to their programming customs.
Designing computer systems with MEMS-based storage
Authors: Schlosser Steven W. , Griffin John Linwood , Nagle David F. , Ganger Gregory R.
Published: November 2005

For decades the RAM-to-disk memory hierarchy gap has plagued computer architects. An exciting new storage technology based on microelectromechanical systems (MEMS) is poised to fill a large portion of this performance gap, significantly reduce system power consumption, and enable many new applications. This paper explores the system-level implications of integrating MEMS-based storage into the memory hierarchy. Results show that standalone MEMS-based storage reduces I/O stall times by 4--74X over disks and improves overall application runtimes by 1.9--4.4X. When used as on-board caches for disks, MEMS-based storage improves I/O response time by up to 3.5X. Further, the energy consumption of MEMS-based storage is 10--54X less than that of state-of-the-art low-power disk drives. The combination of the high-level physical characteristics of MEMS-based stor-age (small footprints, high shock tolerance) and the ability to directly integrate MEMS-based storage with processing leads to such new applications as portable gigabit storage systems and ubiquitous active storage nodes.
FLASH vs. (simulated) FLASH
Authors: Gibson Jeff , Kunz Robert , Ofelt David , Horowitz Mark , Hennessy John , Heinrich Mark
Published: November 2005

Simulation is the primary method for evaluating computer systems during all phases of the design process. One significant problem with simulation is that it rarely models the system exactly, and quantifying the resulting simulator error can be difficult. More importantly, architects often assume without proof that although their simulator may make inaccurate absolute performance predictions, it will still accurately predict architectural trends.This paper studies the source and magnitude of error in a range of architectural simulators by comparing the simulated execution time of several applications and microbenchmarks to their execution time on the actual hardware being modeled. The existence of a hardware gold standard allows us to find, quantify, and fix simulator inaccuracies. We then use the simulators to predict architectural trends and analyze the sensitivity of the results to the simulator configuration. We find that most of our simulators predict trends accurately, as long as they model all of the important performance effects for the application in question. Unfortunately, it is difficult to know what these effects are without having a hardware reference, as they can be quite subtle. This calls into question the value, for architectural studies, of highly detailed simulators whose characteristics are not carefully validated against a real hardware design.
Evaluating design alternatives for reliable communication on high-speed networks
Authors: Bhoedjang Raoul A. F. , Verstoep Kees , Rühl Tim , Bal Henri E. , Hofman Rutger F. H.
Published: November 2005

We systematically evaluate the performance of five implementations of a single, user-level communication interface. Each implementation makes different architectural assumptions about the reliability of the network hardware and the capabilities of the network interface. The implementations differ accordingly in their division of protocol tasks between host software, network-interface firmware, and network hardware. Using microbenchmarks, parallel-programming systems, and parallel applications, we assess the performance impact of different protocol decompositions. We show how moving protocol tasks to a relatively slow network interface yields both performance advantages and disadvantages, depending on the characteristics of the application and the underlying parallel-programming system. In particular, we show that a communication system that assumes highly reliable network hardware and that uses network-interface support to process multicast traffic performs best for all applications.