waashk/dblp huggingface dataset:
software overhead in messaging layers: where does the time go? despite improvements in network interfaces and software messaging layers, software communication overhead still dominates the hardware routing cost in most systems. in this study, we identify the sources of this overhead by analyzing software costs of typical communication protocols built atop the active messages layer on the cm-5. we show that up to 50&ndash;70% of the software messaging costs are a direct consequence of the gap between specific network features such as arbitrary delivery order, finite buffering, and limited fault-handling, and the user communication requirements of in-order delivery, end-to-end flow control, and reliable transmission. however, virtually all of these costs can be eliminated if routing networks provide higher-level services such as in-order delivery, end-to-end flow control, and packet-level fault-tolerance. we conclude that significant cost reductions require changing the constraints on messaging layers: we propose designing networks and network interfaces which simplify or replace software for implementing user communication requirements.
using registers to optimize cross-domain call performance. this paper describes a new technique to improve the performance of cross-domain calls and returns in a capability-based computer system. using register optimization information obtained from the compiler, a trusted linker can minimize the number of registers that must be saved, restored, or cleared when changing from one protection domain to another. the size of the performance gain depends on the level of trust between the calling and called protection domains. the paper presents alternate implementations for an extended vax architecture and for a risc architecture and reports performance measurements done on a re-microprogrammed vax-11/730 processor.
a vliw architecture for a trace scheduling compiler. very long instruction word (vliw) architectures were promised to deliver far more than the factor of two or three that current architectures achieve from overlapped execution. using a new type of compiler which compacts ordinary sequential code into long instruction words, a vliw machine was expected to provide from ten to thirty times the performance of a more conventional machine built of the same implementation technology.multiflow computer, inc., has now built a vliw called the tracetm along with its companion trace schedulingtm compacting compiler. this new machine has fulfilled the performance promises that were made. using many fast functional units in parallel, this machine extends some of the basic reduced-instruction-set precepts: the architecture is load/store, the microarchitecture is exposed to the compiler, there is no microcode, and there is almost no hardware devoted to synchronization, arbitration, or interlocking of any kind (the compiler has sole responsibility for runtime resource usage).this paper discusses the design of this machine and presents some initial performance results.
effective null pointer check elimination utilizing hardware trap. we present a new algorithm for eliminating null pointer checks from programs written in java&trade;. our new algorithm is split into two phases. in the first phase, it moves null checks backward, and it is iterated for a few times with other optimizations to eliminate redundant null checks and maximize the effectiveness of other optimizations. in the second phase, it moves null checks forward and converts many null checks to hardware traps in order to minimize the execution cost of the remaining null checks. as a result, it eliminates many null checks effectively and exploits the maximum use of hardware traps. this algorithm has been implemented in the ibm cross-platform java just-in-time (jit) compiler. our experimental results show that our approach improves performance by up to 71% for jbytemark and up to 10% for specjvm98 over the previously known best algorithm. they also show that it increases jit compilation time by only 2.3%. although we implemented our algorithm for java, it is also applicable for other languages requiring null checking.
micro-optimization of floating point operations. this paper describes micro-optimization, a technique for reducing the operation count and time required to perform floating-point calculations. micro-optimization involves breaking floating-point operations into their constituent micro-operations and optimizing the resulting code. exposing micro-operations to the compiler creates many opportunities for optimization. redundant normalization operations can be eliminated or combined. also, scheduling micro-operations separately allows dependent operations to be partially overlapped. a prototype expression compiler has been written to evaluate a number of micro-optimizations. on a set of benchmark expressions operation count is reduced by 33% and execution time is reduced by 40%.
the effect of instruction set complexity on program size and memory performance. one potential disadvantage of a machine with a reduced instruction set is that object programs may be substantially larger than those for a machine with a richer, more complex instruction set. the main reason is that a small instruction set will require more instructions to implement the same function. in addition, the tendency of risc machines to use fixed length instructions with a few instruction formats also increases object program size. it has been conjectured that the resulting larger programs could adversely affect memory performance and bus traffic. in this paper we report the results of a set of experiments to isolate and determine the effect of instruction set complexity on cache memory performance and bus traffic. three high-level language compilers were constructed for machines with instruction sets of varying degrees of complexity. using a set of benchmark programs, we evaluated the effect of instruction set complexity had on program size. five of the programs were used to perform a set of trace-driven simulations to study each machine's cache and bus performance. while we found that the miss ratio is affected by object program size, it appears that this can be corrected by simplying increasing the size of the cache. our measurements of bus traffic, however, show that even with large caches, machines with simple instruction sets can expect substantially more main memory reads than machines with dense object programs.
a risc architecture for symbolic computation. the g-machine is a language-directed processor architecture designed to support graph reduction as a model of computation. it can carry out lazy evaluation of functional language programs and can evaluate programs in which logical variables are used. to support these language features, the abstract machine requires tagged memory and executes some rather complex instructions, such as to evaluate a function application.this paper explores an implementation of the g-machine as a high performance risc architecture. complex instructions can be represented by risc code without experiencing a large expansion of code volume. the instruction pipeline is discussed in some detail. the processor is intended to be integrated into a standard, 32-bit memory architecture. tagged memory is supported by aggregating data with tags in a cache.
overlapped loop support in the cydra 5. the cydratm 5 architecture adds unique support for overlapping successive iterations of a loop to a very long instruction word (vliw) base. this architecture allows highly parallel loop execution for a much larger class of loops than can be vectorized, without requiring the unrolling of loops usually used by compilers for vliw machines. this paper discusses the cydra 5 loop scheduling model, the special architectural features which support it, and the loop compilation techniques used to take full advantage of the architecture.
the effect of sharing on the cache and bus performance of parallel programs. bus bandwidth ultimately limits the performance, and therefore the scale, of bus-based, shared memory multiprocessors. previous studies have extrapolated from uniprocessor measurements and simulations to estimate the performance of these machines. in this study, we use traces of parallel programs to evaluate the cache and bus performance of shared memory multiprocessors, in which coherency is maintained by a write-invalidate protocol. in particular, we analyze the effect of sharing overhead on cache miss ratio and bus utilization. our studies show that parallel programs incur substantially higher miss ratios and bus utilization than comparable uniprocessor programs. the sharing component of these metrics proportionally increases with both cache and block size, and for some cache configurations determines both their magnitude and trend. the amount of overhead depends on the memory reference pattern to the shared data. programs that exhibit good per-processor-locality perform better than those with fine-grain-sharing. this suggests that parallel software writers and better compiler technology can improve program performance through better memory organization of shared data.
a message driven or-parallel machine. a message driven architecture for the execution of or-parallel logic languages is proposed. the computational model is based on well known compilation techniques for logic languages. we present first the multiple binding mechanism for the or-parallel prolog architecture and the corresponding or-parallel abstract machine is described. a scheduling algorithm which does not rely upon the availability of global data structures to direct the search for work is discussed. the message driven processor, the processing node of the parallel machine, is designed to interact with a shared global address space and to efficiently process messages from other processing nodes. we discuss some of the results obtained from a high level functional simulator of the message driven machine.
an adaptive, non-uniform cache structure for wire-delay dominated on-chip caches. growing wire delays will force substantive changes in the designs of large caches. traditional cache architectures assume that each level in the cache hierarchy has a single, uniform access time. increases in on-chip communication delays will make the hit time of large on-chip caches a function of a line's physical location within the cache. consequently, cache access times will become a continuum of latencies rather than a single discrete latency. this non-uniformity can be exploited to provide faster access to cache lines in the portions of the cache that reside closer to the processor. in this paper, we evaluate a series of cache designs that provides fast hits to multi-megabyte cache memories. we first propose physical designs for these non-uniform cache architectures (nucas). we extend these physical designs with logical policies that allow important data to migrate toward the processor within the same level of the cache. we show that, for multi-megabyte level-two caches, an adaptive, dynamic nuca design achieves 1.5 times the ipc of a uniform cache architecture of any size, outperforms the best static nuca scheme by 11%, outperforms the best three-level hierarchy--while using less silicon area--by 13%, and comes within 13% of an ideal minimal hit latency solution.
deconstructing storage arrays. we introduce shear, a user-level software tool that characterizes raid storage arrays. shear employs a set of controlled algorithms combined with statistical techniques to automatically determine the important properties of a raid system, including the number of disks, chunk size, level of redundancy, and layout scheme. we illustrate the correctness of shear by running it upon numerous simulated configurations, and then verify its real-world applicability by running shear on both software-based and hardware-based raid systems. finally, we demonstrate the utility of shear through three case studies. first, we show how shear can be used in a storage management environment to verify raid construction and detect failures. second, we demonstrate how shear can be used to extract detailed characteristics about the individual disks within an array. third, we show how an operating system can use shear to automatically tune its storage subsystems to specific raid configurations.
increasing web server throughput with network interface data caching. this paper introduces network interface data caching, a new technique to reduce local interconnect traffic on networking servers by caching frequently-requested content on a programmable network interface. the operating system on the host cpu determines which data to store in the cache and for which packets it should use data from the cache. to facilitate data reuse across multiple packets and connections, the cache only stores application-level response content (such as http data), with application-level and networking headers generated by the host cpu. network interface data caching can reduce pci traffic by up to 57% on a prototype implementation of a uniprocessor web server. this traffic reduction results in up to 31% performance improvement, leading to a peak server throughput of 1571 mb/s.
scalable selective re-execution for edge architectures. pipeline flushes are becoming increasingly expensive in modern microprocessors with large instruction windows and deep pipelines. selective re-execution is a technique that can reduce the penalty of mis-speculations by re-executing only instructions affected by the mis-speculation, instead of all instructions. in this paper we introduce a new selective re-execution mechanism that exploits the properties of a dataflow-like explicit data graph execution (edge) architecture to support efficient mis-speculation recovery, while scaling to window sizes of thousands of instructions with high performance. this distributed selective re-execution (dsre) protocol permits multiple speculative waves of computation to be traversing a dataflow graph simultaneously, with a commit wave propagating behind them to ensure correct execution. we evaluate one application of this protocol to provide efficient recovery for load-store dependence speculation. unlike traditional dataflow architectures which resorted to single-assignment memory semantics, the dsre protocol combines dataflow execution with speculation to enable high performance and conventional sequential memory semantics. our experiments show that the dsre protocol results in an average 17% speedup over the best dependence predictor proposed to date, and obtains 82% of the performance possible with a perfect oracle directing the issue of loads.
design and evaluation of compiler algorithms for pre-execution. pre-execution is a promising latency tolerance technique that uses one or more helper threads running in spare hardware contexts ahead of the main computation to trigger long-latency memory operations early, hence absorbing their latency on behalf of the main computation. this paper investigates a source-to-source c compiler for extracting pre-execution thread code automatically, thus relieving the programmer or hardware from this onerous task. at the heart of our compiler are three algorithms. first, program slicing removes non-critical code for computing cache-missing memory references, reducing pre-execution overhead. second, prefetch conversion replaces blocking memory references with non-blocking prefetch instructions to minimize pre-execution thread stalls. finally, threading scheme selection chooses the best scheme for initiating pre-execution threads, speculatively parallelizing loops to generate thread-level parallelism when necessary for latency tolerance. we prototyped our algorithms using the stanford university intermediate format (suif) framework and a publicly available program slicer, called unravel [13], and we evaluated our compiler on a detailed architectural simulator of an smt processor. our results show compiler-based pre-execution improves the performance of 9 out of 13 applications, reducing execution time by 22.7%. across all 13 applications, our technique delivers an average speedup of 17.0%. these performance gains are achieved fully automatically on conventional smt hardware, with only minimal modifications to support pre-execution threads.
register allocation for free: the c machine stack cache. the bell labs c machine project is investigating computer architectures to support the c programming language.1 one of the goals is to match an efficient architecture to the language and the compiler technology available. measurements of different c programs show that roughly one out of every twenty instructions executed is either a procedure call or return.2 procedure call overhead is therefore a very important consideration in the overall machine design. a second and related area of primary concern in overall machine efficiency is the register allocation strategy. while use of additional registers can offer considerable improvement in execution times, adding registers usually has the adverse effects of increasing the procedure call overhead due to register saving and creating an undue burden on the compiler. in this paper we describe a piece of the c machine architecture which effectively eliminates the register allocation problem, and improves procedure calling by drastically reducing storage references required by traditional register saving. the technique can be generalized for other languages and architectures, though we will only directly address those issues involving the c language.
enabling trusted software integrity. preventing execution of unauthorized software on a given computer plays a pivotal role in system security. the key problem is that although a program at the beginning of its execution can be verified as authentic, while running, its execution flow can be redirected to externally injected malicious code using, for example, a buffer overflow exploit. existing techniques address this problem by trying to detect the intrusion at run-time or by formally verifying that the software is not prone to a particular attack.we take a radically different approach to this problem. we aim at intrusion prevention as the core technology for enabling secure computing systems. intrusion prevention systems force an adversary to solve a computationally hard task in order to create a binary that can be executed on a given machine. in this paper, we present an exemplary system--spef--a combination of architectural and compilation techniques that ensure software integrity at run-time. spef embeds encrypted, processor-specific constraints into each block of instructions at software installation time and then verifies their existence at run-time. thus, the processor can execute only properly installed programs, which makes installation the only system gate that needs to be protected. we have designed a spef prototype based on the arm instruction set and validated its impact on security and performance using the mediabench suite of applications.
evaluation of architectural support for global address-based communication in large-scale parallel machines. large-scale parallel machines are incorporating increasingly sophisticated architectural support for user-level messaging and global memory access. we provide a systematic evaluation of a broad spectrum of current design alternatives based on our implementations of a global address language on the thinking machines cm-5, intel paragon, meiko cs-2, cray t3d, and berkeley now. this evaluation includes a range of compilation strategies that make varying use of the network processor; each is optimized for the target architecture and the particular strategy. we analyze a family of interacting issues that determine the performance trade-offs in each implementation, quantify the resulting latency, overhead, and bandwidth of the global access operations, and demonstrate the effects on application performance.
programming language optimizations for modular router configurations. networking systems such as ensemble, the x-kernel, scout, and click achieve flexibility by building routers and other packet processors from modular components. unfortunately, component designs are often slower than purpose-built code, and routers in particular have stringent efficiency requirements. this paper addresses the efficiency problems of one component-based router, click, through optimization tools inspired in part by compiler optimization passes. this pragmatic approach can result in significant performance improvements; for example, the combination of three optimizations reduces the amount of cpu time click requires to process a packet in a simple ip router by 34%. we present several optimization tools, describe how those tools affected the design of click itself, and present detailed evaluations of click's performance with and without optimization.
the performance impact of flexibility in the stanford flash multiprocessor. a flexible communication mechanism is a desirable feature in multiprocessors because it allows support for multiple communication protocols, expands performance monitoring capabilities, and leads to a simpler design and debug process. in the stanford flash multiprocessor, flexibility is obtained by requiring all transactions in a node to pass through a programmable node controller, called magic. in this paper, we evaluate the performance costs of flexibility by comparing the performance of flash to that of an idealized hardwired machine on representative parallel applications and a multiprogramming workload. to measure the performance of flash, we use a detailed simulator of the flash and magic designs, together with the code sequences that implement the cache-coherence protocol. we find that for a range of optimized parallel applications the performance differences between the idealized machine and flash are small. for these programs, either the miss rates are small or the latency of the programmable protocol can be hidden behind the memory access time. for applications that incur a large number of remote misses or exhibit substantial hot-spotting, performance is poor for both machines, though the increased remote access latencies or the occupancy of magic lead to lower performance for the flexible design. in most cases, however, flash is only 2%&ndash;12% slower than the idealized machine.
overlapping execution with transfer using non-strict execution for mobile programs. in order to execute a program on a remote computer, it mustfirst be transferred over a network. this transmission incurs the over-head of network latency before execution can begin. this latency can vary greatly depending upon the size of the program., where it is located (e.g., on a local network or across the internet), and the bandwidth available to retrieve the program. existing technologies, like java, require that a jle be filly transferred before it can start executing. for large files and low bandwidth lines, this delay can be significant.in this paper we propose and evaluate a non-strict form of mobile program execution. a mobile program is any program that is transferred to a different machine and executed. the goal of nonstrict execution is to overlap execution with transfer; allowing the program to start executing as soon as possible. non-strict execution allows a procedure in the program to start executing as soon as its code and data have transferred. to enable this technology, we examine several techniques for rearranging procedures and reorganizing the data inside java classjles. our results show that nonstrict execution decreases the initial transfer delay between 31% and 56% on average, with an average reduction in overall execution time between 25% and 40%.