waashk/dblp huggingface dataset:
debugging concurrent processes: a case study. we present a case study that illustrates a method of debugging concurrent processes in a parallel programming environment. it uses a new approach called speculative replay to reconstruct the behavior of a program from the histories of its individual processes. known time dependencies between events in different processes are used to divide the histories into dependence blocks. a graphical representation called a concurrency map displays possibilities for concurrency among processes. the replay technique preserves the known dependencies and compares the process histories generated during replay with those that were logged during the original program execution. if a process generates a replay history that does not match its original history, replay backs up. an alternative ordering of events is created and tested to see if it produces process histories that match the original histories. successively more controlled replay sequences are generated, by introducing additional dependencies. we describe ongoing work on tools that will control replay without reconstructing the entire space of possible event orderings. the case study presents a miniature example of shared-queue management that can be examined in detail. it demonstrates the replay technique and the construction and use of the concurrency map. using our techniques, we detect a failure to which a standard algorithm for shared-queue management is susceptible.
compile-time composition of run-time data and iteration reorderings. many important applications, such as those using sparse data structures, have memory reference patterns that are unknown at compile-time. prior work has developed run-time reorderings of data and computation that enhance locality in such applications.this paper presents a compile-time framework that allows the explicit composition of run-time data and iteration-reordering transformations. our framework builds on the iteration-reordering framework of kelly and pugh to represent the effects of a given composition. to motivate our extension, we show that new compositions of run-time reordering transformations can result in better performance on three benchmarks.we show how to express a number of run-time data and iteration-reordering transformations that focus on improving data locality. we also describe the space of possible run-time reordering transformations and how existing transformations fit within it. since sparse tiling techniques are included in our framework, they become more generally applicable, both to a larger class of applications, and in their composition with other reordering transformations. finally, within the presented framework data need be remapped only once at runtime for a given composition thus exhibiting one example of overhead reductions the framework can express.
a region-based compilation technique for a java just-in-time compiler. method inlining and data flow analysis are two major optimization components for effective program transformations, however they often suffer from the existence of rarely or never executed code contained in the target method. one major problem lies in the assumption that the compilation unit is partitioned at method boundaries. this paper describes the design and implementation of a region-based compilation technique in our dynamic compilation system, in which the compiled regions are selected as code portions without rarely executed code. the key part of this technique is the region selection, partial inlining, and region exit handling. for region selection, we employ both static heuristics and dynamic profiles to identify rare sections of code. the region selection process and method inlining decision are interwoven, so that method inlining exposes other targets for region selection, while the region selection in the inline target conserves the inlining budget, leading to more method inlining. thus the inlining process can be performed for parts of a method, not for the entire body of the method. when the program attempts to exit from a region boundary, we trigger recompilation and then rely on on-stack replacement to continue the execution from the corresponding entry point in the recompiled code. we have implemented these techniques in our java jit compiler, and conducted a comprehensive evaluation. the experimental results show that the approach of region-based compilation achieves approximately 5% performance improvement on average, while reducing the compilation overhead by 20 to 30%, in comparison to the traditional function-based compilation techniques.
the type inference and coercion facilities in the scratchpad ii interpreter. the scratchpad ii system is an abstract datatype programming language, a compiler for the language, a library of packages of polymorphic functions and parametrized abstract datatypes, and an interpreter that provides sophisticated type inference and coercion facilities. although originally designed for the implementation of symbolic mathematical algorithms, scratchpad ii is a general purpose programming language. this paper discusses aspects of the implementation of the interpreter and how it attempts to provide a user friendly and relatively weakly typed front end for the strongly typed programming language.
a study of dead data members in c++ applications. object-oriented applications may contain data members that can be removed from the application without affecting program behavior. such "dead" data members may occur due to unused functionality in class libraries, or due to the programmer losing track of member usage as the application changes over time. we present a simple and efficient algorithm for detecting dead data members in c++ applications. this algorithm has been implemented using a prototype version of the ibm visualage c++ compiler, and applied to a number of realistic benchmark programs ranging from 600 to 58,000 lines of code. for the non-trivial benchmarks, we found that up to 27.3% of the data members in the benchmarks are dead (average 12.5%), and that up to 11.6% of the object space of these applications may be occupied by dead data members at run-time (average 4.4%).
compiling dataflow analysis of logic programs. abstract interpretation is a technique extensively used for global dataflow analyses of logic programs. existing implementations of abstract interpretation are slow due to interpretive or transforming overhead and the inefficiency in manipulation of global information. since abstract interpretation mimics standard interpretation, it is a promising alternative to compile abstract interpretation into the framework of the wam (warren abstract machine) for better performance. in this paper, we show how this approach can be effectively implemented in a low-cost manner. to evaluate the possible benefits of this approach, a prototype dataflow analyzer has been implemented for inference of mode, type and variable aliasing information of logic programs. for a subset of benchmark programs in [15], it significantly improves the performance by a factor of over 150 on the average.
til: a type-directed optimizing compiler for ml. 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.
a unified framework for schedule and storage optimization. we present a unified mathematical framework for analyzing the tradeoffs between parallelism and storage allocation within a parallelizing compiler. using this framework, we show how to find a good storage mapping for a given schedule, a good schedule for a given storage mapping, and a good storage mapping that is valid for all legal schedules. we consider storage mappings that collapse one dimension of a multi-dimensional array, and programs that are in a single assignment form with a one-dimensional schedule. our technique combines affine scheduling techniques with occupancy vector analysis and incorporates general affine dependences across statements and loop nests. we formulate the constraints imposed by the data dependences and storage mappings as a set of linear inequalities, and apply numerical programming techniques to efficiently solve for the shortest occupancy vector. we consider our method to be a first step towards automating a procedure that finds the optimal tradeoff between parallelism and storage space.
quality and speed in linear-scan register allocation. a linear-scan algorithm directs the global allocation of register candidates to registers based on a simple linear sweep over the program being compiled. this approach to register allocation makes sense for systems, such as those for dynamic compilation, where compilation speed is important. in contrast, most commercial and research optimizing compilers rely on a graph-coloring approach to global register allocation. in this paper, we compare the performance of a linear-scan method against a modern graph-coloring method. we implement both register allocators within the machine suif extension of the stanford suif compiler system. experimental results show that linear scan is much faster than coloring on benchmarks with large numbers of register candidates. we also describe improvements to the linear-scan approach that do not change its linear character, but allow it to produce code of a quality near to that produced by graph coloring.
a framework for unrestricted whole-program optimization. procedures have long been the basic units of compilation in conventional optimization frameworks. however, procedures are typically formed to serve software engineering rather than optimization goals, arbitrarily constraining code transformations. techniques, such as aggressive inlining and interprocedural optimization, have been developed to alleviate this problem, but, due to code growth and compile time issues, these can be applied only sparingly.this paper introduces the procedure boundary elimination (pbe) compilation framework, which allows unrestricted whole-program optimization. pbe allows all intra-procedural optimizations and analyses to operate on arbitrary subgraphs of the program, regardless of the original procedure boundaries and without resorting to inlining. in order to control compilation time, pbe also introduces novel extensions of region formation and encapsulation. pbe enables targeted code specialization, which recovers the specialization benefits of inlining while keeping code growth in check. this paper shows that pbe attains better performance than inlining with half the code growth.
gum: a portable parallel implementation of haskell. gum is a portable, parallel implementation of the haskell functional language. despite sustained research interest in parallel functional programming, gum is one of the first such systems to be made publicly available.gum is message-based, and portability is facilitated by using the pvm communications harness that is available on many multi-processors. as a result, gum is available for both shared-memory (sun sparcserver multiprocessors) and distributed-memory (networks of workstations) architectures. the high message-latency of distributed machines is ameliorated by sending messages asynchronously, and by sending large packets of related data in each message.initial performance figures demonstrate absolute speedups relative to the best sequential compiler technology. to improve the performance of a parallel haskell program gum provides tools for monitoring and visualising the behaviour of threads and of processors during execution.
compiling programs for a linear systolic array. this paper describes an al compiler for the warp systolic array. al is a programming language in which the user programs a systolic array as if it were a sequential computer and relies on the compiler to generate parallel code. this paper introduces the notion of data relations in compiling programs for systolic arrays. unlike dependence relations among statements of a program, data relations define compatibility relations among data objects of a program. the al compiler uses data relations to compute data compatibility classes, determine data distribution, and distribute loop iterations. the al compiler can generate efficient parallel code almost identical to what the user would have written by hand. for example, the al compiler generates parallel code for the linpack lu decomposition (sgefa) and qr decomposition (sqrdc) routines with a nearly 8-fold speedup on the 10-cell warp array for matrices of size 180 &times; 180.
the liberty structural specification language: a high-level modeling language for component reuse. rapid exploration of the design space with simulation models is essential for quality hardware systems research and development. despite striking commonalities across hardware systems, designers routinely fail to achieve high levels of reuse across models constructed in existing general-purpose and domain-specific languages. this lack of reuse adversely impacts hardware system design by slowing the rate at which ideas are evaluated. this paper presents an examination of existing languages to reveal their fundamental limitations regarding reuse in hardware modeling. with this understanding, a solution is described in the context of the design and implementation of the liberty structural specification language (lss), the input language for a publicly available high-level digital-hardware modeling tool called the liberty simulation environment. lss is the first language to enable low-overhead reuse by simultaneously supporting static inference based on hardware structure and flexibility via parameterizable structure. through lss, this paper also introduces a new type inference algorithm and a new programming language technique, called use-based specialization, which, in a manner analogous to type inference, customizes reusable components by statically inferring structural properties that otherwise would have had to have been specified manually.
correctness-preserving derivation of concurrent garbage collection algorithms. constructing correct concurrent garbage collection algorithms is notoriously hard. numerous such algorithms have been proposed, implemented, and deployed - and yet the relationship among them in terms of speed and precision is poorly understood, and the validation of one algorithm does not carry over to others.as programs with low latency requirements written in garbagecollected languages become part of society's mission-critical infrastructure, it is imperative that we raise the level of confidence in the correctness of the underlying system, and that we understand the trade-offs inherent in our algorithmic choice.in this paper we present correctness-preserving transformations that can be applied to an initial abstract concurrent garbage collection algorithm which is simpler, more precise, and easier to prove correct than algorithms used in practice--but also more expensive and with less concurrency. we then show how both pre-existing and new algorithms can be synthesized from the abstract algorithm by a series of our transformations. we relate the algorithms formally using a new definition of precision, and informally with respect to overhead and concurrency.this provides many insights about the nature of concurrent collection, allows the direct synthesis of new and useful algorithms, reduces the burden of proof to a single simple algorithm, and lays the groundwork for the automated synthesis of correct concurrent collectors.
using node merging to enhance graph coloring. a chaitin-style register allocator often blocks during its simplification phase because no node in the interference graph has a degree that is sufficiently small. typically, this is handled by node-splitting, or by optimistically continuing---and hoping that a legal n-coloring will still be found. we observe that the merging of two nodes in a graph causes a reduction in the degree of any node that had been adjacent to both. we have enhanced chaitin's coloring algorithm so that it attempts node-merging during graph simplification; this often allows simplification to continue, while still guaranteeing a coloring for the graph. we have tested this algorithm using appel's database of register-coloring graphs, and have compared it with chaitin's algorithm. the merge-enhanced algorithm yields a better coloring about 8% of the time, and a worse coloring less than 0.1% of the time.
precise and efficient static array bound checking for large embedded c programs. in this paper we describe the design and implementation of a static array-bound checker for a family of embedded programs: the flight control software of recent mars missions. these codes are large (up to 280 kloc), pointer intensive, heavily multithreaded and written in an object-oriented style, which makes their analysis very challenging. we designed a tool called c global surveyor (cgs) that can analyze the largest code in a couple of hours with a precision of 80%. the scalability and precision of the analyzer are achieved by using an incremental framework in which a pointer analysis and a numerical analysis of array indices mutually refine each other. cgs has been designed so that it can distribute the analysis over several processors in a cluster of machines. to the best of our knowledge this is the first distributed implementation of static analysis algorithms. throughout the paper we will discuss the scalability setbacks that we encountered during the construction of the tool and their impact on the initial design decisions.
a framework for construction and evaluation of high-level specifications for program analysis techniques. abstract interpretation introduced the notion of formal specification of program analyses. denotational frameworks are convenient for reasoning about such specifications. however, implementation considerations make denotational specifications complex and hard to develop. we present a framework that facilitates the construction and understanding of denotational specifications for program analysis techniques. the framework is exemplified by specifications for program analysis techniques from the literature and from our own research. this approach allows program analysis techniques to be incorporated into automatically generated program synthesizers by including their specifications with the language definition.
incrementalized pointer and escape analysis. we present a new pointer and escape analysis. instead of analyzing the whole program, the algorithm incrementally analyzes only those parts of the program that may deliver useful results. an analysis policy monitors the analysis results to direct the incremental investment of analysis resources to those parts of the program that offer the highest expected optimization return. our experimental results show that almost all of the objects are allocated at a small number of allocation sites and that an incremental analysis of a small region of the program surrounding each site can deliver almost all of the benefit of a whole-program analysis. our analysis policy is usually able to deliver this benefit at a fraction of the whole-program analysis cost.
higher-order attribute grammars. a new kind of attribute grammars, called higher order attribute grammars, is defined. in higher order attribute grammars the structure tree can be expanded as a result of attribute computation. a structure tree may be stored in an attribute. the term higher order is used because of the analogy with higher order functions, where a function can be the result or parameter of another function. a relatively simple method, using oags, is described to derive an evaluation order on the defining attribute occurrences which comprises all possible direct and indirect attribute dependencies. as in oags, visit-sequences are computed from which an efficient algorithm for attribute evaluation can be derived.
incremental analysis of real programming languages. a major research goal for compilers and environments is the automatic derivation of tools from formal specifications. however, the formal model of the language is often inadequate; in particular, lr(k) grammars are unable to describe the natural syntax of many languages, such as c++ and fortran, which are inherently non-deterministic. designers of batch compilers work around such limitations by combining generated components with ad hoc techniques (for instance, performing partial type and scope analysis in tandem with parsing). unfortunately, the complexity of incremental systems precludes the use of batch solutions. the inability to generate incremental tools for important languages inhibits the widespread use of language-rich interactive environments.we address this problem by extending the language model itself, introducing a program representation based on parse dags that is suitable for both batch and incremental analysis. ambiguities unresolved by one stage are retained in this representation until further stages can complete the analysis, even if the reaolution depends on further actions by the user. representing ambiguity explicitly increases the number and variety of languages that can be analyzed incrementally using existing methods.to create this representation, we have developed an efficient incremental parser for general context-free grammars. our algorithm combines tomita's generalized lr parser with reuse of entire subtrees via state-matching. disambiguation can occur statically, during or after parsing, or during semantic analysis (using existing incremental techniques); program errors that preclude disambiguation retsin multiple interpretations indefinitely. our representation and analyses gain efficiency by exploiting the local nature of ambiguities: for the spec95 c programs, the explicit representation of ambiguity requires only 0.5% additional space and less than 1% additional time during reconstruction.