Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!psuvax1!brutus.cs.uiuc.edu!samsung!uunet!pdn!oz!alan
From: alan@oz.nm.paradyne.com (Alan Lovejoy)
Newsgroups: comp.arch
Subject: Re: BitBlt, new instructions for RISC.
Message-ID: <7488@pdn.paradyne.com>
Date: 27 Feb 90 20:04:09 GMT
References: <7466@pdn.paradyne.com< <BBC.90Feb25195510@legia.rice.edu>
Sender: usenet@pdn.paradyne.com
Reply-To: alan@oz.paradyne.com (Alan Lovejoy)
Distribution: usa
Organization: AT&T Paradyne, Largo, Florida
Lines: 113

In article <BBC.90Feb25195510@legia.rice.edu< Benjamin Chase <bbc@rice.edu> writes:
<alan@oz.paradyne.com writes:
<
<>In an email message to me, bbd@rice.edu wrote:
<>To which I attempted to reply via email. However:
<>[it failed]
<>So here is my reply:
<
<>I apologize:  I did not realize how easy it would be to misinterpret what I
<>wrote.
<
<How painfully true.  I'm bbc@rice.edu (as in British Broadcasting
<Company), not bbd@rice.edu.

Hey, shit happens :-) (translation: we all make mistakes, from little typos
to Great Social Blunders.  Peace, bro.).

<>  I did not mean to imply that pixels which are vertically sequential
<>are also stored sequentially in memory.  The point of my comment was how
<>"narrow" the screen is in terms of words of memory, to make it graphically :-)
<>obvious that many blits fall within a single word or two.
<
<But the _screen_ isn't narrow.  A modern monochrome display is 32
<(32 bit) words wide.

Well, I think ~30 words is "narrow."  It's a much less imposing number than
1024, which approximates the number of pixels along the x-axis.  But it
depends on your point of view, I guess.

<>The point about
<>vertical lines is that they always (unless they, or the pixels themselves,
<>are very thick) fall within one or two words horizontally.
<
<Yes, and ~1000 words vertically.  And these words are spaced at ~32
<intervals.  Thus, when you draw a vertical line, you get a word of
<screen memory, perform some operation on it to turn on or off ~1 bit
<of that word, and then write it back to screen memory.  Then, you get
<the next word, which is 32 words further along, and whoops, it's not
<in the data cache, because your silly fetcher got the next 3
<consecutive words of screen memory (which you won't be needing right
<now because your vertical line is so skinny and all), rather than the
<next 3 words spaced at 32 word offsets, which is what you really
<wanted it to do if you were drawing a vertical line.

Yep. That's why one "loads" the word from screen memory before "load"-ing
the word from the source bitmap, so that there are as many cycles as possible
between the load instruction which fetches the destination word and the 
first instruction which accesses that word.  This is where the 88k's multiple
independent functional units, full pipelining and register scoreboarding
really help.  But even so, one may in fact pay some of the performance penalty 
you describe, depending on the details of the situation.  Different hardware 
configurations exact different penalties for cache misses, especially in the 
case of the frame buffer.  Also, if there is a mask (stipple) bitmap, that 
adds  roughly 4 to 6 more cycles between the destination bitmap load and the 
first access of the loaded word.  One can also get REALLY agressive, and
have different versions of bitblt optimized for the the (tall, narrow) and
(short, wide) cases.  But best of all, the code for striding to the next line
(of each bitmap) can execute immediately after the loads for the first words in
those lines, but before acessing the loaded words, adding many cycles between 
first-word-in-line loads and first access to those words.  My code gets 
really aggressive :-).      

But what am I doing giving away my secrets like this!  

<>  In any case, characters are normally blitted in a loop which
<>writes a whole string to the screen, often soon followed by another.  So it 
<>is likely that the most frequently used characters would have their pixels
<>in the cache already.
<
<But that's only half the problem.  What about the screen memory that
<isn't in the cache because it won't fit?  (Especially when you're
<filling the cache with screen words that you won't be writing upon, as
<in my example above.)

The usual case FOR ME is to blit a string of characters whose glyphs are
one bit per pixel to a destination bitmap (often the screen) which is 8 bits 
per pixel.  The way I actually do this is to blit the character string to
a temporary one-bit-per-pixel destination bitmap (which can be treated as a
special case), then blit the temporary bitmap to the screen using a 
bit-depth-changing/pixel-value-translating algorithm.  This (bit-depth-changing
blit) algorithm provides even more cycles between the load-word-from-dest 
instruction and the first instruction accessing that word.  And of course,
in tends to shift performance considerations away from first word/last word
issues back toward inner-loop issues.  And it's a very big win, much more so
than one would think.

<Now, getting back to "new instructions for RISCs", sort of...  [I
<think most of this is from a brain-storming session one recent night
<that afflicted me and Preston Briggs. :-) ]
<
<Perhaps in the floating point slot of the superscalar instruction,
<you'd put (among other things?) little hints to the cache instead?
<Whisper gently into the processor's ear, saying "get the value in
<register N, and use that as a stride for yanking words into the cache
<until I tell you something different".

Check out the RPM-40.  It does something along these lines.  

In order for hardware to "go faster," it must either "do more work" per cycle 
or go through more cycles per second.  In order to "do more work per cycle," 
it must find more things it can do simultaneously or in parallel.  In order to 
do more things simultaneously/in parallel, it must have more parallel hardware,
more information per instruction, and instruction semantics which are composed 
of more primitive components. Also, the hardware must make fewer assumptions 
about the future, so that its behavior becomes more fully programable, allowing
greater optimization.  Obviously, the more information the instruction stream 
provides about what will happen in the future, the more work the hardware can 
do in advance (and in parallel with other things) to get ready for it.  

____"Congress shall have the power to prohibit speech offensive to Congress"____
Alan Lovejoy; alan@pdn; 813-530-2211; AT&T Paradyne: 8550 Ulmerton, Largo, FL.
Disclaimer: I do not speak for AT&T Paradyne.  They do not speak for me. 
Mottos:  << Many are cold, but few are frozen. >>     << Frigido, ergo sum. >>