Search
Join ACM

Computing Profession

Advertisement

Research and Advances

Improving locality of reference in a garbage-collecting memory management system

Modern Lisp systems make heavy use of a garbage-collecting style of memory management. Generally, the locality of reference in garbage-collected systems has been very poor. In virtual memory systems, this poor locality of reference generally causes a large amount of wasted time waiting on page faults or uses excessively large amounts of main memory. An adaptive memory management algorithm, described in this article, allows substantial improvement in locality of reference. Performance measurements indicate that page-wait time typically is reduced by a factor of four with constant memory size and disk technology. Alternately, the size of memory typically can be reduced by a factor of two with constant performance.
Research and Advances

The input/output complexity of sorting and related problems

We provide tight upper and lower bounds, up to a constant factor, for the number of inputs and outputs (I/OS) between internal memory and secondary storage required for five sorting-related problems: sorting, the fast Fourier transform (FFT), permutation networks, permuting, and matrix transposition. The bounds hold both in the worst case and in the average case, and in several situations the constant factors match. Secondary storage is modeled as a magnetic disk capable of transferring P blocks each containing B records in a single time unit; the records in each block must be input from or output to B contiguous locations on the disk. We give two optimal algorithms for the problems, which are variants of merge sorting and distribution sorting. In particular we show for P = 1 that the standard merge sorting algorithm is an optimal external sorting method, up to a constant factor in the number of I/Os. Our sorting algorithms use the same number of I/Os as does the permutation phase of key sorting, except when the internal memory size is extremely small, thus affirming the popular adage that key sorting is not faster. We also give a simpler and more direct derivation of Hong and Kung's lower bound for the FFT for the special case B = P = O(1).
, , and
Research and Advances

Program verification: the very idea

The notion of program verification appears to trade upon an equivocation. Algorithms, as logical structures, are appropriate subjects for deductive verification. Programs, as causal models of those structures, are not. The success of program verification as a generally applicable and completely reliable method for guaranteeing program performance is not even a theoretical possibility.
Research and Advances

The 1986-1987 Taulbee survey

The Computing Research Board's 1986-87 Taulbee Survey includes the latest statistics on production and employment of Ph.D.'s and faculty in computer science and engineering. For the first time, departments offering Ph.D.'s in computer engineering are also included.
and
Research and Advances

An empirical study of computer capacity planning in Japan

Capacity planners in Japan rely heavily on intuitive and judgmental approaches in their computer capacity planning functions, even more so than their U.S. counterparts, according to the following survey. The emphasis in large Japanese firms on job rotations, lifetime employment, and extensive social and informal interaction among employees helps contribute to the effectiveness of these judgmental methods.
Research and Advances

Computer science education in the People’s Republic of China in the late 1980s

Last year a delegation of international computer professionals with interests in computer science education participated in an information exchange with colleagues in the People's Republic of China. The delegation's experiences suggest that the Chinese have made substantial progress in some aspects of computer science education since late 1982, but that difficult problems remain to be solved.
Research and Advances

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.
, , and
Research and Advances

Abstraction mechanisms in hypertext

Abstraction is the means by which information can be stored and retrieved from an information structure at different levels of detail and from different perspectives. As such, abstraction mechanisms in hypertext are interesting to evaluate from a theoretical perspective as they become various first-order logic formulae.
and
Research and Advances

Graphics and managerial decision making: research-based guidelines

Graphical charts are generally thought to be a superior reporting technique compared to more traditional tabular representations in organizational decision making. The experimental literature, however, demonstrates only partial support for this hypothesis. To identify the characteristics of the situations that have been shown to benefit from the use of graphics, existing studies are reviewed in terms of the type of task used, the format employed, and the user experience. The examination of the literature reveals a set of empirically based—though preliminary—guidelines as to when and how to use business graphics.
and
Research and Advances

Tablet: personal computer of the year 2000

A design represents a compromise between conflicting goals, and the design of the personal computer of the year 2000 is no exception. We seek something that will fit comfortably into people's lives while dramatically changing them. This may appear to be a contradiction that cannot be reconciled. But if the technology does not fit easily into the habits and lifestyles of its human users, it will be discarded by those it was meant to help. And if this new tool does not change the life of its owner, it is only because we have been too shortsighted to imagine the possibilities. Our way out of this dilemma is to base the design upon something which is already integrated into everyone's life, to take a vital tool and give it more life. We have chosen to improve something that most people use everyday, the humble paper notebook. We have all heard the computer revolution was supposed to eliminate paper from the workplace. Instead, it has lead to desktop publishing; now we can not only write papers but typeset them ourselves. Paper notebooks have many properties that make them particularly friendly. They are light and portable. No one thinks twice about taking a pad anywhere. They are easy and natural to use, as accessible to the toddler as to the octogenarian and as relevant to the artist as the engineer. They can be used to communicate with other people. They are the ideal medium for integrating text and graphics, and perfect for creative doodling. Moreover, notebooks are forgiving of mistakes, simply peel off the page and start anew. It is natural to revise and edit written documents. There is something satisfying about crossing out an offending sentence from a written draft, a feeling that word processors have not captured. We aim for a computer that will provide all of these benefits and more. Thus, the personal computer of the year 2000 will be a portable machine the size of a notebook. We will write and draw with a stylus on a screen which mimics a physical writing surface. Enhancing this with the powers of computation and communication, we create a tool that will improve the way we live and work. This report provides a more concrete depiction of the machine we have in mind, namely TABLET.
Research and Advances

Introduction to special section on software testing

The field of software testing spans mathematical theory, the art and practice of validation, and methodology of software development. To cover this range would require a textbook (or several texts), not a trio of articles. But the work presented in this special section is a kind of "test set." Each paper is a significant contribution within one of the three broad areas. The reader must now make the assessment that is critical to any review of test points: are they representative? My own answer is 'no'; these articles are provocative and revealing rather than routine summaries. And perhaps that is what software testing is all about: good tests are the ones that provide new insights, not the ones that cover well worn ground.
Research and Advances

The category-partition method for specifying and generating fuctional tests

A method for creating functional test suites has been developed in which a test engineer analyzes the system specification, writes a series of formal test specifications, and then uses a generator tool to produce test descriptions from which test scripts are written. The advantages of this method are that the tester can easily modify the test specification when necessary, and can control the complexity and number of the tests by annotating the tests specification with constraints.
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