| Andrew Kahng | abk-tilos@eng.ucsd.edu | Identifying "doomed runs" of an IC routing tool | The “detailed routing” step of IC place-and-route can take many hours or days. The routing tool must construct a set of trees of wire segments, where each tree connects a prescribed set of terminals of logic gates in the chip design. The trees cannot touch each other. Routing tools perform many iterations of “ripup-and-reroute” to gradually reduce the number of design rule violations in the routing solution. But if the tool cannot reduce the violations to a usable level (e.g., 2000 violations can be fixed by an expert engineer in a week), then the run is useless. This project will try to predict “doomed runs” (or, a final number of violations) based on information available at the initial iterations of the routing tool. Being able to terminate “doomed runs”, without terminating runs that will eventually succeed, has very high value in the chip design process. | Dr. Seungwon Kim, sek006@eng.ucsd.edu | (1) Slides 10, 11, 12 in: https://vlsicad.ucsd.edu/NEWS18/malenda-kahng-talk-distributed.pdf (workshop talk at DAC-2018)
(2) GitHub: TritonRoute https://github.com/The-OpenROAD-Project/OpenROAD/tree/master/src/drt
(3) A. B. Kahng, L. Wang and B. Xu, "TritonRoute-WXL: The Open Source Router with Integrated DRC Engine", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2021), doi:10.1109/TCAD.2021.3079268 https://vlsicad.ucsd.edu/Publications/Journals/j136.pdf | Google Doc open for comments (please use @abk-tilos@eng.ucsd.edu to flag for attention): https://docs.google.com/document/d/1rOHx6fYesH-XgKHKyNZcWy30lF33WvAJEEJKFBwZBj0/edit?usp=sharing | 03/09/2022 |
| Tara Javidi | tjavidi@eng.ucsd.edu | Empirical Optimization of Band-limitted (Graph) Signals For Networks | We have developed an adaptive sampling method for empirical (zeroth order) optimization of a function in reproducing kernel Hilbert space with a known kernel. We are interested in extending this work in the following directions:
1. A special case of RKHS is that of band-limited functions where our algorithm can be precisely compared to a Shannon/Nyquest sampler. This view suggests similar correspondence might be of interest when the input space consists of graphs.
2. Practically, data needs to be used to identify the kernel and estimate parameters. I am interested to work with networking and chip use case folks to see how such estimation can be optimized. | Tara Javidi
Farinaz Koushanfar | Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS. https://arxiv.org/abs/2005.04832
AdaNS: Adaptive Non-Uniform Sampling for Automated Design of Compact DNNs | | 03/11/2022 |
| Andrew Kahng | abk-tilos@eng.ucsd.edu | Learning Good Hierarchical Clustering in Clock Distribution | The clock signal is the “heartbeat” of any synchronous digital circuit. The clock signal is distributed from a “clock source” to every “clock sink” (flip-flop) via a rooted “clock tree” of wires and buffers. For figures, see the reference Doc. (1) The clock signal should reach every sink at roughly the same time: this is the goal of “zero skew” or “bounded skew” (e.g., Charikar et al., SODA99). (2) Also, the clock tree should have minimum total wirelength, since more wirelength means more power consumption. (3) And, the clock signal must be “refreshed” every so often, because a logic gate can only drive a limited amount of capacitive load. Thus, the clock tree has a hierarchy of “clock buffers”, each of which sends the signal onward to a bounded amount of wiring and child buffers/sinks.
The goal is to learn how to hierarchically cluster sinks and buffers in clock trees, based on “good example solutions” obtained by running clock tree synthesis (CTS) in commercial place-and-route tools. Benchmark testcases and solution quality evaluators, and potentially relevant metadata/features, can be provided. See the “2013_CTS_study” link in the reference Doc. | Ravi Varadarajan, rvaradarajan@ucsd.edu
Matt Liberty, mliberty@eng.ucsd.edu | M. Charikar, J. Kleinberg, R. Kumar, S. Rajagopalan, A. Sahai and A. Tomkins, “Minimizing Wirelength in Zero and Bounded Skew Clock Trees”, Proc. SODA, 1999, pp. 177-184. http://web.cs.ucla.edu/~sahai/work/web/1999Publications/SODA1999.pdf
A. Z. Zelikovsky and I. I. Mandoiu, “Practical Approximation Algorithms for Zero- and Bounded-Skew Trees”, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.1047&rep=rep1&type=pdf
See images in HTML files linked from https://vlsicad.ucsd.edu/2013_CTS_study/index.html .
E.g., “Click to change level” in https://vlsicad.ucsd.edu/2013_CTS_study/uni_high_ar2.html . Can we learn this clustering, and what vertex or layout features determine this clustering? | Google Doc open for comments (please use @abk-tilos@eng.ucsd.edu to flag for attention):
https://docs.google.com/document/d/1_AQNf6N75fz6cBtoQSX3hJsQNJV20DHmTIrZO9NkCvQ/edit?usp=sharing | 03/13/2022 |
| Andrew Kahng | abk-tilos@eng.ucsd.edu | Clusters That Stay Together | A chip design can be viewed as a hypergraph with lots of metadata/labels on vertices and hyperedges. A complex sequence of heuristic algorithms will place this hypergraph onto the layout region of the chip. The goal is to reduce problem size without losing solution quality by clustering the hypergraph, such that each cluster “stays together” in the placement. I.e., we want to learn how to cluster “with no mistakes”. Even a 10X problem size reduction “with no mistakes” would have a huge impact on chip design practice. See Slide 6 of the first reference.
See also the “Tutorial on chips + ML” (second reference). The existing collaborators can provide relevant data such as hypergraphs, various metadata on vertices and hyperedges, information from placements returned by a commercial place-and-route tool, etc. | Zhiang Wang, zhw033@ucsd.edu
Bodhi Pramanik, bpramanik@eng.ucsd.edu | Slide 6 (see talknotes as well) in this PPTX file from the TILOS Retreat (January 6): https://docs.google.com/presentation/d/17ENPs9KLt4MoHtTRdhaXapNweC6auRlm/edit?usp=sharing&ouid=107509409457975522044&rtpof=true&sd=true
Work in Progress: “Tutorial on chips + ML”, https://docs.google.com/document/d/15cr32aB1Q7kawFwNq__DvL0_CkzimXr8BTx4Xk0lFGY/edit?usp=sharing
M. Fogaça, A. B. Kahng, E. Monteiro, R. Reis, L. Wang and M. Woo, "On the Superiority of Modularity-Based Clustering for Determining Placement-Relevant Clusters", (.pdf) Integration: The VLSI Journal 74 (2020), pp. 32-44. | Google Doc open for comments (please use @abk-tilos@eng.ucsd.edu to flag for attention): https://docs.google.com/document/d/12RqI4FVKcLNfaZq1wCiac3sm3C-duj3qxHYSvuWSnyE/edit?usp=sharing | 03/13/2022 |
