Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!linus!decvax!harpo!seismo!hao!hplabs!sri-unix!mark%umcp-cs@UDel-Relay From: mark%umcp-cs@UDel-Relay@sri-unix.UUCP Newsgroups: net.ai Subject: maximum speed Message-ID: <4289@sri-arpa.UUCP> Date: Tue, 16-Aug-83 20:33:29 EDT Article-I.D.: sri-arpa.4289 Posted: Tue Aug 16 20:33:29 1983 Date-Received: Fri, 19-Aug-83 01:54:03 EDT Lines: 18 From: Mark Weiser This *maximum* time business needs further ground rules if we are to discuss it here (which we probably shouldn't). For instance, the argument that communication and multiplcation paths don't matter in an nxn matrix multiply, but that the limiting step is the summation of n numbers, seems to allow too much power in specifying components. I am allowed unboundedly many processors and communication paths, but only a tree of adders? I can build you a circuit that will add n numbers simultaneously, so that means the *maximum* speed of an nxn matrix multiply is constant. But it just ain't so. As n grows larger and larger and larger the communication paths and the addition circuitry will also either grow and grow and grow, or the algorithm will slow down. Good old time-space tradeoff. (Another time-space tradeoff for matrix multiply on digital computers: just remember all the answers and look them up in ROM. Result: constant time matrix multiply for bounded n.)