Reading Group on the Intersections between Architecture and Theory, Spring 2022

Note: this reading group has concluded; this page is for archival and reference purposes only. Depending on interest and speaker availability, we may host another such group in the fall.

Time: Wednesdays 11:00-12:00 (Berkeley time)

Location: hybrid in-person (511 Soda)/Zoom

Slack: #hw-arch-theory on the EECS slack ( Note that if you don’t have an email, you will need to be specifically invited to join, even if you have a email; please contact the organizers if you need this.

Organizers: Grace Dinh and Nate Young

Goals: This reading group interested in the intersection of hardware and theory. In particular, much of “classical” theory is based on models, such as Turing machines and Boolean or arithmetic circuits, that only very loosely resemble the systems people program on today. Real-world performance depends on many more factors, and new computational models (limited-fast-memory model, polyhedral model, TCU model, etc.), more similar to real-world hardware, have been developed to allow for the derivation of stronger lower bounds and to develop algorithms that can run more efficiently in practice.

We seek to understand these models, and to see whether these models (and the algorithms and bounds based on them) can be combined or improved to provide insights into both theoretical and practical problems in both algorithms and hardware.

Date Speaker Topic and Notes
2/23/2022 Grace Dinh, Nate Young Intro
3/02/2022 Nate Young, Jonathan Greene VLSI lower bounds [Slides 1, Slides 2]
3/09/2022 Nate Young, Grace Dinh Finish VLSI Lower bounds; Matrix multiply lower bound
3/16/2022 Grace Dinh Communication-optimal tiling and loop reordering for nested loops [Slides]
3/23/2022 Spring Break No Talk
3/30/2022 Nate Young Polyhedral models and hardware (PolySA, AutoSA) [Slides]
4/6/2022 Grace Dinh TCU computational models [Slides]
4/13/2022 Nate Young Pebbling/HBL and vavefront lower bounds, IOLB [Slides]
4/20/2022 Bhaskar Roberts, Mathias Weiden Circuit designs for near-term quantum computers [Slides]
4/27/2022 Nate Young Updates on VLSI theory [Slides]
5/04/2022 Round table discussion Conclusion: future research directions and brainstorming

List of Interesting Papers

A preliminary list of papers that may be of interest are listed below. If you’re interested in talking about one of them, or would like to suggest an additional papers, please send us mail or message us on the slack. Thanks!