bluuebunny/crossref_metadata_2025_split huggingface dataset:
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.
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.
Effective synchronization removal for Java
Authors: Ruf Erik 
Published: November 2005

We present a new technique for removing unnecessary synchronization operations from statically compiled Java programs. Our approach improves upon current efforts based on escape analysis, as it can eliminate synchronization operations even on objects that escape their allocating threads. It makes use of a compact, equivalence-class-based representation that eliminates the need for fixed point operations during the analysis.
We describe and evaluate the performance of an implementation in the
Marmot native Java compiler. For the benchmark programs examined, the optimization removes 100% of the dynamic synchronization operations in single-threaded programs, and 0-99% in multi-threaded programs, at a low cost in additional compilation time and code growth.
On effectiveness of GC in Java
Authors: Shaham Ran , Kolodner Elliot K. , Sagiv Mooly 
Published: November 2005

We study the effectiveness of garbage collection (GC) algorithms by measuring the time difference between the actual collection time of an object and the potential earliest collection time for that object. Our ultimate goal is to use this study in order to develop static analysis techniques that can be used together with GC to allow earlier reclamation of objects. The results may also be used to pinpoint application source code that could be rewritten in a way that would allow more timely GC.
Specifically, we compare the objects reachable from the root set to the ones that are actually used again. The idea is that GC could reclaim unused objects even if they are reachable from the root set. Thus, our experiments indicate a kind of upper bound on storage savings that could be achieved. We also try to characterize these objects in order to understand the potential benefits of various static analysis algorithms.
The Java Virtual Machine (JVM) was instrumented to measure objects that are reachable, but not used again, and to characterize these objects. Experimental results are shown for the SPECjvm98 benchmark suite. The potential memory savings for these benchmarks range from 23% to 74%.
Thread-specific heaps for multi-threaded programs
Authors: Steensgaard Bjarne 
Published: November 2005

Garbage collection for a multi-threaded program typically involves either stopping all threads while doing the collection or involves copious amounts of synchronization between threads. However, a lot of data is only ever visible to a single thread, and such data should ideally be collected without involving other threads.
Given an escape analysis, a memory management system may allocate thread-specific data in thread-specific heaps and allocate shared data in a shared heap. Garbage collection of data in a thread-specific heaps can be done independent of other threads and of data in their thread-specific heaps. For multi-threaded programs, thread-specific heaps allow reduced garbage collection latency for active threads. On multi-processor computers, thread-specific heaps allow concurrent garbage collection of different thread-specific heaps with minimal synchronization overhead.
We present an escape analysis and a sample memory management system using thread-specific heaps.
Java without the coffee breaks
Authors: Bacon David F. , Attanasio Clement R. , Lee Han B. , Rajan V. T. , Smith Stephen 
Published: November 2005

The deployment of Java as a concurrent programming language has created a critical need for high-performance, concurrent, and incremental multiprocessor garbage collection. We present the
Recycler
, a fully concurrent pure reference counting garbage collector that we have implemented in the Jalapeño Java virtual machine running on shared memory multiprocessors.

While a variety of multiprocessor collectors have been proposed and some have been implemented, experimental data is limited and there is little quantitative basis for comparison between different algorithms. We present measurements of the Recycler and compare it against a non-concurrent but parallel load-balancing mark-and-sweep collector (that we also implemented in Jalapeño), and evaluate the classical tradeoff between response time and throughput.
When processor or memory resources are limited, the Recycler runs at about 90% of the speed of the mark-and-sweep collector. However, with an extra processor to run collection and with a moderate amount of memory headroom, the Recycler is able to operate without ever blocking the mutators and achieves a maximum measured mutator delay of only 2.6 milliseconds for our benchmarks. End-to-end execution time is usually within 5%.
Automatic predicate abstraction of C programs
Authors: Ball Thomas , Majumdar Rupak , Millstein Todd , Rajamani Sriram K. 
Published: November 2005

Model checking has been widely successful in validating and debugging designs in the hardware and protocol domains. However, state-space explosion limits the applicability of model checking tools, so model checkers typically operate on abstractions of systems.
Recently, there has been significant interest in applying model checking to software. For infinite-state systems like software, abstraction is even more critical. Techniques for abstracting software are a prerequisite to making software model checking a reality.

We present the first algorithm to automatically construct a
predicate abstraction
of programs written in an industrial programming language such as C, and its implementation in a tool — C2BP. The C2BP tool is part of the SLAM toolkit, which uses a combination of predicate abstraction, model checking, symbolic reasoning, and iterative refinement to statically check temporal safety properties of programs.

Predicate abstraction of software has many applications, including detecting program errors, synthesizing program invariants, and improving the precision of program analyses through predicate sensitivity. We discuss our experience applying the C2BP predicate abstraction tool to a variety of problems, ranging from checking that list-manipulating code preserves heap invariants to finding errors in Windows NT device drivers.
Morphable Cache Architectures
Authors: Kadayif I. , Kandemir M. , Vijaykrishnan N. , Irwin M. J. , Ramanujam J. 
Published: November 2005

Computer architects have tried to mitigate the consequences of high memory latencies using a variety techniques. An example of these techniques is multi-level caches to counteract the latency that results from having a memory that is slower than the processor. Recent research has demonstrated that compiler optimizations that modify data layouts and restructure computation can be successful in improving memory system performance. However, in many cases, working with a fixed cache configuration prevents the application/compiler from obtaining the maximum performance. In addition, prompted by demands in portability, long battery life, and low-cost packaging, the computer industry has started viewing energy and power as decisive design factors, along with performance and cost. This makes the job of the compiler/user even more difficult as one needs to strike a balance between low power/energy consumption and high performance. Consequently, adapting the code to the underlying cache/memory hierarchy is becoming more and more difficult.
In this paper, we take an alternate approach and attempt to adapt the cache architecture to the software needs. We focus on array-dominated applications and measure the potential benefits that could be gained from a morphable (reconfigurable) cache architecture. Our results show that not only different applications work best with different cache configurations, but also that different loop nests in a given application demand different configurations. Our results also indicate that the most suitable cache configuration for a given application or a single nest depends strongly on the objective function being optimized. For example, minimizing cache memory energy requires a different cache configuration for each nest than an objective which tries to minimize the overall memory system energy. Based on our experiments, we conclude that fine-grain (loop nest-level) cache configuration management is an important step for a solution to the challenging architecture/software tradeoffs awaiting system designers in the future.
Issues in the design of object-oriented database programming languages
Authors: Bloom Toby , Zdonik Stanley B. 
Published: November 2005

We see a trend toward extending object-oriented languages in the direction of databases, and, at the same time, toward extending database systems with object-oriented ideas. On the surface, these two activities seem to be moving in a consistent direction. However, at a deeper level, we see difficulties that may inhibit their ending up at the same point. We feel that many of these difficulties are a result of the underlying assumptions that are inherent in the fields of programming language and database systems research. Many of these assumptions are historical and contribute to a set of cultural biases that often prevent the two communities from interacting as effectively as possible.
The purpose of this paper is to try to uncover some of the cultural presuppositions that have inhibited development of a fully integrated database programming language. We have identified database and language features that seem to be difficult to reconcile. We try to uncover the basic problems in these two areas that these features were intended to solve. In order to resolve these problems, we attempt to distinguish fundamental differences from historical artifacts.
Expression optimization using unary complement operators
Authors: Frailey Dennis J. 
Published: November 2005

For purposes of code optimization there are two basic philosophies of expression analysis: one approach would attempt to do a relatively complete analysis, detecting all redundancies which are logically possible. The other approach would aim at those things which are easily detected and/or highly likely to occur. This paper gives a set of algorithms which derive from the latter philosophy but which are based on general properties rather than specific facts about a particular language or machine.
The first section of the paper gives details of a notation used for describing code and defining algorithms. The most significant feature of this notation is that it allows operands to be complemented by any number of “complement operators”. This is done because most of the algorithms make frequent use of the properties of such operators. The second section describes a canonical form for expressions and a series of algorithms based on this form and the properties of complement operators. There are various facets of compiler structure which might bear on the exact usage of these algorithms. Although such considerations are not part of the scope of this paper, occasional comments are made about the relationship of an algorithm to other parts of a compiler. The third section contains a discussion of how these algorithms would fit within an overall optimizer structure.
CDC 6600/7600 optimization
Authors: Zwakenberg Richard G. 
Published: November 2005

Efficient use of the CDC 6600/7600 computers requires maximum utilization of the parallelism (6600/7600) and pipeline (7600) features of the functional units and the ability to perform iterative execution within a minimal number of machine words (6600/7600).
Factors which must be taken into consideration when producing efficient object codes are: (1) The need for compression of code generated for loop structures, and (2) The criteria concerning instruction issue and execution times.
The addition of an optimization pass to the LRLTRAN compiler has allowed the LRLTRAN language programmer to attain the maximum potential speeds of the 6600/7600 computers.
Software design with invocation diagram
Authors: Denil N. J. 
Published: November 2005

This paper describes a medium being developed for abstraction and expression of program structure. The medium is to be used to represent programs during the design process; It forms the basis for their implementation.
The following point of view is adopted. Program design is an iterative, trial-and-error process, in which a basic solution to part of the problem is refined, added to, and modified into a complete solution. The final result should be well-structured in the sense described by Dijkstra (1) in order for the designer to understand the program sufficiently to be confident in its correctness.
The Paralyzer
Authors: Presberg David L. 
Published: November 2005

The ILLIAC IV Fortran compiler's Parallelism Analyzer and Synthesizer (mnemonicized as the Paralyzer) detects computations in Fortran DO loops which can be performed in parallel. It is a step of the compiling process which lies between source language parsing and target code generation, and as such can be considered as a high-level optimization step specific to the ILLIAC architecture. The Paralyzer performs its transformations within the Intermediate Language tables of the compiler. The parallel execution constructs introduced into the user's program are those which can be expressed in the extended Fortran language, IVTRAN, the source language of the compiler [1]. With a decompiler from the Intermediate Language to IVTRAN source, the Paralyzer can act as a source-to-source translater.
Some pertinent characteristics of the ILLIAC IV motivate the parallelism detection methods employed by the Paralyzer. ILLIAC is in the general class of parallel processors known as array processors. That is to say, it performs identical computations in a lock-step, synchronous fashion over separate data streams. Its computational access to main memory is highly constrained: each of the 64 Processing Units can access directly only a private section of the whole memory. Data can be passed from one Processing Unit to another by a relatively expensive routing instruction. This is executed identically by all Processing Units and passes data a uniform end-around distance in the fixed ordering of the Processing Units. The machine executes most efficiently those computations which are element-by-element operations on vectors or arrays. Thus, the most fruitful sources of parallelism in Fortran programs intended for ILLIAC IV execution are DO loops containing array references with subscripts depending on the DO index variables.
Movement of implicit parallel and vector expressions out of program loops
Authors: Schneck Paul B. 
Published: November 2005

The concept of “interference” is introduced and related to the problem of transforming implicit parallel and vector operations to an explicit form. Statement types and constructs which cause interference are identified. Programming techniques which avoid use of potentially interfering statements result in programs which are better suited for operation on parallel and vector processors.
The analysis of the inhibiting effect of interfering statements on the motion of parallel and vector expressions has been implemented and demonstrated as an addition to an existing compiler which recognizes parallelism implicit in current serial programs.
Managing the development of reliable software
Authors: Williams R. D. 
Published: November 2005

This paper discusses the serious need for improved management methods and software development technology to support the production of truly reliable software and presents experience gained on TRW's Site Defense Program in addressing that need.
The basic theme is simply this: We have attempted to achieve a better understanding of how to specify, design, build and validate reliable software; we have translated that understanding into an integrated and exceptionally disciplined software development methodology; we have used, evaluated and refined the methodology enough to recognize and report substantial early success and continuing progress toward that goal.
Maintenance of the computer sciences teleprocessing system
Authors: Bucher D.E. W. 
Published: November 2005

This paper describes the maintenance and enhancement of the Computer Sciences Teleprocessing System (CSTS) and its component processors. CSTS is the system offered by the INFONET Division of Computer Sciences Corporation to provide nationwide conversational and batch teleprocessing service. In the first section, the organization of the project personnel and major activities of project departments are described. The second section describes the process by which functional enhancements and error corrections are implemented. The final section describes testing techniques and procedures used during implementation.
The project staff is organized into implementation departments and service departments. Implementation departments develop new features of the system, corrections to errors, and improvements in system operation, especially in reduction of software overhead. Implementation departments are organized by system software functions such as operating system (device control, task management, and file management), language processors and data management systems, communications software, and applications. The service departments are system integration, performance analysis, product management and system test. The functions performed by these departments are described. Also described are the system evolution conferences and the periodic review of enhancements by a Change Advisory Board.
During the development of a new version of the system, effective tracking of the status of changed modules is essential. The data base and process used to track new features, error corrections and changed component modules are described. The flow of implemented changes through system integration and system test is delineated, as is the development and verification of change documentation for users, administrators and operations personnel.
The final section of the paper describes the design and documentation of test programs and the organization of test sets. Effective test operations are achieved by using self-checking tests as well as automated test operation and verification. Tests for compliance with functional specifications and for conformity to internal design are described.