My Take on ASP-DAC on
its 20th AnniversaryDavid Z. Pan
Dept. of Electrical and Computer Engineering
The University of Texas at Austin
http://www.cerc.utexas.edu/utda

1

Congratulations to ASP-DAC!

2

Congratulations to ASP-DAC!

3

Disclaimert I am truly honored and humbled to be asked togive this talk, for the 20th anniversary celebrationt There are many, many key contributors of ASP-

DAC who are more qualified than me to give thistalk, in particular, on the history of ASP-DAC, etc.
(I need to grow more gray hairs for that J)t I will share my personal experience andperspective

4

So, where was I in 1995?
t The first ASP-DAC was held 08.29-9.1.1995 in Makuharit At that time, I was a graduate student in Physical Sciencest Just took an introductory CS classt Know nothing about VLSI or CADt So, I was really a new born baby in EDA J

Luckily, I met Prof. Jason
Cong who introduced me
into the new world of EDA

5

I received thisaward last nightas Prof. Jason
Cong’s proxy6

My ASP-DAC Historyt My first ASP-DAC paper in 1999 (Hong Kong)t My second ASP-DAC paper in 2001 (Japan)t -----------------------------------------------------------------------t My first physical attendance at ASP-DAC was actually 2005

– exactly 10 years ago in Shanghai J

› G. Xu, L. Huang, D. Z. Pan and M. D.-F. Wong, “Redundant-Via
Enhanced Maze Routing for Yield Improvement”› 10-year Retrospective Most Influential Paper Award Candidatet Regularly submit papers to ASP-DAC› 30 papers at ASP-DAC (including several invited papers)t Best Paper Award twice (2010 and 2012)t Best Paper Award Nomination in 2006, 2008, 2013t ASP-DAC Frequently Cited Author Award7

My first ASP-DAC paper, in 19998

Interconnect Layout Optimizationt E.g., UCLA TRIO (Tree, Repeater,Interconnect Optimization) Package› Interconnect topology optimization› Optimal buffer insertion› Wiresizing optimization› Global interconnect sizing and spacing› Simultaneous driver, buffer & interconnect sizing› Simultaneous topology generation with bufferinsertion and wiresizingt Delay can be improved many times

Main Results and Impactt Develop a set of delay estimation models, underdifferent optimizations such as wire sizing, driversizing, buffer insertion/sizing, etc.
› Closed-form formula or simple characteristic equations› Constant running time in practice› High accuracy (about 90% on average)› Great for interconnect planningt Impacts:› Citation: 68 (based on Google Scholar)› Widely adopted by industry (IBM, Freescale, Intel, etc.)› Jason Cong’s SRC Technical Excellence Award in
2000, for "Interconnect Estimation, Planning andSynthesis for Deep Sub-micron Designs"10

My second ASP-DAC paper, in 2001

11

Main Results and Impactt Develop a closed-form crosstalk noise model, which has

high fidelity cf. detailed spice simulationst Unified previous crosstalk noise modelst Great to guide crosstalk optimizations during physicalsynthesis (buffer insertion, driver sizing, spacing, …)t Impacts:› Citation: 146› US Patent issued› Used by Magma (acquired by Synopsys)

12

My first physical presence at ASP-DAC, Shanghai, 2005

13

Main Results and Impactt The first paper on redundant via aware routingt Proposed on-track, off-track redundant viast Constrained optimization with Lagrangian Relaxationt Impacts:› Citation: 91› 10-year Retrospective Most Influential Paper AwardCandidate› The first paper on redundant via aware routing› All major fabs strongly recommend redundant vias
› All modern EDA commercial routers have redundant via
insertion awareness

14

ASP-DAC 2008

MeshWorks: An Efficient Framework forPlanning, Synthesis & Optimization ofClock Mesh Networks
Anand Rajaram§* and David Z. Pan§§ ECE Department, University of Texas at Austin.

* DDSP, Texas Instruments, Dallas.

Main Results and Impactt We proposed a systematic methodology for clock

mesh planning, synthesis, and optimizationt Impacts:› Citation: 42› ASP-DAC’08 Best Paper Candidate› The first paper on fully automatic clock mesh synthesis› Clock mesh design was mostly done manually before› Now it is available in EDA tools as high-performance
ASIC designs may need some mesh-like structures todeal with PVT variations

16

ASP-DAC 2010

A New Graph-Theoretic, Multi-Objective
Layout Decomposition Framework forDouble Patterning Lithography
Jae-Seok Yang, Katrina Lu, Minsik Cho, Kun
Yuan, and David Z. PanECE Department, University of Texas at Austin

17

What is Double Patterning?

AStitchEmindp

Overlay Error
18

A Graph-Partitioning Based, MultiObjective Decomposer[Yang+, ASPDAC10]

Decomposition Graph Construction
E

A
A(17)

Ē1

Ā

Ā(20)

2X(9)

1E

AY

Ē

ZX

Z(5)

E

1A
Ē

Ē(17)

1E(15)

ĀY(9)2Constraint:(A, Ā) and (E, Ē) are repulsive pairs.

ĀTheorem : Stitch minimization problem is equivalent to themin-cut partitioning of the decomposition graph
Extensions of the framework: to incorporate otherconstraints and costs into graph partitioning, e.g., balanced
density, overlay compensation, and so on19

Main Results and Impactt First holistic framework to consider overlay

compensation, stitch minimization, and balanced
density togethert Easily adjust weights/multi-objective; very fastt Impacts:› Citation: 51› ASP-DAC 2010 Best Paper Award› IBM Research 2010 Pat Goldberg Memorial Best
Paper Award in CS/EE/Math (among all papers in verybroad areas under CS, EE, and mathematical sciencesco-authored by IBM’s 4000+ researchers in 2010)› Industry usage of double/triple patterning (layoutdecomposition is a key step for both mask/PD)
20

Back in 2003

”Daddy, don’t worry. I can show
you some bright idea!”“Double patterning!!!”21

ASPDAC 2012, Sydney

EPIC: Efficient Prediction of IC
Manufacturing Hotspots using a
Unified Meta-Classification Method
Duo Ding, Bei Yu, Joydeep Ghosh and David Z. Pan
Dept. of Electrical and Computer Engineering
The Univ. of Texas at Austin
http://www.cerc.utexas.edu/utda

Main Results and Impactt Proposed a novel meta-classification method tounify machine learning and pattern matching
methods togethert Impacts:› ASP-DAC 2012 Best Paper Award› ASP-DAC 2011 paper: “High performance lithographic
hotspot detection using hierarchically refined machinelearning” (citation: 30)› Helped spark the ICCAD 2012 CAD Contest, organized
by Mentor Graphics, on “Lithography HotspotDetection” (many teams participated)› Very well attended ASPDAC’15 Special Session on“Machine Learning in EDA” yesterday
23

ASP-DAC is Truly International
ASP-DAC Top Authors(based on DBLP, up to 2014)24

Xianlong Hong (56)
Massoud Pedram (41)Martin D. F. Wong (38)
Yici Cai (36)
Chung-Kuan Cheng (34)
Jason Cong (33)
Hidetoshi Onodera (29)Sheldon X.-D. Tan (28)David Z. Pan (27)Yuan Xie (26)Andrew B. Kahng (25)Sung Kyu Lim (23)Hai Zhou (22)Kwang-Ting Cheng (21)Masanori Hashimoto (21)Jing-Yang Jou (20)
Sachin S. Sapatnekar (20)
Kenichi Okada (20)
Kaushik Roy (20)Nozomu Togawa (19)
Tsutomu Sasao (19)Lei He (19)Rolf Drechsler (19)Yao-Wen Chang (19)How to Win an ASP-DAC BPA?
t I hope I have a secret saucet Seriously, just submit your best work to ASP-DACt Then don’t worry about itt Right topic + elegant algorithm + a lot of luck!

25

ASP-DAC Best Paper Statistics
Based on published data missing years 2004, 2001,and 1995-1999

Count other author countries as wellOnly count first/contact authors

26

Moore’s Law 50th Anniversary!
t Moore’s original paper in 1965

[Moore, 1965]
27

Moore’s Law Amendment
NO EXPONENTIAL IS FOREVER…
BUT
WE CAN DELEY “FOREVER”[Moore, ISSCC 2003]

Future “EDA” Researcht More Moore: continue pushing the envelope,14nm, 11nm, 7nm› Multiple patterning and emerging lithography› Computational scaling (CAD tools still very sub-optimal)t More than Moore: New CAD issues› Vertically – 3D IC integration› New device/material: FINFET, III-V, graphene, …
› New domains: Bio, Photonic, …
› New applications: energy, big data, security,automotive, …
t “EDA” – Extreme Difficulty Automation› You can do anything if you can handle “EDA”
29

I

ASP-DACASPDAC’06, Yokohama

ASPDAC’12, Sydney

ASPDAC’15 TPC Meeting
Daejeon30