Editing Ken Batcher

{{Short description|American computer scientist (1935–2019)}}

'''Kenneth Edward Batcher'''<ref>{{Cite web |url=https://archives.library.illinois.edu/erec/University%20Archives/0101802/02_volume_sections/1960-1962/19_meeting_1962-02-21.pdf |title=Archived copy |access-date=2018-03-05 |archive-date=2019-05-17 |archive-url=https://web.archive.org/web/20190517090537/https://archives.library.illinois.edu/erec/University%20Archives/0101802/02_volume_sections/1960-1962/19_meeting_1962-02-21.pdf |url-status=dead }}</ref> (December 27, 1935 – August 22, 2019) was an American academic who was emeritus professor of [[Computer Science]] at [[Kent State University]]. He also worked as a [[computer architecture|computer architect]] at [[Goodyear Aerospace]] in [[Akron, Ohio]] for 28 years.

==Background==
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 [[Alfred H. Grebe|A. H. Grebe]] Radio Company until its bankruptcy in 1932.<ref>[http://www.earlytelevision.org/batcher_articles.html/ Early Electronic Television, Early TV In New York City] {{Webarchive|url=https://web.archive.org/web/20170102001540/http://earlytelevision.org/batcher_articles.html |date=2017-01-02 }} Retrieved on 5 Mar 2018</ref>

Batcher graduated from [[Brooklyn Technical High School]],<ref name="kent"/> and then from [[Iowa State University]] with [[Bachelor of Engineering|B.E.]] degree in 1957. In 1964, Batcher received his Ph.D. in [[electrical engineering]] from the [[University of Illinois at Urbana-Champaign|University of Illinois]].

Batcher died in [[Stow, Ohio]] on August 22, 2019, at the age of 83.<ref>{{cite web |title=Kenneth E. Batcher |url=https://www.legacy.com/us/obituaries/ohio/name/kenneth-batcher-obituary?id=11701396 |website=Legacy |access-date=14 February 2024}}</ref>

==Career and achievements==
Among the designs he worked on at Goodyear were the:

* [[Goodyear MPP|Massively Parallel Processor]] (16,384 custom bit-serial processors {8 to a chip} organized in a [[SIMD]] 128 x 128 processor array with additional CPU rows for [[fault-tolerance]]) which was located at the [[NASA]] [[Goddard Space Flight Center]], and is now in the [[Smithsonian]]. This unit predates [[Danny Hillis]]' [[Thinking Machines Corporation]]'s [[Connection Machine]]
* The Goodyear [[STARAN]] associative processor arrays, a version of which (called ASPRO) was found in the [[US Navy]] [[Northrop Grumman E-2 Hawkeye]] radar planes.

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.<ref name="kent">[http://www.cs.kent.edu/~batcher/ Kenneth E. Batcher] Retrieved on 5 Mar 2018</ref><ref>[https://www.computer.org/web/awards/cray-kenneth-batcher/ Kenneth E. Batcher] {{Webarchive|url=https://web.archive.org/web/20181121103956/https://www.computer.org/web/awards/cray-kenneth-batcher/ |date=2018-11-21 }} Retrieved on 5 Mar 2018</ref>

==Awards==
In 1980, he received an ''Arnstein Award'' presented by Goodyear Aerospace Corporation for technical achievement.<ref name="kent"/>

In 1990, Batcher was awarded the [[Association for Computing Machinery|ACM]]/[[Institute of Electrical and Electronics Engineers|IEEE]] [[Eckert-Mauchly Award]] for his pioneering work on parallel computers.  He holds 14 patents.

In 2007, Batcher was awarded the [[Institute of Electrical and Electronics Engineers|IEEE]] [[Seymour 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 credited with discovering two important parallel sorting algorithms: the [[odd-even mergesort]] and the [[bitonic sorter|bitonic mergesort]].<ref>{{cite book| first = Thomas H. | last = Cormen | author-link = Thomas H. Cormen |author2=Charles E. Leiserson |author2-link=Charles E. Leiserson |author3=Ronald L. Rivest |author3-link=Ronald L. Rivest |author4=Clifford Stein |author4-link=Clifford Stein | title = [[Introduction to Algorithms]]| edition = 2e| publisher = MIT Press and McGraw-Hill | year = 2001| isbn = 0-262-03293-7 }}</ref><ref>[[Donald E. Knuth]]. ''[[The Art of Computer Programming]].'' ''Volume 3: [[Sorting algorithm|Sorting]] and [[Search algorithms|Searching]]''. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. {{ISBN|0-201-89685-0}}´</ref>

Batcher is known for his half-serious, half-humorous definition that ''"A [[supercomputer]] is a device for turning [[Compute bound|compute-bound]] problems into [[I/O bound|I/O-bound]] problems."''

==Publications==
*''Sorting Networks and their Applications'', 1968 Spring Joint Computer Conference, AFIPS Proc. vol. 32, pp 307–314.
'''As author or co-author in "Journal articles"'''<ref name="kent"/>
* ''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. Batcher==
* ''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.<ref name="kent"/>

==U.S. patents with Kenneth E. Batcher as the inventor or one of the inventors==
The patent number is followed by the title and the year issued.<ref name="kent"/>

* 3,183,363 ''Logic Mechanization System'', 1965 (multiple inventors)
* 3,300,762 ''Multiple Response Resolver Apparatus'', 1967
* 3,418,632 ''Means for Merging Sequences of Data'', 1968
* 3,428,946 ''Means for Merging Data'' 1969
* 3,605,024 ''Apparatus for Shifting Data in a Long Register'', 1971
* 3,681,781 ''Storing and Retrieval Method'', 1972
* 3,711,692 ''Determination of Number of Ones in a Data Field by Addition'', 1973
* 3,786,448 ''Multiple Access Plated Wire Memory'', 1974 (multiple inventors)
* 3,800,289 ''Multi-Dimensional Access Solid State Memory'', 1974
* 3,812,467 ''Permutation Network'', 1974
* 3,936,806 ''Solid State Associative Processor Organization'', 1976
* 4,314,349 ''Processing Element for Parallel Array Processors'', 1982
* 4,727,474 ''Staging Memory for Massively Parallel Processor'', 1988
* 5,153,843 ''Layout of Large Multistage Interconnection Networks'', 1992

==See also==
* [[Batcher odd–even mergesort]]
* [[Bitonic sorter]]

==References==
{{Reflist}}

*Batcher, K. E., "Design of a Massively Parallel Processor," ''IEEE Transactions on Computers'', Vol. C29, September 1980, 836–840.

==External links==
* [http://www.cs.kent.edu/~batcher/ Batcher's web page at Kent State University]
*  {{cite book |last=University of Illinois |date= 21 February 1962|title=MEETING OF THE BOARD OF TRUSTEES OF THE UNIVERSITY OF ILLINOIS|url=https://archives.library.illinois.edu/erec/University%20Archives/0101802/02_volume_sections/1960-1962/19_meeting_1962-02-21.pdf
|page=1351 }}

==Literature==
* 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}}.

{{Sorting}}

{{Authority control}}

{{DEFAULTSORT:Batcher, Ken}}
[[Category:1935 births]]
[[Category:2019 deaths]]
[[Category:Computer designers]]
[[Category:Computer systems researchers]]
[[Category:Computer hardware researchers]]
[[Category:Computer hardware engineers]]
[[Category:American theoretical computer scientists]]
<!--  bitonic sorting -->
[[Category:American electrical engineers]]
[[Category:1994 fellows of the Association for Computing Machinery]]
[[Category:Kent State University faculty]]
[[Category:Grainger College of Engineering alumni]]
[[Category:Brooklyn Technical High School alumni]]
[[Category:People from Akron, Ohio]]
[[Category:Seymour Cray Computer Engineering Award recipients]]