Optimal prepaging and font caching

ABSTRACT

An efficient algorithm for communicating letter-shape information from a high-speed computer with a large memory to a typesetting device that has a limited memory is presented. The encoding is optimum, in the sense that the total time for typesetting is minimized, using a model that generalizes well-known “demand paging” strategies to the case where changes to the cache are allowed before the associated information is actually needed. Extensive empirical data show that good results are obtained even when difficult technical material is being typeset on a machine that can store information concerning only 100 characters. The methods of this paper are also applicable to other hardware and software caching applications with restricted lookahead.

REFERENCES

• 1: BELADY, L.A. A study of replacement algorithms for a virtual-storage computer. IBM Syst. J. 5 (1966), 78-101.
• 2: BELAOY, L. A., ANO PALERMO, F.P. On-line measurement of paging behavior by the multivalued MIN algorithm. IBM J. Res. Dev. 18 (1974), 2-19.
• 3: GAREY, M. R., JOHNSON, D.S. Computers and Intractability. W. H. Freeman, San Francisco, 1979.
• 4: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 5: MATTSON, R. L., GECSEI, J., SLUTZ, D. R., AND TRAIGER, I. L. Evaluation techniques for storage hierarchies. IBM Syst. J. 9 (1970), 78-117.

INDEX TERMS

Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage; Virtual memory; Allocation/deallocation strategies

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Photocomposition/typesetting

General Terms:
Algorithms, Measurement, Performance, Theory