Search
Join ACM

Architecture and Hardware

Advertisement

Research and Advances Sep 1 1983

The fifth generation project — a trip report

As part of Japan's effort to become a leader in the computer industry, the Institute for New Generation Computer Technology has launched a revolutionary ten-year plan for the development of large computer systems which will be applicable to knowledge information processing systems. These Fifth Generation computers will be built around the concepts of logic programming. In order to refute the accusation that Japan exploits knowledge from abroad without contributing any of its own, this project will stimulate original research and will make its results available to the international research community.
Research and Advances Aug 1 1983

An overview of the proposed american national standard for local distributed data interfaces

The Local Distributed Data Interface (LDDI) Project of X3 Technical Committee X3T9 has resulted in three draft proposed American National Standards for a high performance local area network. The proposed standards are organized in accordance with the ISO Reference Model for Open Systems Interconnection and encompass the lowest two protocol layers (data link and physical) of the model, plus a serial broadband coaxial bus interface. The intended application of the LDDI is as a backend network for the interconnection of high performance CPUs and block transfer peripherals such as magnetic disk and tapes. A carrier-sense multiple access with collision prevention (CSMA-CP) distributed bus arbitration protocol is employed. The cable interface supports the attachment of up to 28 ports over a cable distance of 0.5 km (8 ports may be attached to a 1 km cable) at a transfer rate of 50 Mbit/s.
Research and Advances Jul 1 1983

Precision averaging for real-time analysis

An analysis of the computation of the arithmetic mean using only single-precision fixed-point arithmetic is presented. This is done to ease the timing constraints common to many on-line applications. Others have introduced several averaging algorithms in floating-point arithmetic for use in inferential statistics. In this paper, these algorithms are evaluated with respect to their feasibility as fixed-point methods in the context of real-time analysis. Modifications of these algorithms are presented, and previously unpublished ones are introduced in the interest of avoiding overflow (necessary) and minimizing truncation errors (highly desirable). All algorithms presented are tested for speed and accuracy on several sets of data, including their own “worst case.” The applicability of each algorithm is discussed with respect to some of the basic functions that real-time programs must perform.
and
Research and Advances Jun 1 1983

A real-time garbage collector based on the lifetimes of objects

In previous heap storage systems, the cost of creating objects and garbage collection is independent of the lifetime of the object. Since objects with short lifetimes account for a large portion of storage use, it is worth optimizing a garbage collector to reclaim storage for these objects more quickly. The garbage collector should spend proportionately less effort reclaiming objects with longer lifetimes. We present a garbage collection algorithm that (1) makes storage for short-lived objects cheaper than storage for long-lived objects, (2) that operates in real time—object creation and access times are bounded, (3) increases locality of reference, for better virtual memory performance, (4) works well with multiple processors and a large address space.
and
Research and Advances Mar 1 1983

Speeding up an overrelaxation method of division in Radix-2n machine

For normalized floating point division, digital computers can take advantage of a division process that uses an iterative multiplying operation instead of repeated subtractions. An improvement of this division process by using accelerating constants in the overrelaxation has previously been proposed. Multiplication by a chosen accelerating constant accelerates the process of generating accurate digits of a quotient in division. We propose a further improvement by generalizing the accelerating constants in the overrelaxation method. Two benefits resulting from this improvement promise to yield faster division in digital computers.
and
Research and Advances Mar 1 1983

A tree convolution algorithm for the solution of queueing networks

A new algorithm called the tree convolution algorithm, for the computation of normalization constants and performance measures of product-form queueing networks, is presented. Compared to existing algorithms, the algorithm is very efficient in the solution of networks with many service centers and many sparse routing chains. (A network is said to have sparse routing chains if the chains visit, on the average, only a small fraction of all centers in the network.) In such a network, substantial time and space savings can be achieved by exploiting the network's routing information. The time and space reductions are made possible by two features of the algorithm: (1) the sequence of array convolutions to compute a normalization constant is determined according to the traversal of a tree; (2) the convolutions are performed between arrays that are smaller than arrays used by existing algorithms. The routing information of a given network is used to configure the tree to reduce the algorithm's time and space requirements; some effective heuristics for optimization are described. An exact solution of a communication network model with 64 queues and 32 routing chains is illustrated.
and
Research and Advances Feb 1 1983

The computational metaphor and quantum physics

Concurrent computational systems, viewed as sets of cooperating processes, are shown to have close analogies in the world of quantum physics. In particular, analogies exist between processes and particles, between a process' state and a particle's mass, between a process'state changes and a particle's velocity, and between interprocess communications and particle interactions. This view allows the application in the computational world of special relativity theory, the uncertainty principle, the law of conservation of momentum, and many of particle physics' fundamental results. This paper describes the basic analogy and some fundamental results. It is the authors' belief that new insights into a computational processes will be gained as the analogy is developed and vice versa. It is conceivable that established results of the computational sciences may contribute to a new understanding of some of the problems of physics. Other process-oriented sciences, such as biology, economics, and psychology, could also benefit from such development.
and
Research and Advances Nov 1 1982

HISDL—a structure description language

The features of a language designed for the description of the structure of computer systems are described. The structure of a system is specified hierarchically as an interconnection of components with each component being a named instance of a component type. The system itself is another component type. The interconnection between components is specified in two ways: either by specifying all the ports that are connected together, or by specifying a component and the ports that are connected to its ports. A structure specification is a list of such connection specifications. The language has an iterative construct for specifying highly regular structures, and a conditional construct is also provided. A component type can be recursively specified while parameterization of component type specifications is supported. The latter is particularly useful for specifying classes of components of similar structure.
Research and Advances Nov 1 1982

MINI-EXEC: a portable executive for 8-bit microcomputers

As microprocessor systems and single-chip microcomputers become more complex, so do the software systems developed for them. In many cases, software is being designed that incorporates multiple control functions running asynchronously on a single microprocessor. Here, discussion focuses on the motivation for running such multiple functions under the control of a real-time multitasking executive. A successfully implemented executive whose design is portable and suitable for use on most 8-bit microprocessors is presented.
Opinion Sep 1 1982

Letters to the editor: A protection model and its implementation in a dataflow system

A protection model is presented for a general purpose computing system based on tags attached as seals and signatures to values exchanged among processes. A tag attached to a value as a seal does not prevent that value from being propagated to any place within the system; rather, it guarantees that the value and any information derived from it cannot leave the system unless a matching tag is presented. A tag attached to a value as a signature is used by a process to verify the origin of the received data. Solutions to problems from the areas of interprocess communication and proprietary services are given.
Research and Advances Sep 1 1982

Efficient parallel algorithms for some graph problems

We study parallel algorithms for a number of graph problems, using the Single Instruction Stream-Multiple Data Stream model. We assume that the processors have access to a common memory and that no memory or data alignment time penalties are incurred. We derive a general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph. In particular, an O(log2 n) time bound can be achieved using only K = n⌈n/log2 n⌉ processors. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.
, , and
Research and Advances May 1 1982

On an improved algorithm for decentralized extrema finding in circular configurations of processors

This note presents a more efficient algorithm for finding the largest element in a circular list of processors when messages can be passed in either direction. It passes 2N*floor(lg N) + 3N messages in the worst case, compared to Chang and Roberts' N(N + 1)/2 and Hirschberg and Sinclair's 8N + 8*ceiling(N lg N) messages. The technique is a selective elimination of possible processes, which then merely relay future messages between the remaining contenders.
Research and Advances Apr 1 1982

Grapevine: an exercise in distributed computing

Grapevine is a multicomputer system on the Xerox research internet. It provides facilities for the delivery of digital messages such as computer mail; for naming people, machines, and services; for authenticating people and machines; and for locating services on the internet. This paper has two goals: to describe the system itself and to serve as a case study of a real application of distributed computing. Part I describes the set of services provided by Grapevine and how its data and function are divided among computers on the internet. Part II presents in more detail selected aspects of Grapevine that illustrate novel facilities or implementation techniques, or that provide insight into the structure of a distributed system. Part III summarizes the current state of the system and the lesson learned from it so far.
, , , and
Research and Advances Apr 1 1982

Performing remote operations efficiently on a local computer network

A communication model is described that can serve as a basis for a highly efficient communication subsystem for local networks. The model contains a taxonomy of communication instructions that can be implemented efficiently and can be a good basis for interprocessor communication. These communication instructions, called remote references, cause an operation to be performed by a remote process and, optionally, cause a value to be returned. This paper also presents implementation considerations for a communication system based upon the model and describes an experimental communication subsystem that provides one class of remote references. These remote references take about 150 microseconds or 50 average instruction times to perform on Xerox Alto computers connected by a 2.94 megabit Ethernet.
Research and Advances Apr 1 1982

A technique for testing command and control software

A technique for testing embedded-microprocessor command and control programs is described. The continuity inherent in functions computed by programs which monitor natural phenomena is exploited by a simple difference equation-based algorithm to predict a program's next output from its preceding ones. The predicted output is compared with the actual output while indexing through the program's domain. Outputs which cannot be predicted are flagged as potential errors. Data are presented which show that this technique can be a sensitive measure of a program's correctness.
Research and Advances Mar 1 1982

The “worm” programs—early experience with a distributed computation

The “worm” programs were an experiment in the development of distributed computations: programs that span machine boundaries and also replicate themselves in idle machines. A “worm” is composed of multiple “segments,” each running on a different machine. The underlying worm maintenance mechanisms are responsible for maintaining the worm—finding free machines when needed and replicating the program for each additional segment. These techniques were successfully used to support several real applications, ranging from a simple multimachine test program to a more sophisticated real-time animation system harnessing multiple machines.
and
Research and Advances Nov 1 1981

Authentication of signatures using public key encryption

One of Needham and Schroeder's proposed signature authentication protocols is shown to fail when there is a possibility of compromised keys: this invalidates one of the applications of their technique. A more elaborate mechanism is proposed which does not require a network clock, but does require a third party to the transaction. The latter approach is shown to be reliable in a fairly strong sense.
Research and Advances Nov 1 1981

The evolution of user behavior in a computerized conferencing system

Data from 18-month operational trials of the EIES system indicate that the range of features considered valuable in a computer-based communication system increases with the amount of experience gained by using this medium of communication. Simple message systems alone are not likely to satisfy the communications needs of long term, regular users of computerized communications systems. Among the capabilities which long term, regular users find valuable are group conferences, notebooks for text composition, and self-defined commands.
and
Research and Advances Sep 1 1981

Comparison of synonym handling and bucket organization methods

A theoretical description of the access times required in open addressing and external chaining is given. Values are calculated for different record and bucket sizes and load factors, and the corresponding values for the two methods are compared. Practical guidelines for determining bucket sizes and load factors are presented. It is proved that open addressing is almost always superior to external chaining and the optimal bucket size is between 1 and 4.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More