Variations on UNIX for parallel-processing computers
Porting a familiar UNIX environment to today's parallel-processing computers is challenging, but options abound.
Architecture and Hardware
Advertisement
Economies of scale in computing: Grosch’s law revisited
Does Grosch's law apply in the 1980s? A look at the price and performance of computer systems concludes that there are no economies of scale in computing. Computer technology is characterized by constant returns to scale, a fact that has important implications on future centralization/decentralization decisions.
A plausibility-driven approach to computer architecture design
A dilemma skirting the discipline of computer architecture concerns the plausibility of architectural designs. To counter the widely held perception that architecture is a nebulous entity is a proposal to view such designs as specifications of constraints to be satisfied.
Designing large real-time systems with Ada
The programming language Ada encourages improved methods for the design of real-time systems.
Recently developed word processing software can correctly format the cursive, interacting letters of the Arabic script. Moreover, new layout procedures can automatically intermix right-to-left Arabic writing with left-to-right text in European or other languages.
Adjacency detection using quadcodes
A method is presented for determining whether two given regions are adjacent, and for finding all the neighbors of different sizes for a given region. Regions are defined as elementary squares of any size. In a companion paper [2], we introduce the quadcode and discuss its use in representing geometric concepts in the coded image, such as location, distance, and adjacency. In this paper we give a further discussion of adjacency in terms of quadcodes. Gargantini [1] discussed adjacency detection using linear quadtrees. Her discussion was applied to pixels, and a procedure was given to find a pixel's southern neighbor only. This paper considers elementary squares of any size, and gives procedures for both aspects of the problem: for determining whether two given regions are adjacent, and for finding all the neighbors of different sizes for a given region.
The quadcode and its arithmetic
The quadcode is a hierarchical data structure for describing digital images. It has the following properties: (1) straightforward representation of dimension, size, and the relationship between an image and its subsets; (2) explicit description of geometric properties, such as location, distance, and adjacency; and (3) ease of conversion from and to raster representation. The quadcode has applications to computer graphics and image processing because of its ability to focus on selected subsets of the data and to allow utilization of multiple resolutions in different parts of the image. A related approach is the quadtree. Samet recently presented a thorough survey of the literature in that field [7]. Gargantini [2] and Abel and Smith [1] presented linear quadtrees and linear locational keys that are efficient labeling techniques for quadtrees. In those papers the geometric concepts of the image are discussed by using the tree as an interpretive medium, and the approaches and procedures are based on traversal of the nodes in the tree. In this paper we present the quadcode system, which is a direct description of the image, and discuss the geometric concepts in terms of the coded images themselves.
Spanish is a language with very precise and regular orthographic rules. A syllabication algorithm strictly based on syntactic analysis, not requiring any semantic knowledge, is presented and further extended to include hyphenation. Algorithms are presented as pattern matching schemata, and efficient implementations are considered.
The tea-leaf reader algorithm: an efficient implementation of CRC-16 and CRC-32
The tea-leaf reader CRC algorithms are error-detection algorithms that use a look-ahead table to increase execution speed.
An analysis of variance (ANOVA) model is developed for determining the existence of significant differences among strategies employing heuristics. Use of the model is illustrated in an application involving capacity assignment for networks utilizing the dynamic hierarchy architecture, in which the apex node is reassigned in response to changing environments. The importance of the model lies in the structure provided to the evaluation of heuristics, a major need in the assessment of benefits of artificial-intelligence applications. A nested three-factor design with fixed and random effects provides a numerical example of the model.
Distribution of mathematical software via electronic mail
A large collection of public-domain mathematical software is now available via electronic mail. Messages sent to "netlib@anl-mcs" (on the Arpanet/CSNET) or to "research!netlib" (on the UNIX® network) wake up a server that distributes items from the collection. The one-line message "send index" causes a library catalog to be sent by return mail.
Case study: IBM’s system/360-370 architecture
The architecture of IBM's System/360-370 series of compatible processors is one of the most durable artifacts of the computer age. Through two major revisions of the product line and 23 years of technological change, it has remained a viable and versatile interface between machine and user.
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.
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.
The ACM SIGOPS Workshop on Accommodating Heterogeneity was conducted in December 1985 in Eastbound, Wash., as a forum for an international group of fifty researchers to discuss the technical issues surrounding heterogeneous computing environments.
COBOL on a PC: a new perspective on a language and its performance
A comparison of Cobol performance on the PC AT Enhanced versus an IBM 370 mainframe suggests that high-quality PC compiler implementations—combined with the new language features of the Cobol 85 Standard—are improving the PC environment for Cobol to the point where serious applications can now be developed and debugged on the PC, either to be run on the PC itself, or for eventual uploading to a mainframe.
A relational information resource dictionary system
A relational implementation of IRDS using SQL demonstrates how the flexibility of the relational environment enhances the extensibility of the IRDS while at the same time providing more powerful dictionary capabilities than are typically found in relational systems.
Contention is no obstacle to shared-memory multiprocessing
Contention in large-scale shared-memory systems is less of a concern than generally believed. Through careful engineering of a parallel system, the effects of contention can be controlled.
The intensive use of memory to recall specific episodes from the past—rather than rules—should be the foundation of machine reasoning.
Parallel free-text search on the connection machine system
A new implementation of free-text search using a new parallel computer—the Connection Machine®—makes possible the application of exhaustive methods not previously feasible for large databases.
Advanced compiler optimizations for supercomputers
Compilers for vector or multiprocessor computers must have certain optimization features to successfully generate parallel code.
Parallel computers with tens of thousands of processors are typically programmed in a data parallel style, as opposed to the control parallel style used in multiprocessing. The success of data parallel algorithms—even on problems that at first glance seem inherently serial—suggests that this style of programming has much wider applicability than was previously thought.
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