[EDA] Negotiation-Based Maze Routing 的部分困擾

Negotiation-based maze routing 可以說是現在 router 的基礎架構了，這個主要因素來自於當有許多 Net 要共同競爭相同的路徑以便縮短線長時，這個機制會讓競爭激烈的地區有相對大的成本，讓有其他選擇的 Net 可以轉而選擇相對較差但仍能完成繞線的路徑。當然，這種機制聽起來很單純美好，實作起來時總是會有其他許許多多衍伸的問題

[EDA] Transmission Gate (傳輸閘) - Logic Switch using CMOS design

目前數位 IC 設計上所用到的電晶體分成兩種型態 P-type MOSFET (P-MOS) & N-type MOSFET (N-MOS)，兩者在數位 IC 設計上的功用都是當做開關 (switch)，用以控制電流是否能通過。另外由於 MOSFET 本身的特性：電壓要低於一定閥值 (threshold voltage) 才能導通，同時這個閥值不是固定的，會受到源極 (source) 訊號以及汲極 (drain) 訊號的電壓影響 (好像是叫 body effect，先進製程應該會有更多會影響 threshold voltage 的問題)，因此 P-MOS 跟 N-MOS 在啟動開關跟傳輸電流上各有差異：

[EDA] Routing Resource Estimation & Planning - Pattern Routing

• Resource Estimation: 重點主要是放在估算可用的 routing resource

• Resource Planning: 重點偏向粗略規劃 routing 的結果

其實這兩者現在很少有人分開來講，原因在於 planning 的結果先決條件就是估算可用的 routing resource 這一步算得有多準；相對的，estimation 做得再好，沒有 planning 就沒有意義，因此就我的經驗來說，目前沒有人會特地把這二步分開來講，而是提出一套完整的方法同時包含這二個步驟。這次就先整理最簡單、也最常被使用的一個方法：pattern routing，概念是來自於 [1] 這篇論文。

[EDA] Routing Estimation / Planning - 前言

不知道大家有沒有玩過 (或看過) 一個遊戲叫做 "Flow Free"？遊戲畫面長得像下面這樣

這遊戲簡單來說就是給你一堆點且有各自的顏色，目標就是把相同顏色的二個點連接起來，次要目標則是盡可能的填滿所有格子 (所以會看到有些線, ex: 白色的線, 很明顯地有更短的連法)，限制則是線段之間不能重疊 / 接觸到。

[EDA] Standard Cell Layout Design Guideline

筆記一下在畫 standard cell layout 時要注意的幾點事項，不過因為我做的主要是 digital high performance standard cell，其他類型的應該會有截然不同的綱要

[EDA] Steiner Tree v.s. Spanning Tree

一般演算法講到 greedy method 時都會用 spanning tree (生成樹) 當範例，因為 spanning tree 有 O(n log n) 的 greedy method 可以找到最佳解。相對於 spanning tree，某些情況人們會更偏好 Steiner tree (中文好像是翻成史坦納樹)，兩者雖然都是要找一個方法把給定的點連成一顆樹，並且一般都會要求 cost 要最低，但是一個很大的差別在於 steiner tree 允許連線時增加多餘的點，但 spanning tree 不行。有多餘的點可連差異會很大嗎？我想可以參考 wikipedia 這篇的圖例就會知道這差異有多大。簡單的一個結論是 minimum steiner tree 的 cost 是小於、最多等於 minimum spanning tree。

[EDA] Design Challenge in Rouoting Algorithm - 繞線演算法的設計困難處

在 IC 設計中，Routing (中譯：繞線) 的用意就是把需要連接的地方用金屬線連起來，概念很簡單。要判別一個 routing 結果的好與壞也很容易：計算總線長就好。因為總線長越長也就意謂著需要越多的金屬線以及空間，所以如果有許多種不同的 routing 結果，我們會選擇總線長最少的那個當成最後結果。

隨著製程的演進，現在 routing 要考慮的因素越來越多，因此在演算法的設計上也就越趨複雜，而且通常難以有個通盤考量的好結果。這一篇要來簡單的總結現在 routing 上最重要的設計考量 - 繞線資源的規劃與使用 (routing resource estimation & management, 以下簡寫 RREM)

[EDA] Design Chanllenges of Standard Cells

Standard cell (中譯：標準元件) 是數位 IC 設計的基本單元，指的就是諸如 AND 閘、OR 閘 ... 等等的邏輯閘或是 Flip-flop、latch 等記憶單元。因為數位 IC 有絕大部分都是這些基本邏輯閘，因此設計良好的 standard cell 絕對會對最後的 IC 成品有舉足輕重的影響。這篇只是簡單聊聊現在 standard cell 及其相關設計會遇到的問題，不會深入去談技術細節 (人懶就說)

[EDA] SubHunter: A High-Performance and Scalable Sub-Circuit Recognition Method with Prüfer-Encoding

識別子電路 (sub-circuit recognition, 以下簡稱 SR) 問題是給定一個大電路 (MC) 與一個小電路 (SC) ，希望能在 MC 中找出所有跟 SC 相同的部分。

此問題的應用在於可將原始較大的電路中特定功能的電路予以取代，如此可將原始電路的大小縮小，有利於降低後續電路的分析與驗證的複雜度與所需時間。

因此在 SR 問題中效能是非常重要的考量，同時必須確保演算法的擴展性足以應付電路的複雜度與大小皆有爆炸性成長的趨勢。

[EDA] Mordern IC Design in Advanced Technology Nodes

我猜可能標題不用看完，跟 IC design 無關的人就直接關掉了 XD

雖然等等要講的東西沒有很深入，但確實也不是對這領域沒興趣的人會想知道的東西就是了~

這篇其實只是簡單整理一下從碩班做到現在，做過的東西 & 看過的論文的一些整理與心得，不過因為我很懶，所以不用期待會看到完整詳實的數據或圖表 XD

[EDA] A Novel Fast Layout Encoding Method for Exact Multi-Layer Pattern Matching with Prufer-Encoding

其實這是一篇充滿心酸血淚史的 paper，從碩一開始做的計畫，碩二開始寫成論文投稿，歷經 3 ~ 4 次的投稿被拒，途中多次的修改與延伸才終於完成。期間其實也有把部分成果投到 workshop 去，不但被接受，還被選為 best paper，但投到國際期刊還是被 reject，各種傷心淚水流滿地...不過最後終於是投上 EDA 的 top journal 了。

這篇論文刊登在 2014 的 Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)，主題是探討在先進製程上很被看重的 DFM (Design for Manufacturing) - 可製造性設計的其中一個細項 - hotspot detection (或者是 pattern recognition)。

[EDA] Multiple Patterning Lithography (MPL)

IC 界很常聽到、paper 上也很常當作引言的摩爾定律告訴我們：IC 上的電晶體數目每 18 個月就增加一倍 ( 可以參考我之前寫的這篇文章 )。而這幾年的做法就是一直把電晶體的大小縮小，但是現在已經縮到 16nm 的等級了，預計再過個 1 ~ 2 年就會到 10nm，1 個原子大小也才 0.1 nm，在這種情況下，製造 IC 的難度跟以往是無法比較的，以現在製造上最常被拿出來討論的問題就是無法精細的做出設計者預期中的形狀導致的良率問題。MPL 則是現在常被拿出來討論的解決方法之一。

[閒聊] 摩爾定律

搞硬體設計的人一定都聽過的摩爾定律是這樣的：

"Over the history of computer hardware, the number of transistors in a dense integrated circuit doubles approximately every two years.

簡單翻譯的話就是說 IC裡的電晶體數目大約每兩年就增加一倍

[C++] Efficient Minimum Spanning Tree Construction without Delaunay Triangulation

這 title 是來自一篇 paper [1]，主要是探討如何在 O(n log n) 的時間內找出一顆 minimum spanning tree (MST)。等等，找 MST 這問題不是已經有許多方法可以用 greedy 的技巧在 O(n log n) 做到了嗎? 那這篇發表日期還是在 2001 年的 paper 是有何貢獻呢？原因是這樣的：傳統的 MST 演算法跟這篇要討論的問題其實有一點不同。不同的地方在於傳統 MST 演算法是給一個 undirected graph，要在這 graph 上找一顆 MST；這篇要討論的是給一堆二維座標平面上的點，任兩點間都可以用一條線連起來，要你找出一種連法使得所有的點都被連起來，並且線段總長是最短的。

這個問題其實也有一段時間了，正式的名稱是 Euclidean Minimum Spanning Tree (EMST) [2]。這問題最簡單的做法就是把每個座標點都當成 vertex，先建出一個 complete graph，edge 上的 weight 就是兩點間距離，然後在這個 complete graph 上找 MST 就是答案了。想當然爾，建 complete graph 的時間是 O(n^2)，所以這做法最花時間的地方是建 graph。因此 EMST 的演算法要討論的重點不是 MST，而是怎樣建 graph 最好。

[程式] 程式設計師永遠都會遇到的難題：document

注意：這是一篇抱怨 document 的問題多到讓我抓狂抱怨文

學過程式一段時間而且有看過 coding style 或是 clean code 之類的書籍或文章的應該都知道要有良好的註解或是 document，不然就是 coding 要注意命名、寫法之類的以提升程式可讀性，不過工程師最常做的就是懶得寫註解或文件。這到底有多重要呢？重要到看到兩個都做很差的程式會讓人腦溢血阿!!

[EDA] Timing Driven Placement

     Placement 在 EDA 的 back-end flow 中扮演著承先啟後的角色，電路中的所有的邏輯閘、Macro (比方說來自其他人設計好的電路)要在這個階段通通擺放在 "適當" 的位置。何謂適當的位置? 這沒有標準答案，純粹看想要達到怎樣的目的。比方說，如果希望最後總連線長度 (wirelength) 要最短，適當的位置就是擺完後的結果要可以滿足這個條件。然而隨著電路的設計越來越複雜 (根據我所看過的 paper 中，不論是做怎樣的題目，在 abstract 或 introduction 以這句話作為引言的我覺得有八、九成以上...) ，要考慮的問題其實越來越多，也越來越難解決。電路設計過程中最看重的 timing 就是其中之一。