bluuebunny/crossref_metadata_2025 huggingface dataset:
Compiler optimizations for improving data locality
Authors: Carr Steve , McKinley Kathryn S. , Tseng Chau-Wen
Published: October 2004

In the past decade, processor speed has become significantly faster than memory speed. Small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit
data locality
. In this paper, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. The model computes both
temporal
and
spatial
reuse of cache lines to find desirable loop organizations. The cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. We demonstrate that these program transformations are useful for optimizing many programs.

To validate our optimization strategy, we implemented our algorithms and ran experiments on a large collection of scientific programs and kernels. Experiments with kernels illustrate that our model and algorithm can select and achieve the best performance. For over thirty complete applications, we executed the original and transformed versions and simulated cache hit rates. We collected statistics about the inherent characteristics of these programs and our ability to improve their data locality. To our knowledge, these studies are the first of such breadth and depth. We found performance improvements were difficult to achieve because benchmark programs typically have high hit rates even for small data caches; however, our optimizations significantly improved several programs.
Simple compiler algorithms to reduce ownership overhead in cache coherence protocols
Authors: Skeppstedt Jonas , Stenström Per
Published: October 2004

We study in this paper the design and efficiency of compiler algorithms that remove ownership overhead in shared-memory multiprocessors with write-invalidate protocols. These algorithms detect loads followed by stores to the same address. Such loads are marked and constitute a hint to the cache to obtain an exclusive copy of the block. We consider three algorithms where the first one focuses on load-store sequences within each basic block of code and the other two analyse the existence of load-store sequences across basic blocks at the intra-procedural level. Since the dataflow analysis we adopt is a trivial variation of live-variable analysis, the algorithms are easily incorporated into a compiler.

Through detailed simulations of a cache-coherent NUMA architecture using five scientific parallel benchmark programs, we find that the algorithms are capable of removing over 95% of the separate ownership acquisitions. Moreover, we also find that even the simplest algorithm is comparable in efficiency with previously proposed hardware-based adaptive cache coherence protocols to attack the same problem.
Interleaving
Authors: Laudon James , Gupta Anoop , Horowitz Mark
Published: October 2004

There is an increasing trend to use commodity microprocessors as the compute engines in large-scale multiprocessors. However, given that the majority of the microprocessors are sold in the workstation market, not in the multiprocessor market, it is only natural that architectural features that benefit only multiprocessors are less likely to be adopted in commodity microprocessors. In this paper, we explore multiple-context processors, an architectural technique proposed to hide the large memory latency in multiprocessors. We show that while current multiple-context designs work reasonably well for multiprocessors, they are ineffective in hiding the much shorter uniprocessor latencies using the limited parallelism found in workstation environments. We propose an alternative design that combines the best features of two existing approaches, and present simulation results that show it yields better performance for both multiprogrammed workloads on a workstation and parallel applications on a multiprocessor. By addressing the needs of the workstation environment, our proposal makes multiple contexts more attractive for commodity microprocessors.
Hardware support for fast capability-based addressing
Authors: Carter Nicholas P. , Keckler Stephen W. , Dally William J.
Published: October 2004

Traditional methods of providing protection in memory systems do so at the cost of increased context switch time and/or increased storage to record access permissions for processes. With the advent of computers that supported cycle-by-cycle multithreading, protection schemes that increase the time to perform a context switch are unacceptable, but protecting unrelated processes from each other is still necessary if such machines are to be used in non-trusting environments.

This paper examines
guarded pointers
, a hardware technique which uses tagged 64-bit pointer objects to implement capability-based addressing. Guarded pointers encode a segment descriptor into the upper bits of every pointer, eliminating the indirection and related performance penalties associated with traditional implementations of capabilities. All processes share a single 54-bit virtual address space, and access is limited to the data that can be referenced through the pointers that a process has been issued. Only one level of address translation is required to perform a memory reference. Sharing data between processes is efficient, and protection states are defined to allow fast protected subsystem calls and create unforgeable data keys.
Enhancing data warehouse performance through query caching
Authors: Saharia Aditya N. , Babad Yair M.
Published: October 2004

The main function of a data warehouse is the separation of the decision layer from the operation layer so that users can invoke analysis, planning, and decision support applications without having to worry about constantly evolving operational databases. Such applications allow ad hoc queries for which no predefined reports exist. It is possible that an ad hoc query is submitted by different users or even by the same user at different times, requiring its repeated evaluations even though the contents of the warehouse have not changed in between. In this work, we propose an enhancement to a data warehouse structure, by building additional intelligence in the form of an adaptive and efficient query cache. The cache contains a list of recently executed ad hoc queries and their answers. Whenever possible, a new query is satisfied by answers already stored in the cache, thereby avoiding potentially large data scans. We discuss issues related to organizing and searching the query cache. In particular, we outline subsumption detection algorithms for a number of different situations that allow for quick decision on whether the cache can be used to evaluate an arriving query.
Some observations on the dynamics of a congestion control algorithm
Authors: Shenker Scott , Zhang Lixia , Clark David D.
Published: October 2004

We use simulation to make some observations about the behavior of the congestion control algorithm currently embedded in the 4.3-Tahoe BSD TCP implementation. We investigate a simple case of a few TCP connections, originating and terminating at the same pair of hosts, using a single bottleneck link. Our simulations reveal two unexpected phenomena. First, packets from the individual connections, rather than being mixed together, completely separate into individual clusters. Second, every
connection loses a single packet during each congestion epoch. As a way of exploring the cause of these phenomena, we discuss how the behavior is altered by modifications to the congestion control algorithm and to the switch queue control algorithm
.
Design considerations for usage accounting and feedback in internetworks
Authors: Estrin Deborah , Zhang Lixia
Published: October 2004

This paper investigates the design of resource usage feedback mechanisms for packet switched internetworks. After a discussion of the
motivations
for feedback mechanisms,
feedback channels
and
policies
are described. We then outline issues raised by the design of
mechanisms
to realize these policies, including: network service disciplines, accounting granularity, metrics, authentication, and coordination among transit carriers.Usage-based charging is only one means of feedback. Our purpose is to begin a systematic discussion of the technical issues associated with a range of usage feedback alternatives. Therefore the paper should not be read as a policy statement promoting usage sensitive charging in internets. In fact, one of the goals of the feedback mechanisms explored in this paper is to allow network service providers and users to
avoid
the introduction of usage sensitive charges if they so wish; while still realizing the benefits of statistical resource sharing offered by packet switching and the benefits of efficient resource utilization offered by usage feedback.
Bindings and Ada
Authors: McCoy L. Scott
Published: October 2004

There is a need in the development of software systems for the utilization of capabilities which are not inherently supported by a chosen development language. In order to overcome this deficiency in a cost-effective manner, bindings are required. This article will discuss bindings, how software systems used external capabilities in the past, how the Ada language allows bindings to be built, and the steps for creating bindings in Ada.
Aggregation and conformance in differentiated service networks
Authors: Guérin Roch A. , Pla Vicent
Published: October 2004

The Differentiated Service (Diff-Serv) architecture [1] advocates a
model based on different “granularity” at network edges and within the network. In particular, core routers are only required to act on a few
aggregates
that are meant to offer a pre-defined set of service levels. The use of aggregation raises a number of questions for end-to-end services, in particular when crossing domain boundaries where policing actions may be applied. This paper focuses on the impact of such policing actions in the context of individual and the bulk services built on top of the Expedited Forwarding (EF) [7] per-hop-behavior (PHB). The findings of this investigation confirm and quantify the expected need for reshaping at network boundaries, and identify a number of somewhat unexpected behaviors. Recommendations are also made for when reshaping is not available.
The Eifel retransmission timer
Authors: Ludwig R. , Sklower K.
Published: October 2004

We analyze two alternative retransmission timers for the Transmission Control Protocol (TCP). We first study the retransmission timer of TCP-Lite which is considered to be the current de facto standard for TCP implementations. After revealing four major problems of TCP-Lite's retransmission timer, we propose a new timer, named the
Eifel retransmission timer
, that eliminates these. The strength of our work lies in its hybrid analysis methodology. We develop models of both retransmission timers for the class of network-limited TCP bulk data transfers in steady state. Using those models, we predict the problems of TCP-Lite's retransmission timer and develop the Eifel retransmission timer. We then validate our model-based analysis through measurements in a real network that yield the same results.
An application developer's perspective on reliable multicast for distributed interactive media
Authors: Mauve Martin , Hilt Volker
Published: October 2004

In this paper we investigate which characteristics reliable multicast services should have in order to be appropriate for use by distributed interactive media applications such as shared whiteboards, networked computer games, or distributed virtual environments. We take a close look at the communication requirements of these applications and at existing approaches to realize reliable multicast. Based on this information we deduce which reliable multicast transport protocols are appropriate for the different aspects of distributed interactive media. Furthermore we discuss how the application program interface of a reliable multicast service should be designed in order to support the development of applications for distributed interactive media.
Knowledge-proof based versatile smart card verification protocol
Authors: Nyang Dae Hun , Song Joo Seok
Published: October 2004

We propose a zero-knowledge interactive proof based identification and signature scheme. The protocol is based on Euler's totient function and discrete logarithms over the ring
Z/nZ
, and can be applied to smart cards. A prover keeps a signed subgroup generator provided by a trusted center as its secret information. Our scheme has symmetricity in the sense that the same computational complexity and the same hardware both for Prover and for Verifier are required. Also, it requires minimal amount of computation and communications for secret information. The protocol is versatile enough to be applicable to digital signature scheme, multiple digital signature scheme and key exchange protocol. We outline those protocols to show the versatility of our protocol.
Big omega versus the wild functions
Authors: Vitányi Paul M. B. , Meertens Lambert
Published: October 2004

The question of the desirable properties and proper definitions of the Order-of-Magnitude symbols, in particular O and Ø, is addressed once more. The definitions proposed are chosen for complementary mathematical properties, rather than for similarity of form.
Convergence of simulated annealing-hastings
Authors: Hastings Harold M.
Published: October 2004

We develop worst-case and typical estimates for the rate of convergence of annealing algorithms. The worst-case estimates extend results of Geman and Geman (1983) for pattern recognition. However, as Geman and Geman observe, and empirical results imply, simulated annealing usually displays much faster convergence (and thus allows much faster cooling) than their worst-case results. Our typical case results help to explain this phenomenon.
Non-Ada to Ada conversion
Authors: Martin Donald G.
Published: October 2004

Ada was created with the intention that future computer software be designed and written in a maintainable form. The computer systems written in the past have not been easily maintainable due to the lack of adherence to modern software principles, hence the need for Ada. Many in the industry are not aware of the differences in the approach that is needed with Ada and consider a translation a relatively trivial endeavor. This paper intends to outline some of the issues that need to be considered when converting a non-Ada computer language into Ada.
Non-preemptive time warp scheduling algorithms
Authors: Burdorf Christopher , Marti Jed
Published: October 2004

This paper presents results of experiments we conducted on a number of scheduling algorithms used in a multi-processing Time Warp system. Our results show that system performance can be improved by using indirect indicators of Time Warp progress without going to the expense of user specified scheduling or relying on dependency graphs. Our best algorithm is based on a composite measure of simulation advance rate, flow control, and the appearance of specific message types.
Pandora - an experimental system for multimedia applications
Authors: Hopper Andy
Published: October 2004

Pandora is a joint project between Olivetti Research Cambridge and the University of Cambridge Computer Laboratory. The project is investigating the use of multimedia workstations in a working environment with particular emphasis on digital video. It endeavours to place a camera on the desktop to make generation of multimedia documents as easy as producing text. We are aiming to produce a number of new applications as well as to provide insights into the way computer systems should be designed.The project is in three stages. In the first a peripheral, Pandora's Box, has been designed. This box can be attached to any one of a range of workstations and provides multimedia features. In the second stage a number of such systems are being deployed amongst a community of systems developers and application writers. Finally we will use the experimental system in our daily work to evaluate new applications. From the users point of view the normal workstation environment is maintained but additional features are available.This paper describes the design decisions which must be taken when incorporating video in a workstation. A description of the Pandora's Box peripheral which provides multimedia features is given. Finally the distributed system under construction is discussed.
A disstributed backoff algorithm to support real-time traffic on ethernet
Authors: Gupta Vijay
Published: October 2004

Ethernets are very popular in LANs because of their ease of administration. With the growing trend towards distributed multimedia applications, it has become essential for the underlying systems to provide resource guarantees. Traditionally, Ethernet uses the Truncated Binary Exponential Backoff (BEB) algorithm for medium access. BEB has very good characteristics for reducing the average latency of packets, but is not designed to support low delay jitter. We propose an IEEE 802.3-compliant distributed backoff algorithm which gives good bounds on the delay jitter and average delay for the transmission of real-time traffic over shared 100 Mbit/sec Ethernet medium. Simulation results show that for a mixture of data and constant bit rate (CBR) video traffic, our backoff algorithm has an order of magnitude less delay jitter than BEB for offered loads below 76%. The delay jitter of our algorithm is around 4 times lower than BEB for simulation of a mixture of data and variable bit rate (VBR) video traffic.
Co-opetition and knowledge transfer
Authors: Loebecke Claudia , Van Fenema Paul C. , Powell Philip
Published: October 2004

Recent business trends have given rise to co-opetition: simultaneous co-operation and competition between firms. Co-opetition entails the sharing of knowledge which may be a key source of competitive advantage. Under co-opetition there is a paradox that the knowledge shared for cooperation may also be used for competition. While the existence of this problem is known, there is little investigation of how it may be modeled and, thus, managed.This paper begins by discussing the problem situation and its underlying theory. It then introduces a game-theoretic framework for analyzing inter-organizational knowledge sharing in the context of co-opetition. This allows the value of knowledge shared to be investigated and reveals that a crucial aspect will be the firm's ability to manage the process. Thus, based on the framework, the paper explores management guidelines predicated on co-ordination and control theory for the most challenging of four contingencies identified. The paper concludes with an agenda for future theoretical and empirical research.
Knowledge capability and maturity in software management
Authors: Baskerville Richard , Pries-Heje Jan
Published: October 2004

Knowledge management is used as the underlying theory to develop a set of key process areas for a supplement to the CMM in small or medium-sized enterprises (SME) that develop software. These processes involve a focus on managing knowledge capability rather than traditional project management. A longitudinal case study provides evidence that current practices have already established the feasibility of these key process areas.
A social action model of situated information systems design
Authors: Gasson Susan
Published: October 2004

The aim of this paper is to examine the nature of information systems (IS) design as situated in its organizational context. Much of the IS literature takes a fragmented perspective of the nature of IS design, examining methodological issues, social issues, or political issues in isolation from the context of the design initiative. Recent work in situated action and social cognition provides a basis for a more integrated understanding of situated IS design.Findings from a participant observation study of situated IS design are discussed, to form the basis for an integrative, social action model of IS design. Findings from the study demonstrate how innovative IS design activity is situated in its organizational context. It is argued that the form and nature of an organizational design "problem" is inseparable from its context and that design knowledge is distributed among a design team rather than shared intersubjectively. The situated nature of design requires design skills to be learned through simulated design contexts, rather than the communication of abstract models (as in many formal education programs). The situated model rejects the predefined goal-structures assumed by decompositional models of design, such as the "waterfall" model. It is suggested that design goal-definition must proceed recursively through the processes of design, which requires new approaches to the design and development of organizational information systems.
Architecture and design of AlphaServer GS320
Authors: Gharachorloo Kourosh , Sharma Madhu , Steely Simon , Van Doren Stephen
Published: October 2004

This paper describes the architecture and implementation of the AlphaServer GS320, a cache-coherent non-uniform memory access multiprocessor developed at Compaq. The AlphaServer GS320 architecture is specifically targeted at medium-scale multiprocessing with 32 to 64 processors. Each node in the design consists of four Alpha 21264 processors, up to 32GB of coherent memory, and an aggressive IO subsystem. The current implementation supports up to 8 such nodes for a total of 32 processors. While snoopy-based designs have been stretched to medium-scale multiprocessors by some vendors, providing sufficient snoop bandwidth remains a major challenge especially in systems with aggressive processors. At the same time, directory protocols targeted at larger scale designs lead to a number of inherent inefficiencies relative to snoopy designs. A key goal of the AlphaServer GS320 architecture has been to achieve the best-of-both-worlds, partly by exploiting the bounded scale of the target systems.This paper focuses on the unique design features used in the AlphaServer GS320 to efficiently implement coherence and consistency. The guiding principle for our directory-based protocol is to address correctness issues related to rare protocol races without burdening the common transaction flows. Our protocol exhibits lower occupancy and lower message counts compared to previous designs, and provides more efficient handling of 3-hop transactions. Furthermore, our design naturally lends itself to elegant solutions for deadlock, livelock, starvation, and fairness. The AlphaServer GS320 architecture also incorporates a couple of innovative techniques that extend previous approaches for efficiently implementing memory consistency models. These techniques allow us to generate commit events (which are used for ordering purposes) well in advance of formulating the reply to a transaction. Furthermore, the separation of the commit event allows time-critical replies to by-pass inbound requests without violating ordering properties. Even though our design specifically targets medium-scale servers, many of the same techniques can be applied to larger-scale directory-based and smaller-scale snoopy-based designs. Finally, we evaluate the performance impact of some of the above optimizations and present a few competitive benchmark results.
MemorIES3
Authors: Nanda Ashwini , Mak Kwok-Ken , Sugarvanam Krishnan , Sahoo Ramendra K. , Soundarararjan Vijayaraghavan , Smith T. Basil
Published: October 2004

Modern system design often requires multiple levels of simulation for design validation and performance debugging. However, while machines have gotten faster, and simulators have become more detailed, simulation speeds have not tracked machine speeds, As a result, it is difficult to simulate realistic problem sizes and hardware configurations for a target machine. Instead, researchers have focussed on developing sealing methodologies and running smaller problem sizes and configurations that attempt to represent the behavior of the real problem. Given the increasing size of problems today, it is unclear whether such an approach yields accurate results. Moreover, although commercial workloads are prevalent and important in today's marketplace, many simulation tools are unable to adequately profile such applications, let alone for realistic sizes.In this paper we present a hardware-based emulation tool that can be used to aid memory system designers. Our focus is on the memory system because the ever-widening gap between processor and memory speeds means that optimizing the memory subsystem is critical for performance. We present the design of the
Memory
I
nstrumentation and
E
mulation
S
ystem (MemoriES). MemoriES is a programmable tool designed using FPGAs and SDRAMs. It plugs into an SMP bus to perform on-line emulation of several cache configurations, structures and protocols while the system is running real-life workloads in real-time, without any slowdown in application execution speed. We demonstrate its usefulness in several case studies, and find several important results. First, using traces to perform system evaluation can lead to incorrect results (off by 100% or more in some cases) if the trace size is not sufficiently large. Second. MemoriES is able to detect performance problems by profiling miss behavior over the entire course of a run, rather than relying on a small interval of time. Finally, we observe that previous studies of SPLASH2 applications using scaled application sizes can result in optimistic miss rates relative to real sizes on real machines, providing potentially misleading data when used for design evaluation.
FLASH vs. (Simulated) FLASH
Authors: Gibson Jeff , Kunz Robert , Ofelt David , Horowitz Mark , Hennessy John , Heinrich Mark
Published: October 2004

Simulation is the primary method for evaluating computer systems during all phases of the design process. One significant problem with simulation is that it rarely models the system exactly, and quantifying the resulting simulator error can be difficult. More importantly, architects often assume without proof that although their simulator may make inaccurate absolute performance predictions, it will still accurately predict architectural trends.This paper studies the source and magnitude of error in a range of architectural simulators by comparing the simulated execution time of several applications and microbenchmarks to their execution time on the actual hardware being modeled. The existence of a hardware gold standard allows us to find, quantify, and fix simulator inaccuracies. We then use the simulators to predict architectural trends and analyze the sensitivity of the results to the simulator configuration. We find that most of our simulators predict trends accurately, as long as they model all of the important performance effects for the application in question. Unfortunately, it is difficult to know what these effects are without having a hardware reference, as they can be quite subtle. This calls into question the value, for architectural studies, of highly detailed simulators whose characteristics are not carefully validated against s real hardware design.
Using meta-level compilation to check FLASH protocol code
Authors: Chou Andy , Chelf Benjamin , Engler Dawson , Heinrich Mark
Published: October 2004

Building systems such as OS kernels and embedded software is difficult. An important source of this difficulty is the numerous rules they must obey: interrupts cannot be disabled for ~too long," global variables must be protected by locks, user pointers passed to OS code must be checked for safety before use, etc. A single violation can crash the system, yet typically these invariants are unchecked, existing only on paper or in the implementor's mind.This paper is a case study in how system implementors can use a new programming methodology, meta-level compilation (MC), to easily check such invariants. It focuses on using MC to check for errors in the code used to manage cache coherence on the FLASH shared memory multiprocessor. The only real practical method known for verifying such code is testing and simulation. We show that simple, system-specific checkers can dramatically improve this situation by statically pinpointing errors in the program source. These checkers can be written by implementors themselves and, by exploiting the system-specific information this allows, can detect errors unreachable with other methods. The checkers in this paper found 34 bugs in FLASH code despite the care used in building it and the years of testing it has undergone. Many of these errors fall in the worst category of systems bugs: those that show up sporadically only after days of continuous use. The case study is interesting because it shows that the MC approach finds serious errors in well-tested, non-toy systems code. Further, the code to find such bugs is usually 10-100 lines long, written in a few hours, and exactly locates errors that, if discovered during testing, would require several days of investigation by an experienced implementor.The paper presents 8 checkers we wrote, their application to five different protocol implementations, and a discussion of the errors that we found.
Evaluating design alternatives for reliable communication on high-speed networks
Authors: Bhoedjang Raoul A. F. , Verstoep Kees , Rühl Tim , Bal Henri E. , Hofman Rutger F. H.
Published: October 2004

We systematically evaluate the performance of five implementations of a single, user-level communication interface. Each implementation makes different architectural assumptions about the reliability of the network hardware and the capabilities of the network interface. The implementations differ accordingly in their division of protocol tasks between host software, network-interface firmware, and network hardware. Using microbenchmarks, parallel-programming systems, and parallel applications, we assess the performance impact of different protocol decompositions. We show how moving protocol tasks to a relatively slow network interface yields both performance advantages and disadvantages, depending on the characteristics of the application and the underlying parallel-programming system. In particular, we show that a communication system that assumes highly reliable network hardware and that uses network-interface support to process multicast traffic performs best for all applications.
Hoard
Authors: Berger Emery D. , McKinley Kathryn S. , Blumofe Robert D. , Wilson Paul R.
Published: October 2004

Parallel, multithreaded C and C++ programs such as web servers, database managers, news servers, and scientific applications are becoming increasingly prevalent. For these applications, the memory allocator is often a bottleneck that severely limits program performance and scalability on multiprocessor systems. Previous allocators suffer from problems that include poor performance and scalability, and heap organizations that introduce false sharing. Worse, many allocators exhibit a dramatic increase in memory consumption when confronted with a producer-consumer pattern of object allocation and freeing. This increase in memory consumption can range from a factor of
P
(the number of processors) to unbounded memory consumption.This paper introduces Hoard, a fast, highly scalable allocator that largely avoids false sharing and is memory efficient. Hoard is the first allocator to simultaneously solve the above problems. Hoard combines one global heap and per-processor heaps with a novel discipline that provably bounds memory consumption and has very low synchronization costs in the common case. Our results on eleven programs demonstrate that Hoard yields low average fragmentation and improves overall program performance over the standard Solaris allocator by up to a factor of 60 on 14 processors, and up to a factor of 18 over the next best allocator we tested.
OceanStore
Authors: Kubiatowicz John , Bindel David , Chen Yan , Czerwinski Steven , Eaton Patrick , Geels Dennis , Gummadi Ramakrishna , Rhea Sean , Weatherspoon Hakim , Weimer Westley , Wells Chris , Zhao Ben
Published: October 2004

OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime. Additionally, monitoring of usage patterns allows adaptation to regional outages and denial of service attacks; monitoring also enhances performance through pro-active movement of data. A prototype implementation is currently under development.
Symbiotic jobscheduling for a simultaneous multithreaded processor
Authors: Snavely Allan , Tullsen Dean M.
Published: October 2004

Simultaneous Multithreading machines fetch and execute instructions from multiple instruction streams to increase system utilization and speedup the execution of jobs. When there are more jobs in the system than there is hardware to support simultaneous execution, the operating system scheduler must choose the set of jobs to coscheduleThis paper demonstrates that performance on a hardware multithreaded processor is sensitive to the set of jobs that are coscheduled by the operating system jobscheduler. Thus, the full benefits of SMT hardware can only be achieved if the scheduler is aware of thread interactions. Here, a mechanism is presented that allows the scheduler to significantly raise the performance of SMT architectures. This is done without any advance knowledge of a workload's characteristics, using sampling to identify jobs which run well together.We demonstrate an SMT jobscheduler called SOS. SOS combines an overhead-free sample phase which collects information about various possible schedules, and a symbiosis phase which uses that information to predict which schedule will provide the best performance. We show that a small sample of the possible schedules is sufficient to identify a good schedule quickly. On a system with random job arrivals and departures, response time is improved as much as 17% over a schedule which does not incorporate symbiosis.
An analysis of operating system behavior on a simultaneous multithreaded architecture
Authors: Redstone Joshua A. , Eggers Susan J. , Levy Henry M.
Published: October 2004

This paper presents the first analysis of operating system execution on a simultaneous multithreaded (SMT) processor. While SMT has been studied extensively over the past 6 years, previous research has focused entirely on user-mode execution. However, many of the applications most amenable to multithreading technologies spend a significant fraction of their time in kernel code. A full understanding of the behavior of such workloads therefore requires execution and measurement of the operating system, as well as the application itself.To carry out this study, we (1) modified the Digital Unix 4.0d operating system to run on an SMT CPU, and (2) integrated our SMT Alpha instruction set simulator into the SimOS simulator to provide an execution environment. For an OS-intensive workload, we ran the multithreaded Apache Web server on an 8-context SMT. We compared Apache's user- and kernel-mode behavior to a standard multiprogrammed SPECInt workload, and compared the SMT processor to an out-of-order superscalar running both workloads. Overall, our results demonstrate the microarchitectural impact of an OS-intensive workload on an SMT processor and provide insight into the OS demands of the Apache Web server. The synergy between the SMT processor and Web and OS software produced a greater throughput gain over superscalar execution than seen on any previously examined workloads, including commercial databases and explicitly parallel programs.
Compiler-controlled memory
Authors: Cooper Keith D. , Harvey Timothy J.
Published: October 2004

Optimizations aimed at reducing the impact of memory operations on execution speed have long concentrated on improving cache performance. These efforts achieve a. reasonable level of success. The primary limit on the compiler's ability to improve memory behavior is its imperfect knowledge about the run-time behavior of the program. The compiler cannot completely predict runtime access patterns.There is an exception to this rule. During the register allocation phase, the compiler often must insert substantial amounts of
spill code
; that is, instructions that move values from registers to memory and back again. Because the compiler itself inserts these memory instructions, it has more knowledge about them than other memory operations in the program.Spill-code operations are disjoint from the memory manipulations required by the semantics of the program being compiled, and, indeed, the two can interfere in the cache. This paper proposes a hardware solution to the problem of increased spill costs---a small
compiler-controlled memory
(CCM) to hold spilled values. This small random-access memory can (and should) be placed in a distinct address space from the main memory hierarchy. The compiler can target spill instructions to use the CCM, moving most compiler-inserted memory traffic out of the pathway to main memory and eliminating any impact that those spill instructions would have on the state of the main memory hierarchy. Such memories already exist on some DSP microprocessors. Our techniques can be applied directly on those chips.This paper presents two compiler-based methods to exploit such a memory, along with experimental results showing that speedups from using CCM may be sizable. It shows that using the register allocation's coloring paradigm to assign spilled values to memory can greatly reduce the amount of memory required by a program.
An empirical analysis of instruction repetition
Authors: Sodani Avinash , Sohi Gurindar S.
Published: October 2004

We study the phenomenon of instruction repetition, where the inputs and outputs of multiple dynamic instances of a static instruction are repeated. We observe that over 80% of the dynamic instructions executed in several programs are repeated and most of the repetition is due to a small number of static instructions. We attempt understand the source of this repetitive behavior by categorizing dynamic program instructions into dynamic program slices at both a global level and a local (within function) level. We observe that repeatability is more an artifact of how computation is expressed, and less of program inputs. Function-level analysis suggests that many functions are called with repeated arguments, though almost all of them have side effects. We provide commentary on exploiting the observed phenomenon and its sources in both software and hardware.
Data speculation support for a chip multiprocessor
Authors: Hammond Lance , Willey Mark , Olukotun Kunle
Published: October 2004

Thread-level speculation is a technique that enables parallel execution of sequential applications on a multiprocessor. This paper describes the complete implementation of the support for threadlevel speculation on the Hydra chip multiprocessor (CMP). The support consists of a number of software speculation control handlers and modifications to the shared secondary cache memory system of the CMP This support is evaluated using five representative integer applications. Our results show that the speculative support is only able to improve performance when there is a substantial amount of medium--grained loop-level parallelism in the application. When the granularity of parallelism is too small or there is little inherent parallelism in the application, the overhead of the software handlers overwhelms any potential performance benefits from speculative-thread parallelism. Overall, thread-level speculation still appears to be a promising approach for expanding the class of applications that can be automatically parallelized, but more hardware intensive implementations for managing speculation control are required to achieve performance improvements on a wide class of integer applications.
Active disks
Authors: Acharya Anurag , Uysal Mustafa , Saltz Joel
Published: October 2004

Several application and technology trends indicate that it might be both profitable and feasible to move computation closer to the data that it processes. In this paper, we evaluate
Active Disk
architectures which integrate significant processing power and memory into a disk drive and allow application-specific code to be downloaded and executed on the data that is being read from (written to) disk. The key idea is to offload bulk of the processing to the diskresident processors and to use the host processor primarily for coordination, scheduling and combination of results from individual disks. To program Active Disks, we propose a stream-based programming model which allows disklets to be executed efficiently and safely. Simulation results for a suite of six algorithms from three application domains (commercial data warehouses, image processing and satellite data processing) indicate that for these algorithms, Active Disks outperform conventional-disk architectures.
Hardware-software trade-offs in a direct Rambus implementation of the RAMpage memory hierarchy
Authors: Machanick Philip , Salverda Pierre , Pompe Lance
Published: October 2004

The RAMpage memory hierarchy is an alternative to the traditional division between cache and main memory: main memory is moved up a level and DRAM is used as a paging device. The idea behind RAMpage is to reduce hardware complexity, if at the cost of software complexity, with a view to allowing more flexible memory system design. This paper investigates some issues in choosing between RAMpage and a conventionalcache architecture, with a view to illustrating trade-offs which can be made in choosing whether to place complexity in the memory system in hardware or in software. Performance results in this paper are based on a simple Rambus implementation of DRAM, with performance characteristics of Direct Rambus, which should be available in 1999. This paper explores the conditions under which it becomes feasible to perform a context switch on a miss in the RAMpage model, and the conditions under which RAMpage is a win over a conventional cache architecture: as the CPU-DRAM speed gap grows, RAMpage becomes more viable.
An out-of-order execution technique for runtime binary translators
Authors: Le Bich C.
Published: October 2004

A dynamic translator emulates an instruction set architccturc by translating source instructions to native code during execution. On statically-scheduled hardware, higher performance can potentially be achieved by reordering the translated instructions; however, this is a challenging transformation if the source architecture supports precise exception semantics, and the user-level program is allowed to register exception handlers. This paper presents a software technique which allows a translator to achieve the out-of-order execution of user-level programs, while preserving all sequential semantics. The design combines a translator, an interpreter, and a set of operating system services. Using the proposed techniques, a dynamic translator can optimistically reorder instructions and speculate them across branch boundaries. If a mispeculated operation causes an exception, the recovery algorithm reverts the application state to a safe point, then retranslates the faulty code without reordering to disable further exceptions.
Overlapping execution with transfer using non-strict execution for mobile programs
Authors: Krintz Chandra , Calder Brad , Lee Han Bok , Zorn Benjamin G.
Published: October 2004

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%.
UTLB
Authors: Chen Yuqun , Bilas Angelos , Damianakis Stefanos N. , Dubnicki Cezary , Li Kai
Published: October 2004

An important aspect of a high-speed network system is the ability to transfer data directly between the network interface and application buffers. Such a
direct data path
requires the network interface to "know" the virtual-to-physical address translation of a user buffer,
i.e
., the physical memory location of the buffer. This paper presents an efficient address translation architecture, User-managed TLB (UTLB), which eliminates system calls and device interrupts from the common communication path. UTLB also supports application-specific policies to pin and unpin application memory. We report micro-benchmark results for an implementation on Myrinet PC clusters. A trace-driven analysis is used to compare the UTLB approach with the interrupt-based approach. It is also used to study the effects of UTLB cache size, associativity, and prefetching. Our results show that the UTLB approach delivers robust performance with relatively small translation cache sizes.
Investigating optimal local memory performance
Authors: Temam Olivier
Published: October 2004

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.