---
# System prepended metadata

title: '[LPHP Lab M0] IC Design Contest 2022'

---

# **[LPHP Lab M0]** IC Design Contest 2022
    
    
## **題目要求簡述:**
- 本年題目要求以窮舉法列出所有的派工配對組合，然後找到最低的成本以及符合最低成本的組合數量。
- 依照題目要求可以將整個系統分為兩大部分，其一是基於現在的派工組合找到下一個派工組合以達到窮舉的方式。第二個部分則是用來累加當前的派工組合成本並比較得到是否為最小的成本並記錄。


### ***目標:*** 
![image](https://hackmd.io/_uploads/rk50anU0p.png =70%x)
- 在本年的評分標準中可以看到基本上只要模擬cycle小於600,000、面積小於10,000的話，比較的只有繳交速度。因此可以從這些Benchmark中擬定我們的策略。
- 首先先計算8位數窮舉總共有幾種組合可以得到40320種組合，並且因為每一個組合最少需要8個cycle去做累加(被RAM一個Cycle只能讀一個決定)因此光是窮舉計算所有的組合cost就要322,560個cycle。
- 基於以上條件，我們透過平行運算的方式將計算新組合順序以及累加成本的功能平行進行來讓cycle數不至於超過600,000。詳細實現方式會在下面解釋。

### **結果**
- Area: 8098 $um^2$
- Timing: 10 $ns$
- Run Cycle: 387,528

## **演算法討論**    
- 本題中我們採用的演算法為題目中所提供的字典序演算法:
![image](https://hackmd.io/_uploads/SJDhy6L06.png)


    
    
    
## **State Graph:** 
![2022-3](https://hackmd.io/_uploads/HybB76LAp.jpg)
- SWITCH_POINT: 用counter i 來從Pattern[7]開始倒過來比較直到右側的數大於左側的數以得到SwitchPoint
- MIN_LARGE:  Point後從Switch Point開始走道Pattern[7]找一個大於Switch Point的最小數字並將該數與Switch Point交換
- FLIP: 將Switch Point後的數全部左右翻轉。終止條件為$j=i\ ||\ j+1=i$
- ACCUMULATE: 當在前面的State無法將上一個Pattern累加完也就是上述三個State不到8個cycle時，剩下的Accumulation就會在這裡完成。
- COMPARE:　比較Global的最小Cost與當前運算出來的Cost並記錄。
- OUTPUT: 當Pattern為76543210的時候會進入該State使系統終止並輸出。




## **電路特殊設計:**
- 平行運算
![2022-4](https://hackmd.io/_uploads/Hy8ISa80a.jpg)






## **結果討論:**
- 這一年的題目相較其他年度較為簡單，但在之前的題目中大多是使用Sequential Structure的方式在每一個Cycle只做一件事情等到東西都準備好再一次比較等等的方式去設計。但在今年透過Parallelism的方式大幅壓縮使用的cycle數得到相當好的表現。另外，在完成之後還有另外想到在SWITCH_POINT的時候或許可以不要用i去count的方式慢慢兩個兩個去比較而是直接用一個case去窮舉所有的比較例如7:6, 6:5, 5:4...使能夠在1個cycle就找到Switch Point。如此便可以省去很多cycle。同理，FLIP也可以採用同樣的方式節省cycle數。



