A.M. TURING AWARD WINNERS BY...
BIRTH:

Charlotte, North Carolina, May 30, 1925

DEATH:

Valhalla, New York, July 16, 2002 

EDUCATION:

BSE (Bachelor of Science in Engineering, Duke University, mechanical engineering, 1946); Ph.D. (Duke University, Mathematics, 1953).

EXPERIENCE:

IBM T. J. Watson Research Laboratory, 1954-1992 

HONORS AND AWARDS: 

IBM Fellow (1972), Member, National Academy of Engineering (1979); Eckert-Mauchly Award (a joint award between the ACM and the IEEE Computer Society, 1985); Fellow, American Academy of Arts and Sciences (1986); ACM Turing Award (1987); Honorary Doctor of Science, Duke University (1988); IEEE Computer Society Pioneer Award (1989); IBM John E. Bertram Award for Sustained Excellence (1990); National Medal of Technology (1991); Member, National Academy of Sciences (1993); NEC Foundation Computers & Communications Prize(1994); National Medal of Science (1994); The Franklin Institute's Certificate of Merit (1996); Seymour Cray Computer Science and Engineering Award (1999); the Benjamin Franklin Medal (2000); Fellow of the Computer History Museum (2002).

John Cocke

United States – 1987
CITATION

For significant contributions in the design and theory of compilers, the architecture of large systems and the development of reduced instruction set computers (RISC); for discovering and systematizing many fundamental transformations now used in optimizing compilers including reduction of operator strength, elimination of common subexpressions, register allocation, constant propagation, and dead code elimination.

John Cocke was born in Charlotte, North Carolina, in 1925. His father Norman was the president of Duke Power Company (later Duke Energy) and a member of the Board of Trustees of Duke University. That connection made it natural for John to attend college there. He earned his BSE (Bachelor of Science in Engineering) in Mechanical Engineering in 1946 and his PhD in mathematics in 1956. After graduation he joined IBM and worked at the T.J. Watson Research Center until his retirement 37 years later.

John Cocke made fundamental contributions to the architecture of high performance computers and to the design of optimizing compilers. Starting in 1975 he led the 801 Minicomputer project in IBM, which began as a pure research project but later led to a commercial product. The 801 design philosophy was based on a tight coupling between—and simultaneous development of—the hardware and the compiler. The resulting architecture was unlike the then common practice of having many complex instructions built into the hardware. For example, the earlier IBM 7030 “Stretch” computer had 735 different instructions, including instructions for variable-length operands. Such a rich set of hardware operations proved useful for special programming situations, but the designers of high level language compilers found it very difficult to use them in creating compiled code.

Cocke decided instead to design the 801 with a small set of basic instructions optimized for use by compilers, which resulted in a simpler but faster machine. This had a broad impact on computer architecture research, and was later called the Reduced Instruction Set Computer (RISC) approach. Cocke and a small group of collaborators recognized that an appropriately defined set of machine instructions, with programs produced by a compiler carefully designed to exploit that instruction set, could result in a very high performance pipelined processor with lower cost and fewer circuits than computer using complex instructions. Their PL.8 compiler, which supported both Pascal and PL.8 (a variant of PL/I for systems programming), contained the first full implementation of Cocke and others' earlier optimization techniques, as well as new ones needed for RISC like a register allocator that avoided memory access delays and an instruction scheduler that hid branching delays.

Critical to the success of RISC was an optimizing compiler able to use the reduced instruction set efficiently. A pioneer in the development of the theoretical foundation for such compilers, Cocke co-developed interval analysis with Frances Allen, a program analysis technique based on a control flow graph reduction [3]. Cocke co-invented many of the optimizing transformations underlying today's compilers, including efficient range checking for arrays, global common subexpression elimination, code motion, operator strength reduction, constant propagation, dead code elimination, and instruction scheduling. Unlike the work of others, Cocke’s compiler optimization techniques were closely linked to related designs for the computer architecture.

The RISC idea was influenced by Cocke’s prior work on computer architecture and optimizing compiler technology. The Stretch project he worked on had the ambitious goal of being 100 times faster than existing computing systems (such as the IBM 704) while providing flexibility in addressing, floating-point arithmetic, and nonnumeric operations. The challenge of improving performance by two orders of magnitude led to several hardware and software features co-designed by Cocke, including instruction pipelining, error correcting codes (ECC), instruction scheduling, and register allocation. Most of these ideas are still used in modern computer architectures more than 50 years after their first use in Stretch. The Stretch project served as a prototype for the IBM System/360, and for the IBM Engineering Verification Engine, a special purpose parallel processor used to simulate IBM computer logic circuits.

The Stretch project focused primarily on performance without regard to cost. But Cocke observed that much of the richness of the Stretch architecture could not be exploited by the compiler. He saw that it is easier to write compilers for a simpler instruction set, and that had a major impact on the approach he took for the 801 project.

Another IBM Research project that had a major influence on Cocke’s work was the Advanced Computer System (ACS) in the 1960’s, whose goal was to build the fastest possible computer for scientific applications. It was capable of executing multiple instructions in a single processor cycle, which is very challenging for a single instruction stream machine. In ACS seven operations could be initiated in a single cycle—one in the branch unit, three in the fixed point unit, and three in the floating point unit—a technique later called superscalar processing. To provide operands for all these instructions, ACS provided fast access to memory by allowing two memory accesses per cycle and having a store queue that was a forerunner of the store buffer used in modern processors. It also included a branch history table that allowed instruction prefetching based on dynamic execution patterns, a concept now referred to as branch prediction.

As a precursor to the RISC design methodology, an experimental ACS optimizing compiler was written long before the hardware design was finalized, which enabled computer architects to prioritize candidate hardware features based on the relative ease or difficulty of using them in the compiler. That compiler was also the breeding ground for many of the code optimization methods co-developed by Cocke. Although ACS never became an IBM product, it was an important  research project whose breakthrough ideas greatly influenced later work by Cocke and others.

Cocke’s pioneering research on computer architecture and optimizing compilers had a lasting impact on computing systems. The 801 Minicomputer is considered to be the first RISC machine. That technology directly fed into IBM’s commercial RISC-based RS/6000 series workstations, and later into the PowerPC processor architecture co-developed by Apple, IBM, and Motorola that is used in a wide range of computer systems including IBM’s Blue Gene/L supercomputers. RISC processors were even used in the IBM 3090 and 390 series of mainframe machines to provide special functions. Many computer companies have incorporated RISC technology into their product lines. Hewlett-Packard based its product line on variants and extensions of the RISC principles, and has also licensed its designs to Hitachi and Samsung. Many computer companies around the world have sought licenses from IBM to use the RISC technologies developed by Cocke. Sun Microsystems, MIPS, Motorola, and Intel also developed RISC-based microprocessors.

John was renowned for the breadth of his intellect, for his energy, for his insights—and for his unconventional working methods. He often wandered the halls of IBM seeking out colleagues to chat with. He was a chain smoker, so an effective method of locating him was to follow the trail of his cigarette butts in the ash trays. Cocke was considered eccentric, particularly within the very proper atmosphere encouraged at IBM. Like many bachelor scientists, he would sometimes forget to cash his pay checks, and might wear the same clothes many days in a row. He eventually married Anne Holloway in 1989, when he was close to retirement. In a 1998 Forbes magazine interview he said, “I guess I was relatively absent-minded… but, you know, there are people more interested in science than in normal ways of life.”

Despite his unconventional demeanor, IBM recognized his many accomplishments by making him an IBM Fellow in 1972. This gave him the flexibility, for the next twenty years until he retired, to work on any aspect of hardware or software that interested him without being narrowly focused on immediate commercial applicability.

Cocke’s technical interests were broad, which led to contributions in areas of computer science beyond computer architecture and optimizing compilers, such as magnetic recording, data compaction, error control, coding theory, and acceleration of circuit simulation. Cocke was able to provide ideas that then served as a catalyst for others to generate more ideas. This influence often occurred through informal interactions rather than via scholarly publications. Many large and high-impact research projects within IBM arose from "discussions with John."

Cocke’s influence extended to collaborators in universities as well, most notably at New York University and Rice University. He and Jacob T. Schwartz of NYU authored the first comprehensive studies of compiler optimizations [4] and were contributors to Addison-Wesley's IBM Programming Book Series.

John Cocke was truly a “renaissance man” in computer science research, whose impact on the field stemmed from both his own technical contributions and his influence on others. He held more than 20 patents. A professorship at Duke University is named in his honor. He died in 2002 after a long illness and a series of strokes, and is survived by his wife Anne.

 

Authors: Michael G. Burke and Vivek Sarkar