Ken Batcher, full name Kenneth Edward Batcher (December 1935 – August 2019) was an emeritus professor of
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
at
Kent State University
Kent State University (KSU) is a public research university in Kent, Ohio. The university also includes seven regional campuses in Northeast Ohio and additional facilities in the region and internationally. Regional campuses are located in As ...
. He also worked as a
computer architect at
Goodyear Aerospace
Goodyear Aerospace Corporation (GAC) was the aerospace and defense subsidiary of the Goodyear Tire and Rubber Company. The company was originally operated as a division within Goodyear as the Goodyear Zeppelin Corporation, part of a joint project ...
in
Akron, Ohio
Akron () is the fifth-largest city in the U.S. state of Ohio and is the county seat of Summit County, Ohio, Summit County. It is located on the western edge of the Glaciated Allegheny Plateau, about south of downtown Cleveland. As of the 2020 C ...
for 28 years.
Early life and education
He was born in December 1935 in Queens, New York City, to Lois and Ralph Batcher. He died in August 2019 in Stow Ohio. 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. He graduated from
Brooklyn Technical High School
Brooklyn Technical High School, commonly called Brooklyn Tech and administratively designated High School 430, is an elite public high school in New York City that specializes in science, technology, engineering, and mathematics. It is one of th ...
.
Batcher graduated from
Iowa State University
Iowa State University of Science and Technology (Iowa State University, Iowa State, or ISU) is a public land-grant research university in Ames, Iowa. Founded in 1858 as the Iowa Agricultural College and Model Farm, Iowa State became one of the n ...
with
B.E.
A Bachelor of Engineering (BEng) or a Bachelor of Science in Engineering (BSE) is an academic undergraduate degree awarded to a student after three to five years of studying engineering at an accredited college or university.
In the UK, a Bache ...
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 which 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 (U of I, Illinois, University of Illinois, or UIUC) is a public land-grant research university in Illinois in the twin cities of Champaign and Urbana. It is the flagship institution of the University ...
.
His 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 processing in Flynn's taxonomy. SIMD can be internal (part of the hardware design) and it can be directly accessible through an instruction set architecture (ISA), but it should ...
128 x 128 processor array with additional CPU rows for
fault-tolerance
Fault tolerance is the property that enables a system to continue operating properly in the event of the failure of one or more faults within some of its components. If its operating quality decreases at all, the decrease is proportional to the ...
) which was located at the
NASA
The National Aeronautics and Space Administration (NASA ) is an independent agency of the US federal government responsible for the civil space program, aeronautics research, and space research.
NASA was established in 1958, succeeding t ...
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 empl ...
, and is now in the
Smithsonian. This unit predates
Danny Hillis
William Daniel "Danny" 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 paralle ...
'
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 the ...
's
Connection Machine
A Connection Machine (CM) is a member of a series of massively parallel supercomputers that grew out of doctoral research on alternatives to the traditional von Neumann architecture of computers by Danny Hillis at Massachusetts Institute of Techno ...
* 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 maritime service branch of the United States Armed Forces and one of the eight uniformed services of the United States. It is the largest and most powerful navy in the world, with the estimated tonnage of ...
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.
He 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](_blank)
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 a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operation ...
Eckert-Mauchly Award for his pioneering work on parallel computers. He holds 14 patents.
In 2007, Batcher was awarded the
IEEE
The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operation ...
Seymour Cray Computer Engineering Award
The Seymour Cray Computer Engineering Award, also known as the Seymour Cray Award, is an award given by the IEEE Computer Society, to recognize significant and innovative contributions in the field of supercomputer, high-performance computing. The ...
; ''"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."''
He is credited with discovering two important parallel sorting algorithms: the
odd-even mergesort and the
bitonic mergesort.
Donald E. Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
. ''The Art of Computer Programming
''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of compu ...
.'' ''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 pro ...
and Searching
Searching or search may refer to:
Computing technology
* Search algorithm, including keyword search
** :Search algorithms
* Search and optimization for problem solving in artificial intelligence
* Search engine technology, software for findi ...
''. 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 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 instructions ...
is a device for turning
compute-bound
{{Unreferenced, date=April 2007
In computer science, a computer is CPU-bound (or compute-bound) when the time for it to complete a task is determined principally by the speed of the Central processing unit, central processor: processor utilization ...
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. This is the opposite of a task being CPU bo ...
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
See also
*
Batcher odd–even mergesort
Batcher's odd–even mergesort
is a generic construction devised by Ken Batcher for sorting networks of size O(''n'' (log ''n'')2) and depth O((log ''n'')2), where ''n'' is the number of items to be sorted. Although it is not asympt ...
*
Bitonic sorter
Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O(n\log^2(n)) comparators and have ...
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
Computer designers
Computer systems researchers
Computer hardware researchers
Computer hardware engineers
Theoretical computer scientists
American computer scientists
American electrical engineers
Fellows of the Association for Computing Machinery
Kent State University faculty
Grainger College of Engineering alumni
People from Akron, Ohio
Living people
Seymour Cray Computer Engineering Award recipients
1935 births