Every student in the course will work on a term project. The goal of the class project is to study a particular problem/application in some detail, so as to get a more in-depth understanding of the problem beyond basic textbook knowledge. The project can be based on: 1. Implementation and experimental evaluation of basic physical design techniques on placement, floorplanning, global or detailed routing, clock-tree synthesis, congestion modeling, etc. 2. Theoretical study, or feasibility study, of CAD problems related to phsical design of emerging technologies. 3. Application of fundamental CAD techniques from the physical design domain to non-physical design problems. If you are having some difficulty in chosing a relevent project option, then my suggestion would be the following. [Note that this is just a suggestion, you are free to undertake any study-project that interests you]: Some of you may not have enough experience in computer-aided design of VLSI systems. In such a case, option 1 would be more suitable for you. This will give you some idea about how CAD tools are designed and developed, and how CAD algorithms are employed on various graph-theoretic models and abstractions of circuit netlists. You will also get an opportunity to study contemporary literature in physical design tools and techniques, run some experiments with available CAD tools, and also try a (partial?) implementation of a particular technique. So, first think about whether you are interested in placement, or floorplanning, or routing problems, and then consider the options that I have listed below. Some of you are already working on VLSI-design and CAD techniques for your own research/development work. Then, options 2 & 3 might be of interest to you. So here is a suggestive list, with some references: 1. Study and implementation of known tools and techniques: i) Partitioning-based floor-placement. Try standard-cell or macro-cell based placement. Igor's toolset -- CAPO, Parquet, and MLPart, are good starting points for this set of topics. See his website and related publications: http://vlsicad.eecs.umich.edu/BK/PDtools/ ii) Global Routing: Prof. David Pan's work on BoxRouter: http://www.cerc.utexas.edu/utda/download/BoxRouter.htm along with other global routers also found on Pan's website, such as MaizeRoute and FGR. iii) Detailed Routing: Study and implement Channel Routing, and/or its extension to Over-the-Cell routing for standard cells. Start with channel routing in the book, and study the Yoshimura-Kuh (YK) router. iv) How to use integer programing in Global routing efficiently: GRIP: Global Routing via Integer Programing, by Wu, Davoodi and Linderoth, IEEE TCAD 2011. http://homepages.cae.wisc.edu/~adavoodi/ v) Global and/or detailed Routing for via minimization Search the web for a lot of information, e.g. the tool FastRoute by Prof. Chris Chu: http://home.eng.iastate.edu/~cnchu/pubs/ vi) Spanning trees and Stiener tress in routing/wire-length estimation: The FLUTE paper, again by Prof. Chris Chu, TCAD 2008, see his website above. vii) Simulated annealing based techniques in place-n-route: the Timberwolf std cell placer. viii) How to model routing congestion maps in place-n-route, start with Igor's paper on co-ordinated placement and routing (Co-PR): J. Hu, M.-C. Kim, I. L. Markov, ``Taming the Complexity of Coordinated Place and Route'' , in Proc. Design Automation Conference (DAC), pp. 150-155, Austin, TX, 2013. [Look at all the references in his paper to find other related publications]. ix) Thermal-aware placement of ICs: How are thermal constraints modeled in placement? They usually use force-directed techniques, or even some simulated annealing based methods. Similar techniques are also needed for "thermal via" insertion, to get the heat out of the chip (SiO2 acts as an insulator that traps the heat within the chip, so metal vias conduct the heat out of the chip). Here is a list of papers: A Thermal-Driven Force-Directed Macro Cell Placement Algorithm http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4064412&tag=1 Thermal placement based on heat conduction methodology, Jing Lee, IEEE Trans. on packaging (?) June 2003 Efficient thermal placement of std cells in 3D ICs using a FDA, Sapatnekar, ICCAD 03. See also, placement of thermal vias. J.-L. Tsai, C. C.-P. Chen, G. Chen, B. Goplen, H. Qian, Y. Zhan, S.-M. Kang, D.-F. Wong, and S. S. Sapatnekar, “Temperature-Aware Placement for SOCs,” Proceedings of the IEEE, Vol. 94, No. 8, pp. 1502 - 1518, August 2006. // Decent paper, good references Analytical Thermal Placement for VLSI Lifetime Improvement and Minimum Performance Variation, Andrew Kahng, ICCD 2007 -- also see reference 23, 24, on temperature gradient computation. Temp. aware routing in 3D ICs, Prof. Sachin Sapatnekar's website [Univ. Minnesota] //Yet another paper, looks like same formulation as Sapatnekar's Wire Congestion And Thermal Aware 3D Global Placement, Karthik Balakrishnan, Vidit Nanda, Siddharth Easwar, and Sung Kyu Lim, (Georgia Tech), ASP-DAC Conf., 2005. [This thermal-stuff is a *hot* topic today, so a google search with give you a huge list of papers, look at the recent published papers]. 2. Now let us consider Option 2: i) Placement and Routing problem in microfluidic bio-chips/lab-on-a-chip. Refer to the numerous papers by Prof. Krishnendu Chakrabarty at ECE/Duke university. You may start with: http://people.ee.duke.edu/~krish/DAC2007_51.1.pdf ii) Placement and Routing in reversible/quantum-logic circuits, such as quantum-dot cellular automata (QCA). I recall the papers by Prof. S.K Lim, Georgia Tech: www.gtcad.gatech.edu/www/papers/01500704.pdf. I'm sure there are a few more papers that address similar problems. iii) Placement and routing in integrated optics. My former student Chris Condrat's PhD dissertation is the best resource [As me if you want to browse through it]. You can download some of his channel routing papers from my website. iv) You VLSI guys know what are FinFETs? How do FinFETs affect placement and routing, if at all? v) Want to study CAD techniques for lithography, manufacturability and yeild enhancement? As I recall more such topics, I'll update this list.... 3. Now on to Option 3. You would have noticed by now that many fundamental techniques find application in so many areas in CAD. So if you have some experience in other CAD domains, you may want to apply some of the physical-design techniques to those other applications. i) Network Flow based techniques for FPGA synthesis http://cadlab.cs.ucla.edu/~cong/papers/tcad94.pdf [Really cool paper] ii) Network-flow based circuit verification, by Prof. Ciesielski. Arithmetic Bit-level Verification Using Network Flow Model [I have asked him for a copy of the paper]. iii) Partitioning techniques in constraint programming. This is a fundamental problem, finding applications in many search-based solvers. I have not kept in touch with recent developments, so interested students should do a literature search. You should start by browsing through one of my older papers: http://www.ece.utah.edu/~kalla/papers/iccad04.pdf Can such techniques be applied to other optimization problems, branch-n-bound, dynamic-programming? To search for publication venues: 1. IEEE Trans. on CAD 2. Design Automation Conference (DAC) 3. Intl. Conf. on CAD (ICCAD) 4. Intl. Symposium on Physical Design 5. ACM Trans. on Design Automation (ACM TODAES)