bluuebunny/crossref_metadata_2025 huggingface dataset:
The compiler controlled pack cache and messaging
Authors: Lass Stanley E.
Published: July 2004

A compiler controlled pack cache allows the compiler to plan the allocation of the cache memory to minimize thrashing, group memory accesses, and specify strided transfers between the cache and main memory, thereby achieving a higher usable bandwidth and reducing the overall miss delay.Since it will soon be reasonable to have on-chip DRAM memories of 4 Mbits (512k bytes), a size comparable to the personal computer main memories of several years ago, the accesses to main memory will become more like the disc input/output of personal computers of several years ago.Message passing between adjacent devices will likely supplant busses, e.g. processor to DRAM to DRAM to DRAM to SCSI controller to keyboard controller, etc. Message passing is inherently faster than a buss.
Time-sequenced DMA for multimedia computers
Authors: Wray Stuart C.
Published: July 2004

Current computer architectures are well suited to the transfer of large amounts of data where latency is not important, and to transfering small amounts of data where latency is important. However, when latency is important and the quantity of data is large, today's computers do not perform so well. In this paper I describe a variety of scatter-gather DMA in which large amounts of data can be transfered with low latency through a computer system by using synchronised clocks in the transmitting and receiving devices.
Lazy release consistency for software distributed shared memory
Authors: Keleher Pete , Cox Alan L. , Zwaenepoel Willy
Published: July 2004

Relaxed memory consistency models, such as
release consistency
, were introduced in order to reduce the impact of remote memory access latency in both software and hardware distributed shared memory (DSM). However, in a software DSM, it is also important to reduce the number of messages and the amount of data exchanged for remote memory access.
Lazy release consistency
is a new algorithm for implementing release consistency that
lazily
pulls modifications across the interconnect only when necessary. Trace-driven simulation using the SPLASH benchmarks indicates that lazy release consistency reduces both the number of messages and the amount of data transferred between processors. These reductions are especially significant for programs that exhibit false sharing and make extensive use of locks.
Effects of building blocks on the performance of super-scalar architecture
Authors: Fernandes Edil S. T. , Barbosa Fernando M. B.
Published: July 2004

The inherent low level parallelism of Super-Scalar architectures plays an important role in the processing power provided by these machines: independent functional units promote opportunities for executing several machine operations simultaneously. From the viewpoint of the hardware designer it is very important to assess the influence of each functional unit, and the way they communicate, on the overall performance of the machine. Particularly, it is highly desirable to determine an upper bound in the number of additional functional units which give significant performance improvement ratios.

This work describes experiments that have been carried out to assess the effect of alternative instruction issue mechanisms, multiple functional units, instruction queues, common data bus and other hardware solutions on the performance of Super-Scalar machines. The assessment was obtained by interpreting non optimized object code fo an actual processor on some basic machine models. The paper outline the main aspects of the research, and shows that speed-up ratios of up to 3.35 times were observed during the interpretation of benchmark programs.
Comparative performance evaluation of cache-coherent NUMA and COMA architectures
Authors: Stenström Per , Joe Truman , Gupta Anoop
Published: July 2004

Two interesting variations of large-scale shared-memory machines that have recently emerged are
cache-coherent non-uniform-memory-access
machines (CC-NUMA) and
cache-only memory architectures
(COMA). They both have distributed main memory and use directory-based cache coherence. Unlike CC-NUMA, however, COMA machines automatically migrate and replicate data at the main-memory level in cache-line sized chunks. This paper compares the performance of these two classes of machines. We first present a qualitative model that shows that the relative performance is primarily determined by two factors: the relative magnitude of capacity misses versus coherence misses, and the granularity of data partitions in the application. We then present quantitative results using simulation studies for eight parallel applications (including all six applications from the SPLASH benchmark suite). We show that COMA's potential for performance improvement is limited to applications where data accesses by different processors are finely interleaved in memory space and, in addition, where capacity misses dominate over coherence misses. In other situations, for example where coherence misses dominate, COMA can actually perform worse than CC-NUMA due to increased miss latencies caused by its hierarchical directories. Finally, we propose a new architectural alternative, called COMA-F, that combines the advantages of both CC-NUMA and COMA.
Cache replacement with dynamic exclusion
Authors: McFarling Scott
Published: July 2004

Most recent cache designs use direct-mapped caches to provide the fast access time required by modern high speed CPU's. Unfortunately, direct-mapped caches have higher miss rates than set-associative caches, largely because direct-mapped caches are more sensitive to conflicts between items needed frequently in the same phase of program execution.

This paper presents a new technique for reducing direct-mapped cache misses caused by conflicts for a particular cache line. A small finite state machine recognizes the common instruction reference patterns where storing an instruction in the cache actually harms performance. Such instructions are dynamically excluded, that is they are passed directly through the cache without being stored. This reduces misses to the instructions that would have been replaced.

The effectiveness of dynamic exclusion is dependent on the severity of cache conflicts and thus on the particular program and cache size of interest. However, across the SPEC benchmarks, simulation results show an average reduction in miss rate of 33% for a 32KB instruction cache with 16B lines. In addition, applying dynamic exclusion to one level of a cache hierarchy can improve the performance of the next level since instructions do not need to be stored on both levels. Finally, dynamic exclusion also improves combined instruction and data cache miss rates.
Processor coupling
Authors: Keckler Stephem W. , Dally William J.
Published: July 2004

The technology to implement a single-chip node composed of 4 high-performance floating-point ALUs will be available by 1995. This paper presents processor coupling, a mechanism for controlling multiple ALUs to exploit both instruction-level and inter-thread parallelism, by using compile time and runtime scheduling. The compiler statically schedules individual threads to discover available intra-thread instruction-level parallelism. The runtime scheduling mechanism interleaves threads, exploiting inter-thread parallelism to maintain high ALU utilization. ALUs are assigned to threads on a cycle by cycle basis, and several threads can be active concurrently. We provide simulation results demonstrating that, on four simple numerical benchmarks, processor coupling achieves better performance than purely statically scheduled or multi-processor machine organizations. We examine how performance is affected by restricted communication between ALUs and by long memory latencies. We also present an implementation and feasibility study of a processor coupled node.
Improved multithreading techniques for hiding communication latency in multiprocessors
Authors: Boothe Bob , Ranade Abhiram
Published: July 2004

Shared memory multiprocessors are considered among the easiest parallel computers to program. However building shared memory machines with thousands of processors has proved difficult because of the inevitably long memory latencies. Much previous research has focused on cache coherency techniques, but it remains unclear if caches can obtain sufficiently high hit rates. In this paper we present improved multithreading techniques that can easily tolerate latencies of hundreds of cycles, and yet only require a small number of threads per processor. High performance is achieved by introducing an explicit context switch instruction that can be used by a simple optimizing compiler to group together several shared accesses. This grouping of shared accesses dramatically reduces the frequency of context switches compared to simpler multithreading models. The combination of our techniques achieves efficiencies of 80% or higher on a broad set of applications.
An analysis of loop latency in dataflow execution
Authors: Najjar Walid A. , Miller W. Marcus , Wim Böhm A. P.
Published: July 2004

Recent evidence indicates that the exploitation of locality in dataflow programs could have a dramatic impact on performance. The current trend in the design of dataflow processors suggest a synthesis of traditional non-strict fine grain instruction execution and a strict coarse grain execution in order to exploit locality. While an increase in instruction granularity will favor the exploitation of locality within a single execution thread, the resulting grain size may increase latency among execution threads. In this paper, the resulting latency incurred through the partitioning of fine grain instructions to quantify coarse grain input and output latencies using a set of numeric benchmarks. The results offer compelling evidence that the inner loops of a significant number of numeric codes would benefit from coarse grain execution. Based on cluster execution times, more than 60% of the measured benchmarks favor a coarse grain execution. IN 64% of the cases the input latency to the cluster is the same in coarse or fine grain execution modes. The results suggest that the effects of increased instruction granularity on latency is minimal for a high percentage of the measured codes, and in large part is offset by available intra-thread locality. Furthermore, simulation results indicate that strict or non-strict data structure access does not change the basic cluster characteristics.
A novel cache design for vector processing
Authors: Yang Qing , Yang Liping Wu
Published: July 2004

This paper introduces an innovative cache design for vector computers, called prime-mapped cache. By utilizing the special properties of a Mersenne prime, the new design does not increase the critical path length of a processor, nor does it increase the cache access time as compared to a direct-mapped cache. The prime-mapped cache minimizes cache miss ratio caused by line interferences that have been shown to be critical for numerical applications by previous investigators. We show that significant performance gains are possible by adding the proposed cache memory into an existing vector computer provided that application programs can be blocked. The performance gain will increase with the increase of the speed gap between processors and memories. We develop an analytical performance model based on a generic vector computation model to study the performance of the design. Our preliminary performance analysis on various vector access patterns shows that the prime-mapped cache can provide as much as a factor of 2 to 3 performance improvement over the conventional direct-mapped cache in the vector processing environment. Moreover, the additional hardware cost introduced by the new mapping scheme is negligible.
Increasing the number of strides for conflict-free vector access
Authors: Valero Mateo , Lang Tomás , Llabería José M. , Peiron Montse , Ayguadé Eduard , Navarra Juan J.
Published: July 2004

Address transformation schemes, such as skewing and linear transformations, have been proposed to achieve conflict-free vector access for some strides in vector processors with multi-module memories. In this paper, we extend these schemes to achieve this conflict-free access for a larger number of strides. The basic idea is to perform an out-of-order access to vectors of fixed length, equal to that of the vector registers of the processor. Both matched and unmatched memories are considered: we show that the number of strides is even larger for the latter case. The hardware for address calculations and access control is described and shown to be of similar complexity as that required for access in order.
The impact of communication locality on large-scale multiprocessor performance
Authors: Johnson Kirk L.
Published: July 2004

As multiprocessor sizes scale and computer architects turn to interconnection networks with non-uniform communication latencies, the lure of exploiting communication locality to increase performance become inevitable. Models that accurately quantify locality effects provide invaluable insight into the importance of exploiting locality as machine sizes and features change. This paper presents a framework for modeling the impact of communication locality on system performance. The framework provides a means for combining simple models of application, processor, and network behavior to obtain a combined model that accurately reflects feedback effects between processors and networks. We introduce a model that characterizes application behavior with three parameters that capture computation grain, sensitivity to communication latency, and amount of locality present at execution time. The combined model, we show that exploiting communication locality provides gains which are at most linear in the factor by which average communication distance is reduced when the number of outstanding communication transactions per processor is bounded. The combined model is also used to obtain rough upper bounds on the performance improvement from exploiting locality to minimize communication distance.
Parallel electro-optical rule-based system for fast execution of expert systems (abstract)
Authors: Louri Ahmed , Na Jongwhoa
Published: July 2004

A hybrid electro-optical rule-based system (EORBS) is proposed for the fast and parallel implementation of rule-based systems (RBS's). The EORBS is a hybrid in which electronics is used for the user interface and optics for the inference engine. The EORBS utilizes two-dimensional optical planes as basic computational entities, and is therefore able to provide concurrent inferencing. Unlike conventional RBS's, EORBS provides parallel matching, selection and rule-firing. The thereotical performance of EORBS is estimated and is shown superior to pure electronic RBS's.
A new compiler-directed cache coherence scheme for shared memory multiprocessors with fast and parallel explicit invalidation (abstract)
Authors: Louri Ahmed , Sung Hongki
Published: July 2004

We propose a novel compiler-directed cache management scheme which allows parallel invalidation of a subset of array elements. The scheme limits non-stale data invalidations using a novel memory allocation technique. Its correctness is proved using a flow graph model. It is also shown that the scheme provides more cacheability than the previous compiler-directed ones and has lower overhead in determining read hit at runtime. A new performance parameter called unwanted invalidation ratio, for compiler-directed coherence schemes is also proposed.
The time-constrained barrier synchronizer and its applications in parallel systems (abstract)
Authors: Cheng Der-Chung , Ghose Kanad
Published: July 2004

A barrier synchronizer, allowing processors to participate dynamically by letting them register their intent to participate within a timeout period, is presented. The synchronizer allows some applications - like software combining and highly concurrent queue operations - to be implemented in a rather unconventional but highly efficient manner. The barrier synchronizer generates successive time windows, allowing requests within the same window to be combined, thus ensuring a more-or-less fixed latency for the Fetch-and Op primitive.
Implications of hierarchical N-body methods for multiprocessor architecture
Authors: Singh Jaswinder Pal
Published: July 2004

We first examine the key architectural implications of realistically scaling a representative member of this important class of applications. Using scaling methods that reflect the concerns of an application scientist leads to different conclusions than does naive scaling model, both the communication to computation ratio and the amount of cache memory per processor required for effective performance increase with scaling. We then examine the effect of a shared address space versus message passing as the communication abstraction. We show that the lack of a shared address space substantially increases the programming complexity and performance overheads of a message-passing implementation.
Cache write generate for high performance parallel processing
Authors: Wittenbrink C. M. , Somani A. K. , Chen C. H.
Published: July 2004

We present, Generate, a new cache write handling scheme that avoids unnecessary reads from main memory, reduces bus contention, and increases the available bandwidth of the memory. Cache Write Generate increases the amount of CPU execution and memory load/store overlap, and decreases the memory cycle time. We compare the performance of cache write generate with write around and write allocate in single processor and shared bus multiprocessors and demonstrate a speedup of 1.2 to 1.5 over allocate and write around.
Extraction of massive instruction level parallelism
Authors: Uht Augustus K.
Published: July 2004

Our goal is to dramatically increase the performance of uniprocessors through the exploitation of instruction level parallelism, i.e. that parallelism which exists amongst the machine instructions of a program. Speculative execution may help a lot, but, it is argued, both branch prediction and eager execution are insufficient to achieve performances in speedup factors in the tens (with respect to sequential execution), with reasonable hardware costs.

A new form of code execution, Disjoint Eager Execution (DEE), is proposed which uses less hardware than pure eager execution, and has more performance than pure branch prediction; DEE is a continuum between branch prediction and eager execution. DEE is shown to be optimal, when processing resources are constrained.

Branches are predicted in DEE, but the predictions should be made in parallel in order to obtain high performance. This is not allowed, however, by the use of the standard instruction stream model, the dynamic model (the order is as indicated by the contents of the Program Counter).

The use of the static instruction stream is proposed instead. The static instruction stream oreder is the same as the order of the code in memory, and is independent of the execution of branches. It allows reduced branch dependencies, as well.

It is argued that a new version, Levo, of an old machine model, CONDEL-2, will be able to attain massive Instruction Level Parallelism.
The MC88110 implementation of precise exceptions in a superscalar architecture
Authors: Ullah Nasr , Holle Matt
Published: July 2004

This paper describes the precise exception model of the MC88110 symmetric superscalar microprocessor. The MC88110 is a superscalar, pipelined processor that contains multiple exection units and allows out-of order execution of instructions. The MC88110 implements fully precise exceptions and presents the architecturally correct state to an exception handling routine in a manner that minimizes exception response latency. The interrupt latency timings in the MC88110 are described, and several examples of short and long latencies are provided.
Look-ahead branching hardware
Authors: McLaughlin Robert
Published: July 2004

The operation that causes the greatest slow-up in the execution of computer code on systems with cache is branching. We propose a simple solution to the problem of doing look-ahead branch prediction. This method can be implemented totally in hardware.We also suggest that cache be partitioned to reduce idle CPU cycles during update of cache memory. The ideal cache would consist of at least 4 partitions. Two for data and two for instructions.
A restricted crossbar implementation and its applications
Authors: Beth Thomas , Hatz Volker
Published: July 2004

In this article a new concept for permutation devices is shown. Such devices, like crossbars, are used within connection networks for parallel computers.The idea shown here is to partition the complete graph with
n
vertices into
n
− 1 different partitions and to switch very fast between these partitions, so that the user sees a complete graph structure. Finally a compact VLSI layout is described which can be easily implemented using automatic design tools.
Secondary cache performance in RISC architecture
Authors: Ewy Benjamin J. , Evans Joseph B.
Published: July 2004

In this paper we report on a simulation study that examines a uniprocessor system with a three-level memory hierarchy. A simulation model of a single-cycle-per-instruction processor with a small on-chip cache was constructed and tested with various memory hierarchies. The simulation was intended to focus on meeting the demanding requirements of the latest RISC processors such as the MIPS R4000 and the DEC 21064. The simulator used allowed the authors to run traces of hundreds of millions of memory references per case. These long traces gave a more thorough and accurate picture of the memory demands of current processors. Data is presented enabling a designer to incorporate speed estimates based on implementation restrictions into the process of developing memory hierarchies.
A high-performance object-oriented memory
Authors: Hyatt Craig
Published: July 2004

The proposed design places a high-performance object memory in a portable peripheral that relieves the host CPU of the burden of object address translation and the constant management of live objects. This flexible approach is designed for the newest generation of high-performance workstations running 32-bit Smalltalk, Lisp, C++ and other COP (object oriented programming) environments. With a two-layer cache and 50ns DRAM object memory, the hardware is capable of accessing object data (including bounds and protection checking) in less than 20ns. Objects are allocated or freed in under 500ns using a hardware binary buddy algorithm.
Scheduling parallel I/O operations
Authors: Jain Ravi , Somalwar Kiran , Werth John , Browne J. C.
Published: July 2004

The I/O bottleneck in parallel computer systems has recently begun receiving increasing interest. Most attention has focused on improving the performance of I/O devices using fairlylow-levelparallelism in techniques such as disk striping and interleaving. Widely applicable solutions, however, will require an integrated approach which addresses the problem at multiple system levels, including applications, systems software, and architecture. We propose that within the context of such an integrated approach, scheduling parallel I/O operations will become increasingly attractive and can potentially provide substantial performance benefits.We describe a simple I/O scheduling problem and present approximate algorithms for its solution. The costs of using these algorithms in terms of execution time, and the benefits in terms of reduced time to complete a batch of I/O operations, are compared with the situations in which no scheduling is used, and in which an optimal scheduling algorithm is used. The comparison is performed both theoretically and experimentally. We have found that, in exchange for a small execution time overhead, the approximate scheduling algorithms can provide substantial improvements in I/O completion times.
A new string search hardware architecture for VLSI
Authors: Takahashi K. , Yamada H. , Nagai H. , Matsumi K.
Published: July 2004

This paper presents a new architecture for practical string search hardware design. This architecture is based on the finite state automaton design concept using a character control charge transfer model. The resultant hardware is a set of programmable sequential logic (PSL) circuits, each of which consists of a sequential logic and memory parts. The logic part is an array of logical gates, each of which is controlled by the read-out signal from the memory part, to connect the flip-flops. The memory part stores each variable-length pattern string character on a bit line by bit line basis. Then, several pattern strings in the memory part can be compared with the serial input data string in parallel, even at a non-anchor mode and an approximate matching mode. This new hardware can be easily implemented in an LSI chip, which allows 8192 pattern string storage using 1 Mb RAM cells.
Graph allocation in static dataflow systems
Authors: Hong Y. C. , Payne T. H. , Ferguson L. B O
Published: July 2004

One of the most important considerations for a dataflow multiprocessor is the algorithm by which the nodes of a program graph are allocated for execution to its processors. In the case of the static type of architecture one must consider pipelining as well as spatial concurrency. This paper uses a graph partitioning scheme to aid in the design of such algorithms and selection of the associated interconnection topology. The scheme first refines the usual dataflow program graph and then partitions it into “trees.” Our study shows that the hypercube interconnection accommodates these trees in a way that allows as to develop an algorithm that places producer nodes (of a dataflow graph) nears their consumers to keep the message path very short. The algorithm achieves concurrency in simultaneous execution of subgraphs that involve parallel operations, e.g., array operations, and subgraphs that are highly iterative or recursive. An analytical model is given to evaluate the performance of the algorithm.
Software implementation of a recursive fault tolerance algorithm on a network of computers
Authors: Agrawal P. , Agrawal R.
Published: July 2004

RAFT is a recursive algorithm for fault tolerance that uses a combination of dynamic space and time redundancy techniques for detecting faulty processors and recovering from errors.
U
*
is a multicomputer testbed consisting of a network of AT&T 3B2 computers running a network operating system based on the UNIX system. This paper describes a software implementation of RAFT on
U
*
, and demonstrates the effectiveness of a RAFT-like scheme for designing fault-tolerant multicomputer systems. Results of Monte Carlo experiments, conducted on this system that validated the theoretical basis of RAFT, are presented. Experimentally observed performance penalty, incurred due to fault tolerance, is also presented.
Microprogrammable processor for object-oriented architecture
Authors: Nojiri T. , Kawasaki S. , Sakoda K.
Published: July 2004

An advanced microprocessor has been developed for the high performance execution of object oriented language programs. In object oriented languages, improvement of frequent or complex operations such as dynamic type checking, procedure calls, and storage management, contributes toward the increase of overall performance. In order to improve their performance, the microprocessor adopts large on-chip register files, a large EPROM for microstore, and ingenious instruction dispatching and tag-handling mechanisms. By specially treating frequently accessed data, i.e., allocating activation records in register files, much of the data traffic can be effectively localized within the chip, and the complexity of procedure calls as well as the burden imposed on storage management can be alleviated. The tag-handling mechanisms efficiently perform dynamic type checking. As the result, the microprocessor, together with an efficient microprogram, executes object oriented language programs much faster than existing computers. Furthermore, it can efficiently execute other high-level languages by using corresponding microprograms, especially AI-languages.
On coupling many small systems for transaction processing
Authors: Dias D. M. , Iyer B. R. , Yu P. S.
Published: July 2004

The prospect of coupling a large number of small inexpensive microprocessor based systems to deliver the performance of a large transaction processing system at lower cost has not been realized, to date. Inter-system interference, multi-system coupling protocol overhead and the increased processing time for smaller systems can cause considerable degradation. A methodology is developed to determine the number of processors needed to satisfy transaction throughput and response time requirements for processors of different MIPS (sizes). The minimum MIPS per processor required to satisfy response time, throughput and utilization constraints in a transaction processing complex of N coupled systems is also determined, by using an approximate analytical model driven by measured workload parameters. Despite large assumed cost advantages on a per MIPS basis we find that small systems do not match up to the cost/performance of some larger systems. Besides multi-system's coupling degradation, there is a small system effect. Because of the increased transaction execution time in smaller systems, transaction hold on to resources longer, thereby causing increased inter-system interference. Our cost criterion indicates that there is an optimum processor size below which total system costs would increase appreciably. Ways to reduce the inter-system interference and coupling protocol overheads are investigated and shown to shift this optimum.
A unification processor based on a uniformly structured cellular hardware
Authors: Shobatake Y. , Aiso H.
Published: July 2004

In this paper, an implementation of unification using a systolic-like method is presented for a VLSI-oriented Prolog machine. Not pointers but a line of symbols and the arity of each symbol are used to express the structure of terms on a uniformly structured cellular hardware. This data structure is demanded by the systolic-like method. Using the systolic-like method, copying structure, and occur check are easily executed during the process of unification. Moreover, searching variable is executed in parallel using a broadcast bus.
The architecture and preliminary evaluation results of the experimental parallel inference machine PIM-D
Authors: Ito N. , Sato M. , Kuno E. , Rokusawa K.
Published: July 2004

A parallel inference machine based on the dataflow model and the mechanisms to support two types of logic programming languages are presented. The machine is constructed from multiple processing elements and structure memories interconnected through a low-latency hierarchical network. The preliminary evaluation results of the experimental machine are also presented. The evaluation results show that the machine can exploit parallelism in programs.
The extra stage gamma network
Authors: Lee K. Y. , Hegazy W.
Published: July 2004

The augmented data manipulator (ADM), inverse augmented data manipulator (IADM), and the gamma network are based on the Plus-Minus-2
i
connection patterns. In such a network there exist multiple paths to connect a source S to a destination D except when S=D. The number of paths for (S,D) is a function of the tag value (D-S) modulo N, and the size of the network N.

It is shown in this paper that by adding an extra stage to the original PM21 interconnection network, multiple paths are provided for all the tag value including 0. The extra stage can be any stage out of n=log
2
N stages of the original network.

The analyses on the distribution of the number of paths for various tag values are performed for n possible choices of the extra stage. It is shown that the extra stage of 0, +1, -1 connection patterns gives the most uniform distribution, and also results in a 1-fault tolerant interconnection network.
Evaluation of the FACOM ALPHA Lisp machine
Authors: Yuhara M. , Hattori A. , Niwa M. , Kishimoto M. , Hayashi H.
Published: July 2004

The FACOM ALPHA is the first and only commercially dedicated processor for Lisp and Prolog manufactured in Japan. This paper discusses the evaluation of the FACOM ALPHA for Lisp execution when compared with a general-purpose computer. The CPU use rate of machine instructions and the utilization ratio of the hardware resources are discussed. This paper also explains the interaction between the garbage collector and the virtual memory system, which improves system response time.
An architecture for efficient Lisp list access
Authors: Pleszkun A. R. , Thazhuthaveetil M. J.
Published: July 2004

In this paper, we present a Lisp machine architecture that supports efficient list manipulation. This Lisp architecture is organized as two processing units: a List Processor (LP), that performs all list related operations and manages the list memory, and an Evaluation Processor (EP), that maintains the addressing and control environment. The LP contains a translation table (LPT) that maps a small set of list identifiers into the physical memory addresses of objects. Essentially, the LP and LPT virtualize a list. The EP then operates on these virtualized lists. Such an organization permits the overlap of EP function evaluation with LP memory accesses and management, thus reducing the performance penalties typically associated with Lisp list manipulation activities. We used trace-driven simulations to evaluate this architecture. From our evaluation a relatively small LPT is seen to be sufficient, and to yield “hit rates” on data accesses higher than those of a data cache of comparable size.
A functional level simulation engine of MAN-YO: a special purpose parallel machine for logic design automation
Authors: Nakata T. , Koike N.
Published: July 2004

The architecture of a proto-type functional level simulator element of a massively parallel machine (MAN-YO) designed for logic design automation is presented. At functional level, hardware systems are described in a hardware description language, FDL. The FDL description is compiled into stack oriented intermediate language instructions. Communicating with other gate level/block level/ functional level processors, each functional simulator interprets the compiled instructions and simulates various circuits using 4-value logic. In order to realize high speed processing of 4-value logic/arithmetic operations, the functional simulator utilizes low-level parallelism realized by 3 ALUs which are controlled by the different fields of a long horizontal type microinstruction.

By utilizing low-level parallelism at processor level, as well as processor level parallelism, high speed execution of mixed level simulation becomes possible. The system also provides further performance enhancement by compiling often used FDL macros into microcode.

This paper describes an outline of the MAN-YO (Japanese for ten thousand leaf-nodes in the processor tree), a brief description of FDL, and the architecture of the functional level simulator element (called FDLPE). A rough performance based on the current design is also described.
A scalable dataflow structure store
Authors: Hawakami K. , Gurd J. R.
Published: July 2004

A design for a highly parallel data structure store for the prototype Manchester Dataflow Computer is presented. The main design objective is to allow all storage functions to be performed concurrently. The functions include space allocation and garbage collection, as well as operations for reading and writing the store. The resulting design is scalable in that an incremental increase in performance for any function can be achieved by adding appropriate hardware modules into the system. A relative balance in performance between the different functions can therefore be achieved. In the hardware structure store, the logical and the physical function units are designed separately. This increases flexibility for configuring multiprocessor dataflow systems. A single hardware module performing all the functions has been constructed and attached to the prototype Manchester Dataflow Machine. The performance of this configuration is discussed.
AT
2
= O(N log
4
N), T = O(log N) fast Fourier transform in a light connected 3-dimensional VLSI
Authors: Hasegawa M. , Shigei Y.
Published: July 2004

We can perform a N-point FFT with time performance T=Ο(log N) and area-time performance AT
2
=Ο(N log
4
N), by using the 3-dimensional VLSI system which is optically interconnected. This performance exceeds the theoretical lower bound of the area-time performance (N
2
log
2
N) of the conventional VLSI.
A computer with low-level parallelism QA-2: its applications to 3-D graphics and Prolog/Lisp machines
Authors: Tomita S. , Shibayama K. , Nakata T. , Yuasa S. , Hagiwara H.
Published: July 2004

We proposed a computer with low-level parallelism as one of the basic computer architectures and built a large scale experimental system called QA-2. By low-level parallelism, we mean that a long-word instruction controls simultaneously many ALUs, busses, registers and memories in a mode of fine-grained parallelism. The QA-2 employs a 256-bit instruction by which four different ALU operations, four memory accesses to different/continuous locations and one powerful sequence control are all specified and performed in parallel. If many simultaneously executable operations are detected and embedded in one instruction at compile time, this type of computer can provide a high-degree of performance for a wide variety of applications. This paper describes the architectural benefits and limitations of low-level parallelism in performing 3-D color image generation and interpreting Prolog/Lisp programs. The hardware organization with four ALUs, which are actually implemented in the QA-2, is verified to be adequate. In fact, nearly three out of four ALUs can work in parallel. Any architecture with more than four ALUs can not achieve a significant degree of performance enhancement. This paper also shows the degree of performance improvement achieved by the techniques such as ALU chaining and highly-structured sequence control mechanisms. As compared with the IBM 370 architecture, the QA-2 can generate 3-D color images in 1/5 of dynamic instruction steps. The compiler version of Prolog machine on the QA-2 is as fast (45K LIPS) as the ICOT's PSI. From all results, we expect that the QA-2 is a high-performance computer which will be utilized in the future personal computing environment.
VLSI oriented asynchronous architecture
Authors: Hirayama M.
Published: July 2004

In order to realise dedicated functions that have no special parallel algorithms for efficient full custom VLSI implementation, we propose an asynchronous architecture that consists of several asynchronous functional modules and controls the chip by the local communication among these functional modules. As this architecture is very suitable for mapping from the behavioral specification described by the software onto silicon, it is very useful as a target architecture for silicon compilers.

This paper describes the concept and the VLSI implementation of the asynchronous architecture. An evaluation of the size and the execution speed of chips based on this architecture model is also described.
Performance evaluation of vector accesses in parallel memories using a skewed storage scheme
Authors: Harper D. T. , Jump J. R.
Published: July 2004

This paper presents and evaluates a scheme for reducing the average memory access time in a vector processing architecture. This scheme uses data skewing to distribute vectors among the modules of a parallel memory system in such a way that, for typical vector access patterns, the average number of memory conflicts is reduced. It also employs both address and data buffers in each module to smooth out the transient irregularities that occur in some vector access patterns.

Most previous data skewing techniques were developed to provide conflict-free access for a limited set of access strides. While the proposed scheme does not eliminate all conflicts, it improves the average performance over non-skewed parallel memories by significantly reducing the number of conflicts for a wide range of strides. Also, this effect is much less dependent on the number of memory modules than the skewing schemes used to obtain conflict-free access.
Warp architecture and implementation
Authors: Annaratone M. , Arnould E. , Gross T. , Kung H. T. , Lam M. S.
Published: July 2004

This paper describes the scan line array processor (SLAP), a new architecture designed for high-performance yet low-cost image computation. A SLAP is a SIMD linear array of processors, and hence is easy to build and scales well with VLSI technology; yet appropriate special features and programming techniques make it efficient for a surprisingly wide variety of low and medium level computer vision tasks. We describe the basic SLAP concept and some of its variants, discuss a particular planned implementation, and indicate its performance on computer vision and other applications.
A class of compatible cache consistency protocols and their support by the IEEE futurebus
Authors: Sweazey P. , Smith A. J.
Published: July 2004

Standardization of a high performance blackplane bus, so that it can accommodate boards developed by different vendors, implies the need for a standardized cache consistency protocol. In this paper we define a class of compatible consistency protocols supported by the current IEEE Futurebus design. We refer to this class as the MOESI class of protocols; the term “MOESI” is derived from the names of the states. This class of protocols has the property that any system component can select (dynamically) any action permitted by any protocol in the class, and be assured that consistency is maintained throughout the system. Included in this class are actions suitable for copyback caches, write through caches and non-caching processors. We show that the Berkeley protocol and the Dragon protocol fall within this class, and can be extended to be compatible with other members of the class. The Illinois, Firefly and Write-Once protocols can be adapted to be compatible with this class; the facilities of he Futurebus currently do not support those protocols without adaptation. We discuss very briefly performance choices among protocols, and also other issues relating to a standard bus consistency protocol.
The detection and elimination of useless misses in multiprocessors
Authors: Dubois Michel , Skeppstedt Jonas , Ricciulli Livio , Ramamurthy Krishnan , Stenström Per
Published: July 2004

In this paper we introduce a new classification of misses in shared-memory multiprocessors based on interprocessor communication. We identify the set of essential misses, i.e., the smallest set of misses necessary for correct execution. Essential misses include cold misses and true sharing misses. All other misses are useless misses and can be ignored without affecting the correctness of program execution. Based on the new classification we compare the effectiveness of five different protocols which delay and combine invalidations leading to useless misses. In cache-based systems the protocols are very effective and have miss rates close to the essential miss rate. In virtual shared memory systems the techniques are also effective but leave room for improvements.
Adaptive cache coherency for detecting migratory shared data
Authors: Cox Alan L. , Fowler Robert J.
Published: July 2004

Parallel programs exhibit a small number of distinct data-sharing patterns. A common data-sharing pattern, migratory access, is characterized by exclusive read and write access by one processor at a time to a shared datum. We describe a family of adaptive cache coherency protocols that dynamically identify migratory shared data in order to reduce the cost of moving them. The protocols use a standard memory model and processor-cache interface. They do not require any compile-time or run-time software support. We describe implementations for bus-based multiprocessors and for shared-memory multiprocessors that use directory-based caches. These implementations are simple and would not significantly increase hardware cost. We use trace- and execution-driven simulation to compare the performance of the adaptive protocols to standard write-invalidate protocols. These simulations indicate that, compared to conventional protocols, the use of the adaptive protocol can almost halve the number of inter-node messages on some applications. Since cache coherency traffic represents a larger part of the total communication as cache size increases, the relative benefit of using the adaptive protocol also increases.
Evaluation of release consistent software distributed shared memory on emerging network technology
Authors: Dwarkadas Sandhya , Keleher Peter , Cox Alan L. , Zwaenepoel Willy
Published: July 2004

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

Our simulations indicate that with the processors and networks that are becoming available, coarse-grained applications such as Jacobi and TSP perform well, more or less independent of the protocol used. Medium-grained applications, such as Water, can achieve good performance, but the choice of protocol is critical. For sixteen processors, the best protocol, lazy hybrid, performed more than three times better than the worst, the eager update. Fine-grained applications such as Cholesky achieve little speedup regardless of the protocol used because of the frequency of synchronization operations and the high latency involved.

While the use of relaxed memory models, lazy implementations, and multiple-writer protocols has reduced the impact of false sharing, synchronization latency remains a serious problem for software distributed shared memory systems. These results suggest that the future work on software DSMs should concentrate on reducing the amount of synchronization or its effect.
The J-machine multicomputer
Authors: Noakes Michael D. , Wallach Deborah A. , Dally William J.
Published: July 2004

The MIT J-Machine multicomputer has been constructed to study the role of a set of primitive mechanisms in providing efficient support for parallel computing. Each J-Machine node consists of an integrated multicomputer component, the Message-Driven Processor (MDP), and 1 MByte of DRAM. The MDP provides mechanisms to support efficient communication, synchronization, and naming. A 512 node J-Machine is operational and is due to be expanded to 1024 nodes in March 1993. In this paper we discuss the design of the J-Machine and evaluate the effectiveness of the mechanisms incorporated into the MDP. We measure the performance of the communication and synchronization mechanisms directly and investigate the behavior of four complete applications.
The performance of cache-coherent ring-based multiprocessors
Authors: Barroso Luiz André , Dubois Michel
Published: July 2004

Advances in circuit and integration technology are continuously boosting the speed of microprocessors. One of the main challenges presented by such developments is the effective use of powerful microprocessors in shared memory multiprocessor configurations. We believe that the interconnection problem is not solved even for small scale shared memory multiprocessors, since the speed of shared buses is unlikely to keep up with the bandwidth requirements of new microprocessors. In this paper we evaluate the performance of unidirectional slotted ring interconnection for small to medium scale shared memory systems, using a hybrid methodology of analytical models and trace-driven simulations. We evaluate both snooping and directory-based coherence protocols for the ring and compare it to high performance split transaction buses.