microcode, compilers, and supercomputer architecture

From: Eric Smith <eric_at_brouhaha.com>
Date: Mon Apr 5 03:36:54 1999

> Again, you used the word *assembly* and that implies my point.

Now you've lost me completely. You were quoting your own writing, not
mine. I didn't even *mention* "assembly" in my posting, except in quoting
you.

> Halting problem (P vs NP) difficulties aside,

In the proposed scenario, the halting problem isn't relevant. To test whether
any particular tentative microcode solution is acceptable, it is only
necessary to determine whether simulating its operation for a finite period of
time causes it to produce the desired output, given suitable test vectors as
input. It may be the case that this method rejects microcode that would
produce the desired output after a longer period of time, but rejecting such
"solutions" is actually beneficial and even desirable in this context.

> I have never seen the situation
> in which the resultant output of a language translator could not be further
> optimised, with the exception of trivial cases.

I've never seen the situation in which human-generated code could not be
further optimized, with the exception of trivial cases. Your assertion
does not contradict my claims. Of course, this brings up the issue that
"trivial" is not objectively quantifiable. One could perhaps credibly argue
that a trivial code sequence is one for which no further optimization is
possible. I'm not taking that position, but simply pointing out the
difficulty in basing arguments on non-objective statements.

In point of fact, I've seen huge amounts of human-generated code that was
nowhere near as optimal as code that a compiler would generate.

All this proves is that neither humans nor compilers tend to produce
optimal code. It says nothing about which tends to produce more optimal
code.

> The value that you ascribe to your time, notwithstanding.

You are certainly determined to keep time out of this discussion, and
it's not surprising. Since I've already conceded the infinite-time case,
I propose that we restrict further discussion of this topic to the
finite-time case. And in particular, since I'm not living in an ivory
tower, I'd really like to restrict it to the finite-and-practical time
case. Admittedly "practical" in this case is somewhat subjective, although
in any given real-world scenario it can usually be quantified.

> You argument, again, is the value that you place on your time, and not the
> quality of your intellect.

My argument is that in the real world, a solution is needed in a certain
period of time. A solution that is too late is of lesser or even no value.
Therefore if I can use four weeks of my time to write a compiler and two weeks
to slightly tweak the output of that compiler, and thereby reach a better
solution than I would after spending twelve weeks of my time working directly
on the problem with no compiler, I believe it is accurate to state that the
compiler generated better code than I would have by myself.

> I maintain that the computer, no matter the
> skill of the algorithm, is always to fall short of human productivity.
> In this, I agree with such notable researchers as Roger Penrose and Douglas
> R. Hofstadter. Have you read Godel, Escher, and Bach: The Eternal Golden
> Braid?

Yes, I have. There is nothing in the references you cite which proves or
even posits that a computer can't produce a better solution than a human
given a sufficiently limited problem domain. I think Penrose and Hofstadter
would be surprised that you are trying to misapply their results in this
manner.

Penrose in particular only argues against strong AI. I happen to agree with
his some of his conclusion, despite finding some of the specific arguments he
uses to be flawed. As it happens, I also don't accept his premise (which he
presents as a conclusion, though he gives no viable supporing evidence) that
strong AI is not possible because computers aren't subject to quantum
uncertainty.

But we're not talking about strong AI here. We are in fact very far removed
from it, since we are specifically describing a very precisely defined problem
for which the correctness and merit of solutions is both objective and easily
quantifiable.

> Here, again, you base your argument on your lack of skill and capacity, not
> on the limitations of algorithms.

Yes, precisely. In my specific example, the computer has better capacity for
doing data flow analysis than I do. Therefore, in this limited problem
domain, the computer is *better* at a portion of the microcode generation
process than I am, given a finite time limit.

Another example of this would be using a computer to generate solutions to the
Universal Turing Machine "busy beaver" problem, something I experimented with
in Junior High School. In the general case, a human would do better than a
computer at solving this problem, partially because of the halting problem.
But as soon as you introduce the constraint of finding solutions with an upper
bound on the number of UTM cycles, it becomes clear that a computer is *much*
better at solving this problem than a human.

Are you simply taking the a priori position that computers can't be better
than humans at certain "intellectual" tasks because you find the concept to
be offensive?

> Your argument is that no human can perform the act of a computer, and this
> is shear lunacy.

I've never asserted anything even similar to that. Obviously it can be simply
shown that a human is capable of "playing computer" and executing the same
algorithm the computer would use. Therefore the worst case for the human is
to do only as well as the computer, but the best case is that the human can
come up with a better method than can be easily expressed as an algorithm.

However, given a constraint on the available time (finite and relatively
short), it is entirely possible that the human will *not* come up with as good
a solution as the computer.

As I keep stating and restating, my position is that for a limited problem
domain and a limited available time, a computer may be able to produce a
better solution than a human.

What part of this is it so difficult for you to understand or accept?

In this case, I'm stating that the microcode compiler (which I spent four
weeks developing) produced better output in a few minutes than I could have
generated without it in ten weeks. Therefore, by any reasonable metric
the compiler did in fact produce better code than the human, since ten
weeks were not available.

I'm sure we've bored everyone else to tears with this discussion. Since
you insist on presenting arguments that don't apply to the limited time
constraint, which is the only case in controversy, I suggest we take
any further discussion of this list.
Received on Mon Apr 05 1999 - 03:36:54 BST