Kenneth Edward Batcher was born on December 27, 1935 in Queens, New York, to Lois and Ralph Batcher. His parents met at Iowa State University and later relocated to New York City after graduation. His father, Ralph R. Batcher, was the Chief Engineer of The A. H. Grebe Radio Company until its bankruptcy in 1932.[2]
Batcher published several technical papers and owns 14 patents of his own. "He discovered two parallel sorting algorithms: the odd-even mergesort and the bitonic mergesort". He is also a discoverer of scrambling data method in a random access memory which allows accesses along multiple dimensions. These memories were used in the STARAN and the MPP parallel processors.[3][5]
Awardsedit
In 1980, he received an Arnstein Award presented by Goodyear Aerospace Corporation for technical achievement.[3]
In 1990, Batcher was awarded the ACM/IEEEEckert-Mauchly Award for his pioneering work on parallel computers. He holds 14 patents.
In 2007, Batcher was awarded the IEEESeymour Cray Computer Engineering Award; "For fundamental theoretical and practical contributions to massively parallel computation, including parallel sorting algorithms, interconnection networks, and pioneering designs of the STARAN and MPP computers."
Batcher is known for his half-serious, half-humorous definition that "A supercomputer is a device for turning compute-bound problems into I/O-bound problems."
Publicationsedit
Sorting Networks and their Applications, 1968 Spring Joint Computer Conference, AFIPS Proc. vol. 32, pp 307–314.
On the Number of Stable States in a NOR Network, IEEE Trans. on Computers, vol. EC-14, no. 6, pp 931–932, Dec. 1965.
The Multi-Dimensional Access Memory in STARAN, IEEE Trans. on Computers, vol. C-26, no. 2, pp 174–177, Feb. 1977.
Design of a Massively Parallel Processor, IEEE Trans. on Computers, vol. C-29, no. 9, pp 836–840, Sept. 1980.
Bit-Serial Parallel Processing Systems, IEEE Trans. on Computers, vol. C-31, no. 5, pp 377–384, May 1982.
Adding Multiple-Fault Tolerance to Generalized Cube Networks, IEEE Trans. on Parallel and Distributed Systems vol. 5, no. 8, pp 785–792, Aug. 1994 (co-authored with C. J. Shih).
A Multiway Merge Sorting Network, IEEE Trans. on Parallel and Distributed Systems, vol. 6, no. 2, pp 211–215, Feb. 1995 (co-authored with De-Lei Lee).
Minimizing Communication in the Bitonic Sort, IEEE Trans. on Parallel and Distributed Systems, vol. 11, no. 5, pp 459–474, May 2000 (co-authored with Jae-Dong Lee).
Book chapters authored by Kenneth E. Batcheredit
The STARAN Computer, Infotech State of the Art Report on Supercomputers, vol. 2, pp 33–49, 1979.
MPP: A High-Speed Image Processor, Algorithmically Specialized Parallel Computers, edited by Snyder, Jamieson, Gannon, and Siegel, Academic Press, 1985, pp 59–68.
The Massively Parallel Processor System Overview, The Massively Parallel Processor, edited by J. L. Potter, The MIT Press, 1985, pp 142–149.
Array Unit, The Massively Parallel Processor edited by J. L. Potter, The MIT Press, 1985, pp 150–169.
Array Control Unit, The Massively Parallel Processor edited by J. L. Potter, The MIT Press, 1985, pp 170–190.
Staging Memory, The Massively Parallel Processor edited by J. L. Potter, The MIT Press, 1985, pp 191–204.
MPP System Software, The Massively Parallel Processor edited by J. L. Potter, The MIT Press, 1985, pp 261–275.
Retrospective: Architecture of a Massively Parallel Processor, 25 Years of the Int'l. Symposia on Computer Architecture - Selected Papers, edited by Gurindar Sohi, ACM Press, 1998, pp 15–16.[3]
U.S. patents with Kenneth E. Batcher as the inventor or one of the inventorsedit
The patent number is followed by the title and the year issued.[3]
Batcher, K. E., "Design of a Massively Parallel Processor," IEEE Transactions on Computers, Vol. C29, September 1980, 836–840.
External linksedit
Batcher's web page at Kent State University
University of Illinois (21 February 1962). MEETING OF THE BOARD OF TRUSTEES OF THE UNIVERSITY OF ILLINOIS(PDF). p. 1351.
Literatureedit
Leonard Uhr. Multi-Computer Architectures for Artificial Intelligence: Toward Fast, Robust, Parallel Systems. — John Wiley & Sons, 1987. — 358 p. — ISBN 9780471849797.
Laxmikant V. Kalé, Edgar Solomonik Sorting (англ.) // Encyclopedia of Parallel Computing : encyclopedia — Springer, 2011. — P. 1855–1861. — ISBN 978-0-387-09765-7.
Selim G. Akl Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : encyclopedia. — Springer, 2011. — P. 139–146. — ISBN 978-0-387-09765-7.
Sherenaz W. Al-Haj Baddar, Kenneth E. Batcher. Bitonic merging // Designing Sorting Networks: A New Paradigm. — Springer, 2012. — С. 2–5. — 148 с. — ISBN 978-1461418504.
Donald E. Knuth. Networks for sorting // The art of computer programming. — 2. — Addison-Wesley, 1998. — Т. 3. — С. 212–247. — 780 с. — ISBN 9780201896855.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Bitonic sorting // Introduction to algorithms. — 2. — MIT Press, 2001. — С. 608–611. — 984 с. — ISBN 9780070131514.
Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heribert Vollmer, Dorothea Wagner. Algorithms Unplugged. — Springer, 2010. — С. 36. — 406 с. — ISBN 9783642153280.
The SIMD Model of Parallel Computation. Robert Cypher, Jorge L.C. Sanz. — Springer, 2012. — С. 28. — 149 с. — ISBN 9783642153280.
Maurice Herlihy, Nir Shavit. The Art of Multiprocessor Programming, Revised Reprint. — Elsevier, 2012. — С. 292. — 536 с. — ISBN 9780123977953.
Russ Miller, Laurence Boxer. Bitonic sort on parallel computers // Algorithms Sequential & Parallel: A Unified Approach. — Cengage Learning, 2012. — С. 146–148. — 416 с. — ISBN 9781133366805.