bluuebunny/crossref_metadata_2025 huggingface dataset:
An abstract interpretation-based framework for software watermarking
Authors: Cousot Patrick , Cousot Radhia
Published: November 2005

Software watermarking consists in the intentional embedding of indelible stegosignatures or watermarks into the subject software and extraction of the stegosignatures embedded in the stegoprograms for purposes such as intellectual property protection. We introduce the novel concept of
abstract software watermarking
. The basic idea is that the watermark is hidden in the program code in such a way that it can only be extracted by an abstract interpretation of the (maybe non-standard) concrete semantics of this code. This static analysis-based approach allows the watermark to be recovered even if only a small part of the program code is present and does not even need that code to be executed. We illustrate the technique by a simple abstract watermarking protocol for methods of Java™ classes. The concept applies equally well to any other kind of software (including hardware originally specified by software).
Abstract non-interference
Authors: Giacobazzi Roberto , Mastroeni Isabella
Published: November 2005

In this paper we generalize the notion of non-interference making it parametric relatively to what an attacker can analyze about the input/output information flow. The idea is to consider attackers as data-flow analyzers, whose task is to reveal properties of confidential resources by analyzing public ones. This means that no unauthorized flow of information is possible from confidential to public data, relatively to the degree of precision of an attacker. We prove that this notion can be fully specified in standard abstract interpretation framework, making the degree of security of a program a property of its semantics. This provides a comprehensive account of non-interference features for language-based security. We introduce systematic methods for extracting attackers from programs, providing domain-theoretic characterizations of the most precise attackers which cannot violate the security of a given program. These methods allow us both to compare attackers and program secrecy by comparing the corresponding abstractions in the lattice of abstract interpretations, and to design automatic program certification tools for language-based security by abstract interpretation.
A semantics for web services authentication
Authors: Bhargavan Karthikeyan , Fournet Cédric , Gordon Andrew D.
Published: November 2005

We consider the problem of specifying and verifying cryptographic security protocols for XML web services. The security specification WS-Security describes a range of XML security tokens, such as username tokens, public-key certificates, and digital signature blocks, amounting to a flexible vocabulary for expressing protocols. To describe the syntax of these tokens, we extend the usual XML data model with symbolic representations of cryptographic values. We use predicates on this data model to describe the semantics of security tokens and of sample protocols distributed with the Microsoft WSE implementation of WS-Security. By embedding our data model within Abadi and Fournet's applied pi calculus, we formulate and prove security properties with respect to the standard Dolev-Yao threat model. Moreover, we informally discuss issues not addressed by the formal model. To the best of our knowledge, this is the first approach to the specification and verification of security protocols based on a faithful account of the XML wire format.
The space cost of lazy reference counting
Authors: Boehm Hans-J.
Published: November 2005

Reference counting memory management is often advocated as a technique for reducing or avoiding the pauses associated with tracing garbage collection. We present some measurements to remind the reader that classic reference count implementations may in fact exhibit longer pauses than tracing collectors.We then analyze reference counting with lazy deletion, the standard technique for avoiding long pauses by deferring deletions and associated reference count decrements, usually to allocation time. Our principal result is that if each reference count operation is constrained to take constant time, then the overall space requirements can be increased by a factor of Ω(
R
) in the worst case, where
R
is the ratio between the size of the largest and smallest allocated object. This bound is achievable, but probably large enough to render this design point useless for most real-time applications.We show that this space cost can largely be avoided if allocating an $n$ byte object is allowed to additionally perform
O
(
n
) reference counting work.
Abstractions from proofs
Authors: Henzinger Thomas A. , Jhala Ranjit , Majumdar Rupak , McMillan Kenneth L.
Published: November 2005

The success of model checking for large programs depends crucially on the ability to efficiently construct parsimonious abstractions. A predicate abstraction is parsimonious if at each control location, it specifies only relationships between
current
values of variables, and only those which are required for proving correctness. Previous methods for automatically refining predicate abstractions until sufficient precision is obtained do not systematically construct parsimonious abstractions: predicates usually contain symbolic variables, and are added heuristically and often uniformly to many or all control locations at once. We use Craig interpolation to efficiently construct, from a given abstract error trace which cannot be concretized, a parsominous abstraction that removes the trace. At each location of the trace, we infer the relevant predicates as an interpolant between the two formulas that define the past and the future segment of the trace. Each interpolant is a relationship between current values of program variables, and is relevant only at that particular program location. It can be found by a linear scan of the proof of infeasibility of the trace.We develop our method for programs with arithmetic and pointer expressions, and call-by-value function calls. For function calls, Craig interpolation offers a systematic way of generating relevant predicates that contain only the local variables of the function and the values of the formal parameters when the function was called. We have extended our model checker
Blast
with predicate discovery by Craig interpolation, and applied it successfully to C programs with more than 130,000 lines of code, which was not possible with approaches that build less parsimonious abstractions.
Summarizing procedures in concurrent programs
Authors: Qadeer Shaz , Rajamani Sriram K. , Rehof Jakob
Published: November 2005

The ability to summarize procedures is fundamental to building scalable interprocedural analyses. For sequential programs, procedure summarization is well-understood and used routinely in a variety of compiler optimizations and software defect-detection tools. However, the benefit of summarization is not available to multithreaded programs, for which a clear notion of summaries has so far remained unarticulated in the research literature.In this paper, we present an intuitive and novel notion of procedure summaries for multithreaded programs. We also present a model checking algorithm for these programs that uses procedure summarization as an essential component. Our algorithm can also be viewed as a precise interprocedural dataflow analysis for multithreaded programs. Our method for procedure summarization is based on the insight that in well-synchronized programs, any computation of a thread can be viewed as a sequence of transactions, each of which appears to execute atomically to other threads. We summarize within each transaction; the summary of a procedure comprises the summaries of all transactions within the procedure. We leverage the theory of reduction [17] to infer boundaries of these transactions.The procedure summaries computed by our algorithm allow reuse of analysis results across different call sites in a multithreaded program, a benefit that has hitherto been available only to sequential programs. Although our algorithm is not guaranteed to terminate on multithreaded programs that use recursion (reachability analysis for multithreaded programs with recursive procedures is undecidable [18]), there is a large class of programs for which our algorithm does terminate. We give a formal characterization of this class, which includes programs that use shared variables, synchronization, and recursion.
Atomizer
Authors: Flanagan Cormac , Freund Stephen N
Published: November 2005

Ensuring the correctness of multithreaded programs is difficult, due to the potential for unexpected interactions between concurrent threads. Much previous work has focused on detecting race conditions, but the absence of race conditions does not by itself prevent undesired thread interactions. We focus on the more fundamental non-interference property of
atomicity
; a method is atomic if its execution is not affected by and does not interfere with concurrently-executing threads. Atomic methods can be understood according to their sequential semantics, which significantly simplifies (formal and informal) correctness arguments.This paper presents a dynamic analysis for detecting atomicity violations. This analysis combines ideas from both Lipton's theory of reduction and earlier dynamic race detectors. Experience with a prototype checker for multithreaded Java code demonstrates that this approach is effective for detecting errors due to unintended interactions between threads. In particular, our atomicity checker detects errors that would be missed by standard race detectors, and it produces fewer false alarms on benign races that do not cause atomicity violations. Our experimental results also indicate that the majority of methods in our benchmarks are atomic, supporting our hypothesis that atomicity is a standard methodology in multithreaded programming.
Separation and information hiding
Authors: O'Hearn Peter W. , Yang Hongseok , Reynolds John C.
Published: November 2005

We investigate proof rules for information hiding, using the recent formalism of separation logic. In essence, we use the separating conjunction to partition the internal resources of a module from those accessed by the module's clients. The use of a logical connective gives rise to a form of dynamic partitioning, where we track the transfer of ownership of portions of heap storage between program components. It also enables us to enforce separation in the presence of mutable data structures with embedded addresses that may be aliased.
Tridirectional typechecking
Authors: Dunfield Jana , Pfenning Frank
Published: November 2005

In prior work we introduced a pure type assignment system that encompasses a rich set of property types, including intersections, unions, and universally and existentially quantified dependent types. This system was shown sound with respect to a call-by-value operational semantics with effects, yet is inherently undecidable.In this paper we provide a decidable formulation for this system based on bidirectional checking, combining type synthesis and analysis following logical principles. The presence of unions and existential quantification requires the additional ability to visit subterms in evaluation position before the context in which they occur, leading to a
tridirectional
type system. While soundness with respect to the type assignment system is immediate, completeness requires the novel concept of
contextual type annotations
, introducing a notion from the study of principal typings into the source program.
Principal typings for Java-like languages
Authors: Ancona Davide , Zucca Elena
Published: November 2005

The contribution of the paper is twofold. First, we define a general notion of type system equipped with an entailment relation between type environments; this generalisation serves as a pattern for instantiating type systems able to support separate compilation and inter-checking of Java-like languages, and allows a formal definition of soundess and completeness of inter-checking w.r.t. global compilation. These properties are important in practice since they allow selective recompilation. In particular, we show that they are guaranteed when the type system has principal typings and provides sound and complete entailment relation between type environments.The second contribution is more specific, and is an instantiation of the notion of type system previously defined for Featherweight Java with method overloading and field hiding. The aim is to show that it is possible to define type systems for Java-like languages, which, in contrast to those used by standard compilers, have principal typings, hence can be used as a basis for selective recompilation.
Non-linear loop invariant generation using Gröbner bases
Authors: Sankaranarayanan Sriram , Sipma Henny B. , Manna Zohar
Published: November 2005

We present a new technique for the generation of non-linear (algebraic) invariants of a program. Our technique uses the theory of ideals over polynomial rings to reduce the non-linear invariant generation problem to a numerical constraint solving problem. So far, the literature on invariant generation has been focussed on the construction of linear invariants for linear programs. Consequently, there has been little progress toward non-linear invariant generation. In this paper, we demonstrate a technique that encodes the conditions for a given template assertion being an invariant into a set of constraints, such that all the solutions to these constraints correspond to non-linear (algebraic) loop invariants of the program. We discuss some trade-offs between the completeness of the technique and the tractability of the constraint-solving problem generated. The application of the technique is demonstrated on a few examples.
Operation expressions in MARY
Authors: Rain Mark
Published: November 2005

Conventional languages are serial from statement to statement unless broken by explicit parenthesization such as BEGIN blocks or their equivalent in other languages. However, they are not serial within statements, but possess a complex priority scheme which seems to have little justification except historical notation in a few branches of mathematics. By making the elaboration sequence consistant in all contexts, MARY has succeeded in introducing several powerful new constructions in an orthagonal manner, while retaining clarity and ease of notation. This paper discusses one construction, the operation expression, in which program portions are evaluated to yield an operation to be applied to constant operands, instead of yielding an operand to be manipulated by constant operators.
Estimating the execution speed of an Algol program
Authors: Wichmann B. A.
Published: November 2005

This report gives details of a simple method of estimating the speed of an ALGOL program. It can be used as a programming aid in the construction of officient algorithms.
The EXEC 8 implementation of LIST PROCESSOR-N
Authors: Lambird Robert J. , Cornish Lawrence E.
Published: November 2005

This paper describes the Exec 8 implementation of List Processor-N, a set of list processing subprograms which provide the Fortran programmer with the ability to dynamically allocate arbitrarily complicated data structures.
Flowcharting loops without cycles
Authors: Weiderman N. H. , Rawson B. M.
Published: November 2005

In spite of recent progress in software engineering, many programmers continue to use flowcharting techniques which hamper rather than enhance their ability to create structured programs. This paper describes some of the problems of representing loops with existing techniques and suggests an alternative which solves these problems. The ideas presented here are meant to deal with some of the same issues which were raised by Nassi and Schneiderman [1] and Hopson and Dill [2] in a manner that is a natural out-growth from existing techniques.
Exception handling design issues
Authors: Goodenough John B.
Published: November 2005

Exception handling design issues are reflected in discussions by Zahn [1] Parnas [2], Hill [3], Elson [4], Organick [5], and myself [6, 7]. The purpose of this paper is to summarize these issues. This summary can be used to evaluate the strengths and weaknesses of proposed or existing exception handling language features and as a guide in designing new features.
The specification of program flow in Madcap 6
Authors: Morris James B. , Wells Mark B.
Published: November 2005

The control structures of the Madcap language have evolved to a point where today those of Madcap 6 have obviated programmer defined labels and go-to statements. The benefits of the removal of these concepts are discussed in detail. Madcap has a powerful class of data structures, including sets, sequences, and expressions, along with a full array of operators for manipulating these structures. These operators include important facilities for forming sets and for forming and concatenating sequences, based on very general iterative expressions. Procedures in Madcap are expressions whose evaluation is deferred; characteristics of this approach are discussed. Also described is a notation which facilitates backtrack programming.
A case against the GOTO
Authors: Wulf William A.
Published: November 2005

It has been proposed, by E. W. Dijkstra and others, that the goto statement in programming langauge is a principal culprit in programs which are difficult to understand, modify, and debug. More correctly, the argument is that it is possible to use the goto to synthesize program structures with these undesirable properties. Not all uses of the goto are to be considered harmful; however, it is further argued that the "good" uses of the goto fall into one of a small number of specific cases which may be handled by specific language constructs. This paper summarizes the arguments in favor of eliminating the goto statement and some of the theoretical and practical implications of the proposal.
The importance of implementation models in ALGOL 68
Authors: Berry Daniel M.
Published: November 2005

The need for implementation models in understanding languages, Algol 68 in particular, is stressed. The model is used to demonstrate the new concept of necessary environment of a procedure.
Towards a dynamic (FORTRAN) programming system
Authors: Archibald Julius A.
Published: November 2005

A major deficiency of programming languages, when compared to natural languages, is the inability of programming languages to adapt to improved means of communicating thoughts. A means of alleviating this difficulty in a FORTRAN environment, is presented.
BUILD
Authors: Bennett Richard K.
Published: November 2005

The traditional approach to computer language design has been to design one language at a time. This approach has led to languages which are syntactally complex and incompatible with one another. The proposed approach develops a language base, utilizing primitive language forms, upon which new languages may be built for all purposes. The resulting languages may possess diverse vocabulary and characteristics, but they are unified by the grammar of the language base upon which they are built, and they can be translated by one general processor. These languages can possess all the functions and facilities of today's languages and they can be readily extended to accommodate new requirements as they arise. A partial implementation of a general processor for this approach has been completed and is described.
Preprocessing of typed two-dimensional mathematical expressions
Authors: Wells Mark B.
Published: November 2005

An algorithm is discussed which translates two-dimensional mathematical expressions such as subscripting and displayed division, that have been prepared using a keyboard input device, into a string form suitable for input to a classical compiler. The algorithm allows reasonably general forms, yet is sufficiently simple to be practically applicable today. It may be used as a preprocessor to an existing compiler in order to improve the readability of an existing language.
A note on loop "optimization"
Authors: Feign David
Published: November 2005

The well-known execution-time reduction by moving invariant code out of a loop can be applied to an unconditional jump. Yet, this simple "optimization" is overlooked by most programmers and compiler designers. This paper reveals the overlooked unconditional jump and shows how moving it can not only reduce execution time, but can standardize and simplify the prototype loop.
ATOL
Authors: Axford T. H. , Burkhardt Diana , Dodd W. P. , Laflin Susan , Parkyn D. G. , Ramsay P.
Published: November 2005

The use of complex data structures in most common languages is often unnecessarily confusing to all but the most experienced programmers. ATOL has been designed to include a variety of data structures in a way that is both simple to understand and easy to handle, yet sufficiently general and powerful for a wide range of applications. The syntax of the language is quite simple and suitable for interactive program development at on-line terminals, rather like Basic.The primary data type of the language is a character string or text. Three classes of data structures may be constructed: records, files and sequences. For each of these, the components may be either texts or other structures in any of the three classes. Records may be defined recursively to generate lists or trees of variable size. Arrays are not present in the language, their place being taken by files which are structures containing variable numbers of components selected by text keys. Data from a very wide range of applications may thus be easily and conveniently represented.The method used to denote the components of a structure in a program is significantly simpler than that used in languages like Algol 68 and Pascal. In addition, the need to use pointers explicitly has been kept to a minimum, thus reducing another source of confusion among inexperienced programmers. In general the language has been designed for the beginning programmer whose interests are in non-numerical applications such as occur in the arts and humanities and many areas of commercial data processing.
Value receiving procedures
Authors: Mayer Alastair J. W.
Published: November 2005

The concept of value receiving procedures (functions which may act as the target of an assignment statement) is described and their utility discussed. The new keyword
receive
is suggested as an Ada extension. Extensions are also suggested for Pascal and PL/I.
The case against Pascal as a teaching tool
Authors: Levy Eric B.
Published: November 2005

As long as Pascal was merely a vehicle for demonstrating new concepts in programming languages, its utility was unquestioned. However, as Pascal becomes more widely taught in our universities the flaws in this popular language are beginning to produce a new generation of unmaintainable programs. The overuse of global variables dictated by the existence of nested scope is compared to the undisciplined use of the goto statement.
The memory usage of a LISP system
Authors: Olsson Olle
Published: November 2005

In this paper we will describe the memory management of a LISP interpreter, implemented in FORTRAN. The memory is used to store both LISP programs and LISP data structures. The dynamic use of this memory was examined during the execution of a large LISP program. The usage of this memory seen as a paged memory was analysed in terms of the Belady Life-Time Function. The results of this analysis is presented.
The programmer as navigator
Authors: Yuen C. K.
Published: November 2005

This paper takes a new view of the familiar title. It is argued that a computer program may be viewed as a map, and the programmer as a cargo-laden vessel navigating the routes. Two programming case studies are presented to show that, even where the map itself is well structured, hazardous journeys may result from the overloading of the vessel with directional cargo.
Programming language issues for the 1980's
Authors: Rowe Lawrence A. , Deutsch Peter , Feldman Stu , Lampson Butler , Liskov Barbara , Winograd Terry
Published: November 2005

At the SIGPLAN '83 conference, a panel discussion was held to discuss what the important programming language issues might be in the 1980's. This paper is an edited transcript of the discussion.I want to thank John White, General Chairman for the conference, who suggested that we have the panel and Richard Probst and Tim Learmont from U.C. Berkeley who recorded and transcribed the discussion. In the transcript below we have identified the speakers where possible. We apologize to those members of the audience whose comments are included below but who are not identified because we did not know their name.
Measurements of program similarity in identical task environments
Authors: Berghel H. L. , Sallach D. L.
Published: November 2005

This paper summarizes the results of a study which compared the efficiency of two methods of measuring program similarity in the context of novice programmers trying to reach identical objectives. Both methods look for similarity by comparing 'program profiles'. Such profiles are created by feature extraction routines which map each program onto a tuple <f
1
, f
2
,..., f
n
> where each f
i
is a count of an occurrence of a particular feature. A comparison routine is then invoked which detects similarities between tuples. The results showed that in this environment the comparison routine based on the Halstead metric failed to perform as well as a conceptually simpler alternative.
Multilevel files for software development
Authors: Hammons Charles , Dobbs Paul
Published: November 2005

A proposal is put forth for the use of multilevel files in software development. A set of tools which take advantage of the file sturcture is proposed.
A case for teaching multi-exit loops to beginning programmers
Authors: Buhr P. A.
Published: November 2005

While programming using the WHILE and REPEAT constructs, as in Pascal, is well established and taught regularly, programming using a LOOP construct with multiple exits is not. I feel that this much more general construct is a more useful programming construct and that it should be taught in introductory programming courses.
Software conversion
Authors: Heyman Jerrold
Published: November 2005

Writing transportable code is always desireable. Using extensions and enhancements implemented by the manufacturer does not help portability, nor does the use of specific system calls unique to that particular environment.The goal of this article is to show the converse implementation described by Herbert Mayer[1]. The transportation problems are somewhat similar but are also caused by differing implementations of the language --- FORTRAN 77.The two versions described are PRIME FORTRAN 77 (the host language running on a PRIME 750) and Microsoft MS-FORTRAN 77 version 3.1 (and later version 3.2) for the target machine, IBM PC.
A CAI implementation of Pascal
Authors: Tomek Ivan , Muldner Tomasz
Published: November 2005

PMS is a system designed to automate many of the tasks of the teacher of Pascal. It divides the language into minilanguages, each implemented as a combination of a syntax-driven program editor and a special purpose interpreter. The main features provided by the interpreter are:- simultaneous display of the source program, contents of memory, i/o, and additional concept-dependent information- step by step execution with highlightning of the source and simultaneous updating of "memory".PMS implements most of standard Pascal plus a few common extensions. Its implementation of strings is rather uncommon and 'clean'.
A note on English for decision tables considered harmful and the nested IF-THEN-ELSE
Authors: Vanthienen J.
Published: November 2005

In SIGPLAN NOTICES of July 1982 (Vol. 17, no. 7, p. 88), Michael Lesk of Bell Laboratories showed a nice example of a complex English text which appeared in the New York Times for Wednesday, Dec. 16, 1981, under the heading "Playoff Possibilities" and credited to Associated Press. It was stated that in most programming languages the triply nested conditional would be neither shorter nor easier to understand and a (decision) table was given representing the problem logic.In this note we try to show that a decision table software tool offers a powerful and understandable solution to this kind of problems and to the construction and representation difficulties with complex nested conditionals.
A further note on looping in Prolog
Authors: Covington Michael A.
Published: November 2005

In an earlier paper (Covington 1984) I proposed that looping in Prolog should be prevented by blocking all derivations in which the current goal matches a higher goal. This is too strong a constraint; it causes exhaustive searches to be incomplete. A better approach is to block all derivations in which the current goal matches a higher goal and is about to be evaluted using the same rule as was used to evaluate the higher goal. This is sufficient to block looping, and produces otherwise correct behavior, in all of the cases mentioned in the earlier paper.
A programming solution to certain problems with loops in Prolog
Authors: Nute Donald
Published: November 2005

Representing transitive relations in the obvious way in Prolog results in unwanted loops. A programming solution to this problem is provided and limitations and possible extension of this solution to other looping problems is discussed.
The towers of Hanoi
Authors: Eggers Bleicke
Published: November 2005

Another nonrecursive algorithm for The towers of Hanoi Problem is presented. It serves to compute the disk configuration from a given move number and the disk to be moved together with its current peg and target. The procedure gives rise to detect faults in erroneous computations.
PS-algol
Authors: Atkinson Malcolm , Chisholm Ken , Cockshott Paul
Published: November 2005

PS-algol is a dialect of algol for the programming of problems that would normally require a database management system. It supports a persistent heap, and an associative store; it has embedded within the language features to support tasks normally carried out by filing systems or database management systems.
Data flow analysis for Cobol
Authors: Kao H. , Chen T. Y.
Published: November 2005

This paper proposes new definitions of actions, states and state-transition diagrams for usage in the dynamic data flow analysis of Cobol programs.
Register allocation and spilling via graph coloring
Authors: Chaitin Gregory
Published: November 2005

In a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to the number of available machine registers, it must add code to spill and reload registers to and from storage. Previously the compiler produced spill code whose quality sometimes left much to be desired, and the ad hoc techniques used took considerable amounts of compile time. We have now discovered how to extend the graph coloring approach so that it naturally solves the spilling problem. Spill decisions are now made on the basis of the register conflict graph and cost estimates of the value of keeping the result of a computation in a register rather than in storage. This new approach produces better object code and takes much less compile time.
Efficient instruction scheduling for a pipelined architecture
Authors: Muchnick Steven S. , Gibbons Phillip B.
Published: November 2005

As part of an effort to develop an optimizing compiler for a pipelined architecture, a code reorganization algorithm has been developed that significantly reduces the number of runtime pipeline interlocks. In a pass after code generation, the algorithm uses a dag representation to heuristically schedule the instructions in each basic block.Previous algorithms for reducing pipeline interlocks have had worst-case runtimes of at least
O
(
n
4
). By using a dag representation which prevents scheduling deadlocks and a selection method that requires no lookahead, the resulting algorithm reorganizes instructions almost as effectively in practice, while having an
O
(
n
2
) worst-case runtime.
Software pipelining
Authors: Lam Monica S.
Published: November 2005

The basic idea behind software pipelining was first developed by Patel and Davidson for scheduling hardware pipe-lines. As instruction-level parallelism made its way into general-purpose computing, it became necessary to automate scheduling. How and whether instructions can be scheduled statically have major ramifications on the design of computer architectures. Rau and Glaeser were the first to use software pipelining in a compiler for a machine with specialized hardware designed to support software pipelining. In the meantime, trace scheduling was touted to be the scheduling technique of choice for VLIW (Very Long Instruction Word) machines. The most important contribution from this paper is to show that software pipelining is effective on VLIW machines without complicated hardware support. Our understanding of software pipelining subsequently deepened with the work of many others. And today, software pipelining is used in all advanced compilers for machines with instruction-level parallelism, none of which, except the Intel Itanium, relies on any specialized support for software pipelining.This paper shows that software pipelining is an effective and viable scheduling technique for VLIW processors. In software pipelining, iterations of a loop in the source program are continuously initiated at constant intervals, before the preceding iterations complete. The advantage of software pipelining is that optimal performance can be achieved with compact object code.This paper extends previous results of software pipelining in two ways: First, this paper shows that by using an improved algorithm, near-optimal performance can be obtained without specialized hardware. Second, we propose a
hierarchical reduction
scheme whereby entire control constructs are reduced to an object similar to an operation in a basic block. With this scheme, all innermost loops, including those containing conditional statements, can be software pipelined. It also diminishes the start-up cost of loops with small number of iterations. Hierarchical reduction complements the software pipelining technique, permitting a consistent performance improvement be obtained.The techniques proposed have been validated by an implementation of a compiler for Warp, a systolic array consisting of 10 VLIW processors. This compiler has been used for developing a large number of applications in the areas of image, signal and scientific processing.
Improving register allocation for subscripted variables
Authors: Callahan David , Carr Steve , Kennedy Ken
Published: November 2005

Most conventional compilers fail to allocate array elements to registers because standard data-flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating-point registers, which are most often used as temporary repositories for subscripted variables.In this paper, we present a source-to-source transformation, called
scalar replacement
, that finds opportunities for reuse of subscripted variables and replaces the references involved by references to temporary scalar variables. The objective is to increase the likelihood that these elements will be assigned to registers by the coloring-based register allocators found in most compilers. In addition, we present transformations to improve the overall effectiveness of scalar replacement and show how these transformations can be applied in a variety of loop nest types. Finally, we present experimental results showing that these techniques are extremely effective---capable of achieving integer factor speedups over code generated by good optimizing compilers of conventional design.
Profile guided code positioning
Authors: Pettis Karl , Hansen Robert C. , Davidson Jack W.
Published: November 2005

This paper presents the results of our investigation of code positioning techniques using execution profile data as input into the compilation process. The primary objective of the positioning is to reduce the overhead of the instruction memory hierarchy.After initial investigation in the literature, we decided to implement two prototypes for the Hewlett-Packard Precision Architecture (PA-RISC). The first, built on top of the linker, positions code based on whole procedures. This prototype has the ability to move procedures into an order that is determined by a "closest is best" strategy.The second prototype, built on top of an existing optimizer package, positions code based on basic blocks within procedures. Groups of basic blocks that would be better as straight-line sequences are identified as
chains.
These chains are then ordered according to branch heuristics. Code that is never executed during the data collection runs can be physically separated from the primary code of a procedure by a technique we devised called
procedure splitting.
The algorithms we implemented are described through examples in this paper. The performance improvements from our work are also summarized in various tables and charts.
Improving data-flow analysis with path profiles
Authors: Ammons Glenn , Larus James R.
Published: November 2005

Data-flow analysis computes its solutions over the paths in a control-flow graph. These paths---whether feasible or infeasible, heavily or rarely executed---contribute equally to a solution. However, programs execute only a small fraction of their potential paths and, moreover, programs' execution time and cost is concentrated in a far smaller subset of
hot paths.
This paper describes a new approach to analyzing and optimizing programs, which improves the precision of data flow analysis along hot paths. Our technique identifies and duplicates hot paths, creating a
hot path graph
in which these paths are isolated. After flow analysis, the graph is reduced to eliminate unnecessary duplicates of unprofitable paths. In experiments on SPEC95 benchmarks, path qualification identified 2--112 times more non-local constants (weighted dynamically) than the Wegman-Zadek conditional constant algorithm, which translated into 1--7% more dynamic instructions with constant results.
Modeling concurrency in parallel debugging
Authors: Hseush W. , Kaiser G. E.
Published: November 2005

We propose a debugging language,
Data Path Expressions
(DPEs), for modeling the behavior of parallel programs. The debugging paradigm is for the programmer to describe the expected program behavior and for the debugger to compare the actual program behavior during execution to detect program errors. We classify DPEs into five subclasses according to syntactic criteria, and characterize their semantics in terms of a hierarchy of extended Petri Net models. The characterization demonstrates the power of DPEs for modeling parallelism. We present
predecessor automata
as a mechanism for implementing the third subclass of DPEs, which expresses bounded parallelism. Predecessor automata extend finite state automata to provide efficient event recognizers for parallel debugging. We briefly describe the application of DPEs to race conditions, deadlock and starvation.
Programming techniques for efficiently exploiting parallelism in logic programming languages
Authors: Tick E. , Ichiyoshi N.
Published: November 2005

Granularity collecting (e.g., in OR-parallel Prolog) and removal of synchronization points (e.g., in AND-parallel committed-choice languages), are in general useful techniques for speeding up parallel logic programs. In this paper we explain these techniques with a unifying example: the Semigroup Problem, the calculation of the members of a semigroup given an initial set of generators. Performance measurements on a Sequent Symmetry multiprocessor are presented as evidence of the utility of the paradigms.
The evolution of HPC/VORX
Authors: Katseff H. P. , Gaglianello R. D. , Robinson B. S.
Published: November 2005

HPC/VORX is a computing system that provides closely coupled computing between large numbers of processors. It also supports the connection of many host workstations which may be geographically distributed within the area of a large building and allows a single applications to span many processors and many workstations. We relate some of the lessons that were learned while building and using HPC/VORX and in the transition to HPC/VORX from a smaller, less capable system. The problems that we encountered included difficulties in scaling resource managers and human interfaces to large numbers of processors, the design of communications primitives and protocols, and the implementation of programming abstractions.
Continuations and concurrency
Authors: Hieb R. , Dybvig R. Kent
Published: November 2005

Continuations have proven to be useful for implementing a variety of control structures, including exception handling facilities and breadth-first searching algorithms. However, traditional continuations are not useful in the presence of concurrency, because the notion of the rest of the computation represented by a continuation does not in general make sense. This paper presents a new type of continuation, called a
process continuation
, that may be used to control tree-structured concurrency. Just as a traditional continuation represents the rest of a computation from a given point in the computation, a process continuation represents the rest of a
subcomputation
, or
process
, from a given point in the
subcomputation
. Process continuations allow nonlocal exits to arbitrary points in the process tree and allow the capture of a subtree of a computation as a composable continuation for later use. Even in the absence of multiple processes, the precise control achievable with process continuations makes them more useful than traditional continuations.
An approach to ordering optimizing transformations
Authors: Whitfield D. , Soffa M. L.
Published: November 2005

As an approach to deriving an application order of optimizing transformations, a framework is developed for examining the interactions of the transformations. The framework is based on an axiomatic specification technique and includes both pre-conditions and post conditions that must exist before and after applying optimizations. For a selected set of optimizations, the framework is used to determine those interactions among the optimizations that can create conditions and those that can destroy conditions for applying other optimizations. From these interactions, an application order is derived to obtain the potential benefits of the optimizations that can be applied to a program. In some cases, the ordering of a pair of optimizations is unambiguous in that one optimization can either create or destroy the conditions for the other. In the few cases where there is a cyclic interaction, the ordering is resolved based on the perceived importance of the two optimizations.
The effectiveness of task-level parallelism for high-level vision
Authors: Harvey W. , Kalp D. , Tambe M. , McKeown D. , Newell A.
Published: November 2005

Large production systems (rule-based systems) continue to suffer from extremely slow execution which limits their utility in practical applications as well as in research settings. Most investigations in speeding up these systems have focused on match (or knowledge-search) parallelism. Although good speed-ups have been achieved in this process, these investigations have revealed the limitations on the total speed-up available from this source. This limited speed-up is insufficient to alleviate the problem of slow execution in large-scale production system implementations. Such large-scale systems are expected to increase as researchers develop increasingly more competent production systems.

In this paper, we focus on task-level parallelism, which is obtained by a high-level decomposition of the production system. Speed-ups obtained from task-level parallelism will multiply with the speed-ups obtained from match parallelism. The vehicle for our investigation of task-level parallelism is SPAM, a high-level vision system, implemented as a production system. SPAM is a mature research system with a typical run requiring between 50,000 to 400,000 production firings and an execution time of the order of 10 to 100 cpu hours.

We report very encouraging speed-ups from task-level parallelism in SPAM — our parallel implementation shows near linear speed-ups of over 12 fold using 14 processors and points the way to substantial (50-100 fold) speed-ups from task-level parallelism. We present a characterization of task-level parallelism in production systems and describe our methodology for selecting and applying a particular approach to parallelize SPAM. Additionally, we report the speed-ups obtained from the use of
shared virtual memory
(network shared memory) in this implementation. Overall, task-level parallelism has not received much attention in the literature. Our experience illustrates that it is potentially a very important tool for speeding up large-scale production systems
1
.
Munin: distributed shared memory based on type-specific memory coherence
Authors: Bennett J. K. , Carter J. B. , Zwaenepoel W.
Published: November 2005

We are developing Munin, a system that allows programs written for shared memory multiprocessors to be executed efficiently on distributed memory machines. Munin attempts to overcome the architectural limitations of shared memory machines, while maintaining their advantages in terms of ease of programming. Our system is unique in its use of loosely coherent memory, based on the partial order specified by a shared memory parallel program, and in its use of type-specific memory coherence. Instead of a single memory coherence mechanism for all shared data objects, Munin employs several different mechanisms, each appropriate for a different class of shared data object. These type-specific mechanisms are part of a runtime system that accepts hints from the user or the compiler to determine the coherence mechanism to be used for each object. This paper focuses on the design and use of Munin's memory coherence mechanisms, and compares our approach to previous work in this area.
Concurrent aggregates (CA)
Authors: Chien A. A. , Dally W. J.
Published: November 2005

To program massively concurrent MIMD machines, programmers need tools for managing complexity. One important tool that has been used in the sequential programming world is hierarchies of abstractions. Unfortunately, most concurrent object-oriented languages construct hierarchical abstractions from objects that serialize — serializing the abstractions. In machines with tens of thousands of processors, unnecessary serialization of this sort can cause significant loss of concurrency.

Concurrent Aggregates (CA) is an object-oriented language that allows programmers to build unserialized hierarchies of abstractions by using aggregates. An aggregate in CA is a homogeneous collection of objects (called representatives) that are grouped together and may be referenced by a single aggregate name. Aggregates are integrated into the object model, allowing them to be used wherever an object could be used. Concurrent Aggregates also incorporates several innovative language features that facilitate programming with aggregates. Intra-aggregate addressing aids cooperation between parts of an aggregate. Delegation allows programmers to compose an concurrent aggregate behavior from a number of objects or aggregates. Messages in CA are first class objects that can be used to create message handling abstractions (they handle messages as data). Such abstractions facilitate concurrent operations on aggregates. Continuations are also first class objects. In addition, programmers can construct continuations and use them just like system continuations. User constructed continuations can implement synchronization structures such as a barrier synchronization.