[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 則是現在常被拿出來討論的解決方法之一。

[C++] Tips of Calculating Floor and Ceiling on Integer Types

C/C++ 寫了一段時間的人，應該或多或少會遇到一些簡便的偷懶寫法，例如不用暫存變數就交換兩個變數的值之類的，這類技巧雖然多半有著先天的限制條件，但是適用場合因為相當的廣泛，所以用的人其實不少。

這次要介紹的小技巧是在給定兩個型態是整數型態的變數 a & b，計算 $\left\lfloor\frac{a}{b}\right\rfloor$ 跟 $\left\lceil\frac{a}{b}\right\rceil$ 。

[C++] Loop Unrolling Using Metaprogramming

Loop unrolling (迴圈展開) 是 compiler 在編譯過程中基本常用的優化方式。然而， compiler 到底會不會採用 loop unrolling 其實完全由 compiler 決定，換言之，你可以預期 compiler 會做，但事實上 compiler 不一定會做，因此這邊介紹利用 metapromming 的方式，強迫使用 loop unrolling 的技巧。

[C++] Name Mangling (名稱修飾)

當初事先 PO 了一篇雜記提醒自己要寫這篇文章果然是明智的決定! 

迷之音：富堅了這麼久還敢說?

這篇要談的主題是 Name Mangling (名稱修飾)，這是個 C++ 用來實現 function overloading 的方法，然而這東西卻也可能會導致連結器 (linker) 要把兩個分別用 C 與 C++ 編譯完的 object file 連結起來時出現問題，因此這邊就來淺談這玩意兒。至於與其相關的 Overloading Resolution (重載決議)，因為實在有點複雜，需要不少版面來說明，就留到下一篇好了。繼續富堅的意味

[閒聊] 摩爾定律

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

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

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

[茶] 關於泡茶的三兩事

泡茶說來簡單，不過也可以很麻煩，因為其實就像泡咖啡，水溫以及水的流速等等會影響茶 / 咖啡在味道的萃取上有不同的影響，所以要泡一杯茶 / 咖啡很簡單，不過要泡的好，學問就很大。

[隨筆] puyo 的由來

之前跟朋友去吃飯時，因為混雜了同屆、學弟妹跟外校等等不同區塊的人，有些人比較獨特的綽號就會被問是怎麼來的，比方說明明是男的，綽號卻叫 rose 這樣 XD 不過這次主角不是他，是另一位被叫做 puyo 的人。相較於 rose 的來由是屬於當事人的黑歷史，不適合公開拿出來講，puyo 的來由是個適合闔家觀賞又富有遊戲性、動感與觸感的貼切形容。

[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 最好。

[C++] template value type extraction

各位如果翻開 STL container 的 document，應該會看到有一部分是寫 member type 的 document。其中應該會看到這樣的描述：

value_type : The first template parameter (T)

定義這種 type 其實用途不是為了 container 本身，而是為了使用這個 container 的 user，特別是使用這個 container 的地方是在 template class / function 時，定義這個 type 尤為重要，細節可以參考我之前寫的這篇。然而 C++ template 雖然可以讓程式撰寫上有更好的泛用性，但是因為需要做型態推導上，在使用上只要推導過程中會有疑義都會導致編譯失敗，也因此需要多做些手腳以便能夠順利編譯。這次要講的就是上次那篇 type function 的延伸