在這個文章中,我們將介紹怎麼在特定 T 下,最小化 A。

一般來說,在 IC 競賽中,T 值規定會是以 cycle 數計算,並不會以總時常來做限制。另外,這個 cycle 數也會改的非常寬鬆,基本上你看完題目當下能想到最簡單的方法都會在這個 cycle 數的規定以下。

當然,一個大家都會做的優化就是把 cycle 的週期條的很大,只要超過 critical path 的大小,我們就可以在合成時有比較好的面積。除此之外,在架構設計上,一個規則化的硬體會非常的省面積。

什麼是規則化硬體?也就是盡量的利用同一套硬體去做很多不同的事情。簡單的例子是,一個演算法用到 +、x、/。另一個方法雖然時間比較久,只用了 x,我們就應該選用這樣的方法。下面,我們會以一個例子來說明這個概念:

簡單例子

這邊我會先簡單介紹一個排序的例子,在 2020 IC競賽決賽實作中,我們可以看到一個更複雜的例子。

各位讀者應該都知道排序有很多種, insertion sort、merge sort、bubble sort 等等。如果說我們要在特定 T 下,最小化 A,最好的做法就是做一個 bubble sort 的硬體,他只需要一個簡單的比較器和簡單的 register 即可。

你可能會想,merge sort 的操作次數不是更少嗎?要注意的是這邊我們的 T 值是很足夠的,如果選擇 merge sort 這類操作複雜的演算法實作,我們就會設計出很多套的硬體,造成不必要的硬體面積浪費。

另外,更進一步的來看。一個簡單的 bubble sort 如下:

給定 n 個數值 A_1, A_2, ..., A_n
for i = 1 : n
  for j = i + 1 : n
    if A_i > A_j
      swap(A_i, A_j)

這已經是一個最好設計的硬體了嗎?我們要考量在算 i 和 j 的數值時,也是需要家法器的,而且 j = i + 1 這點也會造成面積浪費。

如果我們時做下面的作法呢?可以看到,我們就不需要 j 了,也使得存 j 的 register 可以省掉。雖然所用的 cycle 數增加了,但只要在符合規定的 cycle 數內,我們就應該靜可能的去把演算法進行規則化。盡力的重複操作同樣的步驟,即使重複操作很幾次也無妨

給定 n 個數值 A_1, A_2, ..., A_n
for i = 1 : n*(n-1)
  if A_i > A_(i+1)
    swap(A_i, A_(i1+))

小節

我非常喜歡競賽中出現特定 T 下,最小化 A這樣的題目。因為,當我們把軟體的演算法學熟了,常常會不自覺的就想到一些步驟比較少的作法,進會直接想去實作他。當我們遇到這樣的問題時,應該要考量硬體的代價,特別是 A 值估計對於沒有硬體設計經驗的人相對又很困難。這樣的題目很容易就可以考驗考生對於硬體的認知。