bluuebunny/crossref_metadata_2025 huggingface dataset:
Memory management support for tiled array organization
Authors: Newman Gary
Published: July 2004

Organization of two dimensional array data into sub-arrays, sometimes called tiles, has been known to provide better performance than either row or column ordering since the late 1960s. Yet the tiling of arrays is little used today. Although some image processing and graphics memory systems have provided tile access modes, tiling has never been provided in a general purpose way.A novel method is described which adds support for tiled arrays to an otherwise conventional paged memory management unit. The result is that pages contain two dimensional tiles of data rather than one dimensional strips, making tiled virtual memory transparently available to general purpose application programs. Extending this new tiling method, the same benefits are shown to support sub-arrays with three or more dimensions. Finally, the image memory management unit of the Kodak Prophecy Color Publishing System is shown as an example implementation of tiled virtual memory.
Instruction-level parallelism from execution interlock collapsing
Authors: Malik Nadeem , Eickemeyer Richard J. , Vassiliadis Stamatis
Published: July 2004

An innovative technique has been developed that permits the collapsing of execution interlocks between integer ALU operations as well as between address generation operations, allowing parallel execution of two instructions, having true dependencies, in a single cycle. Given that the proposed scheme has been shown not to increase the machine cycle time, it potentially provides an attractive means for increasing the instruction--level parallelism. Preliminary results show that within the basic blocks, the geometric mean of the speedup from this new design technique is up to 10% in the integer SPEC Benchmarks. The geometric mean of the speedup including floating point benchmarks is up to 6%. The results also suggest that depending on the application environment this new design may be used as an alternative to the relatively more expensive out--of--order instruction issue approach.
On the attributes of the SCISM organization
Authors: Vassiliadis Stamatis , Blaner Bart , Eickemeyer Richard J.
Published: July 2004

In this paper, we describe some of the attributes of the SCISM organization, a multiple instruction-issuing machine, the outcome of five years of research at the IBM Glendale Laboratory, in Endicott, New York. The proposed organization embodies a number of mechanisms, including the analysis of instruction sequences and deciding which instructions will execute in parallel prior to instruction fetch and issue, the incorporation of permanent preprocessing of instructions to be executed in parallel, the categorization of instructions for parallel execution on the basis of hardware utilization rather than opcode description, the avoidance of memory interlocks through the preprocessing mechanism, and the elimination of execution interlocks with specialized hardware. It is shown that by incorporating these mechanisms, a SCISM capable of issuing and executing two instructions per cycle can achieve more than 90% of the theoretical maximum performance of an idealized, dual instruction issue superscalar machine.
Planar-adaptive routing
Authors: Chien Andrew A. , Kim Jae H.
Published: July 2004

Network throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of adaptive routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels, independent of network size and dimension. Planar adaptive routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each routing step. In the fault-free case, planar-adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-adaptive router can be extended with misrouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar adaptive networks can simultaneously support both in-order and adaptive, out-of-order packet delivery.

Planar-adaptive routing is of practical significance. It provides the simplest known support for deadlock-free adaptive routing in k-ary n-cubes of more than two dimensions (with
k
> 2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-adaptive routers is amenable to efficient implementation.
A study of I/O system organizations
Authors: Narasimha Reddy A. L.
Published: July 2004

With the increasing processing speeds, it has become important to design powerful and efficient I/O systems. In this paper, we look at several design options in designing an I/O system and study their impact on the performance. Specifically, we use trace driven simulations to study a disk system with a nonvolatile cache. Some of the considered design parameters include the cache block size, the fetch size, the cache size and the disk access policy. We show that decoupling the fetch size and the cache block size results in significant performance improvements. A new write-back policy is presented that is shown to offer significant performance benefits. We show that optimal block size in a two-level memory hierarchy is dependent only on the latency, data rate product of the second level as previously conjectured. We also present results showing the effect of a split access operation of a disk read/write head.
A class of prefetch schemes for on-chip data caches
Authors: Varma Anujan , Sinha Gunjan
Published: July 2004

We introduce and evaluate a class of prefetch schemes for on-chip data caches in high-performance RISC processors. These schemes are conservative, initiating a prefetch only when a sequential pattern of references have been observed. Performance results based on traces of five programs in the SPEC suite on an IBM RS/6000 show that these schemes result in a significant reduction in miss ratio without the large increase in memory traffic associated with earlier schemes.
A partitioned translation lookaside buffer approach to reducing address bandwith (abstract)
Authors: Farrens Matthew , Park Arvin , Fanfelle Rob , Ng Pius , Tyson Gary
Published: July 2004

Simulations indicate a simple modification of existing virtual memory hardware can significantly reduce the number of pins required to transmit address information from processor to off-chip memory. This modification consists of partitioning a TLB so that virtual page numbers are stored in a cache on the processor and corresponding real page numbers are sotred in registers at the memory, making it possible to transmit a small register index instead of the entire real page number.
Architectural and implementation tradeoffs in the design of multiple-context processors (abstract)
Authors: Laudon James , Gupta Anoop , Horowitz Mark
Published: July 2004

We examine two multiple-context schemes in the context of scalable shared-memory multiprocessors. The blocked scheme switches between contexts at cache misses. The proposed interleaved scheme switches between available contexts on a cycle-by-cycle basis, while providing full pipeline interlocks for good single-context performance. We show the interleaved scheme to have a performance advantage over the blocked scheme due to its ability to hide pipeline dependencies and reduce the context switch cost. We also show that, while the implementation of the interleaved scheme is more complex, this complexity is not overwhelming.
Analysis of multithreaded microprocessors under multiprogramming
Authors: Culler David E. , Gunter Michial , Lee James C.
Published: July 2004

We examine multithreading to improve uniprocessor cost/performance on multiple processes. Processor utilization and cache behavior are studied analytically and under simulation by interleaving reference traces to model timesharing and multithreading. Multithreading a small number of threads is superior with large on-chip caches and significant memory latency. The switch need not be extremely fast. Surprisingly, miss ratios under multithreading may be lower than under timesharing, because switch-on-miss multithreading favors processes with better cache behavior.
A process-dependent partitioning strategy for cache memories
Authors: Deville Yannick
Published: July 2004

This paper presents a method for partitioning cache memories which contain both instruction and data blocks. This partitioning scheme limits the total number of instruction blocks, while no conditions are set on the total number of data blocks. The partitioning is reconfigured by changing the maximum allowed number of instruction blocks, called a “threshold”. A method for choosing this threshold is provided, based on the observation that its optimum value depends on the executable code of the processes considered but almost not on its input data. Trace-driven simulations show that, when medium cache sizes are considered, the proposed structure often yields a much lower miss ratio than the corresponding classical mixed cache (typically 20% to 40% and 50% to 80% lower, respectively if the caches have 4 and 16 ways).
Precise instruction scheduling without a precise machine model
Authors: Baker Henry G.
Published: July 2004

A simple technique is presented which allows an optimizing compiler to more precisely compare the performance of alternative instruction sequences on a complex RISC architecture so that the better sequence can be chosen. This technique may be faster than current techniques, and has the advantage that minor modifications to the hardware do not require any changes to the compiler (not even recompilation), and yet have an immediate effect on instruction scheduling decisions.
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 insrtruction stream model, the dynamic model (the order is as indicated by the contents of the Program Counter).The use of the static insruction 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 Parallelsim.
Physical limitations of a computer
Authors: Danesh Iraj
Published: July 2004

This article introduces the physical limitations of a computer and describes limiting architectural impact of the laws of physics on computer hardware design and shows how imaginative application of skills of a computer architect and artistic management of the circuitry may override some of these limitations.
A case for uniform memory access multiprocessors
Authors: Dewan Gautam , Nair V. S. S.
Published: July 2004

Virtually all the shared-memory architectures that have appeared in recent times are of the NUMA (Non-Uniform Memory Access) type. A centralized memory that is uniformly accessible by all the nodes of a multiprocessor, rather than memory that is distributed among the nodes, leads to a simpler platform for software to run on. Certain performance advantages gained by distributing memory among nodes are not all that clearcut. The same penalties are being paid, albeit in a different form, and at a different time in the execution of a program.Ring based multiprocessors built from fast point-to-point links can be the next generation of medium scalable UMA machines, replacing the shared-bus kind. One such architecture is described along with details of how any snooping protocol, including those of the write-broadcast variety, can be ported to this new environment.
Parallelizing I/O intensive applications for a workstation cluster
Authors: Lin Z. , Zhou S.
Published: July 2004

An I/O intensive application, parallel full text retrieval based on a signature file method, is studied. The text retrieval system is implemented on a cluster of DEC5000 workstations connected by Ethernet. Experiments are performed to evaluate the benefit and cost for running such an application in a workstation cluster. Results show that substantial improvement in speed can be obtained through parallelism in disk accesses, despite the high communication and synchronization overhead that is incurred. Several factors that affect the performance of a parallel I/O application in this type of computing environment are discussed. The advantages of a workstation cluster are its large combined I/O buffer capacity, and possible concurrent accesses to disks local to each workstation. Our study demonstrates that these advantages, when exploited properly, can lead to effective performance improvement without the need for additional hardware.
Implementing the NHT-1 application I/O benchmark
Authors: Fineberg Samuel A.
Published: July 2004

The NHT-1 I/O (Input/Output) benchmarks are a benchmark suite developed at the Numerical Aerodynamic Simulation Facility (NAS) located at NASA Ames Research Center. These benchmarks are designed to test various aspects of the I/O performance of parallel supercomputers. One of these benchmarks, the Application I/O Benchmark, is designed to test the I/O performance of a system while executing a typical computational fluid dynamics application. In this paper the implementation of this benchmark on three parallel systems located at NAS and the results obtained from these implementations are reported. The machines used were an 8 processor Cray Y-MP, a 32768 processor CM-2, and a 128 processor iPSC/860. The results show that the Y-MP is the fastest machine and has relatively well balanced I/O performance. I/O adds 2--40% overhead, depending on the number of processors utilized. The CM-2 is the slowest machine, but it has I/O that is fast relative to its computational performance. This resulted in typical I/O overheads on the CM-2 of less than 4%. Finally, the iPSC/860, while not as computationally fast as the Y-MP, is considerably faster than the CM-2. However, the iPSCI860's I/O performance is quite poor and can add overhead of more than 70%.
Improved parallel I/O via a two-phase run-time access strategy
Authors: del Rosario Juan Miguel , Bordawekar Rajesh , Choudhary Alok
Published: July 2004

As scientists expand their models to describe physical phenomena of increasingly large extent, I/O becomes crucial and a system with limited I/O capacity can severely constrain the performance of the entire program.We provide experimental results, performed on an lntel Touchtone Delta and nCUBE 2 I/O system, to show that the performance of existing parallel I/O systems can vary by several orders of magnitude as a function of the data access pattern of the parallel program. We then propose a two-phase access strategy, to be implemented in a runtime system, in which the data distribution on computational nodes is decoupled from storage distribution. Our experimental results show that performance improvements of several orders of magnitude over direct access based data distribution methods can be obtained, and that performance for most data access patterns can be improved to within a factor of 2 of the best performance. Further, the cost of redistribution is a very small fraction of the overall access cost.
An overview of techniques to support continuous retrieval of multimedia objects
Authors: Ghandeharizadeh Shahram , Shahabi Cyrus , Ramos Luis
Published: July 2004

Multimedia information systems have emerged as an essential component of many application domains ranging from library information systems to entertainment technology. However, most implementations of these systems (based on a workstation) cannot support a continuous display of multimedia objects and suffer from frequent disruptions and delays termed
hiccups
. This is due to the low I/O bandwidth of the current disk technology, the high bandwidth requirement of multimedia objects, and the large size of these objects which requires them to be almost always disk resident. One approach to resolve this limitation is to decluster a multimedia object across multiple disk drives in order to employ the aggregate bandwidth of several disks to support its continuous retrieval (and display). To support simultaneous display of several multimedia objects for different users, the system can replicate data across multiple groups of disk drives in a
virtual
manner. This paper provides an overview of: 1) techniques to manage the replicas of objects, and 2) strategies for grouping the disk drives when the database consists of a mix of media types.
A transputer T9000 family based architecture for parallel database machines
Authors: Li Qiang , Rishe Naphtali
Published: July 2004

Parallel computing is a promising way to achieve high performance in a database system. The disk access speed has been a well known bottleneck for database machines, and the data intensive nature and the random communication patterns of databases make the interconnection network in a database machine difficult to design.This article describes the design of a highly parallel, high throughput database machine based on the new T9000 transputer family and a large number of relatively inexpensive disks. The database machine is designed to achieve a throughput of more than 10,000 elementary transactions per second and a total size in the range of terabytes. The Semantic Binary Database Model is employed by the system. Besides its logical aspects, this model's implementation facilitates the utilization of the parallel processing power and improves the reliability of the system.
A RISC processor architecture with a versatile stack system
Authors: Aßmann Claus
Published: July 2004

Modern RISC processors mainly differ w.r.t, the organization of their register files. There are currently three different approaches: a flat register file (e.g., MIPS), fixed-size register windows (SPARC), or a stack-like organization (AM29K). This paper describes a processor architecture with a new stack system, which is tailored to the needs of executing functional languages. In order to support a fast subroutine call mechanism and efficient parameter passing, our architecture uses a system of four stacks, of which two are interchangeable.A simulation of this processor architecture shows that a selection of functional benchmark programs can be executed with less machine cycles than equivalent code-optimized C programs on a SPARC or MIPS processor.
Implementation and evaluation of a list-processing-oriented data flow machine
Authors: Amamiya M. , Takesue M. , Hasegawa R. , Mikami H.
Published: July 2004

The architecture of a data flow machine, called DFM, is developed for parallel list processing. The DFM can maximally exploit parallelism inherent in list processing, due to its ultra-multi-processing mechanism, packet communication-based parallel and pipeline execution mechanism, and lenient cons mechanism. A practical DFM implementation is described. A DFM prototype machine is implemented and DFM performance is evaluated in a simulation on the register transfer level using several benchmark programs. The DFM single processor system is shown to be about five times faster than conventional machines which use the same device technology, while a multi-processor DFM system is shown to achieve a linear speed-up ratio of 0.6 ~ 0.9.
Parallel algorithms and architectures for rule-based systems
Authors: Gupta A. , Forgy C. , Newell A. , Wedig R.
Published: July 2004

Rule-based systems, on the surface, appear to be capable of exploiting large amounts of parallelism—it is possible to match each rule to the data memory in parallel. In practice, however, we show that the speed-up from parallelism is quite limited, less than 10-fold. The reasons for the small speed-up are: (1) the small number of rules relevant to each change to data memory; (2) the large variation in the processing required by the relevant rules; and (3) the small number of changes made to data memory between synchronization steps. Furthermore, we observe that to obtain this limited factor of 10-fold speed-up, it is necessary to exploit parallelism at a very fine granularity. We propose that a suitable architecture to exploit such fine-grain parallelism is a bus-based shared-memory multiprocessor with 32-64 processors. Using such a multiprocessor (with individual processors working at 2 MIPS), it is possible to obtain execution speeds of about 3800 rule-firings/sec. This speed is significantly higher than that obtained by other proposed parallel implementations of rule-based systems.
Concert: design of a multiprocessor development system
Authors: Halstead R. R. , Anderson T. L. , Osborne R. B. , Sterling T. L.
Published: July 2004

Concert
is a shared-memory multiprocessor testbed intended to facilitate experimentation with parallel programs and programming languages. It consists of up to eight clusters, with 4-8 processors in each cluster. The processors in each cluster communicate using a shared bus, but each processor also has a private path to some memory. The novel feature of Concert is the
RingBus
, a segmented bus in the shape of a ring that permits communication between clusters at relatively low cost. Efficient arbitration among requests to use the RingBus is a major challenge, which is met by a novel hardware organization, the
criss-cross arbiter
. Simulation of the Concert RingBus and arbiter show their performance to lie between that of a crossbar switch and a simple shared intercluster bus.
An instruction fetch unit for a graph reduction machine
Authors: Thakkar S. S. , Hostmann W. E.
Published: July 2004

The G-machine provides architecture support for the evaluation of functional programming languages by graph reduction. This paper describes an instruction fetch unit for such an architecture that provides a high throughput of instructions, low latency and adequate elasticity in the instruction pipeline. This performance is achieved by a hybrid instruction set and a decoupled RISC architecture. The hybrid instruction set consists of complex instructions that reflect the abstract architecture and simple instructions that reflect the hardware implementation. The instruction fetch unit performs translation from complex instruction to a sequence of simple instructions which can be executed rapidly. A suitable mix of techniques, including cache, buffers and the translation scheme, provide the memory bandwidth required to feed a RISC execution unit. The simulation results identify the performance gains, maximum throughput and minimum latency achieved by various techniques. Results achieved here are in general applicable to von Neumann architectures.
Fast object-oriented procedure calls: lessons from the Intel 432
Authors: Gehringer E. F. , Colwell R. P.
Published: July 2004

As modular programming grows in importance, the efficiency of procedure calls assumes an ever more critical role in system performance. Meanwhile, software designers are becoming more aware of the benefits of object-oriented programming in structuring large software systems. But object-oriented programming requires a good deal of support, which can best be distributed between the compiler and architectural levels. A major part of this support relates to the execution of procedure calls. Must such support exact an unacceptable performance penalty? By considering the case of the Intel 432, a prominent object-oriented architecture, we argue that it need not. The 432 provided all the facilities needed to support object orientation. Though its procedure call was slow, the reasons were only tenuously related to object orientation. Most of the inefficiency could be removed in future designs by the adoption of a few new mechanisms: stack-based allocation of contexts, a memory-clearing coprocessor, and the use of multiple register sets to hold addressing information. These proposals offer the prospect of an object-oriented procedure call that can, on average, be performed nearly as fast as an ordinary unprotected procedure call.
Performance measurement of paging behavior in multiprogramming systems
Authors: Malkawi M. I. , Patel J. H.
Published: July 2004

This paper presents empirical results on the performance of CD, a compiler directed memory management policy, and the Working Set policy in a multiprogramming system. A description of the multiprogramming model used in the experiments is also presented. The results show that CD outperforms WS in terms of fault rate, space time cost, and throughput characteristics. Moreover, WS is shown to lack controllability. Two anomaly types are reported in this paper, both of which are exhibited by WS but not by CD.
Experimenting with EPILOG: some results and preliminary conclusions
Authors: Wise M. J.
Published: July 2004

The EPILOG language and model of computation are briefly described, together with four multiprocessor architectures on which it is proposed to run the model: a form of chordal network and a slight variant of Wu and Feng's Baseline and Reverse Baseline networks. Results are reported for the simulated execution of some EPILOG programs on these architectures. Finally, some tentative conclusions are drawn and some possible avenues for future research are indicated.
An efficient routing control for the SIGMA network Σ
(4)
Authors: Seznec A.
Published: July 2004

When processing vectors on SIMD computers, the interconnection network may become the bottleneck for performances if it lacks an efficient routing control unit. In the pass, many multistage networks have been designed, but general algorithms to control them cannot be used at execution time : they are too time consuming. This has led many manufacturers to use crossbar networks in the design of SIMD computers. In [Se84a],[Se84b], we defined the Sigma network Σ
(n)
and we gave realistic algorithms to control it for performing families of permutations covering standard needs in vector processing. Here, we expose the design of a very efficient control unit for the Sigma network Σ
(4)
(16 entries, 16 exits).
REYSM, a high performance, low power multi-processor bus
Authors: Nicoud J. D. , Skala K.
Published: July 2004

In order to build lower cost multimicroprocessor systems, a narrow synchronous bus (15 active lines) is proposed. It multiplexes address and data on 8 bits, and arbitrates in two pipe-lined cycles on four lines. Due to the 20 to 40 MHz bus clock, and the pipelined control logic, the performances are equivalent to Multibus-2, IEEE-P896 and similar 32-bit buses.

For the implementation, cards are disposed radially around a special connector. The very short connections allows for the usage of fast HC-MOS drivers with only a light adaptation.
Evaluation of the SPUR Lisp architecture
Authors: Taylor G. S. , Hilfinger P. N. , Larus J. R. , Patterson D. A. , Zorn B. G.
Published: July 2004

The SPUR microprocessor has a 40-bit tagged architecture designed to improve its performance for Lisp programs. Although SPUR includes just a small set of enhancements to the Berkeley RISC-II architecture, simulation results show that with a 150-ns cycle time SPUR will run Common Lisp programs at least as fast as a Symbolies 3600 or a DEC VAX 8600. This paper explains SPUR's instruction set architecture and provides measurements of how certain components of the architecture perform.
Evaluation of a prototype data flow processor of the SIGMA-1 for scientific computations
Authors: Shimada T. , Hiraki K. , Nishida K. , Sekiguchi S.
Published: July 2004

A processing element and a structure element of data flow computer SIGMA-1 for scientific computations is now operational. The elements are evaluated for several benchmark programs. For efficient execution of loop constructs, the sticky token mechanism which holds loop invariants is evaluated and exhibits a remarkable effect. From the standpoint that performance of a single processor of a data flow computer must be comparable to that of a Von Neumann computer, comparison of both computers is discussed and improvement of the SIGMA-1 instruction set is proposed.
Stored data structures on the Manchester dataflow machine
Authors: Sargeant J. , Kirkham C. C.
Published: July 2004

Experience with the Manchester Dataflow Machine has highlighted the importance of efficient handling of stored data structures in a practical parallel machine. It has proved necessary to add a special-purpose structure store to the machine, and this paper describes the role of this structure store and the software which uses it. Some key issues in data structure handling for parallel machines are raised.
On design of rotary array communication and wavefront-driven algorithms for solving large-scale band-limited matrix equations
Authors: Onaga K. , Takechi T.
Published: July 2004

This paper proposes a design of matrix machines for solving large-scale band-limited matrix equations. The design provides a guide-line for specifying functionality of each processing element PE, array arrangements of PEs, communication structures and parallel algorithms. The basic feature of the design is (1) a rotary array arrangement of data-flow type PEs with the slant width 2B-1 and circumference Z, on which the diagonal strip of a band-limited matrix data is wound around, and (2) wavefront-sequential executions of tasks, each of which is consisted of a group of pipelined wavefronts and circulates around the rotary array. The wavefront algorithm first produces the Gaussian solution via LU decomposition and then its accuracy is improved by applying the incomplete LU (conjugate) residual iteration.
A computer architecture for dynamic finite element analysis
Authors: Napolitano L. M.
Published: July 2004

The explicit finite element method for dynamic structural analysis can be expressed in a highly parallel form. A proposed architecture is described that addresses the fundamental algorithmic issues of the method. An approximation equation for the efficiency is given as a function of processing time for a single element, the fundamental interprocessor communication time, the number of processors, and the number of finite elements. The predicted speedups are plotted against postulated parallel processor speedup bounds, and are shown to be much closer to the upper (linear) bound than to the lower bounds of Amdahl and Minsky.
Pseudo MIMD array processor—AAP2
Authors: Kondo T. , Tsuchiya T. , Kitamura T. , Sugiyama Y. , Kimura T.
Published: July 2004

A highly integrated array processor (AAP2)-LSI has been developed. After the past 3 years study on the adaptive array processor 1 (AAP1), a challenging improvements on the SIMD's restraints are achieved by using the AAP2-LSI. The AAP2 array system makes it possible to carry out wideband modifiable operation (pseudo MIMD). Furthermore, each PE is capable of supporting a large amount of memory. The AAP2 potential for massively, parallel and pipelined processing is discussed in the field of image processing and CAD applications.

A highly integrated array processor (AAP2)-LSI has been developed. After the past 3 years study on the adaptive array processor 1 (AAP1), a challenging improvements on the SIMD's restraints are achieved by using the AAP2-LSI. The AAP2 array system makes it possible to carry out wideband modifiable operation (pseudo MIMD). Furthermore, each PE is capable of supporting a large amount of memory. The AAP2 potential for massively, parallel and pipelined processing is discussed in the field of image processing and CAD applications.
An in-cache address translation mechanism
Authors: Wood D. A. , Eggers S. J. , Gibson G. , Hill M. D. , Pendleton J. M.
Published: July 2004

In the design of SPUR, a high-performance multiprocessor workstation, the use of large caches and hardware-supported cache consistency suggests a new approach to virtual address translation. By performing translation in each processor's virtually-tagged cache, the need for separate translation lookaside buffers (TLBs) is eliminated. Eliminating the TLB substantially reduces the hardware cost and complexity of the translation mechanism and eliminates the translation consistency problem. Trace-driven simulations show that normal cache behavior is only minimally affected by caching page table entries, and that in many cases, using a separate device would actually reduce system performance.
On the use of registers vs. cache to minimize memory traffic
Authors: Goodman J. R. , Hsu W. C.
Published: July 2004

Single-chip computers are becoming increasingly limited by the access constraints to off-chip memory. To achieve high performance, the structure of on-chip memory must be appropriate, and it must be allocated effectively to minimize off-chip communication. We report experiments that demonstrate that on-chip memory can be effective for local variable accesses. For best use of the limited on-chip area, we suggest organizing memory as registers and argue that an effective register spilling scheme is required. We introduce a heuristic algorithm for register spilling within basic blocks and demonstrate that trace optimization techniques can extend the use of the algorithm to global allocation. Through trace simulation, we show that the use of registers can be more effective in reducing the bus traffic than cache memory of the same size.
Highly concurrent scalar processing
Authors: Hsu P. Y T , Davidson E. S.
Published: July 2004

High speed scalar processing is an essential characteristic of high performance general purpose computer systems. Highly concurrent execution of scalar code is difficult due to data dependencies and conditional branches. This paper proposes an architectural concept called
guarded instructions
to reduce the penalty of conditional branches in deeply pipelined processors. A code generation heuristic, the
decision tree scheduling
technique, reorders instructions in a complex of basic blocks so as to make efficient use of guarded instructions. Performance evaluation of several benchmarks are presented, including a module from the UNIX kernel. Even with these difficult scalar code examples, a speedup of two is achievable by using conventional pipelined uniprocessors augmented by guard instructions, and a speedup of three or more can be achieved using processors with parallel instruction pipelines.
Reducing the cost of branches
Authors: McFarling S. , Hennesey J.
Published: July 2004

Pipelining is the major organizational technique that computers use to reach higher single-processor performance. A fundamental disadvantage of pipelining is the loss incurred due to branches that require stalling or flushing the pipeline. Both hardware solutions and architectural changes have been proposed to overcome these problems. This paper examines a range of schemes for reducing branch cost focusing on both static (compile-time) and dynamic (hardware-assisted) prediction of branches. These schemes are investigated from quantitative performance and implementation viewpoints.
1
Memory access buffering in multiprocessors
Authors: Dubois M. , Scheurich C. , Briggs F.
Published: July 2004

In highly-pipelined machines, instructions and data are prefetched and buffered in both the processor and the cache. This is done to reduce the average memory access latency and to take advantage of memory interleaving. Lock-up free caches are designed to avoid processor blocking on a cache miss. Write buffers are often included in a pipelined machine to avoid processor waiting on writes. In a shared memory multiprocessor, there are more advantages in buffering memory requests, since each memory access has to traverse the memory- processor interconnection and has to compete with memory requests issued by different processors. Buffering, however, can cause logical problems in multiprocessors. These problems are aggravated if each processor has a private memory in which shared writable data may be present, such as in a cache-based system or in a system with a distributed global memory. In this paper, we analyze the benefits and problems associated with the buffering of memory requests in shared memory multiprocessors. We show that the logical problem of buffering is directly related to the problem of synchronization. A simple model is presented to evaluate the performance improvement resulting from buffering.
The TickerTAIP parallel RAID architecture
Authors: Cao Pei , Lim Swee Boon , Venkataraman Shivakumar , Wilkes John
Published: July 2004

Traditional disk arrays have a centralized architecture, with a single controller through which all requests flow. Such a controller is a single point of failure, and its performance limits the maximum size that the array can grow to. We describe here TickerTAIP, a parallel architecture for disk arrays that distributed the controller functions across several loosely-coupled processors. The result is better scalability, fault tolerance, and flexibility.

This paper presents the TickerTAIP architecture and an evaluation of its behavior. We demonstrate the feasibility by an existence proof; describe a family of distributed algorithms for calculating RAID parity; discuss techniques for establishing request atomicity, sequencing and recovery; and evaluate the performance of the TickerTAIP design in both absolute terms and by comparison to a centralized RAID implementation. We conclude that the TickerTAIP architectural approach is feasible, useful, and effective.
Parity logging overcoming the small write problem in redundant disk arrays
Authors: Stodolsky Daniel , Gibson Garth , Holland Mark
Published: July 2004

Parity encoded redundant disk arrays provide highly reliable, cost effective secondary storage with high performance for read accesses and large write accesses. Their performance on small writes, however, is much worse than mirrored disks—the traditional, highly reliable, but expensive organization for secondary storage. Unfortunately, small writes are a substantial portion of the I/O workload of many important, demanding applications such as on-line transaction processing. This paper presents parity logging, a novel solution to the small write problem for redundant disk arrays. Parity logging applies journalling techniques to substantially reduce the cost of small writes. We provide a detailed analysis of parity logging and competing schemes—mirroring, floating storage, and RAID level 5— and verify these models by simulation. Parity logging provides performance competitive with mirroring, the best of the alternative single failure tolerating disk array organizations. However, its overhead cost is close to the minimum offered by RAID level 5. Finally, parity logging can exploit data caching much more effectively than all three alternative approaches.
A comparison of dynamic branch predictors that use two levels of branch history
Authors: Yeh Tse-Yu , Patt Yale N.
Published: July 2004

Recent attention to speculative execution as a mechanism for increasing performance of single instruction streams has demanded substantially better branch prediction than what has been previously available. We [1,2] and Pan, So, and Rahmen [4] have both proposed variations of the same aggressive dynamic branch predictor for handling those needs. We call the basic model Two-Level Adaptive Branch Prediction; Pan, So, and Rahmeh call it Correlation Branch Prediction. In this paper, we adopt the terminology of [2] and show that there are really nine variations of the same basic model. We compare the nine variations with respect to the amount of history information kept. We study the effects of different branch history lengths and pattern history table configurations. Finally, we evaluate the cost effectiveness of the nine variations.
Improving AP1000 parallel computer performance with message communication
Authors: Horie Takeshi , Hayashi Kenichi , Shimizu Toshiyuki , Ishihata Hiroaki
Published: July 2004

The performance of message-passing applications depends on cpu speed, communication throughput and latency, and message handling overhead. In this paper we investigate the effect of varying these parameters and applying techniques to reduce message handling overhead on the execution efficiency of ten different applications. Using a message level simulator set up for the architecture of the AP1000, we showed that improving communication performance, especially message handling, improves total performance. If a cpu that is 32 times faster is provided, the total performance increases by less than ten times unless message handling overhead is reduced. Overlapping computation with message reception improves performance significantly. We also discuss how to improve the AP1000 architecture.
Instruction execution sequence confirmation
Authors: Litchfield Kay P.
Published: July 2004

Acquiring extremely dependable results from computers requires attention to all of the stages from program and machine design through execution of the program. One of the smaller, but still important, stages is that of verifying that the sequence of instructions executed by the processor was exactly the sequence specified by the compiler. A surprisingly small addition to the logic of the processor (and code produced by the compiler) is sufficient to achieve this.
Report of the 1993 workshop on rapid prototyping of microelectronic systems for universities
Authors: Allen Phil , Brglez Franc , Carter Hal , Caverly Robert , Dillion Jerry , Lo Albert , Lomax Ron , Oldfield John , Pina Cesar , Wilkinson T. J.
Published: July 2004

Under sponsorship of the National Science Foundation, eleven participants from universities and industry and seven individuals from the NSF met during October 18-19, 1993, to assess the unique needs educators have for rapid prototyping of microelectronic systems and to suggest potential solutions for continuously improving the state-of-the-art in U.S. universities. The following vision statement was adopted: Educate students who can use the paradigm of design, simulate, design-for-test, build and test (as opposed to just design, build and test) to create microelectronic systems, not just integrated circuits tiCs), of sufficient quality that the global competitiveness of U.S. industry will be continued and enhanced. From this statement a number of findings and recommendations were made. Some of these include: (1) Student projects should be simulated thoroughly prior to submission to MOSIS for fabrication. (2) The use of Field-Programmable Gate Arrays (FPGAs) to support logic design and systems-oriented courses should be encouraged. (3) Fabrication services provided by MOSIS should be used largely for designs in which some portion has been performed manually. (4) NSF support for advanced classes should be broadened to include not only IC fabrication via MOSIS but also the acquistion of prototyping boards or multi-chip modules (MCMs) (5) Remote access via the Internet to expensive testers and prototyping systems should be made available. (6) MOSIS should add the following services: BiCMOS process, microelectro-mechanical post-processing, optoelectronic device fabrication and MCM prototyping. (7) A national clearinghouse should be supported to provide ready access by the educational community to existing and rapidly emerging resources that are presently dispersed. (8) Conferences, faculty enhancement short courses and newsletters should be supported to encourage widespread exchange of information.
Compile time instruction cache optimizations
Authors: Mendlson Abraham , Pinter Shlomit S. , Shtokhamer Ruth
Published: July 2004

This paper presents a new approach for improving performance of instruction cache based systems. The idea is to prevent cache misses caused when different segments of code which are executed in the same loop are mapped onto the same cache area. The new approach uses static information only and does not rely on any special hardware mechanisms such as support of noncachable addresses.The technique is based on replication of code together with algorithms for code placement. We introduce the notion of abstract caches and present simulation results of the new technique. The results show that in certain cases, the number of cache misses is reduced by two orders of magnitude.
HALSIM—a very fast SPARC V9 behavioral model
Authors: Barach David , Kohli Jaspal , Slice John , Spaulding Marc , Bharadhwaj Rajeev , Hudson Don , Neighbors Cliff , Saxena Nirmal , Crunk Rolland
Published: July 2004

This paper describes several implementation techniques used in HAL's 250 KIPS SPARC V9 behavioral model. Beyond presenting the details of our processor model, we describe several areas of innovation: architectural state-vector capture for injection into a gate-level hardware model, using an EDC polynomial-based signature scheme to verify a hardware design; obtaining accurate kernel and user-mode instruction trace data.
Performance evaluation of a massively parallel I/O subsystem
Authors: Baylor Sandra Johnson , Benveniste Caroline , Hsu Yarsun
Published: July 2004

Presented are the trace-driven simulation results of a study conducted to evaluate the performance of the internal parallel I/O subsystem of the Vulcan MPP architecture. The system sizes evaluated vary from 16 to 512 nodes. The results show that a compute node to I/O node ratio of four is the most cost effective for all system sizes, showing high scalability. Also, processor-to-processor communication effects are negligible for small message sizes and the greater the fraction of I/O reads, the better the I/O performance. Worse case I/O node placement is within 13% of more efficient placement strategies. Introducing parallelism into the internal I/O subsystem improves I/O performance significantly.
Instability in parallel I/O systems
Authors: Sinclair James B. , Tang Jay , Varman Peter J.
Published: July 2004

The performance of a shared-disk parallel I/O system with several concurrent processes is studied. It is observed that under some naturally occurring conditions such a system can exhibit instability, with a subset of the processes racing ahead of the others and monopolizing I/O resources. This race can lead to serialization of the processes and poor disk utilization. The study has implications for both data placement in multiple disk systems and task partitioning for parallel processing.
Measurement of I/O bus contention and correlation among heterogeneous device types in a single-bus multiprocessor system
Authors: Vanderleest Steven H. , Iyer Ravishankar K.
Published: July 2004

This paper describes an approach to measuring bus contention and quantifying the resulting performance degradation. The focus is contention for a single I/O bus resulting from accesses to multiple heterogeneous I/O device types in an MP system. Heterogeneous device types are defined as devices that have widely different characteristics, such as video, network, and disk devices. Correlation analysis is used to characterize the contention and then the corresponding loss in performance is quantified using actual trace data.