《生命游戲》FPGA實例評測：?有限狀態(tài)機(jī)用哪種編碼更好？（附：源碼下載）
2021-01-08 12:51:34 EETOP用于FSM的三種最受歡迎的編碼是二進(jìn)制(Binary)、格雷（Gray）和獨熱碼（one-hot）。
二進(jìn)制編碼
二進(jìn)制編碼是在將值順序分配給狀態(tài)時可以直觀使用的簡單方法。這樣，您將使用盡可能少的位來編碼狀態(tài)。
二進(jìn)制編碼的示例
格雷碼
在一組數(shù)的編碼中，若任意兩個相鄰的代碼只有一位二進(jìn)制數(shù)不同，則稱這種編碼為格雷碼（Gray Code），另外由于最大數(shù)與最小數(shù)之間也僅一位數(shù)不同，即“首尾相連”，因此又稱循環(huán)碼或反射碼。此外如果狀態(tài)序列得到最佳遵循，則此編碼還可將動態(tài)功耗降至最低。
格雷碼輪
獨熱編碼
獨熱編碼任何狀態(tài)只有1bit為1，其余皆為0，編碼密度低，由于使用的位數(shù)和無效狀態(tài)的過多，這似乎不太有效。但是，獨熱編碼非常適合簡化觸發(fā)器的激勵邏輯，因為位就是狀態(tài)，因此無需解碼狀態(tài)。
獨熱編碼的示例
這是一個棘手的問題，主要是因為每種編碼都有它的優(yōu)點和缺點，所以它歸根結(jié)底是一個優(yōu)化問題，取決于很多因素。
如果一個非常簡單的系統(tǒng)在不同的編碼中產(chǎn)生非常相似的結(jié)果，那么原始編碼就是最好的選擇。
如果FSM在一條路徑上循環(huán)地通過其狀態(tài)（像計數(shù)器一樣），那么格雷碼是一個非常好的選擇。
如果FSM有一組任意的狀態(tài)轉(zhuǎn)換，或者預(yù)計在高頻下運(yùn)行，也許獨熱碼是最好的方式。
現(xiàn)在，所有這些說法都只是有根據(jù)的猜測，找到最佳狀態(tài)分配是一個復(fù)雜的問題。正因為如此，我建議是讓邏輯綜合替你決定。盡管如此，下面我決定在三種不同的開發(fā)工具和三種不同的狀態(tài)機(jī)對這三種編碼的結(jié)果進(jìn)行比較。
接下來的三個實驗說明了確定哪種編碼適合給定FPGA的過程。
對于此實驗，我想大量實例化一個狀態(tài)機(jī)，以放大使用二進(jìn)制，格雷和獨熱編碼時所得硬件的差異。
我最終選擇的系統(tǒng)是康威的《生命的游戲》，這是一種細(xì)胞自動機(jī)，它模擬了活細(xì)胞在其環(huán)境中的行為，模擬了這些細(xì)胞的出生、繁殖和死亡過程，命游戲是一個二維網(wǎng)格游戲，這個網(wǎng)格中每個方格居住著一個活著或死了的細(xì)胞。一個細(xì)胞在下一個時刻的生死取決于相鄰8個方格中活著或死了的細(xì)胞的數(shù)量。如果相鄰方格活著的細(xì)胞數(shù)量過多，這個細(xì)胞會因為資源匱乏而在下一個時刻死去；相反，如果周圍活細(xì)胞過少，這個細(xì)胞會因為孤單而死去。
在康威的生命游戲中，規(guī)定了如下生存定律。
(1)當(dāng)前細(xì)胞為死亡狀態(tài)時，當(dāng)周圍有3個存活細(xì)胞時，則迭代后該細(xì)胞變成存活狀態(tài)(模擬繁殖)；若原先為生，則保持不變。
(2)當(dāng)前細(xì)胞為存活狀態(tài)時，當(dāng)周圍的鄰居細(xì)胞低于兩個(不包含兩個)存活時，該細(xì)胞變成死亡狀態(tài)(模擬生命數(shù)量稀少)。
(3)當(dāng)前細(xì)胞為存活狀態(tài)時，當(dāng)周圍有兩個或3個存活細(xì)胞時，該細(xì)胞保持原樣。
(4)當(dāng)前細(xì)胞為存活狀態(tài)時，當(dāng)周圍有3個以上的存活細(xì)胞時，該細(xì)胞變成死亡狀態(tài)(模擬生命數(shù)量過多)。
這些規(guī)則創(chuàng)建了許多有趣的行為和模式，這些行為和模式已在計算機(jī)科學(xué)中廣泛研究。
這就是生命游戲在運(yùn)行所謂的Gosper滑翔槍時的圖例。
《生命游戲》的一種變體，稱為Bill Gosper的滑翔機(jī)槍。
回到我們的測試系統(tǒng)，每個單元被設(shè)計為一個具有8個狀態(tài)的狀態(tài)機(jī)。不可否認(rèn)，生命游戲中的細(xì)胞邏輯可以在一個周期內(nèi)解決，但我決定制作一個8狀態(tài)機(jī)，以便在使用不同編碼時產(chǎn)生顯著差異。這些狀態(tài)被用來計算一個細(xì)胞的存活鄰居。
下面一段Verilog代碼顯示了這些細(xì)胞的單元模塊結(jié)構(gòu)，包括狀態(tài)的原始二進(jìn)制編碼。
`define STATE_0 3'b000
`define STATE_1 3'b001
`define STATE_2 3'b010
`define STATE_3 3'b011
`define STATE_4 3'b100
`define STATE_5 3'b101
`define STATE_6 3'b110
`define STATE_7 3'b111
module LifeCell(
inputclk,
inputnrst,
inputseed,
input[7:0] neighbors,
outputreg alive);
reg [2:0] state;
always @ (posedge clk)
if(nrst == 0)
state<= `STATE_0;
else
case(state)
`STATE_0:begin
//...
state<= `STATE_1;
end
`STATE_1:begin
//...
state<= `STATE_2;
end
//...
`STATE_7:begin
//...
state<= `STATE_1;
end
endcase
endmodule
如果您想更深入地了解代碼，可以在GitHub上查看該項目。
https://github.com/kuashio/conways-game-of-life
FPGA編碼實現(xiàn)
該系統(tǒng)被綜合并實現(xiàn)為一個23x23細(xì)胞的世界，共有27個變體：使用了三種不同的FSM，都使用了上述三種編碼，并且都在三種不同的目標(biāo)FPGA上實現(xiàn)。
FSM＃1：原始模型
該機(jī)器有一個初始狀態(tài)，運(yùn)行一次，然后循環(huán)運(yùn)行其余7個狀態(tài)。這幾乎是一個完整的序列，所以一開始我覺得格雷編碼很有希望。
FSM＃2：序列
這臺機(jī)器表現(xiàn)為3位計數(shù)器，所以我也期待格雷編碼能碾壓競爭對手。
FSM＃3：任意路徑糾結(jié)
該機(jī)器具有與FSM＃1相同的關(guān)鍵路徑，但是當(dāng)已知存在的鄰居數(shù)量超過3個時，它將會通過任意路徑。
對于這種任意狀態(tài)轉(zhuǎn)換行為，我希望獨熱編碼是最佳選擇。
目標(biāo)架構(gòu)
該系統(tǒng)針對三款目標(biāo)FPGA，利用其供應(yīng)商的開發(fā)工具實現(xiàn)。
結(jié)果比較
比較兩個或多個系統(tǒng)的性能很困難，主要是因為判決取決于我們使用的指標(biāo)以及我們認(rèn)為哪些方面比其他方面更重要。在本實驗中，我收集了以下數(shù)據(jù)以為每個實現(xiàn)產(chǎn)生一個分?jǐn)?shù)：
比較兩個或更多系統(tǒng)的性能是很困難的，主要是因為判決取決于我們使用的指標(biāo)，以及我們認(rèn)為哪些方面比其他方面更重要。在這個實驗中，我收集了以下數(shù)據(jù)，以便為每個實現(xiàn)打一個分?jǐn)?shù)：
對于每一個實施方案，這四個方面在三個編碼之間進(jìn)行比較，所以在編碼之間，我得到一個最好的，一個最差的，一個中間的結(jié)果。最好的得正分，最差的得負(fù)分，中間的得0分。
將每個模型的所有分?jǐn)?shù)相加后，我得到以下結(jié)果：
所有27種實現(xiàn)的結(jié)果表。在每一行中，最好的編碼用綠色顯示，最差的用紅色顯示，如果沒有平局，中間的用黃色顯示。
這似乎表明要遠(yuǎn)離獨熱編碼，只有兩種情況下它會獲勝，其中一種是平局。此外，雖然我最初認(rèn)為獨熱編碼是FSM模型#3的最佳編碼，但結(jié)果卻是最差的編碼，沒有開發(fā)工具推薦它。不過在某些情況下，獨熱編碼會勝過其他的，主要是在頻率和功率指標(biāo)上。
總體而言，格雷編碼似乎是此特定系統(tǒng)的最佳選擇。
從該表中提取贏家，我們得到以下信息：
盡管這次比較似乎偏向于格雷編碼而不是二進(jìn)制和獨熱，但結(jié)果在很大程度上取決于我們使用的指標(biāo)，而這些指標(biāo)是反映了對我們重要的東西。例如，在這次比較中，我們認(rèn)為頻率和功率比使用率(設(shè)計中的邏輯元件和寄存器數(shù)量)更重要。如果我重視使用率而不是頻率，或重視頻率而不是功率，肯定會得出不同的排名。
這個比較并不是為了成為使用這些編碼所獲得的性能的權(quán)威性工作。相反，它顯示了我在使用的架構(gòu)中的個人偏好所產(chǎn)生的排名。
提醒一下，如果你想看看代碼，看看27個實現(xiàn)，或者看看我對《生命游戲》的模擬操作，請查看GitHub上的項目：
https://github.com/kuashio/conways-game-of-life
EETOP 官方微信
創(chuàng)芯大講堂 在線教育
半導(dǎo)體創(chuàng)芯網(wǎng) 快訊
相關(guān)文章
