waashk/dblp huggingface dataset:
memory access coalescing: a technique for eliminating redundant memory accesses. as microprocessor speeds increase, memory bandwidth is increasingly the performance bottleneck for microprocessors. this has occurred because innovation and technological improvements in processor design have outpaced advances in memory design. most attempts at addressing this problem have involved hardware solutions. unfortunately, these solutions do little to help the situation with respect to current microprocessors. in previous work, we developed, implemented, and evaluated an algorithm that exploited the ability of newer machines with wide-buses to load/store multiple floating-point operands in a single memory reference. this paper describes a general code improvement algorithm that transforms code to better exploit the available memory bandwidth on existing microprocessors as well as wide-bus machines. where possible and advantageous, the algorithm coalesces narrow memory references into wide ones. an interesting characteristic of the algorithm is that some decisions about the applicability of the transformation are made at run time. this dynamic analysis significantly increases the probability of the transformation being applied. the code improvement transformation was implemented and added to the repertoire of code improvements of an existing retargetable optimizing back end. using three current architectures as evaluation platforms, the effectiveness of the transformation was measured on a set of compute- and memory-intensive programs. interestingly, the effectiveness of the transformation varied significantly with respect to the instruction-set architecture of the tested platform. for one of the tested architectures, improvements in execution speed ranging from 5 to 40 percent were observed. for another, the improvements in execution speed ranged from 5 to 20 percent, while for yet another, the transformation resulted in slower code for all programs.
selective specialization for object-oriented languages. dynamic dispatching is a major source of run-time overhead in object-oriented languages, due both to the direct cost of method lookup and to the indirect effect of preventing other optimizations. to reduce this overhead, optimizing compilers for object-oriented languages analyze the classes of objects stored in program variables, with the goal of bounding the possible classes of message receivers enough so that the compiler can uniquely determine the target of a message send at compile time and replace the message send with a direct procedure call. specialization is one important technique for improving the precision of this static class information: by compiling multiple versions of a method, each applicable to a subset of the possible argument classes of the method, more precise static information about the classes of the method's arguments is obtained. previous specialization strategies have not been selective about where this technique is applied, and therefore tended to significantly increase compile time and code space usage, particularly for large applications. in this paper, we present a more general framework for specialization in object-oriented languages and describe a goal directed specialization algorithm that makes selective decisions to apply specialization to those cases where it provides the highest benefit. our results show that our algorithm improves the performance of a group of sizeable programs by 65% to 275% while increasing compiled code space requirements by only 4% to 10%. moreover, when compared to the previous state-of-the-art specialization scheme, our algorithm improves performance by 11% to 67% while simultaneously reducing code space requirements by 65% to 73%.
unfold/fold transformations and loop optimization of logic programs. programs typically spend much of their execution time in loops. this makes the generation of efficient code for loops essential for good performance. loop optimization of logic programming languages is complicated by the fact that such languages lack the iterative constructs of traditional languages, and instead use recursion to express loops. in this paper, we examine the application of unfold/fold transformations to three kinds of loop optimization for logic programming languages: recursion removal, loop fusion and code motion out of loops. we describe simple unfold/fold transformation sequences for these optimizations that can be automated relatively easily. in the process, we show that the properties of unification and logical variables can sometimes be used to generalize, from traditional languages, the conditions under which these optimizations may be carried out. our experience suggests that such source-level transformations may be used as an effective tool for the optimization of logic programs.
profile-guided code compression. as computers are increasingly used in contexts where the amount of available memory is limited, it becomes important to devise techniques that reduce the memory footprint of application programs while leaving them in an executable form. this paper describes an approach to applying data compression techniques to reduce the size of infrequently executed portions of a program. the compressed code is decompressed dynamically (via software) if needed, prior to execution. the use of data compression techniques increases the amount of code size reduction that can be achieved; their application to infrequently executed code limits the runtime overhead due to dynamic decompression; and the use of software decompression renders the approach generally applicable, without requiring specialized hardware. the code size reductions obtained depend on the threshold used to determine what code is "infrequently executed" and hence should be compressed: for low thresholds, we see size reductions of 13.7% to 18.8%, on average, for a set of embedded applications, without excessive runtime overhead.
task granularity analysis in logic programs. while logic programming languages offer a great deal of scope for parallelism, there is usually some overhead associated with the execution of goals in parallel because of the work involved in task creation and scheduling. in practice, therefore, the &ldquo;granularity&rdquo; of a goal, i.e. an estimate of the work available under it, should be taken into account when deciding whether or not to execute a goal concurrently as a separate task. this paper describes a method for estimating the granularity of a goal at compile time. the runtime overhead associated with our approach is usually quite small, and the performance improvements resulting from the incorporation of grainsize control can be quite good. this is shown by means of experimental results.
interprocedural may-alias analysis for pointers: beyond -limiting. existing methods for alias analysis of recursive pointer data structures are based on two approximation techniques: k-limiting, and store-based (or equivalently location or region-based) approximations, which blur distinction between elements of recursive data structures. although notable progress in inter-procedural alias analysis has been recently accomplished, very little progress in the precision of analysis of recursive pointer data structures has been seen since the inception of these approximation techniques by jones and muchnick a decade ago. as a result, optimizing, verifying and parallelizing programs with pointers has remained difficult. we present a new parametric framework for analyzing recursive pointer data structures which can express a new natural class of alias information not accessible to existing methods. the key idea is to represent alias information by pairs of symbolic access paths which are qualified by symbolic descriptions of the positions for which the alias pair holds. based on this result, we present an algorithm for interprocedural may-alias analysis with pointers which on numerous examples that occur in practice is much more precise than recently published algorithms [cwz90, he90, lr92, cbc93].
safecode: enforcing alias analysis for weakly typed languages. static analysis of programs in weakly typed languages such as c and c++ is generally not sound because of possible memory errors due to dangling pointer references, uninitialized pointers, and array bounds overflow. we describe a compilation strategy for standard c programs that guarantees that aggressive interprocedural pointer analysis (or less precise ones), a call graph, and type information for a subset of memory, are never invalidated by any possible memory errors. we formalize our approach as a new type system with the necessary run-time checks in operational semantics and prove the correctness of our approach for a subset of c. our semantics provide the foundation for other sophisticated static analyses to be applied to c programs with a guarantee of soundness. our work builds on a previously published transformation called automatic pool allocation to ensure that hard-to-detect memory errors (dangling pointer references and certain array bounds errors) cannot invalidate the call graph, points-to information or type information. the key insight behind our approach is that pool allocation can be used to create a run-time partitioning of memory that matches the compile-time memory partitioning in a points-to graph, and efficient checks can be used to isolate the run-time partitions. furthermore, we show that the sound analysis information enables static checking techniques that eliminate many run-time checks. our approach requires no source code changes, allows memory to be managedexplicitly, and does not use meta-data on pointers or individual tag bits for memory. using several benchmark s and system codes, we show experimentally that the run-time overheads are low (less than 10% in nearly all cases and 30% in the worst case we have seen).we also show the effectiveness of static analyses in eliminating run-time checks.
improving cache performance in dynamic applications through data and computation reorganization at run time. with the rapid improvement of processor speed, performance of the memory hierarchy has become the principal bottleneck for most applications. a number of compiler transformations have been developed to improve data reuse in cache and registers, thus reducing the total number of direct memory accesses in a program. until now, however, most data reuse transformations have been static---applied only at compile time. as a result, these transformations cannot be used to optimize irregular and dynamic applications, in which the data layout and data access patterns remain unknown until run time and may even change during the computation.in this paper, we explore ways to achieve better data reuse in irregular and dynamic applications by building on the inspector-executor method used by saltz for run-time parallelization. in particular, we present and evaluate a dynamic approach for improving both computation and data locality in irregular programs. our results demonstrate that run-time program transformations can substantially improve computation and data locality and, despite the complexity and cost involved, a compiler can automate such transformations, eliminating much of the associated run-time overhead.
predicting whole-program locality through reuse distance analysis. profiling can accurately analyze program behavior for select data inputs. we show that profiling can also predict program locality for inputs other than profiled ones. here locality is defined by the distance of data reuse. studying whole-program data reuse may reveal global patterns not apparent in short-distance reuses or local control flow. however, the analysis must meet two requirements to be useful. the first is efficiency. it needs to analyze all accesses to all data elements in full-size benchmarks and to measure distance of any length and in any required precision. the second is predication. based on a few training runs, it needs to classify patterns as regular and irregular and, for regular ones, it should predict their (changing) behavior for other inputs. in this paper, we show that these goals are attainable through three techniques: approximate analysis of reuse distance (originally called lru stack distance), pattern recognition, and distance-based sampling. when tested on 15 integer and floating-point programs from spec and other benchmark suites, our techniques predict with on average 94% accuracy for data inputs up to hundreds times larger than the training inputs. based on these results, the paper discusses possible uses of this analysis.
dynamic feedback: an effective technique for adaptive computing. this paper presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environments. a compiler that uses dynamic feedback produces several different versions of the same source code; each version uses a different optimization policy. the generated code alternately performs sampling phases and production phases. each sampling phase measures the overhead of each version in the current environment. each production phase uses the version with the least overhead in the previous sampling phase. the computation periodically resamples to adjust dynamically to changes in the environment.we have implemented dynamic feedback in the context of a parallelizing compiler for object-based programs. the generated code uses dynamic feedback to automatically choose the best synchronization optimization policy. our experimental results show that the synchronization optimization policy has a significant impact on the overall performance of the computation, that the best policy varies from program to program, that the compiler is unable to statically choose the best policy, and that dynamic feedback enables the generated code to exhibit performance that is comparable to that of code that has been manually tuned to use the best policy. we have also performed a theoretical analysis which provides, under certain assumptions, a guaranteed optimality bound for dynamic feedback relative to a hypothetical (and unrealizable) optimal algorithm that uses the best policy at every point during the execution.
compiler support for garbage collection in a statically typed language. we consider the problem of supporting compacting garbage collection in the presence of modern compiler optimizations. since our collector may move any heap object, it must accurately locate, follow, and update all pointers and values derived from pointers. to assist the collector, we extend the compiler to emit tables describing live pointers, and values derived from pointers, at each program location where collection may occur. significant results include identification of a number of problems posed by optimizations, solutions to those problems, a working compiler, and experimental data concerning table sizes, table compression, and time overhead of decoding tables during collection. while gc support can affect the code produced, our sample programs show no significant changes, the table sizes are a modest fraction of the size of the optimized code, and stack tracing is a small fraction of total gc time. since the compiler enhancements are also modest, we conclude that the approach is practical.
type-based alias analysis. this paper evaluates three alias analyses based on programming language types. the first analysis uses type compatibility to determine aliases. the second extends the first by using additional high-level information such as field names. the third extends the second with a flow-insensitive analysis. although other researchers suggests using types to disambiguate memory references, none evaluates its effectiveness. we perform both static and dynamic evaluations of type-based alias analyses for modula-3, a statically-typed type-safe language. the static analysis reveals that type compatibility alone yields a very imprecise alias analysis, but the other two analyses significantly improve alias precision. we use redundant load elimination (rle) to demonstrate the effectiveness of the three alias algorithms in terms of the opportunities for optimization, the impact on simulated execution times, and to compute an upper bound on what a perfect alias analysis would yield. we show modest dynamic improvements for (rle), and more surprisingly, that on average our alias analysis is within 2.5% of a perfect alias analysis with respect to rle on 8 modula-3 programs. these results illustrate that to explore thoroughly the effectiveness of alias analyses, researchers need static, dynamic, and upper-bound analysis. in addition, we show that for type-safe languages like modula-3 and java, a fast and simple alias analysis may be sufficient for many applications.
automatic inline allocation of objects. object-oriented languages like java and smalltalk provide a uniform object model that simplifies programming by providing a consistent, abstract model of object behavior. but direct implementations introduce overhead, removal of which requires aggressive implementation techniques (e.g. type inference, function specialization); in this paper, we introduce object inlining, an optimization that automatically inline allocates objects within containers (as is done by hand in c++) within a uniform model. we present our technique, which includes novel program analyses that track how inlinable objects are used throughout the program. we evaluated object inlining on several object-oriented benchmarks. it produces performance up to three times as fast as a dynamic model without inlining and roughly equal to that of manually-inlined codes.
an automatic object inlining optimization and its evaluation. automatic object inlining [19, 20] transforms heap data structures by fusing parent and child objects together. it can improve runtime by reducing object allocation and pointer dereference costs. we report continuing work studying object inlining optimizations. in particular, we present a new semantic derivation of the correctness conditions for object inlining, and program analysis which extends our previous work. and we present an object inlining transformation, focusing on a new algorithm which optimizes class field layout to minimize code expansion. finally, we detail a fuller evaluation on eleven programs and libraries (including xpdf, the 25,000 line portable document format (pdf) file browser) that utilizes hardware measures of impact on the memory system. we show that our analysis scales effectively to large programs, finding many inlinable fields (45 in xpdf) at acceptable cost, and we show that, on some programs, it finds nearly all fields for which object inlining is correct, and averages 40% of such fields across our benchmarks. we implement our analyses in an advanced analysis infrastructure, and we show that, compared to traditional 1-cfa, that infrastructure provides better results and lower and more scalable cost. across all programs, analysis identified about 30% of objects as inlinable on average. our transformation increases code size by only 20% while inlining this 30% of fields. inlining these objects eliminated on average 28% of field reads, 58% of object creations, 12% of all loads. further, the optimized programs have significantly improved memory reference behavior, producing 25% fewer l1 data cache misses and 25% fewer read stalls. on average the runtime improved by 14%.
a generational on-the-fly garbage collector for java. an on-the-fly garbage collector does not stop the program threads to perform the collection. instead, the collector executes in a separate thread (or process) in parallel to the program. on-the-fly collectors are useful for multi-threaded applications running on multiprocessor servers, where it is important to fully utilize all processors and provide even response time, especially for systems for which stopping the threads is a costly operation. in this work, we report on the incorporation of generations into an on-the-fly garbage collector. the incorporation is non-trivial since an on-the-fly collector avoids explicit synchronization with the program threads. to the best of our knowledge, such an incorporation has not been tried before. we have implemented the collector for a prototype java virtual machine on aix, and measured its performance on a 4-way multiprocessor. as for other generational collectors, an on-the-fly generational collector has the potential for reducing the overall running time and working set of an application by concentrating collection efforts on the young objects. however, in contrast to other generational collectors, on-the-fly collectors do not move the objects; thus, there is no segregation between the old and the young objects. furthermore, on-the-fly collectors do not stop the threads, so there is no extra benefit for the short pauses obtained by generational collection. nevertheless, comparing our on-the-fly collector with and without generations, it turns out that the generational collector performs better for most applications. the best reduction in overall running time for the benchmarks we measured was 25%. however, there were some benchmarks for which it had no effect and one for which the overall running time increased by 4%.
cssv: towards a realistic tool for statically detecting all buffer overflows in c. erroneous string manipulations are a major source of software defects in c programs yielding vulnerabilities which are exploited by software viruses. we present c string static verifyer (cssv), a tool that statically uncovers all string manipulation errors. being a conservative tool, it reports all such errors at the expense of sometimes generating false alarms. fortunately, only a small number of false alarms are reported, thereby proving that statically reducing software vulnerability is achievable. cssv handles large programs by analyzing each procedure separately. to this end procedure contracts are allowed which are verified by the tool.we implemented a cssv prototype and used it to verify the absence of errors in real code from eads airbus. when applied to another commonly used string intensive application, cssv uncovered real bugs with very few false alarms.
a cost-driven compilation framework for speculative parallelization of sequential programs. the emerging hardware support for thread-level speculation opens new opportunities to parallelize sequential programs beyond the traditional limits. by speculating that many data dependences are unlikely during runtime, consecutive iterations of a sequential loop can be executed speculatively in parallel. runtime parallelism is obtained when the speculation is correct. to take full advantage of this new execution model, a program needs to be programmed or compiled in such a way that it exhibits high degree of speculative thread-level parallelism. we propose a comprehensive cost-driven compilation framework to perform speculative parallelization. based on a misspeculation cost model, the compiler aggressively transforms loops into optimal speculative parallel loops and selects only those loops whose speculative parallel execution is likely to improve program performance. the framework also supports and uses enabling techniques such as loop unrolling, software value prediction and dependence profiling to expose more speculative parallelism. the proposed framework was implemented on the orc compiler. our evaluation showed that the cost-driven speculative parallelization was effective. our compiler was able to generate good speculative parallel loops in ten spec2000int benchmarks, which currently achieve an average 8% speedup. we anticipate an average 15.6% speedup when all enabling techniques are in place.