# **[LPHP Lab M0]** IC Design Contest 2021

## **題目要求簡述:**
- 本年題目要求完成完成一地理圍籬(geofence)系統，系統使用6顆接收器在平面上建構出虛擬圍籬，地理圍籬系統依據接收器的座標及待測物體的座標來分析待測物體是在圍籬內或圍籬外。
- 依照題目的要求來說，主要分為兩個步驟去完成此系統功能。第一步為排序6顆接收器為順時針或逆時針順序。(為了在第二步判斷待測物是否位於虛擬圍欄內)第二步為使用待測物的座標到各接收器的向量外積個接收器之間的向量得到待測物是否位於圍欄內的資訊。

### ***目標:***
- 在本年的評分標準中，A等級的排序方式依照繳交時間的早晚排序，因此在設計上會主要著重在一定程度節省面積範圍內去構思簡單易懂的設計來加速Coding的時間。
- 另外，因為本年的clk period控制在30ns且粗估critical path應該會是10 bit 的乘法器用來作外積的運算因此我們認為clk的部分只要在計算外積的state只做乘法這件事情，應該是很好去符合題目的clk period要求的。

## **演算法簡述:**
- 本題中我們採用題目提到的演算法，要排序接收器順序，可將其中一接收器作為原點，和其它5接收器形成5向量(圖五)；利用計算向量外積判斷兩向量方向關係，進行排序讓前後向量固定維持順時針或逆時針關係，然後可得圍籬順序。
- 向量外積計算(圖六)：若有兩向量，向量A=(Ax，Ay) = (x1-x0，y1-y0)，向量B=(Bx，By) = (x2-x0，y2-y0)， A到B外積 = Ax*By – Bx*Ay， 若外積結果<0，表示B在A順時針方向(A到B順時針夾角<180o)，反之為逆時針方向。

- 基於以上的排序法，我們會建立一個Hash的矩陣儲存對應Index的接收器為順時針排序時的第幾個接收器。排序的方式首先會先將Hash矩陣初始為0,1,2,3,4,5並依序排序各接收器(先固定0,1, 從第2個接收器開始)透過計算新加入的向量與已排序的向量的外積去判斷新加入的向量在已排序的向量的順時針或逆時針側。若新加入的向量在已排序的左側則會進入SORT_INSERT將該新向量插入並改動其他的編號。若在右側則會回到FIND_INDEX0去尋找下一個已排序向量直到fix = loop + 1代表新向量在已排序的所有向量的最右側則會直接加入。

- 至於判斷待測物是否在圍欄內則採用與題目一樣的方式，在排序好圍欄後依次做外積並記錄正負。等全部外積完再判斷是否為全正或全負即可得知。(注: 當任一外積的答案為0時會直接跳到SPECIAL_OUTPUT強制讓is_inside = 0)

## **State Graph:**


- 在此系統的State Graph中展示了系統如何去排序接收器以及計算待測物是否於圍欄內的流程。由於系統較複雜，各State轉換的判斷是比較雜亂且有兩個ctr以不同的條件在累計與重置因此以下分別對每個State的功能做解釋。Ctr變化的部分則到code直接參考會比較容易。
- READ_MARK: 儲存標的物座標
- READ_FENCE: 會Loop6次儲存所有接收器的座標，並建立一個Hash的矩陣儲存目前對應Column的接收器被排在第幾個位置(順時針)
- FIND_INDEX0: 透過for迴圈(code的部分因應for迴圈有做改動但園藝與for迴圈的功能一樣)的方式去找出對應ctr_loop的hash[i]的i儲存成index方便後面做外積。
- SUBTRACT0_X(後面三個同理): 使用ctr_fix以及上一個state得到的index以及第0欄位中的座標得到A與B向量。
- CROSS0: 計算$A_xB_y$並存到Register中。
- CROSS1: 計算$A_yB_x$並提出上一State的$A_xB_y$做$A_xB_y - A_yB_x$。
- SORT_INSERT: 插入當前(ctr_fix)置Hash中並將原有的Hash重新調整數值。
- SORT_RIGHT: 將ctr_fix插入在Hash當前已排序的最右側。
- CTR_RESET: 當還沒找到當前接收器的位置時要回到FIND_INDEX0之前reset ctr_loop的State。
- FIND_INDEX1: 找出目前要外積的接收器與他的下一個接受器Index。
- MARK_SUB0_X/MARK_CROSS: 做外積，同理。
- OUTPUT: 判斷輸出結果是否為全正或全負-->is_inside = ?
- SPECIAL_OUTPUT: 若外積結果= 0進入此State直接輸出is_inside = 0。

## **電路特殊設計:**
- 由於我們在使用for迴圈的時候不需要Interger的32bit這麼多(只做0~5)因此我們將ctr_loop這個ctr重新利用將for迴圈拆成以下的形式達到同樣的效果但將counter從32bit節省成3bit的ctr且還是重複利用的因此面積上直接少了一個32bit counter。

## **結果討論:**
- 這次的題目相較之前的幾年較為困難，主要是因為要控制多個ctr並完成排序演算法。因此在State Graph的地方便要很小心地使用ctr以及做Reset的動作來讓Register的使用最少且能正確的控制各個Hash。

- 另外，在這次題目中發現了幾個相當重要的經驗:
1.
如果使用這樣先用Case去Append各個Operand再用一個單純做乘法的乘法器去計算兩個Operand相比直接在Case中去分5個不同Multiply_reg = AAA * BBB這樣的寫法會直接少掉6000的面積。(推估是寫成後者的寫法會變成5個乘法器而上面的寫法則會合成一個乘法器)


2.
我們在將各個Register減少至可容忍的最小bit數時發現當我們減少40個bit數時面積約間少了2000左右因此未來在估算面積時可以用1bit ~= 50去做估算會在之後處理面積問題時有更好的視野。