Search
Join ACM

Systems and Networking

Advertisement

Research and Advances Apr 1 1987

Attributes of the performance of central processing units: a relative performance prediction model

Using readily available data on CPU characteristics—main memory size, cache memory size, number of channels, and machine cycle time—it is possible to predict relative CPU performance for a wide range of machines. Statistical analyses indicate that these characteristics explain virtually all the variance in relative performance.
and
Research and Advances Apr 1 1987

Computing multi-colored polygonal masks in pipeline architecture and its application to automated visual inspection

New techniques for computing multicolored polygonal masks for image analysis and computer vision applications are presented. The procedures do not require random access of the image memory. They are based on efficient generation of coordinate-reference images (ramps) and other simple general purpose architectural features such as look-up tables. The techniques presented are, unlike their predecessors, highly parallel and can be efficiently implemented in existing pipeline image processors. In addition, we show an architecture in the form of functional building blocks that will enable us to compute polygonal and other masks much faster than commercially available pipeline systems. Extensive motivation and use of the new algorithms for digital visual inspection applications are given throughout.
, , and
Research and Advances Mar 1 1987

The effect of data structures on the logical complexity of programs

The logical complexity of a program is a measure of the effort required to understand it. We hypothesize that the logical complexity of a program increases with the increase in the opaqueness of the relationship between the physical data structures used in the program and their corresponding abstract data types. The results of an experiment conducted to investigate this hypothesis are reported. Documentation techniques for making programs easier to understand using complex data structures are discussed. Data structure diagrams, data structure invariants, stepwise transformation of data structures, and formal specification of the mapping between abstract and concrete data structures are illustrated using two nontrivial examples.
and
Research and Advances Mar 1 1987

Pairing heaps: experiments and analysis

The pairing heap has recently been introduced as a new data structure for priority queues. Pairing heaps are extremely simple to implement and seem to be very efficient in practice, but they are difficult to analyze theoretically, and open problems remain. It has been conjectured that they achieve the same amortized time bounds as Fibonacci heaps, namely, O(log n) time for delete and delete_min and O(1) for all other operations, where n is the size of the priority queue at the time of the operation. We provide empirical evidence that supports this conjecture. The most promising algorithm in our simulations is a new variant of the twopass method, called auxiliary twopass. We prove that, assuming no decrease_key operations are performed, it achieves the same amortized time bounds as Fibonacci heaps.
and
Research and Advances Mar 1 1987

An interview with the 1986 A. M. Turing Award recipients—John E. Hopcroft and Robert E. Tarjan

In the following interview, which took place at the 1986 Fall Joint Computer Conference in Dallas, Texas, John Hopcroft and Robert Tarjan discuss their collaboration and its influence on their separate research today. They also comment on supercomputing and parallelism, particularly with regard to statements by FJCC Keynote speakers Kenneth Wilson, Nobel laureate and director of Cornell University's Supercomputer Center, and C. Gordon Bell, chief architect on the team that designed DEC's VAX and now with the National Science Foundation. Finally the Turing Award winners air their views on the direction of computer science as a whole and on funding and the Strategic Defense Initiative.
Research and Advances Feb 1 1987

An improved parallel thinning algorithm

An iterative thinning algorithm reduces a two-dimensional pattern of strokes to its skeleton by removing layers of edge elements until each stroke has unit thickness. A parallel solution requires the independent calculation of new values for each iteration, using a window of nearest neighbors for each element. The traditional need for at least two subiterations can be avoided by modifying the window to permit the availability of intermediate calculations. Timings on an ICL DAP (an array processor) indicate an improvement of over 40 percent. Additional refinements are suggested to reduce noise in the final skeleton.
, , , and

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