An application of number theory to the organization of raster-graphics memory

ABSTRACT

A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ability to quickly move or copy small rectangles of pixels is essential. This paper proposes a novel organization of raster-graphics memory that permits all small rectangles to be moved efficiently. The memory organization is based on a doubly periodic assignment of pixels to M memory chips according to a “Fibonacci” lattice. The memory organization guarantees that, if a rectilinearly oriented rectangle contains fewer than M/ @@@@5 pixels, then all pixels will reside in different memory chips and thus can be accessed simultaneously. Moreover, any M consecutive pixels, arranged either horizontally or vertically, can be accessed simultaneously. We also define a continuous analog of the problem, which can be posed as: “What is the maximum density of a set of points in the plane such that no two points are contained in the interior of a rectilinearly oriented rectangle of unit area?” We show the existence of such a set with density 1/ @@@@5, and prove this is optimal by giving a matching upper bound.

REFERENCES

• 1: Ed Catmull , Alvy Ray Smith, 3-D transformations of images in scanline order, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.279-285, July 14-18, 1980, Seattle, Washington, United States
• 2: CHOR, B., LEISERSON, C. E., AND RIVEST, R.L. An application of number theory to the organization of raster graphics memory (extended abstract). In Proceedings ofthe 23rdAnnual Symposium on Foundations of Computer Science (October). IEEE, New York, 1982, pp. 92-99.
• 3: CLARK, J. H., AND HANNAH, M.R. Distributed processing in a high-performance smart image memory. Lambda, fourth quarter (1980), 40-45.
• 4: FIAT, A., AND SHAMIR, A. Polymorphic arrays: A novel VLSI layout for systolic computers, in Proceedings of the 25th Annual Symposium on Foundations of Computer Science (Oct.). IEEE, 1984, pp. 37-45.
• 5: Satish Gupta, Architectures and algorithms for parallel updates of raster scan displays, 1982
• 6: HARDY, G. H., AND WRIGHT, E. M. All Introduction to the Theory of Numbers. Oxford Univ. Press, London, 1968.
• 7: HOLLADAY, T. M. An optimum algorithm for halftone generation for displays and hard copies. Proc. Soc. Inf. Display 21, 2 (1980), 185-192.
• 8: NIVEN, I., AND ZUCKERMA'N, H. S. An Introduction to the Theory of Numbers. Wiley, New York, 1972.
• 9: SPROULL, R. F., SUTHERLAND, I. E., THOMPSON, A., GUPTA, S., AND MINTER, C. The 8-by-8 display. Tech. Rep. CMU-CS-82-105. Carnegie-Mellon Univ., Pittsburgh, Pa., 1981.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Raster display devices

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Design, Measurement, Performance, Theory, Verification