waashk/dblp huggingface dataset:
investigating optimal local memory performance. recent work has demonstrated that, cache space is often poorly utilized. however, no previous work has yet demonstrated upper bounds on what a cache or local memory could achieve when exploiting both spatial and temporal locality. belady's min algorithm does yield an upper bound, but exploits only temporal locality. in this article, we present an optimal replacement algorithm for local memory that exploits temporal locality and spatial locality simultaneously. this algorithm is an extension of belady's algorithm. we prove the optimality of this new algorithm with respect to minimizing misses, and we show experimentally that the algorithm produces nearly minimum memory traffic on the spec95 benchmarks. like belady's algorithm, our algorithm requires the entire program trace. it selects replacement victims and the number of words it fetches at once based on future accesses. many different spatial locality strategies can be implemented with this algorithm. with an optimal strategy, the algorithm yields an upper bound that enables us to evaluate alternative implementations to today's caches. we further demonstrate the utility of this algorithm as an analysis tool by evaluating several intermediate strategies between cache and optimal to highlight the limitations of the cache line paradigm using the spec95 benchmarks.
program optimization for instruction caches. this paper presents an optimization algorithm for reducing instruction cache misses. the algorithm uses profile information to reposition programs in memory so that a direct-mapped cache behaves much like an optimal cache with full associativity and full knowledge of the future. for best results, the cache should have a mechanism for excluding certain instructions designated by the compiler. this paper first presents a reduced form of the algorithm. this form is shown to produce an optimal miss rate for programs without conditionals and with a tree call graph, assuming basic blocks can be reordered at will. if conditionals are allowed, but there are no loops within conditionals, the algorithm does as well as an optimal cache for the worst case execution of the program consistent with the profile information. next, the algorithm is extended with heuristics for general programs. the effectiveness of these heuristics are demonstrated with empirical results for a set of 10 programs for various cache sizes. the improvement depends on cache size. for a 512 word cache, miss rates for a direct-mapped instruction cache are halved. for an 8k word cache, miss rates fall by over 75%. over a wide range of cache sizes the algorithm is as effective as increasing the cache size by a factor of 3 times. for 512 words, the algorithm generates only 32% more misses than an optimal cache. optimized programs on a direct-mapped cache have lower miss rates than unoptimized programs on set-associative caches of the same size.
firefly: a multiprocessor workstation. firefly is a shared-memory multiprocessor workstation that contains from one to seven microvax 78032 processors, each with a floating point unit and a sixteen kilobyte cache. the caches are coherent, so that all processors see a consistent view of main memory. a system may contain from four to sixteen megabytes of storage. input-output is done via a standard dec qbus. input-output devices are an ethernet controller, fixed disks, and a monochrome 1024 x 768 display with keyboard and mouse. optional hardware includes a high resolution color display and a controller for high capacity disks. figure 1 is a system block diagram.the firefly runs a software system that emulates the ultrix system call interface. it also supports medium- and coarse-grained multiprocessing through multiple threads of control in a single address space. communications are implemented uniformly through the use of remote procedure calls.this paper describes the goals, architecture, implementation and performance analysis of the firefly. it then presents some measurements of hardware performance, and discusses the degree to which src has been successful in producing software to take advantage of multiprocessing.
a quantitative analysis of loop nest locality. this paper analyzes and quantifies the locality characteristics of numerical loop nests in order to suggest future directions for architecture and software cache optimizations. since most programs spend the majority of their time in nests, the vast majority of cache optimization techniques target loop nests. in contrast, the locality characteristics that drive these optimizations are usually collected across the entire application rather than the nest level. indeed, researchers have studied numerical codes for so long that a number of commonly held assertions have emerged on their locality characteristics. in light of these assertions, we use the perfect benchmarks to take a new look at measuring locality on numerical codes based on references, loop nests, and program locality properties. our results show that several popular assertions are at best overstatements. for example, we find that temporal and spatial reuse have balanced roles within a loop nest and most reuse across nests and the entire program is temporal. these results are consistent with high hit rates, but go against the commonly held assumption that spatial reuse dominates. another result contrary to popular assumption is that misses within a nest are overwhelmingly conflict misses rather than capacity misses. capacity misses are a significant source of misses for the entire program, but mostly correspond to potential reuse between different loop nests. our locality measurements reveal important differences between loop nests and programs; refute some popular assertions; and provide new insights for the compiler writer and the architect.
the effectiveness of multiple hardware contexts. multithreaded processors are used to tolerate long memory latencies. by executing threads loaded in multiple hardware contexts, an otherwise idle processor can keep busy, thus increasing its utilization. however, the larger size of a multi-thread working set can have a negative effect on cache conflict misses. in this paper we evaluate the two phenomena together, examining their combined effect on execution time.the usefulness of multiple hardware contexts depends on: program data locality, cache organization and degree of multiprocessing. multiple hardware contexts are most effective on programs that have been optimized for data locality. for these programs, execution time dropped with increasing contexts, over widely varying architectures. with unoptimized applications, multiple contexts had limited value. the best performance was seen with only two contexts, and only on uniprocessors and small multiprocessors. the behavior of the unoptimized applications changed more noticeably with variations in cache associativity and cache hierarchy, unlike the optimized programs.as a mechanism for exploiting program parallelism, an additional processor is clearly better than another context. however, there were many configurations for which the addition of a few hardware contexts brought as much or greater performance than a larger multiprocessor with fewer than the optimal number of contexts.
guidelines for creating a debuggable processor. hardware without software is of little use. systems that ease the task of debugging software reduce cost and speed development. this paper presents guidelines for designing processors that ease debugging for real-time computer systems. special hardware can aid the debugging process by tracing execution and accesses to memory. such hardware requires access to signals that may not be readily available. other, less exotic hardware provides an interface to the programmer and other processors. the hardware and software of the debugging system should not alter the real-time characteristics of the system under test and should be able to operate on a field-grade processor. it is undesirable to require special versions of processor hardware and software for the debugging system.
exploiting dual data-memory banks in digital signal processors. over the past decade, digital signal processors (dsps) have emerged as the processors of choice for implementing embedded applications in high-volume consumer products. through their use of specialized hardware features and small chip areas, dsps provide the high performance necessary for embedded applications at the low costs demanded by the high-volume consumer market. one feature commonly found in dsps is the use of dual data-memory banks to double the memory system's bandwidth. when coupled with high-order data interleaving, dual memory banks provide the same bandwidth as more costly memory organizations such as a dual-ported memory. however, making effective use of dual memory banks remains difficult, especially for high-level language (hll) dsp compilers.in this paper, we describe two algorithms --- compaction-based (cb) data partitioning and partial data duplication --- that we developed as part of our research into the effective exploitation of dual data-memory banks in hll dsp compilers. we show that cb partitioning is an effective technique for exploiting dual data-memory banks, and that partial data duplication can augment cb partitioning in improving execution performance. our results show that cb partitioning improves the performance of our kernel benchmarks by 13%-40% and the performance of our application benchmarks by 3%-15%. for one of the application benchmarks, partial data duplication boosts performance from 3% to 34%.
a software instruction counter. although several recent papers have proposed architectural support for program debugging and profiling, most processors do not yet provide even basic facilities, such as an instruction counter. as a result, system developers have been forced to invent software solutions. this paper describes our implementation of a software instruction counter for program debugging. we show that an instruction counter can be reasonably implemented in software, often with less than 10% execution overhead. our experience suggests that a hardware instruction counter is not necessary for a practical implementation of watch-points and reverse execution, however it will make program instrumentation much easier for the system developer.
fab: building distributed enterprise disk arrays from commodity components. this paper describes the design, implementation, and evaluation of a federated array of bricks (fab), a distributed disk array that provides the reliability of traditional enterprise arrays with lower cost and better scalability. fab is built from a collection of bricks, small storage appliances containing commodity disks, cpu, nvram, and network interface cards. fab deploys a new majority-voting-based algorithm to replicate or erasure-code logical blocks across bricks and a reconfiguration algorithm to move data in the background when bricks are added or decommissioned. we argue that voting is practical and necessary for reliable, high-throughput storage systems such as fab. we have implemented a fab prototype on a 22-node linux cluster. this prototype sustains 85mb/second of throughput for a database workload, and 270mb/second for a bulk-read workload. in addition, it can outperform traditional master-slave replication through performance decoupling and can handle brick failures and recoveries smoothly without disturbing client requests.
hardware and software support for efficient exception handling. program-synchronous exceptions, for example, breakpoints, watchpoints, illegal opcodes, and memory access violations, provide information about exceptional conditions, interrupting the program and vectoring to an operating system handler. over the last decade, however, programs and run-time systems have increasingly employed these mechanisms as a performance optimization to detect normal and expected conditions. unfortunately, current architecture and operating system structures are designed for exceptional or erroneous conditions, where performance is of secondary importance, rather than normal conditions. consequently, this has limited the practicality of such hardware-based detection mechanisms.we propose both hardware and software structures that permit efficient handling of synchronous exceptions by user-level code. we demonstrate a software implementation that reduces exception-delivery cost by an order-of-magnitude on current risc processors, and show the performance benefits of that mechanism for several example applications.
visa: netstation's virtual internet scsi adapter. in this paper we describe the implementation of visa, our virtual internet scsi adapter. visa was built to evaluate the performance impact on the host operating system of using ip to communicate with peripherals, especially storage devices. we have built and benchmarked file systems on visa-attached emulated disk drives using udp/ip. by using ip, we expect to take advantage of its scaling characteristics and support for heterogeneous media to build large, long-lived systems. detailed file system and network cpu utilization and performance data indicate that it is possible for udp/ip to reach more than 80% of scsi's maximum throughput without the use of network coprocessors. we conclude that ip is a viable alternative to special-purpose storage network protocols, and presents numerous advantages.
separating data and control transfer in distributed operating systems. advances in processor architecture and technology have resulted in workstations in the 100+ mips range. as well, newer local-area networks such as atm promise a ten- to hundred-fold increase in throughput, much reduced latency, greater scalability, and greatly increased reliability, when compared to current lans such as ethernet.we believe that these new network and processor technologies will permit tighter coupling of distributed systems at the hardware level, and that distributed systems software should be designed to benefit from that tighter coupling. in this paper, we propose an alternative way of structuring distributed systems that takes advantage of a communication model based on remote network access (reads and writes) to protected memory segments.a key feature of the new structure, directly supported by the communication model, is the separation of data transfer and control transfer. this is in contrast to the structure of traditional distributed systems, which are typically organized using message passing or remote procedure call (rpc). in rpc-style systems, data and control are inextricably linked&mdash;all rpcs must transfer both data and control, even if the control transfer is unnecessary.we have implemented our model on decstation hardware connected by an atm network. we demonstrate how separating data transfer and control transfer can eliminate unnecessary control transfers and facilitate tighter coupling of the client and server. this has the potential to increase performance and reduce server load, which supports scaling in the face of an increasing number of clients. for example, for a small set of file server operations, our analysis shows a 50% decrease in server load when we switched from a communications mechanism requiring both control transfer and data transfer, to an alternative structure based on pure data transfer.
the effect of the pdp-11 architecture on code generation for chill. this paper outlines the implementation of the ccitt*) high level programming language chill on pdp-11 computers in the chill compiler constructed at the dr. neher laboratories. the characteristics and structure of the compiler are briefly described. the relationship between the pdp-11 architecture and the implementation of chill is outlined in more detail.
trap-driven simulation with tapeworm ii. tapeworm ii is a software-based simulation tool that evaluates the cache and tlb performance of multiple-task and operating system intensive workloads. tapeworm resides in an os kernel and causes a host machine's hardware to drive simulations with kernel traps instead of with address traces, as is conventionally done. this allows tapeworm to quickly and accurately capture complete memory referencing behavior with a limited degradation in overall system performance. this paper compares trap-driven simulation, as implemented in tapeworm, with the more common technique of trace-driven memory simulation with respect to speed, accuracy, portability and flexibility.
resource allocation in a high clock rate microprocessor. this paper discusses the design of a high clock rate (300mhz) processor. the architecture is described, and the goals for the design are explained. the performance of three processor models is evaluated using trace-driven simulation. a cost model is used to estimate the resources required to build processors with varying sizes of on-chip memories, in both single and dual issue models. recommendations are then made to increase the effectiveness of each of the models.
direct execution of lisp on a list-directed architecture. we have defined a direct-execution model dedicated to non-numerical processing which is based upon an internal representation of source programs derived from lisp. this model provides good support for both sophisticated editing (syntactical parsing, tree manipulation, pretty-printing, ...) of conventional languages and artificial intelligence languages. a high level microprogramming language (lem) was designed to write the interpreters and the editors. a hardware processor was built and a lisp interpreter, microprogrammed in lem, has been operational since september 1980. first, the influence of lisp on the lem language and the architecture is discussed. at the lem level, we will see that lisp has prompted the control constructs and the access functions to the tree-structured internal form. as for the architecture, we present the hardware implementation of a special garbage collector based upon reference counters. in turn, the machine has influenced the implementation of lisp. we present here the structure of our lisp interpreter and we give evaluation measures dealing with size, development effort, speed; they prove that programming in lem is easy, short to debug and very concise. moreover, the speed of our lisp interpreter confirms that the architecture is very efficient for symbolic processing.
a comparative study of arbitration algorithms for the alpha 21364 pipelined router. interconnection networks usually consist of a fabric of interconnected routers, which receive packets arriving at their input ports and forward them to appropriate output ports. unfortunately, network packets moving through these routers are often delayed due to conflicting demand for resources, such as output ports or buffer space. hence, routers typically employ arbiters that resolve conflicting resource demands to maximize the number of matches between packets waiting at input ports and free output ports. efficient design and implementation of the algorithm running on these arbiters is critical to maximize network performance.this paper proposes a new arbitration algorithm called spaa (simple pipelined arbitration algorithm), which is implemented in the alpha 21364 processor's on-chip router pipeline. simulation results show that spaa significantly outperforms two earlier well-known arbitration algorithms: pim (parallel iterative matching) and wfa (wave-front arbiter) implemented in the sgi spider switch. spaa outperforms pim and wfa because spaa exhibits matching capabilities similar to pim and wfa under realistic conditions when many output ports are busy, incurs fewer clock cycles to perform the arbitration, and can be pipelined effectively. additionally, we propose a new prioritization policy called the rotary rule, which prevents the network's adverse performance degradation from saturation at high network loads by prioritizing packets already in the network over new packets generated by caches or memory.
a performance evaluation of optimal hybrid cache coherency protocols. the caches within a multiprocessor typically use either a write-invalidate protocol or a write-update protocol to maintain consistency. the recently introduced mips r4000 processor allows operating system software to select, on a per-page basis, which multiprocessor cache coherence protocol (write-invalidate versus write-update) the hardware will use. the availability of the r4000 and the prospect of even more flexible hardware motivated us to examine the potential performance advantages of allowing user-level control over the choice of coherence protocol on a per-page basis and to ask whether more powerful hybrid protocols provide substantially more benefit. we examine the potential benefits of three classes of hybrid protocols: (1) hybrid protocols that choose statically, at the beginning of the program, between write-invalidate (wi) or write-update (wu) on a per-page basis, (2) hybrid protocols that choose statically between wi or wu for each cache block, and (3) dynamic hybrid protocols that can choose between wi or wu at each write. in order to determine how much potential benefit could be obtained by each of these protocol classes, we used trace-driven simulations to evaluate the optimal off-line protocol for each class. we found that the use of a hybrid protocol can substantially reduce the cost of memory references for most of the programs studied. a few programs can also realize large additional benefits from a per-block static hybrid protocol compared to a per-page static hybrid protocol. none of the programs, however, receive a significant additional benefit from using a dynamic hybrid protocol compared to the per-block static hybrid protocol, unless cache block sizes are larger than 16 words (64 bytes).
data buffering: run-time versus compile-time support. data-dependency, branch, and memory-access penalties are main constraints on the performance of high-speed microprocessors. the memory-access penalties concern both penalties imposed by external memory (e.g. cache) or by under utilization of the local processor memory (e.g. registers). this paper focuses solely on methods of increasing the utilization of data memory, local to the processor (registers or register-oriented buffers). a utilization increase of local processor memory is possible by means of compile-time software, run-time hardware, or a combination of both. this paper looks at data buffers which perform solely because of the compile-time software (single register sets); those which operate mainly through hardware but with possible software assistance (multiple register sets); and those intended to operate transparently with main memory implying no software assistance whatsoever (stack buffers). this paper shows that hardware buffering schemes cannot replace compile-time effort, but at most can reduce the complexity of this effort. it shows the utility increase of applying register allocation for multiple register sets. the paper also shows a potential utility decrease inherent to stack buffers. the observation that a single register set, allocated by means of interprocedural allocation, performs competitively with both multiple register set and stack buffer emphasizes the significance of the conclusion