Search
Join ACM

Computing Applications

Advertisement

Research and Advances

A note on virtual memory indexes

In [4] Maruyama and Smith analyzed design alternatives for virtual memory indexes. The indexes investigated were those modeled on the structure of VSAM [5] which are closely related to B-trees [1]. Maruyama and Smith presented alternatives for search strategies, page format, and whether or not to compress keys. They made a comparative analysis based on the average cost of processing the index for retrieval of a key with its associated data pointer (or a sequence of keys and data pointers). The analysis showed that the optimal solution depends on machine and file characteristics and they provided formulas for selecting the best alternative. In this brief note1 we propose that another alternative for the page format be considered. The basic idea is to replace the sequential representation within a page by a linked representation. The main advantage of this method is realized in the construction (and maintenance) phase of the index. Although this phase is difficult to analyze quantitatively—as alluded to in [4]—we provide data to substantiate our claim of a net saving in construction cost without any corresponding loss in the average retrieval cost. In the ensuing discussion we assume that the reader is familiar both with B-trees and the paper of Maruyama and Smith [4].
Research and Advances

Hybrid simulation models of computer systems

This paper describes the structure and operation of a hybrid simulation model in which both discrete-event simulation and analytic techniques are combined to produce efficient yet accurate system models. In an example based on a simple hypothetical computer system, discrete-event simulation is used to model the arrival and activation of jobs, and a central-server queueing network models the use of system processors. The accuracy and efficiency of the hybrid technique are demonstrated by comparing the result and computational costs of the hybrid model of the example with those of an equivalent simulation-only model.
Research and Advances

A model for verification of data security in operating systems

Program verification applied to kernel architectures forms a promising method for providing uncircumventably secure, shared computer systems. A precise definition of data security is developed here in terms of a general model for operating systems. This model is suitable as a basis for verifying many of those properties of an operating system which are necessary to assure reliable enforcement of security. The application of this approach to the UCLA secure operating system is also discussed.
and
Research and Advances

Event manipulation for discrete simulations requiring large numbers of events

The event-manipulation system presented here consists of two major parts. The first part addresses the familiar problem of event scheduling efficiency when the number of scheduled events grows large. The second part deals with the less apparent problem of providing efficiency and flexibility as scheduled events are accessed to be executed. Additional features and problems dealt with include the proper handling of simultaneous events; that certain events must be created, scheduled, and executed at the same points in simulated time; that infinite loops caused by the concatenation of such “zero-time” events are possible and must be diagnosed; that maintaining various event counts is practical and economical; and that a capability for handling “time-displaceable” events is desirable and possible.
Research and Advances

A controlled experiment in program testing and code walkthroughs/inspections

This paper describes an experiment in program testing, employing 59 highly experienced data processing professionals using seven methods to test a small PL/I program. The results show that the popular code walkthrough/inspection method was as effective as other computer-based methods in finding errors and that the most effective methods (in terms of errors found and cost) employed pairs of subjects who tested the program independently and then pooled their findings. The study also shows that there is a tremendous amount of variability among subjects and that the ability to detect certain types of errors varies from method to method.
Research and Advances

Right brother trees

Insertion and deletion algorithms are provided for the class of right (or one-sided) brother trees which have O (log n) performance. The importance of these results stems from the close relationship of right brother trees to one-sided height-balanced trees which have an insertion algorithm operating in O (log2 n). Further, although both insertion and deletion can be carried out in O (log n) time for right brother trees, it appears that the insertion algorithm is inherently much more difficult than the deletion algorithm—the reverse of what one usually obtains.
, , and
Research and Advances

Simulations of dynamic sequential search algorithms

In [3], R.L. Rivest presents a set of methods for dynamically reordering a sequential list containing N records in order to increase search efficiency. The method Ai (for i between 1 and N) performs the following operation each time that a record R has been successfully retrieved: Move R forward i positions in the list, or to the front of the list if it was in a position less than i. The method A1 is called the transposition method, and the method AN-1 is called the move-to-front method.
Research and Advances

Fast parallel sorting algorithms

A parallel bucket-sort algorithm is presented that requires time O(log n) and the use of n processors. The algorithm makes use of a technique that requires more space than the product of processors and time. A realistic model is used in which no memory contention is permitted. A procedure is also presented to sort n numbers in time O(k log n) using n1+1/k processors, for k an arbitrary integer. The model of computation for this procedure permits simultaneous fetches from the same memory location.
Research and Advances

A time- and space-efficient garbage compaction algorithm

Given an area of storage containing scattered, marked nodes of differing sizes, one may wish to rearrange them into a compact mass at one end of the area while revising all pointers to marked nodes to show their new locations. An algorithm is described here which accomplishes this task in linear time relative to the size of the storage area, and in a space of the order of one bit for each pointer. The algorithm operates by reversibly encoding the situation (that a collection of locations point to a single location) by a linear list, emanating from the pointed-to location, passing through the pointing locations, and terminating with the pointed-to location's transplanted contents.
Research and Advances

Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs

Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor—the von Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs. An alternative functional style of programming is founded on the use of combining forms for creating programs. Functional programs deal with structured data, are often nonrepetitive and nonrecursive, are hierarchically constructed, do not name their arguments, and do not require the complex machinery of procedure declarations to become generally applicable. Combining forms can use high level programs to build still higher level ones in a style not possible in conventional languages. Associated with the functional style of programming is an algebra of programs whose variables range over programs and whose operations are combining forms. This algebra can be used to transform programs and to solve equations whose “unknowns” are programs in much the same way one transforms equations in high school algebra. These transformations are given by algebraic laws and are carried out in the same language in which programs are written. Combining forms are chosen not only for their programming power but also for the power of their associated algebraic laws. General theorems of the algebra give the detailed behavior and termination conditions for large classes of programs. A new class of computing systems uses the functional programming style both in its programming language and in its state transition rules. Unlike von Neumann languages, these systems have semantics loosely coupled to states—only one state transition occurs per major computation.
Research and Advances

Value conflicts and social choice in electronic funds transfer system developments

During the last few years, computer-based systems which automate the transfer and recording of debits and credits have begun to be implemented on a large scale. These systems promise both financial benefits for the institutions that use them and potential conveniences to their customers. However, they also raise significant social, legal, and technical questions that must be resolved if full scale systems for Electronic Funds Transfer (EFT) are not to cause more problems for the larger public than they solve. This paper examines the incentives for EFT developments and the social problems they raise in the context of conflicts between five different value positions that are often implicit in analyses of proposed EFT arrangements. These conflicts reflect the relative importance of certain problems for specific groups. The value positions implicit in EFT proposals help to organize analyses of market arrangements, system reliability, and privacy of transactions. These topics are analyzed in this article and related to the value positions held by concerned parties. Last, the ways in which the public can learn about the social qualities of different EFT arrangements and the pace of EFT developments are both discussed in the context of social choice.
Research and Advances

Communicating sequential processes

This paper suggests that input and output are basic primitives of programming and that parallel composition of communicating sequential processes is a fundamental program structuring method. When combined with a development of Dijkstra's guarded command, these concepts are surprisingly versatile. Their use is illustrated by sample solutions of a variety of a familiar programming exercises.
Research and Advances

Feedback coupled resource allocation policies in the multiprogramming-multiprocessor computer system

Model studies of some integrated, feedback-driven scheduling systems for multiprogrammed-multiprocessor computer systems are presented. The basic control variables used are the data-flow rates for the processes executing on the CPU. The model systems feature simulated continuous-flow and preempt-resume scheduling of input-output activity. Attention is given to the amount of memory resource required for effective processing of the I/O activity (buffer space assignment). The model studies used both distribution-driven and trace-driven techniques. Even relatively simple dynamic schedulers are shown to improve system performance (as measured by user CPU time) over that given by optimal or near-optimal static schedulers imbedded in identical system structures and workload environments. The improvement is greatest under a heavy I/O demand workload.
and
Research and Advances

Pseudochaining in hash tables

This paper presents pseudochaining as a new collision-resolution method. Pseudochaining is half way between open addressing and chaining. It owes its name to the fact that link fields are present in each cell of the hash table which permits “chaining” of the first overflow items in the table. The efficiency of the method is derived and a tradeoff analysis is given.
and
Research and Advances

Analysis of the availability of computer systems using computer-aided algebra

Analytical results, related to the availability of a computer system constructed of unreliable processors, are presented in this paper. These results are obtained by using various computer-aided algebraic manipulation techniques. A major purpose of this paper is to demonstrate that the difficulties of obtaining analytical solutions to Markov processes can be considerably reduced by the application of symbol manipulation programs. Since many physical systems can be modeled by Markov and semi-Markov processes, the potential range of application of these techniques is much wider than the problem of availability analyzed here.
and
Research and Advances

An O(n) algorithm for determining a near-optimal computation order of matrix chain products

This paper discusses the computation of matrix chain products of the form M1 × M22 × ··· × Mn where Mi's are matrices. The order in which the matrices are computed affects the number of operations. A sufficient condition about the association of the matrices in the optimal order is presented. An O(n) algorithm to find an order of computation which takes less than 25 percent longer than the optimal time Topt is also presented. In most cases, the algorithm yields the optimal order or an order which takes only a few percent longer than Topt (less than 1 percent on the average).
Research and Advances

On the complexity of computing the measure of ∪[ai,bi]

The decision tree complexity of computing the measure of the union of n (possibly overlapping) intervals is shown to be &OHgr;(n log n), even if comparisons between linear functions of the interval endpoints are allowed. The existence of an &OHgr;(n log n) lower bound to determine whether any two of n real numbers are within ∈ of each other is also demonstrated. These problems provide an excellent opportunity for discussing the effects of the computational model on the ease of analysis and on the results produced.
and
Research and Advances

Interpolation search—a log logN search

Interpolation search is a method of retrieving a desired record by key in an ordered file by using the value of the key and the statistical distribution of the keys. It is shown that on the average log logN file accesses are required to retrieve a key, assuming that the N keys are uniformly distributed. The number of extra accesses is also estimated and shown to be very low. The same holds if the cumulative distribution function of the keys is known. Computational experiments confirm these results.
, , and
Research and Advances

Time, clocks, and the ordering of events in a distributed system

The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.
Research and Advances

Proving the correctness of heuristically optimized code

A system for proving that programs written in a high level language are correctly translated to a low level language is described. A primary use of the system is as a postoptimization step in code generation. The low level language programs need not be generated by a compiler and in fact could be hand coded. Examples of the usefulness of such a system are given. Some interesting results are the ability to handle programs that implement recursion by bypassing the start of the program, and the detection and pinpointing of a wide class of errors in the low level language programs. The examples demonstrate that optimization of the genre of this paper can result in substantially faster operation and the saving of memory in terms of program and stack sizes.
Research and Advances

An English language question answering system for a large relational database

By typing requests in English, casual users will be able to obtain explicit answers from a large relational database of aircraft flight and maintenance data using a system called PLANES. The design and implementation of this system is described and illustrated with detailed examples of the operation of system components and examples of overall system operation. The language processing portion of the system uses a number of augmented transition networks, each of which matches phrases with a specific meaning, along with context registers (history keepers) and concept case frames; these are used for judging meaningfulness of questions, generating dialogue for clarifying partially understood questions, and resolving ellipsis and pronoun reference problems. Other system components construct a formal query for the relational database, and optimize the order of searching relations. Methods are discussed for handling vague or complex questions and for providing browsing ability. Also included are discussions of important issues in programming natural language systems for limited domains, and the relationship of this system to others.
Research and Advances

Shallow binding in Lisp 1.5

Shallow binding is a scheme which allows the value of a variable to be accessed in a bounded amount of computation. An elegant model for shallow binding in Lisp 1.5 is presented in which context-switching is an environment tree transformation called rerooting. Rerooting is completely general and reversible, and is optional in the sense that a Lisp 1.5 interpreter will operate correctly whether or not rerooting is invoked on every context change. Since rerooting leaves assoc [v, a] invariant, for all variables v and all environments a, the programmer can have access to a rerooting primitive, shallow[], which gives him dynamic control over whether accesses are shallow or deep, and which affects only the speed of execution of a program, not its semantics. In addition, multiple processes can be active in the same environment structure, so long as rerooting is an indivisible operation. Finally, the concept of rerooting is shown to combine the concept of shallow binding in Lisp with Dijkstra's display for Algol and hence is a general model for shallow binding.

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