2024 ICCAD Problem B

新增boost package

$ make boost

之後commit前請先確保自己的code會通過cppcheck

$ make cppcheck

An IU a day keeps the bad code away. Contributed by Cheng

Funny flipflopXD

• 2024 ICCAD Problem B
  • 1. Introduction
  • 2. Contest Objective
  • 4. Solution Flow?
  • 5. Reference Paper
    • 0. Slack Redistributed Register Clustering with Mixed-Driving Strength Multi-bit Flip-Flops
    • 1.Graceful Register Clustering by Effective Mean Shift Algorithm for Power and Timing Balancing.
    • 2.Flip-flop clustering by weighted K-means algorithm
    • 3.Generation of Mixed-Driving Multi-Bit Flip-Flops for Power Optimization
    • 4.INTEGRA: Fast Multibit Flip-Flop Clustering forClock Power Saving
    • 5.Post-Placement Power Optimization with Multi-Bit Flip-Flops
    • 6.FF-Bond: Multi-bit Flip-flop Bonding at Placement
    • 7.Agglomerative-Based Flip-Flop Merging with Signal Wirelength Optimization
    • 8.Improved Flop Tray-Based Design Implementation for Power Reduction
    • 9.Power-Driven Flip-Flop Merging and Relocation
    • 10. Abacus: Fast Legalization of Standarc Cell Circuits with Minimal Movement
  • Taskflow Simple Usage & Install
  • Force Directed Placement
  • Other cluster algorithm
    • K-means
    • SVM
    • Halfspace
  • hmetis manual & binary
  • Draw Die
  • 留言區
  • TODO
  • some boost usage with static linking

1. Introduction

Using multibit flip-flops (FFs) to replace multiple single-bit FFs offers several advantages:

• Reduction in area
• Decrease in power consumption
• Potential timing issues (when converting multibit to single bit, known as debanking)

2. Contest Objective

For the ICCAD 2024 problem B, we need to consider the following objectives:

1. Timing
2. Power
3. Area
4. No cell overlapping

Timing slack need to consider both displacement delay & Q-Pin delay. (Try not to move FF far away…)

Cost function:

$$\begin{array}{c}\sum _{\mathrm{\forall }i\in FF}(\alpha \cdot TNS(i)+\beta \cdot Power(i)+\gamma \cdot Area(i))+\delta \cdot D\end{array}$$

where

$$\{\begin{array}{ccc}TNS(i)& =& totalnegativeslack\\ D& =& \mathrm{\#}binviolateutil\\ \alpha & =& TNSweight\\ \beta & =& Powerweight\\ \gamma & =& Areaweight\\ \delta & =& Violateweight\end{array}$$

For each bin, can not exceed density constraint. (BinMaxUtil). Or might lose some score due to penality.

切bin是為了估placement density，才可以去預估routing difficulty…

4. Solution Flow?

Given the preplaced FF, can we not solve globally, can we use some corsening to generate the initial solution such as ntuplace3?

and next, we can apply the flip flop clustering to further optimize in the uncorsening stage, or we just solve flatten?

5. Reference Paper

0. Slack Redistributed Register Clustering with Mixed-Driving Strength Multi-bit Flip-Flops

Paper

PPT

Video

• 演算法流程
  藍色部分為此篇的創新演算法

1. Window-Based Adaptive Interval Graph Construction

   為了避免某些FF的feasible region較大造成cluster後的displacement過大在最開始先設定window大小由左至右、由下至上掃過一整個chip

   

   沒有global optimize

2. Coordinate transform

   先計算在window內的FFs的feasible region，若有overlap則代表有機會cluster，可以將feaible region overlap的關聯性變成intersection graph

   此intersection graph的關係可以用X,Y的兩個sequence來表示，先將所有矩形順時針轉45度並產生新的X'Y'座標，根據矩形X'座標與Y'座標的start point(S)與end point(E)可以獲得不同FF的先後關係資訊
   

3. Finding possible merged FFs & Maximal Clique Extraction

   在X' sequence中的S,E交界處插入decision point(D)，在這邊會把X'Y'座標中S與E相鄰的FF remove，因為代表此FF沒有與其他FF overlap。接下來每一個decision point會做一次判斷，看哪些FF可以cluster，它將S在D前的FF設為related FF，接著從Y'的sequence中找出由related FFs所組成的max clique(Partial Y')

   

4. Candidate Choose

   找E在previous and current decision point中間 & S在next and current decision point 中間的
   ->這兩種都是FF的feasible region與related FF較近的
   同時會計算每個candidate FF最大的feasible region，即從connected path中可借到的最多salck，若此region與maximal clique的overlapping region未overlap則從candidate中移除

   

   這篇採用inclusion force來決定要選擇哪個candidate
   (larger means less slack borrowing and smaller impact on original maximal clique)

   

   Fatt (Attractive factor) : 考慮feasible region與maximal clique的overlap region的xy距離遠近
   

   

   Frep (Repulsive factor) : 受到目前的maximal clique與candidate FF本身所屬的maximal clique size差異影響，這裡的斥力為candidate FF與其maximal clique的排斥程度
   

   

   SMFFj代表candidate FFj所屬的maximal clique的size

   代表不小於SMFFj的FF perfect size

   代表比SMFFj小的FF perfect size

   第一、二條式子代表SMFFj比perfect size更大、小的情況
   從第三條式子可以看出若SMFFj剛好為perfect size則Frep=0

   計算完inclusion force後根據大小排序，從最高force的candidate加入maximal clique並更新overlapping region，直到clique size達到perfect size或沒有candidate後停止。

   這裡的perfect size可以由題目給定的FF決定，另外可以加入power與displacement權重考量

   *決定好哪些FF要cluster後要將其移除X' sequence

5. Slack Release

   在當前iteration clustering的FF，其diamond region可以壓縮到僅包圍MBFF的矩形，並將多餘的slack分給其他connected and unclustered的FFs

• 資料結構

  因為需要一直做slack redistribution，X'中FF的順序會一直改變，因此儲存X'Y' sequence用red-black tree可以快速delete and insert

可以改用VanEmdeBoas tree嘗試進一步加速: insert delete lookup O(lglgN)

• 實驗結果比較

  與mean shift algorithm相比在timing的部分稍顯退步，但在power的結果較好，rumtime部分也比採用平行運算的mean shift algorithm快一點點

1.Graceful Register Clustering by Effective Mean Shift Algorithm for Power and Timing Balancing.

from iccad 2015 problem c

Paper

Github

• Code execution:

#Install boost first
$ wget https://boostorg.jfrog.io/artifactory/main/release/1.84.0/source/boost_1_84_0.tar.gz
$ tar xvf boost_1_84_0.tar.gz
$ ./bootstrap.sh --prefix=/usr/local/
$ ./b2
$ setenv BOOSTDIR "/home/vdalab/coherent17/boost_1_84_0"
$ setenv LD_LIBRARY_PATH "$BOOSTDIR/stage/lib"
    
$ git clone https://github.com/waynelin567/Register_Clustering.git
# Change CFLAGS in makefile to "CFLAGS = -O3 $(DEPENDDIR) -fopenmp -std=c++17 -lboost_program_options"
$ make -j
$ ./bin/clustering <input> <output>

演算法大綱: 透過改良傳統的mean shift algorithm並且整合KNN的概念，來進行cluster。

• 傳統的mean shift algorithm

1. 建立Density Surface
2. Gradient Ascent來移動資料點至最近的peak
3. 系統收斂後，在同一點的即為相同的cluster

想法:
假設FF的初始位置為機率分布函數(PDF)，想辦法找到這個機率分布函數

$f(x,y)$。 用類似Fourier Expansion的方式，在每個資料點上放一個Kernal Function，而後將

$n$個Kernal Function的總和視為Kernal Density Estimator(KDE)。

原本的Mean shift algorithm:

$$\begin{array}{c}f(x)=\frac{1}{n{h}^d}\sum _{i=1}^{n}K(\frac{x-x_i}{h})\end{array}$$

where

$$\{\begin{array}{ccc}n& =& \mathrm{\#}datapoint(FF)\\ h& =& bandwidth\\ d& =& Dim\end{array}$$

其中

$K$是Kernal function，用以擬和Density Surface，會需要是一個對秤原點的方程式，在論文中使用Gaussian Function:

$$\begin{array}{c}K(u)=\frac{1}{\sqrt{(}2\cdot \pi )}\cdot e^{\frac{-1}{2}}{u}^2\end{array}$$

可以思考是否要維持使用Gaussian Function而不使用其他Kernal Function。
因為Gaussian Function計算相對複雜，如果使用三角波的superposition會不會比較簡單?
只是要確保該Kernal Function積分起來要是1就好。
或是可以使用某個正比於FF的參數來控制積分起來要是多少。

前面所提到的

$h$控制的類似Gaussian中的

$\sigma$，控制視野，因此若是h越大，Gaussian function底下的寬越大。

當h很小時，所有FF會自成一類，但是當h很大時，視野會很大，因此很有可能會將所有FF都歸在同一類:

因此如何決定

$h$也是很重要的事情。

• Kernal Density Estimator Visualization

會是這樣的概念，基本上就是很多Kernal Function的Superposition

建完density surface之後，對FF做gradient ascent，往density surface中的peak移動。

考慮到整體的座標，因此可以看出中心不會在該cluster中間(可以用KNN來限縮影響範圍)

https://colab.research.google.com/drive/1ZN9Ku9mcUwqLLArbum8pQgHzgiC1czLZ?usp=sharing

這篇論文提出說h不該是定值，應該要將h設為變數，用timing constraint來定義h要是多少。而後，建立density surface時，不需要考慮所有的FF的位置，只需要考慮前M近的FF就好，以免FF的displacement過大，因此他先使用KNN來找到前K近(Manhaton Distance)的，再去建density surface再做gradient ascent來做FF cluster。

$$\begin{array}{c}{h}_i(x_i)=min(h_{max},\alpha ||x_i-x_{i,M}||)\end{array}$$

透過KNN找到第M近的neighbor與自己的距離，而後如果是非常timing critical 的FF那就可以將

$\alpha$設為接近0，因此

$h_i$便會很小，因此會比較容易自成一類，讓displacement也不會有太大的影響。

因此

$h_i$便是

$x$的變數了，因此在計算gradient的時候便需要考慮該項。

除了displacement delay，能否把

$Dela{y}_{D2Q}$也納入考量?

所以綜合以上

$h_i$的調整及整合

$KNN$，新的density function為:

$$\begin{array}{c}f(x)=\frac{1}{n}\sum _{i\in KNN(x)}\frac{1}{h_i^d}K(\frac{x-x_i}{h_i})\end{array}$$

要思考KNN是否只用距離來當作參數，AREA POWER能否一概考慮?
需要有一個機制來讓超過MTFF library制定規定bit的FF移動到其他的cluster。

• 平行化的可行性: 因為每個FF都是個別去相對於原本的座標點來做計算及移動，因此只要一開始先有一份原始座標點的副本後，每個FF都是可以被平行計算的。

但我認為這邊有個問題，因為當

$F{F}_A$在移動後

$F{F}_B$仍是看到它原本的座標，這樣會不會不太好?是否有更好的方式讓

$F{F}_B$可以考慮到的是移動後

$F{F}_A$的座標?

2.Flip-flop clustering by weighted K-means algorithm

[Paper] https://home.engineering.iastate.edu/~cnchu/pubs/c88.pdf

3.Generation of Mixed-Driving Multi-Bit Flip-Flops for Power Optimization

Paper
主要的貢獻為mixed-driving的MBFF、MBFF的bit數可以留一個empty bit藉此組成更多MBFF

流程可以分成：

• 取得原始design中FF的fanin/fanout pin位置及它們的timing slack
• 計算FF feasible region
• 找到rectangular intersection graph對應到的可以merge的maximal group FFs
• 組成MBFFs
• MBFF location assingment
• bit which has redudant slack downsize in MBFF

1. 計算FF feasible region
   feasible region由manhattan circle決定，中心點為fanin/fanout pin，radius為FF和其fanin/fanout的timing slack，將slack透過look up table的方式轉換成wirelength bound。
   ix-driving feasible region有交集的可由graph Gi表示，vertex代表ix-driving feasible region of a FF，有edge代表兩個的feasible region有交集
   ex :
   有clique代表原FF組成MBFFs不會有timing violation
   

   

2. 找到graph中的maximal clique
   將chip順時鐘轉45度後利用sweep line method，透過延伸ix-driving feasible region的垂直線，將平面劃分成多個vertical strip。從上到下scan each strip，辨別舉行的top boundary(in-edge) and bottom boundary(out-edge)，如果clique大小大於正上、正下方的clique則代表其為當前strip的maximal clique。
   ex :
   如下圖中，左圖的maximal clique in middle strip為{B1,C1}, {A1,B1}，右圖的maximal clique in second from right strip則為{A2, B2, C2}
   

   
   每個strip中取得的maximal clique還要跟前面的strip比，如果有clique為其他clique的subset則移除，以此方式得到Gi內的所有maximal clique。

3. Non-conflict MBFF generation
   對於每個clique c、每種library內的k-bit MBFFs隨機產生min(|c|取k,samle bound)個MBFF candidates，然後再選cost最小的成為c的candidate。

   • 計算new MBFF μ的cost：
     定義FF的合併彈性𝛿為每個intersection graph Gi的maximal clique有包含到此FF的數量總和
     ex :
     𝛿(e) = 3，𝛿越小代表該FF越少merge的選擇->越早merge它
     
     

   公式：
   

   

   D(μ) : 平均的𝛿 in μ
   B(μ) : number of used bit
   Power(μ) : FF power of μ
   OriPower(μ) : 組成μ的FFs原本各自的power加總
   𝛼i : switchgin rate of signal i
   OriWLi : 原本signal的HPWL EstWLi : 與μ有關的signal i用μ預估的position所估計出來的HPWL，它是由所有連接到μ的cell的x,y座標取weighted median算出
   λ1,λ2,λ3為user define的參數

   公式可以加入displacement的估計？

   • 得到所有maximal clique的MBFF candidate後，開始產生MBFFs

   

   line3,4 : according to cost push into priority queue Q
   line6 : 選Q中minimal cost的MBFF μ
   line8-11 : 檢查μ中的FF f是否和已產生的MBFF Nm conflict
   line12-15 : 若沒有conflict，μ加入Nm並mark all FFs in μ
   line16 : 包含μ的maximal clique c(μ)會remove所有marked的FF而減少其size line17 : 若reduced clique c' size仍≥2，產生新的c'的candidate push到Q內(新的加在Q last?)

   repeat line 5-18直到Q empty

4. location assignment

   • 先計算fanin/fanout pin X/Y座標的weighted median interval，pin的weight為MBFF與pin之間的signal net的switching rate，透過這兩個weighted median interval的交集決定出preferred region
   • 切割placement area into bins，把MBFF preferred region cover的bin稱為preferred bin，preferred bin的rank設為0，根據MBFF feasible region包含到的其他bin與preferred bin的距離，rank編號遞增，每個MBFF分配到其feasible region內rank最低的bin
   • locate MBFF到所選bin內最接近preferred bin的vacant slot
   • 此篇paper設定slot的大小為2x-driving 2-bit MBFF size，確保MBFF與其他cell的overlap minimize，讓commercial tool可以解決(這邊我們要想如何確保完全無overlap)

   可以參考這篇MBFF placement的決定

• 實驗結果
  有和mean-shift比較沒有empty bit及identical-driving的版本，在runtime上和mean-shft差不多，#sink少了40%、FF area少了8%，power少了4.5%，看起來timing也有比較好(沒有比較displacement)，但是mean-shift只有到分cluster所以後面MBFF的決定是用他們另外的方法分的。

4.INTEGRA: Fast Multibit Flip-Flop Clustering forClock Power Saving

Paper

• 基本上是0.的前身
  • 對於整個chip計算feasible region
  • 將feasible region轉換成方形
  • 透過decision point去找出max cliques
• 可能可用的想法:
  • 利用0-1背包問題的想法去選擇怎麼cluster FF
  • 預先利用輸入的參數去算出每個FF的cost，將redundant的FF剃除
• 問題:
  • 輸入會有Preclustered MBFF?

不是很重要的筆記

5.Post-Placement Power Optimization with Multi-Bit Flip-Flops

Paper

基本上這篇演算法流程可以分為:

• 先對MBFF library做前處理，計算每個MBFF power/bit的效率(這篇是Optimize for power)
• 用progressive window sliding找到可以被merge在一起的多個FF
• 建立TSFG(timing slack free group)，透過B&B找到哪些bit合起來比較好的候選人
• 接著從這些候選人中找到independent set來確認哪些FF要合在一起
• 最後透過考慮placement density及HPWL找到該MBFF要放在哪個bin上

• a.Progressive window sliding & expansion
  

(a)是2x2 bins來找到局部最佳解，比起整個電路flatten下去解，透過只考慮框框內做最佳化會比較好，為了找到更好的解，會再把windows size調大(b)。而後續再做FF cluster & placement時只會考慮到該框框內的所有FF。

(a)可以看成是先cluster成許多小單位的MBFF，而後調大kernal size(window size)後，做的便可能是多個小的MBFF的cluster，或者是MBFF與single bit FF的cluster。

• b.建立TSFR & TSFG

  • TSFR(timing slack free region)
  

  能否以兩個pin為圓心取圓面積的交集，並且develope有效率的計算方法? (grid base??)

  • TSFG(timing slack free group)
  

  f1 & f2因為TSFR有重疊，因此可以構成一個TSFG，也就是如果f1跟f2 bank在一起，放在這個重疊區域不會有timing violation的問題。便可以將f1 & f2視為一個TSFG

  

將每個FF視為一個node，如果兩個FF間的TSFR有重疊，那就將他們之間加一個edge。當這個intersetion graph建好之後，如果要找m-bit的FF cluster，便可以將問題變為找到所有的m-clique的問題，可以透過branch & bound來解。

補充: What is clique?
就是一個graph的subgraph，且對於subgraph中的所有vertex，任兩點都會有一條邊。

因此上圖可以找到兩個4-clique:

• $G^4=(g_1^4,g_2^4)=(n1,n2,n3,n4),(n1,n3,n4,n6)$

那究竟要將哪個合為4-bit FF呢?找到TSFG的independent set(IS)。

• IS(independent set) 接著，為了將前一步找到的TSFG進一步分類為哪些FF要合在一起，因為有些FF會重複出現在不同的clique中，因此這邊需要決定該FF要跟誰合在一起，因為該FF不會影分身之術，可以一次存在兩個cluster中。這邊他提出的演算法是考慮了Area及HPWL來greedy的做決定，而非DP來解optimal solution。

因此他便會先去排序剛剛

$G^m$中所有組合的面積(intersection area)減HPWL後，而後

$F^{\prime }$為記錄已拜訪過的FF，然後

$G_{IS}^m$則為那些不重複的

$g_i^m$

舉例: 假設4-clique問題:

$G^4=(g_1^4,g_2^4,g_3^4)=(n1,n2,n3,n4),(n1,n3,n4,n6),(n6,n7,n8,n9)$

$i=1$:

$F^{\prime }$={n1,n2,n3,n4},

$G_{IS}^4=(g_1^4)$

$i=2$:

$g_2^4$中有元素與

$F^{\prime }$重複，skip

$i=3$:

$F^{\prime }$={n1,n2,n3,n4,n6,n7,n8,n9},

$G_{IS}^4=(g_1^4,g_3^4)$

因此共可以合出兩個4-bit FF

• MBFF placement 這邊在placement的時候有兩個考量:
  • 1. Placement Density
       基本上就是將MBFF擺在前面圈起來那些FF的intersetion中的bin，挑bin density小的擺
  • 2. Interconnecting Wirelength
       找到這些FF原始座標的中位數，找到與前面intersecton重疊的部分，如果找不到就往附近的座標外擴

6.FF-Bond: Multi-bit Flip-flop Bonding at Placement

Paper

PDF

能否整合原子半徑的問題，與前面mean shift所提到的視野bandwidth

$h$來做呢?

eg:
MBFF Library = 元素週期表
FF = 價電子
動態的

$h$ = 原子半徑
正比於當下cluster了多少FF，用於決定現在的視野要多大?

能否結合熱力學第二定律:系統會朝熵增(最大亂度，最低能量)的方向前進? 非退火而是analytical的方式去找到熵增的方向?

在placement階段做MBFF cluster,因為在post-placement階段做FF的移動要考慮到slack限制，flexibility和solution quality有限

如上圖，找一超過perfect size的clique，FF當作是要釋放的e，和另一個undersized clique吸引結合，藉由此FF bounding force，引導每一個FF移動到適合合併的position(有點像在placement時先分好哪些FF成為MBFF，每一次iteration都讓同一群clique的越來越接近)

像上圖原本FF1~FF4因為feasible region沒有完全重疊，沒辦法做cluster，如果把FF2往FF3移動讓他們overlap就可以改善cluster result

可以想成允許負的slack存在的情況，讓feasible region沒有重疊的FF也cluster在一起形成perfect size

• FF bonding演算法
  利用INTEGRA這篇的方式提取maximal clique並分成oversized, perfect, undersized cliques，處理的優先順序為perfect->undersized->oversize，perfect size的先保留，其他兩個則在指定區域選擇最近的FF以形成target-sized clique，undersized clique照clique size降序順序處理(沒有說oversized的)

  

  若maximal clique有overlap，對於相同size的clique先處理有較多independant FFs(只存在於一個maximal clique)的clique

  
  如上圖，在處理完1,2後，3沒有independant FF->跳過該clique

不確定已經被合併的FF是否要從其他maximal clique內去掉並更新size、重新排處理的order

7.Agglomerative-Based Flip-Flop Merging with Signal Wirelength Optimization

Paper

使用了bottom up的方法來做FF clustering

這篇FF cluster主要分成以下幾步:

• 1. Construct intersection graph
• 2. FF merging
• 3. FF placement

提到了其他幾篇paper的缺點: reference paper5: sliding window-based會喪失掉globel view

在論文中提到這句話:

our approach avoids identifying maximum clique which is unnecessary when given MBFF library is limited. 你們怎想?

• a. 先用slack constraint來建立movable zone，並且一樣做座標轉換

  

• b. 建立intersection graph(with rb-tree & sweep line algorithm)

先將所有的長方形依照x座標排序，而後用紅線依序來掃，如果掃到就放進rbtree，掃完就移除rbtree，並且只需要判斷rbtree中的長方形是否有重疊就好，全部掃完就可以建好intersection graph。

會不會出現complete graph -> 長方形都移不出rbtree -> 需要比較超多次…

可以用VanEmdeBoas tree來加速: insert delete lookup O(lglgN) https://github.com/coherent17/NYCU-Physical-Design-Automation/blob/main/Lab2_Floorplan/include/Fast_Priority_Queue.h

• c. 如何建立intersection graph的edge cost?

  (1)是算所有連接到
  $f{f}_i$的pin的x, y方向的平均值
  (2)是算
  $f{f}_i$與
  $f{f}_j$之間在intersection graph 中的edge cost。

• d. FF merging

  

從前面所建立的intersection graph中按照edge cost由小到大來試著merge ff。如果成功被merge起來的FF，則會將原本的node移除，並加上新的node代表merge FF。merge的終止條件為intersection graph中沒有edge了

(c) => (d)這步因為

$M_{AB}$與E沒有形成clique，因此在(d)中就沒有產生新edge去相連。

• e. FF placement
  先計算merge FF後所有的pin的x, y方向的平均值，而後投影到mergeable Zone(??)。先看有沒有人佔據該投影到的點，及是否違反density constraint。如果有違反則使用BFS來找到最近可以擺放MBFF的地方，如果都還是找不到，則會將他們debanking，回歸還沒merge的狀態。

他這邊沒有仔細地解釋如何投影…

given flip-flop library is limited => is that still need to find the max-clique in x-bit ff clustering?

agglomerative algorithm time complexity is big!

line sweep to construct the intersection graph: https://leetcode.com/discuss/study-guide/2166045/line-sweep-algorithms

8.Improved Flop Tray-Based Design Implementation for Power Reduction

Paper (SAT解? 給我自己記得用的)

• 特色:

  • 可以使用任意大小的MBFFs。
  • 包含MBFFs合成以及擺放。
  • 最小化timing-critical start-end相對位移，使得FFs可能被擺放在feasible region外(?)。
  • Global-aware optimization。

• 方法:

  • 使用1 bit FF找出初始位置(ideal location for FFs)，再利用K-meas 找出合適的MBFFs。

  • 透過不斷迭代兩個演算法

    1. Min cost flow(capacitive K-means optimization)來clust FFs。
    2. Linear programming 找出optimal location。

    最後使用ILP來找出optimal的MBFFs組合以及擺放位置

• Methodology

  Multi-step algorithm : 先選擇要cluster的FF，再選擇要擺放的位置，裡面有提到因為複雜度的原因所以辦法同時考慮不同bit數以及aspect ratio的MBFFs(也許我們可以往這方面優化?)。

  1. Capacitated K-Means Clustering(紅框部分)

     1. 將FFs cluster到N/K個K-bit MBFF，使用min-cost flow演算法。
     2. Linear programming找出合適的位置。
     3. 重複1、2直到收斂或是達到迭代上限。
     4. 重複3直到所有的MBFF都被使用過。
     • MBFFs的初始位置
       

     隨機從一個FF開始，離這越遠的FF越有機會被選到，直到選到N/K個起始位置。

     • Min-cost flow
       
       • $h:FFs$
       • $f_{i}j:\mathrm{第}i\mathrm{個}MBFF\mathrm{的}\mathrm{第}j\mathrm{個}slot$

     cost是使用曼哈頓距離，(這裡可以encode其他cost function來達到優化的目標)。

     • Linear programming for location

       

       最小化在這個MBFF裡所有FF的displacement。

       

     • 結果比較

       

     • Too long I do not understand cluster的初始位置會影響最終的結果，所以這裡引入了func，他可以計算solution quality，他利用這個以及重複隨機初始位置，再跑一小段(15 epoch)capacitated K-means，去看結果，之後在利用cluster的結果作為下一次初始位置。

       

  2. ILP-Based Matching Optimization

     • Given : 不同size的MBFFs以及他們的位置。
     • Target : 找出最佳的subset，s.t. :
       1. 每個FF都有被map。
       2. total displacement和MBFFs cost是最小的
     

(5)

$W:costforMBFFs$

$D:totaldisplacementforallFFs$

$Z:relativedisplacementforalltimingcriticalpairs$

(6)(7)(8) constraint for displacement for all FFs.

(9)(10)(11) relative displacement

(12)(13) force

$e_i$ to be 1, if

$MBF{F}_i$ is used

(14) total cost for MBFFs

(15)(16) Ensure each FF is assign to single MBFF and each slot of MBFF is matched to at most one FF.

• The impact for

  $\alpha$ and
  $\beta$ are discuss in papar (但我覺得這部分不太重要，我們可以直接用題目給定的參數)

• Experiment Result

  
  $opt\mathrm{\_}mb$是propesed，
  $opt\mathrm{\_}m{b}^{\prime }$是限制能使用的MBFF，做為跟
  $ref\mathrm{\_}mb2$的公平比較。
  $ref\mathrm{\_}mb2$是(4)INTEGRA: Fast Multibit Flip-Flop Clustering forClock Power Saving的結果去比較，可以看到power都比較小(平均13%)，但worst negative slack有時候會比較大

TL;DR

1. 過去的解決方法通常不考慮MBFF的aspect ratio (W/H)，而64-bit MBFF就是一顆非常寬的cell，而這種cell會導致placement的optimazation變得困難。(但我們的case理論上也不用考慮?)

2. Logic clustering : 再synthesis的階段進行cluster，但結果顯示再沒有physical information的情況下進行cluster會造成更差的結果。

   

9.Power-Driven Flip-Flop Merging and Relocation

Paper

10. Abacus: Fast Legalization of Standarc Cell Circuits with Minimal Movement

Paper

Mainly focus on legalization algorithm after GP

• Tetris: Don't move the legalized cell. check cell 1 2 3, the displacement is small, but the cell 4 5 6 7 will have large displacement.

• Abacus: Move legalized cell to better optimize. The overall displacement is smaller to the Tetris legalize algorithm.

Overall flow

Abacus same as Tetris, first sort the cell by height and trial to place the cell on the best rows 1 by 1 with dynamic programming in PlaceRow() function.

Taskflow Simple Usage & Install

By Claire

$ git clone https://github.com/taskflow/taskflow.git

Simply include header :

#include <taskflow/taskflow.hpp>

版本要c++17

Force Directed Placement

• Phase1: relative position(overlap)
• Phase2: slot assignment

拉力只能在該partition中，不能拉超過partition? 不然displacement會太大 我越想越覺得Force directed好像沒啥用== wire-length driven placement有啥可以轉譯成cluster? Force-directed 用於timing優化 TNS的部分?

[Paper] https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1084652

[Github1] https://github.com/kabazoka/Wirelength-Driven-Detailed-Macro-Placement-with-Force-Directed-Method/tree/main

[Github2] https://github.com/madhav427/Force-Directed-Placement-and-Maze-Routing-Tool/tree/master

Other cluster algorithm

K-means

Hierarchical用KNN分群，在該群中bank/debank?

feature吃x,y coordinate? 用cost function決定是否bank?

pros:displacement小

cons:易受初始狀態及outlier影響、cluster數量要預先設定

SVM

Halfspace

可用Linear Programming解

hmetis manual & binary

Github

Draw Die

• 每個pin腳都有接到Net(?)

• Need input : (Not need to follow the order)

  1. Die size
  2. Bin size
  3. Site position
  4. I/O pin
  5. FF cells & its pin location
  6. Gate cells & its pin location
  7. Inst name, xy location, its cell's name
  8. Netlist
  ​​​​### example for drawDie input format
  ​​​​#die size
  ​​​​DieSize 0.0 0.0 50.0 30.0
  ​​​​#bin size
  ​​​​BinWidth 10.0
  ​​​​BinHeight 10.0
  ​​​​#site position
  ​​​​PlacementRows 0.0 10.0 2.0 10.0 10
  ​​​​#I/O pin
  ​​​​NumInput 3
  ​Input INPUT0 0 5
  ​Input INPUT1 0 25
  ​Input CK0 0 15
  ​NumOutput 3
  ​Output OUTPUT0 50 5
  ​Output OUTPUT1 50 15
  ​Output OUTPUT2 50 25
  ​​​​#FF cells
  ​​​​FlipFlop 2 FF2 8.0 5.0 5
  ​Pin D0 0.0 9.0
  ​Pin D1 0.0 6.0
  ​Pin Q0 8.0 9.0
  ​Pin Q1 8.0 6.0
  ​Pin CLK 0.0 2.0
  ​​​​#Gate cells
  ​​​​Gate G1 5.0 10.0 2
  ​​​​Pin IN 0.0 8.0
  ​​​​Pin OUT 5.0 2.0
  ​​​​#Inst
  ​​​​Inst C5 G1 22.0 10.0
  ​​​​#Netlist
  ​​​​Net N3 2    # net name, net pin number
  ​Pin C1/Q    # FF/Gate name, its pin name
  ​Pin OUTPUT0 # I/O pin
  

Share some result with us! With the graph or some simple testcase for drawing!

留言區

TODO

1. Partition into 8 regions

2. Different cluster merge優化方法

3. 單一cluster內banking/debanking

4. Taskflow usage

5. 最近jemalloc好夯，去研究遺下這是啥鬼 (Done smth @ compile time)

6. 研究若不是在直角坐標，若是在極座標，漣漪演算法的可行性?

7. MTFF Library technology mapping?

   

8. Legalization Algorithm help? Min Sum of the displacement??

9. check for boost geometry

10. cpp linter ClangFormat

    How to use

    Please also help me confirm whether this .clang-format work for the linter.

    .clang-format:

    ​​​​BasedOnStyle: Chromium
    ​​​​Language: Cpp
    ​​​​MaxEmptyLinesToKeep: 3
    ​​​​IndentCaseLabels: false
    ​​​​AllowShortIfStatementsOnASingleLine: false
    ​​​​AllowShortCaseLabelsOnASingleLine: false
    ​​​​AllowShortLoopsOnASingleLine: false
    ​​​​DerivePointerAlignment: false
    ​​​​PointerAlignment: Right
    ​​​​SpaceAfterCStyleCast: true
    ​​​​TabWidth: 4
    ​​​​UseTab: Never
    ​​​​IndentWidth: 4
    ​​​​BreakBeforeBraces: Linux
    ​​​​AccessModifierOffset: -4
    

11. static analysis cppcheck

    ​​​​$ wget https://github.com/danmar/cppcheck/archive/2.13.0.tar.gz
    ​​​​$ tar xvf 2.13.0.tar.gz
    ​​​​$ cd cppcheck-2.13.0/
    ​​​​$ make
    ​​​​
    ​​​​# execute cppcheck
    ​​​​# <checkFile> : path for file or directory
    ​​​​$ ./cppcheck <checkFilePath> --enable=all --inconclusive --suppress=missingIncludeSystem
    

• –enable=all : 檢查所有項目(error, warning, …)
  
• –inconclusive : cppcheck分析不確定時也會顯示錯誤訊息
• –suppress=missingIncludeSystem : 不加會有找不到某些include檔的訊息
• –output-file= reportFilePath : 把report存到file內
• example :
  
  

report :

(can you give me some example that can be caught by cppecheck, and show the result)

14. ci to run the testcase & verifier after commit CI

    reference ci workflow: ncku linux kernal lab

    need scripts to automate these:

    • Integrate with clang-format
    • Integrate with cpp-check
    • Check for mem-leak with valgrind
    • Check for the new line at the end of the file: reference

15. Simple git usage

• Download

# replace with your own info & type in cmd (first use only)
$ git config --global user.name "Coherent17"
$ git config --global user.email [e-mail]

• fork the repo (can use this repo to practice: https://github.com/coherent17/test_repo)
• git clone from your forked repo
• write code, commit & push
• pull request and wait for merge
• pull after admin merge
• reference video

禁止直接commit到mater branch

14. Topological sort based legalization from秀儒?

15. Meeting per 2 weeks?

16. check post placement vs logic synthesis兩個階段對於MBFF cluster的作法有何不同之處?

17. How to deal with the pre-place MBFF to cluster with other 1-bit FF?

18. Data structure rtree: ref

    
    

19. read thisRDF

20. for not deterministic const function, will good for optimization?

21. For next week, what should we do?

22. 影像分割演算法與clustering的連結??

• DBSCAN

• Mean Shift

• Spectral Clustering

• Agglomerative Clustering

• Affinity Propagation

  電子親和力 -> FF親和力

• OPTICS

• BIRCH

23. Violation of the rule??

• Have some negative slack?
• Violate some density rule(overlap penality)

24. Some suggestion

• There methodology currently is more based on heuristic and rule-based solution.

• First, optimize on the power and the area, for the timing critical net, they will further perform some timing optimize at that net.

• Not using the gradient or other analytical method to solve the question => some issue happens at advanced node process.(gradient method failed…)

• 讀題目

• 各選一個algorithm然後做到clustering完之後，再共同經過Placement engine來決定位置?

• Placement engine大致上使用fan-in fan-out pin的x,y average。

• Alpha test:

前面有一個Manager，而後會去call 3 task，(might be multi-core or not)，而後這三個task都各別輸出flip flop cluster的結果，再共同經過placement engine。

這樣從cluster與placement間切開是可以的嗎?

placement engine:我們先取fanin fanout pin的所有x,y平均(中位數)來找與feasible region重疊的區域。如果找不到，將平均出來的結果放鬆?BFS找附近不會有density violation的結果。如果還是找不到，就拆開放回原處吧…

• Die size with IO port sample
  

兩種Placement constraint

• Density constraint
• Placement row on site

需要研究一下sub-gradient ascent

為啥class FF跟class Gate不要繼承class Cell? 因為預期instance的數量會遠比cell library中的cell數量多，如果用繼承的會有很多一樣的資訊，且compiler會需要一直查表，所以用指標指向cell library的位置。若是merge到更大的multi-bit FF則僅需要更改指標指的位址，不需要更新一大堆資訊。

some boost usage with static linking

$ wget https://boostorg.jfrog.io/artifactory/main/release/1.84.0/source/boost_1_84_0.tar.gz
$ tar xvf boost_1_84_0.tar.gz
$ ./bootstrap.sh --prefix=/usr/local/
$ ./b2

$ g++ -static -I./boost_1_84_0 main.cpp -o main ./boost_1_84_0/stage/lib/libboost_system.a ./boost_1_84_0/stage/lib/libboost_filesystem.a

by using static linking， the binary can be distributed without boost installing!!

• Banking.h
• Cell.h
• Cell_Library.h
• Checker.h
• Cluster.h
• Coor.h
• DetailPlacement.h
• Die.h
• Dumper.h
• FF.h
• Gate.h
• Instance.h
• Legalizer.h
• Manager.h
• MeanShift.h
• Net.h
• Node.h
• OptimalLocation.h
• ParamMgr.h
• Parser.h
• Pin.h
• PostBankingOptimizer.h
• Preprocess.h
• PrettyTable.h
• Random.h
• Row.h
• Subrow.h
• Timer.h
• Util.h
• XTour.h