February 1985 - Vol. 28 No. 2

February 1985 issue cover image

Features

Research and Advances

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

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

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.

Recent Issues

  1. December 2024 CACM cover
    December 2024 Vol. 67 No. 12
  2. November 2024 CACM cover
    November 2024 Vol. 67 No. 11
  3. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  4. September 2024 CACM cover
    September 2024 Vol. 67 No. 9