In many areas of program and system analysis and optimization, locality is a common concept and has been defined and measured in many ways. This article aims to formally establish relations between these previously disparate types of locality. It categorizes locality definitions in three groups and shows whether and how they can be interconverted. For the footprint, a recent metric, it gives a new measurement algorithm that is asymptotically more time/space efficient than previous approaches. Using the conversion relations, the new algorithm derives with the same efficiency different locality metrics developed and used in program analysis, memory management, and cache design.

ACM Ubiquity hosted a symposium in 2010–2011 on Turing's question, ‘What is computation?’ The editor reflects on how the symposium was organized and what conclusions it reached. The authors showed strong consensus around the propositions that computation is a process, computational model matters, many computations are natural, many important computations are continuous, many important computations are nonterminating and computational thinking has emerged as a core practice of computing. They left open the questions of whether the Turing model is the best reference model, is computational necessarily a physical process, what is information and what is an algorithm.

Most people understand a computation as a process evoked when a computational agent acts on its inputs under the control of an algorithm. The classical Turing machine model has long served as the fundamental reference model because an appropriate Turing machine can simulate every other computational model known. The Turing model is a good abstraction for most digital computers because the number of steps to execute a Turing machine algorithm is predictive of the running time of the computation on a digital computer. However, the Turing model is not as well matched for the natural, interactive, and continuous information processes frequently encountered today. Other models whose structures more closely match the information processes involved give better predictions of running time and space. Models based on transforming representations may be useful.

The “computation” symposium presents the reflections of thinkers from many sectors of computing on the fundamental question in the background of everything we do as computing professionals. While many of us have too many immediate tasks to allow us time for our own deep reflection, we do appreciate when others have done this for us. Peter Freeman points out, by analogy, that as citizens of democracies we do not spend a lot of time reflecting on the question, “What is a democracy.” But from time to time we find it helpful to see what philosophers and political scientists are saying about the context in which we act as citizens.

The article of record as published may be found at http://doi.org/10.1093/comjnl/bxs065

No abstract available.

No abstract available.

The nearly three dozen core technologies of computing sit in a simple framework defined by great principles and by computing practices. The great principles are of two kinds, mechanics and design. Computing mechanics comprises computation, communication, coordination, recollection, and automation. Design principles address concerns for complexity, resilience, performance, evolvability, and security. Practices comprise programming, systems, modeling, innovating, and applying. This framework opens many new possibilities for teaching computer science, including new approaches to programming. The new CS curriculum at the Naval Postgraduate School is based on the framework presented here.

Questions and answers about the great principles framework for computing and its impact on the organization and content of curriculum, with special attention to communicating our field, teaching programming, and appealing to a diverse audience.

No abstract available.

No abstract available.

In the fall of 1998, the ACM Education Board and the Educational Activities Board of the IEEE Computer Society appointed representatives to a joint task force to prepare Curriculum 2001, the next installment in a series of reports on the undergraduate Computer Science curriculum that began in 1968 and was then updated in 1978 and 1991. The purpose of this panel is to present an overview of the early work of the task force and to generate discussion in the SIGCSE membership about the directions and plans for the new curriculum.

ing with credit is permitted. To copy otherwise, to republish, to repost on public lists or servers, or to use any component of this work in other works whether directly There is a connection between operating systems and workflow and groupware systems that is not widely appreciated. It has profound implications for the design and performance evaluation of computer systems. For over four decades the basic set of abstractions around which we structure operating systems has not changed. This is a testimony to the power and ruggedness of those ...

It is ACM's 40th year and an old debate continues. Is computer science a science? An engineering discipline? Or merely a technology, an inventor and purveyor of computing commodities? What is the intellectual substance of the discipline? Is it lasting, or will it fade within a generation? Do core curricula in computer science and engineering accurately reflect the field? How can theory and lab work be integrated in a computing curriculum?We project an image of a technology-oriented discipline whose fundamentals are in mathematics and engineering — for example, we represent algorithms as the most basic objects of concern and programming and hardware design as the primary activities. The view that “computer science equals programming” is especially strong in our curricula: the introductory course is programming, the technology is in our core courses, and the science is in our electives. This view blocks progress in reorganizing the curriculum and turns away the best students, who want a greater challenge. It denies a coherent approach to making experimental and theoretical computer science integral and harmonious parts of a curriculum.Those in the discipline know that computer science encompasses far more than programming. The emphasis on programming arises from our long-standing belief that programming languages are excellent vehicles for gaining access to the rest of the field — but this belief limits out ability to speak about the discipline in terms that reveal its full breadth and richness.The field has matured enough that it is now possible to describe its intellectual substance in a new and compelling way. In the spring of 1986, ACM President Adele Goldberg and ACM Education Board Chairman Robert Aiken appointed this task force with the enthusiastic cooperation of the IEEE Computer Society. At the same time, the Computer Society formed a task force on computing laboratories with the enthusiastic cooperation of the ACM.The charter of the task force has three components: Present a description of computer science that emphasizes fundamental questions and significant accomplishments.Propose a new teaching paradigm for computer science that conforms to traditional scientific standards and harmoniously integrates theory and experimentation.Give at least one detailed example of a three-semester introductory course sequence in computer science based on the curriculum model and the disciplinary description.We immediately extended our task to encompass computer science and computer engineering, for we came to the conclusion that in the core material there is no fundamental difference between the two fields. We use the phrase “discipline of computing” to embrace all of computer science and engineering. The rest of this paper is a summary of the recommendation.The description of the discipline is presented in a series of passes, starting from a short definition and culminating with a matrix as shown in the figure. The short definition:Computer science and engineering is the systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all of computing is, “What can be (efficiently) automated?”The detailed description of the field fills in each of the 27 cells in the matrix with significant issues and accomplishments. (That description occupies about 16 pages of the report.)For the curriculum model, we recommend that the introductory course consist of regular lectures and a closely coordinated weekly laboratory. The lectures emphasize fundamentals; the laboratories emphasize technology and know-how. The pattern of closely coordinated lectures and labs can be repeated where appropriate in other courses. The recommended model is traditional in the physical sciences and in engineering: lectures emphasize enduring principles and concepts while laboratories emphasize the transient material and skills relating to the current technology.

CSNET is the acronym for the Computer Science Research Network, a project supported by NSF to provide advanced computer network services to the computer research community. CSNET is a "logical net" -- a high-level communication environment spanning several physical nets, including the ARPANET, Phonenet, and Telenet. This paper reviews the history, the goals, the organization, the components, and the status of CSNET.

What is experimental computer science? This question has been widely discussed ever since the Feldman Report was published (1979 [18]). Many computer scientists believe that survival of their discipline is intimately linked to their ability to rejuvenate experimentation. The National Science Foundation instituted the Coordinated Experimental Research Program (CERP) in 1979 to help universities set up facilities capable of supporting experimental research. Other agencies of government are considering similar programs. Some industrial firms are offering similar help through modest cash grants and equipment discounts.

A program's working set is the collection of segments (or pages) recently referenced. This concept has led to efficient methods for measuring a program's intrinsic memory demand; it has assisted in undetstanding and in modeling program behavior; and it has been used as the basis of optimal multiprogrammed memory management. The total cost of a working set dispatcher is no larger than the total cost of other common dispatchers. This paper outlines the argument why it is unlikely that anyone will find a cheaper nonlookahead memory policy that delivers significantly better performance.

The query programs of certain databases report raw statistics for query sets, which are groups of records specified implicitly by a characteristic formula. The raw statistics include query set size and sums of powers of values in the query set. Many users and designers believe that the individual records will remain confidential as long as query programs refuse to report the statistics of query sets which are too small. It is shown that the compromise of small query sets can in fact almost always be accomplished with the help of characteristic formulas called trackers. Schlörer's individual tracker is reviewed; it is derived from known characteristics of a given individual and permits deducing additional characteristics he may have. The general tracker is introduced: It permits calculating statistics for arbitrary query sets, without requiring preknowledge of anything in the database. General trackers always exist if there are enough distinguishable classes of individuals in the database, in which case the trackers have a simple form. Almost all databases have a general tracker, and general trackers are almost always easy to find. Security is not guaranteed by the lack of a general tracker.

A database is compromised if a user can determine the data elements associated with keys which he did not know previously. If it is possible, compromise can be achieved by posing a finite set of queries over sets of data elements and employing initial information to solve the resulting system of equations. Assuming the allowable queries are linear, that is, weighted sums of data elements, we show how compromise can be achieved and we characterize the maximal initial information permitted of a user in a secure system. When compromise is possible, the initial information and the number of queries required to achieve it is surprisingly small.

A program's working set is the collection of pages (or segments) recently referenced. This concept has led to efficient methods for measuring a program's intrinsic memory demand; it has assisted in understanding program behavior; and it has been used as the basis of optimal multiprogrammed memory management. This paper outlines the argument why it is unlikely that anyone will find a cheaper nonlookahead memory policy that delivers significantly better performance. This paper is based on a longer paper that presents the arguments in greater detail [DENN78d].

Balancing interpagefault lifetime (L) against page swap time (S) has always been a performance criterion of great intuitive appeal. This paper shows that, under normal conditions, controlling the memory policy parameter to enforce the constraint L ≥ S, and allowing the multiprogramming load to rise as high as demand warrants without violating this constraint, will produce a load slightly higher than optimum. Equivalently, using the criterion L = uS for some u slightly larger than 1 will approximate an optimal load. Using simulations, this criterion is compared with two others reported in the literature, namely the “knee criterion” (operate with L at the knee of the lifetime curve) and the 50% criterion (operate with the paging device at 50% utilization).The knee criterion produced optimal loads more often than the L=S criterion, which in turn produced optimal loads more often than the 50% criterion. Since no practical implementation of the knee criterion is known, the L=S criterion is the most attractive of the three.

A program model can be regarded as decomposible into two main parts. The macromodel captures the phase-transition behavior by specifying locality sets and their associated reference intervals (phases). The micromodel captures the reference patterns within phases. A semi-Markov model can be used at the macro level, while one of the simple early models (such as the random-reference or LRU stack) can be used at the micro level. This paper shows that, even in simplest form, this type of model is capable of reproducing known properties of empirical lifetime functions. A micromodel, alone without a macromodel, is incapable of doing so.

The linear approximation relating mean time between page transfers between levels of memory, as reported by Saltzer for Multics, is examined. It is tentatively concluded that this approximation is untenable for main memory, especially under working set policies; and that the linearity of the data for the drum reflects the behavior of the Multics scheduler for background jobs, not the behavior of programs.

Dynamic multiprogramming memory management strategies are classified and compared using extant test data. Conclusions about program behavior are then drawn.

This book will become a lethal weapon against skepticism toward the possibility of presenting programming as a precise discipline based on clear and simple principles. It treats what many regard as advanced topics in programming in so straightforward a manner, that there is little doubt that the "advanced topics" are in fact elementary notions. The material is presented simultaneously at many levels: the college sophomore will enjoy a hearty repast of solid conceptual and practical aspects of algorithm design, and the college professor or industrial professional will enjoy many morsels from the philosophy of programming to practical advice on the best uses of each language construction. The material is presented in a fast-moving, unadorned style, reminiscent in places of sketchy lecture notes; indeed, fully fourteen chapters appear in the first 124 pages. Every concept is backed by an example; I counted approximately 45 sample algorithms or programs in the text and about 25 more in the Exercises. The sample programs are masterpieces of clarity, exemplifying how invariant assertions can be embedded in comments to make understanding and verifying the programs as simple as possible. Wirth leaves little doubt as to the power of this technique, not merely by disoussing it but by doing it.

A model of paged multiprogramming computer systems using variable storage partitioning is considered. A variable storage partitioning policy is one which allocates storage among the active tasks according to a sequence of fixed partitions of main storage. The basic result obtained is, mean processing efficiency is increased and mean fault-rate decreased under a variable partition, provided that the curves of efficiency and fault-rate as a function of allocated space are concave up.

Two generalizations of the simple precedence grammars are considered.The first, the weak precedence grammars, are shown to generate exactly the simple precedence languages.The second, the "simple" mixed strategy precedence grammars, are shown to generate exactly the deterministic context-free languages.Algorithms for their implementation are given, and the complexity of these algorithms studied.

This paper appears in the March, 1972, issue of the Communications of the ACM. Its abstract is reproduced below.

ABSTP~CT.A formal model is presented for paging algorithms under /-order nonstationary assumptions about program behavior.When processing a program under paging in a given memory, a given paging policy generates a certain (expected) number of page calls, i.e., its "cost."Under usual assumptions about memory system organization, minimum cost is always achieved by a demand paging algorithm.The minimum cost for /-order program behavior assumptions is expressed as a dynamic programming problem whose solution yields an optimal replacement algorithm.Solutions are exhibited in several 0-order cases of interest.Paging algorithms that implement and approximate the minimum cost are discussed.

This paper describes the content of a one-term advanced undergraduate course being developed in the Department of Electrical Engineering at Princeton University.

A computer system is said to be balanced whenever the set of running programs presents a total demand, for both processors and memory, that matches the available equipment. The equipment configuration, here defined as the proper relative capacities of processor and memory resources in a balanced computer system, may be determined analytically.

Probably the most basic reason behind the absence of a general treatment of resource allocation in modern computer systems is an adequate model for program behavior. In this paper a new model is developed, the “working set model”, which enables us to decide which information is in use by a running program and which is not. Such knowledge is vital for dynamic management of paged memories. The working set of pages associated with a process, defined to be the collection of its most recently used pages, is a useful allocation concept. A proposal for an easy-to-implement allocation policy is set forth; this policy is unique, inasmuch as it blends into one decision function the heretofore independent activities of process-scheduling and memory-management.