bluuebunny/crossref_metadata_2025 huggingface dataset:
The optimal logic depth per pipeline stage is 6 to 8 FO4 inverter delays
Authors: Hrishikesh M. S. , Burger Doug , Jouppi Norman P. , Keckler Stephen W. , Farkas Keith I. , Shivakumar Premkishore
Published: July 2004

Microprocessor clock frequency has improved by nearly 40% annually over the past decade. This improvement has been provided, in equal measure, by smaller technologies and deeper pipelines. From our study of the SPEC 2000 benchmarks, we find that for a high-performance architecture implemented in 100nm technology, the optimal clock period is approximately 8 fan-out-of-four (FO4) inverter delays for integer benchmarks, comprised of 6 FO4 of useful work and an overhead of about 2 FO4. The optimal clock period for floating-point benchmarks is 6 FO4. We find these optimal points to be insensitive to latch and clock skew overheads. Our study indicates that further pipelining can at best improve performance of integer programs by a factor of 2 over current designs. At these high clock frequencies it will be difficult to design the instruction issue window to operate in a single cycle. Consequently, we propose and evaluate a high-frequency design called a segmented instruction window.
Increasing processor performance by implementing deeper pipelines
Authors: Sprangle Eric , Carmean Doug
Published: July 2004

One architectural method for increasing processor performance involves increasing the frequency by implementing deeper pipelines. This paper will explore the relationship between performance and pipeline depth using a Pentium® 4 processor like architecture as a baseline and will show that deeper pipelines can continue to increase performance.This paper will show that the branch misprediction latency is the single largest contributor to performance degradation as pipelines are stretched, and therefore branch prediction and fast branch recovery will continue to increase in importance. We will also show that higher performance cores, implemented with longer pipelines for example, will put more pressure on the memory system, and therefore require larger on-chip caches. Finally, we will show that in the same process technology, designing deeper pipelines can increase the processor frequency by 100%, which, when combined with larger on-chip caches can yield performance improvements of 35% to 90% over a Pentium® 4 like processor.
A large, fast instruction window for tolerating cache misses
Authors: Lebeck Alvin R. , Koppanalil Jinson , Li Tong , Patwardhan Jaidev , Rotenberg Eric
Published: July 2004

Instruction window size is an important design parameter for many modern processors. Large instruction windows offer the potential advantage of exposing large amounts of instruction level parallelism. Unfortunately naively scaling conventional window designs can significantly degrade clock cycle time, undermining the benefits of increased parallelism.This paper presents a new instruction window design targeted at achieving the latency tolerance of large windows with the clock cycle time of small windows. The key observation is that instructions dependent on a long latency operation (e.g., cache miss) cannot execute until that source operation completes. These instructions are moved out of the conventional, small, issue queue to a much larger waiting instruction buffer (WIB). When the long latency operation completes, the instructions are reinserted into the issue queue. In this paper, we focus specifically on load cache misses and their dependent instructions. Simulations reveal that, for an 8-way processor, a 2K-entry WIB with a 32-entry issue queue can achieve speedups of 20%, 84%, and 50% over a conventional 32-entry issue queue for a subset of the SPEC CINT2000, SPEC CFP2000, and Olden benchmarks, respectively.
ReVive
Authors: Prvulovic Milos , Zhang Zheng , Torrellas Josep
Published: July 2004

This paper presents ReVive, a novel general-purpose rollback recovery mechanism for shared-memory multiprocessors. ReVive carefully balances the conflicting requirements of availability, performance, and hardware cost. ReVive performs checkpointing, logging, and distributed parity protection, all memory-based. It enables recovery from a wide class of errors, including the permanent loss of an entire node. To maintain high performance, ReVive includes specialized hardware that performs frequent operations in the background, such as log and parity updates. To keep the cost low, more complex checkpointing and recovery functions are performed in software, while the hardware modifications are limited to the directory controllers of the machine. Our simulation results on a 16-processor system indicate that the average error-free execution time overhead of using ReVive is only 6.3%, while the achieved availability is better than 99.999% even when the errors occur as often as once per day.
Avoiding initialization misses to the heap
Authors: Lewis Jarrod A. , Black Bryan , Lipasti Mikko H.
Published: July 2004

This paper investigates a class of main memory accesses (
invalid memory traffic
) that can be eliminated altogether. Invalid memory traffic is real data traffic that transfers invalid data. By tracking the initialization of dynamic memory allocations, it is possible to identify store instructions that miss the cache and would fetch uninitialized heap data. The data transfers associated with these initialization misses can be avoided without losing correctness. The memory system property crucial for achieving good performance under heap allocation is
cache installation
- the ability to allocate and initialize a new object into the cache without a penalty. Tracking heap initialization at a cache block granularity enables cache installation mechanisms to provide zero-latency prefetching into the cache. We propose a hardware mechanism, the
Allocation Range Cache,
that can efficiently identify initializing store misses to the heap and trigger cache installations to avoid invalid memory traffic.
Results:
For a 2MB cache 23% of cache misses (35% of compulsory misses) to memory are initializing the heap in the SPEC CINT2000 benchmarks. By using a simple base-bounds range sweeping scheme to track the initialization of the 64 most recent dynamic memory allocations, nearly 100% of all initializing store misses can be identified and installed in cache without accessing memory. Smashing invalid memory traffic via cache installation at a cache block granularity removes 23% of all miss traffic and can provide up to 41% performance improvement.
More enhancements of the simplescalar tool set
Authors: Manjikian Naraig
Published: July 2004

An earlier paper described enhancements to the SimpleScalar tool set for functional multiprocessor simulation and visualization of cache coherence, and the software was made available at http://www.simplescalar.org. This paper describes additional enhancements to the SimpleScalar tool set. The enhancements include memory access visualization for uniprocessor and multiprocessor simulation, mnltiprocessor enhancement of the DLite! debugger that is included with SimpleScalar, modifications to the GNU tools to use conventional register names in assembly language, and a tool to embed C source code as comments in the assembly language output of the compiler. These enhancements were inspired in part by research needs and in part by a desire to improve the utility of the SimpleScalar tool set in education. Undergraduate and graduate students at Queen's University have used several of these enhancements in both coursework and research, and the software for the enhancements will be released for wider use in the computer architecture community.
Internet nuggets
Authors: Thorson Mark
Published: July 2004

This column consists of selected traffic from the
comp.arch
newsgroup, a forum for discussion of computer architecture on Internet---an international computer network.
Energy characterization of embedded real-time operating systems
Authors: Acquaviva Andrea , Benini Luca , Riccó Bruno
Published: July 2004

In this paper we propose a methodology to analyze the energy overhead due to the presence of an embedded operating system in a wearable device. Our objective is to determine the key parameters affecting the energy consumption of the RTOS allowing the development of more efficient OS-based power management policies. To achieve this target, we propose a characterization strategy that stimulates the RTOS both at the kernel and at the I/O driver level by analyzing various OS-related parameters. Our analisys focus in particular on the relationship between energy consumption and processor frequency characterizing the different functionalities of an RTOS, suggesting a way to develop effective OS-aware energy optimization policies based on variable voltage and frequency. Experimental results are presented for eCos, an open-source embedded OS ported and installed on a prototype of wearable device, the HP SmartBadgeIII.
Improving energy saving in hard real time systems via a modified dual priority scheduling
Authors: Moncusi M. Angels , Arenas Alex , Labarta Jesus
Published: July 2004

In this paper, we present a modification of the Dual Priority scheduling algorithm, for hard real-time systems, that takes advantage of its performance to efficiently improve energy saving. The approach exploit the priority scheme to lengthen the runtime of tasks reducing the speed of the processor and the voltage supply, thereby saving energy by spreading run cycles up to the maximal time constraints allowed. We show by simulation that our approach improves the energy saving obtained with a pre-emptive Fixed Priority scheduling.
A middleware component supporting flexible user interaction for networked home appliances
Authors: Nakajima Tatsuo
Published: July 2004

In this paper, we describe a middleware component supporting flexible user interaction for networked home appliances, which is a simple mechanism to fill the gap between traditional user interface systems and advanced user interaction devices. Our system enables us to control appliances in a uniform way at any places, and the system allows us to select suitable input and output devices according to our preferences and situations. Our system has based on the stateless thin-client system, and translates input and output interaction events according to user interaction devices. We also show the effectiveness of our approach in our home computing systems.
Monitoring and diagnosing computer systems by radio communication
Authors: Eberle Hans
Published: July 2004

A radio network is described for configuring, monitoring, and diagnosing the components of a computer system. Using radio communication offers many advantages: (a) it removes dependencies between the monitoring and monitored systems as orthogonal interconnects are used; (b) by broadcasting information it offers direct communication between the monitoring and monitored devices that does not rely on any intermediate communication devices; (c) it does not rely on a physical interconnect exposed to mechanical wear and tear.
A few examples of how to use a symmetrical multi-micro-processor
Authors: Mazare Guy
Published: July 2004

This paper presents an overview of an architecture of a multi-micro-processor architecture in which all processors are equivalent. The structure is characterized by a central memory and several caches, and is designed to avoid incoherent data. A fast mechanism of “subcontracting” between one processor and another is described.

The execution of two simple programs under this architecture is studied. The parallel algorithms are described and compared with the original (sequential) algorithms; it is shown that the overhead remains small, few extra memories are necessary and synchronization do not slow down the execution unduly. Furthermore, the locality of the parallel algorithm is compared to that of the sequential algorithm and is found to be less good, but in a reasonable way. As well, an estimation of the cost of the coherence keeping mechanism is given using the difference between the miss ratio of the classical cache and the “coherence keeping cache”, respectively.
The universality of various types of SIMD machine interconnection networks
Authors: Siegel Howard Jay
Published: July 2004

SIMD machine architects must choose an interconnection network to provide interprocessor communication. The universality of a network is its ability to simulate arbitrary interconnections of the processing elements. We examine the universality of five particular networks which cover the types used in the Illiac IV, STARAN, Omen, SIMDA, and RAP machines. They also cover the types discussed by Feng, Lang, Lawrie, Orcutt, Siegel, and Stone. We give O((log2N)2) algorithms, where N is the number of processing elements, for the Perfect Shuffle, PM21, WPM21, and Cube networks to simulate arbitrary interconnections (Orcutt has given an O(N1/2log2N) algorithm for the Illiac network). We analyze Batcher's bitonic sorting method and show how each network can implement it on an SIMD machine. We discuss how sorting destination tags is equivalent to simulating interconnections.
A modular memory scheme for array processing
Authors: Ahuja S. R. , Jump J. R.
Published: July 2004

This paper presents a parallel memory scheme suited for pipelined processing units. The scheme is shown to be modular, relatively low cost and flexible. The scheme allows an arbitrary number of variables in the vector operations. It is shown that data alignment is handled by a simple interconnection scheme and that the interconnection scheme can be implemented in the memory modules. It is shown that the scheme facilitates efficient implementation of the Perfect Shuffle interconnection, hence the implementation of parallel algorithms using that interconnection scheme.
The architecture of an ALGOL 60 computer implemented with distributed processors
Authors: Haynes Leonard S.
Published: July 2004

In conventional computer systems, the computer hardware does not actually execute the user's source program. Instead, a software compiler and link editor transform the program into low level machine code which is executed by the hardware.

This mapping from a high-level language to a von Neumann instruction set is

a. Computationally costly because compilers and link editors are big and slow.

b. Inefficient because the object code is generally poor.

c. Error prone because compilers and link editors are difficult to design, debug, and maintain.

Furthermore, diagnostic messages for execution errors (an arithmetic overflow for example) are either cryptic and require the user to be familiar with the machine language (i.e., a dump), or the object code generated must require considerable run time overhead to permit run time errors to refer back to the users source program (i.e., pointers and tables, etc.).
A large scale, homogeneous, fully distributed parallel machine, I
Authors: Sullivan Herbert , Bashkow T R
Published: July 2004

The preliminary hardware description of CHOPP (Columbia Homogeneous Parallel Processor), a MIMD machine supporting a fully distributed host-less operating system is presented. The architecture is intended to permit implementation of machines with 10
5
to 10
6
processors. Issues of interconnection networks, throughput, and memory structure are treated.
An instruction timing model of CPU performance
Authors: Peuto Bernard L. , Shustek Leonard J.
Published: July 2004

A model of high-performance computers is derived from instruction timing formulas, with compensation for pipeline and cache memory effects. The model is used to predict the performance of the IBM 370/168 and the Amdahl 470 V/6 on specific programs,/and the results are verified by comparison with actual performance. Data collected about program behavior is combined with the performance analysis to highlight some of the problems with high-performance implementations of such architectures.
Information content of CPU memory referencing behavior
Authors: Hammerstrom D. W. , Davidson E. S.
Published: July 2004

The memory reference trace of a computation is modeled as a probabilistic process and the information content of that process is derived. Techniques are developed for analyzing the effectiveness of the addressing architecture and Memory/CPU traffic of existing machines with respect to the information theoretic bound for a given trace.

Several techniques for analyzing particular aspects of addressing architecture are also developed. Possible areas of improvement for addressing architecture, compilers, and memory architecture are suggested for performance enhancement.
Message communication protocol and operating system design for the Distributed Loop Computer Network (DLCN)
Authors: Liu Ming T. , Reames Cecil C
Published: July 2004

The Distributed Loop Computer Network (DLCN) is envisioned as a powerful, unified distributed computing system which interconnects midi/mini/micro-computers, terminals and other peripherals through careful integration of hardware, software and a loop communication network. Research concerning DLCN has concentrated on the loop communication network, message protocol and distributed network operating system. For the loop communication network, previous papers [2,3] reported a novel message transmission mechanism, its hardware implementation, and its superior performance verified by GPSS simulation. This paper presents an overview of the design requirements and implementation techniques for DLCN's message protocol and network operating system. Firstly, a bit-oriented distributed message communication protocol (DLMCP) which handles four message types under one common format is proposed. Besides user information transfer, this protocol supports automatic hardware-generated message acknowledgment, error detection and recovery, and network control and distributed operating system functions, Secondly, the network operating system (DLOS) is described which provides facilities for interprocess communication by process name, global process control and calling of remote programs, generalized data transfer, alterable multi-linked process control structures, distributed resource management, and logical I/O transmission in a distributed file system.
A multimicroprocessor approach to numerical analysis
Authors: McGill Robert , Steinhoff John
Published: July 2004

A parallel processing system is described that consists of a minicomputer host and a set of bipolar microcomputer modules. It is argued that such a system in which the microcomputers operate with little mutual interaction should be effective for an important class of problems in numerical analysis. In particular, estimates are given for the operation of the system on a problem in gaming theory. In this problem, the extensive I/O and software capabilities of the minicomputer provide ease of use for a large part of the problem. The relatively simple part of the problem, which requires almost all of the computational time, is executed in parallel on the microcomputers. It is argued that the system, with 10 to 20 modules, would offer one to two orders of magnitude more speed at several orders of magnitude less cost than current large general-purpose machines. The potential for the development of new algorithms that exploit fully the characteristics of the new devices is discussed.
A microprocessor oriented data acquisition and control system for power system control
Authors: Mulder Michael C. , Fasang Patrick P.
Published: July 2004

The advent of microcomputer systems with their inherent cost/performance advantages had precipitated a reassessment of known application areas that heretofore were not considered candidates for digital systems solution.

Described in this paper is a
MICRO
processor oriented
D
ata
A
cquisition and
C
ontrol system referred to as MICRODAC which is capable of monitoring high voltage perturbations (via transducers), accepting and issuing control commands, performing format changes and error encoding/decoding, performing system self checks, and transmitting data to supervisory computers. This system performs a very necessary function in power system data acquisition and control at low cost, high reliability, and low power consumptions.
Interface, a dispersed architecture
Authors: Vissers Chris A.
Published: July 2004

Past and current specification techniques use timing diagrams and written text to describe the phenomenology of an interface.

This paper treats an interface as the architecture of a number of processes, which are dispersed over the related system parts and the message path. This approach yields a precise definition of an interface. With this definition as starting point, the inherent structure of an interface is developed. A horizontal and vertical partitioning strategy, based on one functional entity per partition and described by a state description, is used to specify the structure. This method allows unambiguous specification, interpretation, and implementation, and allows a much easier judgement of the quality of an interface. The method has been applied to a number of widely used interfaces.
A design study of a shared resource computing system
Authors: Thomasian A. , Avizienis A.
Published: July 2004

The motivations for the design study of a modular, shared resource computing system are given by discussing fault-tolerance and resource utilization issues in parallel processing architectures. A design is presented which employs an array of pipelined arithmetic processors to perform array operations. The design provides for fault-tolerance (“graceful degradation”) capability and is efficient in using main memory bandwidth. Various architectural tradeoffs of the design are discussed. Some results of simulations used for the verification of design decisions are also reported.
The design of a user-programmable digital interface (Recent Results)
Authors: Gault James W. , Parker Alice C.
Published: July 2004

An interface for digital computers and peripherals is described in this paper. The design process is traced, beginning with the definition of the problem environment, and the derivation of primitive interfacing functions. The functions are associated with four functional classes; data input/output, data storage, data manipulation, and control. Interface capabilities range from control over the synchronization of input and output pulse data to control over the data word widths acceptable. System limitations include technical, timing, and synchronization problems. The interface is modular, generalized, and user programmable. The control is contained in two levels: a user microprogram, and a read only nanoprogram.
Design and simulation of the distributed loop computer network (DLCN)
Authors: Reames Cecil C. , Liu Ming T.
Published: July 2004

The primary goals of this paper are two-fold: 1) to present the design and hardware implementation of the interface transmitter for the Distributed Loop Computer Network (DLCN), using a novel shift-register insertion message transmission mechanism, and 2) to discuss simulation results comparing DLCN with Pierce and Newhall loops, which verify earlier claims as to DLCN's superior performance.
Efficient message routing in Mega-Micro-Computer networks
Authors: Wittie Larry D.
Published: July 2004

With rapidly developing microprocessor technology, we can anticipate an entire microcomputer being contained on a single, low-cost LSI chip. It will be technically and economically feasible to interconnect thousands or millions of these microcomputers to form a very large and powerful machine—a
Mega-Micro-Computer
(MMC). This paper defines a system of interlocking buses allowing dense message flow within an MMC. Each microcomputer shares two buses; each bus is shared by sixteen computers. There is a simple algorithm for optimal routing of messages. Data activity on each bus is analytically determined as a function of network size and the spatial distribution of messages between nodes. MMCs are about equally efficient whether connected by buses or by Pierce rings. For equal line costs, an MMC can allow 200 times denser message flow than a million computer network structured like Illiac IV.
Critical issues in mapping neural networks on message-passing multicomputers
Authors: Ghosh J. , Hwang K.
Published: July 2004

Connectionist models such as artificial neural systems, offer an intrinsically concurrent computational paradigm. We investigate the architectural requirements for efficiently simulating large neural networks on a multicomputer system with thousands of fine-grained processors and distributed memory. First, models for characterizing the structure of a neural network and the function of individual cells are developed. These models provide guidelines for efficiently mapping the network onto multicomputer topologies such as the
hypercube, hypernet
and
torus
. They are further used to estimate the amount of interprocessor communication bandwidth required, and the number of processors needed to meet a particular cost/performance goal. Design issues such as memory organization and the effect of VLSI technology are also considered.
Multinomial conjunctoid statistical learning machines
Authors: Takefuji Y. , Jannarone R. , Cho Y. B. , Chen T.
Published: July 2004

Multinomial Conjunctoids are supervised statistical modules that learn the relationships among binary events. The multinomial conjunctoid algorithm precludes the following problems that occur in existing feedforward multi-layered neural networks: (a) existing networks often cannot determine underlying neural architectures, for example how many hidden layers should be used, how many neurons in each hidden layer are required, and what interconnections between neurons should be made; (b) existing networks cannot avoid convergence to suboptimal solutions during the learning process; (c) existing networks require many iterations to converge, if at all, to stable states; and (d) existing networks may not be sufficiently general to reflect all learning situations. By contrast, multinomial conjunctoids are based on a well-developed statistical decision theory framework, which guarantees that learning algorithms will converge to optimal learning states as the number of learning trials increases, and that convergence during each trial will be very fast. In this paper a prototype multinomial conjunctoid circuit based on CMOS VLSI technology is described.
On the inclusion properties for multi-level cache hierarchies
Authors: Baer J.-L. , Wang W.-H.
Published: July 2004

The inclusion property is essential in reducing the cache coherence complexity for multiprocessors with multilevel cache hierarchies. We give some necessary and sufficient conditions for imposing the inclusion property for fully- and set-associative caches which allow different block sizes at different levels of the hierarchy. Three multiprocessor structures with a two-level cache hierarchy (single cache extension, multiport second-level cache, bus-based) are examined. The feasibility of imposing the inclusion property in these structures is discussed. This leads us to propose a new inclusion-coherence mechanism for two-level bus-based architectures.
Hyperswitch network for the hypercube computer
Authors: Chow E. , Madan H. , Peterson J. , Grunwald D. , Reed D.
Published: July 2004

The performance of a parallel algorithm depends in a large part on the interconnection topology of the multicomputer system. The method presented in this paper realizes a kind of interconnection network, called a hyperswitch network, that is achieved using a mixture of static and dynamic topologies. Here, available or fault free paths need not be specified by a source because the routing header can be modified in response to congestion or faults encountered as a path is established. This method can be accomplished in a static topology such as the hypercube network if the nodes have switching elements which are capable of performing the necessary routing header revisions dynamically. Detailed simulation results show that the hyperswitch network is consistently more efficient than fixed path routing for large message traffic conditions. The simulation results also show that the hyperswitch network has equivalent latency overhead for messages with localized and antilocal destinations (i.e., less then a 25% difference between diameter 1 and 5).
Exploiting bit level concurrency in real-time geometric feature extractions
Authors: Liu W. , Yeh T.-F. , Batchelor W. E. , Cavin R.
Published: July 2004

Geometric feature extraction can be characterized as a computationally intensive task in the environment of real-time automated vision systems requiring algorithms with a high degree of parallelism and pipelining under the raster-scan I/O constraint. Using divide-and-conquer techniques, many feature extraction algorithms have been formulated as a pyramid and then as a binary tree structure. An efficient mapping from a tree structure into a pipelined array of
2logN
, stages is presented for processing a NxN image. In the proposed mapping structure, the identification of the
information growing
property inherit in feature extraction algorithms allows us to exploit bit-level concurrency in the architectural design. Accordingly, the design of each staged pipelined processor is simplified.

A single VLSI chip which can generate (
p
+
1
)(
q
+
1
) moments concurrently in real-time applications is reported. This chip posses a hardware complexity of Ο(
pq
(
p
+
q
)log
2
N
) where
p
,
q
stand for the orthogonal orders of the moment. This hardware complexity is an improvement over other reported methods Ο(
pq
(
p
+
q
)
2
log
2
N
).
The architecture of a Linda coprocessor
Authors: Krishnaswamy V. , Ahuja S. , Carriero N. , Gelernter D.
Published: July 2004

We describe the architecture of a coprocessor that supports the communication primitives of the Linda parallel programming environment in hardware. The coprocessor is a critical element in the architecture of the Linda Machine, an MIMD parallel processing system that is designed top down from the specifications of Linda. Communication in Linda programs takes place through a logically shared associative memory mechanism called tuple space. The Linda Machine, however, has no physically shared memory. The microprogrammable coprocessor implements distributed protocols for executing tuple space operations over the Linda Machine communication network. The coprocessor has been designed and is in the process of fabrication. We discuss the projected performance of the coprocessor and compare it with software Linda implementations.

This work is supported in part by National Science Foundation grants CCR-8657615 and ONR N00014-86-K-0310.
Deadlock avoidance for systolic communication
Authors: Kung H. T.
Published: July 2004

Under the systolic communication model, each cell (or processor) in a parallel processing system can operate directly on data residing at the cell's input queues and move computed results directly to the cell's output queues. Incoming and outgoing messages need not be stored in the cell's local memory, if not required by the computation. By avoiding these local memory accesses, systolic communication can achieve high efficiency when executing many systolic algorithms. Though efficient, systolic communication may lead to deadlocks at run time if data arriving at a cell's input queues are improperly ordered. This paper describes the nature of this deadlock problem, gives an abstract formulation of the problem, and provides a deadlock avoidance strategy.
Cache performance of vector processors
Authors: So K. , Zecca V.
Published: July 2004

An instruction-level simulator for IBM 3090 with VF (vector facility) has been developed for studying the performance of vector processors and their memory hierarchies. Initial use of the simulator is to understand the program locality of real vectorized applications. Observation on several large scientific applications indicates that the program locality of vector execution can be significantly different from that of the scalar execution of the same application. Although these large applications generally do not exhibit a locality as strong as that of the conventional mainframe applications, their cache hit ratios are high enough to take advantage of a cache. The cache performance of these applications with respect to various cache parameters is also presented.
A cache-based message passing scheme for a shared-bus multiprocessor
Authors: Preiss B. R. , Hamacher V. C.
Published: July 2004

This paper describes a scheme for using cache-based hardware to provide simple and efficient message passing support for message-based software systems on a tightly-coupled, shared-bus multiprocessor. This approach is based on the utilization of the existing interprocessor communications medium, the shared bus, to effect the exchange of single-word messages. Communication between processes is accomplished over logical channels using simple, blocking
send
and
receive
primitives. The physical processor/channel interface is designed so that the message transfer primitives can be implemented as single machine instructions, namely
store
and
fetch
. Special-purpose caches, called
message caches,
mediate channel operations and effect the exchange of messages over the shared bus.
A fetch-and-op implementation for parallel computers
Authors: Lipovski G. J. , Vaughan P.
Published: July 2004

An efficient fetch-and-op circuit is described. A bit-serial circuit-switched implementation requires only 5 gates per node in a binary tree. This versatile circuit is also capable of test-and-set primitives (priority circuits) and swap operators, as well as AND and OR operations used in SIMD tests such as “branch on all carries set.” It provides an alternative implementation for the combining fetch-and-add circuit to the one designed for the Ultracomputer project; this implementation is suited to SIMD computing and can be adapted to MIMD computing.
The VMP multiprocessor: initial experience, refinements, and performance evaluation
Authors: Cheriton D. R. , Gupta A. , Boyle P. D. , Goosen H. A.
Published: July 2004

VMP is an experimental multiprocessor being developed at Stanford University, suitable for high-performance workstations and server machines. Its primary novelty lies in the use of software management of the per-processor caches and the design decisions in the cache and bus that make this approach feasible. The design and some uniprocessor trace-driven simulations indicating its performance have been reported previously.

In this paper, we present our initial experience with the VMP design based on a running prototype as well as various refinements to the design. Performance evaluation is based both on measurement of actual execution as well as trace-driven simulation of multiprocessor executions from the Mach operating system.
Data buffer performance for sequential Prolog architectures
Authors: Tick E.
Published: July 2004

Several local data buffers are proposed and measurements are presented for variations of the Warren Abstract Machine (WAM) architecture for Prolog. Choice point buffers, stack buffers, split-stack buffers, multiple register sets, copyback caches, and “smart” caches are examined. Statistics collected from four benchmark programs indicate that small conventional local memories perform quite well because of the WAM's high locality. The data memory performance results are equally valid for native code and reduced instruction set implementations of Prolog.
Banyan networks for partitioning multiprocessor systems
Authors: Goke L. Rodney , Lipovski G. J.
Published: July 2004

This paper describes a class of partitioning networks, called banyans, whose cost function grows more slowly than that of the crossbar and whose fan-out requirements are independent of network size. Such networks can economically partition the resources of large modular systems into a wide variety of subsystems. Any possible partition can be realized by paralleling several networks or by multiplexing a single network in a manner to be described later. Results will be given indicating that a cost/performance advantage over the crossbar can be obtained for large systems and that the crossbar can, in fact, be considered a non-optimal special case of a banyan network. Inherent fail-soft capability and the existence of rapid control algorithms which can be largely performed by distributed logic within the network are also important attributes of banyans.

This paper presents fundamental properties and preliminary simulation results of banyan partitioning networks. A more detailed treatment, including proofs of theoretical properties, is reserved for reference (5).
Comments on capabilities, limitations and “correctness” of Petri nets
Authors: Agerwala Tilak , Flynn Mike
Published: July 2004

In this paper we examine the capabilities and limitations of Petri nets and investigate techniques for proving their correctness. We define different classes of nets where each is basically a Petri net with slight modifications and study the relationship between the various classes. One particular class appears to be quite powerful, with respect to its capability for representing coordinations. In the second part of the paper we establish the feasibility of using the methods of computational induction and inductive assertions to prove restricted statements about Petri nets.
A varistructured fail-soft cellular computer
Authors: Lipovski G. J.
Published: July 2004

The architecture of a von-Neumann class computer is considered, in which the user programmer can request, at the beginning of his task, one of many word widths, and one of many memory heights. Several users are able to space share the computer. We call this feature varistructure. The computer is a minimally, yet strongly connected cellular structure consisting of microcomputers, and has the capability of being fail-soft.
A hardware laboratory for computer architecture research
Authors: Vaucher Jean , Rey Christian
Published: July 2004

Because of dramatic reductions in cost of mini-computers, peripherals and logic modules, it is becoming evident that many problems confronting the computer system designer will be solved in the future by hybrid designs involving not only software but also specialized computers with architectures best suited to each application. Accordingly, hardware research must no longer be considered as a separate discipline by system programmers but as a tool in exactly the same way as languages. To illustrate this philosophy, a hardware laboratory has been set up at the University of Montreal. The primary interest of the founders was in designing and building small specialized computing systems.

This paper describes some of the aspects of the laboratory with emphasis on two major developments:

(1) The design of a programmable I/O switch between two mini-computers.

(2) The addition and monitoring of a writable control store connected to one system.
Computer architecture courses in electrical engineering departments
Authors: Sloan M. E.
Published: July 2004

This paper traces the history of computer architecture courses in electrical engineering departments. Previously unpublished data from the Fall 1972 COSINE survey are given to show current computer architecture course offerings and texts. Computer architecture courses offered in 1972-73 are analyzed, compared with ACM and COSINE recommendations, and classified into five categories: introductory computer engineering courses with a computer architecture flavor, software-oriented computer organization courses, hardware-oriented computer organization courses, case study courses, and topical seminars. Future trends in computer architecture education are predicted.
Increasing hardware complexity—a challenge to computer architecture education
Authors: Hartenstein R.
Published: July 2004

The paper starts with a survey over history and present-day situation of educational concepts and design methods in computer architecture. Complexity problems, bad design habits, cooperation problems between specialists, as well as their changing range of responsibility are covered, and the consequences of the developmental trends are discussed: now it is time for switching over to an integrated teaching of hardware/software design methods. The HIM scheme (
h
ierarchy of
i
nterpretive
m
odules) is suggested as a conceptual machine organization framework for modelling the implementation of language hierarchies. The application of the HIM scheme for better understanding of semantics, and for a derivation of designing guidelines is discussed.
Micromodules
Authors: Cooper Richard G.
Published: July 2004

The purpose of the Micromodules project is to greatly reduce the amount of effort expended on logic design, fabrication and debug for small quantity developments. Secondly, with this modular approach, a quick reaction capability is sought that would allow a large reduction in the time interval between system specification and the delivery of the finished product. Finally, by simultaneously simplifying and speeding up the development process, we aim to improve the practicability of implementing more complex equipments.
Automatically characterizing large scale program behavior
Authors: Sherwood Timothy , Perelman Erez , Hamerly Greg , Calder Brad
Published: July 2004

Understanding program behavior is at the foundation of computer architecture and program optimization. Many programs have wildly different behavior on even the very largest of scales (over the complete execution of the program). This realization has ramifications for many architectural and compiler techniques, from thread scheduling, to feedback directed optimizations, to the way programs are simulated. However, in order to take advantage of time-varying behavior, we must first develop the analytical tools necessary to automatically and efficiently analyze program behavior over large sections of execution.Our goal is to develop automatic techniques that are capable of finding and exploiting theLarge Scale Behaviorof programs (behavior seen over billions of instructions). The first step towards this goal is the development of a hardware independent metric that can concisely summarize the behavior of an arbitrary section of execution in a program. To this end we examine the use ofBasic Block Vectors.We quantify the effectiveness of Basic Block Vectors in capturing program behavior across several different architectural metrics, explore the large scale behavior of several programs, and develop a set of algorithms based on clustering capable of analyzing this behavior. We then demonstrate an application of this technology to automatically determine where to simulate for a program to help guide computer architecture research.
Maté
Authors: Levis Philip , Culler David
Published: July 2004

Composed of tens of thousands of tiny devices with very limited resources ("motes"), sensor networks are subject to novel systems problems and constraints. The large number of motes in a sensor network means that there will often be some failing nodes; networks must be easy to repopulate. Often there is no feasible method to recharge motes, so energy is a precious resource. Once deployed, a network must be reprogrammable although physically unreachable, and this reprogramming can be a significant energy cost.We present Maté, a tiny communication-centric virtual machine designed for sensor networks. Maté's high-level interface allows complex programs to be very short (under 100 bytes), reducing the energy cost of transmitting new programs. Code is broken up into small capsules of 24 instructions, which can self-replicate through the network. Packet sending and reception capsules enable the deployment of ad-hoc routing and data aggregation algorithms. Maté's concise, high-level program representation simplifies programming and allows large networks to be frequently reprogrammed in an energy-efficient manner; in addition, its safe execution environment suggests a use of virtual machines to provide the user/kernel boundary on motes that have no hardware protection mechanisms.
Programming language optimizations for modular router configurations
Authors: Kohler Eddie , Morris Robert , Chen Benjie
Published: July 2004

Networking systems such as Ensemble, the
x
-kernel, Scout, and Click achieve flexibility by building routers and other packet processors from modular components. Unfortunately, component designs are often slower than purpose-built code, and routers in particular have stringent efficiency requirements. This paper addresses the efficiency problems of one component-based router, Click, through optimization tools inspired in part by compiler optimization passes. This pragmatic approach can result in significant performance improvements; for example, the combination of three optimizations reduces the amount of CPU time Click requires to process a packet in a simple IP router by 34%. We present several optimization tools, describe how those tools affected the design of Click itself, and present detailed evaluations of Click's performance with and without optimization.
The architecture of the Burroughs B5000
Authors: Mayer Alastair J. W.
Published: July 2004

The Burroughs B5000 was introduced over twenty years ago. The architectural features it introduced, and refined when it was upgraded to the B5500 and B6500, are only now appearing in new computer designs. This paper briefly describes some of these features, as they relate to high-level language and operating system support, and as interesting features in their own right. References are given for more detailed information.
From the other side of the Alantic
Authors: Brakefield James C.
Published: July 2004

The MU5 computer and its commercial counter-part the ICL2900 have become historically interesting in much the same way that Algol 60 prompted research in programming languages. What follows is my extrapolation of where the MU5 architecture leads.
The protection of the processor status word of the PDP-11/60
Authors: Huguet Miquel
Published: July 2004

This work discusses the protection of the Processor Status Word of the PDP-11/60 computer and shows how a non-privileged user can modify the processor priority and execute his programs at PR7 priority level, that is, with all interrupts blocked. It also suggests some possible solutions to this problem. Finally, it considers how the problem is solved in the VAX-11.
Fair dynamic arbitration for a multiprocessor communications bus
Authors: Knott J. D. , Crockett T. W.
Published: July 2004

The Finite Element Machine (FEM) is an experimental parallel computer consisting of an array of 36 asynchronous microcomputers. One method of interprocessor communication on FEM is a bi-directional parallel bus which uses a dynamic arbitration scheme to increase bus bandwidth. Testing of this bus revealed an in transfer rates for individual processors. The imbalance was traced to a defect in arbiter design, and two criteria were identified which must be met to ensure fair dynamic arbitration. These involve (1) priority sequencing, and (2) the efficiency of the arbiter.
A comparison of microcode, assembly code, and high-level languages on the VAX-11 and RISC I
Authors: Larus James R.
Published: July 2004

This paper compares the performance of three implementations of simplified pattern matching instruction. The fastest version was microprogrammed on a VAX-11/750, the next fastest was written for a Reduced Instruction Set. Computer (RISC I) developed at Berkeley, and the slowest was pro grammed on the VAX. The paper presents execution times for the microcode and for high-level language and machine language versions of the instruction.
OPA
Authors: Schulthess Peter , Vonaesch Fritz
Published: July 2004

We propose a stack instruction set with a reduced number of instructions. It allows for straight-forward compilation of high-level languages, extensive run-time checking and compact object code even for large programs.