[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 的延伸

[雜記] 下集預告：C++ name mangling & overloading resolution

一段時間沒 PO 文，本來還在思考下次要選 C++ 的什麼主題，今天有個學弟跑來問為什麼程式編譯後出現 "undefined referenced to ... "，然後不知道要怎麼解決。研究一段時間後發現是 C++ name mangling (名稱修飾，C++ 處理 function overloading 的技巧) 導致 linker 在 link 時找不到對應函式。正好是個不錯可以好好細講的主題，而且還可以扯上 C++ 的 overloading resolution (重載決議，也就是 C++ 如何決定一個 function call 有多個 function 可以選擇時，到底該忽叫哪個 function)。不過最近有不少事情要做，就請讓我繼續拖稿吧XD 之後看到這篇應該會記得要來寫的XD

[茶] 初探龍井 - 三峽之旅

其實事情的起頭是這樣子的：前陣子卡路里在哀怨找不到可以當水喝 (不過其實他的上限是一斤 $1500，這其實還滿好找的)、適合冷泡的綠茶。不過臺灣最多的其實是烏龍茶，就算是高山茶也多半走烏龍茶的風格。臺灣的綠茶我只想得到三峽的碧螺春，在稍做研究後發現三峽那邊的三大茶是：碧螺春、龍井與蜜香紅茶，其中碧螺春與龍井都屬於綠茶，而蜜香紅茶似乎是近幾年有點被吵紅的，因此最後就決定到三峽一趟，去親自嘗試這三種主要茶葉。

[筆記] MathJax - 好用的 blogger 數學編輯器

我在寫這篇文章因為需要撰寫大量的數學式子，不過因為 blogger 沒有提供這種功能，所以一開始的數學式子只能用很醜的方式來表達。但就在發佈文章後沒多久，float 大神就推薦了MathJax給我，是個可以在 HTML 上撰寫數學式子，而且不需要額外安裝軟體，只要 blowser 有支援 javascript 即可。

[程式] Gray Code Generation

來寫點昨天讀到 TAOCP (The Art of Computer Programming) 介紹 Gray Code (中譯好像是格雷碼) 的一點心得筆記 (花了一小時讀不到 5 頁...)。

[遊記] 銀河洞越嶺步道

銀河洞越嶺登山步道是條由新店通往貓空的步道，與上次去的樟湖、樟樹步道同屬二格山系步道。步道中途有個瀑布名為 "銀河洞瀑布"，同時瀑布附近有個內凹的山壁，其名為 "銀河洞"，步道之名也由此而來。

[隨筆] 堅持

(為什麼我的新注音的自動選字是 "煎匙".......)

最近挺常胡思亂想的，想東，想西，想到以前的種種，自己因為什麼樣的選擇導致了什麼樣的結果。從以前就覺得自己的龜毛癖與強迫症時不時會發作，結果好像就因此錯過了許多機會，而且都是在錯失機會後才發覺自己為什麼會有一些無謂的堅持。

[遊記] 樟樹步道賞桐花

近年來越來越多人去看被稱為五月雪的桐花，現在也有桐花季的網站，上面有介紹有哪些步道可以賞桐花，以及開花情況如何等等，有心要去看桐花的人我想這是個很好的參考資料。不過為了避開人潮，這次我去的是相較之下比較少人的樟樹 / 樟湖步道。

[筆記] 20140427 品酒會筆記

自從開始喝葡萄酒後，新竹這邊有酒友大約每個月會扮一次品酒會這樣 (不過其實喝的半隨興半認真XD)，喝到現在大約兩年了，其實這對我的幫助也滿大的，因為可以一次喝到比較多種類的酒，在建立資料庫的時候會快很多。這次的主題是柏根地

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

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

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

[EDA] Timing Driven Placement

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

[食記] 餐酒會 @ 竹北 Vincent's Foods & Drinks

自從加入葡萄酒社團後，新竹幫這邊大約每個月會有一次聚會，然後偶而會有隨性的餐酒會，今天的餐酒會地點是辦在竹北的歐式餐廳：Vincent's Foods & Drinks，搭配的酒是 Maison Lou Dumont 2009 年的一支廣域勃根地的白酒 + 四支不同村莊的村級酒。

[C++] Exception Safety & Guarantees

Exception Handling 是個大學程式設計課通常會教，但不會著墨太深，卻又很重要的東西之一。一般課程關於 exception handling 的部分通常在講解完該語言如何使用 exception 之後就差不多結束了，但是 exception 的重要性卻完全沒有被涵蓋其中，一般作業上也很難出到可以讓同學理解它的重要性何在，何況在僅講究有寫出來就好的作業/project 等情況下，即便是個適合使用 exception 的場合也多半不會使用，是以大多數沒有自行鑽研的人是不太了解的。這篇是來簡單淺談 C++ 的 Exception Handling 中的 exception safety 與 exception guarantees，內容主要參考自 Effective C++、More Effective C++ 以及 Exceptional C++。書中會更深入探討這部分，有興趣的人可以自行參閱。

[品茶] 茶帷-爾利亞春夏摘大吉嶺品飲心得

在某次茶友來找我泡茶時，因為聊到了素有茶中之香檳的大吉嶺在臺灣手搖飲料店其實相當的普遍，不過若想買到大吉嶺的茶葉其實沒有想像中的容易。大吉嶺因為只有在印度原產地出產的才能叫大吉嶺，換言之它是個只有進口才喝的到的茶。若是想喝到品質較好，也勢必需要找到有信譽的商家購買，在一開始時其實我是完全不知道要去哪邊找大吉嶺的茶葉的。後來網路上搜尋、茶友推薦後得知了三家店：PEKOE、綠碧 與 茶帷，這才開始探訪大吉嶺的奧妙。

[品茶] 綠碧 - 夏摘與秋摘大吉嶺

 大吉嶺，這個我們常聽到的紅茶名稱其實是印度的一個地名，可以參考 [1] 的地圖。那邊出產的茶因為其特殊的地型與氣候而有著迷人的風采，一開始所生產的茶葉是專門輸出給英國的，後來因為屢次得獎出名後也行銷到全世界了。大吉嶺紅茶的迷人風采來自於獨特的氣候環境，只有那邊所生產的紅茶才有資格叫大吉嶺紅茶，也有茶中之香檳的美稱 (價格也像香檳一樣不斐)。

[生活] 品味生活，從屏除一切靜下心開始

開始品茶品酒已經快 3 年了，最一開始其實只是很簡單的喜歡的一款茶，或是嚐到覺得喜歡的酒，沒有深入的研究，也沒有真正的了解過。真正開始學著去了解一款茶、一支酒是從葡萄酒開始，它帶著我進入了一個我從未接觸過的世界與交際圈，開始學著怎樣去了解所謂的 "飲品" 是什麼樣的概念與藝術。

[C++] rvalue reference & implementation class

之前在這篇文章有簡單的聊過 rvalue reference 這東西，當初標準會定義這個簡單來說就是為了效能，特別是 C++ 常常會暗地裡幫你做了一大堆你根本沒想到的事情，因此善用 rvalue reference 可以促使 compiler 提升程式的整體效能 -- 特別是避免無意義的複製這方面。

這篇主要是談 rvalue reference + implementation class 的結合可以產生什麼樣的效果，在 C++，由於 header file 必須定義好 class 的 declaration -- 包含使用者不需要知道的 private members，因此創出了 implementation class 這東西負責撰寫並處理原始 class 要做的事情，而要公開的另一個 class 就只有一個 private member 是 implementation class 產生的 object，而 public member 就是 implementation class 的 public interface。這個小技巧原本就如同前面所說，只是個用來 client 不會看到不用知道的東西，除此之外確實是沒什麼效果，但是 rvalue reference 的出現讓這個效果可以有提升效能的作用。

[C++] Type Erasure (型別抹除) - A Technique of Behavior Abstraction

    其實我真正要寫的是這篇XD 只是剛好有例子會用到 Functor，所以就順道寫了那兩篇 functor 的介紹。Type erasure (後面都會簡寫成 TE) 其實不算是 C++ 語言中的特性，應該算是一種技巧，用來避開 C++ 在編譯過程中型別檢查造成的麻煩 (所以才會叫型別抹除)。這項技巧其實在 C 也有，只是 C++ 因為引入了 OO，所以 C 的型別抹除技巧不能完全套用在 C++ 上，就如同 qsort 在 class 上會撞牆是一樣的情況 [2]。另一方面，C++ 因為有了 template 可以使用，所以這項技巧可以有了更好的發揮空間。同時，TE 也扮演了 template 跟 OO 之間的接合劑 (聽起來好像有點奇怪...) [3]。一個最顯而易見的例子就是 std::sort 的第三個參數就是運用了 TE 的技巧，所以他可以吃進任何可以像 function 般操作的東西，而不管你扔進來的東西的型態為何。

[隨筆] 博士的訓練

曾經有人這麼跟我說過：

如果你直接繼續念博班，那麼你就是拿你人生最精華的時間去做一場極大的投資

也有人這麼跟我說：

所謂的讀博士，就是拿你人生最精華這段時間，用來讓自己在各個方面都準備好 面對各種挑戰，在自己的領域中補足自己所有缺乏的部份，當你從博士班畢業的時候, 就可以從容的應對各種困難

以前我難以理解所謂的 "所有" 缺乏的部分，現在我知道這句話的來由。也因此我慶幸我遇到了一個對我來說對的指導教授，只是這場極大的投資何時能回收還要再過好幾年才能知道

[C++] type function

前陣子看到一個有趣的資料結構叫 pairing heap，單純看複雜度來說比 fibonacci heap 高
不過 pairing heap 的操作很簡單，所以複雜度的 constant 不大
是個頗吸引我的資料結構，所以這陣子有想要自己實做，然後試著做成像 STL 那樣的架構
一研究下去發現，STL 果真是集工程師智慧之大成，一大堆看不懂的技巧在裡面Orz

這篇是記錄之前看不懂得其中一樣設計：type function
這幾天翻書翻到才搞懂這設計的意義為何

[C++] Functor (仿函式) - A Function-Like Object PART II - The Use of Functor

在 PART I 時我們簡單的介紹了下 qsort，並且說明了在結合 OO 時將會遇上一些問題，現在就讓我們來看看會遇上怎樣的問題吧！

[C++] Functor (仿函式) - A Function-Like Object PART I - Start From qsort

Functor 簡單來說就是具有 function 功能的 object
因此 functor 讓我們可以像是呼叫 function 般的去使用一個 object
這個技巧賦予我們在寫程式時更方便與安全的方法