Bill Pugh

Professor Emeritus
2164 Iribe Center
(301) 405-2705
(301) 405-6707
Academic Web Page
Education: 
Ph.D., Cornell University (Computer Science)
Special Awards/Honors: 
Packard Fellow
Biography: 

Bill Pugh is a professor emeritus of computer science in the University of Maryland Institute for Advanced Computer Studies.

He is known for inventing Skip Lists and has made significant contributions to incremental computation, functional and object-oriented languages, and the Java programming language. Pugh’s research also includes techniques for analyzing and transforming scientific codes for supercomputers.

Go here to view Pugh's academic publications on Google Scholar.

Publications

2007


Foster JS, Hicks MW, Pugh W.  2007.  Improving software quality with static analysis. Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. :83-84.

2006


Hovemeyer D, Pugh W, Spacco J.  2006.  Atomic instructions in java. ECOOP 2002—Object-Oriented Programming. :5-16.

Grossman D, Manson J, Pugh W.  2006.  What do high-level memory models mean for transactions? Proceedings of the 2006 workshop on Memory system performance and correctness - MSPC '06. :62-62.

2005


Manson J, Pugh W, Adve SV.  2005.  The Java memory model. Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. :378-391.

Hovemeyer D, Spacco J, Pugh W.  2005.  Evaluating and tuning a static analysis to find null pointer bugs. Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. :13-19.

Spacco J, Strecker J, Hovemeyer D, Pugh W.  2005.  Software repository mining with Marmoset: an automated programming project snapshot and testing system. ACM SIGSOFT Software Engineering Notes. 30(4):1-5.

2004


Pugh W, Spacco J.  2004.  Mpjava: High-performance message passing in java using java. nio. Languages and Compilers for Parallel Computing. :323-339.

Hovemeyer D, Pugh W.  2004.  Finding bugs is easy. ACM SIGPLAN NoticesSIGPLAN Not.. 39(12):92-92.

Hovemeyer D, Pugh W.  2004.  Finding concurrency bugs in java. Proceedings of the PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, Newfoundland, Canada.

2001


Hovemeyer D, Pugh W.  2001.  More efficient network class loading through bundling. Proceedings of the 2001 Symposium on Java TM Virtual Machine Research and Technology Symposium-Volume 1. :17-17.

Manson J, Pugh W.  2001.  Core semantics of multithreaded Java. Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande - JGI '01. :29-38.

2000


Pugh W.  2000.  The Java memory model is fatally flawed. Concurrency - Practice and Experience. 12(6):445-455.

1999


Pugh W, Shpeisman T.  1999.  SIPR: A new framework for generating efficient code for sparse matrix computations. Languages and Compilers for Parallel Computing. :213-229.

Bultan T, Gerber R, Pugh W.  1999.  Model-checking concurrent systems with unbounded integer variables: symbolic representations, approximations, and experimental results. ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst.. 21(4):747-789.

Pugh W.  1999.  Compressing Java class files. ACM SIGPLAN Notices. 34:247-258.

Pugh W.  1999.  Fixing the Java memory model. Proceedings of the ACM 1999 conference on Java Grande. :89-98.

1998


Pugh W, Wonnacott D.  1998.  Constraint-based array dependence analysis. ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst.. 20(3):635-678.

1997


Pugh W, Rosser E.  1997.  Iteration space slicing and its application to communication optimization. Proceedings of the 11th international conference on Supercomputing. :221-228.

Bultan T, Gerber R, Pugh W.  1997.  Symbolic model checking of infinite state systems using Presburger arithmetic. Computer Aided Verification. :400-411.

1996


Sheffler T, Schreiber R, Pugh W, Gilbert J, Chatterjee S.  1996.  Efficient distribution analysis via graph contraction. Languages and Compilers for Parallel Computing. :377-391.

Kelly W, Pugh W, Rosser E, Shpeisman T.  1996.  Transitive closure of infinite graphs and its applications. Languages and Compilers for Parallel Computing. :126-140.

1995


Kelly W, Pugh W, Rosser E.  1995.  Code generation for multiple mappings. Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the. :332-341.

Pugh W, Kelly W.  1995.  Finding Legal Reordering Transformations using Mappings. Languages and compilers for parallel computing: 7th International Workshop, Ithaca, NY, USA, August 8-10, 1994: proceedings. 7:107-107.

Kelly W, Pugh W.  1995.  A unifying framework for iteration reordering transformations. Algorithms and Architectures for Parallel Processing, 1995. ICAPP 95. IEEE First ICA/sup 3/PP., IEEE First International Conference on. 1:153-162.

Gerber R, Pugh W, Saksena M.  1995.  Parametric dispatching of hard real-time tasks. IEEE Transactions on ComputersIEEE Trans. Comput.. 44(3):471-479.

Pugh W, Wonnacott D.  1995.  Going beyond integer programming with the Omega test to eliminate false data dependences. IEEE Transactions on Parallel and Distributed Systems. 6(2):204-211.

1994


Maslov V, Pugh W.  1994.  Simplifying polynomial constraints over integers to make dependence analysis more precise. Parallel Processing: CONPAR 94—VAPP VI. :737-748.

Pugh W.  1994.  Counting solutions to Presburger formulas: how and why. ACM SIGPLAN Notices. 29(6):121-134.

Pugh W, Wonnacott D.  1994.  Static analysis of upper and lower bounds on dependences and parallelism. ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst.. 16(4):1248-1278.

1993


Nirkhe V, Pugh W.  1993.  A partial evaluator for the Maruti hard real-time system. Real-Time Systems. 5(1):13-30.

1992


Pugh W.  1992.  The Omega test: a fast and practical integer programming algorithm for dependence analysis. Communications of the ACM. 8(102-114):2-6.

Pugh W.  1992.  Definitions of dependence distance. ACM Letters on Programming Languages and SystemsACM Lett. Program. Lang. Syst.. 1(3):261-265.

Nirkhe V, Pugh W.  1992.  Partial evaluation of high-level imperative programming languages with applications in hard real-time systems. Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. :269-280.

Pugh W, Wonnacott D.  1992.  Eliminating false data dependences using the Omega test. Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation. :140-151.

1991


Pugh W.  1991.  Uniform techniques for loop optimization. Proceedings of the 5th international conference on Supercomputing. :341-352.

1990


Pugh W, Weddell G.  1990.  Two-directional record layout for multiple inheritance. Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation. :85-91.

Pugh W.  1990.  Probabilistic analysis of set operations with constant-time set equality test. Advances in Computing and Information—ICCI'90. :62-71.

Pugh W.  1990.  Skip lists: a probabilistic alternative to balanced trees. Communications of the ACMCommun. ACM. 33(6):668-676.

1989


Pugh W, Teitelbaum T.  1989.  Incremental computation via function caching. Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. :315-328.

1988


Pugh W.  1988.  An improved replacement strategy for function caching. Proceedings of the 1988 ACM conference on LISP and functional programming - LFP '88. :269-276.

1987


Kozen D, Teitelbaum T, Chen WZ, Field JH, Pugh W, Vander Zanden BT.  1987.  ALEX-an Alexical Programming Language. TR87-835