Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!ut-sally!husc6!endor!reiter From: reiter@endor.harvard.edu (Ehud Reiter) Newsgroups: comp.arch Subject: Re: Connection Machine Argument Message-ID: <827@husc6.UUCP> Date: Fri, 5-Dec-86 13:55:18 EST Article-I.D.: husc6.827 Posted: Fri Dec 5 13:55:18 1986 Date-Received: Fri, 5-Dec-86 21:08:08 EST References: <745@husc6.UUCP> <246@think.COM> Sender: news@husc6.UUCP Reply-To: reiter@harvard.UUCP (Ehud Reiter) Distribution: na Organization: Aiken Computation Lab, Harvard University Lines: 78 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)