Donald B. Gillies

Last updated
Donald B. Gillies
Gillies Donald B.jpg
Circa 1974, courtesy U-Illinois UC CS Dept.
Born
Donald Bruce Gillies

(1928-10-15)15 October 1928
Died17 July 1975(1975-07-17) (aged 46)
Urbana, Illinois, USA
NationalityCanadian
Alma mater University of Toronto
University of Illinois at Urbana-Champaign
Princeton University
Scientific career
Fields Mathematics, Computer Science
Institutions University of Illinois,
Stanford (sabbatical),
National Research Development Corporation, UK
Doctoral advisor John von Neumann
Doctoral students Alan M. Davis

Donald Bruce Gillies (October 15, 1928 – July 17, 1975) was a Canadian computer scientist and mathematician who worked in the fields of computer design, game theory, and minicomputer programming environments.

Contents

Early life and education

Donald B. Gillies was born in Toronto, Ontario, Canada, to John Zachariah Gillies (a Canadian) and Anne Isabelle Douglas MacQueen (an American).

He attended the University of Toronto Schools, a laboratory school originally affiliated with the University. Students at this Ontario school skipped a year ahead and so he finished his 13th-grade studies at the age of 18. Gillies attended the University of Toronto (1946–1950), intending to major in Languages. He started his first semester taking seven different language courses. In his second semester he quickly switched back to majoring in Mathematics which was his love while in high school.

During his time as an undergraduate, he spent a great deal of time at the U-Toronto Computation Center. In the Putnam exam competition of 1950, Gillies was stunned at not being selected by the faculty to compete with the U-Toronto team. To avenge himself, Gillies placed in the top 10 in North America, following his University of Toronto classmates John P. Mayberry and Richard J. Semple who were top 5 Putnam Fellows. Toronto would likely have won the competition in 1950 had Gillies been on the faculty-designated team. [1]

For graduate school, Gillies applied to the University of Illinois University of Illinois at Urbana-Champaign, which was "a very busy place building lots of computers". While he was there, he began working on the ORDVAC/Illiac I project. After one year of graduate school (1951), Gillies transferred to Princeton University to work with John von Neumann, at the urging of and also to be with John P. Mayberry, who was also studying under John von Neumann. Gillies and Mayberry were both arch-rivals and best friends, [2] and after Mayberry beat Gillies in the Putnam exam, each competed to finish his PhD degree first.

During his graduate studies, and after working with von Neumann, Gillies became a fan of the book "One-upmanship" by Stephen Potter. John von Neumann was also a fan of this work, and was extremely successful at impressing others with his intelligence. An apocryphal math problem asks about a bumble bee flying back and forth between two approaching trains, and how far did it fly before colliding? When von Neumann gave the correct answer, the questioner asked if he used a standard time/rate-of-travel trick, and he replied, 'no, I summed the infinite series in my head' to impress the questioner. This method of impressing and astonishing others appealed to both Gillies and von Neumann.

During his time at Princeton his interest area was computer design first and mathematics second. He continued to work with U-Illinois researchers and participated the check-out of the ORDVAC Computer (from U-Illinois) at Aberdeen Proving Ground in Maryland, in the summer of 1951.

At one point during his graduate studies, von Neumann found out that Gillies had been spending time working on an assembler (something that had not yet been invented). Von Neumann became enraged and told Gillies to stop work immediately because computers would never be used to perform such menial tasks. [3]

After only two years of study at Princeton, Gillies completed his PhD before Mayberry, at age 25, in 1953, which was published in Contributions to the theory of games, vol.2 — in which he characterized the core which is the set of stable solutions (among all coalitions) in a non-zero-sum game. [4]

Early career

Gillies then went to England for two years to work for the NRDC (National Research Development Corporation) and worked with an early Ferranti Pegasus computer there. This was a time when the American, British, and Canadian, governments were conscripting young men for service in the Korean War. In later years, after he returned to the U.S., he was again drafted, but successfully appealed against the order.

While at the NRDC, Gillies and Christopher Strachey filed several American, British, and Canadian patents. [5] [6] [7] The patent on Order (instruction) Control laid out the details of how to implement a base register for program relocation in computers - before it had been done. He considered these patents as kind of a joke, and assigned the rights of the patents to either NRDC or IBM, without taking fees for this service. This kept the ideas from being patented by others which would have hindered progress in the computer industry.

When Gillies returned to the US in 1956, he received a 1-A draft status which persisted until he was age 36. Upon returning to the US, Gillies married Alice E. Dunkle and began a job as a professor at the University of Illinois at Urbana-Champaign. [8]

In early October 1957 the Soviet Military launched Sputnik I, and caused a widespread panic across the United States. Just hours later the UIUC Astronomy Department [9] rigged an ad-hoc interferometer to measure signals from the satellite. The astronomers approached Dr. Gillies and Dr Jim Snyder to program the ILLIAC I computer to calculate the satellite orbit from this data. The programming and calculation was completed in under two days. The very rapid publication of the ephemeris (orbit) in the journal Nature [10] —just a month after satellite launch—helped to dispel some of the fear created by the Sputnik launch by the Soviet Union. It also lent credence to the (likely false) idea that the Sputnik launch was part of an organized effort to dominate space. [11]

Starting in 1958, Gillies designed the 3-stage pipeline control of the ILLIAC II supercomputer at the University of Illinois. The control circuitry consisted of advanced control, delayed control, and interplay. This work was in the public domain, and competed with the Stretch computer system design from IBM that is often credited with inventing pipelining. This work was presented in a 1962 Michigan conference on computer design, "On the design of a very high speed computer" [12]

The Math Department at UIUC celebrated the new primes with a postal meter cancellation stamp -- until Appel and Haken proved the 4-color theorem in 1976. MersennePrimeStamp.gif
The Math Department at UIUC celebrated the new primes with a postal meter cancellation stamp — until Appel and Haken proved the 4-color theorem in 1976.

As the main designer of the pipelined control circuitry for ILLIAC II, Gillies developed the algorithms for the month-long checkout and acceptance testing of the new computer. To draw attention to this new computer design in the field of mathematics, he wrote an implementation of the Lucas–Lehmer primality test and found three new Mersenne primes, and published them in a paper, "Three new Mersenne primes and a statistical theory." [13] The new Mersenne primes were reported in the Guinness Book of World Records, and the largest one was immortalized on all mail sent from the Post Office (Annex) at the Math department of the University of Illinois. In the same paper, Gillies made a conjecture about the distribution of prime divisors of Mersenne numbers.

Later career

In the late 1960s, Gillies became concerned that students were not getting direct access to computers any more. He lobbied UIUC to adopt the 1968 WATFOR one-pass FORTRAN compiler / runtime system from the University of Waterloo in Ontario. This was a fast-turnaround IDE for batch-based mainframe computers. At the time it was common practice to submit a job (card deck) and pick up the results the next day. The WATFOR compiler could compile, link, and run a short program in the compiler's memory space in a few seconds. This compiler allowed the university to offer undergraduate programming courses not only to computer scientists but also to business majors and to other non-specialists. Gillies and his family traveled to Waterloo to pick up a magtape with this compiler, on one of his visits to see his family, in the early 1970s.

In 1969, Gillies received a preprint of Wirth's "Pascal User Manual and Report" and launched a project to build the first Pascal compiler written in North America. Ian Stocks was one of the graduate students who worked on this fast-turnaround in-memory 2-pass compiler, and the compiler (for the Digital Equipment PDP-11 minicomputer) was completed in the early 1970s. This work was part of the "PDP-11 Playpen" project which focused on getting graduate students direct access to low-cost computer hardware, such as the PDP-11/23, where the Pascal compiler ran.

Two years later at the urging of his new graduate student, Greg Chesson, Gillies became in 1974 the first licensee for the UNIX operating system from Bell Labs. [14] [15] Chesson went on to be the third person to edit the Unix kernel and was the eighth hire at Silicon Graphics Inc.


Personal life

Gillies met his future wife, Alice E. Dunkle, while at Princeton and began dating her, but after several months, their relationship fizzled. Miss Dunkle, knowing of the rivalry between Mayberry and Gillies, intentionally flirted with Mayberry at a dance, and Mayberry subsequently approached Gillies to ask if he was still dating her. This tactic, used only once, led to their eventual marriage.

Death and legacy

Gillies died unexpectedly at age 46 on July 17, 1975, of a rare viral myocarditis. Digital Equipment Corporation and many of his friends, colleagues, and family contributed money for the Donald B. Gillies Memorial Lectureship In Computer Science, at the University of Illinois at Urbana Champaign. This annual lectureship continues to this day.

In 1994, the Nobel Memorial Prize in Economic Sciences was awarded to John Forbes Nash. In the Nash Seminar, [16] Gillies (who was at Princeton at the same time, and was friends with Nash) was mentioned as a pioneer in the field of game theory. Nash proved the existence of stable solutions for non-zero-sum games; Gillies and Shapley extended this work by characterizing the core which is the set of stable solutions that cannot be improved by a coalition.

In 2006 the Donald B. Gillies Chair Professorship was established in the department of Computer Science at the University of Illinois. A generous donation from Lawrence (Larry) White, a former student, established this chair. The first professor to hold this chair is Lui Sha, a well-known authority on real-time and embedded systems.

In 2011, the UIUC Department of Computer Science awarded a Memorial Achievement Award [17] to Gillies, and family members accepted the award on his behalf at the Urbana-Champaign campus.

In 2018, the Donald B. Gillies Chair Professorship endowment had grown so large that Vikram Adve was invested as the second chair professor at UIUC under this designation. Adve led the project that developed the LLVM compiler suite which has been adopted industrywide (by Apple and Google among others). [18]

Students

See also

Related Research Articles

John von Neumann mathematician and physicist

John von Neumann was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. Von Neumann was generally regarded as the foremost mathematician of his time and said to be "the last representative of the great mathematicians"; he integrated pure and applied sciences.

IAS machine

The IAS machine was the first electronic computer to be built at the Institute for Advanced Study (IAS) in Princeton, New Jersey. It is sometimes called the von Neumann machine, since the paper describing its design was edited by John von Neumann, a mathematics professor at both Princeton University and IAS. The computer was built from late 1945 until 1951 under his direction. The general organization is called von Neumann architecture, even though it was both conceived and implemented by others. The computer is in the collection of the Smithsonian National Museum of American History but is not currently on display.

ORDVAC

The ORDVAC or Ordnance Discrete Variable Automatic Computer, an early computer built by the University of Illinois for the Ballistic Research Laboratory at Aberdeen Proving Ground, was based on the IAS architecture developed by John von Neumann, which came to be known as the von Neumann architecture. The ORDVAC was the first computer to have a compiler. ORDVAC passed its acceptance tests on March 6, 1952 at Aberdeen Proving Ground in Maryland. Its purpose was to perform ballistic trajectory calculations for the US Military. In 1992, the Ballistic Research Laboratory became a part of the US Army Research Laboratory.

ILLIAC I Vacuum tube computer

The ILLIAC I, a pioneering computer in the ILLIAC series of computers built in 1952 by the University of Illinois, was the first computer built and owned entirely by a United States educational institution.

ILLIAC II

The ILLIAC II was a revolutionary super-computer built by the University of Illinois that became operational in 1962.

John Cocke American computer scientist and mathematician

John Cocke was an American computer scientist recognized for his large contribution to computer architecture and optimizing compiler design. He is considered by many to be "the father of RISC architecture."

University of Illinois at Urbana–Champaign Public university in Illinois, U.S.

The University of Illinois at Urbana–Champaign 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 of Illinois system and was founded in 1867.

von Neumann architecture computer architecture where code and data share a common bus

The von Neumann architecture—also known as the von Neumann model or Princeton architecture—is a computer architecture based on a 1945 description by John von Neumann and others in the First Draft of a Report on the EDVAC. That document describes a design architecture for an electronic digital computer with these components:

Christopher Strachey British computer scientist

Christopher S. Strachey was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design and computer time-sharing. He was a member of the Strachey family, prominent in government, arts, administration, and academia.

ILLIAC was a series of supercomputers built at a variety of locations, some at the University of Illinois at Urbana–Champaign. In all, five computers were built in this series between 1951 and 1974. Some more modern projects also use the name.

Abraham H. Taub American mathematician

Abraham Haskel Taub was a distinguished American mathematician and physicist, well known for his important contributions to the early development of general relativity, as well as differential geometry and differential equations.

Minimal instruction set computer instruction set architecture

Minimal instruction set computer (MISC) is a central processing unit (CPU) architecture, usually in the form of a microprocessor, with a very small number of basic operations and corresponding opcodes, together forming an instruction set. Such sets are commonly stack-based rather than register-based to reduce the size of operand specifiers.

Wen-mei Hwu is the Walter J. Sanders III-AMD Endowed Chair professor in Electrical and Computer Engineering in the Coordinated Science Laboratory at the University of Illinois at Urbana-Champaign. His research is on compiler design, computer architecture, computer microarchitecture, and parallel processing. He is a principal investigator for the petascale Blue Waters supercomputer, is co-director of the Universal Parallel Computing Research Center (UPCRC), and is principal investigator for the first NVIDIA CUDA Center of Excellence at UIUC. At the Illinois Coordinated Science Lab, Hwu leads the IMPACT Research Group and is director of the OpenIMPACT project – which has delivered new compiler and computer architecture technologies to the computer industry since 1987. From 1997 to 1999, Hwu served as the chairman of the Computer Engineering Program at Illinois. Since 2009, Hwu has served as chief technology officer at MulticoreWare Inc., leading the development of compiler tools for heterogeneous platforms. The OpenCL compilers developed by his team at MulticoreWare are based on the LLVM framework and have been deployed by leading semiconductor companies.

MISTIC computer system at Michigan State University

The MISTIC, or Michigan State Integral Computer, was the first computer system at Michigan State University and was built by its students, faculty and staff in 1957. Powered by vacuum tubes, its design was based on ILLIAC, the supercomputer built at University of Illinois at Urbana–Champaign, a descendant of the IAS architecture developed by John von Neumann.

David J. Kuck, a graduate of the University of Michigan, was a professor in the Computer Science Department the University of Illinois at Urbana-Champaign from 1965 to 1993. He is the father of Olympic silver medalist Jonathan Kuck. While at the University of Illinois at Urbana-Champaign he developed the Parafrase compiler system (1977), which was the first testbed for the development of automatic vectorization and related program transformations. In his role as Director (1986–93) of the Center for Supercomputing Research and Development (CSRD-UIUC), Kuck led the construction of the CEDAR project, a hierarchical shared-memory 32-processor SMP supercomputer completed in 1988 at the University of Illinois.

Paul Trevier Bateman was an American number theorist, known for formulating the Bateman–Horn conjecture on the density of prime number values generated by systems of polynomials and the New Mersenne conjecture relating the occurrences of Mersenne primes and Wagstaff primes.

Department of Computer Science, University of Illinois at Urbana–Champaign

The Department of Computer Science (CS) at the University of Illinois at Urbana-Champaign has consistently been ranked as a top computer science program in the world. As of 2018, U.S. News & World Report rank UIUC's Computer Science as a Top 5 CS Graduate School program in the nation, and the University of Illinois at Urbana-Champaign is ranked as one of the Top 6 Undergraduate Schools in Computer Engineering. CSrankings.org puts UIUC in the top 3 computer science schools in the world by publications and research output in top conferences over the past 10 years. Since its reorganization in 1964, the Department of Computer Science has produced a myriad of publications and research that have advanced the field of Computer Science. In addition, many faculty and alumni have been leads with modern-day applications and projects such as Mosaic, LLVM, PayPal, Yelp, and YouTube.

In number theory, Gillies' conjecture is a conjecture about the distribution of prime divisors of Mersenne numbers and was made by Donald B. Gillies in a 1964 paper in which he also announced the discovery of three new Mersenne primes. The conjecture is a specialization of the prime number theorem and is a refinement of conjectures due to I. J. Good and Daniel Shanks. The conjecture remains an open problem: several papers give empirical support, but it disagrees with the widely accepted Lenstra–Pomerance–Wagstaff conjecture.

Alfred Inselberg (1936-2019) was an American-Israeli mathematician and computer scientist based at Tel Aviv University.

Roy H. Campbell is a computer scientist and the Sohaib and Sara Abbasi Professor emeritus at University of Illinois at Urbana–Champaign and director of the Assured Cloud Computing University Center of Excellence. Campbell is best known for his work in operating systems, parallel computing, and multimedia on the internet.

References

  1. L.E. Bush, William Lowell Putnam Mathematical Competition, American Math Monthly Vol 57 No 7 (Aug-Sep 1950) pp 467-470
  2. Kuhn, H. W.; Tucker, A. W.., eds. (1953). "Two variants of Poker, D. B. Gillies, J. P. Mayberry, and J. von Neumann". Contributions to the Theory of Games. 2. pp. 13–51. ISBN   0691079358.
  3. Douglas Jones (U-Iowa Faculty), alt.folklore.computers, 14 July 2000
  4. Kuhn, H. W.; Tucker, A. W.., eds. (1953). "Discriminatory and Bargaining Solutions to a class of Symmetric n-Person Games, D. B. Gillies". Contributions to the Theory of Games. 2. pp. 325–342. ISBN   0691079358.
  5. USissued; expired. 02846142,Strachey, Christopher; Gillies, Donald Bruce,"Electronic Digital Computers (delay-line multiplication)",published 1958-08-05, assigned to NRDC, UK
  6. USissued; expired. 3017094,Strachey, Christopher; Gillies, Donald Bruce,"Order control arrangements for electronic digital computers",published 1962-01-16, assigned to IBM
  7. USissued; expired. 3017090,Strachey, Christopher; Gillies, Donald B.,"Overflow control means for a digital computer",published 1962-01-16, assigned to IBM
  8. Engagement Announcement (New York Times), Alice E. Dunkle is Betrothed to Donald Gillies, a Mathematician, December 10, 1955.
  9. "A HISTORY OF ASTRONOMY AT ILLINOIS". Archived from the original on 2015-03-09. Retrieved 2015-03-18.
  10. I. R. King, G. C. McVittie, G. W. Swenson, Jr., and S. P. Wyatt, Jr., "Further observations of the first satellite," Nature, No. 4593, November 9, 1957, p. 943.
  11. Vladimir Isachenov (AP), Secrets of Sputnik Launch Revealed, October 1, 2007.
  12. Gillies, Donald B.; Meagher, Ralph E.; Muller, David E.; McKay, R.W.; Nash, Jack P.; Robertson, James E.; Taub, Abe H. (October 1957). "On the design of a very high-speed computer". UIUC Dept. Of CS Technical Report No. 80. doi:10.2172/4311370.
  13. Gillies, Donald B. (Jan 1964). "Three new Mersenne primes and a statistical theory". Mathematics of Computation. 18 (5): 93–97. doi: 10.2307/2003409 . JSTOR   2003409.
  14. Greg Chesson, Personal communication to Donald W. Gillies, Spring 1995, 115 Waverley Street, Palo Alto, CA
  15. Thompson, Ken (16 Sep 2014). "personal communication, Ken Thompson to Donald W. Gillies". UBC ECE Website.
  16. Nash Nobel Prize Seminar, 1994
  17. Memorial Achievement Award Archived 2015-03-18 at Archive.today
  18. "vikram adve invested donald b gillies professor computer science". 2018-04-15.