bluuebunny/crossref_metadata_2025 huggingface dataset:
Object oriented requirements analysis in an Ada project
Authors: Freitas Maria Manuel , Moreira Ana , Guerreiro Pedro
Published: October 2004

Among the methodologies that have appeared related to Ada, Object Oriented Development is emerging as the one of choice for a wide range of applications. Although Object Oriented Development is understood as covering more than just the design phase of the software life cycle, most Ada projects adopt these methodologies only in the design phase, using other kinds of methodologies for the requirements analysis, like structured analysis. We believe that if a single coordinated methodology is used throughout all the phases of the software life cycle, it will increase the traceability in the system, decrease the integration problems, and improve conceptual integrity of the design, leading to a more consistent final system.Although there are already many well known Object Oriented Design methods for Ada, Object Oriented Requirements Analysis methods are not so common. Notwithstanding, having a project to be carried out in Ada, we decided to use Object Oriented methodologies from the very beginning, using the Object Oriented Requirements Analysis method proposed by the company EVB Software Engineering, Inc. That work, however, was not completely straightforward. We faced many practical difficulties, that had to be dealt with, and some problems that had to be solved. In this way, a variant of the original method emerged, which we believe is better suited to real word projects.
Rethinking the TCP Nagle algorithm
Authors: Mogul J. C. , Minshall G.
Published: October 2004

Modern TCP implementations include a mechanism, known as the Nagle
algorithm, which prevents the unnecessary transmission of a large number of small packets. This algorithm has proved useful in protecting the Internet against excessive packet loads. However, many applications suffer performance problems as a result of the traditional implementation of the Nagle algorithm. An interaction between the Nagle algorithm and TCP's delayed acknowledgement policy can create an especially severe problems, through a temporary “deadlock.” These flaws in the Nagle algorithm have prompted many application implementors to disable it, even in cases where this is neither necessary nor wise.

We categorize the applications that should and should not disable the Nagle algorithm, and we show that for some applications that often disable the Nagle algorithm, equivalent performance can be obtained through an improved implementation of the algorithm. We describe five possible modifications, including one novel proposal, and analyze their performance on benchmark tests. We also describe a receiver-side modification that can help in some circumstances.
D-ARM
Authors: Ling Lee Luan , Filho Alberto José Centeno
Published: October 2004

This paper presents a new topology for multidimensional
interconnection networks, namely D-ARM, which has the goal of simultaneously providing a high network transmission capacity and a low information transfer delay. The new D-ARM topology has a connection pattern arranged in
alternated regular mesh
fashions with toroidal boundaries. Five distinct network attributes, normally used to characterize interconnection network topologies, were employed to analyze the D-ARM topology: network diameter, bisection width, deflection index, degree of connectivity and symmetry. Also the evaluation of the performance of the D-ARM network through computer simulations was carried out based on the following measures: throughput and information transfer delay. An upper-bound of the network transmission capacity was derived in function of the network dimension (D) and length (W). In order to validate our proposal, as a viable topology among other well-known topologies, a comparative analysis among the D-ARM, MSN and ShuffleNet was performed. The analysis results show that the D-ARM outperforms the MSN and ShuffleNet in many aspects and suggest some plausible applications of the D-ARM networks, e.g., broadband switching architecture, multiprocessor connection, high-speed MAN, WDM optical networks and photonic networks.
Improving TCP performance over asymmetric networks
Authors: Ming-Chit Ivan Tam , Jinsong Du , Wang Weiguo
Published: October 2004

Bandwidth asymmetry is quite common among modern networks; e.g., ADSL, cable TV, wireless, and satellite link with a terrestrial return path. In these networks, the bandwidth over one direction can be orders of magnitude smaller than that over the other. The performance of TCP transfer in the high bandwidth direction can be severly reduced by the delay acknowledgment packets experienced in the reverse direction. In this paper, we describe our proposed solution ACE (Acknowledgement Based on
Cwnd
Estimation). In comparison to other solutions, ACE requires only modification of the TCP stack at terminals attached to an asymmetric network. We evaluated the performance of ACE over a cable modem network by simulation. We have also implemented ACE on the Linux platform and tested it on a small testbed network with an emulated asymmetric link. The performance improvement was significant especially when there is a high degree of asymmetry.
Some thoughts on running a conference
Authors: Simons Barbara
Published: October 2004

Various aspects of the conference running problem are discussed. Solutions for some special cases are presented, and some new open problems are introduced into the literature.
A regular architecture for operating system
Authors: Antonov Vadim G.
Published: October 2004

This paper describes an object-oriented operating system with regular architecture and minimal functionally complete set of primitives. It also considers the possibility of implementation of efficient system with this architecture on von Neumann machines.
A taxonomy-based comparison of several distributed shared memory systems
Authors: Tam Ming-Chit , Smith Jonathan M. , Farber David J.
Published: October 2004

Two possible modes of Input/Output (I/O)are "sequential" and "random-access", and there is an extremely strong conceptual link between I/O and communication. Sequential communication, typified in the I/O setting by magnetic tape, is typified in the communication setting by a
stream
, e.g., a UNIX
1
pipe. Random-access communication, typified in the I/O setting by a drum or disk device, is typified in the communication setting by
shared memory
. In this paper, we study and survey the extension of the random-access model to distributed computer systems.
A Distributed Shared Memory (DSM)
is a memory area shared by processes running on computers connected by a network. DSM provides direct system support of the shared memory programming model. When assisted by hardware, it can also provide a low-overhead interprocess communication (IPC) mechanism to software. Shared pages are migrated on demand between the hosts. Since computer network latency is typically much larger than that of a shared bus, caching in DSM is necessary for performance. We use caching and issues such as address space structure and page replacement schemes to define a taxonomy. Based on the taxonomy we examine three DSM efforts in detail, namely: IVY, Clouds and MemNet.
A survey of remote procedure calls
Authors: Tay B. H. , Ananda A. L.
Published: October 2004

The Remote Procedure Call (RPC) is a popular paradigm for inter-process communication (IPC) between processes in different computers across the network. It is widely used in various Distributed Systems. Although it is conceptually simple and straightforward to implement, there are a lot of different and subtle issues involved which result different RPC implementations. In this paper, various distinctive RPC implementations are surveyed, analyzed and compared: Xerox Courier RPC, Xerox Cedar RPC, Sun ONC/RPC, Apollo NCA/RPC, Cambridge Mayflower Project RPC, MIT Athena Project RPC, Stanford Modula/V RPC, and Rajdoot RPC are presented. The design objectives, features provided, call semantics, orphan treatment, binding, transport protocols supported, security/authentication, data representation and application programming interface of these RPCs are examined.
Maps of the interval, polynomial time, and polynomial space
Authors: Hastings Harold M.
Published: October 2004

We use sequences of expansive maps of the interval to construct non-autonomous systems which appear to display "hyper-exponential loss of information" (defined below). A rigorous proof of this loss of information would prove that the class P of languages accepted in polynomial time is properly contained in the class PTAPE of languages accepted in polynomial space. Thus either P = NP or NP = PTAPE, where NP is the class of languages accepted by non-deterministic machines in polynomial time.
Retargeting and rehosting the DDC Ada compiler system
Authors: Clemmensen Geert B.
Published: October 2004

This paper gives a short description of the effort carried out by Dansk Datamatik Center (DDC) to retarget and rehost the DDC Ada Compiler System to the Honeywell DPS 6 product line. Both technical and management issues of this effort will be discussed.
On the requirements for the use of a program design language
Authors: Berry Daniel M. , Yavne Nancy , Yavne Moshe
Published: October 2004

The linguistic requirements for a program design language that can be used profitably in all stages of the software lifecycle are investigated. What its processor and related tools must be able to do are identified. It is observed that no existing program design language meets all the requirements. Two particular deficiencies are noted in extant program design languages, namely the lack of parameterization and data-structuring. However, some ideas are obtained from an existing program design language, Software Development Processor (SDP). It provides a suitable way of providing parameterization and data-structuring. Extensions of SDP required for a suitable Ada
d
-based program design language are detailed.
On expressing module interconnections in Ada
Authors: Grover Vinod
Published: October 2004

It is commonly believed that Ada lacks the facility to specify explicit import and export lists which are useful in specifying detailed interconnections of various modules. In this paper not only do we show that such requirements can be expressed in the language, but also that related issues of providing flexible linkages and enforcing precise detailed interfaces can be enforced by the use of the Ada language.
Authorisation and antichains
Authors: Crampton Jason , Loizou George
Published: October 2004

We present a summary of our recent work on partial orders and their application to access control modelling. In particular, we introduce a framework for separation of duty policies and a new access control model. We briefly discuss a special case of this model, HSS RBAC, which is our variation of a role-based access control model.
Realize network subsystem QoS guarantee
Authors: Wen Jun , Lu Xiang-liang
Published: October 2004

The increasing needs of high-speed networks have been limited by sending and receiving ends. Provision of network QoS guarantees necessitates appropriate support in the end systems, includes extensions to the communication subsystem and the underlying operating system. This paper focuses on the design of an implementation on new network architecture. It describes the designing approach on the user-level network architecture to guarantee network throughput,realize efficient data packet scheduling to ensure proper processing precedence,and use emulation way to ensure current thread's execution,reduce context switching overheads, which solve the problem of network QoS guarantee and priority inversion problem. Experiment shows that the new network outperforms traditional network greatly.
A Roll-Forward Recovery Scheme for Solving the Problem of Coasting Forward for Distributed Systems
Authors: Gupta B. , Banerjee S. K.
Published: October 2004

In this paper, a new index-based hybrid checkpointing scheme has been proposed to tackle the problem arising due to "coasting forward". This scheme uses both incremental and communication-induced checkpoints. Failures have been classified as hard and soft in order to take the advantage (i.e. possible reduction of rollback) which the incremental checkpoints offer, while designing the recovery approaches for these two types of failures. The presented theoretical results show that for soft failures, the recovery approach offers maximum roll-forward.
Collaboration and collaborative information technologies
Authors: Karsten Helena
Published: October 2004

Collaborative information technologies have been claimed to enhance collaboration in organizations, under certain conditions. This claim was found problematic in several respects, also in the light of the results of 18 case studies of Lotus Notes use, taken from the literature. The cases may be split into three groups: (1) exploratory, conservative, or cautious use; (2) planned and expanding use; and (3) extensive and engaged use of Notes. In the first group, no changes in work arrangements due to Notes use could be found. In the second group, the planned Notes applications supported the established work arrangements, both collaborative and hierarchical. Only in the third group were there significant changes towards more collaboration. These changes were due to a conscious and continued effort to bring about new work arrangements and new kinds of Notes support.A number of issues emerged in the review that could help to understand the relationship of collaborative information technologies and changes in work and organization. The issues included the role of the specific capabilities of the technology; the difference between technology as a product and technology-in-use; the kind of care needed in bringing about desired changes; the emergent, drifting nature of the change process; the role of the technology as a constructive tool in improvising and enacting the changes; and the gradual translations of influences from work practices to organizational practices.
Situated assessment of problems in software development
Authors: Iversen Jakob , Nielsen Peter Axel , Norbjerg Jacob
Published: October 2004

This paper reports on action research undertaken to understand and to improve the problems with software processes of a medium-sized Danish company. It is argued that, in order to understand what the specific problems are, we may, on the one hand, rely on normative process models like CMM or Bootstrap. On the other hand, we may also see the specific and unique features of software processes in a company through what we call "problem diagnosis." Problem diagnosis deals with eliciting problems perceived by software professionals and with forming commitment to enable software process improvement to effectively take place. A central purpose of problem diagnosis is to base the SPI project on the software developers' own perceptions of software process problems and suggestions for improvement rather than on the prescriptions and norms of a maturity model.
Designing computer systems with MEMS-based storage
Authors: Schlosser Steven W. , Griffin John Linwood , Nagle David F. , Ganger Gregory R.
Published: October 2004

For decades the RAM-to-disk memory hierarchy gap has plagued computer architects. An exciting new storage technology based on microelectromechanical systems (MEMS) is poised to fill a large portion of this performance gap, significantly reduce system power consumption, and enable many new applications. This paper explores the system-level implications of integrating MEMS-based storage into the memory hierarchy. Results show that standalone MEMS-based storage reduces I/O stall times by 4-74X over disks and improves overall application runtimes by 1.9-4.4X. When used as on-board caches for disks, MEMS-based storage improves I/O response time by up to 3.5X. Further, the energy consumption of MEMS-based storage is 10-54X less than that of state-of-the-art low-power disk drives. The combination of the high-level physical characteristics of MEMS-based storage (small footprints, high shock tolerance) and the ability to directly integrate MEMS-based storage with processing leads to such new applications as portable gigabit storage systems and ubiquitous active storage nodes.
Timestamp snooping
Authors: Martin Milo M. K. , Sorin Daniel J. , Ailamaki Anatassia , Alameldeen Alaa R. , Dickson Ross M. , Mauer Carl J. , Moore Kevin E. , Plakal Manoj , Hill Mark D. , Wood David A.
Published: October 2004

Symmetric muultiprocessor (SMP) servers provide superior performance for the commercial workloads that dominate the Internet. Our simulation results show that over one-third of cache misses by these applications result in cache-to-cache transfers, where the data is found in another processor's cache rather than in memory. SMPs are optimized for this case by using snooping protocols that broadcast address transactions to all processors. Conversely, directory-based shared-memory systems must indirectly locate the owner and sharers through a directory, resulting in larger average miss latencies.This paper proposes timestamp snooping, a technique that allows SMPs to i) utilize high-speed switched interconnection networks and ii) exploit physical locality by delivering address transactions to processors and memories without regard to order. Traditional snooping requires physical ordering of transactions. Timestamp snooping works by processing address transactions in a logical order. Logical time is maintained by adding a few bits per address transaction and having network switches perform a handshake to ensure on-time delivery. Processors and memories then reorder transactions based on their timestamps to establish a total order.We evaluate timestamp snooping with commercial workloads on a 16-processor SPARC system using the Simics full-system simulator. We simulate both an indirect (butterfly) and a direct (torus) network design. For OLTP, DSS, web serving, web searching, and one scientific application, timestamp snooping with the butterfly network runs 6-28% faster than directories, at a cost of 13-43% more link traffic. Similarly, with the torus network, timestamp snooping runs 6-29% faster for 17-37% more link traffic. Thus, timestamp snooping is worth considering when buying more interconnect bandwidth is easier than reducing interconnect latency.
Efficient and flexible value sampling
Authors: Burrows M. , Erlingsson Ú , Leung S-T. A. , Vandevoorde M. T. , Waldspurger C. A. , Walker K. , Weihl W. E.
Published: October 2004

This paper presents novel sampling-based techniques for collecting statistical profiles of register contents, data values, and other information associated with instructions, such as memory latencies. Values of interest are sampled in response to periodic interrupts. The resulting value profiles can be analyzed by programmers and optimizers to improve the performance of production uniprocessor and multiprocessor systems.Our value sampling system extends the DCPI continuous profiling infrastructure, and inherits many of its desirable properties: our value profiler has low overhead (approximately 10% slowdown); it profiles all the code in the system, including the operating system kernel; and it operates transparently, without requiring any modifications to the profiled code.
Architectural support for copy and tamper resistant software
Authors: Thekkath David Lie Chandramohan , Mitchell Mark , Lincoln Patrick , Boneh Dan , Mitchell John , Horowitz Mark
Published: October 2004

Although there have been attempts to develop code transformations that yield tamper-resistant software, no reliable software-only methods are know. This paper studies the hardware implementation of a form of execute-only memory (XOM) that allows instructions stored in memory to be executed but not otherwise manipulated. To support XOM code we use a machine that supports internal compartments---a process in one compartment cannot read data from another compartment. All data that leaves the machine is encrypted, since we assume external memory is not secure. The design of this machine poses some interesting trade-offs between security, efficiency, and flexibility. We explore some of the potential security issues as one pushes the machine to become more efficient and flexible. Although security carries a performance penalty, our analysis indicates that it is possible to create a normal multi-tasking machine where nearly all applications can be run in XOM mode. While a virtual XOM machine is possible, the underlying hardware needs to support a unique private key, private memory, and traps on cache misses. For efficient operation, hardware assist to provide fast symmetric ciphers is also required.
Architectural support for fast symmetric-key cryptography
Authors: Burke Jerome , McDonald John , Austin Todd
Published: October 2004

The emergence of the Internet as a trusted medium for commerce and communication has made cryptography an essential component of modern information systems. Cryptography provides the mechanisms necessary to implement accountability, accuracy, and confidentiality in communication. As demands for secure communication bandwidth grow, efficient cryptographic processing will become increasingly vital to good system performance.In this paper, we explore techniques to improve the performance of symmetric key cipher algorithms. Eight popular strong encryption algorithms are examined in detail. Analysis reveals the algorithms are computationally complex and contain little parallelism. Overall throughput on a high-end microprocessor is quite poor, a 600 Mhz processor is incapable of saturating a T3 communication line with 3DES (triple DES) encrypted data.We introduce new instructions that improve the efficiency of the analyzed algorithms. Our approach adds instruction set support for fast substitutions, general permutations, rotates, and modular arithmetic. Performance analysis of the optimized ciphers shows an overall speedup of 59% over a baseline machine with rotate instructions and 74% speedup over a baseline without rotates. Even higher speedups are demonstrated with optimized substitutions (SBOXes) and additional functional unit resources. Our analyses of the original and optimized algorithms suggest future directions for the design of high-performance programmable cryptographic processors.
Software profiling for hot path prediction
Authors: Duesterwald Evelyn , Bala Vasanth
Published: October 2004

Recently, there has been a growing interest in exploiting profile information in adaptive systems such as just-in-time compilers, dynamic optimizers and, binary translators. In this paper, we show that sophisticated software profiling schemes that provide highly accurate information in an offline setting are ill-suited for these dynamic code generation systems. We experimentally demonstrate that hot path predictions must be made early in order to control the rising cost of missed opportunity that result from the prediction delay. We also show that existing sophisticated path profiling schemes, if used in an online setting, offer no prediction advantages over simpler schemes that exhibit much lower runtime overheads.Based on these observation we developed a new low-overhead software profiling scheme for hot path prediction. Using an abstract metric we compare our scheme to path profile based prediction and show that our scheme achieves comparable prediction quality. In our second set of experiments we include runtime overhead and evaluate the performance of our scheme in a realistic application: Dynamo, a dynamic optimization system. The results show that our prediction scheme clearly outperforms path profile based prediction and thus confirm that
less
profiling as exhibited in our scheme will actually lead to
more
effective hot path prediction.
Hardware support for dynamic activation of compiler-directed computation reuse
Authors: Connors Daniel A. , Hunter Hillery C. , Cheng Ben-Chung , Hwu Wen-mei W.
Published: October 2004

Compiler-directed Computation Reuse (CCR) enhances program execution speed and efficiency by eliminating dynamic computation redundancy. In this approach, the compiler designates large program regions for potential reuse. During run time, the execution results of these reusable regions are recorded into hardware buffers for future reuse. Previous work shows that CCR can result in significant performance enhancements in general applications. A major limitation of the work is that the compiler relies on value profiling to identify reusable regions, making it difficult to deploy the scheme in many software production environments. This paper presents a new hardware model that alleviates the need for value profiling at compile time. The compiler is allowed to designate reusable regions that may prove to be inappropriate. The hardware mechanism monitors the dynamic behavior of compiler-designated regions and selectively activates the profitable ones at run time. Experimental results show that the proposed design makes more effective utilization of hardware buffer resources, achieves rapid employment of computation regions, and improves reuse accuracy, all of which promote more flexible compiler methods of identifying reusable computation regions.
Slipstream processors
Authors: Sundaramoorthy Karthik , Purser Zach , Rotenburg Eric
Published: October 2004

Processors execute the full dynamic instruction stream to arrive at the final output of a program, yet there exist shorter instruction streams that produce the same overall effect. We propose creating a shorter but otherwise equivalent version of the original program by removing ineffectual computation and computation related to highly-predictable control flow. The shortened program is run concurrently with the full program on a chip multiprocessor simultaneous multithreaded processor, with two key advantages:1)
Improved single-program performance.
The shorter program speculatively runs ahead of the full program and supplies the full program with control and data flow outcomes. The full program executes efficiently due to the communicated outcomes, at the same time validating the speculative, shorter program. The two programs combined run faster than the original program alone. Detailed simulations of an example implementation show an average improvement of 7% for the SPEC95 integer benchmarks.2)
Fault tolerance.
The shorter program is a subset of the full program and this partial-redundancy is transparently leveraged for detecting and recovering from transient hardware faults.
Segregating heap objects by reference behavior and lifetime
Authors: Seidl Matthew L. , Zorn Benjamin G.
Published: October 2004

Dynamic storage allocation has become increasingly important in many applications, in part due to the use of the object-oriented paradigm. At the same time, processor speeds are increasing faster than memory speeds and programs are increasing in size faster than memories. In this paper, we investigate efforts to predict heap object reference and lifetime behavior at the time objects are allocated. Our approach uses profile-based optimization, and considers a variety of different information sources present at the time of object allocation to predict the object's reference frequency and lifetime. Our results, based on measurements of six allocation intensive programs, show that program references to heap objects are highly predictable and that our prediction methods can successfully predict the behavior of these heap objects. We show that our methods can decrease the page fault rate of the programs measured, sometimes dramatically, in cases where the physical memory available to the program is constrained.
Schedule-independent storage mapping for loops
Authors: Strout Michelle Mills , Carter Larry , Ferrante Jeanne , Simon Beth
Published: October 2004

This paper studies the relationship between storage requirements and performance. Storage-related dependences inhibit optimizations for locality and parallelism. Techniques such as renaming and array expansion can eliminate all storage-related dependences, but do so at the expense of increased storage. This paper introduces the
universal occupancy vector
(UOV) for loops with a regular stencil of dependences. The UOV provides a schedule-independent storage reuse pattern that introduces no further dependences (other than those implied by true flow dependences). OV-mapped code requires less storage than full array expansion and only slightly more storage than schedule-dependent minimal storage.We show that determine if a vector is a UOV is NPcomplete. However, an easily constructed but possibly nonminimal UOV can be used. We also present a branch and bound algorithm which finds the minimal UOV, while still maintaining a legal UOV at all times.Our experimental results show that the use of OV-mapped storage, coupled with tiling for locality, achieves better performance than tiling after array expansion, and accommodates larger problem sizes than untilable, storage-optimized code. F'urthermore, storage mapping based on the UOV introduces negligible runtime overhead.
Space-time scheduling of instruction-level parallelism on a raw machine
Authors: Lee Walter , Barua Rajeev , Frank Matthew , Srikrishna Devabhaktuni , Babb Jonathan , Sarkar Vivek , Amarasinghe Saman
Published: October 2004

Increasing demand for both greater parallelism and faster clocks dictate that future generation architectures will need to decentralize their resources and eliminate primitives that require single cycle global communication. A Raw microprocessor distributes all of its resources, including instruction streams, register files, memory ports, and ALUs, over a pipelined two-dimensional mesh interconnect, and exposes them fully to the compiler. Because communication in Raw machines is distributed, compiling for instruction-level parallelism (ILP) requires both spatial instruction partitioning as well as traditional temporal instruction scheduling. In addition, the compiler must explicitly manage all communication through the interconnect, including the global synchronization required at branch points. This paper describes RAWCC, the compiler we have developed for compiling general-purpose sequential programs to the distributed Raw architecture. We present performance results that demonstrate that although Raw machines provide no mechanisms for global communication the Raw compiler can schedule to achieve speedups that scale with the number of available functional units.
VISA
Authors: Van Meter Rodney , Finn Gregory G. , Hotz Steve
Published: October 2004

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.
Dependence based prefetching for linked data structures
Authors: Roth Amir , Moshovos Andreas , Sohi Gurindar S.
Published: October 2004

We introduce a dynamic scheme that captures the accesspat-terns of linked data structures and can be used to predict future accesses with high accuracy. Our technique exploits the dependence relationships that exist between loads that produce addresses and loads that consume these addresses. By identzj+ing producer-consumer pairs, we construct a compact internal representation for the associated structure and its traversal. To achieve a prefetching eflect, a small prefetch engine speculatively traverses this representation ahead of the executing program. Dependence-based prefetching achieves speedups of up to 25% on a suite of pointer-intensive programs.
Cache-conscious data placement
Authors: Calder Brad , Krintz Chandra , John Simmi , Austin Todd
Published: October 2004

As the gap between memory and processor speeds continues to widen, cache eficiency is an increasingly important component of processor performance. Compiler techniques have been used to improve instruction cache pet$ormance by mapping code with temporal locality to different cache blocks in the virtual address space eliminating cache conflicts. These code placement techniques can be applied directly to the problem of placing data for improved data cache pedormance.In this paper we present a general framework for Cache Conscious Data Placement. This is a compiler directed approach that creates an address placement for the stack (local variables), global variables, heap objects, and constants in order to reduce data cache misses. The placement of data objects is guided by a temporal relationship graph between objects generated via profiling. Our results show that profile driven data placement significantly reduces the data miss rate by 24% on average.
Variable length path branch prediction
Authors: Stark Jared , Evers Marius , Patt Yale N.
Published: October 2004

Accurate branch prediction is required to achieve high performance in deeply pipelined, wide-issue processors. Recent studies have shown that conditional and indirect (or computed) branch targets can be accuratelypredicted by recording the path, which consists of the target addresses of recent branches, leading up to the branch. In current path based branch predictors, the
N
most recent target addresses are hashed together to form an index into a table, where
N
is some fixed integer. The indexed table entry isused to make a prediction for the current branch.This paper introduces a new branch predictor in which the value of
N
is allowed to vary. By constructing the index into the table using the last
N
target addresses, and using profiling information to select the proper value of
N
for each branch, extremely accurate branch prediction is achieved. For the SPECint95 gee benchmark, this new predictor has a conditional branch misprediction rate of 4.3% given a 4K byte hardware budget. For comparison, the gshare predictor, a predictor known for its high accuracy, has a conditional branch misprediction rate of 8.8% given the same hardware budget. For the indirect branches in gee, the new predictor achieves a misprediction rate of 27.7% when given a hardware budget of 512 bytes, whereas the best competingpredictor achieves a misprediction rate of 44.2% when given the same hardware budget.
Performance isolation
Authors: Verghese Ben , Gupta Anoop , Rosenblum Mendel
Published: October 2004

Shared-memory multiprocessors (SMPs) are being extensively used as general-purpose servers. The tight coupling of multiple processors, memory, and I/O provides enormous computing power in a single system, and enables the efficient sharing of these resources.The operating systems for these machines (UNIX or Windows NT) provide very few controls for sharing the resources of the system among the active tasks or users. This unconstrained sharing model is a serious limitation for a server because the load placed by one user can adversely affect other users' performance in an unpredictable manner. We show that this lack of isolation is caused by the resource allocation scheme (or lack thereof) carried over from singleuser workstations. Multi-user multiprocessor systems require more sophisticated resource management, and we show how the proposed "performance isolation" scheme can address the current weaknesses of these systems. We have implemented performance isolation in the Silicon Graphics IRIX operating system for three important system resources: CPU time, memory, and disk bandwidth. Running a number of workloads we show that our proposed scheme is successful at providing workstation-like isolation under heavy load, SMP-like latency under light load, and SMP-like throughput in all cases.
Precise miss analysis for program transformations with caches of arbitrary associativity
Authors: Ghosh Somnath , Martonosi Margaret , Malik Sharad
Published: October 2004

Analyzing and optimizing program memory performance is a pressing problem in high-performance computer architectures. Currently, software solutions addressing the processor-memory performance gap include compiler-or programmer-applied optimizations like data structure padding, matrix blocking, and other program transformations. Compiler optimization can be effective, but the lack of
precise
analysis and optimization frameworks makes it impossible to confidently make optimal, rather than heuristic-based, program transformations. Imprecision is most problematic in situations where hard-to-predict cache conflicts foil heuristic approaches. Furthermore, the lack of a
general
framework for compiler memory performance analysis makes it impossible to understand the combined effects of several program transformations.The Cache Miss Equation (CME) framework discussed in this paper addresses these issues. We express memory reference and cache conflict behavior in terms of sets of equations. The mathematical precision of CMEs allows us to find true optimal solutions for transformations like blocking or padding. The generality of CMEs also allows us to reason about interactions between transformations applied in concert. Unlike our prior work, this framework applies to caches of arbitrary associativity. This paper also demonstrates the utility of CMEs by presenting precise algorithms for intra-variable padding, inter-variable padding, and selecting tile sizes. Our experiences with CMEs implemented in the SUIF system show that they are a unifying mathematical framework offering the generality and precision imperative for compiler optimizations on current high-performance architectures.
Capturing dynamic memory reference behavior with adaptive cache topology
Authors: Peir Jih-Kwon , Lee Yongjoon , Hsu Windsor W.
Published: October 2004

Memory references exhibit locality and are therefore not uniformly distributed across the sets of a cache. This skew reduces the effectiveness of a cache because it results in the caching of a considerable number of less-recently-used lines which are less likely to be re-referenced before they are replaced. In this paper, we describe a technique that dynamically identifies these less-recently-used lines and effectively utilizes the cache frames they occupy to more accurately approximate the global least-recently-used replacement policy while maintaining the fast access time of a direct-mapped cache. We also explore the idea of using these underutilized cache frames to reduce cache misses through data prefetching. In the proposed design, the possible locations that a line can reside in is not predetermined. Instead, the cache is dynamically partitioned into groups of cache lines. Because both the total number of groups and the individual group associativity adapt to the dynamic reference pattern, we call this design the adaptive group-associative cache. Performance evaluation using trace-driven simulations of the TPC-C benchmark and selected programs from the SPEC95 benchmark suite shows that the group-associative cache is able to achieve a hit ratio that is consistently better than that of a 4-way set-associative cache. For some of the workloads, the hit ratio approaches that of a fully-associative cache.
Value speculation scheduling for high performance processors
Authors: Fu Chao-Ying , Jennings Matthew D. , Larin Sergei Y. , Conte Thomas M.
Published: October 2004

Recent research in value prediction shows a surprising amount of predictability for the values produced by register-writing instructions. Several hardware based value predictor designs have been proposed to exploit this predictability by eliminating flow dependencies for highly predictable values. This paper proposed a hardware and software based scheme for value speculation scheduling (VSS). Static VLIW scheduling techniques are used to speculate value dependent instructions by scheduling them above the instructions whose results they are dependent on. Prediction hardware is used to provide value predictions for allowing the execution of speculated instructions to continue. In the case of miss-predicted values, control flow is redirected to patch-up code so that execution can proceed with the correct results. In this paper, experiments in VSS for load operations in the SPECint95 benchmarks are performed. Speedup of up to 17% has been shown for using VSS. Empirical results on the value predictability of loads, based on value profiling data, are also provided.
A look at several memory management units, TLB-refill mechanisms, and page table organizations
Authors: Jacob Bruce L. , Mudge Trevor N.
Published: October 2004

Virtual memory is a staple in modem systems, though there is little agreement on how its functionality is to be implemented on either the hardware or software side of the interface. The myriad of design choices and incompatible hardware mechanisms suggests potential performance problems, especially since increasing numbers of systems (even embedded systems) are using memory management. A comparative study of the implementation choices in virtual memory should therefore aid system-level designers.This paper compares several virtual memory designs, including combinations of hierarchical and inverted page tables on hardware-managed and software-managed translation lookaside buffers (TLBs). The simulations show that systems are fairly sensitive to TLB size; that interrupts already account for a large portion of memory-management overhead and can become a significant factor as processors execute more concurrent instructions; and that if one includes the cache misses inflicted on applications by the VM system, the total VM overhead is roughly twice what was thought (10--20% rather than 5--10%).
Gypsy
Authors: Ambler Allen L. , Good Donald I. , Browne James C. , Burger Wilhelm F. , Cohen Richard M. , Hoch Charles G. , Wells Robert E.
Published: October 2004

An introduction to the Gypsy programming and specification language is given. Gypsy is a high-level programming language with facilities for general programming and also for systems programming that is oriented toward communications processing. This includes facilities for concurrent processes and process synchronization. Gypsy also contains facilities for detecting and processing errors that are due to the actual running of the program in an imperfect environment. The specification facilities give a precise way of expressing the desired properties of the Gypsy programs. All of the features of Gypsy are fully verifiable, either by formal proof or by validation at run time. An overview of the language design and a detailed example program are given.
Aspects of applicative programming for file systems (Preliminary Version)
Authors: Friedman Daniel P. , Wise David S.
Published: October 2004

This paper develops the implications of recent results in semantics for applicative programming. Applying suspended evaluation (call-by-need) to the arguments of file construction functions results in an implicit synchronization of computation and output. The programmer need not participate in the determination of the pace and the extent of the evaluation of his program. Problems concerning multiple input and multiple output files are considered: typical behavior is illustrated with an example of a rudimentary text editor written applicatively. As shown in the trace of this program, the driver of the program is the sequential output device(s). Implications of applicative languages for I/O bound operating systems are briefly considered.
Some extensions to algebraic specifications
Authors: Guttag Jhon V. , Horowitz Ellis , Musser David R.
Published: October 2004

Algebraic specifications of abstract data types are beginning to gain wide currency. In this paper we discuss an extension to this specification technique which allows the specification of procedures which alter their parameters, and various ways of handling the specification of error conditions.
Restricted data types, specification and enforcement of invariant properties of variables
Authors: Buckle Normand
Published: October 2004

When defining a data type, it is often useful to specify restrictions on the permitted values of that type.

Pascal's subrange type declaration, a special case of this kind of constraint definition, has already proved itself to be quite useful. Restricted data types allow more complex constraints to be defined and checked; for example, a variable could be declared of type “odd integer” or the day field of a “date” type variable could be checked for consistency with the year and month fields.

A simple mechanism is proposed, allowing the formulation of such constraints and their association with data types; the behaviour of a restricted type variable is described. The effects of the use of such a mechanism on program reliability, readability and efficiency are discussed.
An experimental investigation of the effect of program structure on program understanding
Authors: Love Tom
Published: October 2004

A within-subjects experimental design was used to test the effect of two variables on program understanding. The independent variables were complexity of control flow and paragraphing of the source code. Understanding was measured by having the subjects memorize the code for a fixed time and reconstruct the code verbatim. Also some subjects were asked to describe the function of the program after completing their reconstruction. The two groups of subjects for the experiment were students from an introductory programming class and from a graduate class in programming languages.

The major findings were that paragraphing of the source had no effect for either group of subjects but that programs with simplified control flow were easier for the computer science students to understand as measured by their ability to reconstruct the programs. The dependent variable, rated accuracy of their description of the programs functions, did not differ as a function of either independent variable.

The paper is concluded with a description of the utility of this experimental approach relative to improving the reliability of software and a discussion of the importance of these findings.
Abstraction mechanisms in CLU
Authors: Liskov Barbara , Snyder Alan , Atkinson Russell , Schaffert Craig
Published: October 2004

CLU is a new programming language designed to support the use of abstractions in program construction. Work in programming methodology has led to the realization that three kinds of abstractions, procedural, control, and especially data abstractions, are useful in the programming process. Of these, only the procedural abstraction is supported well by conventional languages, through the procedure or subroutine. CLU provides, in addition to procedures, novel linguistic mechanisms that support the use of data and control abstractions.

This paper provides an introduction to the abstraction mechanisms in CLU. By means of programming examples, we illustrate the utility of the three kinds of abstractions in program construction and show how CLU programs may be written to use and implement abstractions. We also discuss the CLU library, which permits incremental program development with complete type-checking performed at compile-time.
An experimental evaluation of data types on programming reliability
Authors: Gannon J. D.
Published: October 2004

The language in which programs are written can have a substantial effect on the reliability of the resulting programs. This paper discusses an experiment that compares the programming reliability of subjects using a statically-typed language and a “typeless” language. Analysis of the number of errors and the number of runs containing errors shows that, at least in one environment, the use of a statically-typed language can increase programming reliability. Detailed analysis of the errors made by the subjects in programming solutions to reasonably small problems shows that the subjects had difficulty manipulating the representation of data.