February 1985 - Vol. 28 No. 2
Features
Grosch’s law re-revisited: CPU power and the cost of computation
Does Grosch's law, which postulated that the costs of computer systems increase at a rate equivalent to the square root of their power, still hold? The age of mini-, micro-, and supercomputers seems to have complicated the situation. When computers are grouped according to their size and power, Grosch's law seems to hold within each group, but not between different groups.
Rating the major computing periodicals on readability
The readability of the ten major computing periodicals is analyzed using the Flesch Reading Ease Index.
From programming language design to computer construction
From NELIAC (via ALGOL 60) to Euler and ALGOL W, to Pascal and Modula-2, and ultimately Lilith, Wirth's search for an appropriate formalism for systems programming yields intriguing insights and surprising results.
User-oriented criteria for the selection of DSS software
Both the composition of the selection team and the choice of evaluation criteria should reflect the end-user orientation of DSS software.
Programmer perceptions of productivity and programming tools
Psychometric scaling methods are applied to programmer productivity assessments of 20 tools to recommend a set of minimal, as well as more comprehensive, tools.
A specification language to assist in analysis of discrete event simulation models
Effective development environments for discrete event simulation models should reduce development costs and improve model performance. A model specification language used in a model development environment is defined. This approach is intended to reduce modeling costs by interposing an intermediate form between a conceptual model (the model as it exists in the mind of the modeler) and an executable representation of that model. As a model specification is constructed, the incomplete specification can be analyzed to detect some types of errors and to provide some types of model documentation. The primitives used in this specification language, called a condition specification (CS), are carefully defined. A specification for the classical patrolling repairman model is used to illustrate this language. Some possible diagnostics and some untestable model specification properties, based on such a representation, are summarized.
Amortized efficiency of list update and paging rules
In this article we study the amortized efficiency of the “move-to-front” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith element from the front of the list takes &thgr;(i) time, we show that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules. Other natural heuristics, such as the transpose and frequency count rules, do not share this property. We generalize our results to show that move-to-front is within a constant factor of optimum as long as the access cost is a convex function. We also study paging, a setting in which the access cost is not convex. The paging rule corresponding to move-to-front is the “least recently used” (LRU) replacement rule. We analyze the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory. No on-line paging algorithm has better amortized performance.
