Path: utzoo!mnetor!tmsoft!torsqnt!jarvis.csri.toronto.edu!rutgers!mephisto!usenet.ins.cwru.edu!pjd!cook
From: cook@pjd.CES.CWRU.Edu (Jonathan E. Cook)
Newsgroups: comp.arch
Subject: Re: hmmm, BitBlt, One-cycle bitblt by Chor et al.
Summary: actually re: Chor
Keywords: memory organisation, number theory, raster-op, bitblt
Message-ID: <1990Mar3.213807.10047@usenet.ins.cwru.edu>
Date: 3 Mar 90 21:38:07 GMT
References: <7398@pdn.paradyne.com> <1990Feb18.084034.7015@utzoo.uucp> <7404@pdn.paradyne.com> <1655@gould.doc.ic.ac.uk>
Organization: Case Western Reserve University
Lines: 34

In article <1655@gould.doc.ic.ac.uk> phjk@doc.ic.ac.uk (Paul Kelly) writes:
>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.
>
From a practical point of view, this result would not seem to provide
very much return on investement, labor, etc. It relies on a high
memory chip count (M) and a relatively small number of pixels for
good results. And we all know that chip count continues downward, while
pixel count is heading up (I'm ready for a 300dpi screen, how about you?)

Besides, wiring and control would be pretty stupefying (sp?).

>Paul Kelly.

Jon.

    ________ 
     / /     		Please reply to cook@alpha.ces.cwru.edu
    / /      
\__/ /___/