🚀 go-pugleaf

I recently posted a comment on the net criticizing the Connection Machine
architecture of a large hypercube of 1-bit processors.  Very briefly, my
argument was that it was foolish to build such a system, because since
the hypercube interconnect was so expensive (O(n*n) in number of processors),
it would dominate the cost of the system, and thus there was little cost
savings, but a large performance penalty, in using small processors at the
nodes instead of large ones.  I've received a number of responses, and here
is my reply to these replies:

1)  My original argument was based on trying to build such a system with
wafer-scale integration, and a number of people criticized this assumption.
Now, obviously the question of how important wafer-scale integration will
be in the future has not been settled, but the same arguments also apply
to conventional systems, although in a much messier fashion.  Just as you
can prove that a hypercube requires O(n**2) space in a 2-D system, you can
prove that a hypercube requires O(n**1.5) in a 3-D system, so the space
devoted to the hypercube interconnect will eventually dominate the space
devoted to the processors, which grows as O(n).  The problem is that the
relationship between space and cost is much clearer in a chip, where
everything is implemented in silicon, than it is in a conventional system,
where wires, back-plane connectors, and chips all have different costs.
Nevertheless, one can point out that, for example, in a hypercube the amount
of wiring needed on the PC boards and the size of the backplane connectors
is at least a linear function of the number of processors on the PC board.
In other words, the density of a hypercube may be limited by board and
connector constraints, not by chip density - and any architecture that can't
take advantage of improving chip technology is in trouble.

2)  A number of people have made arguments to the effect that a 32 bit
processor, for example, would require a 32-bit wide interconnect, which would
then increase the cost of the interconnect system by a factor of 32.
I think, though, that the questions of how big the processors are and how
wide the interconnect is must be addressed separately.  I am not trying
to argue that a 32-bit interconnect is better than a 1-bit interconnect -
I am arguing that a 32-bit processor costs little more than a 1-bit
processor, in this context, and, at least for some applications, would
give better performance than a 1-bit processor.  There may of course
be applications (perhaps including the semantic nets which originally
motivated the Connection Machine) where in fact a 1-bit processor is
no better than a 32-bit processor, but as long as the hypercube of 32-bit
processors costs the same as the hypercube of 1-bit processors, and the 32-bit
system gives more performance for at least some applications, then I maintain
that the 32-bit system is superior.  If A and B cost the same, and B at least
sometimes performs better, then I should buy B, not A.
    Note, by the way, that the size of the network is only linear in the
network width, while it is quadratic (in VLSI) in number of processors - ie
a system of N 32-bit processors with a 32-bit wide interconnect is far cheaper
than a system of 32*N 1-bit processors with a 1-bit wide interconnect.

3)  A number of people have also said that I'm missing the point of the
Connection Machine, which is a broader concept than the current implementation.
Fine - the only point I'm trying to make here is that a hypercube of tiny
processors is a bad idea.

4)  A number of people have mentioned Hillis's book THE CONNECTION MACHINE.
I have in fact read the book, and I have a number of criticisms of it:
   a)  The question of how costly the interconnect is is not addressed.
Indeed, the book seems to imply that the cost of a Connection Machine
will rise linearly with the number of processors, and I think this is
simply not true, because in either 2-D or 3-D, the size of a hypercube
interconnect rises much faster than linear.
   b)  The book justifies using small processors because they give more
processing power per unit of area than large processors.  The whole thrust
of my argument, of course, has been that when one looks at the area of the
complete system, as opposed to the area devoted to processors, then it is
the large processors which are more efficient.
   c)  When comparing algorithms on a conventional system to algorithms on
a Connection Machine, the book only looks at simple algorithms.  For
instance, claims that the Connection Machine is much faster at database
lookup than uniprocessors assume that the uniprocessors are searching
the database linearly, instead of using indexes;  claims that the
Connection Machine is much faster at convolutions assume that the
uniprocessors are convolving in the straightforward way, instead of
using FFT's; etc.  Comparisons should be made against the best uniprocessor
algorithms, not the worst.

					Ehud Reiter
					reiter@harvard	  (ARPA,UUCP)