Advertisement

Research and Advances

A field study of the software design process for large systems

The problems of designing large software systems were studied through interviewing personnel from 17 large projects. A layered behavioral model is used to analyze how three of these problems—the thin spread of application domain knowledge, fluctuating and conflicting requirements, and communication bottlenecks and breakdowns—affected software productivity and quality through their impact on cognitive, social, and organizational processes.
Research and Advances

Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation

The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap—a sequence of m decrease_key and n delete_min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case—O(1) time for decrease_key and O(log n) for delete_min. Relaxed heaps give a processor-efficient parallel implementation of Dijkstra's shortest path algorithm, and hence other algorithms in network optimization. A relaxed heap is a type of binomial queue that allows heap order to be violated.
Research and Advances

Ecological studies of professional programmers

For over two decades, software psychology researchers have been developing insights to software productivity and quality by investigating builders and users of software. This research has been diverse in both its approach and its impacts. It has introduced systematic behavioral measurement into the software development process and into research on new software techniques and technologies, and has also opened up new social and cognitive interpretations of software processes [5, 12]. We now see evidence of a new thrust in software psychology coming to the fore, one in which usability researchers are direct participants in the definition and creation of new software artifacts. We call this paradigm Ecological Design, to emphasize (1) that realistic software situations are being confronted on their own terms, and (2) that the work is directed toward design results, not merely toward evaluation and description in the service of design goals. The reorientation towards studying teamwork was prompted in 1971 by Weinberg and followed by a few researchers at that time, but the movement has accelerated with the recent and intense interest in computer supported collaborative work [15]. This was apparent in the papers presented at the two workshops on Empirical Studies of Programmers [10, 13]. An accompanying shift has also occurred in the software engineering community. The traditional waterfall model of software development with the precise specification of a provable topdown design is giving way to newer exploratory styles of program development that emphasize rapid prototyping and iterative refinement. The shift from product to process also puts greater emphasis on team organization, group processes, management policies, reusability, development tools, design methods, debugging strategies, and maintenance [6]. The three papers in this special section exemplify this new paradigm. Rosson, Maass, and Kellogg and Curtis, Krasner, and Iscoe describe highly qualitative studies of professional designers that produced specific technical proposals for improving software tools and the coordination of project management, an assessment of major bottlenecks, and a new framework for thinking about software design as a learning and communication process. Soloway, Pinto, Letovsky, Littman, and Lampert describe the design and exploration of software documentation that grew out of similarly qualitative studies of program maintenance. We caution that this research paradigm is still in its infancy: setting design requirements and developing prototypes are not traditional activities of psychological researchers. These roles are still emerging, still being reconciled with the earlier paradigms. The particular projects highlighted here are only the beginning; the field continues to evolve, as more researchers are attracted, as more topics are explored, as more methods are developed. Thus, despite the shortcomings of any particular project, the trajectory of this paradigm seems clear to us: it is the development of ideas that directly impact productivity and quality in software. Indeed, part of our intention in presenting this special section is to encourage more and more rapid development of the new paradigm.
Research and Advances

The designer as user: building requirements for design tools from design practice

Software tools that support the design and development of interactive computing systems are an exciting possibility. The potential pay-off is great: user interface management systems, for example, promise not only to speed the process of specifying, implementing and maintaining user interface code, but also to guide the content of the user interfaces they support. As for any tool intended for human use, however, the success of software design tools will hinge on a thorough understanding of the problems they seek to address—design as it is practiced in the real world.
Research and Advances

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

Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem

A new priority queue implementation for the future event set problem is described in this article. The new implementation is shown experimentally to be O(1) in queue size for the priority increment distributions recently considered by Jones in his review article. It displays hold times three times shorter than splay trees for a queue size of 10,000 events. The new implementation, called a calendar queue, is a very simple structure of the multiple list variety using a novel solution to the overflow problem.
Research and Advances

Probabilistic and genetic algorithms in document retrieval

Document retrieval systems are built to provide inquirers with computerized access to relevant documents. Such systems often miss many relevant documents while falsely identifying many non-relevant documents. Here, competing document descriptions are associated with a document and altered over time by a genetic algorithm according to the queries used and relevance judgments made during retrieval.
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.

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