Browse Prior Art Database

Parallel in Place Graphics Buffer Reorganizations

IP.com Disclosure Number: IPCOM000113111D
Original Publication Date: 1994-Jul-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 8 page(s) / 223K

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR [+2]

Abstract

An image buffer (pixmap) is a block of memory used to store pixels that eventually need to be displayed on a screen. The manner in which the pixmap is accessed is dictated by the algorithm. In several algorithms, the pixmap is accessed in a linear scan line fashion, e.g., run-length coding, dithering by error diffusion, etc. In some other algorithms such as filtering, line drawing, small polygon scan conversion, etc., it is advantageous to access the pixmap in a block fashion. The key to an efficient implementation of the algorithm is that consecutive accesses should be contiguous so that cache-misses are minimized. Fig. 1 shows the two different organizations of a pixmap.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 19% of the total text.

Parallel in Place Graphics Buffer Reorganizations

      An image buffer (pixmap) is a block of memory used to store
pixels that eventually need to be displayed on a screen.  The manner
in which the pixmap is accessed is dictated by the algorithm.  In
several algorithms, the pixmap is accessed in a linear scan line
fashion, e.g., run-length coding, dithering by error diffusion, etc.
In some other algorithms such as filtering, line drawing, small
polygon scan conversion, etc., it is advantageous to access the
pixmap in a block fashion.  The key to an efficient implementation of
the algorithm is that consecutive accesses should be contiguous so
that cache-misses are minimized.  Fig. 1 shows the two different
organizations of a pixmap.

      In addition, in a parallel processing environment where the
pixmap is shared among several processors, it is necessary to
partition the frame buffer into several blocks [1,2], each of which
is owned by one processor.  The blocks may either be small
rectangular blocks, or larger rectangular blocks whose width is equal
to that of the scan line.  As the number of processors changes, the
size of the blocks may need to be changed.

      Thus it is clear that in order to achieve the highest
efficiency in a wide range of situations, the organization of the
pixmap may need to be changed depending on the conditions.  However,
in most current schemes a static organization is utilized.  Therefore
in this article we present a solution to the problem of dynamic
pixmap reorganization.

THE ALGORITHM

      Preliminaries - Consider the case where the reconfiguration has
to be done in place, i.e., in the same pixmap without using any
scratch memory.  The other case where a scratch copy of the pixmap is
used is much simpler.

      Fig. 1 shows the two organizations.  We will assume that the
pixmap is of size s X t pixels.  For the scan line organization, all
pixels in scan line "a" will be stored contiguously in the linear
memory.  This will be followed by pixels in scan line "b".  Thus in
this organization, a pixel in scan line "b" that is immediately below
another pixel in scan line "a" are not contiguous in memory.  In the
block organization, the pixmaps is broken into m X n small
rectangular blocks, e.g., "A", "B", each of size u X v.  Pixels for
each sub-scan line within a block will be stored contiguously in
linear memory.  This will be followed by the pixels for the next
sub-scan line within the block.  Once all the pixels for a block have
been stored, the pixels for the next block in the row are stored.
This is followed by the pixels for the blocks in the next row.

      Conversion Equations - Now we answer the simple questions that
will help us derive, using the terms defined in Fig. 1, the parallel
algorithm.

       s = m X u

       t = n X v

      Given a pixel at location (i, j), i.e., row "i" and column "j",
its address S(i, j) in linear memory for the...