做FPGA的兄弟應(yīng)該都有體會(huì)處理一組位寬很大的狀態(tài)寄存器、請求向量或者中斷標(biāo)志位時(shí)最先想干的往往就是兩件事找出最低位那個(gè)1在哪找出最高位那個(gè)1在哪。這個(gè)操作在Verilog里看著簡單真自己動(dòng)手寫很多人第一次都寫成了“半吊子”版本——幾個(gè)bit仿真沒問題換成64位、128位就開始出怪結(jié)果。這篇就按我在項(xiàng)目里沉淀下來的RTL寫法展開聊一聊覆蓋兩種核心目標(biāo)找第一個(gè)1低位優(yōu)先和找最后一個(gè)1高位優(yōu)先包括參數(shù)化寫法、測試方案以及實(shí)際工程里踩過的幾個(gè)真坑。文里的代碼不依賴特殊庫直接用Verilog-2001的可綜合子集稍微懂一點(diǎn)RTL的都能直接拿回去改。無論你做的是總線仲裁、中斷控制器還是硬件調(diào)度器里的空閑隊(duì)列查找這套邏輯基本都能用得上。1. 需求拆解與兩種“1”的語義1.1 第一個(gè)1到底是誰先統(tǒng)一口徑?！暗谝粋€(gè)1”在中文語境里其實(shí)有歧義有人習(xí)慣從左往右數(shù)高位優(yōu)先有人習(xí)慣從右往左數(shù)低位優(yōu)先。在這篇里我把“第一個(gè)1”定義為從最低位LSB往最高位MSB方向看到的第一個(gè)“1”也就是索引值最小的那個(gè)置位位“最后一個(gè)1”定義為從低位往高位方向看到的最后一個(gè)“1”等價(jià)于索引值最大的那個(gè)置位位也就是最高位方向上的第一個(gè)1。舉個(gè)例子假設(shè)輸入是 8’b0010_1100那么第一個(gè)1的位置是 2bit2最后一個(gè)1的位置是 5bit5這個(gè)定義在仲裁器里非常直觀請求向量中最低優(yōu)先級通常對應(yīng)最低位越靠后優(yōu)先級越高或者反過來。無論你用哪種約定代碼里先把語義定清楚后面才不會(huì)亂。1.2 為什么不能靠一條語句解決很多朋友寫完找第一個(gè)1的代碼之后下意識會(huì)覺得“這有什么難的一個(gè)循環(huán)的事”。確實(shí)如果只是仿真for循環(huán)加break邏輯簡單直接跑起來性能也夠。但如果目標(biāo)是在FPGA里綜合出真正的硬件事情就沒那么簡單了。Verilog的for循環(huán)在綜合時(shí)會(huì)被展開成組合邏輯鏈而不是當(dāng)成CPU指令執(zhí)行。也就是說你寫的“循環(huán)里判斷是否找到、找到就退出”這種break風(fēng)格綜合器本質(zhì)上會(huì)把它變成長長的if-else嵌套天然形成一條優(yōu)先級鏈。這條優(yōu)先級鏈的延遲隨著位寬增加而線性變長32位還能接受128位、512位時(shí)timing就會(huì)吃緊。更重要的是很多新手寫的循環(huán)里有break仿真結(jié)果看起來對綜合工具卻不一定給你預(yù)期邏輯甚至可能把輸出變成latch風(fēng)格這個(gè)我在后面踩坑部分專門說。1.3 全零邊界與無效標(biāo)志另一個(gè)容易忽略的邊界是輸入向量全為0。此時(shí)“第一個(gè)1”和“最后一個(gè)1”都不存在函數(shù)輸出該是什么如果按默認(rèn)返回0會(huì)和“bit0置位”的情況混淆調(diào)用方根本分不清。因此規(guī)范的做法是輸出一個(gè)有效標(biāo)志位哪怕占用一個(gè)信號也比事后猜結(jié)果強(qiáng)得多。我在項(xiàng)目里的約定是輸入全零時(shí)輸出索引為0同時(shí)拉低valid信號有任意一個(gè)1時(shí)valid拉高索引值才有效。這個(gè)約定配合外圍做仲裁或者中斷解析時(shí)判斷邏輯會(huì)清爽很多不需要先做一個(gè)OR歸約再判斷結(jié)果。雖然多了一個(gè)信號位但換來的是在系統(tǒng)聯(lián)調(diào)階段少跟隊(duì)友吵很多架值。2. 三種常見實(shí)現(xiàn)思路對比2.1 for循環(huán)配break綜合成優(yōu)先級鏈最常規(guī)的寫法遍歷每一位找到第一個(gè)為1的位記錄索引然后退出。module find_first_one #( parameter W 8 )( input [W-1:0] data, output logic [$clog2(W)-1:0] idx, output logic valid ); always_comb begin idx 0; valid 1b0; for (int i W-1; i 0; i--) begin if (!valid data[i]) begin idx i[$clog2(W)-1:0]; valid 1b1; end end end endmodule注意我這里的寫法是從高位往下掃所以得到的是最高位的1對應(yīng)“最后一個(gè)1”。把循環(huán)方向反過來也就是從低位往上掃則得到第一個(gè)1always_comb begin idx 0; valid 1b0; for (int i 0; i W; i) begin if (!valid data[i]) begin idx i[$clog2(W)-1:0]; valid 1b1; end end end這個(gè)寫法直觀仿真也沒有歧義綜合后得到的優(yōu)先級鏈符合“從低位到高位逐個(gè)比較”的語義。缺點(diǎn)就是位寬大時(shí)路徑會(huì)很長時(shí)序優(yōu)化空間有限但對絕大多數(shù)使用場景已經(jīng)足夠了。2.2 低位獨(dú)熱提取公式n (!n 1)如果只需要最低位的1有個(gè)經(jīng)典的位運(yùn)算公式single_bit data (~data 1)。這個(gè)公式背后的原理是補(bǔ)碼加法的性質(zhì)~data 1等于-data而一個(gè)數(shù)和自己的相反數(shù)做按位與結(jié)果恰好是低位的那個(gè)1獨(dú)熱碼。例如data 8b0010_1100~data 8b1101_0011~data 1 8b1101_0100data (~data 1) 8b0000_0100得到的獨(dú)熱碼是bit2然后要用一個(gè)“獨(dú)熱碼轉(zhuǎn)二進(jìn)制索引”的模塊把4轉(zhuǎn)換成數(shù)字2。這個(gè)公式不需要循環(huán)鏈加法器的進(jìn)位鏈通常在綜合時(shí)比for循環(huán)展開的if-else鏈更可控而且用到了加法器的成熟結(jié)構(gòu)在FPGA上的面積和延遲往往更好。2.3 倒序技巧求最后一個(gè)1求最高位的1最麻煩的一版是我見過有人直接寫一個(gè)512行的casez。完全沒必要。最高位問題可以轉(zhuǎn)成最低位問題來處理先把輸入向量按位倒序鏡像再用找第一個(gè)1的模塊最后把索引反算回去。wire [W-1:0] reversed; genvar g; generate for (g 0; g W; g g 1) begin assign reversed[g] data[W-1-g]; end endgenerate如果reversed中第一個(gè)1的位置是pos_rev那么原向量中最后一個(gè)1的位置就是W-1-pos_rev。這個(gè)辦法的好處是復(fù)用已有的成熟模塊邏輯清晰測試也簡單。壞處是倒序操作在硬件上占用的只是一組交叉連線不消耗資源實(shí)際上是白賺的。2.4 三種方案怎么選把三種方案放一起對比一下方案實(shí)現(xiàn)難度時(shí)序表現(xiàn)面積適用場景for循環(huán)優(yōu)先級標(biāo)志低位寬大時(shí)路徑長省通用首選、中小位寬獨(dú)熱提取公式中需要加法器鏈整體可控較省只要最低位1、對時(shí)序敏感倒序復(fù)用模塊低與for循環(huán)方案一致省需要同時(shí)支持兩個(gè)方向這些方案不是互斥關(guān)系。實(shí)際項(xiàng)目里我最常用的是第一和第三種組合找第一個(gè)1用for循環(huán)找最后一個(gè)1用倒序加for循環(huán)邏輯統(tǒng)一一個(gè)模塊吃遍兩路需求。獨(dú)熱提取公式更多用在仲裁器里不需要索引、只需要獨(dú)熱碼做mask的場景。3. RTL代碼實(shí)現(xiàn)參數(shù)化版本3.1 頂層模塊接口定義我習(xí)慣把這兩個(gè)功能封裝成一個(gè)公共函數(shù)風(fēng)格的模塊參數(shù)化位寬方便在多個(gè)子模塊里例化。接口設(shè)計(jì)如下data輸入位向量寬度由參數(shù)指定first_idx第一個(gè)1最低位側(cè)的索引寬度為log2(W)first_valid第一個(gè)1是否存在的標(biāo)志last_idx最后一個(gè)1最高位側(cè)的索引last_valid最后一個(gè)1是否存在端口命名盡量直白別人拿到你的模塊不用讀詳細(xì)注釋也能猜出七八分意思。這里唯一要說明的是兩個(gè)valid其實(shí)值一樣因?yàn)橹灰蛄糠橇銉蓚€(gè)方向都一定能找到1。冗余輸出純粹是為了讓調(diào)用方在不需要另一個(gè)方向時(shí)不用做邏輯冗余判斷。3.2 找第一個(gè)1的組合邏輯實(shí)現(xiàn)module pos_finder #( parameter W 8 )( input [W-1:0] data, output logic [$clog2(W)-1:0] first_idx, output logic first_valid, output logic [$clog2(W)-1:0] last_idx, output logic last_valid ); logic [W-1:0] rev_data; // 倒序映射 genvar g; generate for (g 0; g W; g g 1) begin : rev_gen assign rev_data[g] data[W-1-g]; end endgenerate // 第一個(gè)1從LSB向MSB掃描 always_comb begin first_idx 0; first_valid 1b0; for (int i 0; i W; i) begin if (!first_valid data[i]) begin first_idx i[$clog2(W)-1:0]; first_valid 1b1; end end end // 最后一個(gè)1從倒序向量里找第一個(gè)1再映射回原索引 logic [$clog2(W)-1:0] rev_first_idx; logic rev_first_valid; always_comb begin rev_first_idx 0; rev_first_valid 1b0; for (int i 0; i W; i) begin if (!rev_first_valid rev_data[i]) begin rev_first_idx i[$clog2(W)-1:0]; rev_first_valid 1b1; end end end assign last_valid rev_first_valid; assign last_idx (W-$clog2(W))(W) - 1 - rev_first_idx; endmodule注意最后一個(gè)賦值里我用了帶寬度轉(zhuǎn)換的寫法有些舊工具可能不支持穩(wěn)妥一點(diǎn)可以直接定義中間變量然后做位寬對齊logic [$clog2(W)-1:0] w_const; assign w_const W[$clog2(W)-1:0] - 1; assign last_idx w_const - rev_first_idx;3.3 實(shí)現(xiàn)細(xì)節(jié)里最容易翻車的幾個(gè)點(diǎn)初始化賦值一定要做。always_comb塊里如果不先給idx和valid一個(gè)默認(rèn)值綜合工具很容易推斷出latch因?yàn)椤澳承┓种滦盘柌桓隆睍?huì)被理解成保持原值。仿真階段看不出問題上板之后就變成隨機(jī)性極強(qiáng)的怪毛病。我見過不止一個(gè)工程師在代碼評審時(shí)被這種問題攔住。索引寬度的計(jì)算$clog2(W)算出的剛好是表達(dá)W-1所需的最少位數(shù)。但注意$clog2是SystemVerilog系統(tǒng)函數(shù)如果你的環(huán)境只支持Verilog-2001需要自己寫一個(gè)clog2函數(shù)。這個(gè)函數(shù)寫成parameter表達(dá)式放在包里面或者寫成一個(gè)function放在公共頭文件里都行。全零處理無論第一還是最后一個(gè)1全零輸入時(shí)兩個(gè)valid信號都是0兩個(gè)idx輸出都是0。這個(gè)約定在模塊內(nèi)部不額外占用資源只是組合邏輯的默認(rèn)路徑所以不必?fù)?dān)心面積開銷。3.4 位寬參數(shù)化的綜合思路參數(shù)化帶來的直接好處是同樣的邏輯從8位擴(kuò)到128位時(shí)不用重寫任何代碼。但綜合路徑延遲會(huì)怎么變心里要有數(shù)。以for循環(huán)展開后的優(yōu)先級鏈為例時(shí)序路徑是data進(jìn)入一系列比較器每級比較器給出“我這一位更高/更低”的判定逐級傳遞到最終索引。每多一位基本上就是多一級MUX邏輯。FPGA上每個(gè)LUT處理幾位比較所以路徑變長幾乎是線性的。對于128位以上單拍組合完成壓力很大這時(shí)候就要考慮流水線拆分了。拆分思路簡單粗暴把輸入切成兩半或者四段每段分別算索引和valid再用一個(gè)多路選擇器根據(jù)段valid選出最終結(jié)果。比如128位切成兩個(gè)64位第一拍算兩半第二拍用MUX合成。這樣延遲翻倍到兩拍但組合路徑減半時(shí)序就能收斂。代碼實(shí)現(xiàn)上把上面的模塊例化兩次再在外面包一層選擇邏輯即可不需要改動(dòng)核心邏輯。4. 測試與驗(yàn)證4.1 先用定向用例跑通語義拿到模塊第一件事別急著上隨機(jī)先寫幾個(gè)手工用例把語義釘死。我的習(xí)慣是按這幾種典型情況測單bit置位0x0001、0x8000、某個(gè)中間位多bit置位比如0x0050同時(shí)檢查兩個(gè)方向輸出全零輸入檢查valid為0全1輸入檢查第一個(gè)1是0最后一個(gè)1是W-1initial begin pos_finder #(.W(16)) u_finder (.data(16h0001), .first_idx(f_idx), .first_valid(f_valid), .last_idx(l_idx), .last_valid(l_valid)); // 檢查f_idx0, l_idx0, f_valid1 // 換成16h8000檢查f_idx15, l_idx15 // 換成16h0050檢查f_idx4, l_idx6 // 換成16h0000檢查f_valid0, l_valid0 end跑完這些用例語義層面基本就穩(wěn)了。4.2 隨機(jī)驗(yàn)證與參考模型定向用例只能防低級錯(cuò)誤真正的邏輯正確性要靠隨機(jī)驗(yàn)證。找位置這類純組合邏輯的模塊隨機(jī)驗(yàn)證非常簡單暴力隨機(jī)生成輸入用行為級參考模型算期望值和RTL輸出對比。參考模型可以直接在testbench里寫一個(gè)笨辦法函數(shù)function automatic [15:0] ref_find(input [127:0] v); ref_find 0; for (int i 0; i 128; i) begin if (v[i]) begin ref_find i; break; end end endfunction注意function用的也是軟件思維仿真器里可以隨便用break不會(huì)綜合只是用來做期望值。隨機(jī)測試跑個(gè)幾千組覆蓋率就上來了。有一點(diǎn)提醒隨機(jī)種子要可配置最好通過仿真器命令行參數(shù)傳進(jìn)去這樣回歸失敗時(shí)可以穩(wěn)定復(fù)現(xiàn)。別圖省事直接寫死一個(gè)固定種子后面迭代代碼時(shí)想復(fù)現(xiàn)bug會(huì)非常折磨。4.3 別忘了時(shí)序檢查功能對了不代表能上板。大規(guī)模位寬的模塊必須在綜合后看時(shí)序報(bào)告里first_idx和last_idx相關(guān)路徑的slack。如果為負(fù)不要慌先看是不是組合邏輯鏈太長試著用前面說的分段流水方案優(yōu)化。還有一個(gè)容易忽略的點(diǎn)如果這個(gè)模塊的輸入來自異步域沒有同步處理的話即使組合邏輯本身沒問題采樣到的數(shù)據(jù)也可能是亞穩(wěn)態(tài)導(dǎo)致的隨機(jī)值。這個(gè)和位置查找邏輯本身無關(guān)但在真實(shí)系統(tǒng)里經(jīng)常被誤判成模塊bug排查時(shí)先確認(rèn)時(shí)鐘域再懷疑邏輯。5. 實(shí)際應(yīng)用場景與工程取舍5.1 仲裁器與優(yōu)先級選擇找第一個(gè)1最經(jīng)典的應(yīng)用就是仲裁器。一組請求向量req[W-1:0]低位代表高優(yōu)先級或低優(yōu)先級取決于你的定義。仲裁器需要拿到當(dāng)前被選中的那個(gè)請求的索引然后去查對應(yīng)的資源或隊(duì)列。這里用第一段講的for循環(huán)版本最直接索引輸出接給后續(xù)的狀態(tài)機(jī)做資源分配。我以前做過一個(gè)跨時(shí)鐘域的請求仲裁模塊用的就是64位的位置查找挑中之后還要把該位清除方便下一輪仲裁。清除操作直接用req req ~(1 idx)其中1 idx就是根據(jù)索引生成的mask這個(gè)組合邏輯順手就能搭出來。5.2 中斷控制器與狀態(tài)寄存器解析SoC中斷控制器里經(jīng)常需要找“當(dāng)前掛起的中斷里編號最高/最低的那個(gè)”以便跳轉(zhuǎn)到對應(yīng)的中斷服務(wù)程序。一組中斷掛起寄存器幾十個(gè)bit用硬件找出最高優(yōu)先級中斷號和跑軟件遍歷中斷表相比響應(yīng)速度快一個(gè)量級。中斷號解析還有一層麻煩中斷源可能帶使能mask必須用pending enable的結(jié)果作為輸入。這個(gè)步驟放在位置查找模塊之前形成一條“先mask再查找”的流水代碼里用一個(gè)wire把mask后的向量接進(jìn)去就行非常簡單。5.3 調(diào)度器空閑隊(duì)列查找在硬件調(diào)度器里經(jīng)常要維護(hù)一組“哪些隊(duì)列非空”的標(biāo)志位然后調(diào)度器需要選一個(gè)非空隊(duì)列來服務(wù)。這個(gè)場景下其實(shí)找的是空隊(duì)列也就是要找0而不是找1。處理辦法也簡單輸入取反即可busy_mask置位表示忙空閑隊(duì)列的位置就是~busy_mask里的第一個(gè)1。這種取反操作在組合邏輯上多了一級反相器完全可以忽略不計(jì)。問題在于取反后如果全是1也就是全部隊(duì)列都忙valid才會(huì)變成0和前面找1的約定天然一致使用上非常順暢。5.4 與優(yōu)先級編碼器和桶形移位器的關(guān)系位置查找電路和優(yōu)先級編碼器、桶形移位器本質(zhì)上是同一族電路。優(yōu)先級編碼器輸出就是第一個(gè)1的索引桶形移位器可以選擇性地把輸入右移/左移若干位。理解這層關(guān)系對調(diào)時(shí)序有益如果你已經(jīng)有一個(gè)桶形移位器IP完全可以用“找到掩碼、用移位器做mask對齊”的方式換一種實(shí)現(xiàn)路徑有時(shí)比for循環(huán)鏈時(shí)序更優(yōu)。比如要找到最低位1并把該位及其后的所有低位置0也就是保留從該位往高位的部分可以用掩碼mask data (~data 1)然后結(jié)果天然就是獨(dú)熱碼不需要額外的移位操作。這個(gè)方案在仲裁器恢復(fù)剩余請求時(shí)很常用。6. 常見問題與排查技巧實(shí)錄6.1 “為什么我的break在綜合后沒用”仿真時(shí)break讓循環(huán)提前退出看起來又省時(shí)間又直觀但綜合工具在展開for循環(huán)時(shí)對break的處理并不統(tǒng)一。有的工具能正確推斷優(yōu)先級有的工具直接給出語義正確但面積爆炸的邏輯最煩的是有的工具推導(dǎo)出的電路和你預(yù)期完全不一樣仿真和綜合對不上排查時(shí)極為痛苦。我在代碼里從不用break而是引入一個(gè)found標(biāo)志通過if (!found ...)來控制優(yōu)先級。這樣工具穩(wěn)、代碼可讀性也高還順帶規(guī)避了“不同工具綜合結(jié)果不一致”的坑。6.2 索引輸出出現(xiàn)X態(tài)用integer i做循環(huán)變量直接賦給窄位寬輸出如果沒做位寬截?cái)喾抡鏁r(shí)很容易出現(xiàn)X態(tài)傳播。比如idx i;在一個(gè)8位向量里i的值范圍是0到7但如果后續(xù)有分支讓i變成未定義或者向量本身有X索引可能就變成X了。解決方法是循環(huán)變量只用于比較賦值時(shí)用i[$clog2(W)-1:0]做顯式截?cái)嗤瑫r(shí)檢查輸入向量本身是否干凈。X態(tài)問題十有八九是上游數(shù)據(jù)帶X不是這個(gè)模塊的鍋定位時(shí)先把輸入波形抓出來看一下。6.3 獨(dú)熱提取公式對大位寬的隱患data (~data 1)看著精妙但要注意~data 1在綜合時(shí)是一整條加法進(jìn)位鏈。位寬到64、128時(shí)這條鏈路延遲可能比for循環(huán)版更長不見得是“更優(yōu)方案”。如果你在時(shí)序報(bào)告里看到這條路徑很緊試著換成for循環(huán)優(yōu)先級鏈的實(shí)現(xiàn)用LUT邏輯替代進(jìn)位鏈有時(shí)反而更好收斂。另外這個(gè)公式只對最低位1有效別想當(dāng)然把data取反后用同樣公式找最高位1邏輯上差很遠(yuǎn)。6.4 常見問題速查表問題現(xiàn)象可能原因解 決 方 法輸出索引始終為0always塊內(nèi)未初始化默認(rèn)值邏輯塊開頭先賦值idx0、valid0valid為高但索引是X索引寬度不夠或截?cái)噱e(cuò)誤用i[$clog2(W)-1:0]顯式截?cái)嗑C合后面積爆炸循環(huán)中使用了break換成found標(biāo)志風(fēng)格避免工具誤判時(shí)序slack為負(fù)位寬過大、優(yōu)先級鏈過長分段流水或換獨(dú)熱公式實(shí)現(xiàn)輸入全零時(shí)輸出0卻無法區(qū)分缺少valid標(biāo)志增加有效標(biāo)志位全零時(shí)拉低仿真結(jié)果正確、上板結(jié)果錯(cuò)誤輸入來自異步域未同步先解決跨時(shí)鐘域問題再回查邏輯128位時(shí)綜合報(bào)$clog2不可用工具不支持SV系統(tǒng)函數(shù)手寫clog2函數(shù)或參數(shù)化計(jì)算6.5 一組實(shí)用的公共函數(shù)封裝建議如果項(xiàng)目里多個(gè)模塊都要用位置查找建議把這套邏輯封裝成公共的function或者獨(dú)立的模塊放進(jìn)來不要每個(gè)子模塊里復(fù)制粘貼一份。我實(shí)際維護(hù)的項(xiàng)目里一開始有人直接把這種查找邏輯散落在仲裁、中斷、調(diào)度三個(gè)模塊里后面位寬需求變了要改動(dòng)3處、跑3輪回歸浪費(fèi)了不少時(shí)間。封裝成獨(dú)立模塊的好處是位寬參數(shù)統(tǒng)一改驗(yàn)證用例集中維護(hù)代碼風(fēng)格可控。壞處是多例化帶來的instance管理成本但這個(gè)成本和一致性收益一比完全值得。我個(gè)人在實(shí)際操作里的習(xí)慣是把常用的位操作集合——找第一個(gè)1、找最后一個(gè)1、獨(dú)熱轉(zhuǎn)索引、mask生成——放在同一個(gè)公共包里每換一個(gè)項(xiàng)目直接拿來用改參數(shù)就行。這套東西寫一次受益很多年建議你也這么干。