Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!icdoc!phjk
From: phjk@doc.ic.ac.uk (Paul H J Kelly)
Newsgroups: comp.arch
Subject: Re: hmmm, BitBlt, One-cycle bitblt by Chor et al.
Summary: raster-op in one cycle for any rectangle
Keywords: memory organisation, number theory, raster-op, bitblt
Message-ID: <1655@gould.doc.ic.ac.uk>
Date: 1 Mar 90 15:14:37 GMT
References: <7398@pdn.paradyne.com> <1990Feb18.084034.7015@utzoo.uucp> <7404@pdn.paradyne.com>
Sender: news@doc.ic.ac.uk
Reply-To: phjk@doc.ic.ac.uk (Paul Kelly)
Organization: Dept of Computing, Imperial College, London, UK.
Lines: 27

It is possible to do BITBLT very fast indeed using an interleaved memory
and a very smart addressing/organisation scheme.  This is described in

B. Chor, C.E. Leiserson, R.L. Rivest, J.B. Shearer,
An application of number theory to the organisation of raster-graphics
memory.
JACM V33 N1 Jan 86 pp 86-104.

"The memory organisation is based on a doubly-periodic assignment of pixels
to M memory chips according to a 'fibonacci' lattice.  The memory
organisation guarantees that, if a rectilinearly oriented rectangle 
contains fewer than M/sqrt(5) pixles then all pixels will reside in 
different memory chips and can thus be accessed simultaneously."

This would seem to provide a neat attack on the problems of overheads in
small BITBLTs.

Has anyone actually done this?

I don't really understand the scheme.  I would be very grateful if someone
could give me a words-of-one-syllable account.

It does seem to use some vary interesting ideas.

Yours in fascination,

Paul Kelly.