waashk/dblp huggingface dataset:
balancing register allocation across threads for a multithreaded network processor. modern network processors employ multi-threading to allow concurrency amongst multiple packet processing tasks. we studied the properties of applications running on the network processors and observed that their imbalanced register requirements across different threads at different program points could lead to poor performance. many times application needs demand some threads to be more performance critical than others and thus by controlling the register allocation across threads one could impact the performance of the threads and get the desired performance properties for concurrent threads. this prompts our work.our register allocator aims to distribute available registers to different threads according to their needs. the compiler analyzes the register needs of each thread both at the point of a context switch as well as internally. compiler then designates some registers as shared and some as private to each thread. shared registers are allocated across all threads explicitly by the compiler. values that are live across a context switch can not be kept in shared registers due to safety reasons; thus, only those live ranges that are internal to the context switch can be safely allocated to shared registers. spill can cause a context switch. and thus, the problems of context switch and allocation are closely coupled and we propose a solution to this problem. the proposed interference graphs (gig,big,iig) distinguish variables that must use a thread's private registers from those that can use shared registers. we first estimate the register requirement bounds, then reduce from the upper bound gradually to achieve a good register balance among threads. to reduce the register needs, move insertions are inserted at program points that split the live ranges or the nodes on the interference graph. we show that the lower bound is reachable via live range splitting and is adequate for our benchmark programs for simultaneously assigning them on different threads. as our objective, the number of move instructions is minimized.empirical results show that the compiler is able to effectively control the register allocation across threads by maximizing the number of shared registers. speed-up for performance critical threads ranges from 18 to 24% whereas degradation for performance of non-critical threads ranges only from 1 to 4%.
differential register allocation. micro-architecture designers are very cautious about expanding the number of architected registers (also the register field), because increasing the register field adds to the code size, raises i-cache and memory pressure, complicates processor pipeline. especially for low-end processors, encoding space could be extremely limited due to area and power considerations. on the other hand, the number of architected registers exposed to the compiler could directly affect the effectiveness of compiler analysis and optimization. for high performance computers, register pressure can be higher than the available registers in some regions, e.g. due to optimizations like aggressive function inlining, software pipelining etc. the compiler cannot effectively perform compilation and optimization if only a small number of registers are exposed through the isa. therefore, it is crucial that more architected registers are available at the compiler's disposal without expanding the code size significantly.in this paper, we look at a new register encoding scheme called differential encoding that allows more registers to be addressed in the operand field of instructions than the direct encoding currently being used. we show it can be implemented with very low overhead. based upon differential encoding, we apply it in several ways such that the extra architected registers can benefit the performance. three schemes are devised to integrate differential encoding with register allocation. we demonstrate that differential register allocation is helpful in improving the performance of both high-end and low-end processors. moreover, we can combine it with software pipelining to provide more registers and reduce spills.our results show that differential encoding significantly reduces the number of spills and speeds up program execution. for a low-end configuration, we achieve over 12% speedup while keeping code size almost unaffected. for optimization on loops, it significantly speeds up loops with high register pressure (over 70% speedup).
accurate, efficient, and adaptive calling context profiling. calling context profiles are used in many inter-procedural code optimizations and in overall program understanding. unfortunately, the collection of profile information is highly intrusive due to the high frequency of method calls in most applications. previously proposed calling-context profiling mechanisms consequently suffer from either low accuracy, high overhead, or both. we have developed a new approach for building the calling context tree at runtime, called adaptive bursting. by selectively inhibiting redundant profiling, this approach dramatically reduces overhead while preserving profile accuracy. we first demonstrate the drawbacks of previously proposed calling context profiling mechanisms. we show that a low-overhead solution using sampled stack-walking alone is less than 50% accurate, based on degree of overlap with a complete calling-context tree. we also show that a static bursting approach collects a highly accurate profile, but causes an unacceptable application slowdown. our adaptive solution achieves 85% degree of overlap and provides an 88% hot-edge coverage when using a 0.1 hot-edge threshold, while dramatically reducing overhead compared to the static bursting approach.
towards locating execution omission errors. execution omission errors are known to be difficult to locate using dynamic analysis. these errors lead to a failure at runtime because of the omission of execution of some statements that would have been executed if the program had no errors. since dynamic analysis is typically designed to focus on dynamic information arising from executed statements, and statements whose execution is omitted do not produce dynamic information, detection of execution omission errors becomes a challenging task. for example, while dynamic slices are very effective in capturing faulty code for other types of errors, they fail to capture faulty code in presence of execution omission errors. to address this issue relevant slices have been defined to consider certain static dependences (called potential dependences) in addition to dynamic dependences. however, due to the conservative nature of static analysis, overly large slices are produced. in this paper, we propose a fully dynamic solution to locating execution omission errors using dynamic slices. we introduce the notion of implicit dependences which are dependences that are normally invisible to dynamic slicing due to the omission of execution of some statements. we design a dynamic method that forces the execution of the omitted code by switching outcomes of relevant predicates such that those implicit dependences are exposed and become available for dynamic slicing. dynamic slices can be computed and effectively pruned to produce fault candidate sets containing the execution omission errors. we solve two main problems: verifying the existence of a single implicit dependence through predicate switching, and recovering the implicit dependences in a demand driven manner such that a small number of verifications are required before the root cause is captured. our experiments show that the proposed technique is highly effective in capturing execution omission errors.
type-preserving compilation for large-scale optimizing object-oriented compilers. type-preserving compilers translate well-typed source code, such as java or c#, into verifiable target code, such as typed assembly language or proof-carrying code. this paper presents the implementation of type-preserving compilation in a complex, large-scale optimizing compiler. compared to prior work, this implementation supports extensive optimizations, and it verifies a large portion of the interface between the compiler and the runtime system. this paper demonstrates the practicality of type-preserving compilation in complex optimizing compilers: the generated typed assembly language is only 2.3% slower than the base compiler's generated untyped assembly language, and the type-preserving compiler is 82.8% slower than the base compiler.
profile-driven energy reduction in network-on-chips. reducing energy consumption of a network-on-chip (noc) is a critical design goal, especially for power-constrained embedded systems.in response, prior research has proposed several circuit/architectural level mechanisms to reduce noc power consumption. this paper considers the problem from a different perspective and demonstrates that compiler analysis can be very helpful for enhancing the effectiveness of a hardware-based link power management mechanism by increasing the duration of communication links' idle periods. the proposed profile-based approach achieves its goal by maximizing the communication link reuse through compiler-directed, static message re-routing. that is, it clusters the required data communications into a small set of communication links at any given time, which increases the idle periods for the remaining communication links in the network. this helps hardware shut down more communication links and their corresponding buffers to reduce leakage power. the current experimental evaluation, with twelve data-intensive embedded applications, shows that the proposed profile-driven compiler approach reduces leakage energy by more than 35% (on average) as compared to a pure hardware-based link power management scheme.
xmem: type-safe, transparent, shared memory for cross-runtime communication and coordination. developers commonly build contemporary enterprise applications using type-safe, component-based platforms, such as j2ee, and architect them to comprise multiple tiers, such as a web container, application server, and database engine. administrators increasingly execute each tier in its own managed runtime environment (mre) to improve reliability and to manage system complexity through the fault containment and modularity offered by isolated mre instances. such isolation, however, necessitates expensive cross-tier communication based on protocols such as object serialization and remote procedure calls. administrators commonly co-locate communicating mres on a single host to reduce communication overhead and to better exploit increasing numbers of available processing cores. however, state-of-the-art mres offer no support for more efficient communication between co-located mres, while fast inter-process communication mechanisms, such as shared memory, are widely available as a standard operating system service on most modern platforms. to address this growing need, we present the design and implementation of xmem ? type-safe, transparent, shared memory support for co-located mres. xmem guarantees type-safety through coordinated, parallel, multi-process class loading and garbage collection. to avoid introducing any level of indirection, xmem manipulates virtual memory mapping. in addition, object sharing in xmem is fully transparent: shared objects are identical to local objects in terms of field access, synchronization, garbage collection, and method invocation, with the only difference being that sharedto-private pointers are disallowed. xmem facilitates easy integration and use by existing communication technologies and software systems, such as rmi, jndi, jdbc, serialization/xml, and network sockets. we have implemented xmem in the open-source, productionquality hotspot java virtual machine. our experimental evaluation, based on core communication technologies underlying j2ee, as well as using open-source server applications, indicates that xmem significantly improves throughput and response time by avoiding the overheads imposed by object serialization and network communication.
improved error reporting for software that uses black-box components. an error occurs when software cannot complete a requested action as a result of some problem with its input, configuration, or environment. a high-quality error report allows a user to understand and correct the problem. unfortunately, the quality of error reports has been decreasing as software becomes more complex and layered. end-users take the cryptic error messages given to them by programsand struggle to fix their problems using search engines and support websites. developers cannot improve their error messages when they receive an ambiguous or otherwise insufficient error indicator from a black-box software component. we introduce clarify, a system that improves error reporting by classifying application behavior. clarify uses minimally invasive monitoring to generate a behavior profile, which is a summary of the program's execution history. a machine learning classifier uses the behavior profile to classify the application's behavior, thereby enabling a more precise error report than the output of the application itself. we evaluate a prototype clarify system on ambiguous error messages generated by large, modern applications like gcc, la-tex, and the linux kernel. for a performance cost of less than 1% on user applications and 4.7% on the linux kernel, the proto type correctly disambiguates at least 85% of application behaviors that result in ambiguous error reports. this accuracy does not degrade significantly with more behaviors: a clarify classifier for 81 la-tex error messages is at most 2.5% less accurate than a classifier for 27 latex error messages. finally, we show that without any human effort to build a classifier, clarify can provide nearest-neighbor software support, where users who experience a problem are told about 5 other users who might have had the same problem. on average 2.3 of the 5 users that clarify identifies have experienced the same problem.
online optimizations driven by hardware performance monitoring. hardware performance monitors provide detailed direct feedback about application behavior and are an additional source of infor-mation that a compiler may use for optimization. a jit compiler is in a good position to make use of such information because it is running on the same platform as the user applications. as hardware platforms become more and more complex, it becomes more and more difficult to model their behavior. profile information that captures general program properties (like execution frequency of methods or basic blocks) may be useful, but does not capture sufficient information about the execution platform. machine-level performance data obtained from a hardware performance monitor can not only direct the compiler to those parts of the program that deserve its attention but also determine if an optimization step actually improved the performance of the application. this paper presents an infrastructure based on a dynamic compiler+runtime environment for java that incorporates machine-level information as an additional kind of feedback for the compiler and runtime environment. the low-overhead monitoring system provides fine-grained performance data that can be tracked back to individual java bytecode instructions. as an example, the paper presents results for object co-allocation in a generational garbage collector that optimizes spatial locality of objects on-line using measurements about cache misses. in the best case, the execution time is reduced by 14% and l1 cache misses by 28%.
sound, complete and scalable path-sensitive analysis. we present a new, precise technique for fully path- and context-sensitive program analysis. our technique exploits two observations: first, using quantified, recursive formulas, path- and context-sensitive conditions for many program properties can be expressed exactly. to compute a closed form solution to such recursive constraints, we differentiate between observable and unobservable variables, the latter of which are existentially quantified in our approach. using the insight that unobservable variables can be eliminated outside a certain scope, our technique computes satisfiability- and validity-preserving closed-form solutions to the original recursive constraints. we prove the solution is as precise as the original system for answering may and must queries as well as being small in practice, allowing our technique to scale to the entire linux kernel, a program with over 6 million lines of code.
automatic volume management for programmable microfluidics. microfluidics has enabled lab-on-a-chip technology to miniaturize and integrate biological and chemical analyses to a single chip comprising channels, valves, mixers, heaters, separators, and sensors. recent papers have proposed programmable labs-on-a-chip as an alternative to traditional application-specific chips to reduce design effort, time, and cost. while these previous papers provide the basic support for programmability, this paper identifies and addresses a practical issue, namely, fluid volume management. volume management addresses the problem that the use of a fluid depletes it and unless the given volume of a fluid is distributed carefully among all its uses, execution may run out of the fluid before all its uses are complete. additionally, fluid volumes should not overflow (i.e., exceed hardware capacity) or underflow (i.e., fall below hardware resolution). we show that the problem can be formulated as a linear programming problem (lp). because lp's complexity and slow execution times in practice may be a concern, we propose another approach, called dagsolve, which over-constrains the problem to achieve linear complexity while maintaining good solution quality. we also propose two optimizations, called cascading and static replication, to handle cases involving extreme mix ratios and numerous fluid uses which may defeat both lp and dagsolve. using some real-world assays, we show that our techniques produce good solutions while being faster than lp.
dataflow analysis for concurrent programs using datarace detection. dataflow analyses for concurrent programs differ from their single-threaded counterparts in that they must account for shared memory locations being overwritten by concurrent threads. existing dataflow analysis techniques for concurrent programs typically fall at either end of a spectrum: at one end, the analysis conservatively kills facts about all data that might possibly be shared by multiple threads; at the other end, a precise thread-interleaving analysis determines which data may be shared, and thus which dataflow facts must be invalidated. the former approach can suffer from imprecision, whereas the latter does not scale. we present radar, a framework that automatically converts a dataflow analysis for sequential programs into one that is correct for concurrent programs. radar uses a race detection engine to kill the dataflow facts, generated and propagated by the sequential analysis, that become invalid due to concurrent writes. our approach of factoring all reasoning about concurrency into a race detection engine yields two benefits. first, to obtain analyses for code using new concurrency constructs, one need only design a suitable race detection engine for the constructs. second, it gives analysis designers an easy way to tune the scalability and precision of the overall analysis by only modifying the race detection engine. we describe the radar framework and its implementation using a pre-existing race detection engine. we show how radar was used to generate a concurrent version of a null-pointer dereference analysis, and we analyze the result of running the generated concurrent analysis on several benchmarks.
efficient program execution indexing. execution indexing uniquely identifies a point in an execution. desirable execution indices reveal correlations between points in an execution and establish correspondence between points across multiple executions. therefore, execution indexing is essential for a wide variety of dynamic program analyses, for example, it can be used to organize program profiles; it can precisely identify the point in a re-execution that corresponds to a given point in an original execution and thus facilitate debugging or dynamic instrumentation. in this paper, we formally define the concept of execution index and propose an indexing scheme based on execution structure and program state. we present a highly optimized online implementation of the technique. we also perform a client study, which targets producing a failure inducing schedule for a data race by verifying the two alternative happens-before orderings of a racing pair. indexing is used to precisely locate corresponding points across multiple executions in the presence of non-determinism so that no heavyweight tracing/replay system is needed.
inferring locks for atomic sections. atomic sections are a recent and popular idiom to support the development of concurrent programs. updates performed within an atomic section should not be visible to other threads until the atomic section has been executed entirely. traditionally, atomic sections are supported through the use of optimistic concurrency, either using a transactional memory hardware, or an equivalent software emulation (stm). this paper explores automatically supporting atomic sections using pessimistic concurrency. we present a system that combines compiler and runtime techniques to automatically transform programs written with atomic sections into programs that only use locking primitives. to minimize contention in the transformed programs, our compiler chooses from several lock granularities, using fine-grain locks whenever it is possible. this paper formally presents our framework, shows that our compiler is sound (i.e., it protects all shared locations accessed within atomic sections), and reports experimental results.
a study of concurrent real-time garbage collectors. concurrent garbage collection is highly attractive for real-time systems, because offloading the collection effort from the executing threads allows faster response, allowing for extremely short deadlines at the microseconds level. concurrent collectors also offer much better scalability over incremental collectors. the main problem with concurrent real-time collectors is their complexity. the first concurrent real-time garbage collector that can support fine synchronization, stopless, has recently been presented by pizlo et al. in this paper, we propose two additional (and different) algorithms for concurrent real-time garbage collection: clover and chicken. both collectors obtain reduced complexity over the first collector stopless, but need to trade a benefit for it. we study the algorithmic strengths and weaknesses of clover and chicken and compare them to stopless. finally, we have implemented all three collectors on the bartok compiler and runtime for c# and we present measurements to compare their efficiency and responsiveness.
deriving linearizable fine-grained concurrent objects. practical and efficient algorithms for concurrent data structures are difficult to construct and modify. algorithms in the literature are often optimized for a specific setting, making it hard to separate the algorithmic insights from implementation details. the goal of this work is to systematically construct algorithms for a concurrent data structure starting from its sequential implementation. towards that goal, we follow a construction process that combines manual steps corresponding to high-level insights with automatic exploration of implementation details. to assist us in this process, we built a new tool called paraglider. the tool quickly explores large spaces of algorithms and uses bounded model checking to check linearizability of algorithms. starting from a sequential implementation and assisted by the tool, we present the steps that we used to derive various highly-concurrent algorithms. among these algorithms is a new fine-grained set data structure that provides a wait-free contains operation, and uses only the compare-and-swap (cas) primitive for synchronization.