waashk/dblp huggingface dataset:
threads cannot be implemented as a library. in many environments, multi-threaded code is written in a language that was originally designed without thread support (e.g. c), to which a library of threading primitives was subsequently added. there appears to be a general understanding that this is not the right approach. we provide specific arguments that a pure library approach, in which the compiler is designed independently of threading issues, cannot guarantee correctness of the resulting code.we first review why the approach almost works, and then examine some of the surprising behavior it may entail. we further illustrate that there are very simple cases in which a pure library-based approach seems incapable of expressing an efficient parallel algorithm.our discussion takes place in the context of c with pthreads, since it is commonly used, reasonably well specified, and does not attempt to ensure type-safety, which would entail even stronger constraints. the issues we raise are not specific to that context.
dynamic program slicing. program slices are useful in debugging, testing, maintenance, and understanding of programs. the conventional notion of a program slice, the static slice, is the set of all statements that might affect the value of a given variable occurrence. in this paper, we investigate the concept of the dynamic slice consisting of all statements that actually affect the value of a variable occurrence for a given program input. the sensitivity of dynamic slicing to particular program inputs makes it more useful in program debugging and testing than static slicing. several approaches for computing dynamic slices are examined. the notion of a dynamic dependence graph and its use in computing dynamic slices is discussed. the dynamic dependence graph may be unbounded in length; therefore, we introduce the economical concept of a reduced dynamic dependence graph, which is proportional in size to the number of dynamic slices arising during the program execution.
constructive real interpretation of numerical programs. we explore the feasibility of providing exact real arithmetic for use in conventional numerical programs. we have built a prototype interpreter which replaces floating point operations with operations on constructive real numbers in the execution of conventional fortran programs. such a facility makes it unnecessary to concern oneself with issues of numerical stability in the solution of small problems. it also provides a useful tool for the development of larger numerical programs.we discuss the computability and algorithmic issues involved in the design of the interpreter, as well as some preliminary experiences and performance measurements.
interprocedural partial redundancy elimination and its application to distributed memory compilation. partial redundancy elimination (pre) is a general scheme for suppressing partial redundancies which encompasses traditional optimizations like loop invariant code motion and redundant code elimination. in this paper we address the problem of performing this optimization interprocedurally. we use interprocedural partial redundancy elimination for placement of communication and communication preprocessing statements while compiling for distributed memory parallel machines.
type inference in the presence of type abstraction. a number of recent programming language designs incorporate a type checking system based on the girard-reynolds polymorphic &lgr;-calculus. this allows the construction of general purpose, reusable software without sacrificing compile-time type checking. a major factor constraining the implementation of these languages is the difficulty of automatically inferring the lengthy type information that is otherwise required if full use is made of these languages. there is no known algorithm to solve any natural and fully general formulation of this &ldquo;type inference&rdquo; problem. one very reasonable formulation of the problem is known to be undecidable. here we define a restricted version of the type inference problem and present an efficient algorithm for its solution. we argue that the restriction is sufficiently weak to be unobtrusive in practice.
checking and inferring local non-aliasing. in prior work [15] we studied a language construct <tt>restrict</tt> that allows programmers to specify that certain pointers are not aliased to other pointers used within a lexical scope. among other applications, programming with these constructs helps program analysis tools locally recover strong updates, which can improve the tracking of state in flow-sensitive analyses. in this paper we continue the study of <tt>restrict</tt> and introduce the construct <tt>confine</tt>. we present a type and effect system for checking the correctness of these annotations, and we develop efficient constraint-based algorithms implementing these type checking systems. to make it easier to use <tt>restrict</tt> and <tt>confine</tt> in practice, we show how to automatically infer such annotations without programmer assistance. in experiments on locking in 589 linux device drivers, <tt>confine</tt> inference can automatically recover strong updates to eliminate 95% of the type errors resulting from weak updates.
space efficient conservative garbage collection. both type-accurate and conservative garbage collectors have gained in importance since the original paper was written. managing unnecessary retention by conservative collectors continues to be an important problem. there appear to be few reimplementations of the techniques we described, but significantly refined descendents of the original implementation are alive and well inside a large number of applications.there has been later work both on quantifying space retention by conservative collectors, and on theoretical bounds for such retention.we call a garbage collector conservative if it has only partial information about the location of pointers, and is thus forced to treat arbitrary bit patterns as though they might be pointers, in at least some cases. we show that some very inexpensive, but previously unused techniques can have dramatic impact on the effectiveness of conservative garbage collectors in reclaiming memory. our most significant observation is that static data that appears to point to the heap should not result in misidentified references to the heap. the garbage collector has enough information to allocate around such references. we also observe that programming style has a significant impact on the amount of spuriously retained storage, typically even if the collector is not terribly conservative. some fairly common c and c++ programming styles significantly decrease the effectiveness of any garbage collector. these observations suffice to explain some of the different assessments of conservative collection that have appeared in the literature.
better static memory management: improving region-based analysis of higher-order languages. static memory management replaces runtime garbage collection with compile-time annotations that make all memory allocation and deallocation explicit in a program. we improve upon the tofte/talpin region-based scheme for compile-time memory management[tt94]. in the tofte/talpin approach, all values, including closures, are stored in regions. region lifetimes coincide with lexical scope, thus forming a runtime stack of regions and eliminating the need for garbage collection. we relax the requirement that region lifetimes be lexical. rather, regions are allocated late and deallocated as early as possible by explicit memory operations. the placement of allocation and deallocation annotations is determined by solving a system of constraints that expresses all possible annotations. experiments show that our approach reduces memory requirements significantly, in some cases asymptotically.
optimal loop parallelization. parallelizing compilers promise to exploit the parallelism available in a given program, particularly parallelism that is too low-level or irregular to be expressed by hand in an algorithm. however, existing parallelization techniques do not handle loops in a satisfactory manner. fine-grain (instruction level) parallelization, or compaction, captures irregular parallelism inside a loop body but does not exploit parallelism across loop iterations. coarser methods, such as doacross [9], sacrifice irregular forms of parallelism in favor of pipelining iterations (software pipelining). both of these approaches often yield suboptimal speedups even under the best conditions-when resources are plentiful and processors are synchronous. in this paper we present a new technique bridging the gap between fine-and coarse-grain loop parallelization, allowing the exploitation of parallelism inside and across loop iterations. furthermore, we show that, given a loop and a set of dependencies between its statements, the execution schedule obtained by our transformation is time optimal: no transformation of the loop based on the given data-dependencies can yield a shorter running time for that loop.
simple garbage-collector-safety. a conservative garbage collector can typically be used with conventionally compiled programs written in c or c++. but two safety issues must be considered. first, the source code must not hide pointers from the garbage collector. this primarily requires stricter adherence to existing restrictions in the language definition. second, we must ensure that the compiler will not perform transformations that invalidate this requirement.we argue that the same technique can be used to address both issues. we present an algorithm for annotating source or intermediate code to either check the validity of pointer arithmetic in the source, or to guarantee that under minimal, clearly defined assumptions about the compiler, the optimizer cannot "disguise" pointers. we discuss an implementation based on a preprocessor for the gnu c compiler (gcc), and give some measurements of program slow down.
demystifying on-the-fly spill code. modulo scheduling is an effective code generation technique that exploits the parallelism in program loops by overlapping iterations. one drawback of this optimization is that register requirements increase significantly because values across different loop iterations can be live concurrently. one possible solution to reduce register pressure is to insert spill code to release registers. spill code stores values to memory between the producer and consumer instructions.spilling heuristics can be divided into two classes: 1) a posteriori approaches (spill code is inserted after scheduling the loop) or 2) on-the-fly approaches (spill code is inserted during loop scheduling). recent studies have reported obtaining better results for spilling on-the-fly. in this work, we study both approaches and propose two new techniques, one for each approach. our new algorithms try to address the drawbacks observed in previous proposals. we show that the new algorithms outperform previous techniques and, at the same time, reduce compilation time. we also show that, much to our surprise, a posteriori spilling can be in fact slitghtly more effective than on-the-fly spilling.
compiling c for vectorization, parallelization, and inline expansion. practical implementations of real languages are often an excellent way of testing the applicability of theoretical principles. many stresses and strains arise from fitting practicalities, such as performance and standard compatibility, to theoretical models and methods. these stresses and strains are valuable sources of new research and insight, as well as an oft-needed check on the egos of theoreticians. two fertile areas that are often explored by implementations are places where tractable models fail to match practice. this can lead to new models, and may also affect practice (e.g., the average programming language has become more context free over the last several decades). places where existing algorithms fail to deal with practical problems effectively, frequently because the problems are large in some dimension that has not been much explored. the present paper discusses the application of a much studied body of algorithms and techniques [alle 83, kklw 80, bane 76, wolf 78, wolf 82, kenn 80, lamp 74, huso 82] for vectorizing and optimizing fortran to the problem of vectorizing and optimizing c. in the course of this work some algorithms were discarded, others invented, and many were tuned and modified. the experience gave us insight into the strengths and weaknesses of the current theory, as well as into the strong and weak points of c on vector/parallel machines. this paper attempts to communicate some of those insights.
efficient algorithms for bidirectional debugging. this paper discusses our research into algorithms for creating an efficient bidirectional debugger in which all traditional forward movement commands can be performed with equal ease in the reverse direction. we expect that adding these backwards movement capabilities to a debugger will greatly increase its efficacy as a programming tool. the efficiency of our methods arises from our use of event counters that are embedded into the program being debugged. these counters are used to precisely identify the desired target event on the fly as the target program executes. this is in contrast to traditional debuggers that may trap back to the debugger many times for some movements. for reverse movements we re-execute the program (possibly using two passes) to identify and stop at the desired earlier point. our counter based techniques are essential for these reverse movements because they allow us to efficiently execute through the millions of events encountered during re-execution. two other important components of this debugger are its i/o logging and checkpointing. we log and later replay the results of system calls to ensure deterministic re-execution, and we use checkpointing to bound the amount of re-execution used for reverse movements. short movements generally appear instantaneous, and the time for longer movements is usually bounded within a small constant factor of the temporal distance moved back.
abstract debugging of higher-order imperative languages. abstract interpretation is a formal method that enables the static determination (i.e. at compile-time) of the dynamic properties (i.e. at run-time) of programs. we present an abstract interpretation-based method, called abstract debugging, which enables the static and formal debugging of programs, prior to their execution, by finding the origin of potential bugs as well as necessary conditions for these bugs not to occur at run-time. we show how invariant assertions and intermittent assertions, such as termination, can be used to formally debug programs. finally, we show how abstract debugging can be effectively and efficiently applied to higher-order imperative programs with exceptions and jumps to non-local labels, and present the syntox system that enables the abstract debugging of the pascal language by the determination of the range of the scalar variables of programs.
majic: compiling matlab for speed and responsiveness. this paper presents and evaluates techniques to improve the execution performance of matlab. previous efforts concentrated on source to source translation and batch compilation; majic provides an interactive frontend that looks like matlab and compiles/optimizes code behind the scenes in real time, employing a combination of just-in-time and speculative ahead-of-time compilation. performance results show that the proper mixture of these two techniques can yield near-zero response time as well as performance gains previously achieved only by batch compilers.
ownership types for safe region-based memory management in real-time java. the real time specification for java (rtsj) allows a program to create real-time threads with hard real-time constraints. real-time threads use region-based memory management to avoid unbounded pauses caused by interference from the garbage collector. the rtsj uses runtime checks to ensure that deleting a region does not create dangling references and that real-time threads do not access references to objects allocated in the garbage-collected heap. this paper presents a static type system that guarantees that these runtime checks will never fail for well-typed programs. our type system therefore 1) provides an important safety guarantee for real-time programs and 2) makes it possible to eliminate the runtime checks and their associated overhead.our system also makes several contributions over previous work on region types. for object-oriented programs, it combines the benefits of region types and ownership types in a unified type system framework. for multithreaded programs, it allows long-lived threads to share objects without using the heap and without memory leaks. for real-time programs, it ensures that real-time threads do not interfere with the garbage collector. our experience indicates that our type system is sufficiently expressive and requires little programming overhead, and that eliminating the rtsj runtime checks using a static type system can significantly decrease the execution time of real-time programs.
scheduling and mapping: software pipelining in the presence of structural hazards. recently, software pipelining methods based on an ilp (integer linear programming) framework have been successfully applied to derive rate-optimal schedules for architectures involving clean pipelines - pipelines without structural hazards. the problem for architectures beyond such clean pipelines remains open. one challenge is how, under a unified ilp framework, to simultaneously represent resource constraints for unclean pipelines, and the assignment or mapping of operations from a loop to those pipelines. in this paper we provide a framework which does exactly this, and in addition constructs rate-optimal software pipelined schedules. the proposed formulation and a solution method have been implemented and tested on a set of 1006 loops taken from various scientific and integer benchmark suites. the formulation found a rate-optimal schedule for 75% of the loops, and required a median time of only 2 seconds per loop on a sparc 10/30.
using lifetime predictors to improve memory allocation performance. dynamic storage allocation is used heavily in many application areas including interpreters, simulators, optimizers, and translators. we describe research that can improve all aspects of the performance of dynamic storage allocation by predicting the lifetimes of short-lived objects when they are allocated. using five significant, allocation-intensive c programs, we show that a great fraction of all bytes allocated are short-lived (> 90% in all cases). furthermore, we describe an algorithm for liftetime prediction that accurately predicts the lifetimes of 42&ndash;99% of all objects allocated. we describe and simulate a storage allocator that takes adavantage of lifetime prediction of short-lived objects and show that it can significantly improve a program's memory overhead and reference locality, and even, at times, improve cpu performance as well.
context-insensitive alias analysis reconsidered. recent work on alias analysis in the presence of pointers has concentrated on context-sensitive interprocedural analyses, which treat multiple calls to a single procedure independently rather than constructing a single approximation to a procedure's effect on all of its callers. while context-sensitive modeling offers the potential for greater precision by considering only realizable call-return paths, its empirical benefits have yet to be measured.this paper compares the precision of a simple, efficient, context-insensitive points-to analysis for the c programming language with that of a maximally context-sensitive version of the same analysis. we demonstrate that, for a number of pointer-intensive benchmark programs, context-insensitivity exerts little to no precision penalty. we also describe techniques for using the output of context-insensitive analysis to improve the efficiency of context-sensitive analysis without affecting precision.
implementation of the data-flow synchronous language signal. this paper presents the techniques used for the compilation of the data-flow, synchronous language signal. the key feature of the compiler is that it performs formal calculus on systems of boolean equations. the originality of the implementation of the compiler lies in the use of a tree structure to solve the equations.
garbage collection using a dynamic threatening boundary. generational techniques have been very successful in reducing the impact of garbage collection algorithms upon the performance of programs. however, all generational algorithms occasionally promote objects that later become garbage, resulting in an accumulation of garbage in older generations. reclaiming this tenured garbage without resorting to collecting the entire heap is a difficult problem. in this paper, we describe a mechanism that extends existing generational collection algorithms by allowing them to reclaim tenured garbage more effectively. in particular, our dynamic threatening boundary mechanism divides memory into two spaces, one for shortlived, and another for long-lived objects. unlike previous work, our collection mechanism can dynamically adjust the boundary between these two spaces either forward or backward in time, essentially allowing data to become untenured. we describe an implementation of the dynamic threatening boundary mechanism and quantify its associated costs. we also describe a policy for setting the threatening boundary and evaluate its performance relative to existing generational collection algorithms. our results show that a policy that uses the dynamic threatening boundary mechanism is effective at reclaiming tenured garbage.
efficient building and placing of gating functions. in this paper, we present an almost-linear time algorithm for constructing gated single assignment (gsa), which is ssa augmented with gating functions at &oslash;-nodes. the gating functions specify the control dependences for each reaching definition at a &oslash;-node. we introduce a new concept of gating path, which is path in the control flow graph from the immediate dominator u of a node v to v, such that every node in the path is dominated by u. previous algorithms start with &oslash;-function placement, and then traverse the control flow graph to compute the gating functions. by formulating the problem into gating path construction, we are able to identify not only a &oslash;-node, but also a gating path expression which defines a gating function for the &oslash;-node.
communication optimization and code generation for distributed memory machines. this paper presents several algorithms to solve code generation and optimization problems specific to machines with distributed address spaces. given a description of how the computation is to be partitioned across the processors in a machine, our algorithms produce an spmd (single program multiple data) program to be run on each processor. our compiler generated the necessary receive and send instructions, optimizes the communication by eliminating redundant communication and aggregating small messages into large messages, allocates space locally on each processor, and translates global data addresses to local addresses. our techniques are based on an exact data-flow analysis on individual array element accesses. unlike data dependence analysis, this analysis determines if two dynamic instances refer to the same value, and not just to the same location. using this information, our compiler can handle more flexible data decompositions and find more opportunities for communication optimization than systems based on data dependence analysis. our technique is based on a uniform framework, where data decompositions, computation decompositions and the data flow information are all represented as systems of linear inequalities. we show that the problems of communication code generation, local memory management, message aggregation and redundant data communication elimination can all be solved by projecting polyhedra represented by sets of inequalities onto lower dimensional spaces.