JOSH@YKTVMH.BITNET ("Josh Knight") (12/30/89)
In <1989Dec29.014753.24266@phri.nyu.edu> roy@phri.nyu.edu (Roy Smith) writes: > Just to be obnoxious (and thought provoking), postulate a hardware > implementation in which a 32x32->64 bit integer multiply is faster than a > 32+32->32+carry bit integer addition. Estimate the change in coding habits > and compiler technology caused by this new technology. Use additional > pages if necesary. Well, that provoked some thoughts, but perhaps not the ones intended. In particular Winograd's (1965) work on the lower bound to the time required to do addition applies equally well multiplication: the bound was on computing a group operation (this doesn't fit the problem, -5 points :-), which describes both modulo addition AND multiplication on fixed word sizes. In Winograd's later (1967) work on a lower bound for the time for multiplication, he speculates (p 801): "The code used to show that the lower bound of Section 4 can be approached was quite different from the code used in [2], to obtain the similar result. Moreover, it seems that the circuit which translates from one code to another is a rather complicated one. This leads to the conjecture that if the same code is being used both for multiplication modulo N and for addition modulo N, at least one of the circuits will require an amount of time much larger than the lower bound." (NOTE: [2] refers to Winograd 1965) Thus one guesses that the an entirely different addressing scheme will need to be used as the current encoding of addresses usually requires a fast addition somewhere (e.g. pointer arithmetic). I.e. if the multiplication is faster than the addition, it's going to be hard to use current array placement conventions. Looking at Winograd's "limits" work reminds me of something more cosmic (and even less related to comp.arch, but what the heck): specifically the work on the physical limits of computation and when these limits might be reached (a question that has appeared here before). There's a Scientific American article (Bennett and Landauer 1985) and an issue of the IBM Journal of Research and Development with several articles on the topic. This issue "notes the 35th anniversary of Rolf Landauer" with IBM and leads off with a very mind bending (at least for me) article by John Archibald Wheeler. Which (finally) reminds me of Freeman Dyson's speculations on the survival and perceptions of life in a dying Universe. Oh well, it's the end of the 80s. The refer format bibliography may justify the otherwise marginal value of this posting. I threw in the reference to Wallace multipliers just for the heck of it, but I don't have a Dyson citation handy...there is discussion and reference to the work in his latest book (1987?). Happy New Year! Josh Knight josh@ibm.com, josh@yktvmh.bitnet Disclaimer: I don't speak for my employer. - - - - - - - - - - - - - - - - cut here - - - - - - - - - - - - - - - %T On the Time Required to Perform Addition %A S. Winograd %J Journal of the ACM %V 12 %N 2 %P 277-285 %D April 1965 %T On the Time Required to Perform Multiplication %A S. Winograd %J Journal of the ACM %V 14 %N 4 %P 277-285 %D October 1967 %T A Suggestion for a Fast Multiplier %A C.S. Wallace %J IEEE Trans Electronic Computers %V 13 %P 14-17 %D February 1964 %T The Fundamental Physical Limits of Computation %A Charles H. Bennett %A Rolf W. Landauer %J Scientific American %D July 1985 %P 48-56 %T World as system self-synthesized by quantum networking %A John Archibald Wheeler %J IBM J R&D %V 32 %N 1 %P 4-15 %D January 1988 %T Notes on the history of reversible computation %A Charles H. Bennett %J IBM J R&D %V 32 %N 1 %P 16-23 %D January 1988 %T Communication: Miniaturization of electronics and its limits %A R.W. Keyes %J IBM J R&D %V 32 %N 1 %P 24-28 %D January 1988 %T Information transport obeying the continuity equation %A Tommaso Toffoli %J IBM J R&D %V 32 %N 1 %P 29-36 %D January 1988 %T Origin of life and physics: Diversified microstructure - Inducement to form Information-Carrying and knowledge Accumulating Systems %A Hans Kuhn %J IBM J R&D %V 32 %N 1 %P 37-46 %D January 1988 %T Density of states of one-dimensional random potentials %A Paul Erdos %J IBM J R&D %V 32 %N 1 %P 47-51 %D January 1988 %T Bloch electron in a magnetic field: Mixed dimensionality and the magnetic-field-induced generalized quantum Hall effect %A Mark Ya. Azbel %J IBM J R&D %V 32 %N 1 %P 52-57 %D January 1988 %T Residual resistivity dipoles, electromigration, and electronic conduction in metallic microstructures %A R.S. Sorbello %A C.S. Chu %J IBM J R&D %V 32 %N 1 %P 58-62 %D January 1988 %T Coherent and sequential tunneling in series barriers %A M. Buttiker %J IBM J R&D %V 32 %N 1 %P 63-75 %D January 1988 %T Diffusion from an entrance to an exit %A Michael E. Fisher %J IBM J R&D %V 32 %N 1 %P 76-81 %D January 1988 %T Band tails, path integrals, instantons, polarons and all that %A M.H. Cohen %A M.Y. Chou %A E.N. Economou %A S. John %A C.M. Soukoulis %J IBM J R&D %V 32 %N 1 %P 82-92 %D January 1988 %T Fundamental questions in the theory of electromigration %A A.H. Verbruggen %J IBM J R&D %V 32 %N 1 %P 93-98 %D January 1988 %T Tunneling times and a quantum clock %A C. Foden %A K.W.H. Stevens %J IBM J R&D %V 32 %N 1 %P 99-102 %D January 1988 %T Coherent voltage oscillations in small normal tunnel junctions and the crossover to the incoherent regime %A Yuval Gefen %J IBM J R&D %V 32 %N 1 %P 103-106 %D January 1988 %T Relative stability in nonuniform temperature %A N.G. van Kampen %J IBM J R&D %V 32 %N 1 %P 107-111 %D January 1988 %T Boundary-layer theory for the extremely underdamped Brownian motion in a metastable potential %A H. Risken %A K. Vogel %A H.D. Vollmer %J IBM J R&D %V 32 %N 1 %P 112-118 %D January 1988 %T Bistability in active circuits: Application of a novel Fokker-Plank approach %A Peter Hanggi %A Peter Jung %J IBM J R&D %V 32 %N 1 %P 119-126 %D January 1988 %T Quantum noise and quantum Langevin equations %A G.W. Gardiner %J IBM J R&D %V 32 %N 1 %P 127-136 %D January 1988 %T Symmetry and transport in disordered systems %A John Pendry %J IBM J R&D %V 32 %N 1 %P 137-143 %D January 1988 %T Correlated discrete transfer of single electrons in ultrasmall tunnel junctions %A K.K. Likharev %J IBM J R&D %V 32 %N 1 %P 144-158 %D January 1988