Saturday, September 17, 2005

Ray Miller's Memoirs


The link to a function at UMD to commemorate the career of Ray Miller is this. The following is the introduction to the function:


Prof. Ray Miller, who retired from our department in 2002, is truly one of the pioneers of the field of computer science. He has had three successful careers – the first at IBM, where he helped build one of the world’s foremost computer science research programs and worked with many of the other leading theoretical computer scientists of his generation – people like Dick Karp, Shmuel Winograd and Nick Pippinger. Ray then had a second career at Georgia Tech,
...


This is a picture of Karp and Miller. The following "relevant part" is excerpted from pages 25-26 of memoirs of Ray Miller (a PDF link):


Upon returning to IBM Research from Cal Tech in the summer of 1963 I was ready to look into some new areas of research. Thus, it was quite appealing when Herman Goldstine, the Director of the Mathematical Sciences Department, suggested to Dick Karp, Sam Winograd, Larry Horwitz and me that looking into parallel computation might be of some interest. Even though this was long before parallel computation was on the minds of many, there was already a clear indication that parallelism could be used to speed up some special purpose computational tasks. IBM had a product developed for the oil industry called the "convolver box". This was a special purpose device that could be attached to the main bus of an IBM computer to do convolutions very rapidly. Convolution was used extensively in oil exploration for the analysis of soundings taken over land and sea to show the deep structure of the earth layers and expose potential locations where oil might be found. With this suggestion we started to look at parallel computation. We designed approaches, algorithms and designs, for many different special purpose computations: parenthesis checking, macro-instruction execution, the Cooley-Tukey convolution algorithm, and others. Our design for the Cooley-Tukey algorithm even rated a footnote in their original paper "An Algorithm for the Machine Computation of Complex Fourier Series" in Mathematics of Computation, April 1965. We published a paper in JACM on uniform recurrence equations that described how parallelism could be used to speed up the numerical computation of systems of differential equations. After a while, the designing of parallel algorithms for these various tasks seemed to be getting quite repetitive to Dick Karp and me, and this led us to realize that there was a hidden approach that we seemed to be using over and over. We formulated this underlying structure, which we called "computation graphs" and published the paper, "Properties of a Model of Parallel Computations: Determinacy, Termination, Queueing" in the SIAM Journal of November 1966. In 1966 this was the only SIAM Journal, but now they publish a number of journals in specialized areas. Computation graphs proved to be quite effective for designing inner loops of computations, but were limited in not 25 having more general computation structures, such as conditional branching, that were needed for more general computations. This led us to a more general model that we termed, "Parallel Program Schemata". We wrote a long paper about these schemata which was finally published in JCSS in May 1969. I continued to work on parallelism even though Dick Karp decided to leave IBM to become a faculty member at Berkeley with a joint appointment in computer science and operations research. I thought it was quite surprising that Dick left IBM at that time because within only a few more months he would have had 10 years service with IBM and thus been vested for retirement benefiets. I wrote another paper on parallel program schemata that discussed some undecidability results based on a schema not possessing the property that we called "repetition freeness", and this paper was published in the first issue of the SIAM Journal of Computing in March 1972.

No comments: