邁向王者的旅途

2015年6月5日

[EDA] Design Chanllenges of Standard Cells

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

2015年5月17日

[隨筆] 失落

因為事情的不順遂，所以失落
因為有所期待卻一再落空，所以失落
因為不如預期卻又不知原因，於是不停的鑽牛角尖還爆發了各種小劇場
也許一切都只是過度的妄想的猜測，但無法排除的可能令人憂心
也許時間過去會恢復原樣，但看不到終點的不確定感令人焦躁

只能等了，等著期望中的未來來到，期待一切的一切終究是過度的猜想

2015年5月16日

[品茶] 大吉嶺 - 凱瑟頓夜光白玉春摘

大吉嶺，印度靠近喜馬拉雅山那一塊，海拔相當高，因此植物的生長也較為緩慢，也較多水氣，故大吉嶺的茶葉相較於其他種類的紅茶通常具有較多芳香物質，因此大吉嶺的一大特色就在於他那相當迷人多變且細膩的香氣。這次嘗試的目標是凱瑟頓莊園的春摘，等級是夜光白玉。

2015年5月13日

[演算法] A Progressive Network-Flow-Based Heuristic for Finding Minimum Cost Clique Partition

minimum clique partition (MCP) 探討的是如何將一個無向圖 (undirected graph) 分成最少數量的 clique。若是無向圖上的邊具有權重的話，並且最少數量的 clique partition 有好幾組的話，則此問題要找的是所有 clique 上的所有邊的權重總和要是最小的那一組。因為這是個 NP-hard 的問題，因此若非一定要找出最佳解 (optimum solution)，一般將採用 heuristic 的方式找出一組次佳解 (optimal solution)。這邊要介紹的是基於 progressive network-flow 的方法找出一組解

2015年5月11日

[C++] The Previous Element of vector::begin() Is Not vector::end()

在使用 STL 的 container 時，相信類似以下這段 code 的片段不是什麼很希奇的事情

std::vector<int> vec;
// blah blah blah
if (--iter != vec.end()) { /* blah blah blah */ }

很顯而易見的邊緣判斷，當 iterator 已經是指向最一開頭的元素時，想要再往前存取前一個元素時就該停止了

不過這段 code 在一個特定的情況下會失效，就是當 iter == vec.begin() 時！沒記錯的話這問題發生在把 container 從 list 換成 vector

原因其實也不難懂，vector 底層的實作是 array，換言之 vector iterator 一般來說在其底層就會是個 array pointer。所以只要用 array pointer 的觀點來想就會知道為什麼那段 code 會有問題囉。

而 vector 因為底層是 array，但又需要能夠動態增減其大小，因此還會有 iterator validity 的問題 (確切一點的說法是所有的 STL container，但是 vector 最容易遇到)，類似這類的問題第一次遇到大概得要花上個數小時找問題吧...

2015年4月29日

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

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

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

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

2015年2月24日

[C++] 強制 STL container 釋放資源

一般來說 STL 的 container 都會提供一個 member function clear() 清除 container 內部的資料，不過我想大家也很常遇到一種情形是這樣的：

1. 先配制足夠的空間給 container
2. 開始存取運用 container 內的資料
3. 呼叫 clear 清空 container 的資料以便下次再度利用這個 container

一般我們可能會假設一呼叫 clear() 後 container 就會釋放所配置的資源，但在這種情境下就很容易出現頻繁記憶體配置與釋放。但這實際上是可以避免得，我們其實只要把儲存在 container 中的資料解構使其所利用的資源變成 raw memory，下次要再度使用時只要重新建構即可，如此一來我們即可省去記憶體是放與配置的冗長時間。基於這個理由，呼叫 STL container 的 clear() 其實不一定會釋放所持有的資源，可能僅僅將所儲存的資料解構而已，因此如果今天想要確保 container 必定會釋放所持有的資源的話可以這樣做 (以下用 vector 做範例說明)：

std::vector<int> vec;
// some operations
vec.swap(std::vector<int>());

當然更好的做法就是讓變數的 scope & 生命週期盡可能的小使其直接呼叫 destructor 來釋放資源囉。

[C++] The Use of priority_queue And decltype

在 C++ 中要使用 heap structure，最直覺的方法就是使用 STL 的 priority_queue。priority_queue 預設會假定你在 template parameter 所指定的 data type 會支援 operator<，並且利用 operator< 去對資料做排序。其預設的排序行為會行程 max heap，若需要使用的是 min heap，則必須在 template parameter 指定 compare function 或 compare object 的 type，並在 constructor 指定 compare functor 的行為。

在 C++11 推出前，為了提供自定義行為的 functor，會讓 code 變得稍稍難看了點 (請參閱 cplusplus 上的範例)，然而，運用 C++11 的 lambda expression 或是 decltype 即可讓程式碼變得更為簡潔易懂。

2015年2月14日

[遊記] 情人節來走情人谷步道 (南坪古道)

其實原本是看到健行筆記的這篇文章要去走南坪古道，後來對照地圖後發現網路上看到的資料其實是叫做 "情人谷步道"，或許以前是叫南坪古道，但現在的南坪古道不是指那條步道了 (google map 上有標示南坪古道，但沒有情人谷步道的地圖，要地圖的話請參考這份地圖，上面虛線部分就是情人谷步道，也就是健行筆記所講的南坪古道)

由於 google map 上標記的那條南坪古道不知道有啥東西，所以我們後來還是去走健行筆記上講的南坪古道，接下來的南坪古道也都是指我們實際走的路線。