bluuebunny/crossref_metadata_2025 huggingface dataset:
An analysis of C machine support for other block-structured languages
Authors: Hill Dwight D.
Published: July 2004

Although the C machine proposed by Ditzel (
et al
.) was originally intended to execute the C programming language, its utility would be enhanced if it could also execute programs written in other languages. Of particular interest is the Ada programming language, in part because it is likely to be a standard for government work, but more importantly because its support requirements are typical of many modern languages such as CHILL, MESA, EUCLID, MODULA, and others. The most salient characteristics of the C machine, e.g. its stack cache and address modes, are seen to map well onto the Ada language. In fact, many of the arguments for these features are more compelling for the Ada language than they are for C. One exception is the way the stack cache may perform on a heavily multi-tasked program, but there is no obvious solution to this, even on much more complex machines like the VAX11-780.
A loop network for simultaneous transmission of variable-length messages
Authors: Reames Cecil C. , Liu Ming T.
Published: July 2004

A loop (ring) system is proposed for distributed computer networks which: i) allows simultaneous transmission of variable-length message frames, 2) minimizes loop access and transmission times, and 3) provides a form of automatic traffic regulation. The ring interface transmitter which performs these three functions is described, and a conceptual model of its operation is developed. The model illustrates a technique by which the ring interface transmitter can delay incoming messages by hardware buffering just long enough for a variable-length output message to be placed on the loop. It is shown how advantage can be taken of gaps between incoming messages to clear out the delay buffer and to make room for future outgoing messages. It is further demonstrated that an interesting form of automatic message traffic regulation results from use of the proposed technique. Possible hardware implementations of the model are also considered, using a variable-length shift register for the incoming message delay buffer. The probable effects of the proposed technique on message transmission are discussed, and ongoing analytic and simulation studies are described.
The computer aided design of processor architectures
Authors: Peskin A. M.
Published: July 2004

A design automation system is described which has certain features that make it particularly well suited to the automation and analysis of entire digital systems; including hardware, firmware and software. The code includes facilities for automated synthesis, simulation and documentation. The languages, called LINDA and MODEL, and their processing algorithms are described.Examples of computer architecture studies which have been conducted using LINDA and MODEL are also presented. These include development of an associative processor and investigations related to a logic-in-memory architecture. It is stressed that reliance on the appropriate design automation procedures have expedited the work and reduced the cost of research by eliminating the implementation phase as a necessary prerequisite to the study of machine concepts.
Intermodule protocol for register transfer level modules
Authors: Huen W. H. , Siewiorek D. P.
Published: July 2004

A distinguishing feature of modular design from ad hoc design is the establishment of an intermodule protocol to which all modules adhere. The problem of representing and analyzing intermodule protocol for the control portion of register transfer level systems is outlined. An introduction to two existing graph models of computation indicates that existing register transfer level module sets are representable by various "token flow" models. A single model that is capable of representing the token flow models and some of its analytical properties are illustrated by example. Finally, three examples of deadlocks in existing modules sets are presented. These deadlocks were uncovered by the analytic properties of the new model. One example is due to incorrect interconnection of modules at the user level. The other two illustrate incorrect signaling conventions between modules necessitating a redesign of some modules.
Architectural advances of the space shuttle orbiter avionics computer system
Authors: Satterfield James M.
Published: July 2004

The Space Shuttle Orbiter manned reusable craft is being developed by NASA for applications in the 1980' and beyond. Navigation, guidance flight control, systems management and control, and payload checkout are but a few of the functions of the Orbiter which are being mechanized in the avionics computer complex.The development of the system is traced through three distinct architectures to the current system. Factors affecting the architecture and system development are discussed. A system figure of merit for evaluating competing systems architecture is developed.
Output devices sharing by minicomputers
Authors: King Willis K. , Carbonaro Fulvio
Published: July 2004

With the dramatic reduction in cost of central processors in recent years, the peripheral devices occupy an ever larger share in terms of cost of a minicomputer system. Sharing the expensive components among users is a time honored way of increasing utilization and hence reducing the cost of unit operation. This paper presents the results of a simulation of sharing an output device, such as the printer, by more than one processor under different workload conditions.
A cellular general purpose computer
Authors: Cornell R. G. , Torng H. C.
Published: July 2004

A 2-dimensional cellular general-purpose computer is specified. This particular cellular computer is distinguished from previously proposed, locally-controlled cellular computers in that the cellular structure is "hidden" from the user. At the ISP level, the machine is similar to a small-scale computer of the von Neumann type. However, the architecture of the computer does not feature physically isolated functional units to implement memory, processor, or control. As a result, we present a machine which may be programmed in the conventional manner, but which has the hardware advantages associated with the cellular structure. Additionally, the machine is controlled by a software microprogram, which lends itself to dynamic micro-programming and to such related applications as machine simulation.
A proposed high-speed computer design
Authors: Turton Trevor
Published: July 2004

The designs of several high performance general purpose computers built during the last two decades are examined. The performance limitations they encountered and their approaches to overcoming these problems are discussed. An alternate design approach is described which avoids these problems. This is to have the computer support the simultaneous execution of several independent programs by multiprogramming its various components at the sub-instruction level. Estimates of its performance are made, and the implications for the Operating System are examined.The principles discussed are generally applicable, but to make the proposals more concrete the hardware implications are worked out in some detail for the IBM System/370, architecture.
Tradeoffs in instruction format design for horizontal architectures
Authors: Sohi Gurindar S. , Vajapeyam Sriram
Published: July 2004

With recent improvements in software techniques and the enhanced level of fine grain parallelism made available by such techniques, there has been an increased interest in horizontal architectures and large instruction words that are capable of issuing more that one operation per instruction. This paper investigates some issues in the design of such instruction formats. We study how the choice of an instruction format is influenced by factors such as the degree of pipelining and the instruction's view of the register file. Our results suggest that very large instruction words capable of issuing one operation to each functional unit resource in a horizontal architecture may be overkill. Restricted instruction formats with limited operation issuing capabilities are capable of providing similar performance (measured by the total number of time steps) with significantly less hardware in many cases.
Overlapped loop support in the Cydra 5
Authors: Dehnert James C. , Hsu Peter Y.-T. , Bratt Joseph P.
Published: July 2004

The

Cydra
TM

5 architecture adds unique support for overlapping successive iterations of a loop to a very long instruction word (VLIW) base. This architecture allows highly parallel loop execution for a much larger class of loops than can be vectorized, without requiring the unrolling of loops usually used by compilers for VLIW machines. This paper discusses the Cydra 5 loop scheduling model, the special architectural features which support it, and the loop compilation techniques used to take full advantage of the architecture.
The fuzzy barrier: a mechanism for high speed synchronization of processors
Authors: Gupta Rajiv
Published: July 2004

Parallel programs are commonly written using barriers to synchronize parallel processes. Upon reaching a barrier, a processor must stall until all participating processors reach the barrier. A software implementation of the barrier mechanism using shared variables has two major drawbacks. Firstly, the execution of the barrier may be slow as it may not only require execution of several instructions and but also result in hot-spot accesses. Secondly, processors that are stalled waiting for other processors to reach the barrier are essentially idling and cannot do any useful work. In this paper, the notion of the fuzzy barrier is presented, that avoids the above drawbacks. The first problem is avoided by implementing the mechanism in hardware. The second problem is solved by extending the barrier concept to include a region of statements that can be executed by a processor while it awaits synchronization. The barrier regions are constructed by a compiler and consist of several instructions such that a processor is ready to synchronize upon reaching the first instruction in this region and must synchronize before exiting the region. When synchronization does occur, the processors could be executing at any point in their respective barrier regions. The larger the barrier region, the more likely it is that none of the processors will have to stall. Preliminary investigations show that barrier regions can be large and the use of program transformations can significantly increase their size. Examples of situations where such a mechanism can result in improved performance are presented. Results based on a software implementation of the fuzzy barrier on the Encore multiprocessor indicate that the synchronization overhead can be greatly reduced using the mechanism.
Efficient synchronization primitives for large-scale cache-coherent multiprocessors
Authors: Goodman James R. , Vernon Mary K. , Woest Philip J.
Published: July 2004

This paper proposes a set of efficient primitives for process synchronization in multiprocessors. The only assumptions made in developing the set of primitives are that hardware combining is not implemented in the inter-connect, and (in one case) that the interconnect supports broadcast.

The primitives make use of synchronization bits (syncbits) to provide a simple mechanism for mutual exclusion. The proposed implementation of the primitives includes efficient (
i.e.
local) busy-waiting for syncbits. In addition, a hardware-supported mechanism for maintaining a first-come first-serve queue of requests for a syncbit is proposed. This queueing mechanism allows for a very efficient implementation of, as well as fair access to, binary semaphores. We also propose to implement Fetch and Add with combining in software rather than hardware. This allows an architecture to scale to a large number of processors while avoiding the cost of hardware combining.

Scenarios for common synchronization events such as work queues and barriers are presented to demonstrate the generality and ease of use of the proposed primitives. The efficient implementation of the primitives is simpler if the multiprocessor has a hardware cache-consistency protocol. To illustrate this point, we outline how the primitives would be implemented in the Multicube multiprocessor [GoWo88].
A unified vector/scalar floating-point architecture
Authors: Jouppi N. P. , Bertoni J. , Wall D. W.
Published: July 2004

In this paper we present a unified approach to vector and scalar computation, using a single register file for both scalar operands and vector elements. The goal of this architecture is to yield improved scalar performance while broadening the range of vectorizable applications. For example, reduction operations and recurrences can be expressed in vector form in this architecture. This approach results in greater overall performance for most applications than does the approach of emphasizing peak vector performance. The hardware required to support the enhanced vector capability is insignificant, but allows the execution of two operations per cycle for vectorized code. Moreover, the size of the unified vector/scalar register file required for peak performance is an order of magnitude smaller than traditional vector register files, allowing efficient on-chip VLSI implementation. The results of simulations of the Livermore Loops and Linpack using this architecture are presented.
Evaluating the performance of software cache coherence
Authors: Owicki S. , Agarwal A.
Published: July 2004

In a shared-memory multiprocessor with private caches, cached copies of a data item must be kept consistent. This is called cache coherence. Both hardware and software coherence schemes have been proposed. Software techniques are attractive because they avoid hardware complexity and can be used with any processor-memory interconnection. This paper presents an analytical model of the performance of two software coherence schemes and, for comparison, snoopy-cache hardware. The model is validated against address traces from a bus-based multiprocessor. The behavior of the coherence schemes under various workloads is compared, and their sensitivity to variations in workload parameters is assessed. The analysis shows that the performance of software schemes is critically determined by certain parameters of the workload: the proportion of data accesses, the fraction of shared references, and the number of times a shared block is accessed before it is purged from the cache. Snoopy caches are more resilient to variations in these parameters. Thus when evaluating a software scheme as a design alternative, it is essential to consider the characteristics of the expected workload. The performance of the two software schemes with a multistage interconnection network is also evaluated, and it is determined that both scale well.
The effect of sharing on the cache and bus performance of parallel programs
Authors: Eggers S. J. , Katz R. H.
Published: July 2004

Bus bandwidth ultimately limits the performance, and therefore the scale, of bus-based, shared memory multiprocessors. Previous studies have extrapolated from uniprocessor measurements and simulations to estimate the performance of these machines. In this study, we use traces of parallel programs to evaluate the cache and bus performance of shared memory multiprocessors, in which coherency is maintained by a write-invalidate protocol. In particular, we analyze the effect of sharing overhead on cache miss ratio and bus utilization.

Our studies show that parallel programs incur substantially higher miss ratios and bus utilization than comparable uniprocessor programs. The sharing component of these metrics proportionally increases with both cache and block size, and for some cache configurations determines both their magnitude and trend. The amount of overhead depends on the memory reference pattern to the shared data. Programs that exhibit good per-processor-locality perform better than those with fine-grain-sharing. This suggests that parallel software writers and better compiler technology can improve program performance through better memory organization of shared data.
Micro-optimization of floating-point operations
Authors: Dally W. J.
Published: July 2004

This paper describes micro-optimization, a technique for reducing the operation count and time required to perform floating-point calculations. Micro-optimization involves breaking floating-point operations into their constituent micro-operations and optimizing the resulting code. Exposing micro-operations to the compiler creates many opportunities for optimization. Redundant normalization operations can be eliminated or combined. Also, scheduling micro-operations separately allows dependent operations to be partially overlapped. A prototype expression compiler has been written to evaluate a number of micro-optimizations. On a set of benchmark expressions operation count is reduced by 33% and execution time is reduced by 40%.
A sequencing-based taxonomy of I/0 systems and review of historical machines
Authors: Smotherman M.
Published: July 2004

A new taxonomy for I/O systems is proposed that is based on the program sequencing necessary for the control of I/O devices. A review of historical machines demonstrates the need for a more comprehensive categorization than previously published and reveals the historical firsts of I/O interrupts in the NBS DYSEAC, DMA in the IBM SAGE (AN/FSQ-7), the interrupt vector concept in the Lincoln Labs TX-2, and fully symmetric I/O in the Burroughs D-825 multiprocessor.
A study parallel disk organizations
Authors: Reddy A. L. N. , Banerjee P.
Published: July 2004

In this paper, several issues related to designing a parallel disk system are discussed. Results of performance evaluation of several parallel disk organizations are presented. A characterization of the disk systems is also presented. Issues such as scalability, networking etc. are discussed. Several problems for future research on improving the I/O performance are pointed out.
Measured response times for page-sized fetches on a network
Authors: Smith J. M. , Maguire G. Q.
Published: July 2004

Previous work has examined the response times associated with disk accesses and the response time associated with various memory access operations. Here, we discuss the response time behavior of access requests for pagesized objects which are made using a network connection. We feel that future architectures must include networked resources as a component of the storage hierarchy; such performance measurements will help architects place these resources intelligently.
A memory controller executing segment operations in time 0(1)
Authors: Seebauer H.
Published: July 2004

A memory controller unit is presented for segmentation of page structured memories. it is intended for the BARDE dataflow processor. Suitably programmed controllers used in parallel can handle arbitrary memory sizes. Segment allocation, release, and access (i.e. translation of a segment relative page addresses into a physical page address) are carried out in at most one add cycle. The allocation method described avoids storage fragmentation and garbage collection by numbering allocated and free pages. A memory controller consists of one page controller for each memory page. The translation from virtual into physical addresses is done by associative search Rmong all page controllers.
A memory controller executing segment operations in time 0(1)
Authors: Seebauer H.
Published: July 2004

A memory controller unit is presented for segmentation of page structured memories. It is intended for the BARDE dataflow processor. Suitably programmed controllers used in parallel can handle arbitrary memory sizes. Segment allocation, release, and access (i.e. translation of a segment relative page addresses into a physical page address) are carried out in at most one add cycle. The allocation method described avoids storage fragmentation and garbage collection by numbering allocated and free pages. A memory controller consists of one page controller for each memory page. The translation from virtual into physical addresses is done by associative search amoag all page controllers.
The design and development of a dynamic program behavior measurement tool for the Intel 8086/88
Authors: Schwartz R. J.
Published: July 2004

When modeling a computer system, it is necessary to study the system's dynamic behavior. Examples of this behavior are branching frequency and operating system usage patterns. The dynamic properties of the system characterize its performance. Models make assumptions about such behavior, but require genuine data to validate the assumptions. In this article, we present a measurement tool that will collect and analyze dynamic program information for the Intel 8086/88. The design and development of the collection tool and its post-processors is described. Details of the interface and collection methods are also given. Finally, a Pascal compilation and a benchmark execution are used to provide examples of data gathered with the tools.
Design and performance of a coherent cache for parallel logic programming architectures
Authors: Goto A. , Matsumoto A. , Tick E.
Published: July 2004

This paper describes the design and performance of a tightly-coupled shared-memory coherent cache optimized for the execution of parallel logic programming architectures. The cache utilizes a copy-back write-allocation protocol having five states and a hardware lock mechanism. Optimizations for logic programming are introduced in four software-controlled memory access commands: direct-write, exclusive-read, read-purge, and read-invalidate. In this paper we describe these operations and present simulated measurements showing their performance advantage for an architecture of the committed-choice language KL1. The cache optimizations also improve the performance of non-committed-choice languages, such as OR-parallel Prolog. A version of the cache design described here is currently being implemented for ICOT's Parallel Inference Machine (PIM).
The Epsilon dataflow processor
Authors: Grafe V. G. , Davidson G. S. , Hoch J. E. , Holmes V. P.
Published: July 2004

The εpsilon dataflow architecture is designed for high speed uniprocessor execution as well as for parallel operation in a multiprocessor system. The εpsilon architecture directly matches ready operands, thus eliminating the need for associative matching stores. εpsilon also supports low cost data fan out and critical sections. A 10 MFLOPS CMOS/TTL processor prototype is running and its performance has been measured with several benchmarks. The prototype processor has demonstrated sustained performance exceeding that of comparable control flow processors running at higher clock rates (three times faster than a 20 Mhz transputer and 24 times faster than a Sun on a suite of arithmetic tests, for example).
An architecture of a dataflow single chip processor
Authors: Sakai S. , Yamaguchi y. , Hiraki K. , Kodama Y. , Yuba T.
Published: July 2004

A highly parallel (more than a thousand) dataflow machine
EM-4
is now under development. The
EM-4
design principle is to construct a high performance computer using a compact architecture by overcoming several defects of dataflow machines. Constructing the
EM-4,
it is essential to fabricate a processing element (PE) on a single chip for reducing operation speed, system size, design complexity and cost. In the
EM-4,
the PE , called
EMC-R,
has been specially designed using a 50,000-gate gate array chip. This paper focuses on an architecture of the
EMC-R.
The distinctive features of it are: a strongly connected arc dataflow model; a direct matching scheme; a RISC-based design; a deadlock-free on-chip packet switch; and an integration of a packet-based circular pipeline and a register-based advanced control pipeline. These features are intensively examined, and the instruction set architecture and the configuration architecture which exploit them are described.
Comparing software and hardware schemes for reducing the cost of branches
Authors: Hwu W. W. , Conte T. M. , Chang P. P.
Published: July 2004

Pipelining has become a common technique to increase throughput of the instruction fetch, instruction decode, and instruction execution portions of modern computers. Branch instructions disrupt the flow of instructions through the pipeline, increasing the overall execution cost of branch instructions. Three schemes to reduce the cost of branches are presented in the context of a general pipeline model. Ten realistic Unix domain programs are used to directly compare the cost and performance of the three schemes and the results are in favor of the software-based scheme. For example, the software-based scheme has a cost of 1.65 cycles/branch vs. a cost of 1.68 cycles/branch of the best hardware scheme for a highly pipelined processor (11-stage pipeline). The results are 1.19 (software scheme) vs. 1.23 cycles/branch (best hardware scheme) for a moderately pipelined processor (5-stage pipeline).
Architectural and organizational tradeoffs in the design of the MultiTitan CPU
Authors: Jouppi N. P.
Published: July 2004

This paper describes the architectural and organizational tradeoffs made during the design of the MultiTitan, and provides data supporting the decisions made. These decisions covered the entire space of processor design, from the instruction set and virtual memory architecture through the pipeline and organization of the machine. In particular, some of the tradeoffs involved the use of an on-chip instruction cache with off-chip TLB and floating-point unit, the use of direct-mapped instead of associative caches, the use of 64-bit vs. 32-bit data bus, and the implementation of hardware pipeline interlocks.
A three-port/three-access register file for concurrent processing and I/O communication in a RISC-like graphics engine
Authors: Anido M. L. , Allerton D. J. , Zaluska E. J.
Published: July 2004

A novel method that provides extremely fast Input/Output (I/O) data transfer to a RISC-like graphics engine is presented. This method employs a combined two-port / two-access and a three-port / three-access register file used for concurrent processing and I/O data transfer. The three-port cell employed is only 25 % larger than the two-port cell, offering considerable advantages over alternative approaches, such as FIFOs or register banks.

This paper discusses some methods that can provide highly fast I/O data transfer in parallel with execution and focuses on the design and implementation of the CMOS-2um register file employed.

Index Terms
- Computer Architecture, Reduced Instruction Set Computers, VLSI Design, Computer Image Generation, Interprocessor Communication.
Adaptive backoff synchronization techniques
Authors: Agarwal A. , Cherian M.
Published: July 2004

Shared-memory multiprocessors commonly use shared variables for synchronization. Our simulations of real parallel applications show that large-scale cache-coherent multiprocessors suffer significant amounts of invalidation traffic due to synchronization. Large multiprocessors that do not cache synchronization variables are often more severely impacted. If this synchronization traffic is not reduced or managed adequately, synchronization references can cause severe congestion in the network. We propose a class of adaptive back-off methods that do not use any extra hardware and can significantly reduce the memory traffic to synchronization variables. These methods use synchronization state to reduce polling of synchronization variables. Our simulations show that when the number of processors participating in a barrier synchronization is small compared to the time of arrival of the processors, reductions of 20 percent to over 95 percent in synchronization traffic can be achieved at no extra cost. In other situations adaptive backoff techniques result in a tradeoff between reduced network accesses and increased processor idle time.
Multiprocessors with a serial multiport memory and a pseudo crossbar of serial links used s a processor-memeory switch
Authors: Litaize Daniel , Hammami Omar , Lalam Mustapha , Mzoughi Adelaziz , Sinrat Pascl
Published: July 2004

This paper presents an inventive information exchange pro-cess between the main memory and cache equipped processors. It makes use of serial multiport memories and high throughput serial transmission supports. It is then possible to consider the realization of a multiprocessor with a common memory shared by several hundreds processors set with a performance level close to that of a crossbar network one's without having its disadvantages. This exchange process generates a family of possible architectures in which serial transfers of informations are parallelized, in the contrary of conventional architectures which serialize parallel transfers of informations.
Register window architecture for multitasking applications
Authors: Quammen D. , Miller D. R. , Tabak D.
Published: July 2004

The organization of large register banks into windows hasbeen shown to be effective in enhancing the performance of sequential programs. One drawback of such an organization, which is of of minor importance to sexsquential languages, is the overhead encountered when the register bank must be replaced during a task switch. With concurrent language paradigms, such as are found in Ada, Occam, and Modula-2, these switches will be more frequent. We introduce here a methodology, and an architecture, which greatly reduces this overhead while maintaining the inherent advantages of the register window approach. In addition, we present ways of implemnting traditional stacks and queues, as well as hierarchical storage structures using windows.
Description and performance of a class of orthogonal multiprocessor networks
Authors: Scherson Isaac D. , Corbett Peter F.
Published: July 2004

We describe a construction technique for orthogonal multiprocessors, based on a definition of the inner product and the orthogonality of binary vectors. Orthogonal networks include spanning bus hypermeshes. A measure of communications overhead in parallel processing systems is defined as a function of algorithm and architecture. Its dependence on the topology of the interconnection network is illustrated by the computation of average distance in a spanning bus hypermesh. The binary hypercube is a simple example of this type of network. The communications overhead can be incorporated in an expression for the expected speedup of a parallel processing system.
An address gneration unit for array accessing
Authors: Hsu Tsong-Chih , Kung Ling-Yang
Published: July 2004

Most current systems have an undesirable large
semantic gap
in that the objects and operations reflected in their architectures are not closely reflected to the objects and operations provided in programming languages [1]. Far more effort than in the past should be spend on the design of novel computer architectures, supporting modern software concepts better than the traditional Von Neumann designs, or with other words, which can narrow the semantic gap. In this paper we propose an address generation unit for array accessing. One major research effort in this research may be to narrow this semantic gap between architecture and array concepts.
Realizing high IPC through a scalable memory-latency tolerant multipath microarchitecture
Authors: Morano D. , Khalafi A. , Kaeli D. R. , Uht A. K.
Published: July 2004

A microarchitecture is described that achieves high performance on conventional single-threaded program codes without compiler assistance. To obtain high instructions per clock (IPC) for inherently sequential (e.g., SpecInt-2000 programs), a large number of instructions must be in flight simultaneously. However, several problems are associated with such microarchitectures, including scalability, issues related to control flow, and memory latency.Our design investigates how to utilize a large mesh of processing elements in order to execute a singlethreaded program. We present a basic overview of our microarchitecture and discuss how it addresses scalability as we attempt to execute many instructions in parallel. The microarchitecture makes use of control and value speculative execution, multipath execution, and a high degree of out-of-order execution to help extract instruction level parallelism. Execution-time predication and time-tags for operands are used for maintaining program order. We provide simulation results for several geometries of our microarchitecture illustrating a range of design tradeoffs. Results are also presented that show the small performance impact over a range of memory system latencies.
Dissecting Cyclops
Authors: Almási George , Caşcaval Cǎlin , Castaños José G. , Denneau Monty , Lieber Derek , Moreira José E. , Warren Henry S.
Published: July 2004

Multiprocessor systems-on-a-chip offer a structured approach to managing complexity in chip design. Cyclops is a new family of multithreaded architectures which integrates processing logic, main memory and communications hardware on a single chip. Its simple, hierarchical design allows the hardware architect to manage a large number of components to meet the design constraints in terms of performance, power or application domain.This paper evaluates several alternative Cyclops designs with different relative costs and trade-offs. We compare the performance of several scientific kernels running on different configurations of this architecture. We show that by increasing the number of threads sharing a floating point unit we can hide fairly high cache and memory latencies. We prove that we can reach the theoretical peak performance of the chip and we identify the optimal balance of components for each application. We demonstrate that the design is well adapted to solve problems that are difficult to optimize. For example, we show that sparse matrix vector multiplication obtains 16 GFlops out of 32 GFlops of peak performance.
An EGA approach to the compile-time assignment of data to multiple memories in digital-signal processors
Authors: Gréwal Gary , Wilson Tom , Morton Andrew
Published: July 2004

In this paper, we present a methodology, based on an Enhanced Genetic Algorithm (EGA), for assigning data objects to dual-bank memories. Our approach is global, and special effort is made to identify those objects that could potentially benefit from an assignment to a specific memory, or perhaps duplication in both memories. The enhancements to the genetic algorithm include a directed mutation operator and a new type of elitism. Together, these enhancements improve the performance of the genetic algorithm and allow the EGA to run unsupervised. The EGA has been incorporated into a retargetable, optimizing compiler for embedded systems, currently under development at the University of Guelph.
A vector and array multiprocessor extension of the sylvan architecture
Authors: Burkowski F. J.
Published: July 2004

The main intent of this paper will be the description of a multiprocessor system that uses microprogrammed hardware to support operating system primitives that contribute to its high performance vector processing capability. The system consists of nodes that communicate over a system interconnect. Each node is a tripartite subsystem that consists of a host processor complex running application code, a vector co-processor and a kernel support processor that handles both operating system functions and control of the vector co-processor. The microcoded kernel processor is used to support a message based operating system that allows concurrent processes to communicate while residing in the same node or in different nodes. Since the kernel processor controls the functioning of the vector co-processor as well as the management of processes (for example, context switching), the node can utilize the resources of the co-processor very effectively.
The schuss filter
Authors: Gonzalez-Rubio R. , Rohmer J. , Terral D.
Published: July 2004

This paper describes the basic principles, the architecture and the applications of a processor called the SCHUSS filter*.

The SCHUSS filter can be seen as a device with two inputs and one output; the first input is the filtering criterion (a program); the second input is the data to be filtered (in a sequential way). The output is the data which fulfills the filter criterion.

Under the architectural point of view the SCHUSS filter can be seen as a specialized processor (in filtering) but also as a general purpose processor. Working as a specialized processor, it can process “on the fly” data coming from a disk where “on the fly” means at the normal disk transfer rate. Even if now disk transfers rates are up to 3 Mbyte/sec SCHUSS can execute searches of reasonable complexity in one pass.

The idea is to off-load the host processor of search tasks and other kinds of processing.
The reduction of branch instruction execution overhead using structured control flow
Authors: Wedig Robert G. , Rose Marc A.
Published: July 2004

This paper presents a technique for specifying change of control (e.g. branch) commands at a sequential processor's macroinstruction set level. It is shown that by representing high level language (HLL) control statements with special machine language instructions, the usual delays associated with control flow changes can be reduced. Preserving the HLL control flow information increases performance by reducing both the number of executed branches and pipeline breaks.
The use of static column ram as a memory hierarchy
Authors: Goodman James R. , Chiang Men-chow
Published: July 2004

The Static Column RAM devices recently introduced offer the potential for implementing a direct-mapped cache on-chip with only a small increase in complexity over that needed for a conventional dynamic RAM memory system. Trace-driven simulation shows that such a cache can only be marginally effective if used in the obvious way. However it can be effective in satisfying the requests from a processor containing an on-chip cache. The SCRAM cache is more effective if the processor cache handles both instructions and data.
Data broadcasting in linearly scheduled array processors
Authors: Fortes J. A. B. , Moldovan D. I.
Published: July 2004

A major problem in executing algorithms in array processors is the implementation of broadcasts without unnecessary speed-up factor degradation. We discuss when and how broadcasts can be eliminated or reduced to easily implementable sequences of reduced local broadcasts. Algorithms are modelled as a structured set of indexed computations which operate on variables associated with a referencing or indexing function. The discussion is restricted to variables with linear indexing functions and to algorithms linearly scheduled for execution in array processors. Linear indexing functions are represented as affine matricial functions of the index set of the algorithm. The linear part of such representation is a coefficient matrix denoted the indexing matrix. Linear schedules are defined as linear time-space allocation functions mapping the computations of an algorithm into time and processors. We discuss necessary and sufficient conditions for the occurrence of broadcasts in a linearly scheduled algorithm. Necessary and sufficient conditions and constructive criteria are given for selecting linear schedules for which all broadcasts are eliminated or reduced to sequences of small local broadcasts.
Modular matrix multiplication on a linear array
Authors: Ramakrishnan I. V. , Varman P. J.
Published: July 2004

A matrix-multiplication algorithm on a linear array using an optimal number of processing elements is proposed. The local storage required by the processing elements and the I/O bandwidth required to drive the array are both constants that are independent of the sizes of the matrices being multiplied. The algorithm is therefore modular, that is, arbitrarily large matrices can be multiplied on a large array built by cascading small arrays. The array is well-suited for VLSI implementation.
Message repository definitional facility
Authors: Kavi Krishna M. , Banios Edward W. , Shriver Bruce D.
Published: July 2004

An architectural model of a system research tool, the Message Repository Definitional Facility (MRDF), is presented. MRDF provides for interprocess communication and synchronization by message passing, and permits the user a wide selection of policy options, promising general descriptive power. The project's current levels of system definition, design considerations and issues, and plans for future development are briefly described. The current goal for this research is the implementation of the MRDF in the data flow simulation environment for test and evaluation. Potential application of this concept beyond the research tool stage is speculated as incorporation in a computer architecture to support concurrent processes and a “self-optimizing” operating system.
A high performance factoring machine
Authors: Rudd W G , Buell Duncan A , Chiarulli Donald M
Published: July 2004

Factoring, primality testing, and other problems of current interest [1, 2, 3, 4, 5, for example] in experimental number theory require machines with different architectures from those for any other application. Algorithms for such problems are small, but their execution requires high-speed arithmetic on very long integers interspersed with shorter precision computing that can conveniently be done by several processors acting in parallel. In this paper, we describe the preliminary design of a processor specifically for computational number theoretic problems. The primary component is a 256-bit ALU which is dynamically reconfigurable to provide for parallel independent operations on groups of 32-bit subwords within the 256-bit word.
VLSI based design principles for MIMD multiprocessor computers with distributed memory management
Authors: Philipson Lars
Published: July 2004

Design principles for MIMD multiprocessor computers with virtual memory based on a common, global and uniform logical address space, supporting parallel, procedural languages such as Ada (Ada is a registered trademark of the US Government, AJPO), are discussed. The major design issues are identified and suggested solutions given, the most important of which are distributed, associative address translation, and local mechanisms supporting efficient resource allocation policies to reduce over-all communication costs. Arguments are given for using shared memory and bus-based global communication. Some preliminary studies of bus-based intercommunication schemes, parallel language implementation, capacity simulation and VLSI implementation are reviewed, as well as a number of existing experimental and commercial multiprocessors. Finally an experimental system for evaluation of different mechanisms and policies in systems of the suggested type is outlined.
Dynamic decentralized cache schemes for mimd parallel processors
Authors: Rudolph Larry , Segall Zary
Published: July 2004

This paper presents two cache schemes for a shared-memory shared bus multiprocessor. Both schemes feature decentralized consistency control and dynamic type classification of the datum cached (i.e. read-only, local, or shared). It is shown how to exploit these features to minimize the shared bus traffic. The broadcasting ability of the shared bus is used not only to signal an event but also to distribute data. In addition, by introducing a new synchronization construct, i.e. the Test-and-Test-and-Set instruction, many of the traditional. parallell processing “hot spots” or bottlenecks are eliminated. Sketches of formal correctness proofs for the proposed schemes are also presented. It appears that moderately large parallel processors can be designed by employing the principles presented in this paper.
Cache hit ratios with geometric task switch intervals
Authors: Haikala Ilkka J.
Published: July 2004

A simple Markov chain model is used to estimate the effect of the cache flushes. The model assumes LRU stack model of program behaviour and geometrically distributed lengths of task switch intervals. Given the LRU stack depth distribution, one may easily compute estimates of miss ratios for caches of all sizes with any desired average task switch interval. The model is validated with three reference strings recorded from simulations of large B7800 Extended Algol programs. The estimates obtained with the Markov model are within 12% error margin from the results obtained by cache simulation.
The significance of microprogramming
Authors: Rosin Robert F.
Published: July 2004

Interest in the topic of microprograrnming appears to have had a great growth in the middle and late 1960's, but since that time it has leveled off or declined somewhat. This paper examines the reasons behind this development and then offers a reconsideration of and a new proposal for the definition of microprogramming.This result is supported by the consideration of three phenomena. First is the evolution of microprogramming during the past twenty years. Second is the evolution in the use of interpretation as an implementation technique. Third is the set of "rules of thumb" resulting from the system designer having to resolve conflicting forces attempting to influence his activity.Five possible meanings of the term microprogramming are considered and rejected totally or in part prior to the one finally offered. The suggestion is made that this redefined concept be avoided as much as possible in the future, and two avenues for research alternatives are encouraged instead.
Reply to the case against stack-oriented instruction sets
Authors: Schulthess Peter U. , Mumprecht Eduard P.
Published: July 2004

In contrast to general opinion the advantages of stack architectures appear most clearly when handling more complex situations than evaluation of simple expressions.
Hardware detection of undefined references
Authors: Gerrity G. W.
Published: July 2004

The construction of reliable programs could benefit substantially from improved hardware support. The automatic detection of one particularly common programming error, namely, the failure to define the value of a data element before referencing it, is quite simple and can be implemented in most microprogrammed machines. A method of introducing machine-detectable null elements for this purpose is described. This leads naturally to a re-appraisal of the basic operations CLEAR and ASSIGN.
On minimizing contention at semaphores
Authors: Denning Peter J. , Dennis T. Don
Published: July 2004

A method for reducing semaphore and ready list contention in multiprocessor operating systems is described. The method is based on tagged memory, semaphore words, and the principle of locking the individual semaphores rather than the programs that manipulate them.
A systematic approach to the design and implementation of a computer instruction set
Authors: Marovac Nenad
Published: July 2004

When selecting the instruction set for a computer family, the designer must consider several criteria. The design considerations leading to the final instruction set for a new computer are very seldom published. The purpose of this paper is twofold:• Discussion of the design and implementation criteria for an instruction set.• Proposal of a systematic approach for the design and implementation of an instruction set.
Providing architectural support for expert systems
Authors: Graham Peter C. J.
Published: July 2004

Many current expert systems are constructed in a rule based fashion. That is, using a series of rules or productions which implement the reasoning logic of the system. While such an approach is well suited to the task of building expert systems, it is not well suited to their implementation via conventional Von-Neumann architectures.What is required is an architecture which is more appropriate for evaluating and executing rules. Such a machine requires the ability to perform many small, heterogenous operations in parallel. A dataflow machine provides just such an ability and there is a natural mapping which may be exploited from rules to a series of dataflow templates.