bluuebunny/crossref_metadata_2025 huggingface dataset:
Energy-efficient policies for embedded clusters
Authors: Xu Ruibin , Zhu Dakai , Rusu Cosmin , Melhem Rami , Mossé Daniel
Published: November 2005

Power conservation has become a key design issue for many systems, including clusters deployed for embedded systems, where power availability ultimately determines system lifetime. These clusters execute a high rate of requests of highly-variable length, such as in satellite-based multiprocessor systems. The goal of power management in such systems is to minimize the aggregate energy consumption of the whole cluster while ensuring timely responses to requests. In the past, dynamic voltage scaling (DVS) and on/off schemes have been studied under the assumptions of continuously tunable processor frequencies and perfect load-balancing. In this work, we focus on the more realistic case of discrete processor frequencies and propose a new policy that adjusts the number of active nodes based on the system
load
, not system frequency. We also design a threshold scheme which prevents the system from reacting to short-lived temporary workload changes in the presence of unstable incoming workload. Simulation and implementation results on real hardware show that our policy is very effective in reducing the overall power consumption of clusters executing embedded applications.
Software design patterns for TinyOS
Authors: Gay David , Levis Phil , Culler David
Published: November 2005

We present design patterns used by software components in the TinyOS sensor network operating system. They differ significantly from traditional software design patterns due to the constraints of sensor networks, and to TinyOS's focus on static allocation and whole-program composition. We describe how nesC has evolved to support these design patterns by including a few simple language primitives and optimisations.
Preventing interrupt overload
Authors: Regehr John , Duongsaa Usit
Published: November 2005

Performance guarantees can be given to tasks in an embedded system by ensuring that access to each shared resource is mediated by an appropriate scheduler. However, almost all previous work on CPU scheduling has focused on thread-level scheduling, resulting in systems that are vulnerable to a lower-level form of overload that occurs when too many interrupts arrive. This paper describes three new techniques, two software-based and one hardware-based, for creating systems that delay or drop excessive interrupt requests before they can overload a processor. Our interrupt schedulers bound both the amount of work performed in interrupt context and its granularity, making it possible to provide strong progress guarantees to thread-level processing. We show that our solutions work and are efficient when implemented on embedded processors. We have also taken a description for a microprocessor in VHDL, modified it to include logic that prevents interrupt overload, synthesized the processor, and verified that it works using simulation. By allowing developers to avoid making assumptions about the worst-case interrupt rates of peripherals, our work fills an important gap in the chain of reasoning leading to a validated system. These techniques cannot replace careful system design, but they do provide a last-ditch safety guarantee in the presence of a serious malfunction.
Generation of permutations for SIMD processors
Authors: Kudriavtsev Alexei , Kogge Peter
Published: November 2005

Short vector (SIMD) instructions are useful in signal processing, multimedia, and scientific applications. They offer higher performance, lower energy consumption, and better resource utilization. However, compilers still do not have good support for SIMD instructions, and often the code has to be written manually in assembly language or using compiler builtin functions. Also, in some applications, higher parallelism could be achieved if compilers inserted permutation instructions that reorder the data in registers. In this paper we describe how we create SIMD instructions from regular code, and determine ordering of individual operations in the SIMD instructions to minimize the number of permutation instructions. Individual memory operations are grouped into SIMD operations based on their effective addresses. The SIMD data flow graph is then constructed by following data dependences from SIMD memory operations. Then, the orderings of operations are propagated from SIMD memory operations into the graph.We also describe our approach to compute decomposition of a given permutation into the permutation instructions of the target architecture. Experiments with our prototype compiler show that this approach scales well with the number of operations in SIMD instructions (SIMD width) and can be used to compile a number of important kernels, achieving up to 35% speedup.
WCRT analysis for a uniprocessor with a unified prioritized cache
Authors: Tan Yudong , Mooney Vincent J.
Published: November 2005

In this paper, we investigate the problem of inter-task cache interference in preemptive multi-tasking real-time systems. A prioritized cache is used to reduce cache conflicts among tasks by partitioning the cache. Cache partitions are assigned to tasks according to their priorities. We extend a known tool, SYMTA, in order to estimate the Worst Case Execution Time of tasks executing on a uniprocessor with a unified prioritized L1 cache. Furthermore, we apply a formal timing analysis approach to estimate the Worst Case Response Time of tasks using the prioritized cache. The prioritized cache is compared to a conventional set associative cache of the same size. Our experiments show that the WCRT estimate can be reduced up to 50% when a prioritized cache is used.
Syncopation
Authors: Bacon David F. , Cheng Perry , Grove David , Vechev Martin T.
Published: November 2005

Real-time garbage collection has been shown to be feasible, but for programs with high allocation rates, the utilization achievable is not sufficient for some systems.Since a high allocation rate is often correlated with a more high-level, abstract programming style, the ability to provide good real-time performance for such programs will help continue to raise the level of abstraction at which real-time systems can be programmed.We have developed techniques that allow generational collection to be used despite the problems caused by variance in program behavior over the short time scales in which a nursery can be collected.
Syncopation
allows such behavior to be detected by the scheduler in time for allocation to by-pass the nursery and allow real-time bounds to be met.We have provided an analysis of the costs of both generational and non-generational techniques, which allow the trade-offs to be evaluated quantitatively. We have also provided measurements of application behavior which show that while syncopation is necessary, the need for it is rare enough that generational collection can provide major improvements in real-time utilization. An additional technique,
arraylet pre-tenuring
, often significantly improves generational behavior.
Static determination of allocation rates to support real-time garbage collection
Authors: Mann Tobias , Deters Morgan , LeGrand Rob , Cytron Ron K.
Published: November 2005

While it is generally accepted that garbage-collected languages offer advantages over languages in which objects must be explicitly deallocated, real-time developers are leery of the adverse effects a garbage collector might have on real-time performance. Semiautomatic approaches based on regions have been proposed, but incorrect usage could cause unbounded storage leaks or program failure. Moreover, correct usage cannot be guaranteed at compile time. Recently, real-time garbage collectors have been developed that provide a guaranteed fraction of the CPU to the application, and the correct operation of those collectors has been proven, subject only to the specification of certain statistics related to the type and rate of objects allocated by the application. However, unless those statistics are provided or estimated appropriately, the collector may fail to collect dead storage at a rate sufficient to pace the application's need for storage. Overspecification of those statistics is safe but leaves the application with less than its possible share of the CPU, which may prevent the application from meeting its deadlines.In this paper we present a static analysis to bound conservatively an application's
allocation rate
. The analysis is based on a data flow framework that requires interprocedural evaluation. We present the framework and results from analyzing some Java benchmarks. Because static analysis is necessarily conservative, we also present measurements of our benchmarks' actual allocation rates.Our work is a necessary step toward making real-time garbage collectors attractive to the hard-real-time community. By guaranteeing a bound on statistics provided to a real-time collector, we can guarantee the operation of the collector for a given application.
Compiling for memory emergency
Authors: Kandemir Mahmut , Chen Guangyu , Kadayif Ismail
Published: November 2005

There has been a continued growth in the sales of mobile and embedded devices, in spite of the economic recession in many parts of the world. Many of these devices operate under tight memory bounds. Past research dealt with this problem and proposed both hardware and software solutions oriented toward reducing memory space requirements of embedded and mobile applications. One of the common characteristics of most of these prior efforts is that they assume the memory space available to an embedded application is fixed for the entire execution. Unfortunately, this is not a valid assumption in many execution environments since a typical embedded/mobile platform can have multiple applications executing concurrently and sharing a common memory space. As a result, the amount of memory available to a particular application can vary during execution. A particularly interesting scenario is what we call "memory emergency", where the size of the memory available to an application suddenly drops. If the application is not written to cope with this emergency scenario, the result would normally be a premature termination due to insufficient memory. In this paper, we propose compiler-based solutions to this memory emergency problem. The proposed compiler support modifies a given application code assuming a memory emergency model and reduces memory space demand (when necessary) by recomputing data values, thereby performing a tradeoff between memory space reduction and performance overhead. Our goal is to be able to work with the reduced memory space but minimize the performance overhead it brings. We evaluate the proposed approaches using twelve array-based embedded benchmarks. Our experimental analysis shows that the proposed approaches are very successful in responding to many memory emergency scenarios.
Recursion patterns and time-analysis
Authors: Barbosa Manuel , Cunha Alcino , Pinto Jorge Sousa
Published: November 2005

This paper explores some ideas concerning the time-analysis of functional programs defined by instantiating typical recursion patterns such as
folds, unfolds
, and
hylomorphisms.
The concepts in this paper are illustrated through a rich set of examples in the Haskell programming language. We concentrate on unfolds and folds (also known as anamorphisms and catamorphisms respectively) of recursively defined types, as well as the more general
hylomorphism
pattern. For the latter, we use as case-studies two famous sorting algorithms, mergesort and quicksort. Even though time analysis is not compositional, we argue that splitting functions to expose the explicit construction of the recursion tree and its later consumption helps with this analysis.
Forth sorts fruit down under
Authors: Frenger Paul
Published: November 2005

The Forth programming language, like grit, seems to get into everything.
Handling the subclassing anomaly with Object Teams
Authors: Furlong Jeff , Radenski Atanas
Published: November 2005

Existing Java software or libraries can evolve via subclassing. Unfortunately, subclassing may not properly support code adaptation when there are dependencies between classes. More precisely, subclassing in collections of related classes may require reimplementation of otherwise valid classes. This problem is defined as the subclassing anomaly, which is an issue when software evolution or code reuse is a goal of the programmer who is using existing classes. Object Teams offers an implicit fix to this problem and is largely compatible with the existing JVM's. In this paper, we evaluate how well Object Teams succeeds in providing a solution for a complex, real world project. Our results indicate that while Object Teams is a suitable solution for simple examples, it does not meet the requirements for large scale projects. The reasons why Object Teams fails in certain usages may prove useful to those who create linguistic modifications in languages or those who seek new methods for code adaptation.
AtomCaml
Authors: Ringenburg Michael F. , Grossman Dan
Published: November 2005

We have designed, implemented, and evaluated AtomCaml, an extension to Objective Caml that provides a synchronization primitive for atomic (transactional) execution of code. A first-class primitive function of type (unit->'a)->'a evaluates its argument (which may call other functions, even external C functions) as though no other thread has interleaved execution. Our design ensures fair scheduling and obstruction-freedom. Our implementation extends the Objective Caml bytecode compiler and run-time system to support atomicity. A logging-and-rollback approach lets us undo uncompleted atomic blocks upon thread pre-emption, and retry them when the thread is rescheduled. The mostly functional nature of the Caml language and the Objective Caml implementation's commitment to a uniprocessor execution model (i.e., threads are interleaved, not executed simultaneously) allow particularly efficient logging. We have evaluated the efficiency and ease-of-use of AtomCaml by writing libraries and microbenchmarks, writing a small application, and replacing all locking with atomicity in an existing, large multithreaded application. Our experience indicates the performance overhead is negligible, atomic helps avoid synchronization mistakes, and idioms such as condition variables adapt reasonably to the atomic approach.
JavaScript at ten years
Authors: Eich Brendan
Published: November 2005

This talk presents the tumultuous history of JavaScript, from its first appearance in Netscape 2 beta releases in the fall of 1995 through the present, with emphasis on the unvarnished, real-world side of designing, implementing, shipping, and standardizing a functional programming language used by millions of people. JavaScript was conceived of as an "object-based scripting language", but its inspiration came originally from Scheme, with an admixture of Self. Designing a language to fit the constraints of the target audience of HTML authors, the embedding browser application, and the market conditions of that time was challenging. We discuss what worked and what did not, and how the language evolved due to competition and
de jure
standardization. The talk ranges widely over the history of the web, including the recent renaissance of JavaScript and its development in the ECMA standards group. We close by presenting new work likely to appear in the next version of the language.
Backtracking, interleaving, and terminating monad transformers
Authors: Kiselyov Oleg , Shan Chung-chieh , Friedman Daniel P. , Sabry Amr
Published: November 2005

We design and implement a library for adding backtracking computations to any Haskell monad. Inspired by logic programming, our library provides, in addition to the operations required by the
MonadPlus
interface, constructs for fair disjunctions, fair conjunctions, conditionals, pruning, and an expressive top-level interface. Implementing these additional constructs is easy in models of backtracking based on streams, but not known to be possible in continuation-based models. We show that all these additional constructs can be
generically
and monadically realized using a single primitive
msplit
. We present two implementations of the library: one using success and failure continuations; and the other using control operators for manipulating delimited continuations.
Modular verification of concurrent assembly code with dynamic thread creation and termination
Authors: Feng Xinyu , Shao Zhong
Published: November 2005

Proof-carrying code (PCC) is a general framework that can, in principle, verify safety properties of arbitrary machine-language programs. Existing PCC systems and typed assembly languages, however, can only handle
sequential
programs. This severely limits their applicability since many real-world systems use some form of concurrency in their core software. Recently Yu and Shao proposed a logic-based "type" system for verifying concurrent assembly programs. Their thread model, however, is rather restrictive in that no threads can be created or terminated dynamically and no sharing of code is allowed between threads. In this paper, we present a new formal framework for verifying general multi-threaded assembly code with unbounded dynamic thread creation and termination as well as sharing of code between threads. We adapt and generalize the rely-guarantee methodology to the assembly level and show how to specify the semantics of thread "fork" with argument passing. In particular, we allow threads to have different assumptions and guarantees at different stages of their lifetime so they can coexist with the dynamically changing thread environment. Our work provides a foundation for certifying realistic multi-threaded programs and makes an important advance toward generating proof-carrying concurrent code.
Software metrics, measurement theory, and viewpoints
Authors: Konrad Erhard
Published: November 2005

This paper presents a critical discussion of a new approach to software quality assurance. Zuse and Bollmann, the protagonists of this approach, claim that they can offer a methodology for properly selecting and applying software metrics. Their approach incorporates ideas borrowed from measurement theory and information retrieval. In this paper, it is shown that Zuse and Bollmann go astray even under their own premises.
On the object-orientedness of C++
Authors: Liu Chung-Shyan
Published: November 2005

In this note, two different definitions of object-oriented programming, whether a class is equivalent to a type or not, will be presented. Then the relative merits of the two definitions, regarding encapsulation of objects, type checking, genericity, and inheritance of objects, will be discussed. In particular, a C++ sample program will be given to illustrate that the encapsulation of objects may be violated.
Exploiting multi-way branching to boost superscalar processor performance
Authors: Oyang Yen-Jen
Published: November 2005

This paper discusses exploiting multi-way branching to boost superscalar processor performance. The exploitation of multi-way branching contributes to a boost in superscalar processor performance through two effects: (1) increase of instruction-level parallelism and (2) reducing of the amount of branch penalty. The work presented in this paper comprises two conjunctive parts. The first part is a compiler technique called the SV (Shadow Variable) transformation. The second part is a new multi-way branching scheme developed in conjunction with the SV transformation. The SV transformation can transform program segments which multi-way branching is originally not applicable to into ones which multi-way branching is applicable to. The proposed multi-way branching scheme, meanwhile, is able to carry out multi-way branches efficiently, especially for those derived from applying the SV transformation, and requires no expensive hardware for implementation.
Top-down parsing in Coco-2
Authors: Dobler H.
Published: November 2005

Coco-2 [Dobler90] is a new compiler compiler with two interesting features: It allows the specification of the lexical structure, syntax and semantics of a source language within a single document
and
it implements a new top-down parsing method. This paper focuses on the new parsing method that conveniently incorporates the evaluation of semantic actions in table-driven top-down parsers. The new method is called
hybrid
because it is a powerful combination of table-driven top-down syntax analysis and the handling of semantic evaluation as implemented in recursive descent parsers. The most notable fact of this method is, that it provides the benefits of table-driven top-down parsing and recursive descent while avoiding their drawbacks.
Why a two pass front end?
Authors: Shepherd Janice C.
Published: November 2005

Compilers for some programming languages are traditionally considered to be best implemented with a front end (lexical analysis, semantic analysis and intermediate code generation phases) that makes only one pass over the source program. A FORTRAN compiler was converted from such a design to one that uses two passes for the benefit of obtaining a front end that is easier to understand and maintain. The details of which language features motivated this conversion are presented. Performance results are also presented that show there was only a 4% increase in compile time after the conversion.
A short introduction to the ABC language
Authors: Pemberton Steven
Published: November 2005

This article gives a quick overview of the programming language ABC and its implementations, and gives a few examples of ABC programs, plus details of where you can find more information.
The benefits of enumerated types in Modula-2
Authors: Cashman Mark
Published: November 2005

This paper shows that, contrary to [Lins90], enumerations are helpful to type safety in trongly-typed programming languages, such as Modula-2.
The ensemble system
Authors: Di Santo Michele , Russo Wilma
Published: November 2005

ENSEMBLE is a programmming system for writing concurrent programs on a personal computer (PC).ENSEMBLE consists of a library of Turbo Pascal
1
units to be used with applications written in the same language and executable on IBM PCs or compatibles under the MS-DOS
2
operating system. ENSEMBLE provides the programmer with a set of facilities and predefined abstractions that simplify the construction of concurrent programs. The main abstractions are coroutines and tasks.ENSEMBLE's main goal is to provide an environment that can be easily used by students for gaining experience in a wide variety of concurrent programming models and techniques. However, ENSEMBLE was designed to be also a satisfactory production tool for writing concurrent and real-time software on a PC.
A database design for graphical models
Authors: Dulli Susi , Milanese Vitaliano
Published: November 2005

In this paper we present an engineering data management system, that is a database which is supposed to store and support the manipulation of data about solid geometry objects. Some technical aspects are particularly addressed, which are related to the modeling environment, system architecture and data manipulation language.
Eiffel Linda
Authors: Jellinghaus Robert
Published: November 2005

Eiffel is a statically-typed object-oriented language which supports good software engineering techniques but provides no support for concurrency; Linda is a parallel programming model which provides a uniform semantics for coordination and communication among multiple processes. This paper describes an Eiffel Linda which injects the Linda operations into the Eiffel language. The resulting synthesis extends both Eiffel and Linda; the implications of the synergy between the two systems are examined, and suggestions for future work are proposed.We begin with an examination of the Eiffel execution model, with particular reference to its emphasis on the correct construction of software systems. We briefly describe the Linda language, and compare it to other parallelism models. The unified Eiffel Linda language is then presented, with discussion of the semantic issues which were considered in the course of its evolution, and details of the interesting features of our particular implementation. Comparisons to past work in Linda and in object-oriented concurrency are offered. In conclusion, we reflect on the significance of Eiffel Linda, and consider its relevance to future work in object-based concurrency.
Path feasibility, linear optimizers and the evaluate standard form
Authors: Coward P. David
Published: November 2005

Symbolic execution of a path through the source program can be used to assist in the generation of a test case to execute the path. One important step in this process is the assessment of the feasibility of the path. Numerical optimizers can be used for solving the set of constraints provided by the path condition (Boye75, Rama76). The construction of an optimization problem from a source program can be automated. The usual way to approach this is to translate the source program into an intermediate representation more suitable for extracting and symbolically executing paths (Asir79, Rama76).The creation of an intermediate form can be achieved in two ways. First, by direct translation from the source program. This requires a complex translator. Second, the source program can undergo several steps of translation into simpler or standard forms in the source language. The final version of the 'source' program is then translated into the intermediate form by a comparatively simple translator. This paper describes a series of translations which can be made to a COBOL source program. The EVALUATE construct provides a standard form for branching.
HARE
Authors: Teodosiu Dan
Published: November 2005

A highly optimizing Scheme compiler called HARE is presented. A combination of several optimization techniques allows for the generation of very efficient code. Easy portability of the compiler has been achieved through the use of a virtual machine as a target for code generation. The compiler will be used as a test-bed for fine-tuning the instruction set of a symbolic architecture, the S-Machine.
A comprehensive analytical model for garbage collection algorithms
Authors: Heymann Jürgen
Published: November 2005

We present an analytical model that allows to compare all known garbage collection (GC) algorithms w.r.t. various performance measures. The overhead functions are
natural
and
accurate
; natural in the sense that they are given in terms of easy to measure and tune parameters, accurate in the sense that they account for
all
relevant sources of time and space overhead of the different algorithms. Space overhead accounted for includes mark bits, mark stack, reference count bits/tables, entry tables for area-GC, object tables etc. as well as storage fragmentation. Time overhead components are e.g. time to mark/scan/copy nodes, update reference counts, check for forwarding pointers, synchronization costs etc.
CL/TB an allegro common Lisp programming interface for TransBase
Authors: Kempe J. , Lenz T. , Freitag B. , Shütz H. , Specht G.
Published: November 2005

This paper presents the "CL/TB" programming interface for Allegro CL (an implementation of Common Lisp.) and the relational database management system TransBase. The interface and its components are presently running on SUN UNIX workstations but can easily be installed on all major UNIX workstations. CL/TB supports data manipulation, data definition, and data control. The database system is called by sending SQL-statements as strings from Allegro CL. Basically, CL/TB offers the prominent services of the underlying TransBase programming interface (TBX). The services are successfully integrated into the functional environment of Lisp and enhanced by many additional features to improve ease of use, programming security, and error support. Thus operating on a database system via CL/TB is easy even for unexperienced users. Furthermore CL/TB is compatible with the relational algebra R-Lisp.Structure, design, implementation, and performance data axe presented and its application is illustrated by examples.
Type-safe linkage for variables and functions
Authors: Spinellis Diomidis
Published: November 2005

In a separate compilation environment type checks across modules are difficult to implement, because the natural place to perform them, the linker, is rarely under the control of the compiler developer. A solution to this problem, presented in the C++ Reference Manual, does not cope with global variables and function return types. It is asserted that lifting those limitations would require modifying the linker or providing an environment for separate compilation. We present a solution that lifts the limitations within the existing scheme.
Thoughts on large scale programming projects
Authors: McLaughlin Robert
Published: November 2005

Developing a theory of software design and implementation has absorbed a great deal of effort in the computer business. In practice, the theory is often ignored or proven to be of no value. In the following, I attempt to develop a pragmatic approach to large scale software projects.The basic issues of management are left out of such discussions: the issues of involving employees in their job and generating an attitude in them that management values them as creative members of a team.
A browsing interface for S-expressions
Authors: Yuasa Kei
Published: November 2005

This paper presents a new system for Lisp object inspecting. The author has implemented a system called "List Window" which provides Lisp programmers with a method for inspecting S-expressions on a screen. This system was designed in order to help Lisp programming, especially debugging.When developing the List Window system, it was necessary to output, a big list into a given sized terminal with proper indentations. The system sets a focal point in a list and truncates elements which are far from the focus. Main parts of this paper describe this method of truncating branches of a list.
Reliance on correlation data for complexity metric use and validation
Authors: MacDonell Stephen
Published: November 2005

This paper reports the results of an experiment to illustrate the hazards of using correlation data as the sole determinant for software metric use and validation. Three widely cited complexity metrics have been examined in relation to the frequency of software development errors.
Function preconditions in object oriented software
Authors: LeJacq Jean Pierre
Published: November 2005

Functions in nonobject oriented languages are typically designed to minimize any preconditions which must be satisfied before the function can be legally called. In object oriented languages this prescription can reduce the refinement of the function through derivation. A tradeoff must be made between refinement potential, efficiency, and risk of incorrect usage.
Compile-time transformations and optimization of parallel Divide-and-Conquer algorithms
Authors: Carpentieri B. , Mou G.
Published: November 2005

In this paper we show how it is often possible to transform and optimize parallel algorithms based on the Divide-and-Conquer paradigm at compile time. Our goal is to make Divide-and-Conquer algorithms suitable for implementation on hypercube-like parallel architectures, such as the Connection Machine, even if the original algorithm implies a division function that is not the left-right division and/or communication pattern that cannot be implemented by direct-neighbor communication.Our tools are the formal model of the Divide-and-Conquer paradigm developed in [4] and the parallel programming language derived from this model: Divacon [2], [3].Our main results concern the replacement of last-k communication (broadcast) and mirror image communication with correspondent communication and the transformation from odd-even division to left-right division and vice versa. By using each of the techniques described in this paper it is possible to improve many Divide-and-Conquer algorithms by a factor of log(n).
Concurrency & object-oriented programming
Authors: Nelson Michael L.
Published: November 2005

This paper serves as an introduction to concurrent and distributed object-oriented systems. This is a relatively new area, with few commercially available systems. Even those systems that are available have not yet stood up to the 'test of time'. Available information on those few systems that are commercially available, as well as several research efforts, is summarized and analyzed.
Which model of programming for LISP
Authors: Yuen C. K.
Published: November 2005

This article reviews models of programming applicable to Lisp, and argues that both the sequential model and the functional model have developed in directions of excessive complexity. For future developments, a mixed model based on old-style Lisp, but augmented with new parallel constructs, can provide a simpler tool for handling practical programming tasks.
Report on the programming language Haskell
Authors: Hudak Paul , Peyton Jones Simon , Wadler Philip , Boutel Brian , Fairbairn Jon , Fasel Joseph , Guzmán María M. , Hammond Kevin , Hughes John , Johnsson Thomas , Kieburtz Dick , Nikhil Rishiyur , Partain Will , Peterson John
Published: November 2005

"Some half dozen persons have written technically on combinatory logic, and most of these, including ourselves, have published something erroneous. Since some of our fellow sinners are among the most careful and competent logicians on the contemporary scene, we regard this as evidence that the subject is refractory. Thus fullness of exposition is necessory for accurary; and excessive condensation would be false economy here, even more than it is ordinarily."
Analogy by generalization—and the quest of the grail
Authors: Furtado Antonio L.
Published: November 2005

It is argued that a powerful kind of reasoning by analogy is provided by combining unification with most specific generalization. A revised version of an existing algorithm to compute the most specific generalization of terms is presented, which decides correctly whether or not new variables should be introduced in each case. Both unification and most specific generalization are extended to frames. It is indicated, as a research goal, the extension of these processes to more complex forms of knowledge representation, a particularly challenging example being the comparison of the structures of literary narratives.
CONS should not CONS its arguments, or, a lazy alloc is a smart alloc
Authors: Baker Henry G.
Published: November 2005

Lazy allocation
is a model for allocating objects on the execution stack of a high-level language which does not create dangling references. Our model provides safe transportation into the heap for objects that may survive the deallocation of the surrounding stack frame. Space for objects that do not survive the deallocation of the surrounding stack frame is reclaimed without additional effort when the stack is popped. Lazy allocation thus performs a first-level garbage collection, and if the language supports garbage collection of the heap, then our model can reduce the amortized cost of allocation in such a heap by filtering out the short-lived objects that can be more efficiently managed in LIFO order. A run-time mechanism called
result expectation
further filters out unneeded results from functions called only for their effects. In a shared-memory multi-processor environment, this filtering reduces contention for the allocation and management of global memory.Our model performs simple local operations, and is therefore suitable for an interpreter or a hardware implementation. Its overheads for functional data are associated only with
assignments
, making lazy allocation attractive for
mostly functional
programming styles. Many existing stack allocation optimizations can be seen as instances of this generic model, in which some portion of these local operations have been optimized away through static analysis techniques.Important applications of our model include the efficient allocation of temporary data structures that are passed as arguments to anonymous procedures which may or may not use these data structures in a stack-like fashion. The most important of these objects are functional arguments (
funargs
), which require some run-time allocation to preserve the local environment. Since a funarg is sometimes returned as a first-class value, its lifetime can survive the stack frame in which it was created. Arguments which are evaluated in a lazy fashion (Scheme
delays
or "suspensions") are similarly handled. Variable-length argument "lists" themselves can be allocated in this fashion, allowing these objects to become "first-class". Finally, lazy allocation correctly handles the allocation of a Scheme control stack, allowing Scheme continuations to become first-class values.
An observation on the C library procedure random()
Authors: Anastasio Thomas A. , Carlson William W.
Published: November 2005

Bit--level repetition of the sequences generated by the C library procedure random() have been observed as a function of seed. This note documents that observation. The effect has not been observed in drand48().
RT-MODULA2
Authors: Hernández Juan , Sanchez Juan Antonio
Published: November 2005

RT-Modula2 is a Modula2 extension for developing concurrent and real-time software. RT-Modula2 gives a simple, estructured and modular way of building concurrent and time depending programs. A new process scheduler has been built, and it has been specially designed for real time processes. This scheduler supports both, ordinary and time depending processes for writing concurrent and real time systems. In this paper, we present key features of RT-Modula2 at the implementation and syntactic level.The actual implementation of RT-Modula2 runs on SUN Workstations and on IBM PCs or compatibles.
Binary wrapping
Authors: Cargille Jon , Miller Barton P.
Published: November 2005

We present a technique, called
binary wrapping
, that allows object code routines to be instrumented. Binary wrapping allows tracing to be placed around (and sometimes within) proprietary code, when source code access is difficult or impossible. This technique is based on wrapping user-written code around the object code routine. No modifications are needed to the programs that call the object code routine. Binary wrapping has proven itself invaluable in instrumenting proprietary libraries, and may well be useful in other similar circumstances.
Lazy evaluation of C++ static constructors
Authors: Sabatella Marc
Published: November 2005

Static constructors in C+ + are functions that are executed implicitly to initialize objects at run time. Although a C+ + implementation is allowed to defer the construction of objects defined in a given translation unit until the first use of any function or object defined in that translation unit, most implementations execute all static constructors for the entire program before the invocation of main(). In this paper, we describe an implementation that defers the execution of static constructors for objects defined by a translation unit in a shared library until the first potential access of any function or object defined in that translation unit. This design relies on the deferred dynamic binding facility provided by the HP-UX shared library implementations. We describe how to modify our design to apply to statically linked programs as well, while avoiding most of the overhead normally associated with dynamic linking.
Modula-2 an alternative to C?
Authors: Angele Jürgen , Küpper Detlef
Published: November 2005

The programming languages C and Modula-2 are compared using criteria significant for efficiently constructing medium and large size commercial software systems. These criteria are motivated in section 2. Section 3 contrasts the features of the two languages which are relevant for the differences.
Compile-time partitioning and scheduling of parallel programs
Authors: Sarkar Vivek , Hennessy John
Published: November 2005

Partitioning and scheduling techniques are necessary to implement parallel languages on multiprocessors. Multiprocessor performance is maximized when parallelism between tasks is optimally traded off with communication and synchronization overhead. We present compile-time partitioning and scheduling techniques to achieve this trade-off.
Automatic generation of fixed-point-finding evaluators for circular, but well-defined, attribute grammars
Authors: Farrow Rodney
Published: November 2005

In the traditional formulation of attribute grammars (AGs) circularities are not allowed, that is, no attribute-instance in any derivation tree may be defined in terms of itself. Elsewhere in mathematics and computing, though, circular (or recursive) definitions are commonplace, and even essential. Given appropriate constraints, recursive definitions are well-founded, and the least fixed-points they denote are computable. This is also the case for circular AGs.

This paper presents constraints on individual attributes and semantic functions of an AG that are sufficient to guarantee that a circular AG specifies a well-defined translation and that circularly-defined attribute-instances can be computed via successive approximation. AGs that satisfy these constraints are called finitely recursive.

An attribute evaluation paradigm is presented that incorporates successive approximation to evaluate circular attribute-instances, along with an algorithm to automatically construct such an evaluator. The attribute evaluators so produced are static in the sense that the order of evaluation at each production-instance in the derivation-tree is determined at the time that each translator is generated.

A final algorithm is presented that tells which individual attributes and functions must satisfy the constraints.
Unifying view of recent LALR(1) lookahead set algorithms
Authors: Ives Fred
Published: November 2005

Since the introduction of LALR parsing, several algorithms have been presented for the computation of the lookahead sets needed to produce an LALR parser. The algorithm in Aho and Ullman[1] has perhaps received the widest exposure. The recent algorithms by DeRemer and Pennello[2] and Park, Choe, and Chang[4] are the most efficient.

A new algorithm has been developed from an algorithm originally based on the Aho and Ullman algorithm and subsequently modified to take advantage of the efficiencies introduced by the DeRemer and Pennello algorithm. The new algorithm performs better than the Park, Choe, and Chang algorithm, and both perform better than the DeRemer and Pennello algorithm. The reasons for the relative performances are easily understood when the algorithms are presented in a common light.
Very fast LR parsing
Authors: Pennello Thomas J.
Published: November 2005

LR parsers can be made to run 6 to 10 times as fast as the best table-interpretive LR parsers. The resulting parse time is negligible compared to the time required by the remainder of a typical compiler containing the parser.

A parsing speed of 1/2 million lines per minute on a computer similar to a VAX 11/780 was achieved, up from an interpretive speed of 40,000 lines per minute. A speed of 240,000 lines per minute on an Intel 80286 was achieved, up from an interpretive speed of 37,000 lines per minute.

The improvement is obtained by translating the parser's finite state control into assembly language. States become code memory addresses. The current input symbol resides in a register and a quick sequence of register-constant comparisons determines the next state, which is merely jumped to. The parser's push-down stack is implemented directly on a hardware stack. The stack contains code memory addresses rather than the traditional state numbers.

The strongly-connected components of the directed graph induced by the parser's terminal and nonterminal transitions are examined to determine a typically small subset of the states that require parse-time stack-overflow-check code when hardware does not provide the check automatically.

The increase in speed is at the expense of space: a factor of 2 to 4 increase in total table size can be expected, depending upon whether syntactic error recovery is required.
Integrating code generation and optimization
Authors: Fraser Christopher W. , Wendt Alan L.
Published: November 2005

This paper describes a compiler with a code generator and machine-directed peephole optimizer that are tightly integrated. Both functions are performed by a single rule-based rewriting system that matches and replaces patterns. This organization helps make the compiler simple, fast, and retargetable. It also corrects certain phase-ordering problems.
Global register allocation at link time
Authors: Wall David W.
Published: November 2005

In previous work in global register allocation, the compiler colors a conflict graph constructed from liveness dataflow information, in order to allocate the same register to many variables that are not simultaneously live. If two procedures are in separately compiled modules, however, the compiler must do this allocation separately for each procedure. As a result, the two procedures might use different registers for the same global, or the same register for different locals.

We can remove these problems if we delay the register allocation until link time. Our compiler produces object modules that can be linked and run without global register allocation, but includes with each object module a body of information describing how the module uses variables and procedures. A link-time register allocator then decides which variables are used most frequently, selects registers for them, and rewrites the code to reflect the decision that these variables reside in registers rather than in memory. Construction of the call graph allows us to use the same register for locals of procedures that are not simultaneously active, giving us most of the advantages of a full-scale coloring without the expense.

When we use our method for 52 registers, our benchmarks speed up by 10 to 25 percent. Even with only 8 registers, the speedup can be nearly that large if we use previously collected profile information to guide the allocation. We cannot do much better, because programs whose variables all fit in registers rarely speed up by more than 30%. Moreover, profiling shows us that we usually remove 60% to 90% of the loads and stores of scalar variables that the program performs during its execution, and often much more.
LogC
Authors: Yulin Feng , Tao Huang , Jing Li
Published: November 2005

LogC incorporates the rule oriented programming to the procedure oriented programming in C. It is designed to support knowledge inference for intelligent problem solving. This paper outlines the design features and demonstrates some results about inference efficiency by comparison with other AI languages.
Dynamic parsers and evolving grammars
Authors: Cabasino S. , Paolucci Pier S. , Todesco G. M.
Published: November 2005

We define "evolving grammars" as successions of static grammars and dynamic parsers as parsers able to follow the evolution of a grammar during the source program parsing. A growing context-free grammar will progressively incorporate production rules specific for the source program under parsing and will evolve following the context created by the source program itself toward a program specific context-free grammar. Dynamic parsers and growing grammars allow a syntactic-only parsing of programs written in powerful and problem adaptable programming languages. Moreover dynamic parsers easily perform purely syntactic strong type checking and operator overloading. The language used to specify grammar evolution and residual semantic actions can be the evolving language itself. The user can introduce new syntactic operators using a bootstrap procedure supported by the previously defined syntax.A dynamic parser ("ZzParser") has been developed by us and has been successfully employed by the APE 100 INFN group to develop a programming language ("ApeseLanguage") and other system software tools for the 100 GigaFlops SIMD parallel machine under development.