Kenneth Edward Batcher (December 27, 1935 – August 22, 2019) was an American academic who was emeritus professor of

Computer Science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

Kent State University Kent State University (KSU) is a Public university, public research university in Kent, Ohio, United States. The university includes seven regional campuses in Northeast Ohio located in Kent State University at Ashtabula, Ashtabula, Kent State ...

. He also worked as a computer architect at Goodyear Aerospace in

Akron, Ohio Akron () is a city in Summit County, Ohio, United States, and its county seat. It is the List of municipalities in Ohio, fifth-most populous city in Ohio, with a population of 190,469 at the 2020 United States census, 2020 census. The Akron metr ...

for 28 years.

Background

Kenneth Edward Batcher was born on December 27, 1935 in

Queens, New York Queens is the largest by area of the Boroughs of New York City, five boroughs of New York City, coextensive with Queens County, in the U.S. state of New York (state), New York. Located near the western end of Long Island, it is bordered by the ...

, 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. Batcher graduated from

Brooklyn Technical High School Brooklyn Technical High School, commonly called Brooklyn Tech and administratively designated High School 430, is a public specialized high school in New York City that specializes in science, technology, engineering, and mathematics. It is on ...

, and then from

Iowa State University Iowa State University of Science and Technology (Iowa State University, Iowa State, or ISU) is a Public university, public land-grant university, land-grant research university in Ames, Iowa, United States. Founded in 1858 as the Iowa Agricult ...

with

B.E. A Bachelor of Engineering (BEng) or a Bachelor of Science in Engineering (BSE) is an undergraduate academic degree awarded to a college graduate majoring in an engineering discipline at a higher education institution. In the United Kingdom, a Bac ...

degree in 1957. In 1964, Batcher received his Ph.D. in

electrical engineering Electrical engineering is an engineering discipline concerned with the study, design, and application of equipment, devices, and systems that use electricity, electronics, and electromagnetism. It emerged as an identifiable occupation in the l ...

from the

University of Illinois The University of Illinois Urbana-Champaign (UIUC, U of I, Illinois, or University of Illinois) is a public university, public land-grant university, land-grant research university in the Champaign–Urbana metropolitan area, Illinois, United ...

. Batcher died in Stow, Ohio on August 22, 2019, at the age of 83.

Career and achievements

Among the designs he worked on at Goodyear were the: * Massively Parallel Processor (16,384 custom bit-serial processors organized in a

SIMD Single instruction, multiple data (SIMD) is a type of parallel computer, parallel processing in Flynn's taxonomy. SIMD describes computers with multiple processing elements that perform the same operation on multiple data points simultaneousl ...

128 x 128 processor array with additional CPU rows for

fault-tolerance Fault tolerance is the ability of a system to maintain proper operation despite failures or faults in one or more of its components. This capability is essential for high-availability, mission critical, mission-critical, or even life-critical sys ...

) which was located at the

NASA The National Aeronautics and Space Administration (NASA ) is an independent agencies of the United States government, independent agency of the federal government of the United States, US federal government responsible for the United States ...

Goddard Space Flight Center The Goddard Space Flight Center (GSFC) is a major NASA space research laboratory located approximately northeast of Washington, D.C., in Greenbelt, Maryland, United States. Established on May 1, 1959, as NASA's first space flight center, GSFC ...

, and is now in the Smithsonian. This unit predates

Danny Hillis William Daniel Hillis (born September 25, 1956) is an American inventor, entrepreneur, and computer scientist, who pioneered parallel computers and their use in artificial intelligence. He founded Thinking Machines Corporation, a parallel super ...

Thinking Machines Corporation Thinking Machines Corporation was a supercomputer manufacturer and artificial intelligence (AI) company, founded in Waltham, Massachusetts, in 1983 by Sheryl Handler and Danny Hillis, W. Daniel "Danny" Hillis to turn Hillis's doctoral work at th ...

Connection Machine The Connection Machine (CM) is a member of a series of massively parallel supercomputers sold by Thinking Machines Corporation. The idea for the Connection Machine grew out of doctoral research on alternatives to the traditional von Neumann arch ...

* The Goodyear STARAN associative processor arrays, a version of which (called ASPRO) was found in the

US Navy The United States Navy (USN) is the naval warfare, maritime military branch, service branch of the United States Department of Defense. It is the world's most powerful navy with the largest Displacement (ship), displacement, at 4.5 millio ...

Northrop Grumman E-2 Hawkeye The Northrop Grumman E-2 Hawkeye is an American all-weather, carrier-capable tactical airborne early warning (AEW) aircraft. This twin-turboprop aircraft was designed and developed during the late 1950s and early 1960s by the Grumman Aircraft ...

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.Kenneth E. Batcher
Retrieved on 5 Mar 2018

Awards

In 1980, he received an ''Arnstein Award'' presented by Goodyear Aerospace Corporation for technical achievement. In 1990, Batcher was awarded the ACM/

IEEE The Institute of Electrical and Electronics Engineers (IEEE) is an American 501(c)(3) organization, 501(c)(3) public charity professional organization for electrical engineering, electronics engineering, and other related disciplines. The IEEE ...

Eckert-Mauchly Award for his pioneering work on parallel computers. He holds 14 patents. In 2007, Batcher was awarded the

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 mergesort. Donald E. Knuth. ''

The Art of Computer Programming ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive multi-volume monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. it consists of published volumes 1, 2, 3, 4A, and 4 ...

.'' ''Volume 3:

Sorting Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. # ordering: arranging items in a sequence ordered by some criterion; # categorizing: grouping items with similar p ...

and

Searching Searching may refer to: Music * " Searchin", a 1957 song originally performed by The Coasters * "Searching" (China Black song), a 1991 song by China Black * "Searchin" (CeCe Peniston song), a 1993 song by CeCe Peniston * " Searchin' (I Gott ...

''. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ´ Batcher is known for his half-serious, half-humorous definition that ''"A

supercomputer A supercomputer is a type of computer with a high level of performance as compared to a general-purpose computer. The performance of a supercomputer is commonly measured in floating-point operations per second (FLOPS) instead of million instruc ...

is a device for turning compute-bound problems into

I/O-bound In computer science, I/O bound refers to a condition in which the time it takes to complete a computation is determined principally by the period spent waiting for input/output operations to be completed, which can be juxtaposed with being CPU boun ...

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" * ''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.

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. * 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

References

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

External links

Batcher's web page at Kent State University
*

Literature

* Leonard Uhr. Multi-Computer Architectures for Artificial Intelligence: Toward Fast, Robust, Parallel Systems. — John Wiley & Sons, 1987. — 358 p. — . * Laxmikant V. Kalé, Edgar Solomonik Sorting (англ.) // Encyclopedia of Parallel Computing : encyclopedia — Springer, 2011. — P. 1855–1861. — . * Selim G. Akl Bitonic Sort (англ.) // Encyclopedia of Parallel Computing : encyclopedia. — Springer, 2011. — P. 139–146. — . * Sherenaz W. Al-Haj Baddar, Kenneth E. Batcher. Bitonic merging // Designing Sorting Networks: A New Paradigm. — Springer, 2012. — С. 2–5. — 148 с. — . * Donald E. Knuth. Networks for sorting // The art of computer programming. — 2. — Addison-Wesley, 1998. — Т. 3. — С. 212–247. — 780 с. — . * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Bitonic sorting // Introduction to algorithms. — 2. — MIT Press, 2001. — С. 608–611. — 984 с. — . * Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heribert Vollmer, Dorothea Wagner. Algorithms Unplugged. — Springer, 2010. — С. 36. — 406 с. — . * The SIMD Model of Parallel Computation. Robert Cypher, Jorge L.C. Sanz. — Springer, 2012. — С. 28. — 149 с. — . * Maurice Herlihy, Nir Shavit. The Art of Multiprocessor Programming, Revised Reprint. — Elsevier, 2012. — С. 292. — 536 с. — . * Russ Miller, Laurence Boxer. Bitonic sort on parallel computers // Algorithms Sequential & Parallel: A Unified Approach. — Cengage Learning, 2012. — С. 146–148. — 416 с. — . {{DEFAULTSORT:Batcher, Ken 1935 births 2019 deaths Computer designers Computer systems researchers Computer hardware researchers Computer hardware engineers American theoretical computer scientists American electrical engineers 1994 fellows of the Association for Computing Machinery Kent State University faculty Grainger College of Engineering alumni Brooklyn Technical High School alumni People from Akron, Ohio Seymour Cray Computer Engineering Award recipients