Bill Pugh
Professor Emeritus
2164 Iribe Center
(301) 405-2705
(301) 405-6707
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
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
2006. Atomic instructions in java. ECOOP 2002—Object-Oriented Programming. :5-16.
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
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.
2005. Software repository mining with Marmoset: an automated programming project snapshot and testing system. ACM SIGSOFT Software Engineering Notes. 30(4):1-5.
2005. The Java memory model. Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. :378-391.
2004
2004. Finding bugs is easy. ACM SIGPLAN NoticesSIGPLAN Not.. 39(12):92-92.
2004. Finding concurrency bugs in java. Proceedings of the PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, Newfoundland, Canada.
2004. Mpjava: High-performance message passing in java using java. nio. Languages and Compilers for Parallel Computing. :323-339.
2001
2001. Core semantics of multithreaded Java. Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande - JGI '01. :29-38.
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.
2000
2000. The Java memory model is fatally flawed. Concurrency - Practice and Experience. 12(6):445-455.
1999
1999. Compressing Java class files. ACM SIGPLAN Notices. 34:247-258.
1999. Fixing the Java memory model. Proceedings of the ACM 1999 conference on Java Grande. :89-98.
1999. SIPR: A new framework for generating efficient code for sparse matrix computations. Languages and Compilers for Parallel Computing. :213-229.
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.
1998
1998. Constraint-based array dependence analysis. ACM Transactions on Programming Languages and SystemsACM Trans. Program. Lang. Syst.. 20(3):635-678.
1997
1997. Symbolic model checking of infinite state systems using Presburger arithmetic. Computer Aided Verification. :400-411.
1997. Iteration space slicing and its application to communication optimization. Proceedings of the 11th international conference on Supercomputing. :221-228.
1996
1996. Efficient distribution analysis via graph contraction. Languages and Compilers for Parallel Computing. :377-391.
1996. Transitive closure of infinite graphs and its applications. Languages and Compilers for Parallel Computing. :126-140.
1995
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.
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.
1995. Parametric dispatching of hard real-time tasks. IEEE Transactions on ComputersIEEE Trans. Comput.. 44(3):471-479.
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.
1995. Code generation for multiple mappings. Frontiers of Massively Parallel Computation, 1995. Proceedings. Frontiers '95., Fifth Symposium on the. :332-341.
1994
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.
1994. Simplifying polynomial constraints over integers to make dependence analysis more precise. Parallel Processing: CONPAR 94—VAPP VI. :737-748.
1994. Counting solutions to Presburger formulas: how and why. ACM SIGPLAN Notices. 29(6):121-134.
1993
1993. A partial evaluator for the Maruti hard real-time system. Real-Time Systems. 5(1):13-30.
1992
1992. Eliminating false data dependences using the Omega test. Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation. :140-151.
1992. The Omega test: a fast and practical integer programming algorithm for dependence analysis. Communications of the ACM. 8(102-114):2-6.
1992. Definitions of dependence distance. ACM Letters on Programming Languages and SystemsACM Lett. Program. Lang. Syst.. 1(3):261-265.
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.
1991
1991. Uniform techniques for loop optimization. Proceedings of the 5th international conference on Supercomputing. :341-352.
1990
1990. Probabilistic analysis of set operations with constant-time set equality test. Advances in Computing and Information—ICCI'90. :62-71.
1990. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACMCommun. ACM. 33(6):668-676.
1990. Two-directional record layout for multiple inheritance. Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation. :85-91.
1989
1989. Incremental computation via function caching. Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. :315-328.
1988
1988. An improved replacement strategy for function caching. Proceedings of the 1988 ACM conference on LISP and functional programming - LFP '88. :269-276.
1987
1987. ALEX-an Alexical Programming Language. TR87-835