phjk@doc.ic.ac.uk (Paul H J Kelly) (03/01/90)
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.
cook@pjd.CES.CWRU.Edu (Jonathan E. Cook) (03/04/90)
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 / / \__/ /___/