bluuebunny/crossref_metadata_2025 huggingface dataset:
Object views
Authors: Lipkind Ilya , Pechtchanski Igor , Karamcheti Vijay
Published: November 2005

Object-based parallel and distributed applications are becoming increasingly popular, driven by the programmability advantages of component technology and a flat shared-object space. However, the flat shared-object space introduces a performance challenge: applications that rely on the transparent coherent caching of objects achieve high performance only on tightly coupled parallel machines. In distributed environments, the overheads of object caching force application designers to choose other solutions. Consequently, most applications sacrifice programmability, relying instead on either the explicit coherence management of cached objects, or on vastly different middleware abstractions such as multicast and events.

In this paper, we describe object views — language support for efficient object caching in parallel and distributed computations. Object views specify restrictions on
how
computation threads can use an object, providing the underlying implementation with information about the potential side effects of object access, and thereby enabling construction of scalable, low-overhead caching protocols customized to application requirements. We present extensions to the Java programming language for expressing object views, and describe the design and implementation of a translator and run-time system for executing view-augmented Java programs on a distributed cluster of workstations. Experimental results based on a shared whiteboard application demonstrate that view-based object caching can achieve performance superior to multicast- and event-based implementations, while retaining essentially a shared object interface.
Static analysis of large programs (invited talk) (abstract only)
Authors: Das Manuvir
Published: November 2005

Our research group at Microsoft has spent some effort over the last few years attempting to apply static analysis methods to large application programs (over a million lines of code). In the first part of the talk, I will share some of the insights we have gained along the way. The first insight is that the static analysis method of interest must scale to large programs. It must scale in terms of performance, both running time and memory requirements. The interesting complexity metric is average-case behaviour. The analysis must also scale in terms of the quality of information produced. This metric is hard to measure, and depends on the problem to be solved. The second insight is that large commercial applications differ from the benchmark programs typically used in the literature in many ways beyond sheer size: For instance, they routinely circumvent the type system, they make use of every conceivable language feature, they use large shared libraries, they contain some very large automatically generated functions, they define functions with large numbers of call sites, and they include many indirect call sites. All of these characteristics make analysis hard. In particular, they make the implementation of a scalable analysis an exercise in careful engineering.

In the second part of the talk, I will make the claim that it is possible to develop scalable static analysis methods for large programs, using the following approach: First, implement an efficient algorithm, and carefully engineer it to scale. Important requirements are modularity, a complete parser, and some form of garbage collection. Next, identify the conceptual limitations of the efficient algorithm, and examine the test programs to identify common cases or idioms in the code that expose these limitations. Finally, extend the original algorithm in a principled manner to account for these common cases, without compromising performance. I will use my work on pointer analysis of large programs as an example of this approach. The key insight is that it is possible to identify common idioms in the code that are the bottlenecks for efficient algorithms. A scalable static analysis method can be developed if these idioms can be identified and accommodated.
Towards partially evaluating reflection in Java
Authors: Braux Mathias , Noyé Jacques
Published: November 2005

Reflection plays a major role in the programming of generic applications. However, it introduces an interpretation layer which is detrimental to performance. A solution consists of relying on partial evaluation to remove this interpretation layer. This paper deals with improving a standard partial evaluator in order to handle the Java reflection API. The improvements basically consist of taking type information into account when distinguishing between static and dynamic data, as well as introducing two new specialization actions:
reflection actions
. Benchmarks using the serialization framework show the benefits of the approach.
On the logical foundations of staged computation (invited talk)
Authors: Pfenning Frank
Published: November 2005

Dividing a computation into stages and optimizing later phases using information from earlier phases is a familiar technique in algorithm design. In the realm of programming languages, staged computation has found two important realizations: partial evaluation and run-time code generation. A priori, these are fundamentally operational concepts, concerned with how a program executes, but not what it computes.

In this talk we provide a logical foundation for staged computation which is consistent with the operational intuition. We concentrate on run-time code generation which is related to modal logic via an interpretation of constructive proofs as programs. This correspondence yields new insights into issues of language design and leads to a static type system in which staging errors become type errors. We sketch the language PML (for Phased ML), whose design has been directly motivated by our foundational reconstruction, and discuss our ongoing compiler construction effort [1; 2; 3; 4].
Using regular approximations for generalisation during partial evalution
Authors: Gallagher John P. , Peralta Julio C.
Published: November 2005

On-line partial evaluation algorithms include a generalisation step, which is needed to ensure termination. In partial evaluation of logic and functional programs, the usual generalisation operation applied to computation states is the most specific generalisation (
msg
) of expressions. This can cause loss of information, which is especially serious in programs whose computations first build some internal data structure, which is then used to control a subsequent phase of execution - a common pattern of computation. If the size of the intermediate data is unbounded at partial evaluation time then the
msg
will lose almost all information about its structure. Hence the second phase of computation cannot be effectively specialised.

In this paper a generalisation based on regular approximations is presented. Regular approximations are recursive descriptions of term structure closely related to tree automata. A regular approximation of computation states can be built during partial evaluation. The critical point is that when generalisation is performed, the upper bound on regular descriptions can be combined with the
msg
, thus preserving structural information including recursively defined structure. The domain of regular approximations is infinite and hence a widening is incorporated in the generalisation to ensure termination. An algorithm for partial evaluation of logic programs, enhanced with regular approximations, along with some examples of its use will be presented.
Non pair-sharing and freeness analysis through linear refinement
Authors: Levi Giorgio , Spoto Fausto
Published: November 2005

Linear refinement is a technique for systematically constructing abstract domains for program analysis directly from a basic domain representing just the property of interest. This paper uses linear refinement to construct a domain for non pair-sharing and freeness analysis. The resulting domain is strictly more precise than the domain for sharing and freeness analysis defined by Jacobs and Langen. Moreover, it can be used for abstract compilation, while Jacobs and Langen's domain can only be used for abstract interpretation. We provide a representation of the domain, together with algorithms for the abstract operations.
Type-based useless variable elimination
Authors: Kobayashi Naoki
Published: November 2005

Useless variable elimination [25] is a transformation that eliminates variables whose values contribute nothing to the final outcome of a computation. We present a type-based method for useless variable elimination and prove its correctness. The algorithm is a surprisingly simple extension of the usual type reconstruction algorithm. Our method seems more attractive than other methods for useless variable elimination in several respects. First, it is simple, so that the proof of the correctness is clear and the method can be easily extended to deal with a polymorphic language. Second, it is efficient: it runs in time almost linear in the size of an input expression for a simply-typed λ-calculus, while Wand and Siveroni's 0CFA-based method may require a cubic time. Moreover, our transformation is
optimal
in a certain sense among those that preserve well-typedness, both for the simply-typed language and for an ML-style polymorphically-typed language. On the other hand, Wand and Siveroni's method is
not
optimal for the polymophically-typed language.
StackThreads/MP
Authors: Taura Kenjiro , Tabata Kunio , Yonezawa Akinori
Published: November 2005

An implementation scheme of fine-grain multithreading that needs no changes to current calling standards for sequential languages and modest extensions to sequential compilers is described. Like previous similar systems, it performs an asynchronous call as if it were an ordinary procedure call, and detaches the callee from the caller when the callee suspends or either of them migrates to another processor. Unlike previous similar systems, it detaches and connects arbitrary frames generated by off-the-shelf sequential compilers obeying calling standards. As a consequence, it requires neither a frontend preprocessor nor a native code generator that has a builtin notion of parallelism. The system practically works with unmodified GNU C compiler (GCC). Desirable extensions to sequential compilers for guaranteeing portability and correctness of the scheme are clarified and claimed modest. Experiments indicate that sequential performance is not sacrificed for practical applications and both sequential and parallel performance are comparable to Cilk[8], whose current implementation requires a fairly sophisticated preprocessor to C. These results show that efficient asynchronous calls (a.k.a.
future calls
) can be integrated into current calling standard with a very small impact both on sequential performance and compiler engineering.
Automatic parallelization of divide and conquer algorithms
Authors: Rugina Radu , Rinard Martin
Published: November 2005

Divide and conquer algorithms are a good match for modern parallel machines: they tend to have large amounts of inherent parallelism and they work well with caches and deep memory hierarchies. But these algorithms pose challenging problems for parallelizing compilers. They are usually coded as recursive procedures and often use pointers into dynamically allocated memory blocks and pointer arithmetic. All of these features are incompatible with the analysis algorithms in traditional parallelizing compilers.This paper presents the design and implementation of a compiler that is designed to parallelize divide and conquer algorithms whose subproblems access disjoint regions of dynamically allocated arrays. The foundation of the compiler is a flow-sensitive, context-sensitive, and interprocedural pointer analysis algorithm. A range of symbolic analysis algorithms build on the pointer analysis information to extract symbolic bounds for the memory regions accessed by (potentially recursive) procedures that use pointers and pointer arithmetic. The symbolic bounds information allows the compiler to find procedure calls that can execute in parallel without violating the data dependences. The compiler generates code that executes these calls in parallel. We have used the compiler to parallelize several programs that use divide and conquer algorithms. Our results show that the programs perform well and exhibit good speedup.
Compile/run-time support for threaded MPI execution on multiprogrammed shared memory machines
Authors: Tang Hong , Shen Kai , Yang Tao
Published: November 2005

MPI is a message-passing standard widely used for developing high-performance parallel applications. Because of the restriction in the MPI computation model, conventional implementations on shared memory machines map each MPI node to an OS process, which suffers serious performance degradation in the presence of multiprogramming, especially when a space/time sharing policy is employed in OS job scheduling. In this paper, we study compile-time and run-time support for MPI by using threads and demonstrate our optimization techniques for executing a large class of MPI programs written in C. The compile-time transformation adopts thread-specific data structures to eliminate the use of global and static variables in C code. The runtime support includes an efficient point-to-point communication protocol based on a novel lock-free queue management scheme. Our experiments on an SGI Origin 2000 show that our MPI prototype called TMPI using the proposed techniques is competitive with SGI's native MPI implementation in a dedicated environment, and it has significant performance advantages with up to a 23-fold improvement in a multiprogrammed environment.
Predictive analysis of a wavefront application using LogGP
Authors: Sundaram-Stukel David , Vernon Mary K.
Published: November 2005

This paper develops a highly accurate LogGP model of a complex wavefront application that uses MPI communication on the IBM SP/2. Key features of the model include: (1) elucidation of the principal wavefront synchronization structure, and (2) explicit high-fidelity models of the MPI-send and MPI-receive primitives. The MPI-send/receive models are used to derive
L, o
, and
G
from simple two-node micro-benchmarks. Other model parameters are obtained by measuring small application problem sizes on four SP nodes. Results show that the LogGP model predicts, in seconds and with a high degree of accuracy, measured application execution time for large problems running on 128 nodes. Detailed performance projections are provided for very large future processor configurations that are expected to be available to the application developers. These results indicate that scaling beyond one or two thousand nodes yields greatly diminished improvements in execution time, and that synchronization delays are a principal factor limiting the scalability of the application.
Space-time memory
Authors: Ramachandran Umakishore , Nikhil Rishiyur S. , Harel Nissim , Rehg James M. , Knobe Kathleen
Published: November 2005

Realistic interactive multimedia involving vision, animation, and multimedia collaboration is likely to become an important aspect of future computer applications. The scalable parallelism inherent in such applications coupled with their computational demands make them ideal candidates for SMPs and clusters of SMPs. These applications have novel requirements that offer new kinds of challenges for parallel system design.We have designed a programming system called
Stampede
that offers many functionalities needed to simplify development of such applications (such as high-level data sharing abstractions, dynamic cluster-wide threads, and multiple address spaces). We have built Stampede and it runs on clusters of SMPs. To date we have implemented two applications on Stampede, one of which is discussed herein.In this paper we describe a part of Stampede called
Space-Time Memory
(STM). It is a novel data sharing abstraction that enables interactive multimedia applications to manage a collection of time-sequenced data items simply, efficiently, and transparently across a cluster. STM relieves the application programmer from low level synchronization and data communication by providing a high level interface that subsumes buffer management, inter-thread synchronization, and location transparency for data produced and accessed anywhere in the cluster. STM also automatically handles garbage collection of data items that will no longer be accessed by any of the application threads. We discuss ease of use issues for developing applications using STM, and present preliminary performance results to show that STM's overhead is low.
Slicing spreadsheets
Authors: Reichwein James , Rothermel Gregg , Burnett Margaret
Published: November 2005

Spreadsheet languages, which include commercial spreadsheets and various research systems, have proven to be flexible tools in many domain specific settings. Research shows, however, that spreadsheets often contain faults. We would like to provide at least some of the benefits of formal testing and debugging methodologies to spreadsheet developers. This paper presents an integrated testing and debugging methodology for spreadsheets. To accommodate the modeless and incremental development, testing and debugging activities that occur during spreadsheet creation, our methodology is tightly integrated into the spreadsheet environment. To accommodate the users of spreadsheet languages, we provide an interface to our methodology that does not require an understanding of testing and debugging theory, and that takes advantage of the immediate visual feedback that is characteristic of the spreadsheet paradigm.
DSL implementation using staging and monads
Authors: Sheard Tim , Benaissa Zine-el-abidine , Pasalic Emir
Published: November 2005

The impact of Domain Specific Languages (DSLs) on software design is considerable. They allow programs to be more concise than equivalent programs written in a high-level programming languages. They relieve programmers from making decisions about data-structure and algorithm design, and thus allows solutions to be constructed quickly. Because DSL's are at a higher level of abstraction they are easier to maintain and reason about than equivalent programs written in a high-level language, and perhaps most importantly
they can be written by domain experts rather than programmers.

The problem is that DSL implementation is costly and prone to errors, and that high level approaches to DSL implementation often produce inefficient systems. By using two new programming language mechanisms, program staging and monadic abstraction, we can lower the cost of DSL implementations by allowing reuse at many levels. These mechanisms provide the expressive power that allows the construction of many compiler components as reusable libraries, provide a direct link between the semantics and the low-level implementation, and provide the structure necessary to reason about the implementation.
Domain specific embedded compilers
Authors: Leijen Daan , Meijer Erik
Published: November 2005

Domain-specific embedded languages (DSELs) expressed in higher-order, typed (HOT) languages provide a composable framework for domain-specific abstractions. Such a framework is of greater utility than a collection of stand-alone domain-specific languages. Usually, embedded domain specific languages are build on top of a set of domain specific primitive functions that are ultimately implemented using some form of foreign function call. We sketch a general design pattern/or embedding client-server style services into Haskell using a domain specific embedded compiler for the server's source language. In particular we apply this idea to implement Haskell/DB, a domain specific embdedded compiler that dynamically generates of SQL queries from monad comprehensions, which are then executed on an arbitrary ODBC database server.
Verischemelog
Authors: Jennings James , Beuscher Eric
Published: November 2005

Verischemelog
(pronounced with 5 syllables, veruh-scheme-uh-log) is a language and programming environment embedded in Scheme for designing digital electronic hardware systems and for controlling the simulation of these circuits. Simulation is performed by a separate program, often a commercial product.
Verischemelog
compiles to Verilog, an industry standard language accepted by several commercial and public domain simulators.

Because many design elements are easily parameterized, design engineers currently write scripts which generate hardware description code in Verilog. These scripts work by textual substitution, and are typically ad-hoc and quite limited. Preprocessors for Verilog, on the other hand, are hampered by their macro-expansion languages, which support few data types and lack procedures.
Verischemelog
obviates the need for scripts and preprocessors by providing a hardware description language with list-based syntax, and Scheme to manipulate it.

An interactive development environment gives early and specific feedback about errors, and structured access to the compiler and run-time environment provide a high degree of reconfigurability and extensibility of
Verischemelog.
An ada-based object-oriented modeling language
Authors: Dai Guilan , Xu Baowen
Published: November 2005

This paper describes an Ada-based object-oriented modeling language AML which is suitable to model large software systems. AML takes a unique and innovative approach to integrate the object-oriented Ada95-like syntax with formal methods in a modeling language. In the paper, the design philosophies of the language are firstly discussed. Secondly AML fundamental constructs and their inherent relations are analyzed. Thirdly the related work is briefly discussed and the main characteristics of the language are summarized. Finally, an AML program for the elevator control system has been given partly to demonstrate the capability and to illustrate the use of AML.
SEIS++
Authors: Yingjun Li , Jian Lu
Published: November 2005

Predominant industrial practice has evolved from general-purpose class libraries to domain-specific frameworks" and design patterns. Both of them are a means to achieve large-scale reuse by capturing successful software development strategies within a particular context. Design patterns focus on reuse of recurring architectural design themes and mainly consist of predefined design structures that can be used as building blocks to compose the architecture of software system. Together the patterns in a specific domain form a pattern language, which can be used to approach a certain class of problems in the application domain. In this paper, we propose a pattern language SEIS++, a set of design patterns, for seismic tool construction and integration in oil and gas exploration domain. The language uses Tools and Materials as the new design conception to guide domain-specific application development, and to enhance software architecture reusability.
Sources of parallelism in software pipelining loops with conditional branches
Authors: Milicev Dragan , Jovanovic Zoran
Published: November 2005

The subject of this paper is the instruction-level parallelism and the process of software pipelining loops with conditional branches. First, preconditions for treating such loops are introduced, and some effects of existence of conditional instructions and their outcomes that are important for parallelization are analyzed These effects are emphasized and systematized
.
A
small
hybrid JIT for embedded systems
Authors: Manjunath Geetha , Krishnan Venkatesh
Published: November 2005

Just-In-Time (JIT) Compilation is a technology used to improve speed of virtual machines that support dynamic loading of applications. It is better known as a technique that accelerates Java programs. Current JIT compilers are either huge in size or compile complete methods of the application requiring large amounts of memory for their functioning. This has made Java Virtual Machines for embedded systems devoid of JIT compilers. This paper explains a simple technique of combining interpretation with compilation to get a hybrid interpretation strategy. It also describes a new code generation technique that works using its self-code. The combination gives a JIT compiler that is very small (10K) and suitable for Java Virtual Machines for embedded systems.
A hybrid state machine notation for component specification
Authors: Sakharov Alexander
Published: November 2005

A wide range of software units can be classified as state machines. We extend conventional state machine notations by adding regular expressions of events and unions of source states to state machine transitions. Reusable software components are generated from these extended state machine specifications. Component specification and generation are illustrated in Java.
The security problem of nested classes
Authors: Yu Li , Gaoyan Xie , Yongsen Xu , Yi Yang
Published: November 2005

This paper mainly discusses the security problem of OO languages caused by the introduction of the nested class mechanism. Firstly, by analyzing various cases concerning about nested classes instances and their owner objects in detail, we illustrate the invalid owner problem arising from the difference between the lifetime of nested class instances and their owner objects. Then a solution to solve this problem is presented. Finally, a conclusion is drawn that the nested class mechanism should be suitable for the languages in which user defined classes are only used to declare dynamically created objects and which have garbage collection support, such as Java, not for the languages in which classes are allowed to declare static objects or local objects and which have no garbage collection support, such as C++.
Semantics of programming languages
Authors: Heering Jan , Klint Paul
Published: November 2005

By paying more attention to semantics-based tool generation, programming language semantics can significantly increase its impact. Ultimately, this may lead to "Language Design Assistants" incorporating substantial amounts of semantic knowledge.
Overcoming the challenges to feedback-directed optimization (Keynote Talk)
Authors: Smith Michael D.
Published: November 2005

Feedback-directed optimization (FDO) is a general term used to describe any technique that alters a program's execution based on tendencies observed in its present or past runs. This paper reviews the current state of affairs in FDO and discusses the challenges inhibiting further acceptance of these techniques. It also argues that current trends in hardware and software technology have resulted in an execution environment where immutable executables and traditional static optimizations are no longer sufficient. It explains how we can improve the effectiveness of our optimizers by increasing our understanding of program behavior, and it provides examples of temporal behavior that we can (or could in the future) exploit during optimization.
Machine-adaptable dynamic binary translation
Authors: Ung David , Cifuentes Cristina
Published: November 2005

Dynamic binary translation is the process of translating and optimizing executable code for one machine to another at runtime, while the program is “executing” on the target machine.

Dynamic translation techniques have normally been limited to two particular machines; a competitor's machine and the hardware manufacturer's machine. This research provides for a more general framework for dynamic translations, by providing a framework based on specifications of machines that can be reused or adapted to new hardware architectures. In this way, developers of such techniques can isolate design issues from machine descriptions and reuse many components and analyses.

We describe our dynamic translation framework and provide some initial results obtained by using this system.
Domain-specific languages
Authors: van Deursen Arie , Klint Paul , Visser Joost
Published: November 2005

We survey the literature available on the topic of domain-specific languages as used for the construction and maintenance of software systems. We list a selection of 75 key publications in the area, and provide a summary for each of the papers. Moreover, we discuss terminology, risks and benefits, example domain-specific languages, design methodologies, and implementation techniques.
Lazy lists in C++
Authors: Schupp Sibylle
Published: November 2005

Languages that support lazy evaluation allow computations with "infinite" data structures (lazy lists); C++ is not among these languages. Using an idiom of generic programming in C++, template metaprogramming, this paper shows how to provide lazy lists nevertheless.
Object-oriented real-time concurrency
Authors: Buhr Peter A. , Harji Ashif S. , Lim Philipp E. , Chen Jiongxiong
Published: November 2005

The primary goal of a real-time system is predictability. Achieving this goal requires
all
levels of the system to work in concert to provide fixed worst-case execution-times. Un-fortunately, many real-time systems are overly restrictive, providing only ad-hoc scheduling facilities and basic concurrent functionality. Ad-hoc scheduling makes developing, verifying, and maintaining a real-time system extremely difficult and time consuming. Basic concurrent functionality forces programmers to develop complex concurrent programs without the aid of high-level concurrency features.Encouraging the use of sophisticated real-time theory and methodology, in conjunction with high-level concurrency features, requires flexibility and extensibility. Giving real-time programmers access to the underlying system data-structures makes it possible to interact with the system to incorporate new ideas and fine-tune specific applications. This paper explores this approach by examining its effect on a selection of crucial real-time issues: real-time monitors, timeouts, dynamic-priority scheduling and basic priority inheritance. The approach is implemented in
μC++
.
Formal specification of CORBA services
Authors: Bastide Rémi , Palanque Philippe , Sy Ousmane , Navarre David
Published: November 2005

CORBA is now established as one of the main contenders in object-oriented middleware. Beyond the definition of this standard for distributed object systems, the Object Management Group (OMG) has specified several object services (Common Object Services, COS) that should foster the interoperability of distributed applications. Based on experiment, the goal of this paper is to show that the OMG's style of specification of the CORBA services is not suited to guarantee that implementers will produce interoperable and substitutable implementations. To illustrate our point, we give an account of an experiment based upon the formal specification of one COS, namely the CORBA Event Service. This formal specification highlights several ambiguities and under-specifications in the OMG document. We then test several commercial and public domain implementations of the CORBA Event Service, in order to assess how the implementers have dealt with these under-specifications. We show that the choices made by the implementers lead to incompatible implementations. We finally suggest a solution to overcome the problem of specification of object services, which satisfies the views of both implementers and users. Specifically, we suggest that the specification of such services be made using a formal description technique, and that implementers be provided with test cases derived from the formal specification.
Middleware object query processing with deferred updates and autonomous sources
Authors: Kiernan Jerry , Carey Michael J.
Published: November 2005

This paper presents a query processing algorithm called DECAF for use in middleware object query systems that are based on the use of an object cache. The DECAF algorithm is designed to work correctly even in the presence of updates to the underlying databases that don't go through the object cache (i.e., even for autonomous data sources that can be updated through legacy applications that do not perform their updates through the middleware object layer). DECAF's query results are consistent with updates performed by such transactions; its results are also consistent with any deferred updates that are present in the object cache but not yet committed at the database server. The DECAF algorithm attempts to push down query predicates to the underlying DBMSs to take advantage of the query processing capabilities of these systems and to reduce the amount of data transferred from these systems to the object cache.
Parametric polymorphism in Java
Authors: Viroli Mirko , Natali Antonio
Published: November 2005

The introduction of parametric polymorphism in Java with translation approaches has been shown to be of considerable interest, allowing the definition of extensions of Java on top of the existing Virtual Machines. Homogeneous translations furthermore, seem to be more useful than heterogeneous, avoiding the continuous increase of library code with redundant information. At this time however, homogeneous approaches aren't as flexible as heterogeneous, with extensions failing to integrate well with base language typing. In this paper, using some of the features of the Core Reflection of Java, we introduce a homogeneous translation in which run-time information about instantiation of type-parameters is carried, allowing full integration of parame-terized types with Java typing. Performance overhead is greatly decreased using a brand new translation technique based on the deferring of the management of type information at load-time. The same power and flexibility of previous heterogeneous approaches is obtained while maintaining homogeneous translation advantages.
A formal specification of Java class loading
Authors: Qian Zhenyu , Goldberg Allen , Coglio Alessandro
Published: November 2005

The Java Virtual Machine (JVM) has a novel and powerful mechanism to support lazy, dynamic class loading according to user-definable policies. Class loading directly impacts type safety, on which the security of Java applications is based. Conceptual bugs in the loading mechanism were found in earlier versions of the JVM that lead to type violations. A deeper understanding of the class loading mechanism, through such means as formal analysis, will improve our confidence that no additional bugs are present.The work presented in this paper provides a formal specification of (the relevant aspects of) class loading in the JVM and proves its type safety. Our approach to proving type safety is different from the usual ones since classes are dynamically loaded and full type information may not be statically available. In addition, we propose an improvement in the interaction between class loading and bytecode verification, which is cleaner and enables lazier loading.
Guava
Authors: Bacon David F. , Strom Robert E. , Tarafdar Ashis
Published: November 2005

We introduce Guava, a dialect of Java whose rules statically guarantee that parallel threads access shared data only through synchronized methods. Our dialect distinguishes three categories of classes: (1) monitors, which may be referenced from multiple threads, but whose methods are accessed serially; (2) values, which cannot be referenced and therefore are never shared; and (3) objects, which can have multiple references but only from within one thread, and therefore do not need to be synchronized. Guava circumvents the problems associated with today's Java memory model, which must define behavior when concurrent threads access shared memory without synchronization.We present an overview of the syntax and the semantic rules of Guava. We discuss how implementations of Guava can exploit these rules to re-enable compiler optimizations inhibited by standard Java. We discuss how compilers for certain multiprocessor architectures can automatically generate certain programming idioms, such as double-check reads, as optimizations of serialized monitors.
Implementation of physical units
Authors: Baldwin Geoff
Published: November 2005

This paper describes an implementation of strong typing with physical units. The typing system of a commercial Pascal compiler was minimally extended to allow compile-time checking of expressions involving physical units to ensure that the familiar semantics of dimensional analysis are not violated. The key concepts and mechanisms are described, as are the differences between ordinary type checking and that for physical units.
MemorIES
Authors: Nanda Ashwini , Mak Kwok-Ken , Sugavanam Krishnan , Sahoo Ramendra K. , Soundararajan Vijayaraghavan , Smith T. Basil
Published: November 2005

Modern system design often requires multiple levels of simulation for design validation and performance debugging. However, while machines have gotten faster, and simulators have become more detailed, simulation speeds have not tracked machine speeds. As a result, it is difficult to simulate realistic problem sizes and hardware configurations for a target machine. Instead, researchers have focussed on developing scaling methodologies and running smaller problem sizes and configurations that attempt to represent the behavior of the real problem. Given the increasing size of problems today, it is unclear whether such an approach yields accurate results. Moreover, although commercial workloads are prevalent and important in today's marketplace, many simulation tools are unable to adequately profile such applications, let alone for realistic sizes.In this paper we present a hardware-based emulation tool that can be used to aid memory system designers. Our focus is on the memory system because the ever-widening gap between processor and memory speeds means that optimizing the memory subsystem is critical for performance. We present the design of the

Memory
I

nstrumentation and

E

mulation

S

ystem (MemorIES). MemorIES is a programmable tool designed using FPGAs and SDRAMs. It plugs into an SMP bus to perform on-line emulation of several cache configurations, structures and protocols while the system is running real-life workloads in real-time, without any slowdown in application execution speed. We demonstrate its usefulness in several case studies, and find several important results. First, using traces to perform system evaluation can lead to incorrect results (off by 100% or more in some cases) if the trace size is not sufficiently large. Second, MemorIES is able to detect performance problems by profiling miss behavior over the entire course of a run, rather than relying on a small interval of time. Finally, we observe that previous studies of SPLASH2 applications using scaled application sizes can result in optimistic miss rates relative to real sizes on real machines, providing potentially misleading data when used for design evaluation.
System architecture directions for networked sensors
Authors: Hill Jason , Szewczyk Robert , Woo Alec , Hollar Seth , Culler David , Pister Kristofer
Published: November 2005

Technological progress in integrated, low-power, CMOS communication devices and sensors makes a rich design space of networked sensors viable. They can be deeply embedded in the physical world and spread throughout our environment like smart dust. The missing elements are an overall system architecture and a methodology for systematic advance. To this end, we identify key requirements, develop a small device that is representative of the class, design a tiny event-driven operating system, and show that it provides support for efficient modularity and concurrency-intensive operation. Our operating system fits in 178 bytes of memory, propagates events in the time it takes to copy 1.25 bytes of memory, context switches in the time it takes to copy 6 bytes of memory and supports two level scheduling. The analysis lays a groundwork for future architectural advances.
Power aware page allocation
Authors: Lebeck Alvin R. , Fan Xiaobo , Zeng Heng , Ellis Carla
Published: November 2005

One of the major challenges of post-PC computing is the need to reduce energy consumption, thereby extending the lifetime of the batteries that power these mobile devies. Memory is a particularly important target for efforts to improve energy efficiency. Memory technology is becoming available that offers power management features such as the ability to put individual chips in any one of several different power modes. In this paper we explore the interaction of page placement with static and dynamic hardware policies to exploit these emerging hardware features. In particular, we consider page allocation policies that can be employed by an informed operating system to complement the hardware power management strategies. We perform experiments using two complementary simulation environments: a trace-driven simulator with workload traces that are representative of mobile computing and an execution-driven simulator with a detailed processor/memory model and a more memory-intensive set of benchmarks (SPEC2000). Our results make a compelling case for a cooperative hardware/software approach for exploiting power-aware memory, with down to as little as 45% of the Energy Delay for the best static policy and 1% to 20% of the Energy Delay for a traditional full-power memory.
Hoard
Authors: Berger Emery D. , McKinley Kathryn S. , Blumofe Robert D. , Wilson Paul R.
Published: November 2005

Parallel, multithreaded C and C++ programs such as web servers, database managers, news servers, and scientific applications are becoming increasingly prevalent. For these applications, the memory allocator is often a bottleneck that severely limits program performance and scalability on multiprocessor systems. Previous allocators suffer from problems that include poor performance and scalability, and heap organizations that introduce false sharing. Worse, many allocators exhibit a dramatic increase in memory consumption when confronted with a producer-consumer pattern of object allocation and freeing. This increase in memory consumption can range from a factor of
P
(the number of processors) to unbounded memory consumption.This paper introduces Hoard, a fast, highly scalable allocator that largely avoids false sharing and is memory efficient. Hoard is the first allocator to simultaneously solve the above problems. Hoard combines one global heap and per-processor heaps with a novel discipline that provably bounds memory consumption and has very low synchronization costs in the common case. Our results on eleven programs demonstrate that Hoard yields low average fragmentation and improves overall program performance over the standard Solaris allocator by up to a factor of 60 on 14 processors, and up to a factor of 18 over the next best allocator we tested.
Symbiotic jobscheduling for a simultaneous mutlithreading processor
Authors: Snavely Allan , Tullsen Dean M.
Published: November 2005

Simultaneous Multithreading machines fetch and execute instructions from multiple instruction streams to increase system utilization and speedup the execution of jobs. When there are more jobs in the system than there is hardware to support simultaneous execution, the operating system scheduler must choose the set of jobs to coscheduleThis paper demonstrates that performance on a hardware multithreaded processor is sensitive to the set of jobs that are coscheduled by the operating system jobscheduler. Thus, the full benefits of SMT hardware can only be achieved if the scheduler is aware of thread interactions. Here, a mechanism is presented that allows the scheduler to significantly raise the performance of SMT architectures. This is done without any advance knowledge of a workload's characteristics, using sampling to identify jobs which run well together.We demonstrate an SMT jobscheduler called SOS. SOS combines an overhead-free sample phase which collects information about various possible schedules, and a symbiosis phase which uses that information to predict which schedule will provide the best performance. We show that a small sample of the possible schedules is sufficient to identify a good schedule quickly. On a system with random job arrivals and departures, response time is improved as much as 17% over a schedule which does not incorporate symbiosis.
An analysis of operating system behavior on a simultaneous multithreaded architecture
Authors: Redstone Joshua A. , Eggers Susan J. , Levy Henry M.
Published: November 2005

This paper presents the first analysis of operating system execution on a simultaneous multithreaded (SMT) processor. While SMT has been studied extensively over the past 6 years, previous research has focused entirely on user-mode execution. However, many of the applications most amenable to multithreading technologies spend a significant fraction of their time in kernel code. A full understanding of the behavior of such workloads therefore requires execution and measurement of the operating system, as well as the application itself.To carry out this study, we (1) modified the Digital Unix 4.0d operating system to run on an SMT CPU, and (2) integrated our SMT Alpha instruction set simulator into the SimOS simulator to provide an execution environment. For an OS-intensive workload, we ran the multithreaded Apache Web server on an 8-context SMT. We compared Apache's user- and kernel-mode behavior to a standard multiprogrammed SPECInt workload, and compared the SMT processor to an out-of-order superscalar running both workloads. Overall, our results demonstrate the micro-architectural impact of an OS-intensive workload on an SMT processor and provide insight into the OS demands of the Apache Web server. The synergy between the SMT processor and Web and OS software produced a greater throughput gain over superscalar execution than seen on any previously examined workloads, including commercial databases and explicitly parallel programs.
The influence of browsers on evaluators or, continuations to program web servers
Authors: Queinnec Christian
Published: November 2005

While developing the software of a browser-operated educational CD-ROM, we had to face a number of problems. This paper presents these problems and the solutions we found. Amusingly, most of our solutions rely on continuations. Are browsers and multimedia the future of continuations?Through their "Back" button or "Clone window" menu item, browsers have powerful abilities that force servers to take care of multiply and simultaneously answered questions. A comprehensive tool to apprehend these problems as well as to solve them is to view these abilities as operators acting on the continuations of the computation performed by servers.Thematical trails are provided to walk through the CD-ROM but do not prevent students to wander elsewhere. A trail may contain choices or quizzes so the rest of the trail should adapt to the walked part. We consider the trail as a computation and the position of the student as a continuation within that computation.Moreover this paper advocates a computation-centric view of servers (in opposition to the usual page-centric view) where interactions with users suspend the computation into continuations that may be later resumed. This approach is superior because the continuation reifies, automatically and without errors, the whole state of the computation.