bluuebunny/crossref_metadata_2025 huggingface dataset:
The predictability of load address
Authors: Zhang Jinsuo
Published: July 2004

Memory access latency is the traditional bottleneck of system performance. Cache is historically introduced to bridge the big gap between processor and main memory so as to reduce the load-to-use delay. The traditional one cycle cache latency has already caused problems for pipeline execution. The situation becomes worse for modern deep pipelined superscalar processor when clock rate continues to increase and cache capacity increases, which inevitably lead to more cycle cache latency.Load address prediction could alleviate the load-to-use delay by predicting the target address of load instruction in the early stage of pipeline. But existing address prediction schemes can only predict up to 67% regular address pattern.To explore the potential of address prediction, in this paper, from the program behavior, we study and simulate various load address change patterns. Our results first show that the address of load has high repeatability. We further classify load instructions naturally into several categories and analyze their behavior respectively. The reason for both correct address prediction and incorrect prediction are studied from program behavior. The load instructions with low prediction rate are further analyzed. Focused on the high misprediction for load from stack scalar variable, one new prediction schemes: stack coloring is proposed. Furthermore, we also propose a new context predictor: global context predictor, which greatly saves the prediction resources. Our results show that the high predictability with 77.5%, 75.8% and 90.6% can be achieved for stride, context and hybrid predictor respectively.
Adapting Tomasulo's algorithm for bytecode folding based Java processors
Authors: El-Kharashi M. Watheq , Elguibaly Fayez , Li Kin F.
Published: July 2004

A novel processor architecture for hardware execution of Java bytecodes is presented. Stack dependency is resolved by the use of a hardware bytecode folding algorithm coupled with Tomasulo's scheduling algorithm. In this paper, we present a framework for adapting Tomasulo's algorithm for bytecode folding based Java processors. We discuss a set of architectural features that are tailored for Java execution as well as for general-purpose Java-independent codes. A comprehensive example is included to illustrate these features graphically.
A microbenchmark suite for OpenMP 2.0
Authors: Bull J. Mark , O'Neill Darragh
Published: July 2004

In this paper we present a set of extensions to an existing microbenchmark suite for OpenMP. The new benchmarks are targeted at directives introduced in the OpenMP 2.0 standard, as well as at the handling of thread-private data structures. Results are presented for a Sun HPC 6500 system, with an early access release of an OpenMP 2.0 compliant compiler, and for an SGI Origin 3000 system.
Multithreading decoupled architectures for complexity-effective general purpose computing
Authors: Sung Michael , Krashinsky Ronny , Asanović Krste
Published: July 2004

Decoupled architectures have not traditionally been used in the context of general purpose computing because of their inability to tolerate control-intensive code that exists across a wide range of applications. This work investigates the possibility of using multithreading to overcome the loss of decoupling dependencies that represent the cause of this main limitation in decoupled architectures. A proposal for a multithreaded decoupled control/access/execute architecture is presented as a platform for achieving high performance on general purpose workloads. It is argued that such a decoupled architecture is more complexity-effective and scalable than comparable superscalar processors, which incorporate enormous amounts of complexity for modest performance gains.
A hierarchical microcomputer system for hardware and software development
Authors: Ravi C. V. , Moller Torben
Published: July 2004

This paper describes a facility for integrated hardware and software development in the microprocessor area by graduate students. The constraints of a low budget, the necessity of providing fast turn-around time for software development, and tightly scheduled laboratory sessions, all of which are necessary in a university environment, precluded the use of methods such as primitive handtranslation of code (too slow), separate floppy-based development systems (too expensive) and in-circuit emulators (too expensive). The result was a hierarchical network of microprocessors whose design and development is described in detail. Experience with its operation and the applicability of the system for more general use is also discussed.
Architecture of the CORAIL building block system
Authors: Poujoulat G. H.
Published: July 2004

The CORAIL system is a set of modular elements, the architect obtains a specialized machine that suits for the desired supervisor system that is immediately operational.
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.
Function distribution in computer system architectures
Authors: Lawson Harold W.
Published: July 2004

The levelwise structuring and complexity of a computer system is presented informally and as a general model based upon the notion of abstract machines (processors), processes and interpreters. The important domains of the computer architect are considered along with historical perspectives of certain stimulae and decisions that have affected the distribution of functions amongst the various levels of computer system implementations.
Architectural support for system protection (Recent Results)
Authors: Fernandez Eduardo B. , Summers Rita C. , Coleman Charles D.
Published: July 2004

A set of architectural extensions, involving hardware/software interaction, is proposed to constrain the execution-time behavior of application and higher authority programs, running in a CPU of the type of IBM System 370. The extensions consist of the addition of a new state to the previous supervisor and problem states enforcement of disciplined transition between states, hardware distinction of four data types, and a set of rules that enforce the structure of processes operating in this environment. Application of the extensions to a shared data base shows that the protection of the operating system under which it runs can be enhanced significantly, with respect to errors or attacks from the users of this data base.
An investigation of descriptor oriented architecture
Authors: Welch Terry A.
Published: July 2004

A computer architecture is proposed which uses a hardware implemented descriptor system to provide facilities for explicit data typing, memory relocation, and access protection at the data element level. The problem of having to fetch descriptors for every operand access is overcome by storing descriptors in small fast memories of various types. The resulting machine runs simple languages (such as FORTRAN) as fast as conventional architectures, and offers significant speed improvement for languages using complex data types (such as data management systems). The cost of the descriptor storage hardware is shown to be modest, so this architecture would be suitable for machines as small as a large minicomputer.
On-line architecture tuning using microcapture
Authors: Abd-Alla A. M. , Moffett Laird H.
Published: July 2004

The modification or tuning of the micro-code in a computer that utilizes a writable control store is one method whereby a program's execution time can be improved. A method for automatically performing a microcode tuning or synthesis has been developed by Drs. Karl-gaard and Abd-Alla and is discussed in detail in [1]. Presented is an extension of this effort which allows the microcode tuning to be performed on-line on program loops. This is accomplished by gathering data on characteristics of the program during its execution, utilizing this data to generate the information required to tune the microprogram, initiating the on-line tuning procedure, and transferring to the tuned routine to complete the execution.
Some implementations of segment sequential functions
Authors: Bush J. A. , Lipovski G. J. , su S. Y. W. , Watson J. K. , Ackerman S. J.
Published: July 2004

Since conventional computers are straining to handle the increased size and sophistication of non-numeric processing (data management, information retrieval, artificial intelligence), a new class of non-numeric architectures is evolving. The segment sequential architecture is one of these. Further development of this architecture requires new techniques for multiple cell operation and intercell communication to handle control and search operations. This paper describes such techniques for instruction fetching, operand recall, string, set and tree context searching, and pointer transfer. It is expected that combinations of these techniques will appear in future architectures that are needed for non-numeric processing.
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.
A bit-plane architecture for optical computing with two-dimensional symbolic substitution
Authors: Louri A. , Hwang K.
Published: July 2004

A novel architecture based on optical technology is presented for constructing parallel computers. The architecture exploits optics for its ultra-high speed, massive parallelism, and dense connectivity. The processing is based on a new technique called
2-D symbolic substitution
which can be implemented with very fast optical components. Two-dimensional symbolic substitution algorithms are developed for arithmetic/logic operations as well as for complex scientific computations such as matrix algebra and FFT. The predicted performance of the system is compared with the performance of existing electronic array processors and is shown to be potentially superior. The
bit-plane
architecture is shown feasible and economical based on state-of-the-art optical and electro-optical technologies.
The performance potential of multiple functional unit processors
Authors: Pleszkun A. R. , Sohi G. S.
Published: July 2004

In this paper, we look at the interaction of pipelining and multiple functional units in single processor machines. When implementing a high performance machine, a number of hardware techniques maybe used to improve the performance of the final system. Our goal is to gain an understanding of how each of these techniques contribute to performance improvement. As a basis for our studies we use a CRAY-like processor model and the issue rate (instructions per clock cycle) as the performance measure. We then systematically augment this base, non-pipelined, machine with more and more hardware features and evaluate the performance impact of each feature. We find, for example, that in non-vector machines, pipelining multiple function units does not provide significant performance improvements. Dataflow limits are then derived for our benchmark programs to determine the performance potential of each benchmark. In addition, other limits are computed which apply more realistic constraints on a computation. Based on these more realistic limits, we determine it is worthwhile to investigate the performance improvements that can be achieved from issuing multiple instructions each clock cycle. Several hardware approaches are evaluated for issuing multiple instructions each clock cycle.
Exploiting parallel microprocessor microarchitectures with a compiler code generator
Authors: Hwu W. W. , Chang P. P.
Published: July 2004

With advances in VLSI technology, microprocessor designers can provide more microarchitectural parallelism to increase performance. We have identified four major forms of such parallelism: multiple microoperations issued per cycle, multiple result distribution buses, multiple execution units, and pipelined execution units. The experiments reported in this paper address two important issues: The effects of these forms and the appropriate balance among them. A
central
microarchitecture is identified as the comparison basis. We separately vary each form of the microarchitectural parallelism in the
central
to measure their individual effects on performance. In addition, we vary two forms of the microarchitectural parallelism in the
central
to derive an appropriate balance between them. To make fair comparisons, our compiler generates different code sequences optimized for different microarchitectural configurations. For each given set of technology constraints, these experiments can be used to derive a cost-effective microarchitecture to execute each given set of workload programs at high speed.
Analysis of memory referencing behavior for design of local memories
Authors: McNiven G. D. , Davidson E. S.
Published: July 2004

Memory referencing behavior is analyzed via the study of traces for the purpose of developing new local memory structures and management techniques. A novel trace processing technique called
flattening
reduces the dependence of the results on the underlying compiler and architecture on which the trace was generated, and partitions each memory location into its constituent
values
. The referencing patterns of each value in the resulting trace is described via statistics such as interreference time, lifetime, etc. The referencing patterns of the entire trace are described via histograms showing the distributions of the statistics for the individual values. The results of this analysis indicate the use of a program controlled cache to efficiently reduce the traffic from the cache to main memory. By using program control, the future knowledge of the compiler can be imparted to the cache, allowing the rejection of dead values and early replacement of values with long interreference times.
Performance evaluation of on-chip register and cache organizations
Authors: Eickenmeyer R. J. , Patel J. H.
Published: July 2004

Chip area is a critical resource in the design of VLSI processors. There are many different alternative designs that could fill this chip area. This paper compares several different local memory organizations applicable for single-chip processors. Several cache types—instruction, data, split, unified, stack, top-of-stack—are considered. These are compared to multiple register set architectures to which various caches can also be added. The performance metric of interest is effective access time, since a wide variety of register and cache organizations are used. A model for access time and a model for chip area required for each organization form the basis for comparison. Extensive simulations of several register-memory organizations are presented. Address traces from a VAX-11/780 running systems programs were used in the simulation.
A simulation study of two-level caches
Authors: Short R. T. , Levy H. M.
Published: July 2004

We report on a trace-driven simulation study to examine the effect of a two-level cache hierarchy in uniprocessors. A simulation model of a multiple-cycle-per-instruction processor was constructed to estimate the total cycles required to execute a synthetic benchmark. Results show that a second-level cache can be used to increase system performance when main memory access times are large relative to CPU cycle time. For example, the addition of a 4-cycle, 64K second-level cache following a 1-cycle, 8K first-level cache increases performance by 15 percent when used in a system with a 15-cycle primary memory. Second level caches are shown to be particularly effective when used behind small on-chip caches; adding an 8K second-level to a 1K first-level increases performance by 26 percent, assuming similar parameters. We also evaluate the performance impact of different write strategies and separate I and D caches.
Analysis of bus hierarchies for multiprocessors
Authors: Winsor D. C. , Mudge T. N.
Published: July 2004

In order to build large shared-memory multiprocessor systems that take advantage of current hardware-enforced cache coherence protocols, an interconnection network is needed that acts logically as a single bus while avoiding the electrical loading problems of a large bus. This paper develops models of bus delay and bus throughput to aid in optimizing the design of such a network. These models are used to derive a method for determining the maximum number of processors that can be supported by each of several bus organizations including conventional single-level buses, two-level bus hierarchies, and binary tree interconnections. An example based on a TTL bus is presented to illustrate the methods and to show that shared-memory multiprocessors with several dozen processors are feasible using a simple two-level bus hierarchy.
Extra group network: a cost-effective fault-tolerant multistage interconnection network
Authors: Wei S. , Lee G.
Published: July 2004

This paper introduces a new class of fault-tolerant multistage interconnection networks, dubbed as Extra Group Networks (EGNs). An EGN-
m
of size
N
is designed to have
m
+ 1 unique path multistage networks of size
N/m
. This approach of constructing the network allows that an EGN-
m
can provide “full access” capability in the presence of multiple faults, up to
m
, in any stage. EGNs can also maintain the permutation capability of the unique path multistage network of size
N
in the presence of any single fault. We show that EGNs are most cost-effective than other previously proposed fault-tolerant multistage interconnection networks with a similar fault-tolerant capability.
Flagship: a parallel architecture for declarative programming
Authors: Watson I. , Woods V. , Watson P. , Banach R. , Greenberg M. , Sargeant J.
Published: July 2004

The Flagship project aims to produce a computing technology based on the declarative style of programming. A major component of that technology is the design for a parallel machine which can efficiently exploit the implicit parallelism in declarative programs. This paper describes the computational models which expose this implicit parallelism, and outlines an architecture designed to exploit it. The operational issues, such as dynamic load balancing, which arise in such a system are discussed, and the mechanisms being used to evaluate the architecture are described.
Priority-driven, preemptive I/O controllers for real-time systems
Authors: Sprunt B. , Kirk D. , Sha L.
Published: July 2004

Current I/O controller architectures inhibit the use of priority-driven preemptive scheduling algorithms that can guarantee hard deadlines in real-time systems. This paper examines the effect of three I/O controller architectures upon schedulable utilization, which is the highest attainable resource utilization at or below which all deadlines can be guaranteed. FIFO request queueing, priority queueing, and priority queueing with preemptable service are simulated for a range of CPU computation to I/O traffic ratios. The results show that, for I/O bound tasks sets and zero preemption costs, priority queueing with preemptable service can provide a level of schedulable utilization 35% higher than that attainable with FIFO queueing and 20% higher than priority queueing and nonpreemptable service. Although the potential gain for priority queueing with preemptable service is large, further simulations that incorporate a time penalty for each preemption show that the gain is very sensitive to preemption cost. With preemption cost represented as a ratio of preemption time to the minimum task period, the level of schedulable utilization for priority queueing with preemptable service degrades to that of priority queueing with nonpreemptable service, for a preemption cost ratio of 0.04. A high level design of a preemptable I/O controller is described and the issues determining preemption cost are detailed along with techniques for its minimization.
*
Measuring VAX 8800 performance with a histogram hardware monitor
Authors: Clark D. W. , Bannon P. J. , Keller J. B.
Published: July 2004

This paper reports the results of a study of VAX 8800 processor performance using a hardware monitor that collects histograms of the processor's micro-PC and memory bus status. The monitor keeps a count of all machine cycles executed at each micro-PC location, as well as counting all occurrences of each bus transaction. It can measure a running system without interfering with it, and this paper's results are based on measurements of live timesharing. Because the 8800 is a microcoded machine, a great deal of information can be gleaned from these data. The paper reports opcode and operand specifier frequencies, as well as the amount of time spent in instruction execution and various kinds of overhead, such as memory management and cache-wait stalls. The histogram method yields a very detailed picture of the amount of time an average VAX instruction spends in various activities on the 8800.
Design of a concurrent computer for solving systems of linear equations
Authors: Jainandunsing K. , Deprettere E. F.
Published: July 2004

In this paper we describe the design of a systolic array of Householder processor elements, which is dedicated to the solution of large (dense) systems of linear equations. The array is capable of executing two different algorithms. One for the solution of general, non-singular systems and one for the solution of symmetric, positive definite systems. The array is designed systematically and such that its dimensions are independent of the size of the problem.
Scrambled storage for parallel memory systems
Authors: Lee D.
Published: July 2004

A scrambled storage scheme is proposed for storing arrays of
NXN
elements in
N
= 2

n

parallel memory modules to allow conflict-free access to various array partitions. It is shown that the scheme allows conflict-free access to rows, columns, square blocks, and distributed blocks of stored arrays. An alternative way of achieving the desired accessibility would use Budnik and Kuck's nonuniform skewed storage [3]; in this case, addressing hardware would require Ο(
n
X2

n

) exclusive-or circuits. The proposed scheme has, however, the advantage of simplifying address generation; addressing hardware requires
n
exclusive-or circuits only. Some of the important questions of scrambling/unscrambling data through a proposed interconnection network are discussed.
Distributed round-robin and first-come first-serve protocols and their applications to multiprocessor bus arbitration
Authors: Vernon M. K. , Manber U.
Published: July 2004

Two new distributed protocols for fair and efficient bus arbitration are presented. The protocols implement round-robin (RR) and first-come first-serve (FCFS) scheduling, respectively. Both protocols use relatively few control lines on the bus, and their logic is simple. The round-robin protocol, which uses
statically assigned
arbitration numbers to resolve conflict during an arbitration, is more robust and simpler to implement than previous distributed RR protocols that are based on rotating agent priorities. The proposed FCFS protocol uses partly static arbitration numbers, and is the first practical proposal for a FCFS arbiter known to the authors. The proposed protocols thus have a better combination of efficiency, cost, and fairness characteristics than existing multiprocessor bus arbitration algorithms.

Three implementations of our RR protocol, and two implementations of our FCFS protocol, are discussed. Simulation results are presented that address: 1) the practical potential for unfairness in the simpler implementation of the FCFS protocol, 2) the practical implications of the higher waiting time variance in the RR protocol, and 3) the allocation of bus bandwidth among agents with unequal request rates in each protocol. The simulation results indicate that there is very little practical difference in the performance of the two protocols.
A cache coherence scheme with fast selective invalidation
Authors: Cheong H. , Vaidenbaum A. V.
Published: July 2004

Software-assisted cache coherence enforcement schemes for large multiprocessor systems with shared global memory and interconnection network have gained increasing attention. Proposed software-assisted approaches rely on either indiscriminate invalidation or selective invalidation to invalidate stale cache lines. The indiscriminate approach combined with advanced memory hardware can quickly invalidate the entire cache but may result in lower hit ratios. The selective approach may achieve a better hit ratio. However, sequential selection and invalidation of cache or TLB entries is time consuming. We propose a new solution that offers the fast operation of the indiscriminate invalidation approach and can selectively invalidate cache items without extensive run-time book-keeping and checking. The solution relies on the combination of compile-time reference tagging and individual invalidation of potentially stale cache lines only when referenced. Performance improvement over an indiscriminate invalidation approach is presented.
An accurate and efficient performance analysis technique for multiprocessor snooping cache-consistency protocols
Authors: Vernon M. K. , Lazowska E. D. , Zahorjan J.
Published: July 2004

A number of dynamic cache consistency protocols have been developed for multiprocessors having a shared bus interconnect between processors and shared memory. The relative performance of these protocols has been studied extensively using simulation and detailed analytical models based on Markov chain techniques. Both of these approaches use relatively detailed models, which capture cache and bus interference rather precisely, but which are highly expensive to evaluate. In this paper, we investigate the use of a more abstract and significantly more efficient analytical model for evaluating the relative performance of cache consistency protocols. The model includes bus interference, cache interference, and main memory interference, but represents the interactions between the caches by steady-state mean collision rates which are computed by iterative solution of the model equations.

We show that the speedup estimates obtained from the mean-value model are highly accurate. The results agree with the speedup estimates of the detailed analytical models to within 3%, over all modifications studied and over a wide range of parameter values. This result is surprising, given that the distinctions among the protocols are quite subtle. The validation experiments include sets of reasonable values of the workload parameters, as well as sets of unrealistic values for which one might expect the mean-value equations to break down. The conclusion we can draw is that this modeling technique shows promise for evaluating architectural tradeoffs at a much more detailed level than was previously thought possible. We also discuss the relationship between results of the analytical models and the results of independent evaluations of the protocols using simulation.
Destination tag routing techniques based on a state model for the LADM network
Authors: Rau D. , Fortes J. A. B. , Siegel H. J.
Published: July 2004

A “state model” is proposed for solving the problem of routing and rerouting messages in the Inverse Augmented Data Manipulator (IADM) network. Using this model, necessary and sufficient conditions for the reroutability of messages are established, and then destination tag schemes are derived. These schemes are simpler, more efficient and require less complex hardware than previously proposed routing schemes. Two destination tag schemes are proposed. For one of the schemes, rerouting is totally transparent to the sender of the message and any blocked link of a given type can be avoided. Compared with previous works that deal with the same type of blockage, the timexspace complexity is reduced from Ο(logN) to Ο(1). For the other scheme, rerouting is possible for any type of link blockage. A universal rerouting algorithm is constructed based on the second scheme, which finds a blockage-free path for any combination of multiple blockages if there exists such a path, and indicates absence of such a path if there exists none. In addition, the state model is used to derive constructively a lower bound on the number of subgraphs which are isomorphic to the Indirect Binary n-Cube network in the IADM network. This knowledge can be used to characterize properties of the IADM networks and for permutation routing in the IADM networks.
Regular CC-banyan networks
Authors: Kim D. W. , Lipovski G J. , Hartmann A. , Jenevein R.
Published: July 2004

Construction algorithms for rectangular and nonrectangular CC-Banyan networks are presented. Routing algorithms for double and single-ended rectangular and non-rectangular CC-Banyan networks are also presented. The time complexities of the routing algorithms are O(
l
), where
l
is the number of stages in the network.
Traffic analysis of rectangular SW-banyan networks
Authors: Jenevein R. M. , Mookken T.
Published: July 2004

This paper describes an algorithm to route packets in Rectangular SW-Banyans. A packet switching scheme is modelled on single and double sided SW-Banyans and the results presented. Effects of queue lengths and processor configurations on performance are studied. Prevention of deadlocks in the network is discussed.
High-performance multi-queue buffers for VLSI communications switches
Authors: Tamir Y. , Frazier G. L.
Published: July 2004

Small
n
x
n
switches are key components of multistage interconnection networks used in multiprocessors as well as in the communication coprocessors used in multicomputers. The design of the internal buffers in these switches is of critical importance for achieving high throughput low latency communication. We discuss several buffer structures and compare them in terms of implementation complexity and their ability to deal with variations in traffic patterns and message lengths. We present a new design of buffers that provide non-FIFO message handling and efficient storage allocation for variable size packets through the use of linked lists managed by a simple on-chip controller. We evaluate the new buffer design by comparing it to several alternative designs in the context of a multi-stage interconnection network. Our modeling and simulations show that the new buffer outperforms its “competition” and can thus be used to improve the performance of a wide variety of systems currently using less efficient buffers.
IMPULSE: a high performance processing unit for multiprocessors for scientific calculation
Authors: Boku T. , Nomura S. , Amano H.
Published: July 2004

In this paper, we propose a high performance processing unit for multiprocessor systems for scientific calculations. This processing unit is called IMPULSE. IMPULSE is equipped with a hardware process control mechanism, and a powerful floating point processor and its controller.

The process control method is based on the concurrent process model called the NC model. In the NC model, the processes and their communicating channels are static, and it is relatively easy to implement the interprocess communication server and process scheduler in hardware according to this model.

To enhance the system performance, IMPULSE is composed of three parts, the TASK ENGINE, IPC ENGINE, and FPP ENGINE. From the results of simulations, it appears that the IPC ENGINE provides efficient process control even if the granularity of the processes is very fine.
Synchronizing processors through memory requests in a tightly coupled multiprocessor
Authors: Seznec A. , Jégou Y.
Published: July 2004

To satisfy the growing need for computing power, a high degree of parallelism will be necessary in future supercomputers. Up to the late 70s, supercomputers were either multiprocessors (SIMD-MIMD) or pipelined monoprocessors. Current commercial products combine these two levels of parallelism.

Effective performance will depend on the spectrum of algorithms which is actually run in parallel. In a previous paper [Je86], we have presented the DSPA processor, a pipeline processor which is actually performant on a very large family of loops.

In this paper, we present the GREEDY network, a new interconnection network (IN) for tightly coupled multiprocessors (TCMs). Then we propose an original and cost effective hardware synchronization mechanism. When DSPA processors are connected with a shared memory through a GREEDY network and synchronized by our synchronization mechanism, a very high parallelism may be achieved at execution time on a very large spectrum of loops including loops where independency of the successive iterations cannot be checked at compile time as e.g. loop 1:

DO 1 I=1 N

1 A(P(I)=A(Q(I))
Design and performance of special purpose hardware for time warp
Authors: Fujimoto R. M. , Tsai J.-J. , Gopalakrishnan G.
Published: July 2004

A special purpose simulation engine based on the Time Warp mechanism is proposed to attack large-scale discrete event simulation problems. A key component of this engine is the rollback chip, a hardware component that efficiently implements state saving and rollback functions in Time Warp. The algorithms implemented by the rollback chip are described, as well as mechanisms that allow efficient implementation. Results of simulation studies are presented that show that the rollback chip can virtually eliminate the state saving overhead that plagues current software implementations of Time Warp.
MASA: a multithreaded processor architecture for parallel symbolic computing
Authors: Halstead R. H. , Fujita T.
Published: July 2004

MASA is a “first cut” at a processor architecture intended as a building block for a multiprocessor that can execute parallel Lisp programs efficiently. MASA features a tagged architecture, multiple contexts, fast trap handling, and a synchronization bit in every memory word. MASA's principal novelty is its use of multiple contexts both to support
multithreaded execution
—interleaved execution from separate instruction streams—and to speed up procedure calls and trap handling in the same manner as register windows. A project is under way to evaluate MASA-like architectures for executing programs written in Multilisp.
Parallel architecture for OPS5
Authors: Butler P. L. , Allen J. D. , Bouldin D. W.
Published: July 2004

An architecture that captures some of the inherent parallelism of the OPS5 expert system language has been designed and implemented at Oak Ridge National Laboratory. A central feature of this architecture is a network bus over which a single host processor broadcasts messages to a set of parallel rule processors. This transmit-only bus is implemented by a memory-mapped scheme which permits the rule processors to be decoded in parallel. All OPS5 rule matching processes and most of the processes associated with conflict resolution are executed by the parallel rule processors. The host performs the tasks associated with the firing of a rule selected by the conflict resolution process. Performance data are presented for the prototype system which comprises a host processor and 64 parallel rule processors, each embodying a Motorola MC68000 microprocessor and 512 Kbytes of unshared memory.
A microprogrammed architecture for front end processing
Authors: Zaks Rodnay
Published: July 2004

The increasing diversity of hardware devices and software procedures developed for remote processing has yielded a multiplicity of new facilities and telecommunication network structures. The corresponding architectures for front-end systems range from specialized device control to sophisticated multi-purpose multi-terminal support. Simultaneously, the very complexity of new data transmission and processing techniques has created a need for flexible and powerful yet transparent communications processors. The functions of a front-end system will be analyzed in order to derive the concepts which will be used to establish a classification.

In a first part, telecommunications and control functions are analyzed in detail, as well as the user facilities at the functional level.

The level of support provided by major commercial operating systems with respect to front-end systems is then examined. Their facilities and shortcomings provide the basis for front-end systems.

Finally, the architecture of a commercial microprogrammed front-end processor is presented. A modular microprogrammed architecture of this type allows efficient and economical system structuring for a wide range of teleprocessing services.
Joint local and global hardware adaptations for energy
Authors: Sasanka Ruchira , Hughes Christopher J. , Adve Sarita V.
Published: July 2004

This work concerns algorithms to control energy-driven architecture adaptations for multimedia applications, without and with dynamic voltage scaling (DVS). We identify a broad design space for adaptation control algorithms based on two attributes: (1) when to adapt or
temporal
granularity and (2) what structures to adapt or
spatial
granularity. For each attribute, adaptation may be
global
or
local.
Our previous work developed a temporally and spatially global algorithm. It invokes adaptation at the granularity of a full frame of a multimedia application (temporally global) and considers the entire hardware configuration at a time (spatially global). It exploits int
er-
frame execution time variability, slowing computation just enough to eliminate idle time before the real-time deadline.This paper explores temporally and spatially local algorithms and their integration with the previous global algorithm. The local algorithms invoke architectural adaptation within an application frame to exploit int
ra-
frame execution variability, and attempt to save energy without affecting execution time. We consider local algorithms previously studied for non-real-time applications as well as propose new algorithms. We find that, for systems without and with DVS, the local algorithms are effective in saving energy for multimedia applications, but the new integrated global and local algorithm is best for the systems and applications studied.
Dynamic dead-instruction detection and elimination
Authors: Butts J. Adam , Sohi Guri
Published: July 2004

We observe a non-negligible fraction--3 to 16% in our benchmarks--of
dynamically dead instructions,
dynamic instruction instances that generate unused results. The majority of these instructions arise from static instructions that also produce useful results. We find that compiler optimization (specifically instruction scheduling) creates a significant portion of these
partially dead
static instructions. We show that most of the dynamically instructions arise from a small set of static instructions that produce dead values most of the time.We leverage this locality by proposing a dead instruction predictor and presenting a scheme to avoid the execution of predicted-dead instructions. Our predictor achieves an accuracy of 93% while identifying over 91% of the dead instructions using less than 5 KB of state. We achieve such high accuracies by leveraging future control flow information (i.e., branch predictions) to distinguish between useless and useful instances of the same static instruction.We then present a mechanism to avoid the register allocation, instruction scheduling, and execution of predicted dead instructions. We measure reductions in resource utilization averaging over 5% and sometimes exceeding 10%, covering physical register management (allocation and freeing), register file read and write traffic, and data cache accesses. Performance improves by an average of 3.6% on an architecture exhibiting resource contention. Additionally, our scheme frees future compilers from the need to consider the costs of dead instructions, enabling more aggressive code motion and optimization. Simultaneously, it mitigates the need for good path profiling information in making inter-block code motion decisions.
An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches
Authors: Kim Changkyu , Burger Doug , Keckler Stephen W.
Published: July 2004

Growing wire delays will force substantive changes in the designs of large caches. Traditional cache architectures assume that each level in the cache hierarchy has a single, uniform access time. Increases in on-chip communication delays will make the hit time of large on-chip caches a function of a line's physical location within the cache. Consequently, cache access times will become a continuum of latencies rather than a single discrete latency. This non-uniformity can be exploited to provide faster access to cache lines in the portions of the cache that reside closer to the processor. In this paper, we evaluate a series of cache designs that provides fast hits to multi-megabyte cache memories. We first propose physical designs for these Non-Uniform Cache Architectures (NUCAs). We extend these physical designs with logical policies that allow important data to migrate toward the processor within the same level of the cache. We show that, for multi-megabyte level-two caches, an adaptive, dynamic NUCA design achieves 1.5 times the IPC of a Uniform Cache Architecture of any size, outperforms the best static NUCA scheme by 11%, outperforms the best three-level hierarchy--while using less silicon area--by 13%, and comes within 13% of an ideal minimal hit latency solution.
Mondrian memory protection
Authors: Witchel Emmett , Cates Josh , Asanović Krste
Published: July 2004

Mondrian memory protection (MMP) is a fine-grained protection scheme that allows multiple protection domains to flexibly share memory and export protected services. In contrast to earlier page-based systems, MMP allows arbitrary permissions control at the granularity of individual words. We use a compressed permissions table to reduce space overheads and employ two levels of permissions caching to reduce run-time overheads. The protection tables in our implementation add less than 9% overhead to the memory space used by the application. Accessing the protection tables adds than 8% additional memory references to the accesses made by the application. Although it can be layered on top of demand-paged virtual memory, MMP is also well-suited to embedded systems with a single physical address space. We extend MMP to support segment translation which allows a memory segment to appear at another location in the address space. We use this translation to implement zero-copy networking underneath the standard read system call interface, where packet payload fragments are connected together by the translation system to avoid data copying. This saves 52% of the memory references used by a traditional copying network stack.
A performance evaluation of the Intel iAPX 432
Authors: Hansen Paul M. , Linton Mark A. , Mayo Robert N. , Murphy Marguerite , Patterson David A.
Published: July 2004

We describe art experiment to test the 432 as a high-level language uniprocessor by comparing it with the 8086, 68000, and VAX-11/780 for four integer and character programs written in Ada, C, and Pascal.