bluuebunny/crossref_metadata_2025 huggingface dataset:
Reducing the cost of branches by using registers
Authors: Davidson Jack W. , Whalley David B.
Published: July 2004

In an attempt to reduce the number of operand memory references, many RISC machines have thirty-two or more general-purpose registers (e.g., MIPS, ARM, Spectrum, 88K). Without special compiler optimizations, such as inlining or interprocedural register allocation, it is rare that a compiler will use a majority of these registers for a function. This paper explores the possibility of using some of these registers to hold branch target addresses and the corresponding instruction at each branch target. To evaluate the effectiveness of this scheme, two machines were designed and emulated. One machine had thirty-two general-purpose registers used for data references, while the other machine had sixteen data registers and sixteen registers used for branching. The results show that using registers for branching can effectively reduce the cost of transfers of control.
VAX vector architecture
Authors: Bhandarkar Dileep , Brunner Richard
Published: July 2004

The VAX Architecture has been extended to include an integrated, register-based vector processor. This extension allows both high-end and low-end implementations and can be supported with only small changes by VAX/VMS and VAX/ULTRIX operating systems. The extension is effectively exploited by the new vectorizing capabilities of VAX FORTRAN. Features of the VAX Vector Architecture and the design decisions which make it a consistent extension of the VAX Architecture are discussed.
Performance of an OLTP application on symmetry multiprocessor system
Authors: Thakkar Shreekant S. , Sweiger Mark
Published: July 2004

Sequent's Symmetry Series is a bus-based shared-memory multiprocessor. System performance in an OLTP relational database application was investigated using the TP1 benchmark. System performance was tested with fully-cached benchmarks and with scaled benchmarks. In fully-cached tests, the entire database fits inside main memory. In scaled tests, the database is larger than available memory. In the fully-cached benchmark, performance was initially limited by bus saturation. The cause was the transfer of process context from processor to processor. This was eliminated by assigning each process to a processor. Processor affinity was combined with reductions in message-passing within the database. Throughput was dramatically improved. The scaled tests were I/O bound. This bottleneck can be eliminated by connecting more disk drives, or by increasing the main memory size.
Trace-driven simulations for a two-level cache design in open bus systems
Authors: Bugge Håkon O. , Kristiansen Ernst H. , Bakka Bjørn O.
Published: July 2004

Two-level cache hierarchies will be a design issue in future high-performance CPUs. In this paper we evaluate various metrics for data cache
*
designs. We discuss both one- and two-level cache hierarchies. Our target is a new 100+
mips
CPU, but the methods are applicable to any cache design. The basis of our work is a new trace-driven, multiprocess cache simulator. The simulator incorporates a simple priority-based scheduler which controls the execution of the processes. The scheduler blocks a process when a system call is executed. A workload consists of a total of 60 processes, distributed among seven unique programs with about nine instances each. We discuss two open bus systems supporting a coherent memory model, Futurebus+ and SCI, as the interconnect system for main memory.
Fast Prolog with an extended general purpose architecture
Authors: Holmer Bruce K. , Sano Barton , Carlton Michael , Van Roy Peter , Haygood Ralph , Bush William R. , Despain Alvin M. , Pendleton Joan M. , Dobry Tep
Published: July 2004

Most Prolog machines have been based on specialized architectures. Our goal is to start with a general purpose architecture and determine a minimal set of extensions for high performance Prolog execution. We have developed both the architecture and optimizing compiler simultaneously, drawing on results of previous implementations. We find that most Prolog specific operations can be done satisfactorily in software; however, there is a crucial set of features that the architecture must support to achieve the best Prolog performance. The emphasis of this paper is on our architecture and instruction set. The costs and benefits of the special architectural features and instructions are analyzed. Simulated performance results are presented and indicate a peak compiled Prolog performance of 3.68 million logical inferences per second.
Architectural support for the management of tightly-coupled fine-grain goals in flat concurrent Prolog
Authors: Alkalaj Leon , Lang Tomás , Ercegovac Miloš
Published: July 2004

We propose architectural support for goal management as part of a special-purpose processor architecture for the efficient execution of Flat Concurrent Prolog. Goal management operations: halt, spawn, suspend and commit are decoupled from goal reduction, and overlapped in the Goal Management Unit. Their efficient execution is enabled using a Goal Cache. We evaluate the performance of the goal management support using an analytic performance model and program parameters characteristic of the System's Development Workload. Most goal management operations are completely overlapped, resulting in a speedup of 2. Higher speedups are obtained for workloads that exhibit greater goal management complexity.
Balance in architectural design
Authors: Ho Samuel , Snyder Lawrence
Published: July 2004

We introduce a performance metric,
normalized time,
which is closely related to such measures as the area-time product of VLSI theory and the price / performance ratio of advertising literature. This metric captures the idea of a piece of hardware “pulling its own weight,” i.e. contributing as much to performance as it costs in resources. We then prove general theorems for stating when the size of a given part is in balance with its utilization, and give specific formulas for commonly found linear and quadratic devices. We also apply these formulas to an analysis of a specific processor element, and discuss the implications for bit-serial
vs
word-parallel, RISC
vs
CISC, and VLIW designs.
A study of I/O behavior of perfect benchmarks on a multiprocessor
Authors: Reddy A. L. Narasimha , Banerjee Prithviraj
Published: July 2004

The I/O behavior of some scientific applications, a subset of Perfect benchmarks, executing on a multiprocessor is studied. The aim of this study is to explore the various patterns of I/O access of large scientific applications and to understand the impact of this observed behavior on the I/O subsystem architecture. I/O behavior of the program is characterized by the demands it imposes on the I/O subsystem. It is observed that implicit I/O or paging is not a major problem for the applications considered and the I/O problem is mainly manifest in the explicit I/O done in the program. Various characteristics of I/O accesses are studied and their impact on architecture design is discussed.
Maximizing performance in a striped disk array
Authors: Chen Peter M. , Patterson David A.
Published: July 2004

Improvements in disk speeds have not kept up with improvements in processor and memory speeds. One way to correct the resulting speed mismatch is to stripe data across many disks. In this paper, we address how to stripe data to get maximum performance from the disks. Specifically, we examine how to choose the striping unit, i.e. the amount of logically contiguous data on each disk. We synthesize rules for determining the best striping unit for a given range of workloads.

We show how the choice of striping unit depends on only two parameters: 1) the number of outstanding requests in the disk system at any given time, and 2) the average positioning time × data transfer rate of the disks. We derive an equation for the optimal striping unit as a function of these two parameters; we also show how to choose the striping unit without prior knowledge about the workload.
A distributed I/O architecture for HARTS
Authors: Shin Kang G. , Dykema Greg
Published: July 2004

The issue of I/O device access in HARTS — a distributed real-time computer system under construction at the Real-Time Computing Laboratory (RTCL), The University of Michigan — is explicitly addressed. Several candidate solutions are introduced, explored, and evaluated according to cost and complexity, reliability, and performance: (1) “node-direct” distribution with the intra-node bus and a local I/O bus, (2) use of dedicated I/O nodes which are placed in the hexagonal mesh as regular applications nodes but which provide I/O services rather than computing services, and (3) use of a separate I/O network which has led to the proposal of an “interlaced” I/O network. The interlaced I/O network is intended to provide both high performance without burdening node processors with I/O overhead as well as a high degree of reliability. Both static and dynamic multi-ownership protocols are developed for managing I/O device access in this I/O network. The relative merits of the two protocols are explored and the performance and accessibility which each provide are simulated.
Better than one operation per clock (panel)
Authors: Fisher Joseph A. , Grohoski Greg , Patt Yale , Smith J. E. , Stiles David R.
Published: July 2004

In the 1980s, considerable advances were made in both software and hardware technology, and CPUs that can issue no more than one operation per clock cycle are rapidly approaching this barrier. Further improvements to uniprocessor performance can be obtained by enhancing the architecture of the CPU to allow multiple operations to be issued in a single clock cycle. The focus of this panel is to discuss three architectural approaches to issuing multiple operations per cycle: (i) vector instructions, (ii) very long instruction words (VLIW), and (iii) superscalar execution. We have asked the panelists to address several issues from the vantage point of their preferred architectural approach. These include:

What operation set parallelism are you trying to exploit (as distinct from instruction set parallelism)?

How does mapping from your operation set to your instruction set enhance or restrict the ability to support this parallelism?

What are the performance optimization responsibilities of the compiler?

How well does your architecture tolerate possible run time uncertainties (cache miss, resource conflicts, dependencies, …) in the context of uniprocessor or multiprocessor systems?

What are the inherent advantages/disadvantages of your architectural approach over the others?

What further enhancements do you envision in the future? How will these affect the choice of architectural approach?
Correction to RAMpage ASPOLOS paper
Authors: Machanick Phillip
Published: July 2004

This paper contains corrections to published results on the RAMpage memory hierarchy. The originally published results contained erroneous values for cache miss penalties for a conventional cache architecture against which the RAMpage hierarchy was being compared. The incorrect results showed that RAMpage with context switches on misses to DRAM had similar performance to a conventional 2-way associative L2 cache-based hierarchy. The corrected results show that the RAMpage hierarchy in fact outperforms a conventional 2-way associative cache hierarchy by up to 29%, for the measured variations.
Design of high performance RAID in real-time system
Authors: Cheng Peng , Jin Hai , Zhang Jiangling
Published: July 2004

In this paper, we design a high performance RAID (
Redundant Arrays of Independent Disks
), called HUST_RAID, in real-time system. First, we give the architecture and the real-time process model of HUST_RAID. On the study of real-time disk I/O scheduling algorithm, we design a multiple queues real-time I/O scheduling algorithm. A new buffer management policy used in HUST_RAID is also given. It is the combination of some advanced technologies. We also introduce the design of software of the control system, which implements request receiving and decomposing, buffer management, data reconstruction, data rebuilding etc. A last, the performance of HUST_RAID is measured. From the testing results, the performance of HUST_RAID system is very excellent
Architectural support for the cache based vector computation
Authors: Yuen C. K.
Published: July 2004

The possibility of providing vector computation support to microprocessors is studied. It is suggested that frame registers pointing to vector elements stored in the cache can be used to stream data to and from vector arithmetic pipelines.
A methodology for performance evaluation of systems with large emulation code
Authors: Khalid Humayun
Published: July 2004

Emulation affects accurate performance evaluation of applications running on the present generation of computing machines. The emulation code from present generation of machines is often passed onto the traces which when used for the trace-driven performance evaluation of the next generation of architectures results in highly incorrect evaluations. The scenario captured by the trace may be real. However, one major problem associated with such a reality is that if such traces are used for future systems design, the underlying Implicit assumption will be that the emulation problem will persist with the same degree of impact. This novel paper presents the performance evaluation problem and solutions associated with a lot of computer systems executing relatively large amount of emulation code. As a case study, we have looked at the 68k emulation code problem on Apple's Macintosh computers for today's benchmarks. We have also attempted to explore the impact of the problem and alleviate it using novel techniques.
Performance evaluation of two operating systems
Authors: Khalid Humayun
Published: July 2004

This report compares the performance of two radically different versions of MacOS™ operating system. In particular, we are interested in the study that focuses primarily on the emulation code related aspect of the performance of two version of the aforementioned operating system. ALPS (Application Level Performance Measurement Suite) benchmarks [1] were used as test cases due to the fact that they contains scenarios which stresses the operating system (OS) related activities.
A scalable approach to thread-level speculation
Authors: Steffan J. Greggory , Colohan Christopher B. , Zhai Antonia , Mowry Todd C.
Published: July 2004

While architects understand how to build cost-effective parallel machines across a wide spectrum of machine sizes (ranging from within a single chip to large-scale servers), the real challenge is how to easily create
parallel software
to effectively exploit all of this raw performance potential. One promising technique for overcoming this problem is
Thread-Level Speculation (TLS),
which enables the compiler to optimistically create parallel threads despite uncertainty as to whether those threads are actually independent. In this paper, we propose and evaluate a design for supporting TLS that seamlessly scales to any machine size because it is a straightforward extension of writeback invalidation-based cache coherence (which itself scales both up and down). Our experimental results demonstrate that our scheme performs well on both single-chip multiprocessors and on larger-scale machines where communication latencies are twenty times larger.
Transient fault detection via simultaneous multithreading
Authors: Reinhardt Steven K. , Mukherjee Shubhendu S.
Published: July 2004

Smaller feature sizes, reduced voltage levels, higher transistor counts, and reduced noise margins make future generations of microprocessors increasingly prone to transient hardware faults. Most commercial fault-tolerant computers use fully replicated hardware components to detect microprocessor faults. The components are lockstepped (cycle-by-cycle synchronized) to ensure that, in each cycle, they perform the same operation on the same inputs, producing the same outputs in the absence of faults. Unfortunately, for a given hardware budget, full replication reduces performance by statically partitioning resources among redundant operations.

We demonstrate that a Simultaneous and Redundantly Threaded (SRT) processor—derived from a Simultaneous Multithreaded (SMT) processor—provides transient fault coverage with significantly higher performance. An SRT processor provides transient fault coverage by running identical copies of the same program simultaneously as independent threads. An SRT processor provides higher performance because it dynamically schedules its hardware resources among the redundant copies. However, dynamic scheduling makes it difficult to implement lockstepping, because corresponding instructions from redundant threads may not execute in the same cycle or in the same order.

This paper makes four contributions to the design of SRT processors. First, we introduce the concept of the
sphere of replication,
which abstracts both the physical redundancy of a lockstepped system and the logical redundancy of an SRT processor. This framework aids in identifying the scope of fault coverage and the input and output values requiring special handling. Second, we identify two viable spheres of replication in an SRT processor, and show that one of them provides fault detection while checking only committed stores and uncached loads. Third, we identify the need for consistent replication of load values, and propose and evaluate two new mechanisms for satisfying this requirement. Finally, we propose and evaluate two mechanisms—slack fetch and branch outcome queue—that enhance the performance of an SRT processor by allowing one thread to prefetch cache misses and branch results for the other thread. Our results with 11 SPEC95 benchmarks show that an SRT processor can outperform an equivalently sized, on-chip, hardware-replicated solution by 16% on average, with a maximum benefit of up to 29%.
A hardware mechanism for dynamic extraction and relayout of program hot spots
Authors: Merten Matthew C. , Trick Andrew R. , Nystrom Erik M. , Barnes Ronald D. , Hmu Wen-mei W.
Published: July 2004

This paper presents a new mechanism for collecting and deploying runtime optimized code. The code-collecting component resides in the instruction retirement stage and lays out hot execution paths to improve instruction fetch rate as well as enable further code optimization. The code deployment component uses an extension to the Branch Target Buffer to migrate execution into the new code without modifying the original code. No significant delay is added to the total execution of the program due to these components. The code collection scheme enables safe runtime optimization along paths that span function boundaries. This technique provides a better platform for runtime optimization than trace caches, because the traces are longer and persist in main memory across context switches. Additionally, these traces are not as susceptible to transient behavior because they are restricted to frequently executed code. Empirical results show that on average this mechanism can achieve better instruction fetch rates using only 12KB of hardware than a trace cache requiring 15KB of hardware, while producing long, persistent traces more suited to optimization.
Energy-driven integrated hardware-software optimizations using SimplePower
Authors: Vijaykrishnan N. , Kandemir M. , Irwin M. J. , Kim H. S. , Ye W.
Published: July 2004

With the emergence of a plethora of embedded and portable applications, energy dissipation has joined throughput, area, and accuracy/precision as a major design constraint. Thus, designers must be concerned with both optimizing and estimating the energy consumption of circuits, architectures, and software. Most of the research in energy optimization and/or estimation has focused on single components of the system and has not looked across the interacting spectrum of the hardware and software. The novelty of our new energy estimation framework,
SimplePower
, is that it evaluates the energy considering the system as a whole rather than just as a sum of parts, and that it concurrently supports both compiler and architectural experimentation.

We present the design and use of the
SimplePower
framework that includes a transition-sensitive, cycle-accurate datapath energy model that interfaces with analytical and transition sensitive energy models for the memory and bus subsystems, respectively. We analyzed the energy consumption of ten codes from the multidimensional array domain, a domain that is important for embedded video and signal processing systems, after applying different compiler and architectural optimizations. Our experiments demonstrate that early estimates from the
SimplePower
energy estimation framework can help identify the system energy hotspots and enable architects and compiler designers to focus their efforts on these areas.
An embedded DRAM architecture for large-scale spatial-lattice computations
Authors: Margolus Norman
Published: July 2004

Spatial-lattice computations with finite-range interactions are an important class of easily parallelized computations. This class includes many simple and direct algorithms for physical simulation, virtual-reality simulation, agent-based modeling, logic simulation, 2D and 3D image processing and rendering, and other volumetric data processing tasks. The range of applicability of such algorithms is completely dependant upon the lattice-sizes and processing speeds that are computationally feasible. Using embedded DRAM and a new technique for organizing SIMD memory and communications we can efficiently utilize 1 Tbit/sec of sustained memory bandwidth in each chip in an indefinitely scalable array of chips. This allows a 10,000-fold speedup per memory chip for these algorithms compared to the CAM-8 lattice gas computer, and is about one million times faster per memory chip for these calculations than a CM-2.
Smart Memories
Authors: Mai Ken , Paaske Tim , Jayasena Nuwan , Ho Ron , Dally William J. , Horowitz Mark
Published: July 2004

Trends in VLSI technology scaling demand that future computing devices be narrowly focused to achieve high performance and high efficiency, yet also target the high volumes and low costs of widely applicable general purpose designs. To address these conflicting requirements, we propose a modular reconfigurable architecture called Smart Memories, targeted at computing needs in the 0.1μ technology generation. A Smart Memories chip is made up of many processing tiles, each containing local memory, local interconnect, and a processor core. For efficient computation under a wide class of possible applications, the memories, the wires, and the computational model can all be altered to match the applications. To show the applicability of this design, two very different machines at opposite ends of the architectural spectrum, the Imagine stream processor and the Hydra speculative multiprocessor, are mapped onto the Smart Memories computing substrate. Simulations of the mappings show that the Smart Memories architecture can successfully map these architectures with only modest performance degradation.
On the value locality of store instructions
Authors: Lepak Kevin M. , Lipasti Mikko H.
Published: July 2004

Value locality, a recently discovered program attribute that describes the likelihood of the recurrence of previously-seen program values, has been studied enthusiastically in the recent published literature. Much of the energy has focused on refining the initial efforts at predicting load instruction outcomes, with the balance of the effort examining the value locality of either all register-writing instructions, or a focused subset of them. Surprisingly, there has been very little published characterization of or effort to exploit the value locality of data words stored to memory by computer programs. This paper presents such a characterization, proposes both memory-centric (based on message passing) and producer-centric (based on program structure) prediction mechanisms for stored data values, introduces the concept of silent stores and new definitions of multiprocessor false sharing based on these observations, and suggests new techniques for aligning cache coherence protocols and microarchitectural store handling techniques to exploit the value locality of stores. We find that realistic implementations of these techniques can significantly reduce multiprocessor data bus traffic and are more effective at reducing address bus traffic than the addition of Exclusive state to a MSI coherence protocol. We also show that squashing of silent stores can provide uniprocessor speedups greater than the addition of store-to-load forwarding.
Performance analysis of the Alpha 21264-based Compaq ES40 system
Authors: Cvetanovic Zarka , Kessler R. E.
Published: July 2004

This paper evaluates performance characteristics of the Compaq ES40 shared memory multiprocessor. The ES40 system contains up to four Alpha 21264 CPU's together with a high-performance memory system. We qualitatively describe architectural features included in the 21264 microprocessor and the surrounding system chipset. We further quantitatively show the performance effects of these features using benchmark results and profiling data collected from industry-standard commercial and technical workloads. The profile data includes basic performance information - such as instructions per cycle, branch mispredicts, and cache misses - as well as other data that specifically characterizes the 21264. Wherever possible, we compare and contrast the ES40 to the AlphaServer 4100 - a previous-generation Alpha system containing four Alpha 21164 microprocessors - to highlight the architectural advances in the ES40. We find that the Compaq ES40 often provides 2 to 3 times the performance of the AlphaServer 4100 at similar clock frequencies. We also find that the ES40 memory system has about five times the memory bandwidth of the 4100. These performance improvements come from numerous microprocessor and platform enhancements, including out-of-order execution, branch prediction, functional units, and the memory system.
Reconfigurable caches and their application to media processing
Authors: Ranganathan Parthasarathy , Adve Sarita , Jouppi Norman P.
Published: July 2004

High performance general-purpose processors are increasingly being used for a variety of application domains - scientific, engineering, databases, and more recently, media processing. It is therefore important to ensure that architectural features that use a significant fraction of the on-chip transistors are applicable across these different domains. For example, current processor designs often devote the largest fraction of on-chip transistors (up to 80%) to caches. Many workloads, however, do not make effective use of large caches; e.g., media processing workloads which often have streaming data access patterns and large working sets.

This paper proposes a new
reconfigurable cache
design. This design enables the cache SRAM arrays to be dynamically divided into multiple partitions that can be used for different processor activities. These activities can benefit applications that would otherwise not use the storage allocated to large conventional caches. Our design involves relatively few modifications to conventional cache design, and analysis using a modification of the CACTI analytical model shows a small impact on cache access time. We evaluate one representative use of reconfigurable caches - instruction reuse for media processing. We find this use gives IPC improvements ranging from 1.04X to 1.20X in simulation across eight media processing benchmarks.
Instruction path coprocessors
Authors: Chou Yuan , Shen John Paul
Published: July 2004

This paper presents the concept of an Instruction Path Coprocessor (I-COP), which is a programmable on-chip coprocessor, with its own mini-instruction set, that operates on the core processor's instructions to transform them into an internal format that can be more efficiently executed. It is located off the critical path of the core processor to ensure that it does not negatively impact the core processor's cycle time or pipeline depth. An I-COP is highly versatile and can be used to implement different types of instruction transformations to enhance the IPC of the core processor. We study four potential applications of the I-COP to demonstrate the feasibility of this concept and investigate the design issues of such a coprocessor. A prototype instruction set for the I-COP is presented along with an implementation framework that facilitates achieving high I-COP performance. Initial results indicate that the I-COP is able to efficiently implement the trace cache fill unit as well as the register move, stride data prefetching and linked data structure prefetching trace optimizations.
Allowing for ILP in an embedded Java processor
Authors: Radhakrishnan Ramesh , Talla Deependra , John Lizy Kurian
Published: July 2004

Java processors are ideal for embedded and network computing applications such as Internet TV's, set-top boxes, smart phones, and other consumer electronics applications. In this paper, we investigate cost-effective microarchitectural techniques to exploit parallelism in Java bytecode streams. Firstly, we propose the use of a fill unit that stores decoded bytecodes into a decoded bytecode cache. This mechanism improves the fetch and decode bandwidth of Java processors by 2 to 3 times. These additional hardware units can also be used to perform optimizations such as instruction folding. This is particularly significant because experiments with the Verilog model of Sun Microsystems pico Java-II core demonstrates that instruction folding lies in the critical path. Moving folding logic from the critical path of the processor to the fill unit allows to improve the clock frequency by 25%. Out-of-order ILP exploitation is not investigated due to the prohibitive cost, but in-order dual-issue with a 64-entry decoded bytecode cache is seen to result in 10% to 14% improvement in execution cycles. Another contribution of the paper is a stack disambiguation technique that allows elimination of false dependencies between different types of stack accesses. Stack disambiguation further exposes parallelism and a dual in-order issue microengine with a 64-entry bytecode cache yields an additional 10% reduction in cycles, leading to an aggregate reduction of 17% to 24% in execution cycles.
Multiple-banked register file architectures
Authors: Cruz José-Lorenzo , González Antonio , Valero Mateo , Topham Nigel P.
Published: July 2004

The register file access time is one of the critical delays in current superscalar processors. Its impact on processor performance is likely to increase in future processor generations, as they are expected to increase the issue width (which implies more register ports) and the size of the instruction window (which implies more registers), and to use some kind of multithreading. Under this scenario, the register file access time could be a dominant delay and a pipelined implementation would be desirable to allow for high clock rates.

However, a multi-stage register file has severe implications for processor performance (e.g. higher branch misprediction penalty) and complexity (more levels of bypass logic). To tackle these two problems, in this paper we propose a register file architecture composed of multiple banks. In particular we focus on a multi-level organization of the register file, which provides low latency and simple bypass logic. We propose several caching policies and prefetching strategies and demonstrate the potential of this multiple-banked organization. For instance, we show that a two-level organization degrades IPC by 10% and 2% with respect to a non-pipelined single-banked register file, for SpecInt95 and SpecFP95 respectively, but it increases performance by 87% and 92% when the register file access time is factored in.
Architectural support for scalable speculative parallelization in shared-memory multiprocessors
Authors: Cintra Marcelo , Martínez José F. , Torrellas Josep
Published: July 2004

Speculative parallelization aggressively executes in parallel codes that cannot be fully parallelized by the compiler. Past proposals of hardware schemes have mostly focused on single-chip multiprocessors (CMPs), whose effectiveness is necessarily limited by their small size. Very few schemes have attempted this technique in the context of scalable shared-memory systems.

In this paper, we present and evaluate a new hardware scheme for scalable speculative parallelization. This design needs relatively simple hardware and is efficiently integrated into a cache-coherent NUMA system. We have designed the scheme in a hierarchical manner that largely abstracts away the internals of the node. We effectively utilize a speculative CMP as the building block for our scheme.

Simulations show that the architecture proposed delivers good speedups at a modest hardware cost. For a set of important non-analyzable scientific loops, we report average speedups of 4.2 for 16 processors. We show that support for per-word speculative state is required by our applications, or else the performance suffers greatly.
Applying predication to efficiently handle runtime class testing
Authors: Sadler Chris , Gupta Sandeep K. S. , Bhatia Rohit
Published: July 2004

Runtime class testing is a technique whereby virtual function calls are transformed into statically-bound function calls through a series of conditional branches. Through this transformation, the overhead of virtual function calls can be significantly reduced. However, the drawback of these tests is that by relying on conditional branches, the amount of instruction-level parallelism (ILP) is limited and the mispredict penalties can be relatively high. We show that by using predication during class testing, these drawbacks can be eliminated, and the benefits of class testing can be improved upon. Predication is a supported feature in Explicitly Parallel Instruction Computing (EPIC) architecture, which converts control dependencies into data dependencies, and thus eliminates the mispredict penalties. With analytical cost models and experimental results, we show that predicated class testing can reduce the direct cost of virtual function calls by 43% on an average, which in contrast to other class testing techniques, is a performance improvement of up to 31% per function call. These results are based on architectural specifications that most modern architectures will exceed, and are considered conservative. The actual speedups resulting from predicated class testing are expected to be higher
Using cache line coloring to perform aggressive procedure inlining
Authors: Aydin Hakan , Kaeli David
Published: July 2004

Memory hierarchy performance has always been an important issue in computer architecture design. The likelihood of a bottleneck in the memory hierarchy is increasing, as improvements in microprocessor performance continue to outpace those made in the memory system. As a result, effective utilization of cache memories is essential in today's architectures.The nature of procedural software poses visibility problems when attempting to perform program optimization. One approach to increasing visibility in procedural design is to perform procedure inlining. The main downside of using inlining is that inlined procedures can place excess pressure on the instruction cache.To address this issue we attempt to perform code reordering. By combining reordering with aggressive inlining, a larger executable image produced through inlining can be effectively remapped onto the cache address space, while not noticeably increasing the instruction cache miss rate.In this paper, we evaluate our ability to perform aggressive inlining by employing cache line coloring. We have implemented three variations of our coloring algorithm in the Alto toolset and compare them against Alto's aggressive basic block reordering algorithms. Alto allows us to generate optimized executables, that can be run on hardware to generate results. We find that by using our algorithms, we can achieve up a 21% reduction is execution runtime over the base Compaq optimizing compiler, and a 6.4% reduction when compared to Alto's interprocedural basic block reordering algorithm.
Exploiting parallelism in a network of workstations using COMA-BC
Authors: Fernández Benjamín Sahelices , Llanos Ferraris Diego R. , de Dios Hernández Agustín
Published: July 2004

In this paper we put forward a design for a multicomputer system based on a network of workstations which we call COMA-BC. It has a common address space in which a shared variables programming model can be used. The management of the shared address space is performed in a similar way to that in existing multiprocessor COMA systems. To be exact, the shared address space is divided into blocks, and their copies reside in the attraction memories of the workstations.The key piece in this system is the coherence cache protocol that we have developed. The goal of the protocol is to minimize the number and size of the messages travelling through the network so that the parallel applications can be executed without creating inconsistencies in the different copies of the blocks residing in the different nodes of the system.The proposed system has not been built, but a simulation environment has been specifically developed. This environment allows the simulation of the execution of parallel standard applications in COMA-BC. This simulation environment is driven by execution. Using the results and a simple analytic model, results have been obtained concerning the performance of the execution of standard parallel applications in terms of acceleration and efficiency. These results show the viability of a COMA-BC system as a way of exploiting parallelism at a low cost using workstations.
Hardware architectures for programming languages and programming languages for hardware architectures
Authors: Wirth Niklaus
Published: July 2004

Programming Languages and Operating Systems introduce abstractions which allow the programmer to ignore details of an implementation. Support of an abstraction must not only concentrate on promoting the efficiency of an implementation, but also on providing the necessary guards against violations of the abstractions. In the frantic drive for efficiency the second goal has been neglected. There are indications that recent designs which are claimed to be both simple and powerful, achieve efficiency by shifting the complex issues of code generation and of appropriate guards onto compilers.Complexity has become the common hallmark of software as well as hardware designs. It cannot be mastered by the common practices of testing and simulation. Hardware design may profit from developments in programming methodology by adopting proof techniques similar to those used in programming.
VLSI assist for a multiprocessor
Authors: Beck Bob , Kasten Bob , Thakkar Shreekant
Published: July 2004

Multiprocessors have long been of interest to computer community. They provide the potential for accelerating applications through parallelism and increased throughput for large multi-user system. Three factors have limited the commercial success of multiprocessor systems; entry cost, range of performance, and ease of application. Advances in very large scale integration (VLSI) and in computer aided design (CAD) have removed these limitations, making possible a new class of multiprocessor systems based on VLSI components. A set of requirements for building an efficient shared multiprocessor system are discussed, including: low-level mutual exclusion, interrupt distribution, inter-processor signaling, process dispatching, caching, and system configuration. A system that meets these requirements is described and evaluated.
Architectural support for multilanguage parallel programming on heterogeneous systems
Authors: Bisiani Roberto , Forin Alessandro
Published: July 2004

We have designed and implemented a software facility, called Agora, that supports the development of parallel applications written in multiple languages. At the core of Agora there is a mechanism that allows concurrent computations to share data structures independently of the computer architecture they are executed on. Concurrent computations exchange control information by using a pattern-directed technique. This paper describes the Agora shared memory and its software implementation on both tightly and loosely-coupled architectures.
An architecture for the direct execution of the Forth programming language
Authors: Hayes John R. , Fraeman Martin E. , Williams Robert L. , Zaremba Thomas
Published: July 2004

We have developed a simple direct execution architecture for a 32 bit Forth microprocessor. The processor can directly access a linear address space of over 4 gigawords. Two instruction types are defined; a subroutine call, and a user defined microcode instruction. On-chip stack caches allow most Forth primitives to execute in a single cycle.
Tags and type checking in LISP: hardware and software approaches
Authors: Steenkiste Peter , Hennessy John
Published: July 2004

One of the major factors that distinguishes LISP from many other languages (Pascal, C, Fortran, etc.) is the need for run-time type checking. Run-time type checking is implemented by adding to each data object a tag that encodes type information. Tags must be compared for type compatibility, removed when using the data, and inserted when new data items are created. This tag manipulation, together with other work related to dynamic type checking and generic operations, constitutes a significant component of the execution time of LISP programs. This has led both to the development of LISP machines that support tag checking in hardware and to the avoidance of type checking by users running on stock hardware. To understand the role and necessity of special-purpose hardware for tag handling, we first measure the cost of type checking operations for a group of LISP programs. We then examine hardware and software implementations of tag operations and estimate the cost of tag handling with the different tag implementation schemes. The data shows that minimal levels of support provide most of the benefits, and that tag operations can be relatively inexpensive, even when no special hardware support is present.
The effect of instruction set complexity on program size and memory performance
Authors: Davidson Jack W. , Vaughan Richard A.
Published: July 2004

One potential disadvantage of a machine with a reduced instruction set is that object programs may be substantially larger than those for a machine with a richer, more complex instruction set. The main reason is that a small instruction set will require more instructions to implement the same function. In addition, the tendency of RISC machines to use fixed length instructions with a few instruction formats also increases object program size. It has been conjectured that the resulting larger programs could adversely affect memory performance and bus traffic. In this paper we report the results of a set of experiments to isolate and determine the effect of instruction set complexity on cache memory performance and bus traffic. Three high-level language compilers were constructed for machines with instruction sets of varying degrees of complexity. Using a set of benchmark programs, we evaluated the effect of instruction set complexity had on program size. Five of the programs were used to perform a set of trace-driven simulations to study each machine's cache and bus performance. While we found that the miss ratio is affected by object program size, it appears that this can be corrected by simplying increasing the size of the cache. Our measurements of bus traffic, however, show that even with large caches, machines with simple instruction sets can expect substantially more main memory reads than machines with dense object programs.
An experimental coprocessor for implementing persistent objects on an IBM 4381
Authors: Georgiou C. J. , Palmer S. L. , Rosenfeld P. L.
Published: July 2004

In this paper we describe an experimental coprocessor for an IBM 4381 that is designed to facilitate the exploration of persistent objects.
Integer multiplication and division on the HP precision architecture
Authors: Magenheimer Daniel J. , Peters Liz , Pettis Karl , Zuras Dan
Published: July 2004

In recent years, many architectural design efforts have focused on maximizing performance for frequently executed, simple instructions. Although these efforts have resulted in machines with better average price/performance ratios, certain complex instructions and, thus, certain classes of programs which heavily depend on these instructions may suffer by comparison. Integer multiplication and division are one such set of complex instructions. This paper describes how a small set of primitive instructions combined with careful frequency analysis and clever programming allows the Hewlett-Packard Precision Architecture integer multiplication and division implementation to provide adequate performance at little or no hardware cost.
A study of scalar compilation techniques for pipelined supercomputers
Authors: Weiss Shlomo , Smith James E.
Published: July 2004

This paper studies two compilation techniques for enhancing scalar performance in high-speed scientific processors: software pipelining and loop unrolling. We study the impact of the architecture (size of the register file) and of the hardware (size of instruction buffer) on the efficiency of loop unrolling. We also develop a methodology for classifying software pipelining techniques. For loop unrolling, a straightforward scheduling algorithm is shown to produce near-optimal results when not inhibited by recurrences or memory hazards. Software pipelining requires less hardware but also achieves less speedup. Finally, we show that the performance produced with a modified CRAY-1S scalar architecture and a code scheduler utilizing loop unrolling is comparable to the performance achieved by the CRAY-1S with a vector unit and the CFT vectorizing compiler.
Performance and architectural evaluation of the PSI machine
Authors: Taki Kazuo , Nakajima Katzuto , Nakashima Hiroshi , Ikeda Morihiro
Published: July 2004

We evaluated a Prolog machine PSI (Personal Sequential Inference machine) for the purpose of improving and redesigning it. In this evaluation, we measured the execution speed and the dynamic characteristics of cache memory, register file, and branching hardware introduced for high-speed execution of Prolog programs.Execution speed of the PSI firmware interpreter was found to be comparable to that of the DEC-10 Prolog compiled code on the DEC-2060. It was also found that PSI was faster than DEC for executing programs containing much unification and backtracking that require runtime processing.With the cache memory, the hit ratio for application programs was found higher than 96%; this demonstrates that the Prolog execution has much memory access locality. The memory access frequency and the appearance ratio between Read and Write command were also investigated.Concerning the register file, use rate of each dedicated access mode was measured and effect of each mode was discussed. In the branching function we confirmed a high appearance rate of conditional branches and multi-way branches based on tag values.