waashk/dblp huggingface dataset:
dynamo: a transparent dynamic optimization system. we describe the design and implementation of dynamo, a software dynamic optimization system that is capable of transparently improving the performance of a native instruction stream as it executes on the processor. the input native instruction stream to dynamo can be dynamically generated (by a jit for example), or it can come from the execution of a statically compiled native binary. this paper evaluates the dynamo system in the latter, more challenging situation, in order to emphasize the limits, rather than the potential, of the system. our experiments demonstrate that even statically optimized native binaries can be accelerated dynamo, and often by a significant degree. for example, the average performance of -o optimized specint95 benchmark binaries created by the hp product c compiler is improved to a level comparable to their -o4 optimized version running without dynamo. dynamo achieves this by focusing its efforts on optimization opportunities that tend to manifest only at runtime, and hence opportunities that might be difficult for a static compiler to exploit. dynamo's operation is transparent in the sense that it does not depend on any user annotations or binary instrumentation, and does not require multiple runs, or any special compiler, operating system or hardware support. the dynamo prototype presented here is a realistic implementation running on an hp pa-8000 workstation under the hpux 10.20 operating system.
shared memory programming for large scale machines. this paper describes the design and implementation of a scalable run-time system and an optimizing compiler for unified parallel c (upc). an experimental evaluation on bluegene/l®, a distributed-memory machine, demonstrates that the combination of the compiler with the runtime system produces programs with performance comparable to that of efficient mpi programs and good performance scalability up to hundreds of thousands of processors.our runtime system design solves the problem of maintaining shared object consistency efficiently in a distributed memory machine. our compiler infrastructure simplifies the code generated for parallel loops in upc through the elimination of affinity tests, eliminates several levels of indirection for accesses to segments of shared arrays that the compiler can prove to be local, and implements remote update operations through a lower-cost asynchronous message. the performance evaluation uses three well-known benchmarks --- hpc randomaccess, hpc stream and nas cg --- to obtain scaling and absolute performance numbers for these benchmarks on up to 131072 processors, the full bluegene/l machine. these results were used to win the hpc challenge competition at sc05 in seattle wa, demonstrating that pgas languages support both productivity and performance.
composing security policies with polymer. we introduce a language and system that supports definition and composition of complex run-time security policies for java applications. our policies are comprised of two sorts of methods. the first is query methods that are called whenever an untrusted application tries to execute a security-sensitive action. a query method returns a suggestion indicating how the security-sensitive action should be handled. the second sort of methods are those that perform state updates as the policy's suggestions are followed.the structure of our policies facilitates composition, as policies can query other policies for suggestions. in order to give programmers control over policy composition, we have designed the system so that policies, suggestions, and application events are all first-class objects that a higher-order policy may manipulate. we show how to use these programming features by developing a library of policy combinators.our system is fully implemented, and we have defined a formal semantics for an idealized subset of the language containing all of the key features. we demonstrate the effectiveness of our system by implementing a large-scale security policy for an email client.
a portable global optimizer and linker. to reduce complexity and simplify their implementation, most compilers are organized as a set of passes or phases. each phase performs a particular piece of the compilation process. in an optimizing compiler, the assignment of function and order of application of the phases is a critical part of the design. a particularly difficult problem is the arrangement of the code generation and optimization phases so as to avoid phase ordering problems caused by the interaction of the phases. in this paper, we discuss the implementation of a compiler/linker that has been designed to avoid these problems. the key aspect of this design is that the synthesis phases of the compiler and the system linker share the same intermediate program representation. this results in two benefits. it permits the synthesis phases of the compiler to be performed in any order and repeatedly, thus eliminating potential phase ordering problems. second, it permits code selection to be invoked at any point during the synthesis phases as well as at link time. the ability to perform code selection at link time presents many opportunities for additional optimizations. measurements about the effectiveness of using this approach in a c compiler on two different machines are presented.
inducing heuristics to decide whether to schedule. instruction scheduling is a compiler optimization that can improve program speed, sometimes by 10% or more, but it can also be expensive. furthermore, time spent optimizing is more important in a java just-in-time (jit) compiler than in a traditional one because a jit compiles code at run time, adding to the running time of the program. we found that, on any given block of code, instruction scheduling often does not produce significant benefit and sometimes degrades speed. thus, we hoped that we could focus scheduling effort on those blocks that benefit from it.using supervised learning we induced heuristics to predict which blocks benefit from scheduling. the induced function chooses, for each block, between list scheduling and not scheduling the block at all. using the induced function we obtained over 90% of the improvement of scheduling every block but with less than 25% of the scheduling effort. when used in combination with profile-based adaptive optimization, the induced function remains effective but gives a smaller reduction in scheduling effort. deciding when to optimize, and which optimization(s) to apply, is an important open problem area in compiler research. we show that supervised learning solves one of these problems well.
diehard: probabilistic memory safety for unsafe languages. applications written in unsafe languages like c and c++ are vulnerable to memory errors such as buffer overflows, dangling pointers, and reads of uninitialized data. such errors can lead to program crashes, security vulnerabilities, and unpredictable behavior. we present diehard, a runtime system that tolerates these errors while probabilistically maintaining soundness. diehard uses randomization and replication to achieve probabilistic memory safety by approximating an infinite-sized heap. diehard's memory manager randomizes the location of objects in a heap that is at least twice as large as required. this algorithm prevents heap corruption and provides a probabilistic guarantee of avoiding memory errors. for additional safety, diehard can operate in a replicated mode where multiple replicas of the same application are run simultaneously. by initializing each replica with a different random seed and requiring agreement on output, the replicated version of die-hard increases the likelihood of correct execution because errors are unlikely to have the same effect across all replicas. we present analytical and experimental results that show diehard's resilience to a wide range of memory errors, including a heap-based buffer overflow in an actual application.
global communication analysis and optimization. reducing communication cost is crucial to achieving good performance on scalable parallel machines. this paper presents a new compiler algorithm for global analysis and optimization of communication in data-parallel programs. our algorithm is distinct from existing approaches in that rather than handling loop-nests and array references one by one, it considers all communication in a procedure and their interactions under different placements before making a final decision on the placement of any communication. it exploits the flexibility resulting from this advanced analysis to eliminate redundancy, reduce the number of messages, and reduce contention for cache and communication buffers, all in a unified framework. in contrast, single loop-nest analysis often retains redundant communication, and more aggressive dataflow analysis on array sections can generate too many messages or cache and buffer contention. the algorithm has been implemented in the ibm phpf compiler for high performance fortran. during compilation, the number of messages per processor goes down by as much as a factor of nine for some hpf programs. we present performance results for the ibm sp2 and a network of sparc workstations (now) connected by a myrinet switch. in many cases, the communication cost is reduced by a factor of two.
spill code minimization via interference region spilling. many optimizing compilers perform global register allocation using a chaitin-style graph coloring algorithm. live ranges that cannot be allocated to registers are spilled to memory. the amount of code required to spill the live range depends on the spilling heuristic used. chaitin's spilling heuristic offers some guidance in reducing the amount of spill code produced. however, this heuristic does not allow the partial spilling of live ranges and the reduction in spill code is limited to a local level. in this paper, we present a global technique called interference region spilling that improves the spilling granularity of any local spilling heuristic. our technique works above the local spilling heuristic, limiting the normal insertion of spill code to a portion of each spilled live range. by partially spilling live ranges, we can achieve large reductions in dynamically executed spill code; up to 75% in some cases and an average of 33.6% across the benchmarks tested.
customization: optimizing compiler technology for self, a dynamically-typed object-oriented programming language. dynamically-typed object-oriented languages please programmers, but their lack of static type information penalizes performance. our new implementation techniques extract static type information from declaration-free programs. our system compiles several copies of a given procedure, each customized for one receiver type, so that the type of the receiver is bound at compile time. the compiler predicts types that are statically unknown but likely, and inserts run-time type tests to verify its predictions. it splits calls, compiling a copy on each control path, optimized to the specific types on that path. coupling these new techniques with compile-time message lookup, aggressive procedure inlining, and traditional optimizations has doubled the performance of dynamically-typed object-oriented languages.
points-to analysis using bdds. this paper reports on a new approach to solving a subset-based points-to analysis for java using binary decision diagrams (bdds). in the model checking community, bdds have been shown very effective for representing large sets and solving very large verification problems. our work shows that bdds can also be very effective for developing a points-to analysis that is simple to implement and that scales well, in both space and time, to large programs.the paper first introduces bdds and operations on bdds using some simple points-to examples. then, a complete subset-based points-to algorithm is presented, expressed completely using bdds and bdd operations. this algorithm is then refined by finding appropriate variable orderings and by making the algorithm propagate sets incrementally, in order to arrive at a very efficient algorithm. experimental results are given to justify the choice of variable ordering, to demonstrate the improvement due to incrementalization, and to compare the performance of the bdd-based solver to an efficient hand-coded graph-based solver. finally, based on the results of the bdd-based solver, a variety of bdd-based queries are presented, including the points-to query.
making context-sensitive points-to analysis with heap cloning practical for the real world. context-sensitive pointer analysis algorithms with full "heapcloning" are powerful but are widely considered to be too expensive to include in production compilers. this paper shows, for the first time, that a context-sensitive, field-sensitive algorithm with fullheap cloning (by acyclic call paths) can indeed be both scalable and extremely fast in practice. overall, the algorithm is able to analyze programs in the range of 100k-200k lines of c code in 1-3 seconds,takes less than 5% of the time it takes for gcc to compile the code (which includes no whole-program analysis), and scales well across five orders of magnitude of code size. it is also able to analyze the linux kernel (about 355k linesof code) in 3.1 seconds. the paper describes the major algorithmic and engineering design choices that are required to achieve these results, including (a) using flow-insensitive and unification-basedanalysis, which are essential to avoid exponential behavior in practice;(b) sacrificing context-sensitivity within strongly connected components of the call graph; and (c) carefully eliminating several kinds of o(n2) behaviors (largely without affecting precision). the techniques used for (b) and (c) eliminated several major bottlenecks to scalability, and both are generalizable to other context-sensitive algorithms. we show that the engineering choices collectively reduce analysis time by factors of up to 10x-15xin our larger programs, and have found that the savings grow strongly with program size. finally, we briefly summarize results demonstrating the precision of the analysis.
iterative type analysis and extended message splitting: optimizing dynamically-typed object-oriented programs. object-oriented languages have suffered from poor performance caused by frequent and slow dynamically-bound procedure calls. the best way to speed up a procedure call is to compile it out, but dynamic binding of object-oriented procedure calls without static receiver type information precludes inlining. iterative type analysis and extended message splitting are new compilation techniques that extract much of the necessary type information and make it possible to hoist run-time type tests out of loops. our system compiles code on-the-fly that is customized to the actual data types used by a running program. the compiler constructs a control flow graph annotated with type information by simultaneously performing type analysis and inlining. extended message splitting preserves type information that would otherwise be lost by a control-flow merge by duplicating all the code between the merge and the place that uses the information. iterative type analysis computes the types of variables used in a loop by repeatedly recompiling the loop until the computed types reach a fix-point. together these two techniques enable our self compiler to split off a copy of an entire loop, optimized for the common-case types. by the time our self compiler generates code for the graph, it has eliminated many dynamically-dispatched procedure calls and type tests. the resulting machine code is twice as fast as that generated by the previous self compiler, four times faster than parcplace systems smalltalk-80,* the fastest commercially available dynamically-typed object-oriented language implementation, and nearly half the speed of optimized c. iterative type analysis and extended message splitting have cut the performance penalty for dynamically-typed object-oriented languages in half.
profile-guided proactive garbage collection for locality optimization. many applications written in garbage collected languages have large dynamic working sets and poor data locality. we present a new system for continuously improving program data locality at run time with low overhead. our system proactively reorganizes the heap by leveraging the garbage collector and uses profile information collected through a low-overhead mechanism to guide the reorganization at run time. the key contributions include making a case that garbage collection should be viewed as a proactive technique for improving data locality by triggering garbage collection for locality optimization independently of normal garbage collection for space, combining page and cache locality optimization in the same system, and demonstrating that sampling provides sufficiently detailed data access information to guide both page and cache locality optimization with low runtime overhead. we present experimental results obtained by modifying a commercial, state-of-the-art garbage collector to support our claims. independently triggering garbage collection for locality optimization significantly improved optimizations benefits. combining page and cache locality optimizations in the same system provided larger average execution time improvements (17%) than either alone (page 8%, cache 7%). finally, using sampling limited profiling overhead to less than 3%, on average.
data distribution support on distributed shared memory multiprocessors. cache-coherent multiprocessors with distributed shared memory are becoming increasingly popular for parallel computing. however, obtaining high performance on these machines mquires that an application execute with good data locality. in addition to making efiective use of caches, it is often necessary to distribute data structures across the local memories of the processing nodes, thereby reducing the latency of cache misses.we have designed a set of abstractions for performing data distribution in the context of explicitly parallel programs and implemented them within the sgi mipspro compiler system. our system incorporates many unique features to enhance both programmability and performance. we address the former by providing a very simple programmming model with extensive support for error detection. regarding performance, we carefully design the user abstractions with the underlying compiler optimizations in mind, we incorporate several optimization techniques to generate efficient code for accessing distributed data, and we provide a tight integration of these techniques with other optimizations within the compiler our initial experience suggests that the directives are easy to use and can yield substantial performance gains, in some cases by as much as a factor of 3 over the same codes without distribution.
exact analysis of the cache behavior of nested loops. we develop from first principles an exact model of the behavior of loop nests executing in a memory hicrarchy, by using a nontraditional classification of misses that has the key property of composability. we use presburger formulas to express various kinds of misses as well as the state of the cache at the end of the loop nest. we use existing tools to simplify these formulas and to count cache misses. the model is powerful enough to handle imperfect loop nests and various flavors of non-linear array layouts based on bit interleaving of array indices. we also indicate how to handle modest levels of associativity, and how to perform limited symbolic analysis of cache behavior. the complexity of the formulas relates to the static structure of the loop nest rather than to its dynamic trip count, allowing our model to gain efficiency in counting cache misses by exploiting repetitive patterns of cache behavior. validation against cache simulation confirms the exactness of our formulation. our method can serve as the basis for a static performance predictor to guide program and data transformations to improve performance.
prototyping fortran-90 compilers for massively parallel machines. massively parallel architectures, and the languages used to program them, are among both the most difficult and the most rapidly-changing subjects for compilation. this has created a demand for new compiler prototyping technologies that allow novel style of compilation and optimization to be tested in a reasonable amount of time. using formal specification techniques, we have produced a data-parallel fortran-90 subset compiler for thinking machines' connection machine/2 and connection machine/5. the prototype produces code from initial fortran-90 benchmarks demonstrating sustained performance superior to hand-coded lisp and competitive with thinking machines' cm fortran compiler. this paper presents some new specification techniques necessary to construct competitive, easily retargetable prototype compilers.
reducing noc energy consumption through compiler-directed channel voltage scaling. while scalable noc (network-on-chip) based communication architectures have clear advantages over long point-to-point communication channels, their power consumption can be very high. in contrast to most of the existing hardware-based efforts on noc power optimization, this paper proposes a compiler-directed approach where the compiler decides the appropriate voltage/frequency levels to be used for each communication channel in the noc. our approach builds and operates on a novel graph based representation of a parallel program and has been implemented within an optimizing compiler and tested using 12 embedded benchmarks. our experiments indicate that the proposed approach behaves better - from both performance and power perspectives - than a hardwarebased scheme and the energy savings it achieves are very close to the savings that could be obtained from an optimal, but hypothetical voltage/frequency scaling scheme.
shangri-la: achieving high performance from compiled network applications while enabling ease of programming. programming network processors is challenging. to sustain high line rates, network processors have extremely tight memory access and instruction budgets. achieving desired performance has traditionally required hand-coded assembly. researchers have recently proposed high-level programming languages for packet processing, but the challenges of compiling these languages into code that is competitive with hand-tuned assembly remain unanswered.this paper describes the shangri-la compiler, which accepts a packet program written in a c-like high-level language and applies scalar and specialized optimizations to generate a highly optimized binary. hot code paths identified by profiling are mapped across processing elements to maximize processor utilization. since our compilation target has no hardware caches, software-controlled caches are generated for frequently accessed application data structures. packet handling optimizations significantly reduce per-packet memory access and instruction counts. finally, a custom stack model maps stack frames to the fastest levels of the target processor's heterogeneous memory hierarchy.binaries generated by the compiler were evaluated on the intel ixp2400 network processor with eight packet processing cores and eight threads per core. our results show the importance of both traditional and specialized optimization techniques for achieving the maximum forwarding rates on three network applications, l3-switch, mpls and firewall.