Path: utzoo!attcan!uunet!ncrlnk!ncr-sd!hp-sdd!hplabs!oracle!hqpyr1!csimmons
From: csimmons@hqpyr1.oracle.UUCP (Charles Simmons)
Newsgroups: comp.arch
Subject: Re: RISC v. CISC --more misconceptions
Message-ID: <475@oracle.UUCP>
Date: 3 Nov 88 10:38:01 GMT
References: <156@gloom.UUCP> <18931@apple.Apple.COM> <40@sopwith.UUCP> <998@l.cc.purdue.edu>
Sender: news@oracle.uucp
Reply-To: csimmons@oracle.UUCP (Charles Simmons)
Organization: Oracle Corporation, Belmont CA
Lines: 31

In article <998@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes:
>There are many other operations which are cheap in hardware and expensive in
>software.  Maybe we should have a "competition" to see how many operations
>we can come up with for which silicon can do a quick, efficient, accurate job,
>but which are clumsy and expensive in software.
>
>I will toss in a few for starters.
>
>	Find the distance to the next one in a bit stream FAST.  It would
>be good to have an exception handler if one is not found.  I am considering
>algorithms not worth implementing if the operation is slow.

I once had a program that needed the above algorithm (I think we
ended up using a floating point normalize, which was still fairly slow).
In the same program, one of the algorithms that we really wanted was

	Find all legal moves for an Othello board.

If you have 1 72-bit register, this can be done in roughly 100 instructions.
With dedicated silicon, I think you can implement this with something
like 1024 gates.  Depending on the exact implementation of the silicon,
using the dedicated silicon would probably take about 10 instructions.

If that instruction is too high level, there are interesting things
one can do if a few instructions existed for permuting the bits in
a register.  For example:  pretend that the register holds an 8x8
board.  Now, rotate the board 90 degrees.  Or reflect the board about
an axis.  Or, permute the board so that the diagonals through the
board are laid end to end...

-- Chuck