Note: this reading group has concluded; this page is for archival and reference purposes only.
Time: Wednesdays 11:00-12:00 (Berkeley time)
Location: hybrid in-person (511 Soda)/Zoom
Slack: #hw-arch-theory on the EECS
slack (eecs.slack.com). Note that if you don’t have an
@eecs.berkeley.edu email, you will need to be specifically invited to
join, even if you have a @berkeley.edu 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 |
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!
PolySA: Polyhedral-Based Systolic Array Auto-Compilation (Cong and Wang ICCAD ’18)
Automated Derivation of Parametric Data Movement Lower Bounds for Affine Programs (Olivry et al. PLDI ’20)
A Model of Computation for VLSI with Related Complexity Results (Chazelle and Monier JACM Jul. ’85)
A framework for solving VLSI graph layout problems (Bhatt and Leighton JACM ’84)
A Computational Model for Tensor Core Units (Chowdhury, Silvestri, and Vella SPAA ’20)
Update (2024): Nate has constructed a new VLSI circuit complexity model that allows for both wire delays (as in the AT2 model of Chazelle and Monier) and input ports located anywhere on the chip. Check out his ITCS paper A VLSI Circuit Model Accounting for Wire Delay with Ce Jin and Ryan Williams!