Error detecting decimal digits
Decimal-oriented error detection schemes are explored in the context of one particular company project.
Architecture and Hardware
Advertisement
Efficient distributed event-driven simulations of multiple-loop networks
Simulating asynchronous multiple-loop networks is commonly considered a difficult task for parallel programming. Two examples of asynchronous multiple-loop networks are presented in this article: a stylized queuing system and an Ising model. In both cases, the network is an n × n grid on a torus and includes at least an order of n2 feedback loops. A new distributed simulation algorithm is demonstrated on these two examples. The algorithm combines three elements: (1) the bounded lag restriction; (2) minimum propagation delays; and (3) the so-called opaque periods. We prove that if N processing elements (PEs) execute the algorithm in parallel and the simulated system exhibits sufficient density of events, then, on average, processing one event would require O(log N) instructions of one PE. Experiments on a shared memory MIMD bus computer (Sequent's Balance) and on a SIMD computer (Connection Machine) show speed-ups greater than 16 on 25 PEs of a Balance and greater than1900 on 214 PEs of a Connection Machine.
A model for predicting and evaluating computer resource consumption
Evaluation and prediction of computer resource consumption can aid in the determination of computer selection and configuration planning as well as in the usefulness and maintenance of existing systems. The model presented can be used in a "What If" mode to make these determinations.
The number of buffers required for sequential processing of a disk file
The number of buffers required for sequential processing of disk files is investigated with the assumption that there is a single user served by two processors: one reads blocks from the disk into buffers in main memory, while the other processor processes the buffers. If processing is faster than reading, then two buffers suffice. However, if processing is slower, using only two buffers does not guarantee minimum completion time. The minimal required number of buffers is calculated in this article.
A subset coloring algorithm and its applications to computer graphics
We consider the following problem: we are given a diagram made up of intersecting circles, where each region is colored either black or white. We wish to display this diagram on a bitmap device, where we are allowed to (i) paint a given circle white and (ii) invert the colors within a given circle, changing white to black and vice versa. (These operations are frequently provided in graphics hardware or software.) We ask: using only these paint and invert operations, is it possible to draw the diagram? A generalization of this problem leads to an analogous coloring problem on a subset of the power set of n elements. We give a polynomial-time algorithm that answers the question above, and produces a "short" sequence of instructions to draw the diagram, if one exists. A simple modification of the algorithm permits us to handle the case where there are more colors than just black and white, and the colors are represented by bit strings. This corresponds to the conventions frequently used with color raster devices.
Characterizing computer performance with a single number
The controversy surrounding single number performance reduction is examined and solutions are suggested through a comparison of measures.
Benchmarks for LAN performance evaluation
A technique for quickly benchmarking the performance of local area networks (LANs) is presented. Programs which model both intermittent and constant network activity are given.
Computation of cyclic redundancy checks via table look-up
Cyclic Redundancy Check (CRC) codes provide a simple yet powerful method of error detection during digital data transmission. Use of a table look-up in computing the CRC bits will efficiently implement these codes in software.
HAM: a general purpose hypertext abstract machine
The HAM is a transaction-based server for a hyper text storage system. The server is designed to handle multiple users in a networked environment. The storage system consists of a collection of contexts, nodes, links, and attributes that make up a hypertext graph. The versatility of the HAM can be illustrated by showing how Guide buttons, intermedia webs, and NoteCard FileBoxes can be implemented using its storage model.
Self-timing programs and the quantum scheduler
Using an internally generated program clock in conjunction with a quantum scheduler creates self-timing programs that are useful in building deterministic computer systems.
The higraph, a general kind of diagramming object, forms a visual formalism of topological nature. Higraphs are suited for a wide array of applications to databases, knowledge representation, and, most notably, the behavioral specification of complex concurrent systems using the higraph-based language of statecharts.
An astronomer-turned-sleuth traces a German trespasser on our military networks, who slipped through operating system security holes and browsed through sensitive databases. Was it espionage?
Distributed programming in Argus
Argus—a programming language and system developed to support the implementation and execution of distributed programs—provides mechanisms that help programmers cope with the special problems that arise in distributed programs, such as network partitions and crashes of remote nodes.
The V distributed System was developed at Stanford University as part of a research project to explore issues in distributed systems. Aspects of the design suggest important directions for the design of future operating systems and communication systems.
Interconnecting heterogeneous computer systems
A software structure created by the Heterogeneous Computer Systems (HCS) Project at the University of Washington was designed to address the problems of heterogeneity that typically arise in research computing environments.
Self-assessment procedure XVIII: fundamentals of data communications
A self-assessment procedure dealing with the fundamentals of data communications
The Cedar File System (CFS) is a workstation file system that provides access to both a workstation's local disk and to remote file servers via a single hierarchical name space. CFS supports a group of cooperating programmers by allowing them to both manage local naming environments and to share consistent versions of collections of software.
On synchronization in hard-real-time systems
The design of software for hard-real-time systems is usually difficult to change because of the constraints imposed by the need to meet absolute real-time deadlines on processors with limited capacity. Nevertheless, a new approach involving a trio of ideas appears to be helpful for those who build software for such complex applications.
Pattern formation and chaos in networks
Chaos theory involves the study of how complicated behavior can arise in systems that are based on simple rules, and how minute changes in the input of a system can lead to great differences in the output. Using computer graphics, the dynamic behavior of chaos-producing networks is explored, and convergence maps reveal a visually striking and intricate class of displayable objects.
Ray tracing Jell-O brand gelatin
New technology is presented for imaging a restricted class of dessert foods.
A comparison of recently proposed parallel text search methods to alternative available search strategies that use serial processing machines suggests parallel methods do not provide large-scale gains in either retrieval effectiveness or efficiency.
Central-processing-unit schedulers have traditionally allocated resources fairly among processes. By contrast, a fair Share scheduler allocates resources so that users get their fair machine share over a long period.
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