Architecture and Hardware
Advertisement
The coordinated use of five performance evaluation methodologies
Information system design can be influenced and ultimate performance parameters accurately forecast through the coordinated use of five performance analysis tools. The complementary methodology is used to first predict and then validate system performance throughout its life cycle.
The computer science research network CSNET: a history and status report
In 1981, the National Science Foundation started a five-year project totaling nearly $5 million to construct a computer science research network, CSNET, connecting all groups engaged in computer science research. For an NSF division with an annual budget of $25 million, the award represents an unusual commitment to a single project; only a handful of such large awards have been made. What is CSNET? Why is it receiving such attention? How will it benefit the community? When will it be completed? Who are the architects and implementors?
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.
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.
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.
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.
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.
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.
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.
Distributed computation on graphs: shortest path algorithms
We use the paradigm of diffusing computation, introduced by Dijkstra and Scholten, to solve a class of graph problems. We present a detailed solution to the problem of computing shortest paths from a single vertex to all other vertices, in the presence of negative cycles.
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.
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.
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.
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.
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 InvolvedCommunications 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