Path: utzoo!attcan!uunet!snorkelwacker!tut.cis.ohio-state.edu!purdue!mentor.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: comp.arch
Subject: Re: Architecture questions
Summary: Reading from a buffer
Message-ID: <2549@l.cc.purdue.edu>
Date: 13 Sep 90 12:48:17 GMT
References: <2531@l.cc.purdue.edu> <4043@auspex.auspex.com> <4056@auspex.auspex.com>
Organization: Purdue University Statistics Department
Lines: 60

In article <4056@auspex.auspex.com>, guy@auspex.auspex.com (Guy Harris) writes:
> >   "Reading from a buffer" in what sense?  Is this just an in-memory buffer
> >   being read by a transaction processing application - in which case I
> >   don't see how an *interrupt* would help, as a dumb old conditional
> >   branch testing whether the number of characters left in the buffer was
> >   zero would probably be *faster* than an interrupt (no tons of context so
> >   save, etc.), or is it something else?
> >
> >Er. You have an 8k buffer. Each branch takes 1 cycle to test, 1 cycle
> >if not taken. There goes 16k cycles. You're telling me that servicing
> >a trap is going to take 16k cycles?
> 
> OK, so what is the extra magic instruction here?  I assume it basically
> amounts to a block move; if the basic "reading from the buffer"
> operation is done with a loop, only terminated with a trap instread of a
> conditional branch, the question is whether servicing the trap takes
> longer than the conditional branch at loop termination (which may be an
> untaken branch, depending on the code in the loop).

In computer generation of random variables, essentially all efficient methods
take a random number of input items.  These items may even be bits.  I believe
that this is an obvious case of a buffered read.  Keep in mind that in a 
Monte Carlo calculation, millions are not that large.

Now it is possible to check at certain times the status of the buffer, and to
have policies to greatly reduce the frequency of a buffer being empty, even
to the extent that this will rarely happen at all.  But it must be provided
for.  It is not at all difficult to have a situation where billions of reads
can be performed, with the probability of a read finding the buffer empty 
being so low that the great bulk of runs will never have an interrupt.

If the items being read are bits, the problems are even worse.  One wants the
bits to be in fast memory, such as registers.  Now we have the following 
situation, to read one bit:

	if(nbits == 0){
		if(nbuf == 0)BUFREFILL;
		read_from_buffer;
		nbits = REGSIZE;}
	nbits -= 1;
	getbit;
	adjust so that the next time, the next bit will be obtained;

and then use the bit.  If we wish to do a conditional transfer on the bit,
a very common situation,  shifting and conditional transfer will eliminate
one operation if tests for overflow and/or carry are available.  This is not
present in the HLLs, so is it present in the architecture any more?

The algorithms which would use this are efficient from the standpoint that
few bits are used, and only simple computations are made (for this purpose,
a multiplication is not simple).  Since we are interested in random output,
the result of this operation is not needed per se--a totally different result
generated by a totally different algorithm can be used.  These far more 
complicated algorithms (from the standpoint of the amount of actual bit
processing which is done) will run far fasted, so that these algorithms
are not even going to be coded.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet)	{purdue,pur-ee}!l.cc!cik(UUCP)