bluuebunny/crossref_metadata_2025 huggingface dataset:
mpC
Authors: Lastovetsky Alexey L.
Published: November 2005

Currently, programming systems for distributed memory machines are limited to either task parallelism or data parallelism. The mpC programming language and its programming system support both task and data parallelism, allows both static and dynamic process and communication structures, enables optimizations aimed at both communication and computation, and supports modular parallel programming and the development of a library of parallel programs. The mpC language is an ANSI C superset. It is based on the notion of network comprising processor nodes of different types connected with links of different lengths. The mpC language has facilities for description of network topology, for creating and discarding networks, for distribution data and computations over networks, for writing of functions that can be called on networks of the proper topology and so on. The paper presents basic principles underlying the mpC language and outlines its programming system.
Translating SQL for database reengineering
Authors: Tuovinen Antti-Pekka , Paakki Jukka
Published: November 2005

A tool for porting database applications is presented. The tool transforms VMS/Rdb applications written in C and embedded SQL into a portable, database-independent application interface which can be directly installed on a target platform and database management system with a separate customization tool. The converter is based on standard techniques developed for compiling programming languages. The original task of the converter was to port a large administrative system from VMS/Rdb into Oracle, but the tool can be used for other reengineering applications as well.
Software complexity—an alternative view
Authors: Kokol Peter , Brest Janez , Žumer Viljem
Published: November 2005

A different view on software complexity based on long range correlations is presented in this paper. Four different methods are proposed first and then used in the analysis of twenty FORTRAN programs. All methods being used indicate the presence of long range correlations, but every method gives different results. The presence of long range correlations denotes that we can infact regard the complexity of computer programs from a different perspective.
A conceptual perspective on the comparison of object-oriented programming languages
Authors: Kristensen Bent Bruun , Østerbye Kasper
Published: November 2005

The understanding of object-oriented programming languages is generally based on their included features. In this understanding, these features form the underlying concepts of both the languages and the modeling processes based on the languages. Consequently, object-oriented languages are generally compared and evaluated based on these features. Alternatively, object-oriented programming languages may be seen as supporting a conceptual perspective on programming. Instead of the features, the underlying concepts are then concepts such as
phenomenon
and
concept
, and also the abstraction processes in relation to these concepts. A comparison of object-oriented languages from the conceptual perspective gives additional understanding of each language and the mutual relations and differences between these.
Intensional equality ;=) for continuations
Authors: Appel Andrew W.
Published: November 2005

I propose a novel language feature,
intensional continuation equality
, useful in languages with or without first-class continuations, and show how it enables
truly remarkable gains in efficiency
of ordinary user programs.Continuations, expressing "what the program will do from now on," are a much-used tool of semantics, and sometimes show up as a user-accessible programming feature. But most use of continuations is
parametric
, in the sense that functions behave the same way independent of their continuation. I will show that nonparametric use of continuations allows very substantial, almost incredible gains in program speed. Furthermore, this technique is compatible with almost any style of programming language; imperative, functional, even object-oriented.
Fair transition system specification
Authors: Jia Guoping , Zheng Guoliang
Published: November 2005

In this paper, we discuss the two approaches to the type of formalism used to express specifications: logic-based approach and model-based approach. Temporal logic and state machine, representatives of formalisms used in each approach, are compared. As a result of this comparison, we know that although temporal logics have many advantages, especially abstraction and flexibility of the specification process, they fail to directly characterize situations easily modeled by model-based formalisms, such as "local" properties of execution sequences. To copy with these drawbacks, we present a new kind of formalism: fair transition system specification (FTSS). This approach combines the best features of temporal logic and state machine methods and it is easy to understand and use. A nontrivial example is used to illustrate our approach and it shows that our FTSS approach is promising.
PL/I for OS/2
Authors: Vowels Robin A.
Published: November 2005

The PL/I language has been updated with a new compiler for OS/2.What's in it?How is it better than existing versions?In this Paper the enhancements over OS PL/I Version 2 (IBM, 1990a, b) are outlined. The new features include strongly-typed list-processing facilities in which declarations and built-in functions bind the pointer to a particular data structure template; ordinals; and a host of built-in functions. Other new data types include unsigned arithmetic data, and zero-terminated varying-length character strings. Aliases enable user types to be defined, while the TYPE attribute permits a data type to be created in the image of another. There is a new method of overlaying one data type with another, intended to improve maintainability. To complement the ordinals and to extend the usefulness of the language generally, new options for the DO statement avoid overflow on the last trip. The macro processor has been significantly enhanced, with new statements and new built-in functions.
A reflection on call-by-value
Authors: Sabry Amr , Wadler Philip
Published: November 2005

A number of compilers exploit the following strategy: translate a term to continuation-passing style (CPS) and optimize the resulting term using a sequence of reductions. Recent work suggests that an alternative strategy is superior: optimize directly in an extended source calculus. We suggest that the appropriate relation between the source and target calculi may be captured by a special case of a
Galois connection
known as a
reflection
. Previous work has focused on the weaker notion of an
equational correspondence
, which is based on equality rather than reduction. We show that Moggi's monad translation and Plotkin's CPS translation can both be regarded as reflections, and thereby strengthen a number of results in the literature.
The role of lazy evaluation in amortized data structures
Authors: Okasaki Chris
Published: November 2005

Traditional techniques for designing and analyzing amortized data structures in an imperative setting are of limited use in a functional setting because they apply only to single-threaded data structures, yet functional data structures can be non-single-threaded. In earlier work, we showed how lazy evaluation supports functional amortized data structures and described a technique (the banker's method) for analyzing such data structures. In this paper, we present a new analysis technique (the physicist's method) and show how one can sometimes derive a worst-case data structure from an amortized data structure by appropriately scheduling the premature execution of delayed components. We use these techniques to develop new implementations of FIFO queues and binomial queues.
Analysis and caching of dependencies
Authors: Abadi Martín , Lampson Butler , Lévy Jean-Jacques
Published: November 2005

We address the problem of dependency analysis and caching in the context of the λ-calculus. The dependencies of a λ-term are (roughly) the parts of the λ-term that contribute to the result of evaluating it. We introduce a mechanism for keeping track of dependencies, and discuss how to use these dependencies in caching.
Complexity of kernel Fun subtype checking
Authors: Ghelli Giorgio
Published: November 2005

System kernel Fun is an abstract version of the system Fun defined by Cardelli's and Wegner's seminal paper [CW85], and is strictly related to system F≤. Extensions of these two systems are currently the basis of most proposals for strong type systems for object-oriented languages.We study here the problem of subtype checking for system kernel Fun, presenting the following results. We show that the standard kernel Fun subtype checking algorithm has an exponential complexity, and generates an exponential number of different subproblems. We then present a new subtype checking algorithm which has a polynomial complexity. In the process we study how variable names can be managed by a kernel Fun subtype checker which is not based on the De Bruijn encoding, and we show how to perform kernel Fun subtype checking with a "constraint generating" technique.The algorithm we give is described by a set of type rules, which we prove to be equivalent to the standard one. This new presentation of kernel Fun type system is characterized by a "multiplicative" behaviour, and it may open the way to new presentations for system F≤ as well.
A probabilistic approach to the problem of automatic selection of data representations
Authors: Chuang Tyng-Ruey , Hwang Wen L.
Published: November 2005

The designs and implementations of efficient aggregate data structures have been important issues in functional programming. It is not clear how to select a good representation for an aggregate when access patterns to the aggregate are highly variant, or even unpredictable. Previous approaches rely on compile--time analyses or programmer annotations. These methods can be unreliable because they try to predict a program's behavior before it is executed.We propose a probabilistic approach, which is based on Markov processes, for automatic selection of data representations. The selection is modeled as a random process moving in a graph with weighted edges. The proposed approach employs coin tossing at run--time to help choosing a suitable data representation. The transition probability function used by the coin tossing is constructed in a simple and common way from a measured cost function. We show that, under this setting, random selections of data representations can be quite effective. The probabilistic approach is used to implement bag aggregates, and the performance results are compared to those of deterministic selection strategies.
Synchronous Kahn networks
Authors: Caspi Paul , Pouzet Marc
Published: November 2005

Synchronous data-flow is a programming paradigm which has been successfully applied in reactive systems. In this context, it can be characterized as some class of static bounded memory data-flow networks. In particular, these networks are not recursively defined, and obey some kind of "synchronous" constraints (
clock calculus
). Based on Kahn's relationship between data-flow and stream functions, the synchronous constraints can be related to Wadler's listlessness, and can be seen as sufficient conditions ensuring listless evaluation. As a by-product, those networks enjoy efficient compiling techniques. In this paper, we show that it is possible to extend the class of static synchronous data-flow to higher order and dynamical networks, thus giving sense to a larger class of synchronous data-flow networks.This is done by extending both the synchronous operational semantics, the clock calculus and the compiling technique of static data-flow networks, to these more general networks.
Collaboratively teaching a multidisciplinary course
Authors: Gladfelter Suzanne
Published: November 2005

In spring 1996 two colleagues and I collaboratively taught an experimental multidisciplinary introductory-level honors speech communications course. The semester-long 4.5 credit course covered public speaking, presentation software, and philosophical soundness. The course demonstrated to students and faculty how technology can serve the humanities.
Establishing a new curriculum in computer technology
Authors: Freedman Josephine Alessi
Published: November 2005

The creation of a new curriculum requires a great deal of enthusiasm, energy, and perseverance, coupled with the support from department colleagues and all the upper levels of administration. The academic and political environment during the academic year 1994-1995 was conducive for the Computer Science Department to establish a new career track curriculum. In this article, I will enumerate the steps that I took to create and establish the Computer Technology curriculum at Suffolk Community College as well as the frustrations and stumbling blocks that I experienced along the way.
Will I still be writing code when I'm forty?
Authors: Christiaanse Vance
Published: November 2005

I had just told a community college instructor that in industry, where I teach and work, a typical software engineer spends little time coding. "So what do you do all day?", she asked.
Split objects
Authors: Bardou Daniel , Dony Christophe
Published: November 2005

This paper's primary aim is to improve the understanding of the delegation mechanism as defined in [18]. We propose a new characterization of delegation based on the notions of name sharing, property sharing and value sharing. It allows us (1) to clearly differentiate delegation from class-inheritance in particular and more generally from other inheritance mechanisms and (2) to explain how a founded use of delegation relies on a correct semantics of variable property sharing between objects connected by a delegation link. We then describe a model of split objects which is proposed as an example of a disciplined and semantically founded use of delegation, where property sharing expresses viewpoints within objects.
Lessons learned from implementing the CORBA persistent object service
Authors: Kleindienst Jan , Plášil František , Tůma Petr
Published: November 2005

In this paper, the authors share their experiences gathered during the design and implementation of the CORBA Persistent Object Service. There are two problems related to a design and implementation of the Persistence Service: first, OMG intentionally leaves the functionality core of the Persistence Service unspecified; second, OMG encourages reuse of other Object Services without being specific enough in this respect. The paper identifies the key design issues implied both by the intentional lack of OMG specification and the limits of the implementation environment characteristics. At the same time, the paper discusses the benefits and drawbacks of reusing other Object Services, particularly the Relationship and Externalization Services, to support the Persistence Service. Surprisingly, the key lesson learned is that a direct reuse of these Object Services is impossible.
The direct cost of virtual function calls in C++
Authors: Driesen Karel , Hölzle Urs
Published: November 2005

We study the direct cost of virtual function calls in C++ programs, assuming the standard implementation using virtual function tables. We measure this overhead experimentally for a number of large benchmark programs, using a combination of executable inspection and processor simulation. Our results show that the C++ programs measured spend a median of 5.2% of their time and 3.7% of their instructions in dispatch code. For "all virtuals" versions of the programs, the median overhead rises to 13.7% (13% of the instructions). The "thunk" variant of the virtual function table implementation reduces the overhead by a median of 21% relative to the standard implementation. On future processors, these overheads are likely to increase moderately.
Formal design constraints
Authors: Klarlund Nils , Koistinen Jari , Schwartzbach Michael I.
Published: November 2005

Large software systems are often built on system platforms that support or enforce specific characteristics of the source code or actual design. These characteristics are either captured informally in design guideline documents or in specialized design and implementation languages.In our view, both approaches are unsatisfactory. Informal descriptions do not allow automated analysis and lead to vague constraint descriptions. The language-based approach leads to different languages for different platforms and even for different versions of the same basic platform.Our approach is to describe and name the constraints separately in a design constraint language called CDL, which is based on an extraordinarily concise logic of parse trees. Designs are then annotated with the names of the constraints they are supposed to satisfy.We discuss how the design constraint language is integrated into a design language environment. We exhibit industrial and experimental evidence that our choice of design constraint language allows us to formalize naturally and succinctly common design characteristics.
A framework for run-time systems and its visual programming language
Authors: Durham Alan M. , Johnson Ralph E.
Published: November 2005

Frameworks and domain-specific visual languages are two different reuse techniques, the first targeted at expert programmers, the second at domain experts. In fact, these techniques are closely related. This paper shows how to develop a domain-specific visual language by first developing a white-box framework for the domain, then turning it into a black-box framework, and finally building a graphical front end for it. We used this technique in a compiler to specify run-time systems.
A TI-92 calculator script for inverting 4x4 matrices
Authors: Niemann Chris
Published: November 2005

This paper illustrates an alternative method for inverting a (4x4) matrix on the TI-92 calculator. I call this the
Power Extended Partition
(P.E.P.) method. This method works for a matrix of any dimension, but my purpose is to present an easily understood introduction to the P.E.P. method. Thus, I will restrict the discussion to (4x4) matrices whose determinants are not zero. (Hence their inverses will exist.)
Learning to teach C++
Authors: Ross John Minor
Published: November 2005

Object-oriented programming, which came on the scene with Simula-67, is continuing to grow in popularity. C++, the object-oriented expansion of C, is one of the most used languages associated with object-oriented programming. Much of what is written about C++, however, is directed towards those already immersed in the object-oriented paradigm. Such writings often are not useful to C language instructors just beginning to work with C++ since there is a considerable learning curve for novices and experts alike. Readers who are C-literate are (1) presented with reasons to move to C++, (2) warned of potential hazards on the object-oriented path, and (3) provided with heuristics to make the transition from C to C++ easier.
The future belongs to those who teach themselves
Authors: Christiaanse Vance
Published: November 2005

You probably spent some time this past summer increasing your technical knowledge. How did you do it? Formal classes or self-study? Which do you like better? Which is more effective?
Static, dynamic and run-time modeling of compound classes
Authors: Agarwal Rakesh , Bruno Giorgio , Torchiano Marco
Published: November 2005

Automation techniques are required to manage the complexity inherent in the design of large computer based systems and to provide an efficient means for using the services present in other system.Operational models often allow timing constraints to be expressed and, consequently, a discrete-event simulation of the model can be performed. In this way, statistical estimates of the system's parameters can be collected in order to support decision making. When a formal proof would be too expensive, such statistics can confidently be used to determine some properties of the system.
O
3
ML (Operational Object-Oriented Modeling Language) is a graphical language develped by us, to model complex operational software system, which is centered upon the creation of a system prototype providing the feature to dynamically generate actors and establish connection during run time. The developed models can be evaluated it in a controlled simulation framework.In
O
3
ML actors can be assembled into complex structures forming composite actors, by establishing connection using connectors. In a more abstract view, these networked structures can be interpreted as entity-relationship models. Such aggregation of actors is always encapsulated within a higher-level composite actor specification. An actor class can, thus, encapsulate an actor (which is a composite actor). This would make the actor structure recursive so that arbitrary complex hierarchical actor structures can be constructed.
Porting the Oberon system to AlphaAXP
Authors: Dotzel Günter , Goebel Hartmut
Published: November 2005

The Oberon System is an object-oriented programming framework supporting persistent objects and run-time extensibility. This paper describes the development of Alpha Oberon, an implementation of the Oberon System V4 for AiphaAXP under OpenVMS with X11 server. The port is based upon the ETH Zürich's Oberon System for MIPS/Unix and ModulaWare's OpenVMS AXP stand-alone Oberon-2 compiler. The processor and operating system specific parts of the Oberon System and its boot-loader were rewritten in Oberon-2 from scratch. Details are provided for the module-loader, bootstrap-mechanism, garbage collector, OpenVMS' vs. Unix's system service support for exception- and stack-processing, procedure calling conventions, data alignment issues, and run-time data structures.
A modest proposal
Authors: Werther Ben , Conway Damian
Published: November 2005

We describe an alternative syntactic binding for C++. This new binding includes a completely redesigned declaration/definition syntax for types, functions and objects, a simplified template syntax, and changes to several problematic operators and control structures. The resulting syntax is LALR(1) parsable and provides better consistency in the specification of similar constructs, better syntactic differentiation of dissimilar constructs, and greater overall readability of code.
Using object-orientation as a common basis for system development education
Authors: Knudsen Jørgen Lindskov , Madsen Ole Lehrmann
Published: November 2005

Object-orientation has a long tradition at the Computer Science Department, Aarhus University, starting with Simula in the early seventies. For more than 20 years there have been courses in object-oriented programming, including BETA, Smalltalk, Self and others. Recently object-orientation has started to be integrated in other parts of the curriculum such as in software engineering, distributed systems and databases. In this paper we report on this approach to teaching object-orientation. One of the advantages of object-orientation is that it provides an integrating perspective on the various areas to be taught. Besides providing a common conceptual framework, it also makes it possible to use common languages and tools that have a profound influence on the integration. Especially in the software engineering course, it has been possible to let the students experience an iterative software development method where they make a number of iterations through analysis, design and implementation. To do these iterations, it is necessary with good development tools like a CASE tool that supports code generation and reverse engineering. The Mjølner BETA System is used in the various courses as a common platform, but the students are also introduced to other object-oriented environments like Smalltalk, Self, Eiffel, and C++. The Mjølner BETA System that is a software development environment for object-oriented development based on the BETA programming language.
Requirements for an imperative language to host logic programming in a seamless way
Authors: Callegarin Giuseppe
Published: November 2005

Designing a widely acceptable multiparadigm language is still a challenging task. A critical problem is the choice of the linguistic tools by means of which the programmer can make the different paradigms "communicate" with each other. The framework for integrating logic and commands presented in this paper is simple and can also be a good starting point toward the integration of objects, functions and constraints. This scheme is effective: it has been used for implementing a small but representative educational multiparadigm language.
Some comments on Morel and Renvoise's “global optimization by suppression of partial redundancies”
Authors: Sorkin Arthur
Published: November 2005

There has been much continuing interest in the global optimization method of Morel and Renvoise as extended by Joshi-Dhamdere and Chow. Unfortunately, the original formulation of Morel and Renvoise and those of Joshi-Dhamdere and Chow do not agree as to the form of the algorithm. The precise form of the algorithm's boolean equations is critical to the algorithm's performance and efficient implementation. Some of the problems with the algorithm noted by other authors can be solved by using a slightly different formulation of the algorithm.
A Note On Type Checking Linear Functional Languages
Authors: Syropoulos Apostolos
Published: November 2005

A linear functional language is based on a linear λ-calculus. Any linear functional program must observe linearity and it has to be type correct. Type correctness can be ensured by means of a type-checking system. A type checker for a linear functional language is essentially a type-checker for an ordinary functional language, modified to properly handle the modality
ofcourse
.
A framework for programming denotational semantics in C++
Authors: Papaspyrou Nikolaos S.
Published: November 2005

In this paper, we describe how the denotational semantics of programming languages can be implemented in C++, by exploiting the object-oriented programming paradigm. Such implementations are execution models, extremely useful for the study of programming languages. Although C++ is not a natural choice for this problem domain, compared to functional programming languages such as ML, we suggest a type-safe framework, implemented in pure C++, that integrates functional characteristics such as high-order functions and is capable of naturally expressing denotational descriptions. Finally, by comparing our approach to possible implementations using functional languages, we investigate extensions to C++ that would be valuable in this problem domain.
ParCeL-1
Authors: Vialle Stéphane , Cornu Thierry , Lallement Yannick
Published: November 2005

In this paper we present a new language, called ParCeL-1, intended to make easier the implementation of computation-intensive applications on highly parallel MIMD architectures. The computational model of ParCeL-1 is object-oriented and synchronous. The current prototype is implemented on several multi-processor systems (Cray T3D, Intel Paragon, Telmat T-Node and workstation networks using PVM). Benchmarks are presented for several parallel programs.
hcc
—a portable ANSI C compiler (with a code generator for the PowerPCs)
Authors: Abdullah Mohd Hanafiah
Published: November 2005

hcc
is a portable optimizing compiler for ANSI C [8] [9] with code generators for the PowerPC and the MIMOS's RISC CPU. The PowerPC is a RISC processor developed jointly by IBM, Motorola, and Apple Computer among others in 1993, while the MIMOS's RISC CPU is an experimental 32-bit RISC processor. At the moment the compiler can be used to program PowerPC based computers including the PowerMacintoshes and the IBM RS6000 PowerPC based workstations.
A note on type checking linear functional languages
Authors: Syropoulos Apostolos
Published: November 2005

A linear functional language is based on a linear λ-calculus. Any linear functional program must observe linearity and it has to be type correct. Type correctness can be ensured by means of a type-checking system. A type checker for a linear functional language is essentially a type-checker for an ordinary functional language, modified to properly handle the modality
ofcourse
.
Porting the
mcc
PowerPC C/C++ compiler into an interactive development environment
Authors: Butt Farooq
Published: November 2005

The quest for software reuse often leads to tools such as compilers and assemblers being used in environments for which they were never designed. This paper discusses the experiences of dropping the Motorola
mcc
command-line based UNIX PowerPC™ compiler into the Macintosh Finder Operating System under the Metrowerks Codewarrior Interactive Development Environment (IDE). We explore the issues that arise when attempting such a project as well as potential pitfalls and challenges.
The design of the REXX language
Authors: Cowlishaw M
Published: November 2005

One way of classifying computer languages is by two classes: languages needing skilled programmers, and personal languages used by an expanding population of general users. REstructured eXtended eXecutor (REXX) is a flexible personal language designed with particular attention to feedback from its users. It has proved to be effective and easy to use, yet it is sufficiently general and powerful to fulffil the needs of many demanding professional applications. REXX is system and hardware independent, so that it has been possible to integrate it experimentally into several operating systems. Here REXX is used for such purposes as command and macro programming, prototyping, education, and personal programming. This paper introduces REXX and describes the basic design principles that were followed in developing it.
A notation for specifying menus
Authors: Hekmatpour S
Published: November 2005

Interactive menus have become an important tool in designing user friendly interfaces to computer systems. In many systems they have replaced the old approach of using command languages to make the dialogue more suggestive. This paper suggest a simple notation for specifying menus. The notation is powerful enough to cope with the wide variety of menus found in today computer systems.
Evaluation of architectural support for global address-based communication in large-scale parallel machines
Authors: Krishnamurthy Arvind , Schauser Klaus E. , Scheiman Chris J. , Wang Randolph Y. , Culler David E. , Yelick Katherine
Published: November 2005

Large-scale parallel machines are incorporating increasingly sophisticated architectural support for user-level messaging and global memory access. We provide a systematic evaluation of a broad spectrum of current design alternatives based on our implementations of a global address language on the Thinking Machines CM-5, Intel Paragon, Meiko CS-2, Cray T3D, and Berkeley NOW. This evaluation includes a range of compilation strategies that make varying use of the network processor; each is optimized for the target architecture and the particular strategy. We analyze a family of interacting issues that determine the performance trade-offs in each implementation, quantify the resulting latency, overhead, and bandwidth of the global access operations, and demonstrate the effects on application performance.
Whole-program optimization for time and space efficient threads
Authors: Grunwald Dirk , Neves Richard
Published: November 2005

Modern languages and operating systems often encourage programmers to use
threads,
or independent control streams, to mask the overhead of some operations and simplify program structure. Multitasking operating systems use threads to mask communication latency, either with hardwares devices or users. Client-server applications typically use threads to simplify the complex control-flow that arises when multiple clients are used. Recently, the scientific computing community has started using threads to mask network communication latency in massively parallel architectures, allowing computation and communication to be overlapped. Lastly, some architectures implement threads in hardware, using those threads to tolerate memory latency.In general, it would be desirable if threaded programs could be written to expose the largest degree of parallelism possible, or to simplify the program design. However, threads incur time and space overheads, and programmers often compromise simple designs for performance. In this paper, we show how to reduce time and space thread overhead using control flow and register liveness information inferred
after
compilation. Our techniques work on binaries, are not specific to a particular compiler or thread library and reduce the the overall execution time of fine-grain threaded programs by ≈ 15-30%. We use execution-driven analysis and an instrumented operating system to show why the execution time is reduced and to indicate areas for future work.
Thread scheduling for cache locality
Authors: Philbin James , Edler Jan , Anshus Otto J. , Douglas Craig C. , Li Kai
Published: November 2005

This paper describes a method to improve the cache locality of sequential programs by scheduling fine-grained threads. The algorithm relies upon hints provided at the time of thread creation to determine a thread execution order likely to reduce cache misses. This technique may be particularly valuable when compiler-directed tiling is not feasible. Experiments with several application programs, on two systems with different cache structures, show that our thread scheduling method can improve program performance by reducing second-level cache misses.
The Rio file cache
Authors: Chen Peter M. , Ng Wee Teck , Chandra Subhachandra , Aycock Christopher , Rajamani Gurushankar , Lowell David
Published: November 2005

One of the fundamental limits to high-performance, high-reliability file systems is memory's vulnerability to system crashes. Because memory is viewed as unsafe, systems periodically write data back to disk. The extra disk traffic lowers performance, and the delay period before data is safe lowers reliability. The goal of the Rio (RAM I/O) file cache is to make ordinary main memory safe for persistent storage by enabling memory to survive operating system crashes. Reliable memory enables a system to achieve the best of both worlds: reliability equivalent to a write-through file cache, where every write is instantly safe, and performance equivalent to a pure write-back cache, with no reliability-induced writes to disk. To achieve reliability, we protect memory during a crash and restore it during a reboot (a "warm" reboot). Extensive crash tests show that even without protection, warm reboot enables memory to achieve reliability close to that of a write-through file system. Adding protection makes memory even
safer
than a write-through file system while adding essentially no overhead. By eliminating reliability-induced disk writes, Rio performs 4-22 times as fast as a write-through file system, 2-14 times as fast as a standard Unix file system, and 1-3 times as fast as an optimized system that risks losing 30 seconds of data and metadata.
Petal
Authors: Lee Edward K. , Thekkath Chandramohan A.
Published: November 2005

The ideal storage system is globally accessible, always available, provides unlimited performance and capacity for a large number of clients, and requires no management. This paper describes the design, implementation, and performance of Petal, a system that attempts to approximate this ideal in practice through a novel combination of features. Petal consists of a collection of network-connected servers that cooperatively manage a pool of physical disks. To a Petal client, this collection appears as a highly available block-level storage system that provides large abstract containers called
virtual disks.
A virtual disk is globally accessible to all Petal clients on the network. A client can create a virtual disk on demand to tap the entire capacity and performance of the underlying physical resources. Furthermore, additional resources, such as servers and disks, can be automatically incorporated into Petal.We have an initial Petal prototype consisting of four 225 MHz DEC 3000/700 workstations running Digital Unix and connected by a 155 Mbit/s ATM network. The prototype provides clients with virtual disks that tolerate and recover from disk, server, and network failures. Latency is comparable to a locally attached disk, and throughput scales with the number of servers. The prototype can achieve I/O rates of up to 3150 requests/sec and bandwidth up to 43.1 Mbytes/sec.
The intrinsic bandwidth requirements of ordinary programs
Authors: Huang Andrew S. , Shen John Paul
Published: November 2005

While there has been an abundance of recent papers on hardware and software approaches to improving the performance of memory accesses, few papers have addressed the problem from the program's point of view. There is a general notion that certain programs have larger working sets than others. However, there is no quantitative method for evaluating and comparing the memory requirements of programs.This paper introduces the
bandwidth spectrum
for characterizing the memory requirements of a program's instruction and data stream. The bandwidth spectrum measures the average bandwidth requirement of a program as a function of available local memory. These measurements are performed under the most idealized conditions of perfect knowledge and perfect memory management. As such, they represent the lower bounds on the memory requirements of programs. We present the bandwidth spectrums for a set of 22 benchmarks and show how they can be used in the comparison of memory requirements and I/O requirement. The bandwidth spectrums also offer a convenient method to weigh the trade-off amongst instruction issue rate, local memory capacity and bandwidth into local memory.Using the bandwidth spectrum, we show that at issue rates of four or less, bandwidth usually scales linearly with the issue rate. At higher issue rates, bandwidth can often scale superlinearly with respect to issue rate. Finally, we also investigate the effects of varying the input sets on the bandwidth spectrums.
Multiple-block ahead branch predictors
Authors: Seznec André , Jourdan Stéphan , Sainrat Pascal , Michaud Pierre
Published: November 2005

A basic rule in computer architecture is that a processor cannot execute an application faster than it fetches its instructions. This paper presents a novel cost-effective mechanism called the two-block ahead branch predictor. Information from the current instruction block is not used for predicting the address of the next instruction block, but rather for predicting the block following the next instruction block.This approach overcomes the instruction fetch bottle-neck exhibited by wide-dispatch "brainiac" processors by enabling them to efficiently predict addresses of two instruction blocks in a single cycle. Furthermore, pipelining the branch prediction process can also be done by means of our predictor for "speed demon" processors to achieve higher clock rate or to improve the prediction accuracy by means of bigger prediction structures.Moreover, and unlike the previously-proposed multiple predictor schemes, multiple-block ahead branch predictors can use any of the branch prediction schemes to perform the very accurate predictions required to achieve high-performance on superscalar processors.
Analysis of branch prediction via data compression
Authors: Chen I-Cheng K. , Coffey John T. , Mudge Trevor N.
Published: November 2005

Branch prediction is an important mechanism in modern microprocessor design. The focus of research in this area has been on designing new branch prediction schemes. In contrast, very few studies address the theoretical basis behind these prediction schemes. Knowing this theoretical basis helps us to evaluate how good a prediction scheme is and how much we can expect to improve its accuracy.In this paper, we apply techniques from data compression to establish a theoretical basis for branch prediction, and to illustrate alternatives for further improvement. To establish a theoretical basis, we first introduce a conceptual model to characterize each component in a branch prediction process. Then we show that current "two-level" or correlation based predictors are, in fact, simplifications of an optimal predictor in data compression, Prediction by Partial Matching (PPM).If the information provided to the predictor remains the same, it is unlikely that significant improvements can be expected (asymptotically) from two-level predictors, since PPM is optimal. However, there are a rich set of predictors available from data compression, several of which can still yield some improvement in cases where resources are limited. To illustrate this, we conduct trace-driven simulation running the Instruction Benchmark Suite and the SPEC CINT95 benchmarks. The results show that PPM can outperform a two-level predictor for modest sized branch target buffers.
The structure and performance of interpreters
Authors: Romer Theodore H. , Lee Dennis , Voelker Geoffrey M. , Wolman Alec , Wong Wayne A. , Baer Jean-Loup , Bershad Brian N. , Levy Henry M.
Published: November 2005

Interpreted languages have become increasingly popular due to demands for rapid program development, ease of use, portability, and safety. Beyond the general impression that they are "slow," however, little has been documented about the performance of interpreters as a class of applications.This paper examines interpreter performance by measuring and analyzing interpreters from both software and hardware perspectives. As examples, we measure the MIPSI, Java, Perl, and Tcl interpreters running an array of micro and macro benchmarks on a DEC Alpha platform. Our measurements of these interpreters relate performance to the complexity of the interpreter's virtual machine and demonstrate that native runtime libraries can play a key role in providing good performance. From an architectural perspective, we show that interpreter performance is primarily a function of the interpreter itself and is relatively
independent
of the application being interpreted. We also demonstrate that high-level interpreters' demands on processor resources are comparable to those of other complex compiled programs, such as gcc. We conclude that interpreters, as a class of applications, do not currently motivate special hardware support for increased performance.
Exploiting dual data-memory banks in digital signal processors
Authors: Saghir Mazen A. R. , Chow Paul , Lee Corinna G.
Published: November 2005

Over the past decade, digital signal processors (DSPs) have emerged as the processors of choice for implementing embedded applications in high-volume consumer products. Through their use of specialized hardware features and small chip areas, DSPs provide the high performance necessary for embedded applications at the low costs demanded by the high-volume consumer market. One feature commonly found in DSPs is the use of dual data-memory banks to double the memory system's bandwidth. When coupled with high-order data interleaving, dual memory banks provide the same bandwidth as more costly memory organizations such as a dual-ported memory. However, making effective use of dual memory banks remains difficult, especially for high-level language (HLL) DSP compilers.In this paper, we describe two algorithms --- compaction-based (CB) data partitioning and partial data duplication --- that we developed as part of our research into the effective exploitation of dual data-memory banks in HLL DSP compilers. We show that CB partitioning is an effective technique for exploiting dual data-memory banks, and that partial data duplication can augment CB partitioning in improving execution performance. Our results show that CB partitioning improves the performance of our kernel benchmarks by 13%-40% and the performance of our application benchmarks by 3%-15%. For one of the application benchmarks, partial data duplication boosts performance from 3% to 34%.
Prolog dialects: a deja vu of BASICs
Authors: Sosnowski R A
Published: November 2005

The evolution of Prolog is reminiscent of the kind of dialect formation that BASIC and LISP went through, only worse. Prolog appears to be spawning divergent mutants that differ from one another in syntax, grammar
and
symmantics. LISP has converged to a set of standards, but BASIC has yet to. LISP as a general purpose language and Prolog as a special purpose language can solve their own class of problems well. Given that both LISP and Prolog are used for artificial intelligence, Prolog has been quite slow to catch on commercially, in large part due to a lack of this standardization, and its future is unclear.
GUM
Authors: Trinder P. W. , Hammond K. , Mattson J. S. , Partridge A. S. , Peyton Jones S. L.
Published: November 2005

GUM is a portable, parallel implementation of the Haskell functional language. Despite sustained research interest in parallel functional programming, GUM is one of the first such systems to be made publicly available.GUM is message-based, and portability is facilitated by using the PVM communications harness that is available on many multi-processors. As a result, GUM is available for both shared-memory (Sun SPARCserver multiprocessors) and distributed-memory (networks of workstations) architectures. The high message-latency of distributed machines is ameliorated by sending messages asynchronously, and by sending large packets of related data in each message.Initial performance figures demonstrate absolute speedups relative to the best sequential compiler technology. To improve the performance of a parallel Haskell program GUM provides tools for monitoring and visualising the behaviour of threads and of processors during execution.
Printing floating-point numbers quickly and accurately
Authors: Burger Robert G. , Dybvig R. Kent
Published: November 2005

This paper presents a fast and accurate algorithm for printing floating-point numbers in both free- and fixed-format modes. In free-format mode, the algorithm generates the shortest, correctly rounded output string that converts to the same number when read back in, accommodating whatever rounding mode the reader uses. In fixed-format mode, the algorithm generates a correctly rounded output string using special # marks to denote insignificant trailing digits. For both modes, the algorithm employs a fast estimator to scale floating-point numbers efficiently.
VCODE
Authors: Engler Dawson R.
Published: November 2005

Dynamic code generation is the creation of executable code at runtime. Such "on-the-fly" code generation is a powerful technique, enabling applications to use runtime information to improve performance by up to an order of magnitude [4, 8,20, 22, 23].Unfortunately, previous general-purpose dynamic code generation systems have been either inefficient or non-portable. We present VCODE, a retargetable, extensible, very fast dynamic code generation system. An important feature of VCODE is that it generates machine code "in-place" without the use of intermediate data structures. Eliminating the need to construct and consume an intermediate representation at runtime makes VCODE both efficient and extensible. VCODE dynamically generates code at an approximate cost of six to ten instructions per generated instruction, making it over an order of magnitude faster than the most efficient general-purpose code generation system in the literature [10].Dynamic code generation is relatively well known within the compiler community. However, due in large part to the lack of a publicly available dynamic code generation system, it has remained a curiosity rather than a widely used technique. A practical contribution of this work is the free, unrestricted distribution of the VCODE system, which currently runs on the MIPS, SPARC, and Alpha architectures.