bluuebunny/crossref_metadata_2025 huggingface dataset:
Isomorphisms of generic recursive polynomial types
Authors: Fiore Marcelo
Published: November 2005

This paper gives the first decidability results on type isomorphism for recursive types, establishing the explicit decidability of type isomorphism for the type theory of sums and products over an inhabited generic recursive polynomial type. The technical development provides connections between themes in programming-language theory (type isomorphism) and computational algebra (Gröbner bases).
Asynchronous and deterministic objects
Authors: Caromel Denis , Henrio Ludovic , Serpette Bernard Paul
Published: November 2005

This paper aims at providing
confluence
and
determinism
properties in concurrent processes, more specifically within the paradigm of
object-oriented
systems. Such results should allow one to program parallel and distributed applications that behave in a deterministic manner, even if they are distributed over local or wide area networks. For that purpose, an object calculus is proposed. Its key characteristics are
asynchronous
communications with futures, and sequential execution within each process.While most of previous works exhibit confluence properties only on specific programs -- or patterns of programs, a general condition for confluence is presented here. It is further put in practice to show the deterministic behavior of a typical example.
Teaching the fatal disease
Authors: Holt Richard C.
Published: November 2005

This paper discusses the problems and advantages of using PL/I as an introductory programming language. The abhorrence of the author for certain qualities of PL/I is divulged. The economico-academico-IBMical inevitability of this programming language is touched upon. Finally, and of some possible worth, certain tenents of self discipline which are required when using this language for teaching (or anything else) are explored.
A consolidation of synchronization primitives
Authors: Holager Per
Published: November 2005

Various facilities for synchronizing parallell, asynchronous processes are reviewed.A new facility, consisting of the data type telegraph, and the operations acquire and release, is presented, and their implementation in the programming language MARY is sketched.The telegraph is a generalization of the Dijkstra semaphore. In addition to the services provided by the semaphore, the telegraph allows data to be passed between processes.
An experiment with the extensibility of SIMULA
Authors: Marlin C. D.
Published: November 2005

A method is described for introducing the semicoroutine sequencing statement
call
into versions of SIMULA which contain only the coroutine sequencing statements
detach
and
resume
. This is achieved by defining a class whose identifier can be used to prefix blocks within which the concept of
call
is required. This experiment illustrates the way in which SIMULA can easily be extended, while indicating some of the limitations of this extensibility.
Linear flowchart generator for a structured language
Authors: Roy Patrick , St-Denis Richard
Published: November 2005

This article refers to a paper by Nassi and Shneiderman published in this review [1]. They introduced a type of flowchart specially designed for structured programming. We have defined a similar flowchart language for the PASCAL programming language [2, 3] and designed a program which, given a program written in PASCAL, generates the corresponding flowchart. The article presents a description of the output produced by this flowchart generator.
Specification and uniform reference to data structures in PL/I
Authors: Sehwabe Daniel , Lucena Carlos J.
Published: November 2005

Through the use of a modified concept of cluster [1, 2] we propose the association of the notions of abstract data types and uniform reference to data structures to PL/I. The proposed programming mechanisms enhance PL/I by the addition of two new linguistic dimensions: a specification level and a common base language to handle the implementation of data structures. This report informally describes the syntax and semantics of the added constructs and gives an example of their use.
An implementation of backtracking for programming languages
Authors: Prenner Charles J. , Spitzen Jay M. , Wegbreit Ben
Published: November 2005

Primitive operations for backtracking and a technique for their implementation are described. The technique is applicable to all programming languages whose control structure is strictly hierarchical. A general stack model for such languages is presented and a realization of the backtracking primitives is described in terms of this model. The primitives give the user control over which assignents to variables will be 'undone' when backtracking. Moreover, their realization, at each point of choice, does not save the entire current machine state but only a relatively small amount of information sufficient to later reconstruct that machine state. Consequently, the implementation makes efficient use of storage and makes backtracking a practical progamming device for dealing with complex problems.
Automatic recognition of vector and parallel operations in a higher level language
Authors: Schneck Paul B.
Published: November 2005

A compiler for recognizing statements of a FORTRAN program which are suited for fast execution on a parallel or pipeline machine such as ILLIAC-IV, STAR or ASC is described. The technique employs "interval analysis" to provide flow information to the vector/parallel recognizer. Where profitable the compiler changes scalar variables to subscripted variables. The output of the compiler is an extension to FORTRAN which shows parallel and vector operations explicitly.
Programming with(out) the GOTO
Authors: Leavenworth B. M.
Published: November 2005

A brief history of the goto controversy (retention or deletion of the goto statement) is presented. After considering some of the theoretical and practical aspects of the problem, a summary of arguments both for and against the goto is given.
A case for the GOTO
Authors: Hopkins Martin E.
Published: November 2005

In recent years there has been much controversy over the use of the goto statement. This paper, while acknowledging that goto has been used too often, presents the case for its retention in current and future programming languages.
Interactors
Authors: Labrèche Pierre , Lamarche Louis
Published: November 2005

Interactors
is a run-time environment for embedded real-time software, which adds concurrency to the C++ object-oriented language.
Interactors
allows sequential processes to interact synchronously or asynchronously, and provides user-definable multiparty interactions. Several forms of selective wait, inspired by Ada, are provided. Scheduling algorithms follow Carnegie-Mellon University's recommendations for implementing hard deadline scheduling. Concepts are illustrated by simple application examples: Producer/Consumer and Dining Philosophers. This paper concludes by a description of the current implementation.
Comparative efficiency of general and residual parsers
Authors: Pagan Frank G.
Published: November 2005

Some fundamentals of the partial computation concept are concisely reviewed, including its relevance to the relationship between table-driven, general syntactic analyzers and source-language-specific, residual syntactic analyzers. A manual methodology for converting general parsers into generators of residual parsers is explained, using an LL(1) parser as a detailed example. The results of several experiments are reported, comparing the time and space efficiencies of different general parsers with corresponding, automatically generated, residual parsers. The latter parsers are usually several times faster than the former ones.
FORTH for microcomputers
Authors: James John S.
Published: November 2005

Forth is a unique threaded language ideally suited for microcomputers. Programs are incredibly compact; e.g. in 5K to 6K bytes you can get the interactive Forth compiler, running stand-alone as its own operating system including I/O drivers and other run-time routines, plus an assembler written in Forth (in case you want to optimize time-critical programs), virtual memory software, and a text editor. Not only does all this fit into 5K to 6K bytes (of which 4K are written in Forth), but it runs in the same space (plus 1K buffer), with no additional symbol table area, overlays, swapping, or use of any other software.And while Forth gives all the convenience of interactive interpreters, it is very fast. For most applications, the run-time overhead is 20 to 30% for minis and 70 to 100% for micros (compared to 1000% or more which is common for interpreters). Number-crunching applications may take longer. And when Forth isn't fast enough, the system's own assembler can be used to re-code inner loops.But the best news of all is that software development times are cut by half or more over assembly programming. The programming is entirely structured (there is no GOTO), and the resulting code is re-entrant and can be designed for PROM.Forth has been implemented on many microcomputers. A recommended configuration is 16K bytes and a terminal; a floppy is a good idea for storing source programs (and virtual memory for programs and data is supported). Forth works well with a CRT, so hard copy is less necessary.Forth has existed for several years, and is used commercially in a number of installations, but until recently it has been priced far out of reach of hobbyists, and even most computer experts have never heard of it. However, the language is in the public domain, and today low-cost versions are just becoming available. Also there is a new Forth Interest Group (787 Old County Rd, San Carlos, CA 94070), dedicated to letting the serious hobbyist and the professional know about Forth and how they can get it.
A study of the structural composition of PL/I programs
Authors: Elshoff James L.
Published: November 2005

Some research on a theory of the structural composition of an algorithm has recently been reported. The theory embodies models of operator and operand distributions that have been proposed by Bayer, Zipf, and Zweben. This paper reports a study in which the three models of operator distributions are compared with the measured distributions found in 34 PL/I programs. Two of three models, one by Zipf and one by Zweben, are shown to correlate highly with the measured distributions. Two variations of the Zipf model are then formulated and tested with good results. Also, the relationship between the method of counting operators and the models is investigated.
On generating binary decision trees with minimum nodes
Authors: Dailey W. H.
Published: November 2005

This paper describes a technique for generating binary decision trees from decision tables. It starts with a fully expended table and does a partial reduction with respect to the actions. The remainder of the reduction is done without reference to actions. Pollack's algorithm is finally applied to determine the next decision to consider.
On expressing control and data structures in predicate logic language ALGOL M
Authors: Glanc Alois
Published: November 2005

We define a procedural semantics for a many sorted predicate logic on many sorted models with generators. Then we express in Predicate Logic do forever, do until, do while, for thru, do unless, call, resume and demon control constructs. Data Structures can be represented using vectors (sequence of logic variables of the same sort.) This indicates that predicate logic can be a base of a high level language (ALGOL M) where programming can be as easy and efficient as in most other programming languages and whose syntax and semantics is simple and uniform. This language has systems programming like features, facilitating representation and utilization of knowledge in Artificial Intelligence Applications.
Summary of the characteristics of several "modern" programming languages
Authors: DeRemer Frank , Levy Philip , Hanson Steve , Jackson Philip , Jullig Richard , Pittman Tom
Published: November 2005

Some characteristics of nine recently developed or historically significant languages are discussed. Abstraction capabilities of the languages are noted in particular. Some characteristics of the languages are displayed in tabular form and others are presented in a separate discussion for each language. A hash coded string table program is written in each language.This paper is the result of a class project of a graduate seminar in programming linguistics at the University of California, Santa Cruz, led by Frank DeRemer
Lazy I/O is not the answer
Authors: Perkins Hal
Published: November 2005

Synchronization problems with input from terminal devices in Pascal have existed for several years. Recently, a technique known as "lazy I/O" has achieved popularity with implementors, and the latest published version of the draft ISO Pascal Standard is carefully worded to allow its use. This paper contends that lazy I/O is not an adequate general solution to the problem, and a simple solution that has been used successfully in several implementations is proposed as an alternative.
Common programming language ambiguity
Authors: Gootherts Paul D. , Davis James W.
Published: November 2005

When most people think of portable programs they think of programs that can be compiled by different compilers (with few, if any, changes required in the source code). It is an unwritten assumption that all of these compilers accept (to a reasonable degree) the same language.In this paper we shall demonstrate that this commonly required similarity can be relaxed considerably under certain circumstances. This is accomplished by introducing an unusual new technique for writing portable programs.
Using simple English sentences to call procedures
Authors: Groves Lindsay J.
Published: November 2005

Simple English sentences should be used to express procedure calls. This supports the use of procedures as abstraction mechanisms by making procedure calls more slef explanatory. Syntax rules for an English-like procedure call are presented and implementation techniques are discussed.
Parallel evolution programming language for data flow machines
Authors: Litvin Yury
Published: November 2005

In the first part of this paper we make a survey of data-driven control concepts and their relation to non-von-Neumann and parallel programming. We then introduce informally a high-level data flow language, PEP, which implements these concepts in a simple and clear form, bringing them closer to practical use by the programmers.The second part of the paper (to appear) will be a PEP programmer's manual which provides more formal description of the language.
Relational data bases in the design of program construction systems
Authors: Ceri S. , Crespi-Reghizzi S.
Published: November 2005

A methodology for designing and implementing program construction systems using relational data bases is presented. Relations are the only data structures used by them and in the definition of interfaces between subsystems. A special-purpose relational database manager (RDB) has been designed for this application.Two large projects using this approach are described. ART (Ada-Relational-Translator) is an experimental compiler-interpreter for ADA in which all subsystems, including parser, semantic analyzer, interpreter and kernel, use relations as their only data structure; the relational approach has been pushed to the upmost to achieve fast prototyping. MML (Multi-Micro Line) is a tool-set for constructing program programs for multi-microprocessors targets, in which relations are used for allocation and configuration control. Both experiences confirm the validity of the approach for managing team work in evolving projects.
Abstracting linked data structures using incremental records
Authors: Woitok Rainer
Published: November 2005

The implementation of an abstract data type "list" using the techniques currently available in some modern programming languages is not as easy as it seems on first glance. The problems inherent in various realizations of such an abstract type are discussed, and a solution is proposed which avoids them. This solution is based on a mechanism called "incremental record declaration" and on generic modules. The combination of these concepts allows an implementation of abstractions which obeys such principles as information hiding, modularity and locality.
A note on types and prototypes
Authors: Wharton R. Michael
Published: November 2005

The notion of "type" in programming languages is considered and the competing notion of "prototype" is introduced. It is shown that a language with prototypes has the same computational power as an analogous language with types, but is conceptually simpler and has fewer rules. Finally, it is shown that a program written in a language with prototypes has a smaller name space than the corresponding program written in a language with types.
Differences between ANS and ISO standards for Pascal
Authors: Zemrowski Kenneth M.
Published: November 2005

Several differences exist between the documents for American National Standard Programming Language Pascal and the International Standard Pascal. Differences arose because of concern by X3J9/IEEE Joint Pascal Committee over ambiguities. One of these ambiguities was questioned by Dr. M. Stadel's letter "A Remark on the ISO-Standard for Pascal," which appeared in SIGPLAN Notices, March 1984.
The efficiency of storage management schemes for Ada programs
Authors: Gupta Rajiv , Soffa Mary Lou
Published: November 2005

The efficient implementation of high level languages which support concurrency is imperative, particularly in such application areas as embedded real-time systems. Various storage management schemes have been proposed for the implementation concurrency. In this work, a methodology is presented for evaluating the performance of these schemes including the standard heap, Berryheap, cactus stack and quantized heap when used for Ada programs. The methodology involves the generation of workload traces from an executing program and the use of simulators of the alternative storage management schemes to produce measures of the performances of the schemes. The performance evaluation metrics used are space, time and the space-time product.
Extensions in Pascal implementations
Authors: Joslin David
Published: November 2005

The Pascal standard (BS6192/ISO7185) is due for revision in about 1987, with BSI as the "sponsoring body". Consideration of the revision has now begun within BSI. In addition, the Joint Pascal Committee (JPC) of ANSI X3J9 and of IEEE has coordinated a great deal of research into proposed extensions to the Pascal language, some of which will undoubtedly be incorporated into the revised standard.
gprof
Authors: Graham Susan L. , Kessler Peter B. , McKusick Marshall K.
Published: November 2005

We extended the UNIX® system's profiler by gathering arcs in the call graph of a program. Here is it 20 years later and this profiler is still in daily use. Why is that? It's not because there aren't well-known areas for improvement.Large complex programs are composed of many small routines that implement abstractions for the routines that call them. To be useful, an execution profiler must attribute execution time in a way that is significant for the logical structure of a program as well as for its textual decomposition. This data must then be displayed to the user in a convenient and informative way. The
gprof
profiler accounts for the running time of called routines in the running time of the routines that call them. The design and use of this profiler is described.
Optimization of range checking
Authors: Markstein Victoria , Markstein Peter , Cocke John
Published: November 2005

An analysis is given for optimizing run-time range checks in regions of high execution frequency. These optimizations are accomplished using strength reduction, code motion and common subexpression elimination. Test programs, using the above optimizations, are used to illustrate run-time improvements.
Register allocation by priority-based coloring
Authors: Chow Fred , Hennessy John
Published: November 2005

The classic problem of global register allocation is treated in a heuristic and practical manner by adopting the notion of priorities in node-coloring. The assignment of priorities is based on estimates of the benefits that can be derived from allocating individual quantities in registers. Using the priorities, the exponential coloring process can be made to run in linear time. Since the costs involved in register allocation are taken into account, the algorithm does not over-allocate. The algorithm can be parameterized to cater to different fetch characteristics and register configurations among machines. Measurements indicate that the register allocation scheme is effective on a number of target machines. The results confirm that, using priority-based coloring, global register allocation can be performed practically and efficiently.
Real-time concurrent collection on stock multiprocessors
Authors: Appel Andrew W.
Published: November 2005

We've designed and implemented a copying garbage-collection algorithm that is efficient, real-time, concurrent, runs on commercial uniprocessors and shared-memory multiprocessors, and requires no change to compilers. The algorithms uses standard virtual-memory hardware to detect references to "from space" objects and to synchronize the collector and mutator threads. We've implemented and measured a prototype running on SRC's 5-processor Firefly. It will be straightforward to merge our techniques with generational collection. An incremental, non-concurrent version could be implemented easily on many versions of Unix.
Interprocedural slicing using dependence graphs
Authors: Horwitz Susan , Reps Thomas , Binkley David
Published: November 2005

A slice of a program with respect to a program point
p
and variable
x
consists of all statements of the program that might affect the value of
x
at point
p
. This paper concerns the problem of interprocedural slicing -- generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. To solve this problem, we introduce a new kind of graph to represent programs, called a
system dependence graph
, which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. Our main result is an algorithm for interprocedural slicing that uses the new representation.The chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. To handle this problem, system dependence graphs include some data-dependence edges that represent
transitive
dependencies due to the effects of procedure calls, in addition to the conventional direct-dependence edges. These edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. This structure takes the form of an attribute grammar. The step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.
Coloring heuristics for register allocation
Authors: Briggs Preston , Cooper Keith D. , Kennedy Ken , Torczon Linda
Published: November 2005

We describe an improvement to a heuristic introduced by Chaitin for use in graph coloring register allocation. Our modified heuristic produces better colorings, with less spill code. It has similar compile-time and implementation requirements. We present experimental data to compare the two methods.
A retrospective on
Authors: Chambers Craig , Ungar David
Published: November 2005

Dynamically-typed object-oriented languages please programmers, but their lack of static type information penalizes performance. Our new implementation techniques extract static type information from declaration-free programs. Our system compiles several copies of a given procedure, each
customized
for one receiver type, so that the type of the receiver is bound at compile time. The compiler
predicts
types that are statically unknown but likely, and inserts run-time type tests to verify its predictions. It
splits
calls, compiling a copy on each control path, optimized to the specific types on that path. Coupling these new techniques with compile-time message lookup, aggressive procedure inlining, and traditional optimizations has doubled the performance of dynamically-typed object-oriented languages.
How to read floating point numbers accurately
Authors: Clinger William D.
Published: November 2005

Converting decimal scientific notation into binary floating point is nontrivial, but this conversion can be performed with the best possible accuracy without sacrificing efficiency.Consider the problem of converting decimal scientific notation for a number into the best binary floating point approximation to that number, for some fixed precision. This problem cannot be solved using arithmetic of any fixed precision. Hence the
IEEE Standard for Binary Floating-Point Arithmetic
does not require the result of such a conversion to be the best approximation.This paper presents an efficient algorithm that always finds the best approximation. The algorithm uses a few extra bits of precision to compute an IEEE-conforming approximation while testing an intermediate result to determine whether the approximation could be other than the best. If the approximation might not be the best, then the best approximation is determined by a few simple operations on multiple-precision integers, where the precision is determined by the input. When using 64 bits of precision to compute IEEE double precision results, the algorithm avoids higher-precision arithmetic over 99% of the time.The input problem considered by this paper is the inverse of an output problem considered by Steele and White: Given a binary floating point number, print a correctly rounded decimal representation of it using the smallest number of digits that will allow the number to be read without loss of accuracy. The Steele and White algorithm assumes that the input problem is solved; an imperfect solution to the input problem, as allowed by the IEEE standard and ubiquitous in current practice, defeats the purpose of their algorithm.
How to print floating-point numbers accurately
Authors: Steele Guy L. , White Jon L.
Published: November 2005

We present algorithms for accurately converting floating-point numbers to decimal representation. The key idea is to carry along with the computation an explicit representation of the required rounding accuracy.We begin with the simpler problem of converting fixed-point fractions. A modification of the well-known algorithm for radix-conversion of fixed-point fractions by multiplication explicitly determines when to terminate the conversion process; a variable number of digits are produced. The algorithm has these properties:• No information is lost; the original fraction can be recovered from the output by rounding.• No "garbage digits" are produced.• The output is correctly rounded.• It is never necessary to propagate carries on rounding.We then derive two algorithms for
free-format
out-put of floating-point numbers. The first simply scales the given floating-point number to an appropriate fractional range and then applies the algorithm for fractions. This is quite fast and simple to code but has inaccuracies stemming from round-off errors and oversimplification. The second algorithm guarantees mathematical accuracy by using multiple-precision integer arithmetic and handling special cases. Both algorithms produce no more digits than necessary (intuitively, the "1.3 prints as 1.2999999" problem does not occur).Finally, we modify the free-format conversion algorithm for use in
fixed-format
applications. Information may be lost if the fixed format provides too few digit positions, but the output is always correctly rounded. On the other hand, no "garbage digits" are ever produced, even if the fixed format specifies too many digit positions (intuitively, the "4/3 prints as 1.333333328366279602" problem does not occur).
Predicting program behavior using real or estimated profiles
Authors: Wall David W.
Published: November 2005

There is a growing interest in optimizations that depend on or benefit from an execution profile that tells where time is spent. How well does a profile from one run describe the behavior of a different run, and how does this compare with the behavior predicted by static analysis of the program? This paper defines two abstract measures of how well a profile predicts actual behavior. According to these measures, real profiles indeed do better than estimated profiles, usually. A perfect profile from an earlier run with the same data set, however, does better still, sometimes by a factor of two. Unfortunately, using such a profile is unrealistic, and can lead to inflated expectations of a profile-driven optimization.
A safe approximate algorithm for interprocedural pointer aliasing
Authors: Landi William , Ryder Barbara G.
Published: November 2005

During execution, when two or more names exist for the same location at some program point, we call them
aliases.
In a language which allows arbitrary pointers, the problem of determining aliases at a program point is
P
-space-hard [Lan92]. We present an algorithm for the Conditional May Alias problem, which can be used to safely approximate Interprocedural May Alias in the presence of pointers. This algorithm is as precise as possible in the worst case and has been implemented in a prototype analysis tool for C programs. Preliminary speed and precision results are presented.
Balanced scheduling
Authors: Kerns Daniel R. , Eggers Susan J.
Published: November 2005

Traditional list schedulers order instructions based on an optimistic estimate of the load delay imposed by the implementation. Therefore they cannot respond to variations in load latencies (due to cache hits or misses, congestion in the memory interconnect, etc.) and cannot easily be applied across different implementations. We have developed an alternative algorithm, known as balanced scheduling, that schedules instructions based on an estimate of the amount of instruction level parallelism in the program. Since scheduling decisions are program- rather than machine-based, balanced scheduling is unaffected by implementation changes. Since it is based on the amount of instruction level parallelism that a program can support, it can respond better to variations in load latencies. Performance improvements over a traditional list scheduler on a Fortran workload and simulating several different machine types (cache-based workstations, large parallel machines with a multipath interconnect and a combination, all with non-blocking processors) are quite good, averaging between 3% and 18%.
ATOM
Authors: Srivastava Amitabh , Eustace Alan
Published: November 2005

ATOM
(
A
nalysis
T
ools with
OM
) is a single framework for building a wide range of customized program analysis tools. It provides the common infrastructure present in all code-instrumenting tools; this is the difficult and time-consuming part. The user simply defines the tool-specific details in instrumentation and analysis routines. Building a basic block counting tool like Pixie with ATOM requires only a page of code.ATOM, using OM link-time technology, organizes the final executable such that the application program and user's analysis routines run in the same address space. Information is directly passed from the application program to the analysis routines through simple procedure calls instead of inter-process communication or files on disk. ATOM takes care that analysis routines do not interfere with the program's execution, and precise information about the program is presented to the analysis routines at all times. ATOM uses no simulation or interpretation.ATOM has been implemented on the Alpha AXP under OSF/1. It is efficient and has been used to build a diverse set of tools for basic block counting, profiling, dynamic memory recording, instruction and data cache simulation, pipeline simulation, evaluating branch prediction, and instruction scheduling.
TIL
Authors: Tarditi David , Morrisett Greg , Cheng Perry , Stone Chris , Harper Robert , Lee Peter
Published: November 2005

The goal of the TIL project was to explore the use of Typed Intermediate Languages to produce high-performance native code from Standard ML (SML). We believed that existing SML compilers were doing a good job of conventional functional language optimizations, as one might find in a LISP compiler, but that inadequate use was made of the rich type information present in the source language. Our goal was to show that we could get much greater performance by propagating type information through to the back end of the compiler, without sacrificing the advantages afforded by loop-oriented and other optimizations.We also confirmed that using typed intermediate languages dramatically improved the reliability and maintainability of the compiler itself. In particular, we were able to use the type system to express critical invariants, and enforce those invariants through type checking. In this respect, TIL introduced and popularized the notion of a certifying compiler, which attaches a checkable certificate of safety to its generated code. In turn, this led directly to the idea of certified object code, inspiring the development of Proof-Carrying Code and Typed Assembly Language as certified object code formats.
Thin locks
Authors: Bacon David F. , Konuru Ravi , Murthy Chet , Serrano Mauricio J.
Published: November 2005

Language-supported synchronization is a source of serious performance problems in many Java programs. Even single-threaded applications may spend up to half their time performing useless synchronization due to the thread-safe nature of the Java libraries. We solve this performance problem with a new algorithm that allows lock and unlock operations to be performed with only a few machine instructions in the most common cases. Our locks only require a partial word per object, and were implemented without increasing object size. We present measurements from our implementation in the JDK 1.1.2 for AIX, demonstrating speedups of up to a factor of 5 in micro-benchmarks and up to a factor of 1.7 in real programs.
Analysis of event synchronization in a parallel programming tool
Authors: Callahan D. , Kennedy K. , Subhlok J.
Published: November 2005

Understanding synchronization is important for a parallel programming tool that uses dependence analysis as the basis for advising programmers on the correctness of parallel constructs. This paper discusses static analysis methods that can be applied to parallel programs with event variable synchronization. The objective is to be able to predict potential data races in a parallel program. The focus is on how dependencies and synchronization statements inside loops can be used to analyze complete programs with parallel loop and parallel case style parallelism.
Design and distributed implementation of the parallel logic language shared Prolog
Authors: Ambriola V. , Ciancarini P. , Danelutto M.
Published: November 2005

The parallel logic language Shared Prolog embeds Prolog as its sequential component. A program is Shared Prolog is composed of a set of logic agents, i.e. Prolog programs, that communicate associatively via a shared workspace called blackboard.

The distinct features that characterize Shared Prolog with respect to other parallel (logic) languages are: scheduling of agents and granularity of parallelism explicitly controlled; Prolog embedded in the language; intrinsic modularity; associative send/receive of messages among agents with a simple operational semantics in terms of assert/retract of clauses. The model of communication puts Shared Prolog in the Linda family of parallel languages.

The current prototype implementation is exposed. The architecture of the system is a distributed network of extended Prolog interpreters running under Unix and communicating via Internet sockets, and was obtained refining a specification written in SP itself.
Employing register channels for the exploitation of instruction level parallelism
Authors: Gupta R.
Published: November 2005

A multiprocessor system capable of exploiting fine-grained parallelism must support efficient synchronization and data passing mechanisms. This paper demonstrates the use of shared register channels as the communication mechanism among processors in a multiprocessor chip. A register channel is provided with a synchronization bit that is used to ensure that a processor succeeds in reading a channel only after the channel has been written to. In contrast to a VLIW machine a system with channels does not require strict lockstep operation of its processors. This reduces the delays caused by unpredictable events such as memory bank conflicts. Providing channels accessible at the speed of registers constraints the number of channels that can be supported in hardware. This paper presents compile-time techniques that efficiently allocate the channels and successfully exploit the fine-grained parallelism using a small number of channels. The scheduling of operations is carried out in a manner that reduces communication among the processors and hence the number of channels required. Redundant synchronizations subsumed by other synchronizations are eliminated and channels are reused whenever possible. Results of experiments demonstrating the effectiveness of the techniques in utilizing a small number of channels are presented.
Supporting shared data structures on distributed memory architectures
Authors: Koelbel C. , Mehrotra P. , Van Rosendale J.
Published: November 2005

Programming nonshared memory systems is more difficult than programming shared memory systems, since there is no support for shared data structures. Current programming languages for distributed memory architectures force the user to decompose all data structures into separate pieces, with each piece “owned” by one of the processors in the machine, and with all communication explicitly specified by low-level message-passing primitives. This paper presents a new programming environment for distributed memory architectures, providing a global name space and allowing direct access to remote parts of data values. We describe the analysis and program transformations required to implement this environment, and present the efficiency of the resulting code on the NCUBE/7 and IPSC/2 hypercubes.
Race checking by context inference
Authors: Henzinger Thomas A. , Jhala Ranjit , Majumdar Rupak
Published: November 2005

Software model checking has been successful for
sequential
programs, where predicate abstraction offers suitable models, and counterexample-guided abstraction refinement permits the automatic inference of models. When checking
concurrent
programs, we need to abstract threads as well as the contexts in which they execute. Stateless context models, such as predicates on global variables, prove insufficient for showing the absence of race conditions in many examples. We therefore use richer context models, which combine (1) predicates for abstracting data state, (2) control flow quotients for abstracting control state, and (3) counters for abstracting an unbounded number of threads. We infer suitable context models automatically by a combination of counterexample-guided abstraction refinement, bisimulation minimization, circular assume-guarantee reasoning, and parametric reasoning about an unbounded number of threads. This algorithm, called CIRC, has been implemented in BLAST and succeeds in checking many examples of NESC code for data races. In particular, BLAST proves the absence of races in several cases where previous race checkers give false positives.
KISS
Authors: Qadeer Shaz , Wu Dinghao
Published: November 2005

The design of concurrent programs is error-prone due to the interaction between concurrently executing threads. Traditional automated techniques for finding errors in concurrent programs, such as model checking, explore all possible thread interleavings. Since the number of thread interleavings increases exponentially with the number of threads, such analyses have high computational complexity. In this paper, we present a novel analysis technique for concurrent programs that avoids this exponential complexity. Our analysis transforms a concurrent program into a sequential program that simulates the execution of a large subset of the behaviors of the concurrent program. The sequential program is then analyzed by a tool that only needs to understand the semantics of sequential execution. Our technique
never
reports false errors but may miss errors. We have implemented the technique in KISS, an automated checker for multithreaded C programs, and obtained promising initial results by using KISS to detect race conditions in Windows device drivers.
Dynamic path-based software watermarking
Authors: Collberg C. , Carter E. , Debray S. , Huntwork A. , Kececioglu J. , Linn C. , Stepp M.
Published: November 2005

Software watermarking is a tool used to combat software piracy by embedding identifying information into a program. Most existing proposals for software watermarking have the shortcoming that the mark can be destroyed via fairly straightforward semantics-preserving code transformations. This paper introduces path-based watermarking, a new approach to software watermarking based on the dynamic branching behavior of programs. The advantage of this technique is that error-correcting and tamper-proofing techniques can be used to make path-based watermarks resilient against a wide variety of attacks. Experimental results, using both Java bytecode and IA-32 native code, indicate that even relatively large watermarks can be embedded into programs at modest cost.
Fast searches for effective optimization phase sequences
Authors: Kulkarni Prasad , Hines Stephen , Hiser Jason , Whalley David , Davidson Jack , Jones Douglas
Published: November 2005

It has long been known that a fixed ordering of optimization phases will not produce the best code for every application. One approach for addressing this phase ordering problem is to use an evolutionary algorithm to search for a specific sequence of phases for each module or function. While such searches have been shown to produce more efficient code, the approach can be extremely slow because the application is compiled and executed to evaluate each sequence's effectiveness. Consequently, evolutionary or iterative compilation schemes have been promoted for compilation systems targeting embedded applications where longer compilation times may be tolerated in the final stage of development. In this paper we describe two complementary general approaches for achieving faster searches for effective optimization sequences when using a genetic algorithm. The first approach reduces the search time by avoiding unnecessary executions of the application when possible. Results indicate search time reductions of 65% on average, often reducing searches from hours to minutes. The second approach modifies the search so fewer generations are required to achieve the same results. Measurements show that the average number of required generations decreased by 68%. These improvements have the potential for making evolutionary compilation a viable choice for tuning embedded applications.
Inducing heuristics to decide whether to schedule
Authors: Cavazos John , Moss J. Eliot B.
Published: November 2005

Instruction scheduling is a compiler optimization that can improve program speed, sometimes by 10% or more, but it can also be expensive. Furthermore, time spent optimizing is more important in a Java just-in-time (JIT) compiler than in a traditional one because a JIT compiles code at run time, adding to the running time of the program. We found that, on any given block of code, instruction scheduling often does not produce significant benefit and sometimes degrades speed. Thus, we hoped that we could focus scheduling effort on those blocks that benefit from it.Using supervised learning we induced heuristics to predict which blocks benefit from scheduling. The induced function chooses, for each block, between list scheduling and not scheduling the block at all. Using the induced function we obtained over 90% of the improvement of scheduling every block but with less than 25% of the scheduling effort. When used in combination with profile-based adaptive optimization, the induced function remains effective but gives a smaller reduction in scheduling effort. Deciding when to optimize, and which optimization(s) to apply, is an important open problem area in compiler research. We show that supervised learning solves one of these problems well.
Array regrouping and structure splitting using whole-program reference affinity
Authors: Zhong Yutao , Orlovich Maksim , Shen Xipeng , Ding Chen
Published: November 2005

While the memory of most machines is organized as a hierarchy, program data are laid out in a uniform address space. This paper defines a model of
reference affinity
, which measures how close a group of data are accessed together in a reference trace. It proves that the model gives a hierarchical partition of program data. At the top is the set of all data with the weakest affinity. At the bottom is each data element with the strongest affinity. Based on the theoretical model, the paper presents
k-distance analysis
, a practical test for the hierarchical affinity of source-level data. When used for array regrouping and structure splitting,
k
-distance analysis consistently outperforms data organizations given by the programmer, compiler analysis, frequency profiling, statistical clustering, and all other methods we have tried.
GraalBench
Authors: Antochi Iosif , Juurlink Ben , Vassiliadis Stamatis , Liuha Petri
Published: November 2005

In this paper we consider implementations of embedded 3D graphics and provide evidence indicating that 3D benchmarks employed for desktop computers are not suitable for mobile environments. Consequently, we present GraalBench, a set of 3D graphics workloads representative for contemporary and emerging mobile devices. In addition, we present detailed simulation results for a typical rasterization pipeline. The results show that the proposed benchmarks use only a part of the resources offered by current 3D graphics libraries. For instance, while each benchmark uses the texturing unit for more than 70% of the generated fragments, the alpha unit is employed for less than 13% of the fragments. The Fog unit was used for 84% of the fragments by one benchmark, but the other benchmarks did not use it at all. Our experiments on the proposed suite suggest that the texturing, depth and blending units should be implemented in hardware, while, for instance, the dithering unit may be omitted from a hardware implementation. Finally, we discuss the architectural implications of the obtained results for hardware implementations.