7 July 2021 in Informatics in Education
Over its short disciplinary history, computing has seen a stunning number of descriptions of the field's characteristic ways of thinking and practicing, under a large number of different labels. One of the more recent variants, notably in the context of K-12 education, is "computational thinking", which became popular in the early 2000s, and which has given rise to many competing views of the essential character of CT. This article analyzes CT from the perspective of computing's disciplinary ways of thinking and practicing, as expressed in writings of computing's pioneers. The article describes six windows into CT from a computing perspective: its intellectual origins and justification, its aims, and the central concepts, techniques, and ways of thinking in CT that arise from those different origins. The article also presents a way of analyzing CT over different dimensions, such as in terms of breadth vs. depth, specialization vs. generalization, and in terms of skill progression from beginner to expert. Those different views have different aims, theoretical references, conceptual frameworks, and origin stories, and they justify their intellectual essence in different ways.
1 November 2010 in Ubiquity
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.
2 February 2021 in ACM Computing Surveys
The working set model for program behavior was invented in 1965. It has stood the test of time in virtual memory management for over 50 years. It is considered the ideal for managing memory in operating systems and caches. Its superior performance was based on the principle of locality, which was discovered at the same time; locality is the observed tendency of programs to use distinct subsets of their pages over extended periods of time. This tutorial traces the development of working set theory from its origins to the present day. We will discuss the principle of locality and its experimental verification. We will show why working set memory management resists thrashing and generates near-optimal system throughput. We will present the powerful, linear-time algorithms for computing working set statistics and applying them to the design of memory systems. We will debunk several myths about locality and the performance of memory systems. We will conclude with a discussion of the application of the working set model in parallel systems, modern shared CPU caches, network edge caches, and inventory and logistics management.
31 August 2016 in Ubiquity
In Part 1, Jeff Buzen discussed the basic principles of his new approach to randomness, which is the topic of his book Rethinking Randomness. He continues here with a more detailed discussion of models that have been used successfully to predict the performance of systems ranging from early time sharing computers to modern web servers. Peter J. Denning Editor in Chief