waashk/dblp huggingface dataset:
the transactional manifesto: software engineering and non-blocking synchronization. computer architecture is about to undergo, if not another revolution, then a vigorous shaking-up. the major chip manufacturers have, for the time being, simply given up trying to make processors run faster. instead, they have recently started shipping "multicore" architectures, in which multiple processors (cores) communicate directly through shared hardware caches, providing increased concurrency instead of increased clock speed.as a result, system designers and software engineers can no longer rely on increasing clock speed to hide software bloat. instead, they must somehow learn to make effective use of increasing parallelism. this adaptation will not be easy. conventional synchronization techniques based on locks and conditions are unlikely to be effective in such a demanding environment. coarse-grained locks, which protect relatively large amounts of data, do not scale, and fine-grained locks introduce substantial software engineering problems.transactional memory is a computational model in which threads synchronize by optimistic, lock-free transactions. this synchronization model promises to alleviate many (perhaps not all) of the problems associated with locking, and there is a growing community of researchers working on both software and hardware support for this approach. this talk will survey the area, with a focus on open research problems.
garbage collection without paging. garbage collection offers numerous software engineering advantages, but interacts poorly with virtual memory managers. existing garbage collectors require far more pages than the application's working set and touch pages without regard to which ones are in memory, especially during full-heap garbage collection. the resulting paging can cause throughput to plummet and pause times to spike up to seconds or even minutes. we present a garbage collector that avoids paging. this bookmarking collector cooperates with the virtual memory manager to guide its eviction decisions. using summary information ("bookmarks") recorded from evicted pages, the collector can perform in-memory full-heap collections. in the absence of memory pressure, the bookmarking collector matches the throughput of the best collector we tested while running in smaller heaps. in the face of memory pressure, it improves throughput by up to a factor of five and reduces pause times by up to a factor of 45 over the next best collector. compared to a collector that consistently provides high throughput (generational mark-sweep), the bookmarking collector reduces pause times by up to 218x and improves throughput by up to 41x. bookmarking collection thus provides greater utilization of available physical memory than other collectors while matching or exceeding their throughput.
caching function calls using precise dependencies. this paper describes the implementation of a purely functional programming language for building software systems. in this language, external tools like compilers and linkers are invoked by function calls. because some function calls are extremely expensive, it is obviously important to reuse the results of previous function calls whenever possible. caching a function call requires the language interpreter to record all values on which the function call depends. for optimal caching, it is important to record precise dependencies that are both dynamic and fine-grained. the paper sketches how we compute such dependencies, describes the implementation of an efficient function cache, and evaluates our implementation's performance.
dynamic software updating. many important applications must run continuously and without interruption, yet must be changed to fix bugs or upgrade functionality. no prior general-purpose methodology for dynamic updating achieves a practical balance between flexibility, robustness, low overhead, and ease of use. we present a new approach for c-like languages that provides type-safe dynamic updating of native code in an extremely flexible manner (code, data, and types may be updated, at programmer-determined times) and permits the use of automated tools to aid the programmer in the updating process. our system is based on dynamic patches that both contain the updated code and the code needed to transition from the old version to the new. a novel aspect of our patches is that they consist of verifiable native code (e.g. proof-carrying code [17] or typed assembly language [16]), which is native code accompanied by annotations that allow on-line verification of the code's safety. we discuss how patches are generated mostly automatically, how they are applied using dynamic-linking technology, and how code is compiled to make it updateable. to concretely illustrate our system, we have implemented a dynamically-updateable web server, flashed. we discuss our experience building and maintaining flashed. performance experiments show that for flashed, the overhead due to updating is typically less than 1%.
representing control in the presence of first-class continuations. languages such as scheme and smalltalk that provide continuations as first-class data objects present a challenge to efficient implementation. allocating activation records in a heap has proven unsatisfactory because of increased frame linkage costs, increased garbage collection overhead, and decreased locality of reference. however, simply allocating activation records on a stack and copying them when a continuation is created results in unbounded copying overhead. this paper describes a new approach based on stack allocation that does not require the stack to be copied when a continuation is created and that allows us to place a small upper bound on the amount copied when a continuation is reinstated. this new approach is faster than the naive stack allocation approach, and it does not suffer from the problems associated with unbounded copying. for continuation-intensive programs, our approach is at worst a constant factor slower than the heap allocation approach, and for typical programs, it is significantly faster. an important additional benefit is that recovery from stack overflow is handled gracefully and efficiently.
debugging optimized code with dynamic deoptimization. self's debugging system provides complete source-level debugging (expected behavior) with globally optimized code. it shields the debugger from optimizations performed by the compiler by dynamically deoptimizing code on demand. deoptimization only affects the procedure activations that are actively being debugged; all other code runs at full speed. deoptimization requires the compiler to supply debugging information at discrete interrupt points; the compiler can still perform extensive optimizations between interrupt points without affecting debuggability. at the same time, the inability to interrupt between interrupt points is invisible to the user. our debugging system also handles programming changes during debugging. again, the system provides expected behavior: it is possible to change a running program and immediately observe the effects of the change. dynamic deoptimization transforms old compiled code (which may contain inlined copies of the old version of the changed procedure) into new versions reflecting the current source-level state. to the best of our knowledge, self is the first practical system providing full expected behavior with globally optimized code.
compiling real-time programs into schedulable code. we present a programming language with first-class timing constructs, whose semantics is based on time-constrained relationships between observable events. since a system specification postulates timing relationships between events, realizing the specification in a program becomes a more straightforward process. using these constraints, as well as those imposed by data and control flow properties, our objective is to transform the code so that its worst-case execution time is consistent with its real-time requirements. to accomplish this goal we first translate an event-based source program into intermediate code, in which the timing constraints are imposed on the code itself, and then use a compilation technique which synthesizes feasible code from the original source program.
alphonse: incremental computation as a programming abstraction. alphonse is a program transformation system that uses dynamic dependency analysis and incremental computation techniques to automatically generate efficient dynamic implementations from simple exhaustive imperative program specifications.
experience with cst: programming and implementation. cst is a programming language based on smalltalk-802 that supports concurrency using locks, asynchronous messages, and distributed objects. in this paper, we describe cst: the language and its implementation. example programs and initial programming experience with cst are described. our implementation of cst generates native code for the j-machine, a fine-grained concurrent computer. some compiler optimizations developed in conjunction with that implementation are also described.
identifying the semantic and textual differences between two versions of a program. text-based file comparators (e.g., the unix utility diff), are very general tools that can be applied to arbitrary files. however, using such tools to compare programs can be unsatisfactory because their only notion of change is based on program text rather than program behavior. this paper describes a technique for comparing two versions of a program, determining which program components represents changes, and classifying each changed component as representing either a semantic or a textual change.
dependence analysis for pointer variables. our concern is how to determine data dependencies between program constructs in programming languages with pointer variables. we are particularly interested in computing data dependencies for languages that manipulate heap-allocated storage, such as lisp and pascal. we have defined a family of algorithms that compute safe approximations to the flow, output, and anti-dependencies of a program written in such a language. our algorithms account for destructive updates to fields of a structure and thus are not limited to the cases where all structures are trees or acyclic graphs; they are applicable to programs that build cyclic structures. our technique extends an analysis method described by jones and muchnick that determines an approximation to the actual layouts of memory that can arise at each program point during execution. we extend the domain used in their abstract interpretation so that the (abstract) memory locations are labeled by the program points that set their contents. data dependencies are then determined from these memory layouts according to the component labels found along the access paths that must be traversed during execution to evaluate the program's statements and predicates. for structured programming constructs, the technique can be extended to distinguish between loop-carried and loop-independent dependencies, as well as to determine lower bounds on minimum distances for loop-carried dependencies.
interprocedural slicing using dependence graphs. a slice of a program with respect to a program point p and variable x consists of all statements of the program that might affect the value of x at point p. this paper concerns the problem of interprocedural slicing -- generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. to solve this problem, we introduce a new kind of graph to represent programs, called a system dependence graph, which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. our main result is an algorithm for interprocedural slicing that uses the new representation.the chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. to handle this problem, system dependence graphs include some data-dependence edges that represent transitive dependencies due to the effects of procedure calls, in addition to the conventional direct-dependence edges. these edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. this structure takes the form of an attribute grammar. the step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.
the design, implementation, and evaluation of a compiler algorithm for cpu energy reduction. this paper presents the design and implementation of a compiler algorithm that effectively optimizes programs for energy usage using dynamic voltage scaling (dvs). the algorithm identifies program regions where the cpu can be slowed down with negligible performance loss. it is implemented as a source-to-source level transformation using the suif2 compiler infrastructure. physical measurements on a high-performance laptop show that total system (i.e., laptop) energy savings of up to 28% can be achieved with performance degradation of less than 5% for the specfp95 benchmarks. on average, the system energy and energy-delay product are reduced by 11% and 9%, respectively, with a performance slowdown of 2%. it was also discovered that the energy usage of the programs using our dvs algorithm is within 6% from the theoretical lower bound. to the best of our knowledge, this is one of the first work that evaluates dvs algorithms by physical measurements.
lifetime-sensitive modulo scheduling. this paper shows how to software pipeline a loop for minimal register pressure without sacrificing the loop's minimum execution time. this novel bidirectional slack-scheduling method has been implemented in a fortran compiler and tested on many scientific benchmarks. the empirical results&mdash;when measured against an absolute lower bound on execution time, and against a novel schedule-independent absolute lower bound on register pressure&mdash;indicate near-optimal performance.
a block-and-actions generator as an alternative to a simulator for collecting architecture measurements. to design a new processor or to modify an existing one, designers need to gather data to estimate the influence of specific architecture features on the performance of the proposed machine (pm). to obtain this data, it is necessary to measure on an existing machine (em) the dynamic behavior of typical programs. traditionally, simulators have been used to obtain measurements for pms. since several hundred em instructions are required to decode, interpret, and measure each simulated (pm) instruction, the simulation time of typical programs is prohibitively large. thus, designers tend to simulate only small programs and the results obtained might not be representative of a real system behavior. in this paper we present an alternative tool for collecting architecture measurements: the block-and-actions generator (bkgen). bkgen produces a version of the program being measured which is directly executable by the em. this executable version is obtained directly with the em compiler or with the pm compiler and a assembly-to-assembly translator. the choice between these alternatives depends on the em and pm compiler technology and the type of measurements to be obtained. bkgen also collects the pm events to be measured (called actions). each em block of instructions is associated with a pm block of actions so that when the program is executed, it collects the measurements associated with the pm. the main advantage of bkgen is that the execution time is substantially reduced compared to the execution time of a simulator while collecting similar data. thus, large typical programs (compilers, assemblers, word processors, ...) can be used by the designer to obtain meaningful measurements.
a general data dependence test for dynamic, pointer-based data structures. optimizing compilers require accurate dependence testing to enable numerous, performance-enhancing transformations. however, data dependence testing is a difficult problem, particularly in the presence of pointers. though existing approaches work well for pointers to named memory locations (i.e. other variables), they are overly conservative in the case of pointers to unnamed memory locations. the latter occurs in the context of dynamic, pointer-based data structures, used in a variety of applications ranging from system software to computational geometry to n-body and circuit simulations. in this paper we present a new technique for performing more accurate data dependence testing in the presence of dynamic, pointer-based data structures. we will demonstrate its effectiveness by breaking false dependences that existing approaches cannot, and provide results which show that removing these dependences enables significant parallelization of a real application.
stride prefetching by dynamically inspecting objects. software prefetching is a promising technique to hide cache miss latencies, but it remains challenging to effectively prefetch pointer-based data structures because obtaining the memory address to be prefetched requires pointer dereferences. the recently proposed stride prefetching overcomes this problem, but it only exploits inter-iteration stride patterns and relies on an off-line profiling method.we propose a new algorithm for stride prefetching which is intended for use in a dynamic compiler. we exploit both inter- and intra-iteration stride patterns, which we discover using an ultra-lightweight profiling technique, called object inspection. this is a kind of partial interpretation that only a dynamic compiler can perform. during the compilation of a method, the dynamic compiler gathers the profile information by partially interpreting the method using the actual values of parameters and causing no side effects.we evaluated an implementation of our prefetching algorithm in a production-level java just-in time compiler. the results show that the algorithm achieved up to an 18.9% and 25.1% speedup in industry-standard benchmarks on the pentium 4 and the athlon mp, respectively, while it increased the compilation time by less than 3.0%.
type declarations as subtype constraints in logic programming. this paper presents a type system for logic programs that supports parametric polymorphism and subtypes. this system follows most knowledge representation and object-oriented schemes in that subtyping is name-based, i.e., &tgr;1 is considered to be a subtype of &tgr;2 iff it is declared as such. we take this as a fundamental principle in the sense that type declarations have the form of subtype constraints. types are assigned meaning by viewing such constraints as horn clauses that, together with a few basic axioms, define a subtype predicate. this technique provides a (least) model for types and, at the same time, a sound and complete proof system for deriving subtypes. using this proof system, we define well-typedness conditions which ensure that a logic program/query respects a set of predicate types. we prove that these conditions are consistent in the sense that every atom of every resolvent produced during the execution of a well-typed program is consistent with its type.
a customizable substrate for concurrent languages. we describe an approach to implementing a wide-range of concurrency paradigms in high-level (symbolic) programming languages. the focus of our discussion is sting, a dialect of scheme, that supports lightweight threads of control and virtual processors as first-class objects. given the significant degree to which the behavior of these objects may be customized, we can easily express a variety of concurrency paradigms and linguistic structures within a common framework without loss of efficiency. unlike parallel systems that rely on operating system services for managing concurrency, sting implements concurrency management entirely in terms of scheme objects and procedures. it, therefore, permits users to optimize the runtime behavior of their applications without requiring knowledge of the underlying runtime system. this paper concentrates on (a) the implications of the design for building asynchronous concurrency structures, (b) organizing large-scale concurrent computations, and (c) implementing robust programming environments for symbolic computing.
flow-directed inlining. a flow-directed inlining strategy uses information derived from control-flow analysis to specialize and inline procedures for functional and object-oriented languages. since it uses control-flow analysis to identify candidate call sites, flow-directed inlining can inline procedures whose relationships to their call sites are not apparent. for instance, procedures defined in other modules, passed as arguments, returned as values, or extracted from data structures can all be inlined. flow-directed inlining specializes procedures for particular call sites, and can selectively inline a particular procedure at some call sites but not at others. finally, flow-directed inlining encourages modular implementations: control-flow analysis, inlining, and post-inlining optimizations are all orthogonal components. results from a prototype implementation indicate that this strategy effectively reduces procedure call overhead and leads to significant reduction in execution time.
an efficient approach to data flow analysis in a multi pass global optimizer. data flow analysis is a time-consuming part of the optimization process. as transformations are made in a multiple pass global optimizer, the data flow information must be updated to reflect these changes. various approaches have been used, including complete recalculation as well as partial recalculation over the affected area. the approach presented here has been designed for maximum efficiency. data flow information is completely calculated only once, using an interval analysis method which is slightly faster than a purely iterative approach, and which allows partial recomputation when appropriate. a minimal set of data flow information is computed, keeping the computation and update cost low. following each set of transformations, the data flow information is updated based on knowledge of the effect of each change. this approach saves considerable time over complete recalculation, and proper ordering of the various optimizations minimizes the amount of update required.
algorithm specialization in generic programming: challenges of constrained generics in c++. generic programming has recently emerged as a paradigm for developing highly reusable software libraries, most notably in c++. we have designed and implemented a constrained generics extension for c++ to support modular type checking of generic algorithms and to address other issues associated with unconstrained generics. to be as broadly applicable as possible, generic algorithms are defined with minimal requirements on their inputs. at the same time, to achieve a high degree of efficiency, generic algorithms may have multiple implementations that exploit features of specific classes of inputs. this process of algorithm specialization relies on non-local type information and conflicts directly with the local nature of modular type checking. in this paper, we review the design and implementation of our extensions for generic programming in c++, describe the issues of algorithm specialization and modular type checking in detail, and discuss the important design tradeoffs in trying to accomplish both.we present the particular design that we chose for our implementation, with the goal of hitting the sweet spot in this interesting design space.