waashk/dblp huggingface dataset:
efficient incremental run-time specialization for free. availability of data in a program determines computation stages. incremental partial evaluation exploit these stages for optimization: it allows further specialization to be performed as data become available at later stages. the fundamental advantage of incremental specialization is to factorize the specialization process. as a result, specializing a program at a given stage costs considerably less than specializing it once all the data are available.we present a realistic and flexible approach to achieve efficient incremental run-time specialization. rather than developing specific techniques, as previously proposed, we are able to re-use existing technology by iterating a specialization process. moreover, in doing so, we do not lose any specialization opportunities. this approach makes it possible to exploit nested quasi-invariants and to speed up the run-time specialization process.this approach has been implemented in tempo, a specializer for c programs that is publicly available. a preliminary experiment confirm that incremental that incremental specialization can greatly speed up the specialization process.
asynchronous exceptions in haskell. asynchronous exceptions, such as timeouts are important for robust, modular programs, but are extremely difficult to program with &mdash; so much so that most programming languages either heavily restrict them or ban them altogether. we extend our earlier work, in which we added synchronous exceptions to haskell, to support asynchronous exceptions too. our design introduces scoped combinators for blocking and unblocking asynchronous interrupts, along with a somewhat surprising semantics for operations that can suspend. uniquely, we also give a formal semantics for our system.
delinearization: an efficient way to break multiloop dependence equations. exact and efficient data dependence testing is a key to success of loop-parallelizing compiler for computationally intensive programs. a number of algorithms has been created to test array references contained in parameter loops for dependence but most of them are unable to answer the following question correctly: are references c(i1 + 10j1) and c(i2 + 5), 0 &le; i1, i2 &le; 4, 0 &le; j1,j2 &le; 9 independent? the technique introduced in this paper recognizes that i1, i2 and j1, j2 make different order contributions to the subscript index, and breaks dependence equation i1 + 10j1 = i2 + 10j2 + 5 into two equations i1 = i2 and 10j1 = 10j2 which then can be solved independently. since resulting equations contain less variables it is less expensive to solve them. we call this technique delinearization because it is reverse of the linearization much discussed in the literature. in the introduction we demonstrate that linearized references are used not infrequently in scientific fortran and c codes. then we present a theorem on which delinearization algorithm is based and the algorithm itself. the algorithm is fairly simple and inexpensive. as a byproduct it tests equations it produces for independence as exactly as it is done by gcd-test and banerjee inequalities combined. the algorithm has been implemented at moscow state university in a vectorizer named vic.
scalable lock-free dynamic memory allocation. dynamic memory allocators (malloc/free) rely on mutual exclusion locks for protecting the consistency of their shared data structures under multithreading. the use of locking has many disadvantages with respect to performance, availability, robustness, and programming flexibility. a lock-free memory allocator guarantees progress regardless of whether some threads are delayed or even killed and regardless of scheduling policies. this paper presents a completely lock-free memory allocator. it uses only widely-available operating system support and hardware atomic instructions. it offers guaranteed availability even under arbitrary thread termination and crash-failure, and it is immune to deadlock regardless of scheduling policies, and hence it can be used even in interrupt handlers and real-time applications without requiring special scheduler support. also, by leveraging some high-level structures from hoard, our allocator is highly scalable, limits space blowup to a constant factor, and is capable of avoiding false sharing. in addition, our allocator allows finer concurrency and much lower latency than hoard. we use powerpc shared memory multiprocessor systems to compare the performance of our allocator with the default aix 5.1 libc malloc, and two widely-used multithread allocators, hoard and ptmalloc. our allocator outperforms the other allocators in virtually all cases and often by substantial margins, under various levels of parallelism and allocation patterns. furthermore, our allocator also offers the lowest contention-free latency among the allocators by significant margins.
a mechanism for efficient debugging of parallel programs. this paper addresses the design and implementation of an integrated debugging system for parallel programs running on shared memory multi-processors (smmp). we describe the use of flowback analysis to provide information on causal relationships between events in a program's execution without re-executing the program for debugging. we introduce a mechanism called incremental tracing that, by using semantic analyses of the debugged program, makes the flowback analysis practical with only a small amount of trace generated during execution. we extend flowback analysis to apply to parallel programs and describe a method to detect race conditions in the interactions of the co-operating processes.
generators and the replicator control structures in the parallel environment of alloy. the need for searching a space of solutions appears often. many problems, such as iteration over a dynamically created domain, can be expressed most naturally using a generate-and-process style. serial programming languages typically support solutions of these problems by providing some form of generators or backtracking. a parallel programming language is more demanding since it needs to be able to express parallel generation and processing of elements. failure driven computation is no longer sufficient and neither is multiple-assignment to generated values. we describe the replicator control operator used in the high level parallel programming language alloy. the replicator control operator provides a new view of generators which deals with these problems.
the pointer assertion logic engine. we present a new framework for verifying partial specifications of programs in order to catch type and memory errors and check data structure invariants. our technique can verify a large class of data structures, namely all those that can be expressed as graph types. earlier versions were restricted to simple special cases such as lists or trees. even so, our current implementation is as fast as the previous specialized tools. programs are annotated with partial specifications expressed in pointer assertion logic, a new notation for expressing properties of the program store. we work in the logical tradition by encoding the programs and partial specifications as formulas in monadic second-order logic. validity of these formulas is checked by the mona tool, which also can provide explicit counterexamples to invalid formulas. to make verification decidable, the technique requires explicit loop and function call invariants. in return, the technique is highly modular: every statement of a given program is analyzed only once. the main target applications are safety-critical data-type algorithms, where the cost of annotating a program with invariants is justified by the value of being able to automatically verify complex properties of the program.
principled scavenging. proof-carrying code and typed assembly languages aim to minimize the trusted computing base by directly certifying the actual machine code. unfortunately, these systems cannot get rid of the dependency on a trusted garbage collector. indeed, constructing a provably type-safe garbage collector is one of the major open problems in the area of certifying compilation. building on an idea by wang and appel, we present a series of new techniques for writing type-safe stop-and-copy garbage collectors. we show how to use intensional type analysis to capture the contract between the mutator and the collector, and how the same method can be applied to support forwarding pointers and generations. unlike wang and appel (which requires whole-program analysis), our new framework directly supports higher-order funtions and is compatible with separate compilation; our collectors are written in provably type-safe languages with rigorous semantics and fully formalized soundness proofs.
managing stack frames in smalltalk. the smalltalk programming language allows contexts (stack frames) to be accessed and manipulated in very general ways. this sometimes requires that contexts be retained even after they have terminated executing, and that they be reclaimed other than by lifo stack discipline. the authoritative definition of smalltalk [goldberg and robson 83] uses reference counting garbage collection to manage contexts, an approach found to be inadequate in practice [krasner, et al. 83]. deutsch and schiffman have described a technique that uses an actual stack as much as possible [deutsch and schiffman 84]. here we offer a less complex technique that we expect will have lower total overhead and reclaim many frames sooner and more easily. we are implementing our technique as part of a state of the art smalltalk interpreter. the approach may apply to other languages that allow indefinite lifetimes for execution contexts, be they interpreted or compiled.
avoiding unconditional jumps by code replication. this study evaluates a global optimization technique that avoids unconditional jumps by replicating code. when implemented in the back-end of an optimizing compiler, this technique can be generalized to work on almost all instances of unconditional jumps, including those generated from conditional statements and unstructured loops. the replication method is based on the idea of finding a replacement for each unconditional jump which minimizes the growth in code size. this is achieved by choosing the shortest sequence of instructions as a replacement. measurements taken from a variety of programs showed that not only the number of executed instructions decreased, but also that the total cache work was reduced (except for small caches) despite increases in code size. pipelined and superscalar machines may also benefit from an increase in the average basic block size.
effective static race detection for java. we present a novel technique for static race detection in java programs, comprised of a series of stages that employ a combination of static analyses to successively reduce the pairs of memory accesses potentially involved in a race. we have implemented our technique and applied it to a suite of multi-threaded java programs. our experiments show that it is precise, scalable, and useful, reporting tens to hundreds of serious and previously unknown concurrency bugs in large, widely-used programs with few false alarms.
profile-based global live-range splitting. live-range splitting is a technique to split the live range of a given variable into multiple subranges, each of which can be assigned to a different register or spilled out to memory in order to improve results of coloring register allocation. previous techniques, such as aggressive live-range splitting, tend to produce extra spill code in the frequently executed (called hot) regions of the code, since they don't distinguish hot regions from others. we propose a new live-range splitting algorithm, which can reduce the amount of spill code in hot regions by coalescing the live ranges based on profile information after splitting the live ranges at every join and fork point in the control-flow graph. our experimental results have shown that our new algorithm improved the performance of specjvm98 by up to 33% over aggressive live-range splitting and 7% over the base coloring algorithm without any live-range splitting.
practical dynamic software updating for c. software updates typically require stopping and restarting an application, but many systems cannot afford to halt service, or would prefer not to. dynamic software updating (dsu) addresses this difficulty by permitting programs to be updated while they run. dsu is appealing compared to other approaches for on-line upgrades because it is quite general and requires no redundant hardware. the challenge is in making dsu practical: it should be flexible, and yet safe, efficient, and easy to use.in this paper, we present ginseng, a dsu implementation for c that aims to meet this challenge. we compile programs specially so that they can be dynamically patched, and generate most of a dynamic patch automatically. ginseng performs a series of analyses that when combined with some simple runtime support ensure that an update will not violate type-safety while guaranteeing that data is kept up-to-date. we have used ginseng to construct and dynamically apply patches to three substantial open-source server programs---very secure ftp daemon, openssh sshd daemon, and gnu zebra. in total, we dynamically patched each program with three years' worth of releases. though the programs changed substantially, the majority of updates were easy to generate. performance experiments show that all patches could be applied in less than 5 ms, and that the overhead on application throughput due to updating support ranged from 0 to at most 32%.
translation validation for an optimizing compiler. we describe a translation validation infrastructure for the gnu c compiler. during the compilation the infrastructure compares the intermediate form of the program before and after each compiler pass and verifies the preservation of semantics. we discuss a general framework that the optimizer can use to communicate to the validator what transformations were performed. our implementation however does not rely on help from the optimizer and it is quite successful by using instead a few heuristics to detect the transformations that take place. the main message of this paper is that a practical translation validation infrastructure, able to check the correctness of many of the transformations performed by a realistic compiler, can be implemented with about the effort typically required to implement one compiler pass. we demonstrate this in the context of the gnu c compiler for a number of its optimizations while compiling realistic programs such as the compiler itself or the linux kernel. we believe that the price of such an infrastructure is small considering the qualitative increase in the ability to isolate compilation errors during compiler testing and maintenance.
the design and implementation of a certifying compiler. this paper presents the design and implementation of a compiler that translates programs written in a type-safe subset of the c programming language into highly optimized dec alpha assembly language programs, and a certifier that automatically checks the type safety and memory safety of any assembly language program produced by the compiler. the result of the certifier is either a formal proof of type safety or a counterexample pointing to a potential violation of the type system by the target program. the ensemble of the compiler and the certifier is called a certifying compiler.several advantages of certifying compilation over previous approaches can be claimed. the notion of a certifying compiler is significantly easier to employ than a formal compiler verification, in part because it is generally easier to verify the correctness of the result of a computation than to prove the correctness of the computation itself. also, the approach can be applied even to highly optimizing compilers, as demonstrated by the fact that our compiler generates target code, for a range of realistic c programs, which is competitive with both the cc and gcc compilers with all optimizations enabled. the certifier also drastically improves the effectiveness of compiler testing because, for each test case, it statically signals compilation errors that might otherwise require many executions to detect. finally, this approach is a practical way to produce the safety proofs for a proof-carrying code system, and thus may be useful in a system for safe mobile code.
real-time replication garbage collection. we have implemented the first copying garbage collector that permits continuous unimpeded mutator access to the original objects during copying. the garbage collector incrementally replicates all accessible objects and uses a mutation log to bring the replicas up-to-date with changes made by the mutator. an experimental implementation demonstrates that the costs of using our algorithm are small and that bounded pause times of 50 milliseconds can be readily achieved.
optimal tracing and incremental reexecution for debugging long-running programs. debugging requires execution replay. locations of bugs are rarely known in advance, so an execution must be repeated over and over to track down bugs. a problem arises with repeated reexecution for long-running programs and programs that have complex interactions with their environment. replaying long-running programs from the start incurs too much delay. replaying programs that interact with their environment requires the difficult (and sometimes impossible) task of exactly reproducing this environment (such as the connections over a one-day period to an x server). we solve these problems by incremental checkpointing and replay. by periodically checkpointing parts of the execution''s state, it can be restarted from intermediate points, bounding the delay to replay any part of the execution and allowing parts of the execution to be skipped. we present adaptive tracing strategies that provide bounded-time incremental replay and that are nearly optimal. our techniques track reads and writes to memory using space-efficient two-level bitvectors. our implementation on a sparc 10 traces less than 15 kilobytes/sec for cpu-intensive programs and for interactive programs the slowdown is low enough that tracing can be left on all the time.
programming ad-hoc networks of mobile and resource-constrained devices. ad-hoc networks of mobile devices such as smart phones and pdas represent a new and exciting distributed system architecture. building distributed applications on such an architecture poses new design challenges in programming models, languages, compilers, and runtime systems. this paper discusses spatialviews, a high-level language designed for programming mobile devices connected through a wireless ad-hoc network. spatialviews allows specification of virtual networks with nodes providing desired services and residing in interesting spaces. these nodes are discovered dynamically with user-specified time constraints and quality of result (qor). the programming model supports "best-effort" semantics, i.e., different executions of the same program may result in "correct" answers of different quality. it is the responsibility of the compiler and runtime system to produce a high-quality answer for the particular network and resource conditions encountered during program execution. four applications, which exercise different features of the spatialviews language, are presented to demonstrate the expressiveness of the language and the efficiency of the compiler generated code. the applications are an application that collects and aggregates sensor data in network, an application that performs dynamic service installation, a mobile camera application that supports computation offloading for image understanding, and an augmented-reality (ar) pacman game. the efficiency of the compiler generated code is verified through simulation and physical measurements. the reported results show that spatialviews is an expressive and effective language for ad-hoc networks. in addition, compiler optimizations can significantly improve response times and energy consumption.
graph coloring register allocation for processors with multi-register operands. though graph coloring algorithms have been shown to work well when applied to register allocation problems, the technique has not been generalized for processor architectures in which some instructions refer to individual operands that are comprised of multiple registers. this paper presents a suitable generalization.
register allocation over the program dependence graph. this paper describes rap, a register allocator that allocates registers over the program dependence graph (pdg) representation of a program in a hierarchical manner. the pdg program representation has been used successfully for scalar optimizations, the detection and improvement of parallelism for vector machines, multiple processor machines, and machines that exhibit instruction level parallelism, as well as debugging, the integration of different versions of a program, and translation of imperative programs for data flow machines. by basing register allocation on the pdg, the register allocation phase may be more easily integrated and intertwined with other optimization analyses and transformations. in addition, the advantages of a hierarchical approach to global register allocation can be attained without constructing an additional structure used solely for register allocation. our experimental results have shown that on average, code allocated registers via rap executed 2.7% faster than code allocated registers via a standard global register allocator.
enhancement through extension: the extension interpreter. the ability to extend programs dynamically has clear advantages. however, providing efficient yet sufficiently flexible support for such capabilities system-wide presents significant challenges. we describe a design and implementation of an extension mechanism that depends heavily on interpretive techniques, including call arbitration, dynamic linking, and multilanguage extensions. we discuss these mechanisms in the context of our extension interpreter, which embodies our ideas and provides a framework for discussing the efficiency and generality of the implementation. our current implementation runs under bsd unix 4.2 and 4.3 on vaxes and sun workstations. extensions can be written in both c and in icon, demonstrating our ability to address problems both of compiled and interpreted languages.
auto-vectorization of interleaved data for simd. most implementations of the single instruction multiple data (simd) model available today require that data elements be packed in vector registers. operations on disjoint vector elements are not supported directly and require explicit data reorganization manipulations. computations on non-contiguous and especially interleaved data appear in important applications, which can greatly benefit from simd instructions once the data is reorganized properly. vectorizing such computations efficiently is therefore an ambitious challenge for both programmers and vectorizing compilers. we demonstrate an automatic compilation scheme that supports effective vectorization in the presence of interleaved data with constant strides that are powers of 2, facilitating data reorganization. we demonstrate how our vectorization scheme applies to dominant simd architectures, and present experimental results on a wide range of key kernels, showing speedups in execution time up to 3.7 for interleaving levels (stride) as high as 8.