Path: utzoo!attcan!uunet!samsung!shadooby!mailrus!purdue!mentor.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: comp.arch
Subject: Uses for unusual instructions
Message-ID: <1743@l.cc.purdue.edu>
Date: 24 Nov 89 22:24:19 GMT
Reply-To: cik@l.cc.purdue.edu (Herman Rubin)
Organization: Purdue University Statistics Department
Lines: 78


Soem time ago, I posted to this group certain instructions which are cheap
in hardware and expensive in software.  I wish to discuss these and give
partial examples; the full examples are too lengthy and would provide little
insight.

The two instructions are to transfer conditionally on a bit, and to then
forget about this bit, and to find the spacing between ones in a random
bit stream.  There is also the question of the relative frequency of these
operations.  I will give adequate information on both points.

For the conditional transfer (ct), there are 4 instructions needed in general.
It can often be arranged that one of them can be omitted.  A typical
program would be

	count -= 1;
	if (count < 0) call getmorebits;
	shift bits by 1;
	transfer on {overflow, negative, low-order bit};

It is unnecessary to clear the bit; it will not be looked at again.

For the spacing between bits, doing it in a straightforward manner
involves similar problems.  On the machines I have seen, the instructions
would be

	i = j;
	clear *i; 	/* clear the bit */
	j = &( next one);
	in (not found) goto rareprocedure;
	result = j-i;

There are ways of eliminating the second operation in many cases, and there
are even ways to produce a buffer more quickly.

Now as for use.  Here is a computationally moderately efficient method of
generating exponential random variable from uniform input.

loop:	i = spacing between ones;
	switch (i){
	case 1: ct loop;
		int += 1;
		goto loop;
	case 2: goto nomask;
	case 3: j = spacing;
		goto quickmask;
	case 4: k = spacing;
		etc.

			}

This procedure uses case 1 50% of the time, case 2 25%, etc.  For 25% of
the time, 1 is added to the integer part; for 43% of the time, an exponetial
is produced by adding the integer part to a fraction, which is a masked 
uniform except in case 2, where there is no mask, and 32% of the time loop
is reentered with nothing done.  The expecte number of uses of spacing is
greater than 1.43, and 50% of the time ct is used.

This is not so efficient.  A more efficient one tries to get two at once.  
It starts out with a spacing, and the most ccmmon branch (8/15 probability)
has two occurrences of ct, the branches being equally likely to add 1 to
the integer or to go to the nomask output procedure.  In the next most
common branch (4/15), there are also two uses of ct, one of which is as
above, and the other one selects a random order between this and quickmask.

The point I am making is that these procedures, which only look at a few
bits before going to a final output stage, use these operations which are
quite simple in hardware, and rather expensive in software.  The spacing
procedure uses an average of 2 bits, and ct only one, yet these procedures
are quite expensive in software.  The use of hundreds of thousands or even
hundreds of millions of exponential random variables is quite common in
simulationa.

times ct is used is 50%, and the expected use of spacing is 
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP)