bluuebunny/crossref_metadata_2025_split huggingface dataset:
Happe Honeywell Associative Parallel Processing Ensemble
Authors: Marvel Orin E. 
Published: July 2004

Many problems, inherent in air traffic control, weather analysis and prediction, nuclear reaction, missile tracking, and hydrodynamics have common processing characteristics that can most efficiently be solved using parallel “non-conventional” techniques. Because of high sensor data rates, these parallel problem solving techniques cannot be economically applied using the standard sequential computer.
The application of special processing techniques such as parallel/associative processing are still resisted because it is a change from the norm. Past implementations utilized special hardware, custom circuits and complex designs. The Honeywell Associative Parallel Processing Ensemble (HAPPE) was built to demonstrate the basic simplicity of hardware concepts inherent in parallel associative processing. HAPPE is implemented with the same standard circuit building blocks (MSI's, ROM's, and RAM's) that are used in all conventional computers. By using standard building blocks a long time objection to associative memory systems, that of requiring special purpose (low usage) circuits is overcome.
The parallel/associative processing element can be both powerful and versatile. The HAPPE architecture proves that one processor element can perform both correlation (associative) and arithmetic processing. The HAPPE demonstrator has become a valuable tool in training system designers and programmers to recognize that new “thinking” can be applied to advanced processing system implementations.
Architectural support for synchronous task communication
Authors: Burkowski F. J. , Cormack G. V. , Dueck G. D. P. 
Published: July 2004

This paper describes the motivation for a set of intertask communication primitives, the hardware support of these primitives, the architecture used in the Sylvan project which studies these issues, and the experience gained from various experiments conducted in this area. We start by describing how these facilities have been implemented in a multiprocessor configuration that utilizes a shared backplane. This configuration represents a single node in the system. The latter part of the paper discusses a distributed multiple node system and the extension of the primitives that are used in this expanded environment.
This research is funded by a strategic grant from the Natural Sciences and Engineering Research Council of Canada (Grant No. G1581).
Efficient debugging primitives for multiprocessors
Authors: Aral Z. , Gerther I. , Schaffer G. 
Published: July 2004

Existing kernel-level debugging primitives are inappropriate for instrumenting complex sequential or parallel programs. These functions incur a heavy overhead in their use of system calls and process switches. Context switches are used to alternately invoke the debugger and the target programs. System calls are used to communicate data between the target and debugger.
None of this is necessary in shared-memory multiprocessors. Multiple processors concurrently run both the debugger and the target. Shared-memory is used to implement efficient communication. The target's state is accessed by running both the target and the debugger in the same address space. Finally, instrumentation points, which have largely been implemented as traps to the system, are reimplemented as simple branches to routines of arbitrary complexity maintained by the debugger. Not only are primitives such as conditional breakpoints thus generalized, but their efficiency is improved by several orders of magnitude. In the process, much of the traditional system's kernel support for debugging is reimplemented at user-level.
This paper describes the implementation of debugging primitives in Parasight, a parallel programming environment. Parasight has been used to implement conditional breakpoints, an important primitive for both high-level and parallel debugging. Preliminary measurements indicate that Parasight breakpoints are 1000 times faster than the breakpoints in parallel “cdb”, a conventional UNIX debugger. Light-weight conditional breakpoints open up new opportunities for debugging and profiling both parallel and sequential programs.
Data buffering: run-time versus compile-time support
Authors: Mulder H. 
Published: July 2004

Data-dependency, branch, and memory-access penalties are main constraints on the performance of high-speed microprocessors. The memory-access penalties concern both penalties imposed by external memory (e.g. cache) or by under utilization of the local processor memory (e.g. registers). This paper focuses solely on methods of increasing the utilization of data memory, local to the processor (registers or register-oriented buffers).
A utilization increase of local processor memory is possible by means of compile-time software, run-time hardware, or a combination of both. This paper looks at data buffers which perform solely because of the compile-time software (single register sets); those which operate mainly through hardware but with possible software assistance (multiple register sets); and those intended to operate transparently with main memory implying no software assistance whatsoever (stack buffers). This paper shows that hardware buffering schemes cannot replace compile-time effort, but at most can reduce the complexity of this effort. It shows the utility increase of applying register allocation for multiple register sets. The paper also shows a potential utility decrease inherent to stack buffers. The observation that a single register set, allocated by means of interprocedural allocation, performs competitively with both multiple register set and stack buffer emphasizes the significance of the conclusion
A real-time support processor for ada tasking
Authors: Roos J. 
Published: July 2004

Task synchronization in Ada causes excessive run-time overhead due to the complex semantics of the rendezvous. To demonstrate that the speed can be increased by two orders of magnitude by using special purpose hardware, a single chip VLSI support processor has been designed. By providing predictable and uniformly low overhead for the entire semantics of a rendezvous, the powerful real-time constructs of Ada can be used freely without performance degradation.
The key to high performance is the set of primitive operations implemented in hardware. Each operation is complex enough to replace a considerable amount of code was designed to execute with a minimum of communication overhead. Task control blocks are stored on-chip as well as headers for entry, delay and ready queues. All necessary scheduling is integrated in the operations. Delays are handled completely on-chip using an internal real-time clock.
A multilevel design strategy, based on silicon compilation, made it possible to run actual Ada programs on a functional emulator of the chip and use the results to verify the detailed design. A high degree of parallelism and pipelining together with an elaborate internal addressing scheme has reduced the number of clock cycles needed to perform each operation. Using 2 μm CMOS, the processor can run at 20 MHz. A complex rendezvous, including the calling sequence and all necessary scheduling, can be performed in less than 15 μs.
The design of nectar: a network backplane for heterogeneous multicomputers
Authors: Arnould Emmanuel , Kung H. T. , Bitz Francois , Sansom Robert D. , Cooperm Eric C. 
Published: July 2004

Nectar is a “network backplane” for use in heterogeneous multicomputers. The initial system consists of a star-shaped fiber-optic network with an aggregate bandwidth of 1.6 gigabits/second and a switching latency of 700 nanoseconds. The system can be scaled up by connecting hundreds of these networks together.
The Nectar architecture provides a flexible way to handle heterogeneity and task-level parallelism. A wide variety of machines can be connected as Nectar nodes and the Nectar system software allows applications to communicate at a high level. Protocol processing is off-loaded to powerful communication processors so that nodes do not have to support a suite of network protocols.
We have designed and built a prototype Nectar system that has been operational since November 1988. This paper presents the motivation and goals for Nectar and describes its hardware and software. The presentation emphasizes how the goals influenced the design decisions and led to the novel aspects of Nectar.
Multi-level shared caching techniques for scalability in VMP-M/C
Authors: Cheriton D. R. , Goosen H. A. , Boyle P. D. 
Published: July 2004

The problem of building a scalable shared memory multiprocessor can be reduced to that of building a scalable memory hierarchy, assuming interprocessor communication is handled by the memory system. In this paper, we describe the VMP-MC design, a distributed parallel multi-computer based on the VMP multiprocessor design, that is intended to provide a set of building blocks for configuring machines from one to several thousand processors. VMP-MC uses a memory hierarchy based on shared caches, ranging from on-chip caches to board-level caches connected by busses to, at the bottom, a high-speed fiber optic ring. In addition to describing the building block components of this architecture, we identify the key performance issues associated with the design and provide performance evaluation of these issues using trace-drive simulation and measurements from the VMP.
This work was sponsored in part by the Defense Advanced Research Projects Agency under Contract N00014-88-K-0619.
A dynamic storage scheme for conflict-free vector access
Authors: Harper D. T. , Linebarger D. A. 
Published: July 2004

Previous investigations into data storage schemes have focused on finding a storage scheme that permits conflict-free access for a set of frequently encountered access patterns. This paper considers an alternative approach. Rather than forcing a single storage scheme to be used for all access patterns, conflict-free accesses of any constant stride can be made by selecting a storage scheme for each vector based on the accessing patterns used with that vector.
By factoring the stride into two components, one a power of 2 and the other relatively prime to 2, a storage scheme can be synthesized which allows conflict-free access to the vector using the specified stride. All such schemes are based on a variation of the row rotation mechanism proposed by Budnik and Kuck[1]. Each storage scheme is based on two parameters, one describes the type of rotation to perform and the other describes the amount of memory to be rotated as a single block. Hardware required to implement this storage scheme is efficient.
The performance of the memory under access strides other than the stride used to specify the storage scheme is also considered. This models a vector being accessed with multiple strides, in particular the row/column access of a matrix, and situations when the stride can not be determined prior to initializing the vector. Simulation results show that if a single buffer is added to each memory port then the average performance of the dynamic scheme surpasses that of the interleaved scheme for arbitrary stride accesses.
For dynamic storage schemes to be effective, the compiler must be able to detect information about the stride of vector accesses. In general, this is within the capabilities of current vectorizing compilers. Dynamic storage schemes also may allow more flexibility in program transformation performed by vectorizing compilers during optimization.
Inexpensive implementations of set-associativity
Authors: Kessler R. E. , Jooss R. , Lebeck A. , Hill M. D. 
Published: July 2004

The traditional approach to implementing wide set-associativity is expensive, requiring a wide tag memory (directory) and many comparators. Here we examine alternative implementations of associativity that use hardware similar to that used to implement a direct-mapped cache. One approach scans tags serially from most-recently used to least-recently used. Another uses a partial compare of a few bits from each tag to reduce the number of tags that must be examined serially. The drawback of both approaches is that they increase cache access time by a factor of two or more over the traditional implementation of set-associativity, making them inappropriate for cache designs in which a fast access time is crucial (e.g. level one caches, caches directly servicing processor requests).
These schemes are useful, however, if (1) the low miss ratio of wide set-associative caches is desired, (2) the low cost of a direct-mapped implementation is preferred, and (3) the slower access time of these approaches can be tolerated. We expect these conditions to be true for caches in multiprocessors designed to reduce memory interconnection traffic, caches implemented with large, narrow memory chips, and level two (or higher) caches in a cache hierarchy.
Introducing memory into the switch elements of multiprocessor interconnection networks
Authors: Mizrahi H. E. , Baer J. L. , Lazowska E. D. , Zahorjan J. 
Published: July 2004

As VLSI technology continues to improve, circuit area is gradually being replaced by pin restrictions as the limiting factor in design. Thus, it is reasonable to anticipate that on-chip memory will become increasingly inexpensive since it is a simple, regular structure than can easily take advantage of higher densities.
In this paper we examine one way in which this trend can be exploited to improve the performance of multistage interconnection networks (MINs). In particular, we consider the performance benefits of placing significant memory in each MIN switch. This memory is used in two ways: to store (the unique copies of) data items and to maintain directories. The data storage function allows data to be placed nearer processors that reference it relatively frequently, at the cost of increased distance to other processors. The directory function allows data items to migrate in reaction to changes in program locality. We call our MIN architecture the Memory Hierarchy Network (MHN).
In a preliminary investigation of the merits of this design [8] we examined the performance of MHNs under the simplifying assumption that an unlimited amount of memory was available in each switch. We found that despite the longer switch processing times of the MHN, system performance is improved over simpler, conventional schemes based on caching.
In this paper we refine the earlier model to account for practical storage limitations. We study ways to reduce the amount of directory storage required by keeping only partial information regarding the current location of data items. The price paid for this reduction in memory requirement is more complicated (and in some circumstances slower) protocols. We obtain comparative performance estimates in an environment containing a single global memory module and a tree-structured MIN. Our results indicate that the MHN organization can have substantial performance benefits and so should be of increasing interest as the enabling technology becomes available.
Using feedback to control tree saturation in multistage interconnection networks
Authors: Scott S. L. , Sohi G. S. 
Published: July 2004

In this paper, we propose the use of feedback schemes in multiprocessors which use an interconnection network with distributed routing control. We show that by altering system behavior so as to minimize the occurrence of a performance-degrading situation in the network, the overall throughout of the system can be improved.
As an example, we have considered the problem of tree saturation caused by hot spots in multistage interconnection networks. Tree saturation degrades the performance of all processors in a system, including those not participating in the hot spot activity. We see that feedback schemes can be used to control tree saturation, reduce degradation to memory requests that are not to the hot memory module and increase overall system bandwidth. As a companion to feedback schemes, damping schemes are also considered. Simulation studies presented in this paper show that feedback schemes can improve overall system performance significantly in many cases.
Evaluation of memory system for integrated Prolog processor IPP
Authors: Morioka M. , Yamaguchi S. , Bandoh T. 
Published: July 2004

This paper discusses an optimal memory system to realize a high performance integrated Prolog processor, the IPP. First, the memory access characteristics of Prolog are analyzed by a simulator, which simulates the execution of a Prolog program at a micro instruction level. The main findings from this analysis are that: the write access ratio of Prolog is larger than that of procedural languages; and performance improvement requires the memory system to process concentrated, large write accesses effectively.
Then the Prolog acceleration strategies for conventional cache memories are discussed. Comparison is made of cache memories (store-swap, store-through) and a stack buffer, regarding not only performance but also reliability, complexity and effects on procedural languages. The advanced store-through cache with a multi-stage write buffer and an interleaved main memory are seen to have the same performance level as the store-swap cache. When considering data reliability, the advanced store-through cache is judged more suitable for the IPP than the store-swap cache. In a comparison between stack buffer and advanced store-through cache, the stack buffer is found to achieve higher peak performance, but this is affected by the program features. On the other hand, the advanced store-through cache constantly gets high performance for Prolog and procedural languages. As a result, it is concluded that the advanced store-through cache is best suited to the IPP.
Analysis of vector access performance on skewed interleaved memory
Authors: Chen C.-L. , Liao C.-K. 
Published: July 2004

Memory interleaving and memory skewing are two hardware approaches to reduce memory access conflict for many advanced computer architectures, while pipelined vector computer covers many commercially available supercomputers. The goal of this paper is to study the vector accessing behavior on skewed interleaved memory under pipelined processing environment.
We establish a criterion, called average time delay, to indicate the performance of a vector access; and a criterion, called aggregate average time delay to indicate the performance of a given memory system. Under these criteria, we analyze some memory design problems. These problems centralize how to design a memory system which is cost-effective and has less conflicts for vector accesses.
We also propose a software approach to reduce memory access conflict, called dimension extension strategy. This strategy performs very well under our analysis.
A cache consistency protocol for multiprocessors with multistage networks
Authors: Stenström P. 
Published: July 2004

A hardware based cache consistency protocol for multiprocessors with multistage networks is proposed. Consistency traffic is restricted to the set of caches which have a copy of a shared block. State information is distributed to the caches and the memory modules need not be consulted for consistency actions.
The protocol provides two operating modes: distributed write and global read. Distribution of writes calls for efficient multicast methods. Communication cost for multicasting is analyzed and a novel scheme is proposed.
Finally, communication cost for the protocol is compared to other protocols. The two-mode approach limits the upperbound for the communication cost to a value considerably lower than that for other protocols.
On data synchronization for multiprocessors
Authors: Su H.-M. , Yew P.-C. 
Published: July 2004

As the grain size becomes smaller, more parallelism can be found in most programs. However, to exploit smaller grain parallelism, more efficient synchronization primitives are needed to reduce the increased synchronization overhead. The granularity of parallelism that can be exploited on a multiprocessor system depends heavily on the type and the efficiency of the synchronization supported by the system. For medium-grain parallelism, ordered dependencies such as data dependencies and control dependencies need to be enforced in order to guarantee the correctness of the parallel execution. Hence, data synchronization is one of the major sources of synchronization overhead in the program execution.
In this paper, we classify the synchronization schemes based on how synchronization variables are used. A new scheme, the process-oriented scheme, is proposed. This scheme requires a very small number of synchronization variables and can be supported very efficiently by simple hardware in the system.
Scheduling of tasks for distributed processors
Authors: Mehrotra Ravi , Talukdar Sarosh N. 
Published: July 2004

The paper describes a technique for estimating the minimum execution time of an algorithm or a mix of algorithms on a distributed processing system. Bottlenecks that would have to be removed to further reduce the execution time are identified. The main applications are for the high level design of special purpose distributed processing systems.
The distributed systems are modelled by P, a set of nonidentical processors and R, a set of resources that the processors can use. The algorithms are modelled by T, an ordered set of tasks. The problem of optimally assigning the processors to the tasks while meeting the resource constraints is NP-complete. However, a heuristic using maximum weighted matchings on graphs has been devised that is extremely fast and comes reasonably close to the optimal solutions.
Hardware/software cooperation in the iAPX-432
Authors: Rattner Justin 
Published: July 2004

The Intel iAPX-432 is an object-based microcomputer system with a unified approach to the design and use of its architecture, operating system, and primary programming language. The concrete architecture of the 432 incorporates hardware support for data abstraction, small protection domains, and language-oriented run-time environments. It also uses its object-orientation to provide hardware support for dynamic heap storage management, interprocess communication, and processor dispatching.
We begin with an overview of the 432 architecture so readers unfamiliar with its basic concepts will be able to follow the succeeding discussion without the need to consult the references. Following that, we introduce the various forms of hardware/software cooperation and the criteria by which a function or service is selected for migration. This is followed by several of the more interesting examples of hardware/software cooperation in the 432. A comparison of cooperation in the 432 with several contemporary machines and discussions of development issues, past and future, complete the paper.
The operating system and language support features of the BELLMAC
TM
-32 microprocessor.
Authors: Berenbaum Alan D. , Condry Michael W. , Lu Priscilla M. 
Published: July 2004

The BELLMAC-32 microprocessor is a 32-bit microprocessor, implemented with CMOS technology, designed to support operating system functions and high level languages efficiently. The architecture was designed with the following objectives in mind:
• High performance.
• Enhanced operating system support capabilities.
• High level language support.
• High reliability, availability and maintainability.