Registered: Oct 2003
Posts: 38

Im browsing one of the computer achictecture books by Hennessy and Patternson and come across this quote -

"Pitfall: Microcode implementing a complex instruction may not be faster than a sequence using simpler instructures"

Of course this is why RISC is actually useful. But one wonders what the NKS explanation of this is?

They are of course thinking of instructions and implementations that they engineer. But how is this true in the space of all possible simple programs? What is the landscape of this space?

This would be an interesting experiment to set up.

But its also interesting to think of it in terms of nks way of thinking. What does it mean for there to be on average no faster way of doing a computation other than with a set of simple primitives?

It may seems to imply that the computation is irreducible. But it might just be the case that the in the world of instruction sets, most possible cases happen to be quite decently covered by a few primitives. (or at least as well covered as they can be under the circumstances).

So im not sold that it "means" the computation is irreducible, but it does seem like it ought to mean something.

__________________
Everything is an expression.

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 551

Kovas,

I ran into a similar problem when I was just
beginning to write theorem proving programs.
For example, there are axiom systems for
propositional logic that use umpteen
axioms, some that use eight, and some,
like the one that comes down to us
from C.S. Peirce and Spencer Brown,
that uses only four initial axioms.
There might be additional oomph in
the more complicated axiom, but
the overhead bottleneck comes
at the point where you have
to decide which axiom to
use to advance a proof,
and many times you are
reduced to trying each
of them at random, so
the degree of the
branch point is
the critical
factor.

Jon Awbrey

Report this post to a moderator | IP: Logged