bluuebunny/crossref_metadata_2025_split huggingface dataset:
Extraction of massive instruction level parallelism
Authors: Uht Augustus K. 
Published: July 2004

Our goal is to dramatically increase the performance of uniprocessors through the exploitation of instruction level parallelism, i.e. that parallelism which exists amongst the machine instructions of a program. Speculative execution may help a lot, but, it is argued, both branch prediction and eager execution are insufficient to achieve performances in speedup factors in the tens (with respect to sequential execution), with reasonable hardware costs.
A new form of code execution, Disjoint Eager Execution (DEE), is proposed which uses less hardware than pure eager execution, and has more performance than pure branch prediction; DEE is a continuum between branch prediction and eager execution. DEE is shown to be optimal, when processing resources are constrained.
Branches are predicted in DEE, but the predictions should be made in parallel in order to obtain high performance. This is not allowed, however, by the use of the standard instruction stream model, the dynamic model (the order is as indicated by the contents of the Program Counter).
The use of the static instruction stream is proposed instead. The static instruction stream oreder is the same as the order of the code in memory, and is independent of the execution of branches. It allows reduced branch dependencies, as well.
It is argued that a new version, Levo, of an old machine model, CONDEL-2, will be able to attain massive Instruction Level Parallelism.
A functional level simulation engine of MAN-YO: a special purpose parallel machine for logic design automation
Authors: Nakata T. , Koike N. 
Published: July 2004

The architecture of a proto-type functional level simulator element of a massively parallel machine (MAN-YO) designed for logic design automation is presented. At functional level, hardware systems are described in a hardware description language, FDL. The FDL description is compiled into stack oriented intermediate language instructions. Communicating with other gate level/block level/ functional level processors, each functional simulator interprets the compiled instructions and simulates various circuits using 4-value logic. In order to realize high speed processing of 4-value logic/arithmetic operations, the functional simulator utilizes low-level parallelism realized by 3 ALUs which are controlled by the different fields of a long horizontal type microinstruction.
By utilizing low-level parallelism at processor level, as well as processor level parallelism, high speed execution of mixed level simulation becomes possible. The system also provides further performance enhancement by compiling often used FDL macros into microcode.
This paper describes an outline of the MAN-YO (Japanese for ten thousand leaf-nodes in the processor tree), a brief description of FDL, and the architecture of the functional level simulator element (called FDLPE). A rough performance based on the current design is also described.
VLSI oriented asynchronous architecture
Authors: Hirayama M. 
Published: July 2004

In order to realise dedicated functions that have no special parallel algorithms for efficient full custom VLSI implementation, we propose an asynchronous architecture that consists of several asynchronous functional modules and controls the chip by the local communication among these functional modules. As this architecture is very suitable for mapping from the behavioral specification described by the software onto silicon, it is very useful as a target architecture for silicon compilers.
This paper describes the concept and the VLSI implementation of the asynchronous architecture. An evaluation of the size and the execution speed of chips based on this architecture model is also described.
Performance evaluation of vector accesses in parallel memories using a skewed storage scheme
Authors: Harper D. T. , Jump J. R. 
Published: July 2004

This paper presents and evaluates a scheme for reducing the average memory access time in a vector processing architecture. This scheme uses data skewing to distribute vectors among the modules of a parallel memory system in such a way that, for typical vector access patterns, the average number of memory conflicts is reduced. It also employs both address and data buffers in each module to smooth out the transient irregularities that occur in some vector access patterns.
Most previous data skewing techniques were developed to provide conflict-free access for a limited set of access strides. While the proposed scheme does not eliminate all conflicts, it improves the average performance over non-skewed parallel memories by significantly reducing the number of conflicts for a wide range of strides. Also, this effect is much less dependent on the number of memory modules than the skewing schemes used to obtain conflict-free access.
Evaluation of release consistent software distributed shared memory on emerging network technology
Authors: Dwarkadas Sandhya , Keleher Peter , Cox Alan L. , Zwaenepoel Willy 
Published: July 2004

We evaluate the effect of processor speed, network characteristics, and software overhead on the performance of release-consistent software distributed shared memory. We examine five different protocols for implementing release consistency: eager update, eager invalidate, lazy update, lazy invalidate, and a new protocol called
lazy hybrid
. This lazy hybrid protocol combines the benefits of both lazy update and lazy invalidate.

Our simulations indicate that with the processors and networks that are becoming available, coarse-grained applications such as Jacobi and TSP perform well, more or less independent of the protocol used. Medium-grained applications, such as Water, can achieve good performance, but the choice of protocol is critical. For sixteen processors, the best protocol, lazy hybrid, performed more than three times better than the worst, the eager update. Fine-grained applications such as Cholesky achieve little speedup regardless of the protocol used because of the frequency of synchronization operations and the high latency involved.
While the use of relaxed memory models, lazy implementations, and multiple-writer protocols has reduced the impact of false sharing, synchronization latency remains a serious problem for software distributed shared memory systems. These results suggest that the future work on software DSMs should concentrate on reducing the amount of synchronization or its effect.
Performance of cached DRAM organizations in vector supercomputers
Authors: Hsu W.-C. , Smith J. E. 
Published: July 2004

DRAMs containing cache memory are studied in the context of vector supercomputers. In particular, we consider systems where processors have no internal data caches and memory reference streams are generated by vector instructions. For this application, we expect that cached DRAMs can provide high bandwidth at relatively low cost.
We study both DRAMs with a single, long cache line and with smaller, multiple cache lines. Memory interleaving schemes that increase data locality are proposed and studied. The interleaving schemes are also shown to lead to non-uniform bank accesses, i.e. hot banks. This suggest there is an important optimization problem involving methods that increase locality to improve performance, but not so much that hot banks diminish performance. We show that for uniprocessor systems, both types of cached DRAMs work well with the proposed interleave methods. For multiprogrammed multiprocessors, the multiple cache line DRAMs work better.
Odd memory systems may be quite interesting
Authors: Seznec André , Lenfant Jacques 
Published: July 2004

Using a prime number of N of memory banks on a vector processor allows a conflict-free access for any slice of N consecutive elements of a vector stored with a stride not multiple of N.
To reject the use of a prime (or odd) number N of memory banks, it is generally advanced that address computation for such a memory system would require systematic Euclidean Division by the number N. We first show that the well known Chinese Remainder Theorem allows to define a very simple mapping of data onto the memory banks for which address computation does not require any Euclidean Division.
Massively parallel SIMD computers may have several thousands of processors. When the memory on such a machine is globally shared, routing vectors from memory to the processors is a major difficulty; the control for the interconnection network cannot be generally computed at execution time. When the number of memory banks and processors is a product of prime numbers, the family of permutations needed for routing vectors for memory to the processors through the interconnection network have very specific properties. The Chinese Remainder Network presented in the paper is able to execute all these permutations in a single path and may be self-routed.
Compiler techniques for data synchronization in nested parallel loops
Authors: Tang Peiyi , Yew Pen-Chung , Zhu Chuan-Qi 
Published: July 2004

The major source of parallelism in ordinary programs is do loops. When loop iterations of parallelized loops are executed on multiprocessors, the cross-iteration data dependencies need to be enforced by synchronization between processors. Existing data synchronization schemes are either too simple to handle general nested loop structures with non-trivia array subscript functions or inefficient due to the large run-time overhead.
In this paper, we propose a new synchronization scheme based on two data-oriented synchronization instructions: synch_read(x,s) and synch_write(x,s). We present the algorithm to compute the ordering number, s, for each data access. Using our scheme, a parallelizing compiler can parallelize a general nested loop structure with complicated cross-iteration data dependencies. If the computations of ordering numbers cannot be done at compile time, the run-time overhead is smaller than the other existing run-time schemes.
Impact of task duplication on static-scheduling performance in multiprocessor systems with variable execution-time tasks
Authors: Luque Emilio , Ripoll Ana , Hernández Porfidio , Margalef Tomás 
Published: July 2004

The problem of scheduling a set of partially ordered tasks on a nonpreemptive multiprocessor system of identical processors assuming that the execution time of some tasks can vary within a set of known values is studied in an effort to construct a more realistic static schedule.
A new heuristic algorithm (CP/MISF/TD) based on task duplication is proposed. The effectiveness of the algorithm is proved by comparing the results obtained for a wide variety of task graphs with the ones obtained by applying the classical list scheduling algorithms which consider fixed time tasks.
Keywords: Static scheduling, List scheduling, Heuristic algorithms, Task duplication, Multiprocessor systems.
The TLB slice—a low-cost high-speed address translation mechanism
Authors: Taylor George , Davies Peter , Farmwald Michael 
Published: July 2004

The MIPS R6000 microprocessor relies on a new type of translation lookaside buffer — called aTLB slice— which is less than one-tenth the size of a conventional TLB and as fast as one multiplexer delay, yet has a high enough hit rate to be practical. The fast translation makes it possible to use a physical cache without adding a translation stage to the processor's pipeline. The small size makes it possible to include address translation on-chip, even in a technology with a limited number of devices.The key idea behind the TLB slice is to have both a virtual tag and a physical tag on a physically-indexed cache. Because of the virtual tag, the TLB slice needs to hold only enough physical page number bits — typically 4 to 8 — to complete the physical cache index, in contrast with a conventional TLB, which needs to hold both a virtual page number and a physical page number. The virtual page number is unnecessary because the TLB slice needs to provide only a hint for the translated physical address rather than a guarantee. The full physical page number is unnecessary because the cache hit logic is based on the virtual tag. Furthermore, if the cache is multi-level and references to the TLB slice are “shielded” by hits in a virtually indexed primary cache, the slice can get by with very few entries, once again lowering its cost and increasing its speed. With this mechanism, the simplicity of a physical cache can been combined with the speed of a virtual cache.
Circuits for wide-window superscalar processors
Authors: Henry Dana S. , Kuszmaul Bradley C. , Loh Gabriel H. , Sami Rahul 
Published: July 2004

Our program benchmarks and simulations of novel circuits indicate that large-window processors are feasible. Using our redesigned superscalar components, a large-window processor implemented in today's technology can achieve an increase of 10-60% (geometric mean of 31%) in program speed compared to today's processors. The processor operates at clock speeds comparable to today's processors, but achieves significantly higher ILP.
To measure the impact of a large window on clock speed, we design and simulate new implementations of the logic components that most limit the critical path of our large-window processor: the schedule logic and the wake-up logic. We use log-depth cyclic segmented prefix (CSP) circuits to reimplement these components. Our layouts and simulations of critical paths through these circuits indicate that our large-window processor could be clocked at frequencies exceeding 500MHz in today's technology. Our commit logic and rename logic can also run at these speeds.
To measure the impact of a large window on ILP, we compare two microarchitectures, the first has a 128-instruction window, an 8-wide fetch unit, and 20-wide issue (four integer, branch, multiply, float, and memory units), whereas the second has a 32-instruction window, and a 4-wide fetch unit and is comparable to today's processors. For each, we simulate different window reuse and bypass policies. Our simulations show that the large-window processor achieves significantly higher IPC. This performance increase comes despite the fact that the large-window processor uses a wrap-around window while the small-window processor uses a compressing window, thus effectively increasing its number of outstanding instructions. Furthermore, the large-window processor sometimes pays an extra clock cycle for bypassing.
Code layout optimizations for transaction processing workloads
Authors: Ramirez Alex , Barroso Luiz André , Gharachorloo Kourosh , Cohn Robert , Larriba-Pey Josep , Lowney P. Geoffrey , Valero Mateo 
Published: July 2004

Commercial applications such as databases and Web servers constitute the most important market segment for high-performance servers. Among these applications, on-line transaction processing (OLTP) workloads provide a challenging set of requirements for system designs since they often exhibit inefficient executions dominated by a large memory stall component. This behavior arises from large instruction and data footprints and high communication miss rates. A number of recent studies have characterized the behavior of commercial workloads and proposed architectural features to improve their performance. However, there has been little research on the impact of software and compiler-level optimizations for improving the behavior of such workloads.
This paper provides a detailed study of profile-driven compiler optimizations to improve the code layout in commercial workloads with large instruction footprints. Our compiler algorithms are implemented in the context of Spike, an executable optimizer for the Alpha architecture. Our experiments use the Oracle commercial database engine running an OLTP workload, with results generated using both full system simulations and actual runs on Alpha multiprocessors. Our results show that code layout optimizations can provide a major improvement in the instruction cache behavior, providing a 55% to 65% reduction in the application misses for 64-128K caches. Our analysis shows that this improvement primarily arises from longer sequences of consecutively executed instructions and more reuse of cache lines before they are replaced. We also show that the majority of application instruction misses are caused by self-interference. However, code layout optimizations significantly reduce the amount of self-interference, thus elevating the relative importance of interference with operating system code. Finally, we show that better code layout can also provide substantial improvements in the behavior of other memory system components such as the instruction TLB and the unified second-level cache. The overall performance impact of our code layout optimizations is an improvement of 1.33 times in the execution time of our workload.
NanoFabrics
Authors: Goldstein Seth Copen , Budiu Mihai 
Published: July 2004

The continuation of the remarkable exponential increases in processing power over the recent past faces imminent challenges due in part to the physics of deep-submicron CMOS devices and the costs of both chip masks and future fabrication plants. A promising solution to these problems is offered by an alternative to CMOS-based computing, chemically assembled electronic nanotechnology (CAEN).
In this paper we outline how CAEN-based computing can become a reality. We briefly describe recent work in CAEN and how CAEN will affect computer architecture. We show how the inherently reconfigurable nature of CAEN devices can be exploited to provide high-density chips with defect tolerance at significantly reduced manufacturing costs. We develop a layered abstract architecture for CAEN-based computing devices and we present preliminary results which indicate that such devices will be competitive with CMOS circuits.
A PMS level language for performance evaluation modelling (V-PMS)
Authors: Kerner Helmut , Beyerle Werner 
Published: July 2004

A comparison of Register Transfer level modelling and V-PMS is quite indicative. While RT-modelling approaches a restricted goal, viz. a hardware structure capable of performing a few hundred algorithms, a V-PMS level model has a complete computer system as its target, i.e. a composite of hardware structures of the RT-level complexity cooperating under the control of an operating system in the execution of a load.
In order to construct a language suitable for describing the hardware as part of a total PMS-level model for performance evaluation, the original form of PMS was substantially changed by providing an expanded set of building blocks with corresponding definitions. This language, with its clearly defined functions and performance data, its unambiguous communication blocks and rules for interconnections, provides a human reader with a clear understanding of the performance of components and of their internal communication within the computer system, and links the hardware part to a model of an operating system (to be supplied at a later time). For computer readable system specification a syntax for connecting the above symbolic components is proposed. A description of the CDC Cyber 74/CDC 6600 system examplifies the use of the proposed language and its merits for building performance evaluation models.
The minerva multi-microprocessor
Authors: Widdoes Lawrence C. 
Published: July 2004

A multiprocessor system is described which is an experiment in low cost, extensible, multiprocessor architectures. Global issues such as inclusion of a central bus, design of the bus arbiter, and methods of interrupt handling are considered.
The system initially includes two processor types, based on microprocessors, and these are discussed. Methods for reducing processor demand for the central bus are described.
A hierarchical, restructurable multi-microprocessor architecture
Authors: Arnold R. G. , Page E. W. 
Published: July 2004

This paper introduces a system architecture which allows a high degree of restructuring so that system resources may be tailored to processing requirements. The proposed system organization consists of a large number of byte-slice processors interconnected through a system of busses. Each processor is capable of communicating with every other processor in the system and any number of adjacent processors may be strung together to create a wider arithmetic capability than is possible with a single processor. Processors may be organized into a number of independent teams while processor teams may, in turn, be organized in a hierarchical fashion to allow for concurrent processing. Processor teams may function either in cooperation with or completely independent of other processor teams.
All communication throughout the system consists of information packets containing the data to be transferred and a series of tags which indicate the destination address for the data and the action to be taken by the processor upon receipt of the information packet.
Two types of busses are employed; Conventional busses and the circulating loop (or Pierce loop). The circulating loop moves an information packet in a fixed direction a uniform distance in each unit of time and therefore allows independent data transfer operations to be carried out simultaneously. Several examples illustrate the utility of the proposed architecture.
A Self Managing Secondary Memory system
Authors: DeMartinis Manlio , Lipovski G. Jack , Su Stanley Y.W. , Watson J. K. 
Published: July 2004

A Self Managing Secondary Memory (SMSM) organization is proposed herein, in which hardware directly assists the storage, retrieval and management of arbitrary length records on such devices as fixed head discs or charge coupled devices (CCD's). This paper emphasizes some of the techniques used to implement an SMSM system.
In an SMSM, fixed length words are organized into variable length records, and these records are packed into a file. The first word of the record, a label, can be associatively addressed to mark the record. Marked records can be output, erased, or a word or a collection of words can be inserted after the label of such records. Erased words are shifted to the bottom of memory as data words are packed upward, so that new records or extensions of old records can be inserted at the bottom of the file. In this system, although the file appears to be a single one dimensional array of words, it is actually stored on a number m of n word circular access memories, such as CCD's or tracks of a fixed head disc. Larger systems are implemented by increasing m. The access time for the entire system depends only on n.
This architecture is self-managing in that no directories are kept, nor is software garbage collection or allocation necessary. The hardware replaces these functions. This appears to be a desirable direction for secondary memory architectures to develop, with special application to their use in computer networks.
This paper discusses techniques for implementing an SMSM. These techniques were developed as part of the Context Addressed Segment Sequential Memory (CASSM) system. This paper therefore also describes that part of CASSM that, by itself, forms a useful SMSM. It is hoped that these techniques will be useful in the development of a new class of intelligent secondary memories to meet present and future needs of computing systems.