The BeBOP group is broadly interested in understanding software performance tuning issues, and the interaction or implications for hardware design. Among our general interests are

  • the interaction between application software, compilers, and hardware
  • managing trade-offs among the various measures of performance, such as speed, accuracy, power, storage, ...
  • automating the performance tuning process, starting with the computational kernels which dominate application performance in scientific computing and information retrieval
  • performance modeling and evaluation of future computer architectures

See the links below for detailed project information and status.

People

Principal Investigators

Affiliated Researchers

Graduate Students

Previous Participants

Software Distributions

Publications

Download BibTeX entries for these papers and reports.

Year: 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001

    2009

  • Ph.D. Thesis: Auto-tuning Stencil Codes for Cache-Based Multicore Platforms
    (Computer Science Division, U.C. Berkeley, December 2009)
    Kaushik Datta
    PDF (3.1M)
    Talk Slides: PPTX (4.1M) -or- PDF (3.3M)

  • Ph.D. Thesis: Automatically Tuning Collective Communication for One-Sided Programming Models
    (Computer Science Division, U.C. Berkeley, December 2009)
    Rajesh Nishtala
    PDF (4.7M)
    Talk Slides: PPTX (5.9M) -or- PDF (8.2M)

  • Paper: A Methodology for Domain-Optimized Power-Efficient Supercomputing
    (In Proc. of SC09, November, 2009)
    Marghoob Mohiyuddin, Mark Murphy, Leonid Oliker, John Shalf, John Wawrzynek, and Sam Williams
    PDF (950k)
    Talk slides:PDF (3.3M)

  • Paper: Minimizing Communication in Sparse Matrix Solvers
    (In Proc. of SC09, November, 2009)
    Marghoob Mohiyuddin, Mark Hoemmen, James Demmel, and Kathy Yelick
    PDF (1.2M)
    Talk slides:PDF (3.9M)

  • Paper: Communication-Optimal Parallel and Sequential Cholesky Decomposition
    (Symposium on Parallelism in Algorithms and Architectures (SPAA 2009), August 2009)
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    PDF (152k)

  • Tech report: Minimizing Communication in Linear Algebra
    (UCB/EECS-2009-62, May 2009)
    Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz PDF (560k)

  • Paper: A Generalized Framework for Auto-tuning Stencil Computations
    (Cray User Group Conference, Atlanta, GA, May 2009)
    [Winner, Best Paper]
    Shoaib Kamil, Cy Chan, Sam Williams, Leonid Oliker, John Shalf, Mark Howison, E. Wes Bethel, Prabhat
    PDF (354k)

  • Journal Paper: Communication Requirements and Interconnect Optimization for High-End Scientific Applications
    (IEEE Transactions on Parallel and Distributed Systems (TPDS), March 2009)
    Shoaib Kamil, Leonid Oliker, Ali Pinar, John Shalf
    Preprint PDF (8467k)

  • Paper: Optimizing Collective Communication on Multicores
    (HotPar 2009 , Berkeley, CA, USA, March 2009)
    Rajesh Nishtala and Katherine Yelick
    Paper: PDF (400kB)

    • 2008

  • Journal Paper: Optimization and Performance Modeling of Stencil Computations on Modern Microprocessors
    (SIAM Review, December 2008)
    Kaushik Datta, Shoaib Kamil, Samuel Williams, Leonid Oliker, John Shalf, and Katherine Yelick
    PDF (2.8 MB)

  • Paper: Benchmarking GPUs to Tune Dense Linear Algebra
    (Supercomputing 2008, November 2008)
    [Winner, Best Student Paper]
    Vasily Volkov and James Demmel
    PDF (648k)

  • Paper: Communication Avoiding Gaussian Elimination
    (Supercomputing 2008, November 2008)
    Laura Grigori, James Demmel, and Hua Xiang
    PDF (584k)

  • Paper: Stencil Computation Optimization and Auto-Tuning on State-of-the-Art Multicore Architectures
    (Supercomputing 2008, November 2008)
    Kaushik Datta, Mark Murphy, Vasily Volkov, Samuel Williams, Jonathan Carter, Leonid Oliker, David Patterson, John Shalf, and Katherine Yelick
    PDF (612k)
    Talk slides: PPT (12.9 MB)

  • Tech report: Communication-optimal parallel and sequential QR and LU factorizations
    (UCB/EECS-2008-89, August 2008)
    James Demmel, Laura Grigori, Mark Frederick Hoemmen, and Julien Langou
    PDF (1.6 MB)

  • Paper: Hybrid Electric/Photonic Networks for Scientific Applications on Tiled CMPs
    (Workshop on High Performance Embedding Computing, August 2008)
    Ankit Jain, Shoaib Kamil, Marghoob Mohiyuddin, John Shalf, and John D. Kubiatowicz
    Abstract: PDF (282k)
    Talk slides: PPT (5.1 MB)

  • Masters Report: pOSKI: An Extensible Autotuning Framework to Perform Optimized SpMVs on Multicore Architectures
    Ankit Jain
    PDF (5.3 MB)

  • Tech report: LU, QR and Cholesky Factorizations using Vector Capabilities of GPUs
    (UCB/EECS-2008-49, May 2008)
    Vasily Volkov and James Demmel
    PDF (1.0 MB)

  • Paper: Avoiding Communication in Sparse Matrix Computations
    (IEEE International Parallel and Distributed Processing Symposium, April 2008)
    James Demmel, Mark Hoemmen, Marghoob Mohiyuddin, and Katherine Yelick
    PDF (1 MB)
    Talk slides: PDF (6.2 MB)

  • Paper: Lattice Boltzmann Simulation Optimization on Leading Multicore Platforms
    (IEEE International Parallel and Distributed Processing Symposium, April 2008)
    [Winner, Best Paper for Applications track]
    Samuel Williams, Jonathan Carter, Leonid Oliker, John Shalf, and Katherine Yelick
    PDF (560k)
    Talk slides: PDF (10.4 MB) | PPT (2.6 MB)

    • 2007

  • Tech report: Using GPUs to Accelerate the Bisection Algorithm for Finding Eigenvalues of Symmetric Tridiagonal Matrices
    (UCB/EECS-2007-179, December 2007)
    Vasily Volkov and James Demmel
    PDF (1.8 MB)

  • Paper: Optimization of Sparse Matrix-Vector Multiplication on Emerging Multicore Platforms
    (Supercomputing 2007, November 2007)
    Samuel Williams, Leonid Oliker, Richard Vuduc, John Shalf, Katherine Yelick, and James Demmel
    PDF (438k)
    Talk slides: PDF (6.4 MB) | PPT (2.5 MB)

  • Tech report: Avoiding Communication in Computing Krylov Subspaces
    (UCB/EECS-2007-123, October 2007)
    James Demmel, Mark Hoemmen, Marghoob Mohiyuddin, and Katherine Yelick
    PDF (34.9 MB)

  • Journal Paper: Scientific Computing Kernels on the Cell Processor
    (International Journal of Parallel Programming, April 2007)
    Samuel Williams, John Shalf, Leonid Oliker, Shoaib Kamil, Parry Husbands, and Katherine Yelick
    PDF (376k)

  • Journal Paper: When Cache Blocking Sparse Matrix Vector Multiply Works and Why
    (Applicable Algebra in Engineering, Communication and Computing, March 2007)
    Rajesh Nishtala, Richard W. Vuduc, James W. Demmel, and Katherine Yelick
    PDF (390k)

  • Paper: Benchmarking Sparse Matrix-Vector Multiply in Five Minutes
    (SPEC Benchmark Workshop 2007, Austin, TX, January 2007)
    Hormozd Gahvari, Mark Hoemmen, James Demmel, Katherine Yelick
    PDF (1 MB)
    Talk slides: PPT (6.4 MB)

    • 2006

  • Master's Thesis: Benchmarking Sparse Matrix-Vector Multiply
    (Computer Science Division, U.C. Berkeley, December 2006)
    Hormozd Gahvari
    PDF (11.5 MB)

  • Paper: Implicit and Explict Optimizations for Stencil Computations
    (Memory Systems Performance and Correctness, San Jose, California, USA, October 2006)
    Shoaib Kamil, Kaushik Datta, Samuel Williams, Leonid Oliker, John Shalf, and Katherine Yelick
    PDF (604k)
    Talk slides: PDF (3.2 MB)

  • Paper: The Potential of the Cell Processor for Scientific Computing
    (Computing Frontiers 2006, Ischia, Italy, May 2006)
    Samuel Williams, John Shalf, Leonid Oliker, Shoaib Kamil, Parry Husbands, and Katherine Yelick
    PDF (216k)

    • 2005

  • Paper: Fast sparse matrix-vector multiplication by exploiting variable blocks
    (Proceedings of the International Conference on High-Performance Computing and Communications, Sorrento, Italy, September 2005)
    Richard Vuduc and Hyun-Jin Moon.
    PDF (322k)

  • Paper: OSKI: A library of automatically tuned sparse matrix kernels
    (Proceedings of SciDAC 2005, Journal of Physics: Conference Series, June 2005)
    Richard Vuduc, James Demmel, and Katherine Yelick.
    PDF (190k)

  • Paper: Self-Adapting Linear Algebra Algorithms and Software
    (Proceedings of the IEEE, Special Issue on Program Generation, Optimization, and Adaptation, 93(2), February 2005)
    James Demmel, Jack Dongarra, Victor Eijkhout, Erika Fuentes, Antoine Petitet, Richard Vuduc, R. Clint Whaley, and Katherine Yelick.
    PDF (600k)

    • 2004

  • Paper: Performance Models for Evaluation and Automatic Tuning of Symmetric Sparse Matrix-Vector Multiply
    (International Conference on Parallel Processing, Montreal, Quebec, Canada, August 2004)
    [Winner, Best Paper Award]
    Benjamin C. Lee, Richard Vuduc, James Demmel, and Katherine Yelick.
    PDF (178k) | Gzip'd PostScript (204k)
    Talk slides: PDF (540k)

  • Paper: Toward automatic performance tuning of matrix triple products based on matrix structure
    (PARA'04 Workshop on State-of-the-art in Scientific Computing, Copenhagen, Denmark, June 2004.)
    Eun-Jin Im, Ismail Bustany, Cleve Ashcraft, James Demmel, and Katherine Yelick.

  • Tech Report: Performance Modeling and Analysis of Cache Blocking in Sparse Matrix Vector Multiply
    (UCB/CSD-04-1335, June 2004)
    Rajesh Nishtala, Richard W. Vuduc, James W. Demmel, and Katherine A. Yelick
    PDF (~8MB)

  • Paper: SPARSITY: An Optimization Framework for Sparse Matrix Kernels
    (International Journal of High Performance Computing Applications, 18 (1), pp. 135-158, February 2004)
    Eun-Jin Im, Katherine A. Yelick, and Richard Vuduc.
    PDF (1.1M) | Gzip'd PostScript (1.2M)

  • Paper: Statistical Models for Empirical Search-Based Performance Tuning
    (International Journal of High Performance Computing Applications, 18 (1), pp. 65-94, February 2004)
    Richard Vuduc, James W. Demmel, and Jeff A. Bilmes.
    PDF (950k) | Gzip'd PostScript (983k)

    • 2003

  • Ph.D. Thesis: Automatic Performance Tuning of Sparse Matrix Kernels
    (Computer Science Division, U.C. Berkeley, December 2003)
    Richard Vuduc.
    PDF (7.6M)

  • Tech report: Performance Optimizations and Bounds for Sparse Symmetric Matrix-Multiple Vector Multiply
    (UCB/CSD-03-1297, November 2003)
    Benjamin C. Lee, Richard W. Vuduc, James W. Demmel, Katherine A. Yelick, Michael de Lorimier, and Lijue Zhong.
    PDF (867k) | Gzip'd PostScript (1.3M)

  • Senior Thesis: Effects of Block Size on the Block Lanczos Algorithm
    (Dept. of Mathematics, U.C. Berkeley, June 2003)
    Christopher Hsu
    MS Word (2.2 MB) | PDF (273k)

  • Paper: Memory Hierarchy Optimizations and Performance Bounds for Sparse ATA*x
    (ICCS 2003: Workshop on Parallel Linear Algebra, Melbourne, Australia, June 2003)
    Richard Vuduc, Attila Gyulassy, James W. Demmel, and Katherine A. Yelick.
    Abstract | PDF (328k) | Gzip'd PostScript (91k)
    Talk slides, PDF (735k) | Talk slides, gzip'd PostScript, 4-up (138k)
    Extended version: U.C. Berkeley Technical Report UCB/CS-03-1232

    • 2002

  • Paper: Performance Optimizations and Bounds for Sparse Matrix-Vector Multiply
    (Proceedings of the IEEE/ACM Conference on Supercomputing, 2002, Baltimore, MD, USA, November 2002)
    Richard Vuduc, James W. Demmel, Katherine A. Yelick, Shoaib Kamil, Rajesh Nishtala, and Benjamin Lee.
    Abstract | PDF (834k) | Gzip'd PostScript (2.7M)
    Talk slides, PDF (1.0M) | Talk slides, gzip'd PostScript, 4-up (159k)

  • Paper: Automatic Performance Tuning and Analysis of Sparse Triangular Solve
    (ICS 2002: Workshop on Performance Optimization via High-Level Languages and Libraries, New York, NY, USA, June 2002)
    Richard Vuduc, Shoaib Kamil, Jen Hsu, Rajesh Nishtala, James W. Demmel, and Katherine A. Yelick.
    Abstract | PDF (548k) | PostScript (1.2M)
    Talk Slides, PDF (681k)

    • 2001

  • Paper: Optimizing Sparse Matrix-Vector Multiplication for Register Reuse
    Eun-jin Im and Katherine A. Yelick.
    International Conference on Computational Science, San Francisco, California, May 2001.
    PDF (164k) Gzip'd PostScript (132k)

  • Paper: Statistical Models for Automatic Performance Tuning
    Richard Vuduc, James Demmel, Jeff Bilmes.
    International Conference on Computational Science, San Francisco, CA, USA, May 2001.
    PDF (410k) | Gzip'd PostScript (163k) | Talk Slides, PDF (685k)


 
Writing in preparation:
  • Tech report: Matrix Splitting and Reordering for Sparse Matrix-Vector Multiply
    Hyun Jin Moon, Richard Vuduc, James W. Demmel, Katherine A. Yelick.
    UCB Technical Report, 2003. (in preparation)
    Abstract (DRAFT)

Talks and Posters

(Talks delivered in conjunction with conference papers appear under Publications.)

Year: 2008 | 2005 | 2004 | 2003 | 2002

    2008

  • Talks: Microsoft/Intel Visit to ParLab
    Multiple Authors.
    (Berkeley, California, USA, April 28-29, 2008)
    Link to Talks

  • Talk: Avoiding Communication in Linear Algebra
    James Demmel.
    (SIAM PP 2008, Atlanta, Georgia, USA, March 12-14, 2008)
    Powerpoint (940k) | PDF (1.7MB)

  • Talk: Bandwidth Avoiding Stencil Computations
    Kaushik Datta, Sam Williams, James Demmel, Katherine Yelick.
    (SIAM PP 2008, Atlanta, Georgia, USA, March 12-14, 2008)
    Powerpoint (2.45MB) | PDF (3.05MB)

  • Talk: Fast Implementations of the Akx Kernel
    Marghoob Mohiyuddin, Mark Hoemmen, James Demmel, Katherine Yelick.
    (SIAM PP 2008, Atlanta, Georgia, USA, March 12-14, 2008)
    PDF (9.3MB)

  • Talk: Communication-avoiding Krylov subspace methods
    Mark Hoemmen.
    (SIAM PP 2008, Atlanta, Georgia, USA, March 12-14, 2008)
    PDF (952k)

    • 2005

  • Talk: The Future of Numerical Linear Algebra Libraries: Automatic Tuning of Sparse Matrix Codes and the Next LAPACK and ScaLAPACK
    (SciDAC 2005 Meeting, San Francisco, California, USA, June 2005)
    PowerPoint (305k)

  • Talk: OSKI: An automatically tuned library of sparse matrix kernels
    (SIAM CSE 2005, Orlando, Florida, USA, February 2005)
    Richard Vuduc, James Demmel, Katherine Yelick.
    PowerPoint | PDF

    • 2004

  • Talk: When Cache Blocking Sparse Matrix Multiply Works and Why
    (PARA'04 Workshop on State-of-the-art in Scientific Computing, Copenhagen, Denmark, June 2004)
    Rajesh Nishtala, Richard Vuduc, James Demmel, Katherine Yelick.
    PDF (147k) | Gzip'd PostScript (138k) | Talk Slides: MS PPT (3MB)

  • Talk: Adaptable benchmarks for register blocked sparse matrix-vector multiplication, Mark Hoemmen, Matrix Computations Seminar at U.C. Berkeley, May 5, 2004.
    PowerPoint (420k) | PDF (420k) | Link to Software

  • Talk: Performance Optimizations and Bounds for Symmetric Sparse Matrix-Multiple Vector Multiply
    SIAM Parallel Processing Meeting, San Francisco, California, USA, March 2004.
    PowerPoint (319k) | PDF (331k)

  • Poster: A Computationally Efficient Triple Matrix Product for a Class of Sparse Schur-Complement Matrices
    SIAM Parallel Processing Meeting, San Francisco, California, USA, March 2004.
    PowerPoint (678k) | PDF (177k) | PNG (504k) | GIF (436k) | JPEG (985k)

  • Poster: Automatic Tuning of Collective Communications in MPI
    An overview of the Probabilistic Algorithm Selection System (PASS) for finding and choosing the best implementation of a given MPI collective operation on a given hardware platform.
    PowerPoint (5.3M) | PDF (118k)
    Full report: PDF (1.9 MB)

    • 2003

  • Poster: Automatic Performance Tuning of Sparse Matrix Kernels
    This poster, shown at the Berkeley-Stanford CS Day (2002, 2003), Bay Area Scientific Computing Day (2002), and the SIAM CSE 2003 Meeting, summarizes our overall approach to tuning a number of sparse matrix kernels, including matrix-vector multiply (non-symmetric and symmetric), triangular solve, and multiplication by ATA.
    PowerPoint (1.7 MB) | PDF (617k) | PNG (520 kB) | GIF (715 kB) | JPEG (1.5 MB)

  • Talk: Automatic Performance Tuning of Sparse Matrix Kernels
    Presentation of recent work to Intel, with a discussion of ideas related to acceleration of the Google PageRank algorithm. (24 Jan 2003)
    PowerPoint (806 kB) | PDF (830k)
    Google matrix pics, PowerPoint (142 kB) | PDF (139k)

    • 2002

  • Talk: Automatic Performance Tuning of Linear Algebra Kernels
    This presentation, given at the TOPS-SciDAC kick-off meeting (25 Jan 2002), describes recent results performance tuning of sparse linear algebra kernels.
    PowerPoint (1.5 MB) | PDF (2.7 MB)

Related Projects

Current Local Activities

  • XBLAS: Extended and Mixed-Precision BLAS
  • Sparsity: A Toolkit for Optimizing Sparse Matrix-Vector Multiply
  • IRAM: Intelligent RAM Project
  • Titanium: High-Performance Java Compiler

Prior Projects

  • PHiPAC: An Automatic Tuning System for Matrix Multiply

External Collaborations

This research was supported in part by the National Science Foundation under NSF Cooperative Agreement No. ACI-9813362, NSF Cooperative Agreement No. ACI-9619020, the Department of Energy under DOE Grant No. DE-FC02-01ER25478, and a gift from Intel. The information presented here does not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred.
 
Standard disclaimer: Publications are presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.