waashk/dblp huggingface dataset:
kiss: keep it simple and sequential. the design of concurrent programs is error-prone due to the interaction between concurrently executing threads. traditional automated techniques for finding errors in concurrent programs, such as model checking, explore all possible thread interleavings. since the number of thread interleavings increases exponentially with the number of threads, such analyses have high computational complexity. in this paper, we present a novel analysis technique for concurrent programs that avoids this exponential complexity. our analysis transforms a concurrent program into a sequential program that simulates the execution of a large subset of the behaviors of the concurrent program. the sequential program is then analyzed by a tool that only needs to understand the semantics of sequential execution. our technique never reports false errors but may miss errors. we have implemented the technique in kiss, an automated checker for multithreaded c programs, and obtained promising initial results by using kiss to detect race conditions in windows device drivers.
mitosis compiler: an infrastructure for speculative threading based on pre-computation slices. speculative parallelization can provide significant sources of additional thread-level parallelism, especially for irregular applications that are hard to parallelize by conventional approaches. in this paper, we present the mitosis compiler, which partitions applications into speculative threads, with special emphasis on applications for which conventional parallelizing approaches fail.the management of inter-thread data dependences is crucial for the performance of the system. the mitosis framework uses a pure software approach to predict/compute the thread's input values. this software approach is based on the use of pre-computation slices (p-slices), which are built by the mitosis compiler and added at the beginning of the speculative thread. p-slices must compute thread input values accurately but they do not need to guarantee correctness, since the underlying architecture can detect and recover from misspeculations. this allows the compiler to use aggressive/unsafe optimizations to significantly reduce their overhead. the most important optimizations included in the mitosis compiler and presented in this paper are branch pruning, memory and register dependence speculation, and early thread squashing.performance evaluation of mitosis compiler/architecture shows an average speedup of 2.2.
profile-directed optimization of event-based programs. events are used as a fundamental abstraction in programs ranging from graphical user interfaces (guis) to systems for building customized network protocols. while providing a flexible structuring and execution paradigm, events have the potentially serious drawback of extra execution overhead due to the indirection between modules that raise events and those that handle them. this paper describes an approach to addressing this issue using static optimization techniques. this approach, which exploits the underlying predictability often exhibited by event-based programs, is based on first profiling the program to identify commonly occurring event sequences. a variety of techniques that use the resulting profile information are then applied to the program to reduce the overheads associated with such mechanisms as indirect function calls and argument marshaling. in addition to describing the overall approach, experimental results are given that demonstrate the effectiveness of the techniques. these results are from event-based programs written for x windows, a system for building guis, and cactus, a system for constructing highly configurable distributed services and network protocols.
data flow frequency analysis. conventional dataflow analysis computes information about what facts may or will not hold during the execution of a program. sometimes it is useful, for program optimization, to know how often or with what probability a fact holds true during program execution. in this paper, we provide a precise formulation of this problem for a large class of dataflow problems --- the class of finite bi-distributive subset problems. we show how it can be reduced to a generalization of the standard dataflow analysis problem, one that requires a sum-over-all-paths quantity instead of the usual meet-overall-paths quantity. we show that kildall's result expressing the meet-over-all-paths value as a maximal-fixed-point carries over to the generalized setting. we then outline ways to adapt the standard dataflow analysis algorithms to solve this generalized problem, both in the intraprocedural and the interprocedural case.
a member lookup algorithm for c++. the member lookup problem in c++ is the problem of resolving a specified member name in the context of a specified class. member lookup in c++ is complicated by the presence of virtual inheritance and multiple inheritance. in this paper, we present an efficient algorithm for member lookup in c++. we also present a formalism for the multiple inheritance mechanism of c++, which we use as the basis for deriving our algorithm. the formalism may also be of use as a formal basis for deriving other c++ compiler algorithms.
relocating machine instructions by currying. relocation adjusts machine instructions to account for changes in the locations of the instructions themselves or of external symbols to which they refer. standard linkers implement a finite set of relocation transformations, suitable for a single architecture. these transformations are enumerated, named, and engraved in a machine-dependent object-file format, and linkers must recognize them by name. these names and their associated transformations are an unnecessary source of machine-dependence.the new jersey machine-code toolkit is an application generator. it helps programmers create applications that manipulate machine code, including linkers. guided by a short instruction-set specification, the toolkit generates the bit-manipulating code. instructions are described by constructors, which denote functions mapping lists of operands to instructions' binary representations. any operand can be designated as "relocatable," meaning that the operand's value need not be known at the time the instruction is encoded. for instructions with relocatable operands, the toolkit computes relocating transformations. tool writers can use the toolkit to create machine-independent software that relocates machine instructions. mld, a retargetable linker built with the toolkit, needs only 20 lines of c code for relocation, and that code is machine-independent.the toolkit discovers relocating transformations by currying encoding functions. an attempt to encode an instruction with a relocatable operand results in the creation of a closure. the closure can be applied when the values of the relocatable operands become known. currying provides a general, machine-independent method of relocation.currying rewrites a &lambda;-term into two nested &lambda;-terms. the standard implementation has the first &lambda; allocate a closure and store therein its operands and a pointer to the second &lambda;. using this strategy in the toolkit means that, when it builds an application, the toolkit generates code for many different inner &lambda;-terms---one for each instruction that uses a relocatable address. hoisting some of the computation out of the second &lambda; into the first makes many of the second &lambda;s identical---a handful are enough for a whole instruction set. this optimization reduces the size of machine-dependent assembly and linking code by 15--20% for the mips, sparc, and powerpc, and by about 30% for the pentium. it also makes the second &lambda;s equivalent to relocating transformations named in standard object-file formats.
a retargetable debugger. we are developing techniques for building retargetable debuggers. our prototype, 1db, debugs c programs compiled for the mips r3000, motorola 68020, sparc, and vax architectures. it can use a network to connect to faulty processes and can do cross-architecture debugging. 1db's total code size is about 16,000 lines, but it needs only 250&ndash;550 lines of machine-dependent code for each target. 1db owes its retargetability to three techniques: getting help from the compiler, using a machine-independent embedded interpreter, and choosing abstractions that minimize and isolate machine-dependent code. 1db reuses existing compiler function by having the compiler emit postscript code that 1db later interprets; postscript works well in this unusual context.
a single intermediate language that supports multiple implementations of exceptions. we present mechanisms that enable our compiler-target language, c--, to express four of the best known techniques for implementing exceptions, all within a single, uniform framework. we define the mechanisms precisely, using a formal operational semantics. we also show that exceptions need not require special treatment in the optimizer; by introducing extra dataflow edges, we make standard optimization techniques work even on programs that use exceptions. our approach clarifies the design space of exception-handling techniques, and it allows a single optimizer to handle a variety of implementation techniques. our ultimate goal is to allow a source-language compiler the freedom to choose its exception-handling policy, while encapsulating the architecture-dependent mechanisms and their optimization in an implementation of c--that can be used by compilers for many source languages.
storage assignment optimizations to generate compact and efficient code on embedded dsps. dsp architectures typically provide dedicated memory address generation units and indirect addressing modes with auto-increment and auto-decrement that subsume address arithmetic calculation. the heavy use of auto-increment and auto-decrement indirect addressing require dsp compilers to perform a careful placement of variables in storage to minimize address arithmetic instructions to generate compact and efficient dsp code. liao et al. formulated the problem of storage assignment as the simple offset assignment problem (soa) and the general offset assignment problem (goa), and proposed heuristic solutions.the storage allocation of variables critically depends on the sequence of variable accesses. in this paper we present techniques to optimize the access sequence of variables by applying algebraic transformations (such as commutativity and associativity) on expression trees to obtain the least cost offset assignment. we develop a new formulation of this problem as the least cost access sequence problem (lcas). based on the proposed framework, we develop heuristic algorithms that determine empirically near-optimal solutions resulting in fewer address arithmetic instructions. we have implemented the proposed heuristic algorithms by extending the storage assignment optimization in the spam compiler back-end targeted for the tms320c25 dsp. in the case of soa, experimental results for programs from the dspstone benchmark suite show an average improvement of 3.36% in static code size and an average relative speed-up of 7.28% over results obtained using existing soa algorithms. the average code size reduction over code compiled with a naive storage assignment algorithm is 7.04%. the proposed framework has also been applied to the goa problem and shows average code size reductions of 2.04% over results obtained using existing goa algorithms, and average code size reductions of 10.84% over a naive goa algorithm. code size reduction and improvement in dynamic instruction counts could be valuable given limited memory and real-time response requirements placed on embedded systems.
register allocation for software pipelined loops. software pipelining is an important instruction scheduling technique for efficiently overlapping successive iterations of loops and executing them in parallel. this paper studies the task of register allocation for software pipelined loops, both with and without hardware features that are specifically aimed at supporting software pipelines. register allocation for software pipelines presents certain novel problems leading to unconventional solutions, especially in the presence of hardware support. this paper formulates these novel problems and presents a number of alternative solution strategies. these alternatives are comprehensively tested against over one thousand loops to determine the best register allocation strategy, both with and without the hardware support for software pipelining.
the lrpd test: speculative run-time parallelization of loops with privatization and reduction parallelization. current parallelizing compilers cannot identify a significant fraction of parallelizable loops because they have complex or statically insufficiently defined access patterns. as parallelizable loops arise frequently in practice, we advocate a novel framework for their identification: speculatively execute the loop as a doall and apply a fully parallel data dependence test to determine if it had any cross-iteration dependences; if the test fails, then the loop is reexecuted serially. since, from our experience, a significant amount of the available parallelism in fortran programs can be exploited by loops transformed through privatization and reduction parallelization, our methods can speculatively apply these transformations and then check their validity at run-time. another important contribution of this paper is a novel method for reduction recognition which goes beyond syntactic pattern matching: it detects at run-time if the values stored in an array participate in a reduction operation, even if they are transferred through private variables and/or are affected by statically unpredictable control flow. we present experimental results on loops from the perfect benchmarks, which substantiate our claim that these techniques can yield significant speedups which are often superior to those obtainable by inspector/executor methods
cache performance of garbage-collected programs. as processor speeds continue to improve relative to main-memory access times, cache performance is becoming an increasingly important component of program performance. prior work on the cache performance of garbage-collected programs either argues or assumes that conventional garbage-collection methods will yield poor performance, and has therefore concentrated on new collection algorithms designed specifically to improve cache-level reference locality. this paper argues to the contrary: many programs written in garbage-collected languages are naturally well-suited to the direct-mapped caches typically found in modern computer systems. garbage-collected programs written in a mostly-functional style should perform well when simple linear storage allocation and an infrequently-run generational compacting collector are employed; sophisticated collectors intended to improve cache performance are unlikely to be necessary. as locality becomes ever more important to program performance, programs of this kind may turn out to have a significant performance advantage over programs written in traditional languages.
optimizing data permutations for simd devices. the widespread presence of simd devices in today's microprocessors has made compiler techniques for these devices tremendously important. one of the most important and difficult issues that must be addressed by these techniques is the generation of the data permutation instructions needed for non-contiguous and misaligned memory references. these instructions are expensive and, therefore, it is of crucial importance to minimize their number to improve performance and, in many cases, enable speedups over scalar code.although it is often difficult to optimize an isolated data reorganization operation, a collection of related data permutations can often be manipulated to reduce the number of operations. this paper presents a strategy to optimize all forms of data permutations. the strategy is organized into three steps. first, all data permutations in the source program are converted into a generic representation. these permutations can originate from vector accesses to non-contiguous and misaligned memory locations or result from compiler transformations. second, an optimization algorithm is applied to reduce the number of data permutations in a basic block. by propagating permutations across statements and merging consecutive permutations whenever possible, the algorithm can significantly reduce the number of data permutations. finally, a code generation algorithm translates generic permutation operations into native permutation instructions for the target platform. experiments were conducted on various kinds of applications. the results show that up to 77% of the permutation instructions are eliminated and, as a result, the average performance improvement is 48% on vmx and 68% on sse2. for several applications, near perfect speedups have been achieved on both platforms.
synchronous operations as first-class values. synchronous message passing via channels is an interprocess communication (ipc) mechanism found in several concurrent languages, such as csp, occam, and amber. such languages provide a powerful selective i/o operation, which plays a vital role in managing communication with multiple processes. because the channel ipc mechanism is &ldquo;operation-oriented,&rdquo; only procedural abstraction techniques can be used in structuring the communication/synchronization aspects of a system. this has the unfortunate effect of restricting the use of selective i/o, which in turn limits the communication structure. we propose a new, &ldquo;value-oriented&rdquo; approach to channel-based synchronization. we make synchronous operations first-class values, called events, in much the same way that functions are first-class values in functional programming languages. our approach allows the use of data abstraction techniques for structuring ipc. we have incorporated events into pml, a concurrent functional programming language, and have implemented run-time support for them as part of the pegasus system.
simple objects for standard ml. we propose a new approach to adding objects to standard ml (sml) based on explicit declarations of object types, object constructors, and subtyping relationships, with a generalization of the sml case statement to a "typecase" on object types. the language, called object ml (oml), has a type system that conservatively extends the sml type system, preserves sound static typing, and permits type inference. the type system sacrifices some of the expressiveness found in recently proposed schemes, but has the virtue of simplicity. we give examples of how features found in other object-oriented languages can be emulated in oml, discuss the formal properties of oml, and describe some implementation issues.
commutativity analysis: a new analysis framework for parallelizing compilers. this paper presents a new analysis technique, commutativity analysis, for automatically parallelizing computations that manipulate dynamic, pointer-based data structures. commutativity analysis views the computation as composed of operations on objects. it then analyzes the program at this granularity to discover when operations commute (i.e. generate the same final result regardless of the order in which they execute). if all of the operations required to perform a given computation commute, the compiler can automatically generate parallel code. we have implemented a prototype compilation system that uses commutativity analysis as its primary analysis framework. we have used this system to automatically parallelize two complete scientific computations: the barnes-hut n-body solver and the water code. this paper presents performance results for the generated parallel code running on the stanford dash machine. these results provide encouraging evidence that commutativity analysis can serve as the basis for a successful parallelizing compiler.
data transformations for eliminating conflict misses. many cache misses in scientific programs are due to conflicts caused by limited set associativity. we examine two compile-time data-layout transformations for eliminating conflict misses, concentrating on misses occuring on every loop iteration. inter-variable padding adjusts variable base addresses, while intra-variable padding modifies array dimension sizes. two levels of precision are evaluated. padlite only uses array and column dimension sizes, relying on assumptions about common array reference patterns. pad analyzes programs, detecting conflict misses by linearizing array references and calculating conflict distances between uniformly-generated references. the euclidean algorithm for computing the gcd of two numbers is used to predict conflicts between different array columns for linear algebra codes. experiments on a range of programs indicate padlite can eliminate conflicts for benchmarks, but pad is more effective over a range of cache and problem sizes. padding reduces cache miss rates by 16% on average for a 16k direct-mapped cache. execution times are reduced by 6% on average, with some spec95 programs improving up to 15%.
the illinois functional programming interpreter. the illinois functional programming (ifp) language is a modified version of backus' fp(1). ifp has the same side-effect free combinator style of backus fp, while introducing an algol-like syntax and structure. while ifp superficially appears to be an inefficient language to execute, its simplicity makes it quick to interpret. functions are always monadic and there are no variable or parameter names. furthermore, combinator-style languages allow common housekeeping operations to be condensed into efficient machine-language primitives.by reference-counting, the interpreter can often convert call-by-value to destructive call-by-reference while preserving referential transparency. the interpreter has an expression cache which can improve the asymptotic time of some combinatorial functions. ifp function definitions are stored as unix files, so much of unix's functionality is immediately borrowed into the ifp environment, e.g. ls, more, and grep.benchmarks indicate that ifp is an order of magnitude faster than berkeley fp[2], and is competitive with interpreted von-neumann languages such as basic. the interpreter can parallel process on shared-memory multiprocessors, e.g. the encore multimax. ifp currently runs on machines as varied as the ibm pc, vax, and cray-xmp.
process decomposition through locality of reference. in the context of sequential computers, it is common practice to exploit temporal locality of reference through devices such as caches and virtual memory. in the context of multiprocessors, we believe that it is equally important to exploit spatial locality of reference. we are developing a system which, given a sequential program and its domain decomposition, performs process decomposition so as to enhance spatial locality of reference. we describe an application of this method - generating code from shared-memory programs for the (distributed memory) intel ipsc/2.