| Presentation | 2021-03-04 [Special Talk] Efficient VLSI Layout Data Structures and Algorithms Shmuel Wimer, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Moore's Law which stopped delivering CMOS device speedup for already a decade is still delivering and will do so for the foreseeable future the geometry scale down premise of 2X transistors/area increase every 24 months. Among other design complexities arising from this on-going nano-scale miniaturization, there is the huge amount of physical layout data which is used all over the chip design backend phase and later on for tape-out and mask generation. The physical layout activities involve "polygon-pushing" and manual fixes handled by mask designers, through automatic extraction of electrical parameters (RC-extract), design rule checking (DRC), design for manufacturability ruled (DFM) and layout Vs. schematics checking (LVS). These backend applications are followed by mask manipulations and optical proximity corrections (OPC) required for manufacturing. All the aforementioned applications require efficient organization for fast navigation through the huge amount of polygons comprising the underlying layout, supported by appropriate data structured and algorithms for layout traversal and manipulations. Though such organizations are usually hierarchical, at a certain points all the layout applications may work on millions of polygons at once. To this end several commonly used data structures and algorithms which are used by most of today's commercial EDA tools are presented. These involve layout extraction and manipulations by scan-line algorithms using Segment-Trees, Interval-Trees and Priority Search-Trees. Some techniques for layout navigation using 2D Range-Trees and KD-Trees will be presented too. Run-time and storage complexities will be discussed together with comments on software implementation. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | VLSI Layout / EDA Backend Tools / Scan-Line Algorithms |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | HWS / VLD |
|---|---|
| Conference Date | 2021/3/3(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Design Technology for System-on-Silicon, Hardware Security, etc. |
| Chair | Makoto Ikeda(Univ. of Tokyo) / Daisuke Fukuda(Fujitsu Labs.) |
| Vice Chair | Yasuhisa Shimazaki(Renesas Electronics) / Makoto Nagata(Kobe Univ.) / Kazutoshi Kobayashi(Kyoto Inst. of Tech.) |
| Secretary | Yasuhisa Shimazaki(Kyushu Univ.) / Makoto Nagata(NTT) / Kazutoshi Kobayashi(Hitachi) |
| Assistant | / Takuma Nishimoto(Hitachi) |
| Paper Information | |
| Registration To | Technical Committee on Hardware Security / Technical Committee on VLSI Design Technologies |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | [Special Talk] Efficient VLSI Layout Data Structures and Algorithms |
| Sub Title (in English) | a Brief Tutorial |
| Keyword(1) | VLSI Layout |
| Keyword(2) | EDA Backend Tools |
| Keyword(3) | Scan-Line Algorithms |
| 1st Author's Name | Shmuel Wimer |
| 1st Author's Affiliation | Bar-Ilan University(Bar-Ilan University) |
| Date | 2021-03-04 |
| Paper # | |
| Volume (vol) | vol. |
| Number (no) | |
| Page | pp.pp.-(), |
| #Pages | |
| Date of Issue | |