bluuebunny/crossref_metadata_2025 huggingface dataset:
MERT - a multi-environment real-time operating system
Authors: Bayer D. L. , Lycklama H.
Published: November 2005

MERT is a multi-environment real-time operating system for the Digital Equipment PDP-11/45 and 11/70 computers. It is a structured operating system built on top of a kernel which provides the basic services such as memory management, process scheduling, and trap handling needed to build various operating system environments. Real-time response to processes is achieved by means of preemptive priority scheduling. The file system structure is optimized for real-time response. Processes are built as modular entities with data structures that are independent of all other processes. Interprocess communication is achieved by means of messages, event flags, shared segments, and shared files. Process ports are used for communication between unrelated processes.
Architecture of a real time operating system
Authors: Pruitt J. L. , Case W. W.
Published: November 2005

Architecture is receiving increasing recognition as a major design factor for operating systems development which contributes to the clarity, and modifiability of the completed system. The MOSS Operating System uses an architecture based on hierarchical levels of system functions overlayed dynamically by asynchronous cooperating processes carrying out the system activities.

Since efficient operation in a real time environment requires that the number of processes and process switches be kept to a minimum, the MOSS system uses processes only where a truly asynchronous activity is identified. The layers of the MOSS Operating System do not represent a hierarchical structure of virtual machine processes, but rather a hierarchy of functions used to create the processes.

This paper describes the layering concepts and process concepts defining the system architecture. It also presents an overview of the specific functions and processes of the MOSS Operating System.
An operational system for computer resource sharing
Authors: Cosell B. P. , Johnson P. R. , Malman J. H. , Schantz R. E. , Sussman J. , Thomas R. H. , Walden D. C.
Published: November 2005

Users and administrators of a small computer often desire more service than it can provide. In a network environment additional services can be provided to the small computer, and in turn to the users of the small computer, by one or more other computers. An operational system for providing such “resource sharing” is described; some “fundamental principles” are abstracted from the experience gained in constructing the system; and some generalizations are suggested.
Sharing data and services in a virtual machine system
Authors: Bagley J. D. , Floto E. R. , Hsieh S. C. , Watson V.
Published: November 2005

Experimental additions have been made to a conventional virtual machine system (VM/370) in order to support a centralized program library management service for a group of interdependent users. These additions enable users to share read/write access to a data base as well as processing services. Although the primary motivation was the enhancement of performance, considerable attention was given to retaining the inherent advantages of the virtual machine system. Extended applications of the basic technique are described and the implications of such extensions on operating system design are considered.
Formal properties of recursive Virtual Machine architectures.
Authors: Belpaire Gerald , Hsu Nai-Ting
Published: November 2005

A formal model of hardware/software architectures is developed and applied to Virtual Machine Systems. Results are derived on the sufficient conditions that a machine architecture must verify in order to support VM systems. The model deals explicitly with resource mappings (protection) and with I/O devices. Some already published results are retrieved and other ones, more general, are obtained.
The PDP-11 virtual machine architecture
Authors: Popek Gerald J. , Kline Charles S.
Published: November 2005

At UCLA, a virtual machine system prototype has been constructed for the Digital Equipment Corporation PDP-11/45. In order to successfully implement that system, a number of hardware changes have been necessary. Some overcome basic inadequacies in the original hardware for this purpose, and others enhance the performance of the virtual machine software. Steps in the development of the modified hardware architecture, as well as relevant aspects of the software structure, are discussed. In addition, a case study of interactions between hardware and software developments is presented, together with conclusions motivated by that experience.
Error resynchronization in producer-consumer systems
Authors: Russell David L. , Bredt Thomas H.
Published: November 2005

This paper is concerned with error processing for parallel producer-consumer interactions such as encountered in the desing of multi-process operating systems. Solutions to resynchronization problems that occur when a consumer process detects errors in information received from a producer process are presented. Fundamental properties of this error processing are discussed. It is shown that explicit error processing results in an increase in program complexity and a decrease in the ease of understanding a program.
A multi-microprocessor computer system architecture
Authors: Arden Bruce W. , Berenbaum Alan D.
Published: November 2005

The development of microprocessors has suggested the design of distributed processing and multiprocessing computer architectures. A computer system design incorporating these ideas is proposed, along with its impact on memory management and process control aspects of the system's operating system. The key design feature is to identify system processes with microprocessors and interconnect them in a hierarchy constructed to minimize intercommunication requirements.
Policy/mechanism separation in Hydra
Authors: Levin R. , Cohen E. , Corwin W. , Pollack F. , Wulf W.
Published: November 2005

The extent to which resource allocation policies are entrusted to user-level software determines in large part the degree of flexibility present in an operating system. In Hydra the determination to separate mechanism and policy is established as a basic design principle and is implemented by the construction of a kernel composed (almost) entirely of mechanisms. This paper presents three such mechanisms (scheduling, paging, protection) and examines how external policies which manipulate them may be constructed. It is shown that the policy decisions which remain embedded in the kernel exist for the sole purpose of arbitrating conflicting requests for physical resources, and then only to the extent of guaranteeing fairness.
Protection in the Hydra Operating System
Authors: Cohen Ellis , Jefferson David
Published: November 2005

This paper describes the capability based protection mechanisms provided by the Hydra Operating System Kernel. These mechanisms support the construction of user-defined protected subsystems, including file and directory subsystems, which do not therefore need to be supplied directly by Hydra. In addition, we discuss a number of well known protection problems, including Mutual Suspicion, Confinement and Revocation, and we present the mechanisms that Hydra supplies in order to solve them.
Computational processor demands of Algol-60 programs
Authors: Brundage Robert E. , Batson Alan P.
Published: November 2005

The characteristics of computational processor requirements of a sample of Algol-60 programs have been measured. Distributions are presented for intervals of processor activity as defined by input-output requests and segment allocation requests occurring within the Johnston contour model and within a stack model in which array allocations are treated separately. The results provide new empirical data concerning the behavior of this class of programs. Some implications of the empirical results which may influence computer system design and performance are presented and discussed.
The enforcement of security policies for computation
Authors: Jones Anita K. , Lipton Richard J.
Published: November 2005

Security policies define who may use what information in a computer system. Protection mechanisms are built into a system to enforce security policies. In most systems, however, it is quite unclear what policies a mechanism can or does enforce.

This paper defines security policies and protection mechanisms precisely and bridges the gap between them with the concept of soundness: whether a protection mechanism enforces a policy. Different sound protection mechanisms for the same policy can then be compared. We also show that the “union” of mechanisms for the same program produces a more “complete” mechanism. Although a “maximal” mechanism exists, it cannot necessarily be constructed.
Models of memory scheduling
Authors: Agrawala A. K. , Bryant R. M.
Published: November 2005

Queueing theoretic models of single and multi-processor computer systems have received wide attention in the computer science literature. Few of these models consider the effect of finite memory size of a machine and its impact on the memory scheduling problem. In an effort to formulate an analytical model for memory scheduling we propose four simple models and examine their characteristics using simulation. In this paper, we discuss some interesting results of these simulations.
RISC assessment
Authors: Patterson David A. , Piepho Richard S.
Published: November 2005

We present the result of an informal experiment comparing the performance of one Reduced Instruction Set Computer, RISC I, to five traditional computers, VAX-11/780, PDP-11/70, BBN C/70, MC68000, and Z8000, in a high-level language environment. Measuring either absolute performance or the penalty for using high-level languages, the best computer is RISC I.
HLL architectures
Authors: Kavi Krishna , Belkhouche Boumediene , Bullard Evelyn , Delcambre Lois , Nemecek Stephen
Published: November 2005

An examination of high-level language architectures reveals that some design considerations are based on inaccurate premises. This paper discusses some HLL architecture design misconceptions. Some features that should be considered in the design of HLL architectures are presented. Based on the HLL architecture design considerations, a methodology for quantifying architecture is proposed.
The NYU Ultracomputer—designing a MIMD, shared-memory parallel machine (Extended Abstract)
Authors: Gottlieb Allan , Grishman Ralph , Kruskal Clyde P. , McAuliffe Kevin P. , Rudolph Larry , Snir Marc
Published: November 2005

We present the design for the NYU Ultracomputer, a shared-memory MIMD parallel machine composed of thousands of autonomous processing elements. This machine uses an enhanced message switching network with the geometry of an Omega-network to approximate the ideal behavior of Schwartz's paracomputer model of computation and to implement efficiently the important fetch-and-add synchronization primitive. We outline the hardware that would be required to build a 4096 processor system using 1990's technology. We also discuss system software issues, and present analytic studies of the network performance. Finally, we include a sample of our effort to implement and simulate parallel variants of important scientific programs.
Performance and fault tolerance improvements in the Inverse Augmented Data Manipulator network
Authors: McMillen Robert J. , Siegel Howard Jay
Published: November 2005

The Inverse Augmented Data Manipulator (IADM) is a multistage interconnection network based on the Augmented Data Manipulator (ADM) and Feng's data manipulator. It is designed to be used in large-scale parallel/distributed processing systems for communication among processors, memories, and other system devices. Two aspects of IADM network design are discussed: performance and fault tolerance. A single stage look-ahead scheme for predicting blockage is presented to enhance performance. Next, one method of adding some links to the network to enable it to tolerate one link failure is described. Finally, a different method of adding links is shown that both improves performance and allows the network to tolerate two switching element or two link failures. Included is a new routing tag scheme that accommodates the new links.
The Gamma network
Authors: Parker D. S. , Raghavendra C. S.
Published: November 2005

The Gamma network is an interconnection network connecting N=2' inputs to N outputs. It consists of log
2
N stages with N switches per stage, each of which is a 3 input, 3 output crossbar. The stages are linked via “power of two” and identity connections in such a way that redundant paths exist between the input and output terminals. In this network, a path from a source to a destination may be represented using one of the redundant forms of the difference between the source and destination numbers. The redundancy in paths may thus be studied using the theory of redundant number systems. Results are obtained on the distribution of paths connecting inputs to outputs, and the permuting capabilities of the Gamma network. Switch settings for certain frequently used permutations and control mechanisms are also considered in this paper. This network has an interesting application in solving tridiagonal systems using the odd-even elimination algorithm.
Efficient code generation for horizontal architectures
Authors: Rau B. Ramakrishna , Glaeser Christopher D. , Picard Raymond L.
Published: November 2005

A horizontal architecture consists of a number of resources that can operate in parallel, each of which is controlled by a field in the wide instruction word. Such architectures offer the potential for high performance scientific computing at a modest cost. If this potential performance is to be realized, the multiple resources of a horizontal processor must be scheduled effectively. The scheduling task for conventional horizontal processors is quite complex and the construction of highly optimizing compilers for them is a difficult and expensive project. The polycyclic architecture is a horizontal architecture with architectural support for the scheduling task. The complexity of scheduling conventional horizontal processors and the ease of scheduling polycyclic processors is demonstrated by means of an example.
Towards a family of languages for the design and implementation of machine architectures
Authors: Dasgupta Subrata , Olafsson Marius
Published: November 2005

In recent years, increases in complexity of hardware/firmware systems, and the concern for systems reliability have resulted in growing interest in methodologies and tools for the design, description and verification of computer systems. A vital component of any such design methodology is the language used for representing the design. In the case of particularly complex systems the design process may involve a succession of stages each of which represents the system at a particular level of abstraction. In such situations several languages may be required, each suited to a particular level of abstraction.

We present here, one such
family of languages
, consisting at present of two members, S*A, an architectural description language, and S*, a high level microprogramming language schema. These closely related (“kin”) languages may be used collaboratively for the systematic, top-down development of an architecture, down to the microcode level. The resulting descriptions of the architecture provide, in addition, a complete unified document of the multilevel design process.
Database filters
Authors: Pramanik Sakti
Published: November 2005

Several hardware database-searchers for a large number of patterns or keys are presented. These searchers can be implemented by a random access memory and are suitable for VLSI implementation. Application of these searchers as database filters is described; a filter detects all the matched records in the database as well as a few others which don't match. The percentage of these unmatched records that manage to pass through can be reduced to any arbitrary minimum value; this is done, for example, by using several filters together, or passing the output records repeatedly through the same filters. Several filters can be used together by cascading them in series, parallel, and series-parallel fashion. The performance of the filters using iterative approach depends very much on the regrouping algorithms of the patterns/keys. Several such algorithms are presented and their performances compared. A single pass is required if they are pipelined. Hardware organization for different pipelined approaches are also studied. Experiments are performed for all the different hardware organizations mentioned above on an employee-name database. The results are presented in graph forms. They support the usefulness of these hardware organizations as filters.
On the semantic structure of information - A proposal of the abstract storage architecture
Authors: Tokoro Mario , Takizuka Takashi
Published: November 2005

An important strategy to enhance both the reliability and performance of high-level program execution is to have computer architecture provided with the mechanisms, such as i) to address information in a unified manner regardless of the structure and/or of the size of information objects, and ii) to dynamically check the eligibility of information accesses. This paper firstly gives the foundation for such abstraction mechanisms through examining the semantic structure of information objects. Information is hereby formalized as a set of relations between an access and the entity that is accessed. The relations are hierarchically classified into four categories, each of which associates to the corresponding level of abstraction. Object-oriented architecture which reflects this hierarchical classification directly in its storage organization is then proposed. This architecture is called the abstract storage architecture. Issues in designing the abstract storage architecture are described. The effectiveness of such architecture is concluded from the view points of both the implementation of existing high-level languages and the design of future high-level languages.
Hardware sorter and its application to data base machine
Authors: Dohi Yasunori , Suzuki Akira , Matsui Noriyuki
Published: November 2005

The main contribution of this paper is the design of a hardware sorter. This sorter is configured as a balanced, fixed binary tree of node units; the configuration of the sorter is independent of the length of data to be sorted. Each node unit can be realized on a single LSI chip. The logic of the hardware sorter design is heavily influenced by a specific, compressed, representation of sorted data. Using this hardware sorter and a few auxiliary functions based on the sorted property, we demonstrate the design of a relational data base machine.
µ3L
Authors: Castan M. , Organick E. I.
Published: November 2005

To eliminate the conceptual distance between the hardware instruction set and the user interface, some architects advocate High Level Language (HLL) machines. To obtain simple, fast and cheap machines, some architects advocate Reduced Instruction Set Computer (RISC) machines. This paper reconciles both views and presents an architecture which has both an HLL user interface and a RISC hardware. Each instance of this architecture is a module of an HLL multiprocessor system.

Functional programming languages offer a bridge between mathematical models of computation and multiprocessor system environments. We choose the language AFPL (A Functional Programming Language) as the HLL user interface. AFPL's direct execution model, based on a tree structured internal representation, takes advantage of the parallelism inherent in programs by decomposing them on the fly into tasks which can be performed concurrently.
The heap/substitution concept - an implementation of functional operations on data structures for a reduction machine
Authors: Hommes F.
Published: November 2005

At first the concept of reduction by direct substitution is described. The syntax of a subset of Berkling's reduction language is given and then its semantics is defined by a set of substitution rules. An example - a program operating on a data structure - will demonstrate two aspects: firstly, it shows how reduction using substitution works, and secondly, it points out the n
2
-problem, i.e. the time taken to run the program is proportional to n
2
, where n is the number of items in the data structure. We discuss the problem and then give a solution, which we call the heap/substitution concept. The solution is an extension of the substitution concept and we get it by adding a restricted use of an environment. All advantages of reduction by substitution remain in effect but the time taken to evaluate programs operating on large data structures is now proportional to n. It is also shown that the heap/substitution concept can be used to implement an efficient implementation of recursive function calls.
A shared resource algorithm for distributed simulation
Authors: Reynolds Paul F.
Published: November 2005

We propose a distributed simulation method which is particularly well suited for the simulation of large synchronous networks. In general, distributed simulation has significant potential for alleviating the time and memory constraints often encountered when using conventional simulation techniques. Currently proposed methods for distributed simulation suffer performance degradation due to the employment of strategies for preventing deadlock and due to artificial blocking of processes. We describe a new method for doing distributed simulation which is deadlock free whenever the physical system being simulated is deadlock free. Furthermore, our method does not suffer from artificial blocking of processes.
Duplication of packets and their detection in X.25 communication protocols
Authors: Jain Bijendra N.
Published: November 2005

In the context of X.25 communication protocols, this paper is concerned with the process of duplication of packets at the frame level, and with their detection at the packet level. With suitable constraints involving

(i) the window sizes used at both the frame and packet levels to flow control, and

(ii) the numbering scheme used to number User Data packets,

it is possible to detect and discard all duplicate copies thereof. Further, it is argued that duplication of 'messages' by a particular layer be detected at the level where these messages are generated and interpreted. Deferring this detection to higher levels is unnecessary and more difficult.
A heterogeneous multiprocessor design and the distributed scheduling of its task group workload
Authors: Miller Leslie Jill
Published: November 2005

A multiprocessor architecture is proposed which is based on the Multics concept of having all on-line information processor-addressible. All memory management is done by an intelligent paged virtual memory system, and each processor deals only with those segments relevant to its single executing program. The processors are chosen to have different implementations of a single system-wide instruction set and the problem is to effectively schedule different categories of programs, called task groups, on the dissimilar processors.

Average weighted instruction times for each task group on every processor are defined as task/processor suitability measures, and typical values are given for different groups of programs running on IBM 370 models. Through the use of linear programming techniques, an optimal schedule for any such multiprocessor is then defined for the static case where task group loads and task/processor suitability values are known in advance. A priority-based task management scheduling algorithm is then defined which uses the optimal schedule of the formal model as a parameter, and its performance is simulated.
A dual processor VAX 11/780
Authors: Goble George H. , Marsh Michael H.
Published: November 2005

This paper describes the design of a dual processor VAX 11/780 built at the Purdue University Electrical Engineering School. It covers the conversion of a standard single processor VAX 11/780 into a dual processor system. A detailed description of hardware modifications performed and a parts list are included.

The dual processor VAX is currently running a modified version of the UNIX (Fourth Berkeley Distribution) operating system. Because of licensing restrictions, operating system modifications will only be covered in general. Finally some performance evaluation will be discussed along with the problems encountered.
Probabilistic analysis of a crossbar switch
Authors: Mudge T. N. , Makrucki B. A.
Published: November 2005

This paper presents a probabilistic analysis of a crossbar switch interconnection network. A crossbar switch can be used to interconnect various combinations of computer subsystems. In the analysis below it is assumed, without loss of generality, that the crossbar is being used to connect
N
processors to
M
memories. The crossbar is termed an N-M crossbar (read “N to M crossbar”). General expressions are developed for a variety of performance figures for an N-M crossbar including: the probability of a memory request being accepted (i.e. not being blocked by another request to the same memory), the expected bandwidth of the crossbar, and the average wait time of a request before it is accepted. Closed form solutions to these expressions are given for the uniform request case and for the favorite memory case (i.e. where processor
i
requests memory
i
with a higher probability than others memories). The closed form solutions are tested against simulations.
Resource allocation in rectangular SW banyans
Authors: Premkumar U. V. , Browne J. C.
Published: November 2005

This paper presents an algorithm for the formation of configurations connecting processors to memory and I/O devices on rectangular SW banyan networks with equivalent processor resources as the base nodes and equivalent memory and I/O resources as the apex nodes. Given a set of resource configuration requests, the algorithm always finds a partition of the network that meets the requests in space and time complexity linear with respect to the number of resources in the network.
Towards a taxonomy of computer architecture based on the machine data type view
Authors: Giloi W. K.
Published: November 2005

Existing taxonomies of computer architecture lack the descriptive tools to deal with the large variety of existing principles, features, and mechanisms of the existing spectrum of single processor, multi processor, and multi computer architectures. Consequently, they lack the discriminating power to be able to taxonomize computer architecture. In the paper, a new approach toward a complete taxonomy is presented. The key to the taxonomy is to start with the dichotomy of 'operational principle' and 'hardware structure' as the foundation of a computer architecture and describe the constituents of the operational principle in terms of 'machine data types' consisting of 'machine data objects', their representations, and the functions applicable on the objects. The resulting taxonomy provides a systematic approach to the design of innovative computer architectures.
Framework for a taxonomy of fault-tolerance attributes in computer systems
Authors: Avižienis Algirdas
Published: November 2005

A conceptual framework is presented that relates various aspects of fault-tolerance in the context of system structure and architecture. Such a framework is an essential first step for the construction of a taxonomy of fault-tolerance.

A design methodology for fault-tolerant systems is used as the means to identify and classify the major aspects of fault-tolerance: system pathology, fault detection and recovery algorithms, and methods of modeling and evaluation.

A computing system is described in terms of four universes of observation and interpretation, ordered in the following sequence: physical, logic, information, and interface, or user's. The description is used to present a classification of faults, i.e., the causes of undesired behavior of computing systems.
Caddie an interactive design environment
Authors: Pehrson Björn , Parrow Joachim
Published: November 2005

The paper reports on a design methodology and an experimental CAD system, named Caddie, based on this methodology. Caddie supports specification, analysis and synthesis of objects that can be described as communicating processes, e.g. electronic circuits, sequential networks, digital processors and programs. Basic ideas behind Caddie are:

- top-down hierarchical design. Specifications are broken down hierarchically by stepwise refinement

- integrated design. Design objects from different design phases are described in the same formalism. This technique allows universal design operations.

- formal systems with varying descriptive and decisive powers are exploited

- incremental design. Parts can be modified separately without effect on other parts.

- interactive design, i.e. the designer can interact with the design tools in real time

Caddie is implemented in Concurrent-lisp, an extension of lisp supporting concurrent programming. Automatic programming tools have been used in the implementation. Caddie consists of

- an interactive parallel programming environment

- automatic design procedures

- a run-time system for execution of design objects (real-time and branching or exhaustive simulation)
On the verification of computer architectures using an architecture description language
Authors: Dasgupta Subrata
Published: November 2005

In a previous paper [8], we had presented the notion of a family of languages for the multilevel design and description of computer architectures. Details of a particular language family, currently under development, was also described. One of the constituent members of this family is S@@@@, intended for the specifications of the outer (or exo-) and inner (or endo-) architectures of general purpose von Neumann style computers. In this paper we describe the formalization and application of S@@@@ to the formal
proofs of correctness
of architecture designs.
Architecture of the PSC-a programmable systolic chip
Authors: Fisher Allan L. , Kung H. T. , Monier Louis M. , Dohi Yasunori
Published: November 2005

In recent years, many systolic algorithms have been proposed as solutions to computationally demanding problems in signal and image processing and other areas. Such algorithms exploit the regularity and parallelism of problems to achieve high performance and low I/O requirements. Since systolic algorithms generally consist of a few types of simple processors, or systolic cells, connected in a regular pattern, they are less expensive to design and implement than more general machines.

This advantage is offset by the fact that a particular systolic system can generally be used only on a narrow set of problems, and thus design cost cannot be amortized over a large number of units. One way to approach this problem is to provide a programmable systolic chip (PSC), many copies of which can be connected and programmed to implement many systolic algorithms.

The systolic environment, by virtue of its emphasis on continuous, regular flow of data and fairly simple per-cell processing, imposes new design requirements for programmable processors which are quite different from those found in a general-purpose system. This paper describes the CMU PSC, a single-chip microprocessor suitable for use in groups of tens or hundreds for the efficient implementation of a broad variety of systolic arrays. The processor has been fabricated in nMOS, and is undergoing testing.
Synchronizing large VLSI processor arrays
Authors: Fisher Allan L. , Kung H. T.
Published: November 2005

Highly parallel VLSI computing structures consist of many processing elements operating simultaneously. In order for such processing elements to communicate among themselves, some provision must be made for synchronization of data transfer. The simplest means of synchronization is the use of a global clock. Unfortunately, large clocked systems can be difficult to implement because of the inevitable problem of clock skews and delays, which can be especially acute in VLSI systems as feature sizes shrink. For the near term, good engineering and technology improvements can be expected to maintain the feasibility of clocking in such systems; however, clock distribution problems crop up in any technology as systems grow. An alternative means of enforcing necessary synchronization is the use of self-timed, asynchronous schemes, at the cost of increased design complexity and hardware cost. Realizing that different circumstances call for different synchronization methods, this paper provides a spectrum of synchronization models; based on the assumptions made for each model, theoretical lower bounds on clock skew are derived, and appropriate or best-possible synchronization schemes for large processor arrays are proposed.

One set of models is based on assumptions that allow the use of a pipelined clocking scheme, where more than one clock event is propagated at a time. In this case, it is shown that even assuming that physical variations along clock lines can produce skews between wires of the
same
length, any one-dimensional processor array can be correctly synchronized by a global pipelined clock while enjoying desirable properties such as modularity, expandability and robustness. This result cannot be extended to two-dimensional arrays, however—the paper shows that under this assumption, it is impossible to run a clock such that the maximum clock skew between two communicating cells will be bounded by a constant as systems grow. For such cases or where pipelined clocking is unworkable, a synchronization scheme incorporating both clocked and “asynchronous” elements is proposed.
The Boolean Vector Machine [BVM]
Authors: Wagner Robert A.
Published: November 2005

We describe the architecture of a class of machines intended to solve computationally intensive problems much faster than can today's machines, at no increase in cost.

We have investigated the programming of the BVM for several interesting algorithms on a BVM of 2
k
bit positions per register. More theoretical study of implementations of such highly parallel algorithms is motivated.
A VLSI tree machine for relational data bases
Authors: Bonuccelli M. A. , Lodi E. , Luccio F. , Maestrini P. , Pagli L.
Published: November 2005

A VLSI chip for performing relational data base operations is proposed. The chip is a tree of processors (TOP), where each chip has elementary storage and processing capabilities. A relation will be stored in the lowest levels of a TOP. More precisely, every m-tuple will occupy a subtree whose root is s= [log
2
(m+1)] =1 levels above the leaves. Denoting by h the height of the tree, the upper h-s levels will be used for routing and bookkeeping purposes. A number of basic operations such as allocate and deallocate subtrees, insert and compare m-tuples etc., are defined for the TOP's. Relational operations are effectively performed as simple combinations of basic operations. The architecture of a data base machine based on TOP's is also sketched. Such a machine is feasible with the current VLSI technology and could become attractive in few years if density and performance of VLSI keep improving at the current rate.
Architecture of a VLSI instruction cache for a RISC
Authors: Patterson David A. , Garrison Phil , Hill Mark , Lioupis Dimitris , Nyberg Chris , Sippel Tim , Dyke Korbin Van
Published: November 2005

A cache was first used in a commercial computer in 1968,
1
and researchers have spent the last 15 years analyzing caches and suggesting improvements. In designing a VLSI instruction cache for a RISC microprocessor we have uncovered four ideas potentially applicable to other VLSI machines. These ideas provide expansible cache memory, increased cache speed, reduced program code size, and decreased manufacturing costs. These improvements blur the habitual distinction between an instruction cache and an instruction fetch unit.

The next four sections present the four architectural ideas, followed by a section on performance evaluation of each idea. We then describe the implementation of the cache and finally summarize the results.
Performance of shared cache for parallel-pipelined computer systems
Authors: Yeh Phil C. C. , Patel Janak H. , Davidson Edward S.
Published: November 2005

Shared-cache memory organizations for parallel-pipelined multiple instruction stream processors avoid the cache coherence problem of private caches by sharing single copies of common blocks. A shared cache may have a higher hit ratio, but suffers performance degradation due to access conflicts.

Effective shared cache organizations are proposed which retain the cache coherency advantage and which have very low access conflict even with very high request rates. Analytic expressions for performance based on a Markov model have been found for several important cases. Performance of shared cache organizations and design tradeoffs are discussed.
Using cache memory to reduce processor-memory traffic
Authors: Goodman James R.
Published: November 2005

The importance of reducing processor-memory bandwidth is recognized in two distinct situations: single board computer systems and microprocessors of the future. Cache memory is investigated as a way to reduce the memory-processor traffic. We show that traditional caches which depend heavily on spatial locality (look-ahead) for their performance are inappropriate in these environments because they generate large bursts of bus traffic. A cache exploiting primarily temporal locality (look-behind) is then proposed and demonstrated to be effective in an environment where process switches are infrequent. We argue that such an environment is possible if the traffic to backing store is small enough that many processors can share a common memory and if the cache data consistency problem is solved. We demonstrate that such a cache can indeed reduce traffic to memory greatly, and introduce an elegant solution to the cache coherency problem.
A study of instruction cache organizations and replacement policies
Authors: Smith James E. , Goodman James R.
Published: November 2005

Instruction caches are analyzed both theoretically and experimentally. The theoretical analysis begins with a new model for cache referencing behavior—the loop model. This model is used to study cache organizations and replacement policies. It is concluded theoretically that random replacement is better than LRU and FIFO, and that under certain circumstances, a direct-mapped or set associative cache may perform better than a full associative cache organization. Experimental results using instruction trace data are then given. The experimental results are shown to support the theoretical conclusions.
Very Long Instruction Word architectures and the ELI-512
Authors: Fisher Joseph A.
Published: November 2005

By compiling ordinary scientific applications programs with a radical technique called trace scheduling, we are generating code for a parallel machine that will run these programs faster than an equivalent sequential machine—we expect 10 to 30 times faster.

Trace scheduling generates code for machines called Very Long Instruction Word architectures. In Very Long Instruction Word machines, many statically scheduled, tightly coupled, fine-grained operations execute in parallel within a single instruction stream. VLIWs are more parallel extensions of several current architectures.

These current architectures have never cracked a fundamental barrier. The speedup they get from parallelism is never more than a factor of 2 to 3. Not that we couldn't build more parallel machines of this type; but until trace scheduling we didn't know how to generate code for them. Trace scheduling finds sufficient parallelism in ordinary code to justify thinking about a highly parallel VLIW.

At Yale we are actually building one. Our machine, the ELI-512, has a horizontal instruction word of over 500 bits and will do 10 to 30 RISC-level operations per cycle [Patterson 82]. ELI stands for Enormously Longword Instructions; 512 is the size of the instruction word we hope to achieve. (The current design has a 1200-bit instruction word.)

Once it became clear that we could actually compile code for a VLIW machine, some new questions appeared, and answers are presented in this paper. How do we put enough tests in each cycle without making the machine too big? How do we put enough memory references in each cycle without making the machine too slow?
Combining tags with error codes
Authors: Gumpertz Richard H.
Published: November 2005

Many computer systems include extra bits in each word of storage to allow detection (and possibly correction) of memory failures. These same bits can be used to implement tag-checking without sacrificing their normal error-handling properties. The tagging facility so provided can be used to detect a variety of hardware and software errors that might otherwise go undetected. Because no extra storage is required, the cost of adding such tagging can be small even though the benefit derived can be large.
Fault diagnosis of bit-slice processor
Authors: Park Young Gil , Cho Jung Wan
Published: November 2005

This paper proposes a microdiagnostic procedure for efficient fault diagnosis of bit-slice processors that are formed by an array of identical bit-slice processors. A test generation procedure for testing the entire array simultaneously instead of testing single slice, one after another, is presented, which is based on the high functional fault model and restricted multiple slice fault assumption within an array. Fault detection and fault location procedures using the generated test sequence are also presented.

Using these procedures, a test microprogram and diagnostic system for the bit-sliced processor constructed by the array of four Am 2901 bit-slices are developed.
Line digraph iterations and the (d,k) problem for directed graphs
Authors: Fiol M. A. , Alegre I. , Yebra J. L.A.
Published: November 2005

We consider in this paper the (d,k) problem for directed graphs: to maximize the number of vertices in a digraph of degree d and diameter k. For any values of d and k, we construct a graph with a number of vertices larger than (d
2
-1)/d
2
times the (non-attainable) Moore bound. In particular, this solves the (d,k) digraph problem for k=2. We also show that these graphs can be obtained as line digraph iterations and that this technique provides us with a simple local routing algorithm for the corresponding networks.
Uniform theory of the shuffle-exchange type permutation networks
Authors: Soviš František
Published: November 2005

This paper presents the uniform theory for describing of the shuffle-exchange type permutation networks - the theory of E
k
stages. The use of this new approach is demonstrated by applying it to the flip, omega, and other incomplete permutation networks and to some complete networks /e.g. the Beneš network/ as well. Especially the paper deals with the p, 2p, and /2p=1/-stage networks, where p = log
2
n and n is number of the inputs /or outputs/ of these networks.
Analysis of Cray-1S architecture
Authors: Srini Vason P. , Asenjo Jorge F.
Published: November 2005

An analysis of the Cray-1S architecture based on dataflow graphs is presented. The approach consists of representing the components of a Cray-1S system as the nodes of a dataflow graph and the interconnections between the components as the arcs of the dataflow graph. The elapsed time and the resources used in a component are represented by the attributes of the node corresponding to the component. The resulting dataflow graph model is simulated to obtain timing statistics using as input a control stream that represents the instruction and data stream of the real computer system.

The Cray-1S architecture is analyzed by conducting several experiments with the model. It is observed that the architecture is a well balanced one and performance improvements are hard to achieve without major changes. Significant improvement in performance is shown when parallel instruction issue is allowed with multiple CIP/LIPs in the architecture.
Performance measurements on HEP - a pipelined MIMD computer
Authors: Jordan Harry F.
Published: November 2005

A pipelined implementation of MIMD operation is embodied in the HEP computer. This architectural concept should be carefully evaluated now that such a computer is available commercially. This paper studies the degree of utilization of pipelines in the MIMD environment. A detailed analysis of two extreme cases indicates that pipeline utilization is quite high.

Although no direct comparisons are made with other computers, the low pipeline idle time in this machine indicates that this architectural technique may be more beneficial in an MIMD machine than in either SISD or SIMD machines.
(SM)
2
-Sparse Matrix Solving Machine
Authors: Amano Hideharu , Yoshida Takaichi , Aiso Hideo
Published: November 2005

In analyzing electronic circuits, it is usually necessary to solve simultaneous linear equations which provide with a sparse coefficient matrix. In order to treat these problems effectively, we propose a dedicated parallel machine called 'Sparse Matrix Solving Machine', or (SM)
2
for short.

(SM)
2
is composed of multiple clusters, each consisting of multiple processing units (PUs) attached to a sophisticated shared memory which enables any PUs to read data from memory simultaneously without conflict. The structure of the cluster is organized so as to make the best use of the neighboring effects involved in the problems.

In this paper, the characteristics of the problems to be solved and the behavior of the PUs will be discussed, and the optimum system configuration for (SM)
2
will be shown and its effectiveness will be justified through behavior analysis and simulations.
Execution control and memory management of a Data Flow Signal Processor
Authors: Kronlöf Klaus
Published: November 2005

The architecture of the Data Flow Signal Processor (DFSP) is discussed with the emphasis on its control mechanism. It is argued that the data flow principle can be efficiently applied to block processing operations of nonrecursive DSP computations, when shared data structures are avoided. Simulation results involving the optimal operand size and the memory use of the control section are presented. Due to the expandability and convenient programmability of the DFSP architecture, the range of its potential applications extends beyond signal processing as demonstrated by a DFSP based database machine.
DDDP-a Distributed Data Driven Processor
Authors: Kishi Masasuke , Yasuhara Hiroshi , Kawamura Yasusuke
Published: November 2005

This paper describes an architecture of a data flow computer named the Distributed Data Driven Processor (DDDP), and presents an experimental system and the results of experiments using several benchmarks. The experimental system has four processing elements connected by a ring bus, and a structured data memory. The main features of our system are that each processing element is provided with a hardware hashing mechanism to implement token coloring, and a ring bus is used to pass tokens concurrently among processing elements. A hardware monitor was used to measure the performance of the experimental system.

The experimental system adopts a low key technology and yet is capable of executing about 0.7 million instructions per second through the benchmarks. This implies that data flow computers can be alternative to the conventional von-Neumann computers if state-of-the-art technologies are adequately introduced.