Publications

ACM mandated notice:
The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

• Software Reliability
  • Static and Dynamic Analyses
  • Architecture

• Appliance Computing

• Parallelism
  • The SUIF Parallelizing and Optimizing Compiler
    • Overview and Evaluation of SUIF
    • Parallelism and Data Locality Optimizations
      • Affine Transformations and Global Optimizations
      • Unimodular Transformations and Blocking
      • Prefetching
    • Interactive Parallelization
    • Interprocedural Parallelization
    • Pointer Alias Analysis
    • Array Analysis
    • Scalar Optimizations
    • Evaluating Privatization
    • Software Pipelining
  • Computer Architecture
    • Speculative Parallelism
    • Superscalar Processors and Instruction-Level Parallelism
  • Parallel Languages and Run-Time Systems
    • The SAM Distributed Memory System
    • The Jade Parallel Programming Language

• Operating System
  • Support for Multimedia Applications
  • Dynamic Updates
• Hardware Description Language Simulation

Software Reliability

• Improving Software Security with A C Pointer Alias Analysis
  Dzintars Avots, Michael Dalton, Benjamin Livshits, Monica S. Lam
  In Proceedings of the 27th International Conference on Software Engineering, May 2005.
  

• Cloning-Based Context-Sensitive Pointer Alias Analysis Using Binary Decision Diagrams
  John Whaley and Monica S. Lam
  In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pages 131-144, June 2004.
  Best paper award.
  

• A Practical Dynamic Buffer Overflow Detector
  Olatunji Ruwase and Monica S. Lam
  In Proceedings of the 11th Annual Network and Distributed System Security Symposium, pages 159-169, February 2004.

• Tracking Pointers with Path and Context Sensitivity for Bug Detection in C Programs
  V. Benjamin Livshits and Monica S. Lam
  In Proceedings of the 11th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE-11), pages 317-326, September 2003.

• A Practical Flow-Sensitive and Context-Sensitive C and C++ Memory Leak Detector
  David L. Heine and Monica S. Lam
  In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, pages 168-181, June 2003.

• Joeq: A Virtual Machine and Compiler Infrastructure
  John Whaley
  In ACM SIGPLAN 2003 Workshop on Interpreters, Virtual Machines and Emulators, pages 58-66, June 2003.

• An Efficient Inclusion-Based Points-To Analysis for Strictly-Typed Languages
  John Whaley and Monica S. Lam
  In Proceedings of the 9th International Static Analysis Symposium, pages 180-195, September 2002.

• Automatic Extraction of Object-Oriented Component Interfaces
  John Whaley, Michael C. Martin and Monica S. Lam
  In Proceedings of the International Symposium on Software Testing and Analysis, pages 218-228, July 2002.
  ACM SIGSOFT Distinguished Paper Award.
  
  
• Tracking Down Software Bugs Using Automatic Anomaly Detection
  S. Hangal and M. S. Lam
  In Proceedings of the International Conference on Software Engineering, pages 291-301, May 2002.
  (Also available in gzip'ed postscript format).
  
  

• Enhancing Software Reliability with Speculative Threads
  Jeffrey Oplinger.
  Ph.D. Thesis. Stanford University, Computer Systems Laboratory, August 2004.
  
  
• Enhancing Software Reliability with Speculative Threads
  Jeffrey Oplinger and Monica S. Lam.
  In Proceedings of the Tenth International Conference on Architectural Support for Programming Languages and Operating Systems , pages 184-196, October 2002.
  
  

Appliance Computing

• Virtual Appliances for Deploying and Maintaining Software BIBTeX
  C. Sapuntzakis, D. Brumley, R. Chandra, N. Zeldovich, J. Chow, M. S. Lam, and M. Rosenblum
  In Proceedings of the Seventeenth Large Installation Systems Administration Conference (LISA 2003), pages 181-194, October 2003.
  

• Virtual Appliances in the Collective: A Road to Hassle-free Computing BIBTeX
  C. Sapuntzakis and M. S. Lam
  In Proceedings of the Ninth Workshop on Hot Topics in Operating Systems (HOTOS IX), pages 55-60, May 2003.

• Optimizing the Migration of Virtual Computers BIBTeX
  C. P. Sapuntzakis, R. Chandra, B. Pfaff, J. Chow, M. S. Lam and M. Rosenblum
  In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation, pages 377-390, December 2002.

• Supporting Ubiquitous Computing with Stateless Consoles and Computation Caches
  B. K. Schmidt
  Ph.D. Thesis, Computer Science Department, Stanford University, August 2000.
  (Also available in PDF and gzip'ed postscript formats.)

• The Interactive Performance of SLIM: A Stateless, Thin-Client Architecture
  B. K. Schmidt, M. S. Lam, and J. D. Northcutt
  Proceedings of the Seventeenth ACM Symposium on Operating Systems Principles, Kiawah Island, SC, December 1999.
  Published as Operating Systems Review, 34(5):32-47.
  (Also available in PDF and gzip'ed postscript formats.)

Overview and Evaluation of SUIF

• Maximizing Multiprocessor Performance with the SUIF Compiler
  M. W. Hall, J. M. Anderson, S. P. Amarasinghe, B. R. Murphy, S.-W. Liao, E. Bugnion and M. S. Lam
  IEEE Computer, December 1996.
  (A special issue on multiprocessors).

• Multiprocessors from a Software Perspective
  S. P. Amarasinghe, J. M. Anderson, C. S. Wilson, S.-W. Liao, B. R. Murphy, R. S. French, M. S. Lam and M. W. Hall
  IEEE Micro, June 1996, pages 52-61.
  (A special issue on the Hot Chips VII Conference, Stanford, CA, Aug. 1995).

Parallelism and Data Locality Optimizations

• A Retrospective: A Data Locality Optimizing Algorithm
  M. S. Lam.
  In 20 Years of PLDI (1979-1999): A Selection, 2004.

• Improving Parallelism And Data Locality With Affine Partitioning
  A. W. Lim
  Ph.D. thesis, Stanford University, Computer Science Department, September 2001.
  

• Blocking and Array Contraction Across Arbitrarily Nested Loops Using Affine Partitioning
  A. W. Lim, S.-W. Liao and M. S. Lam
  Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, June, 2001.

• Cache Optimizations With Affine Partitioning
  A. W. Lim and M. S. Lam.
  Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing, Portsmouth, Virginia, March, 2001.

• An Affine Partitioning Algorithm to Maximize Parallelism and Minimize Communication
  A. W. Lim, G. I. Cheong and M. S. Lam
  Proceedings of the 13th ACM SIGARCH International Conference on Supercomputing, June, 1999.

• Maximizing Parallelism and Minimizing Synchronization with Affine Partitions
  A. W. Lim and M. S. Lam
  Parallel Computing, Vol. 24, Issue 3-4, May 1998, Pages 445-475. (Also available in PDF format.)

• Automatic Computation and Data Decomposition for Multiprocessors
  J. M. Anderson
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, March, 1997. (Also published as Stanford CSL-TR-97-719.)

• Parallelizing Compiler Techniques Based on Linear Inequalities
  S. P. Amarasinghe
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, January, 1997.

• Maximizing Parallelism and Minimizing Synchronization with Affine Transforms
  A. W. Lim and M. S. Lam
  Conference Record of the 24th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January, 1997.

• Finding Affine Partitions that Maximize Parallelism and Minimize Synchronization
  A. W. Lim and M. S. Lam
  Proceedings of the Sixth Workshop on Compilers for Parallel Computers, Aachen, Germany, December, 1996.

• Compiler-Directed Page Coloring for Multiprocessors
  E. Bugnion, J. M. Anderson, T. C. Mowry, M. Rosenblum and M. S. Lam
  Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, October 1996. ( More information)

• Data and Computation Transformations for Multiprocessors (PostScript)
  J. M. Anderson, S. P. Amarasinghe and M. S. Lam
  Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Processing, July, 1995.

• The SUIF Compiler for Scalable Parallel Machines
  S. P. Amarasinghe, J. M. Anderson, M. S. Lam and C. W. Tseng
  Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, February, 1995.

• Locality Optimizations for Parallel Machines
  M. S. Lam
  Parallel Processing: CONPAR 94--VAPP VI.
  Third Joint International Conference on Vector and Parallel Processing, September, 1994. (Keynote address)

• Communication-Free Parallelization via Affine Transformations
  A. W. Lim and M. S. Lam
  Proceedings of the 7th Workshop on Languages and Compilers for Parallel Computing, August, 1994.

• An Overview of a Compiler for Scalable Parallel Machines
  S. P. Amarasinghe, J. M. Anderson, M. S. Lam and A. W. Lim
  Proceedings of the 6th Workshop on Languages and Compilers for Parallel Computing, August, 1993.

• Global Optimizations for Parallelism and Locality on Scalable Parallel Machines (PostScript)
  J. M. Anderson and M. S. Lam
  Proceedings of the ACM SIGPLAN'93 Conference on Programming Language Design and Implementation, June, 1993.

• Communication Optimization and Code Generation for Distributed Memory Machines
  S. P. Amarasinghe and M. S. Lam
  Proceedings of the ACM SIGPLAN'93 Conference on Programming Language Design and Implementation, June, 1993.

• Improving Locality and Parallelism in Nested Loops
  Michael E. Wolf
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, August, 1992.

• A Loop Transformation Theory and An Algorithm to Maximize Parallelism
  M. E. Wolf and M. S. Lam
  IEEE Transactions on Parallel and Distributed Systems, October, 1991.

• A Data Locality Optimizing Algorithm
  M. E. Wolf and M. S. Lam
  Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation, June, 1991.

• The Cache Performance and Optimizations of Blocked Algorithms
  M. S. Lam, E. E. Rothberg and M. E. Wolf
  Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, April, 1991.

• Tolerating Latency Through Software-Controlled Data Prefetching
  Todd C. Mowry
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, March, 1994.

• Design and Evaluation of a Compiler Algorithm for Prefetching (PostScript)
  T. C. Mowry, M. S. Lam and A. Gupta
  Proceedings of the Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, October, 1992.

Interactive Parallelization

• SUIF Explorer: an Interactive and Interprocedural Parallelizer
  S.-W Liao
  Ph.D. Thesis, Technical Report CSL-TR-00-807, Computer Science Department, Stanford University, August 2000.

• SUIF Explorer: An Interactive and Interprocedural Parallelizer
  S.-W Liao, A. Diwan, R. P. Bosch, Jr. and A. Ghuloum, M. S. Lam
  Proceedings of the 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP'99), May, 1999.

Interprocedural Parallelization

• B. R. Murphy
  Frameworks for Precise Program Analysis.
  Ph.D. Dissertation. Stanford University, December, 2001. (text abstract)

• Detecting Coarse-Grain Parallelism Using an Interprocedural Parallelizing Compiler (PostScript)
  M. W. Hall, S. P. Amarasinghe, B. R. Murphy, S. Liao, and M. S. Lam,
  Proceedings of Supercomputing '95, December, 1995.

• Interprocedural Parallelization Analysis: A Case Study (PostScript)
  M. W. Hall, B. R. Murphy, S. P. Amarasinghe, S. Liao, and M. S. Lam,
  Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing (LCPC95) August, 1995.

• Interprocedural Analysis for Parallelization: Design and Experience
  M. W. Hall, B. R. Murphy and S. P. Amarasinghe
  Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, February, 1995.

• Managing Interprocedural Optimization
  M. W. Hall
  Ph.D. thesis, Rice University, Dept. of Computer Science, May, 1991.

Pointer Alias Analysis

• Interprocedural Dataflow Analysis - Alias Analysis
  Patrick W. Sathyanathan
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, June, 2001.

• Efficient Context-Sensitive Pointer Analysis For C Programs
  Robert P. Wilson
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, December, 1997.

• Efficient Context-Sensitive Pointer Analysis for C Programs (PostScript)
  R. P. Wilson and M. S. Lam
  Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation, June, 1995.

Array Analysis

• Array Data Flow Analysis and its Use in Array Privatization
  D. E. Maydan, S. P. Amarasinghe and M. S. Lam
  Proc. 20th Annual ACM Symposium on Principles of Programming Languages, January, 1993.

• Accurate Analysis of Array References
  D. E. Maydan
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, September, 1992.

• Data Dependence and Data-Flow Analysis of Arrays
  D. E. Maydan, S. P. Amarasinghe and M. S. Lam
  Conference Record of 5th Workshop on Languages and Compilers for Parallel Computing, 1992.

• Effectiveness of Data Dependence Analysis
  D. E. Maydan, J. L. Hennessy and M. S. Lam
  Proceedings of the NSF-NCRD Workshop on Advanced Compilation Techniques for Novel Architectures, 1992.

• Efficient and Exact Data Dependence Analysis
  D. E. Maydan and J. L. Hennessy and M. S. Lam
  Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation, June, 1991.

Scalar Optimizations

• Automatic Generation of Data-flow Analyzers: A Tool for Building Optimizers
  Steven W. K. Tjiang
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, July, 1993.

• Sharlit---A Tool for Building Optimizers
  Steven W. K. Tjiang and John L. Hennessy
  Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, July, 1992.

Evaluating Privatization

• Parallelizing Compilers: Implementation and Effectiveness
  Karen L. Pieper
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, June, 1993.

Software Pipelining

• A Retrospective: Software Pipelining: An Effective Scheduling Technique for VLIW Machines.
  M. S. Lam.
  In 20 Years of PLDI (1979-1999): A Selection, 2004.

Speculative Parallelism

• Enhancing Software Reliability with Speculative Threads
  Jeffrey Oplinger.
  Ph.D. Thesis. Stanford University, Computer Systems Laboratory, August 2004.
  
  
• Enhancing Software Reliability with Speculative Threads
  Jeffrey Oplinger and Monica S. Lam.
  In Proceedings of the Tenth International Conference on Architectural Support for Programming Languages and Operating Systems , pages 218-228, October 2002.
  
  
• In Search of Speculative Thread-Level Parallelism
  J. Oplinger, D. Heine and M. S. Lam
  Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques (PACT'99), Newport Beach, CA, October 1999. (Also available in PDF format.)

• Software and Hardware for Exploiting Speculative Parallelism with a Multiprocessor
  J. Oplinger, D. Heine, S.W. Liao, B. A. Nayfeh, M. S. Lam and K. Olukotun
  Stanford University Computer Systems Lab Technical Report CSL-TR-97-715, February 1997. (Also available in PDF format.)

Superscalar Processors and Instruction-Level Parallelism

• Efficient Superscalar Performance Through Boosting
  M. D. Smith, M. A. Horowitz and M. S. Lam
  Proceedings of the Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, October, 1992.

• Boosting Beyond Static Scheduling in a Superscalar Processor.
  M. D. Smith, M. S. Lam and M. A. Horowitz.
  Proceedings of the 17th Annual International Symposium on Computer Architecture, pp. 344-354 May 1990.

• Limits of Control Flow on Parallelism (PostScript)
  M. S. Lam and R. P. Wilson
  Proceedings of the 19th Annual International Symposium on Computer Architecture, May, 1992.

The SAM Distributed Memory System

• Transparent Fault Tolerance for Parallel Applications on Networks of Workstations
  D. J. Scales and M. S. Lam
  Proceedings of the 1996 USENIX Technical Conference, January, 1996.

• The Design and Evaluation of an Efficient Shared Object System for Distributed Memory Machines
  D. J. Scales
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, December, 1995.

• The Design and Evaluation of a Shared Object System for Distributed Memory Machines
  D. J. Scales and M. S. Lam
  Proceedings of the First Symposium on Operating System Design and Implementation, November, 1994.

The Jade Parallel Programming Language

• The Design, Implementation, and Evaluation of Jade
  M. C. Rinard and M. S. Lam
  ACM Transactions on Programming Languages and Systems, Vol. 20, No. 1, January 1998, Pages 1-63.

• The Design, Implementation and Evaluation of Jade, a Portable, Implicitly Parallel Programming Language
  M. C. Rinard
  Ph.D. thesis, Stanford University, Computer Systems Laboratory, September, 1994.

• Jade: A High-Level, Machine-Independent Language for Parallel Programming
  M. C. Rinard and D. J. Scales and M. S. Lam
  IEEE Computer, June, 1993.

• Heterogeneous Parallel Programming in Jade
  M. C. Rinard and D. J. Scales and M. S. Lam
  Proceedings of Supercomputing '92, November, 1992.

• Semantic Foundations of Jade.
  M. C. Rinard and M. S. Lam
  Proceedings of the 19th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 105-118, January 1992.

• Coarse-Grain Parallel Programming in Jade.
  Lam, M. S., and Rinard, M. C.
  Proceedings of the ACM SIGPLAN 3rd Symposium on Principles and Practice of Parallel Programming (PPoPP '91), pp. 94-105, April 1991.

Operating System Support for Multimedia Applications

• A SMART scheduler for multimedia applications
  J. Nieh and M. S. Lam
  ACM Transactions on Computer Systems, May 2003, 21(2), pp. 117-163.

• The Design, Implementation and Evaluation of SMART: A Scheduler for Multimedia Applications
  J. Nieh
  Ph.D. Thesis, Department of Electrical Engineering, Stanford University, June 1999.

• Multimedia on Multiprocessors: Where's the OS When You Really Need It?
  J. Nieh, M. S. Lam
  Proceedings of the Eighth International Workshop on Network and Operating System Support for Digital Audio and Video, Cambridge, U.K., July 1998.

• The Design, Implementation and Evaluation of SMART: A Scheduler for Multimedia Applications
  J. Nieh, M. S. Lam
  Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, Saint-Malo, France, October 1997. (Also available in HTML format).

• SMART UNIX SVR4 Support for Multimedia Applications
  J. Nieh, M. S. Lam
  Proceedings of the IEEE International Conference on Multimedia Computing and Systems, Ottawa, Ontario, Canada, June 1997.

• SMART: A Processor Scheduler for Multimedia Applications
  J. Nieh, M. S. Lam
  Abstract from Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, Copper Mountain, Colorado, December 1995.

• Integrated Processor Scheduling for Multimedia
  J. Nieh and M. S. Lam
  Proceedings of the Fifth International Workshop on Network and Operating Systems Support for Digital Audio and Video, Durham, NH, April, 1995.

• A Method and Apparatus for Measuring Media Synchronization
  B. K. Schmidt and J. D. Northcutt and M. S. Lam
  Proceedings of the Fifth International Workshop on Network and Operating Systems Support for Digital Audio and Video, Durham, NH, April, 1995.

• An End-to-End Software Only Scalable Video Delivery System
  N. Chaddha and G. A. Wall and B. K. Schmidt
  Proceedings of the Fifth International Workshop on Network and Operating Systems Support for Digital Audio and Video, Durham, NH, April, 1995.

• SVR4 UNIX Scheduler Unacceptable for Multimedia Applications
  J. Nieh, J. G. Hanko, J. D. Northcutt, G. A. Wall
  Proceedings of the Fourth International Workshop on Network and Operating System Support for Digital Audio and Video, Lancaster, U.K., November, 1993.

• Volume Rendering on Scalable Shared-Memory MIMD Architectures
  J. Nieh and M. Levoy
  Proceedings of the Boston Workshop on Volume Visualization, October, 1992.

Dynamic Updates

• Dynamic Kernel Modification and Extensibility.
  Arun Kishan and Monica Lam
  Technical Report, May 2002.

Hardware Description Language Simulation

• A General Method for Compiling Event-Driven Simulations (PostScript)
  R. S. French, M. S. Lam, J. R. Levitt, and K. Olukotun
  32nd ACM/IEEE Design Automation Conference, June, 1995.