Clever Geek Handbook

ハッシュテーブルを作成するときにミスを犯した方法と、これからどのような結論を導き出しましたか

理論的な理解を明確にするために、あなた自身の過ちから、あなた自身の苦い経験から学ぶよりも良い方法はありません。 （フリードリッヒエンゲルス）


みなさんこんにちは！







同僚が数週間前にリンクインで私に手紙を書いて、ハッシュテーブルが私のgithub プロジェクトで正しく機能しないと言った。







テストと修正が私に送られ、システムが「ハング」する状況が実際に作成されました。 問題を調査すると、検証中にいくつかの間違いを犯したことに気付きました。 Habrでは、RTLコードの検証のトピックはあまり詳しく描かれていないので、記事を書くことにしました。







記事から次のことを学びます。









猫へようこそ！







プロジェクトについて簡単に



目標と背景



プロジェクトの開始前に設定した目標：









内部デバイス



最大のパフォーマンスを得たいので、パイプラインを整理します。









入力（ ht_cmd



）： 







 typedef enum logic [1:0] { OP_SEARCH, OP_INSERT, OP_DELETE } ht_opcode_t; typedef struct packed { logic [KEY_WIDTH-1:0] key; logic [VALUE_WIDTH-1:0] value; ht_opcode_t opcode; } ht_command_t;


出力（ ht_res



）： 







 typedef enum int unsigned { SEARCH_FOUND, SEARCH_NOT_SUCCESS_NO_ENTRY, INSERT_SUCCESS, INSERT_SUCCESS_SAME_KEY, INSERT_NOT_SUCCESS_TABLE_IS_FULL, DELETE_SUCCESS, DELETE_NOT_SUCCESS_NO_ENTRY } ht_rescode_t; typedef struct packed { ht_command_t cmd; ht_rescode_t rescode; logic [BUCKET_WIDTH-1:0] bucket; // valid only for opcode = OP_SEARCH logic [VALUE_WIDTH-1:0] found_value; } ht_result_t;


注 ：

実際、 found_value



ではrescode



とfound_value



のみに関心がありfound_value



が、少し先を見ています。他のフィールドがないと、検証するのが難しくなります。 とにかく、それらが鉄で使用されていない場合、シンセサイザーはそれらを切り取り、リソースを消費しません。







何がどこにあるか：









head_table



内のhead_table



： 







 typedef struct packed { logic [HEAD_PTR_WIDTH-1:0] ptr; logic ptr_val; } head_ram_data_t;


data_table



内の単語： 







 typedef struct packed { logic [KEY_WIDTH-1:0] key; logic [VALUE_WIDTH-1:0] value; logic [HEAD_PTR_WIDTH-1:0] next_ptr; logic next_ptr_val; } ram_data_t;


操作アルゴリズム：









興味深いニュアンス：









次のようになります（ クリックして拡大 ）：







エラーを回避/デバッグを簡素化するために私がしたこと



ハッシュテーブルの作成を開始する前に、プロジェクトが簡単ではないことを理解したため、開発を加速しデバッグを簡素化するいくつかのことを事前に予測しました。







SystemVerilogとコーディングスタイル



SystemVerilogと企業スタイルのコーディングがHDL言語として使用されました。







これにより、構造を簡単に記述し（上記を参照）、独自のデータ型を作成して、たとえばFSMを記述することができます。 







 enum int unsigned { IDLE_S, NO_VALID_HEAD_PTR_S, READ_HEAD_S, GO_ON_CHAIN_S, KEY_MATCH_S, ON_TAIL_WITHOUT_MATCH_S } state, next_state;


ストリーミングインターフェイス（Avalon-ST）



コンベアを開発するときは、いつ停止するかをよく理解する必要があります。

多くのことを思いつくことができますが、既製の開発されたインターフェースを使用することが最善です。







職場では、アルテラのFPGAを使用して作成しているため、アルテラのFPGAが提供/促進するインターフェースに精通しています。 このプロジェクトでは、 Avalonファミリーを使用しました。







コマンドは単なるデータストリーム（1ワードAvalon-Streaming (Avalon-ST)



コマンド）であるため、 Avalon-Streaming (Avalon-ST)



標準Avalon-Streaming (Avalon-ST)



（ data



、 ready



、 valid



信号）を使用しました。







これは、 readyLatency = 0



（ 標準から取得 ）のときのAvalon-ST



上のトランザクションの様子です。









この図では、スレーブが制御するレディ信号がトランザクションとデータ転送をシャットダウンしていることがわかります。







ダミーハッシュ



このハッシュテーブルをどのように作成するのか疑問に思ったとき、最も困難なことは検証することであることに気付きました。 明らかに、最も興味深いニュアンスは、すでにデータがあるチェーンに追加しようとしたり、長いチェーンから削除したりするときに表示されます。







これは、システムへの影響が適用されたときに、事前定義されたバスケット番号を使用してキー（ key



）を簡単に生成できる必要があることを意味します。







実際のハッシュ関数では、これには問題があるため、 HASH_TYPE



パラメーターの値は"dummy hash"



等しくHASH_TYPE



ます。

このタイプのハッシュが選択されている場合、バスケット番号は単にキーの上位BUCKET_WIDTH



ビットです。







したがって、 key = 0x92123456



で、 BUCKET_WIDTH



が8の場合、 bucket_num = 0x92



です。

これにより、特定の境界ケースの生成に必要なアクションを簡単に作成できます。







シミュレーションロギング



開発者は、 SignalTapまたはChipScopeを使用して、ハードウェア（読み取り、ボード）でRTLモジュールを直接デバッグする場合があります 。 このアプローチは、常に最速かつ最も生産的ではありません-プロジェクト全体（10分から数時間）（時には複数回）、手元のボード、デバッガー、入力アクションの生成などを再構築する必要があります。







開発をスピードアップするために、 ModelSim 、VCS、Icarus Verilogなどの特別なシミュレーターが使用されます。タイムチャート（タイムフレーム）を構築することにより、デバッグ中にすべての（または選択された）信号/ 変数の値を追跡できます。 これらのチャートをデバッグするには、膨大な時間がかかる場合があります。







解決策 ：

発生したすべてのアクションをログに記録し、目を通してすぐに見ることができます。







このために、 data_table_insert



、 data_table_delete



、 data_table_search



に、ログに出力する関数を追加しました。 







 function void print( string s ); $display("%08t: %m: %s", $time, s); endfunction


display



形式はprintf



似ています（ %d



、 %f



などを使用できます）。









FSM遷移のロギング： 







 function void print_state_transition( ); string msg; if( next_state != state ) begin $sformat( msg, "%s -> %s", state, next_state ); print( msg ); end endfunction


新しいタスクの受信を印刷します。 







 function string pdata2str( input ht_pdata_t pdata ); string s; $sformat( s, "opcode = %s key = 0x%x value = 0x%x head_ptr = 0x%x head_ptr_val = 0x%x", pdata.cmd.opcode, pdata.cmd.key, pdata.cmd.value, pdata.head_ptr, pdata.head_ptr_val ); return s; endfunction function void print_new_task( ht_pdata_t pdata ); print( pdata2str( pdata ) ); endfunction


などなど...







シミュレーションには、ModelSimを使用します。 画面に表示されるログ（およびデフォルトでは、 transcript



ファイルにアクセスします）には、次の行が表示されます。 







 1465: top_tb.dut.d_tbl.sea_eng.g_s_eng[3].search.print: opcode = OP_SEARCH key = 0x04000000 value = 0x0000 head_ptr = 0x000 head_ptr_val = 0x0 1465: top_tb.dut.d_tbl.sea_eng.g_s_eng[3].search.print: IDLE_S -> NO_VALID_HEAD_PTR_S 1475: top_tb.dut.d_tbl.sea_eng.g_s_eng[3].search.print: RES: key = 0x04000000 value = 0x0000 rescode = SEARCH_NOT_SUCCESS_NO_ENTRY 1475: top_tb.dut.d_tbl.sea_eng.g_s_eng[3].search.print: NO_VALID_HEAD_PTR_S -> IDLE_S 1475: ht_tb.print: IN_MONITOR: key = 0x04000000 value = 0x0000 rescode = SEARCH_NOT_SUCCESS_NO_ENTRY 1485: top_tb.dut.d_tbl.del_eng.print: opcode = OP_DELETE key = 0x04111111 value = 0x0000 head_ptr = 0x000 head_ptr_val = 0x0 1485: top_tb.dut.d_tbl.del_eng.print: IDLE_S -> NO_VALID_HEAD_PTR_S 1495: top_tb.dut.d_tbl.del_eng.print: RES: key = 0x04111111 value = 0x0000 rescode = DELETE_NOT_SUCCESS_NO_ENTRY 1495: top_tb.dut.d_tbl.del_eng.print: NO_VALID_HEAD_PTR_S -> IDLE_S 1495: ht_tb.print: IN_MONITOR: key = 0x04111111 value = 0x0000 rescode = DELETE_NOT_SUCCESS_NO_ENTRY 1505: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x04000000 value = 0xb95f head_ptr = 0x000 head_ptr_val = 0x0 1505: top_tb.dut.d_tbl.ins_eng.print: IDLE_S -> NO_HEAD_PTR_WR_HEAD_PTR_S 1515: top_tb.dut.h_tbl.print: addr = 0x04 wr_data.ptr = 0x003 wr_data.ptr_val = 0x1 1515: top_tb.dut.d_tbl.ins_eng.print: NO_HEAD_PTR_WR_HEAD_PTR_S -> NO_HEAD_PTR_WR_DATA_S 1525: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x003 key = 0x04000000 value = 0xb95f next_ptr = 0x000, next_ptr_val = 0x0 1525: top_tb.dut.d_tbl.ins_eng.print: RES: key = 0x04000000 value = 0xb95f rescode = INSERT_SUCCESS 1525: top_tb.dut.d_tbl.ins_eng.print: NO_HEAD_PTR_WR_DATA_S -> IDLE_S


このようなテキストログは、grepや検索の実行が簡単です（たとえば、vim'eで）。







ログは時間を大幅に節約しました。簡単な例を送信するとき、どの順序で書かれるべきかを知っていて、ログを見るだけでした。 エラーが発生した場合、タイミング図ではなくコードを分析しました。







チャレンジとして、タイムアウトなしで1週間以内にRTLコードをデバッグすることをお勧めします（快適ゾーンを離れる）。







検証



System Verilog for Verificationなどの優れた文献に目を向けると、優れた正しいテストベンチとして次の図があります。









この記事では、Chris Spearからパンを取り上げるつもりはないので、これらすべてのコンポーネントの意味については詳しく説明しません。







私のテストベンチのスキーム：









top_tb



トップモジュール。







DUT（デバイス/テスト対象設計）



テスト対象は、 hash_table_top



モジュールのインスタンスです。







ht_driver





このメールボックスにコマンドを配置するには、階層アクセスが使用されます。 







 task send_to_dut_c( input ht_command_t c ); // using hierarchial access to put command in mailbox env.drv.gen2drv.put( c ); endtask


テスト



パフォーマンスをテストするために、3つのテスト/入力アクションが作成されました。







作業を簡素化するマクロ： 







 `define CMD( _OP, _KEY, _VALUE ) cmds.push_back( '{ opcode : _OP, key : _KEY, value : _VALUE } ); `define CMD_SEARCH( _KEY ) `CMD( OP_SEARCH, _KEY, 0 ) `define CMD_INSERT( _KEY, _VALUE ) `CMD( OP_INSERT, _KEY, _VALUE ) `define CMD_INSERT_RAND( _KEY ) `CMD_INSERT( _KEY, $urandom() ) `define CMD_DELETE( _KEY ) `CMD( OP_DELETE, _KEY, 0 )


テスト例： 







 task test_01( ); ht_command_t cmds[$]; $display("%m:"); `CMD_INSERT( 32'h01_00_00_00, 16'h1234 ) `CMD_INSERT( 32'h01_00_10_00, 16'h1235 ) `CMD_INSERT_RAND( 32'h01_00_00_00 ) `CMD_INSERT_RAND( 32'h01_00_00_01 ) `CMD_DELETE ( 32'h01_00_00_00 ) `CMD_INSERT_RAND( 32'h01_00_00_02 ) `CMD_SEARCH( 32'h01_00_00_00 ) `CMD_SEARCH( 32'h01_00_00_01 ) `CMD_SEARCH( 32'h01_00_00_01 ) `CMD_SEARCH( 32'h01_00_00_03 ) foreach( cmds[i] ) begin send_to_dut_c( cmds[i] ); end endtask


ht_monitor





ht_scoreboard



DUTの正しい動作を確認します。







次のものが含まれます。









操作アルゴリズム：









カバレッジ



そのため、さまざまな入力の影響を送信したり、DUTの反応の正確さを分析したりできるシステム（必要に応じて、フレームワーク）が既にあります。 バグがないことを確認するには、「可能なすべての」オプションをカバーする必要があります。







SystemVerilogは、カバレッジを評価するために、covergroupおよびcoverpointオブジェクトを導入しました 。 彼らの助けを借りて、サンプリングしたいポイントと、収集する統計を説明できます。 







 covergroup cg(); option.per_instance = 1; CMDOP: coverpoint result_locked.cmd.opcode; CMDRES: coverpoint result_locked.rescode; BUCKOCUP: coverpoint bucket_occup[ result_locked.bucket ] { bins zero = { 0 }; bins one = { 1 }; bins two = { 2 }; bins three = { 3 }; bins four = { 4 }; bins other = { [5:$] }; } CMDOP_BUCKOCUP: cross CMDOP, BUCKOCUP; CMDRES_BUCKOCUP: cross CMDRES, BUCKOCUP { // we should ignore SEARCH_FOUND, INSERT_SUCCESS_SAME_KEY, DELETE_SUCCESS // when in bucket was zero elements, because it's not real situation ignore_bins not_real = binsof( CMDRES ) intersect{ SEARCH_FOUND, INSERT_SUCCESS_SAME_KEY, DELETE_SUCCESS } && binsof( BUCKOCUP ) intersect{ 0 }; } endgroup


説明：









シミュレーションの終了後、ModelSimコンソールでレポートを取得できます。 







 coverage save 1.ucdb vcover report 1.ucdb -verbose -cvg


報告書： 







 COVERGROUP COVERAGE: ---------------------------------------------------------------------------------------------------- Covergroup Metric Goal/ Status At Least ---------------------------------------------------------------------------------------------------- TYPE /top_tb/dut/resm/cg 94.0% 100 Uncovered Coverpoint cg::CMDOP 100.0% 100 Covered Coverpoint cg::CMDRES 85.7% 100 Uncovered Coverpoint cg::BUCKOCUP 100.0% 100 Covered Cross cg::CMDOP_BUCKOCUP 100.0% 100 Covered Cross cg::CMDRES_BUCKOCUP 84.6% 100 Uncovered Covergroup instance \/top_tb/dut/resm/cg1 94.0% 100 Uncovered Coverpoint CMDOP 100.0% 100 Covered covered/total bins: 3 3 missing/total bins: 0 3 bin auto[OP_SEARCH] 21 1 Covered bin auto[OP_INSERT] 21 1 Covered bin auto[OP_DELETE] 18 1 Covered Coverpoint CMDRES 85.7% 100 Uncovered covered/total bins: 6 7 missing/total bins: 1 7 bin auto[SEARCH_FOUND] 12 1 Covered bin auto[SEARCH_NOT_SUCCESS_NO_ENTRY] 9 1 Covered bin auto[INSERT_SUCCESS] 14 1 Covered bin auto[INSERT_SUCCESS_SAME_KEY] 7 1 Covered bin auto[INSERT_NOT_SUCCESS_TABLE_IS_FULL] 0 1 ZERO bin auto[DELETE_SUCCESS] 11 1 Covered bin auto[DELETE_NOT_SUCCESS_NO_ENTRY] 7 1 Covered Coverpoint BUCKOCUP 100.0% 100 Covered covered/total bins: 6 6 missing/total bins: 0 6 bin zero 7 1 Covered bin one 13 1 Covered bin two 9 1 Covered bin three 12 1 Covered bin four 8 1 Covered bin other 11 1 Covered Cross CMDOP_BUCKOCUP 100.0% 100 Covered covered/total bins: 18 18 missing/total bins: 0 18 bin <auto[OP_SEARCH],zero> 1 1 Covered bin <auto[OP_INSERT],zero> 5 1 Covered bin <auto[OP_SEARCH],one> 5 1 Covered ... Cross CMDRES_BUCKOCUP 84.6% 100 Uncovered covered/total bins: 33 39 missing/total bins: 6 39 bin <auto[SEARCH_NOT_SUCCESS_NO_ENTRY],zero> 1 1 Covered bin <auto[INSERT_SUCCESS],zero> 5 1 Covered bin <auto[DELETE_NOT_SUCCESS_NO_ENTRY],zero> 1 1 Covered ...


すべての可能な交差点は自動的に受信されました-私たちは余分なことを書きませんでした。







3つのテストの後、次のことが明らかになります。









最後に





バグは何でしたか



この効果を適用すると、次のことがわかりました。 







 `CMD_INSERT_RAND( 32'h05_00_00_00 ) `CMD_INSERT_RAND( 32'h05_00_00_01 ) `CMD_DELETE ( 32'h05_00_00_01 ) `CMD_INSERT_RAND( 32'h05_00_00_02 ) `CMD_INSERT_RAND( 32'h05_00_00_03 )


これにより、キー0x05000003



挿入されると、 0x05000003



モジュールが「ハング」するという事実につながります。











（ クリックして拡大 ）







ログに次のメッセージが表示されました。 







 385: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000003 value = 0x7e7e head_ptr = 0x000 head_ptr_val = 0x1 385: top_tb.dut.d_tbl.ins_eng.print: IDLE_S -> READ_HEAD_S 415: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1 415: top_tb.dut.d_tbl.ins_eng.print: READ_HEAD_S -> GO_ON_CHAIN_S 445: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1 475: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1 505: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1 535: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1 ...


少しログを巻き戻して分析します。 興味のある行（ data_table



で読み書きされる行）のみを提供しました： 







  75: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000000 value = 0x1f62 head_ptr = 0x000 head_ptr_val = 0x0 95: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x000, next_ptr_val = 0x0 115: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000001 value = 0x3ff2 head_ptr = 0x000 head_ptr_val = 0x1 145: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x000, next_ptr_val = 0x0 155: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x001 key = 0x05000001 value = 0x3ff2 next_ptr = 0x000, next_ptr_val = 0x0 165: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1 185: top_tb.dut.d_tbl.del_eng.print: opcode = OP_DELETE key = 0x05000001 value = 0x0000 head_ptr = 0x000 head_ptr_val = 0x1 215: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1 245: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x001 key = 0x05000001 value = 0x3ff2 next_ptr = 0x000, next_ptr_val = 0x0 255: top_tb.dut.d_tbl.del_eng.print: WR: addr = 0x001 key = 0x05000001 value = 0x3ff2 next_ptr = 0x000, next_ptr_val = 0x0 265: top_tb.dut.d_tbl.del_eng.print: WR: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x000, next_ptr_val = 0x0 285: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000002 value = 0x5429 head_ptr = 0x000 head_ptr_val = 0x1 315: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1 345: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x000, next_ptr_val = 0x0 355: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x001 key = 0x05000002 value = 0x5429 next_ptr = 0x000, next_ptr_val = 0x0 365: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1 385: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000003 value = 0x7e7e head_ptr = 0x000 head_ptr_val = 0x1 415: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1 445: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1 475: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1 505: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1


255〜265 nsの奇妙なイベントが発生した瞬間に気付くかもしれません。最初に、 addr = 0x001



が1つの値を記録し、次に別の値を記録しました。







これにより、 data_table



に誤ったデータが含まれるという事実につながります。









キー0x05000002を追加すると、興味深い状況が発生します。1つのセル0x001で記録が2回発生します。









キー0x05000003を追加しようとすると、チェーンを通過するときにループが発生します。 445 nsからは、チェーンに沿って無限に実行し、同じアドレスを読み取ります。







間違いは何でしたか



明らかに、データを削除したモジュール（ data_table_delete



）によってエラーが発生します。







255 nsの時点で、 next_ptr_val



セルのnext_ptr_valフラグをゼロに設定し、265 nsの時点で0x001に書き込んですべてのゼロを書き込む必要がありました。 そのため、このモジュールのコードで想定されていましたが、これは、見てのとおり、起こりませんでした。







事実、チェーンの最後から読み取るrd_addr



とrd_data



を別々に保存するrd_addr



あったため、作業したばかりの値を使用しました。







このようなエラー（1クロックサイクルによる余分な遅延、間違った時間に上書きされたデータなど）は、RTLコードでは非常に一般的です。 彼らはあまり関心を表していないので、この記事では特に説明しません。







どのような間違いがあったか（開発中）



プロジェクト管理は「不完全」です



事実は、私が想像したようにプロジェクトを論理的な終わりに至らなかったということです。 なぜ-今は覚えていない。







たとえば、 README



では、プロジェクトはこのモジュールがどこでどのように使用され、テストされたかを示していません。







2つのフレーズを比較します。







  1. このプロジェクトは、 100Gスイッチの実稼働で使用されます。
  2. このプロジェクトは数週間にわたって楽しみのために書かれました ビール缶 トマトジュース。


週末にこのモジュールを書いて、どこにも埋め込まなかったことを明確に示していた場合、サードパーティの開発者は私のモジュールを使用せず、時間を節約できなかったでしょう（ただし、バグがあることはわかりません） 、この記事は読みません）。







問題がコード内のどこにあるかをprev_rd_addr



し始めたとき、問題がprev_rd_addr



変数にあることがわかったとき、動揺しました。 値が割り当てられるブロックは次のようになります。 







 always_ff @( posedge clk_i or posedge rst_i ) if( rst_i ) prev_rd_addr <= '0; else if( rd_en_o ) //FIXME prev_rd_addr <= rd_addr;


説明のないFIXME



は悪いです。 問題を説明するための余分な5分間は、将来的に常に成果を上げます。







* 結論 ：









Coverage



, , , :









:







ht_chain_state_t



, , : 







 typedef enum int unsigned { NO_CHAIN, IN_HEAD, IN_MIDDLE, IN_TAIL, IN_TAIL_NO_MATCH } ht_chain_state_t; //    ht_result_t ... // only for verification ht_chain_state_t chain_state; } ht_result_t;


. data_table_delete



: 







 ht_chain_state_t chain_state; always_ff @( posedge clk_i or posedge rst_i ) if( rst_i ) chain_state <= NO_CHAIN; else if( state != next_state ) begin case( next_state ) NO_VALID_HEAD_PTR_S : chain_state <= NO_CHAIN; IN_TAIL_WITHOUT_MATCH_S : chain_state <= IN_TAIL_NO_MATCH; KEY_MATCH_IN_HEAD_S : chain_state <= IN_HEAD; KEY_MATCH_IN_MIDDLE_S : chain_state <= IN_MIDDLE; KEY_MATCH_IN_TAIL_S : chain_state <= IN_TAIL; // no default: just keep old value endcase end //   ,    ```ht_res_monitor``` assign result_o.chain_state = chain_state;


ht_res_monitor



: 







 //   ht_result_t result_history [HISTORY_DELAY:1]; always_ff @( posedge clk_i ) begin if( result_locked_val ) begin result_history[1] <= result_locked; for( int i = 2; i <= HISTORY_DELAY; i++ ) begin result_history[i] <= result_history[i-1]; end end end // 1   ,   (bucket)    logic [HISTORY_DELAY:1] bucket_hist_mask; always_comb begin for( int i = 1; i <= HISTORY_DELAY; i++ ) bucket_hist_mask[i] = ( result_history[i].bucket == result_locked.bucket ); end


covergroup: 







 ... CMDOP_D1: coverpoint result_history[1].cmd.opcode; CMDOP_D2: coverpoint result_history[2].cmd.opcode; CMDRES_D1: coverpoint result_history[1].rescode; CMDRES_D2: coverpoint result_history[2].rescode; CHAIN: coverpoint result_locked.chain_state; BUCK_HIST_MASK: coverpoint bucket_hist_mask; CMDOP_HISTORY_D2: cross CMDOP_D2, CMDOP_D1, CMDOP, BUCK_HIST_MASK; CMDRES_HISTORY_D2: cross CMDRES_D2, CMDRES_D1, CMDRES, BUCK_HIST_MASK { ignore_bins not_check_now = binsof( CMDRES ) intersect{ INSERT_NOT_SUCCESS_TABLE_IS_FULL } || binsof( CMDRES_D1 ) intersect{ INSERT_NOT_SUCCESS_TABLE_IS_FULL } || binsof( CMDRES_D2 ) intersect{ INSERT_NOT_SUCCESS_TABLE_IS_FULL }; } CMDOP_CHAIN: cross CMDOP, CHAIN { ignore_bins insert_in_middle = binsof( CMDOP ) intersect { OP_INSERT } && binsof( CHAIN ) intersect { IN_MIDDLE }; ignore_bins insert_in_tail_no_match = binsof( CMDOP ) intersect { OP_INSERT } && binsof( CHAIN ) intersect { IN_TAIL_NO_MATCH }; }


, bin CMDOP_HISTORY_D2



: 







 bin <auto[OP_DELETE],auto[OP_SEARCH],auto[OP_SEARCH],auto['b10]>


, :









. : 







 Coverpoint cg::CMDOP 100.0% 100 Covered Coverpoint cg::CMDRES 85.7% 100 Uncovered Coverpoint cg::CMDOP_D1 100.0% 100 Covered Coverpoint cg::CMDOP_D2 100.0% 100 Covered Coverpoint cg::CMDRES_D1 85.7% 100 Uncovered Coverpoint cg::CMDRES_D2 85.7% 100 Uncovered Coverpoint cg::CHAIN 100.0% 100 Covered Coverpoint cg::BUCK_HIST_MASK 100.0% 100 Covered Coverpoint cg::BUCKOCUP 100.0% 100 Covered Cross cg::CMDOP_BUCKOCUP 100.0% 100 Covered Cross cg::CMDRES_BUCKOCUP 84.6% 100 Uncovered Cross cg::CMDOP_HISTORY_D2 18.5% 100 Uncovered covered/total bins: 20 108 missing/total bins: 88 108 Cross cg::CMDRES_HISTORY_D2 3.1% 100 Uncovered covered/total bins: 27 864 missing/total bins: 837 864 Cross cg::CMDOP_CHAIN 84.6% 100 Uncovered


( , .. )







, HISTORY



(18.5% 3.1%). , , .







, ?

. , , , , 100% .







— . , ( 5 6 ).







:











, .

. — . , : Constrained Random Verification .







, , - , - ( ) , , .







, : 







 function bit [KEY_WIDTH-1:0] gen_rand_key( int min_bucket_num = 0, int max_bucket_num = ( 2**BUCKET_WIDTH - 1 ), int max_key_value = ( 2**( KEY_WIDTH - BUCKET_WIDTH ) - 1 ) ); bit [BUCKET_WIDTH-1:0] bucket_num; bit [KEY_WIDTH-1:0] gen_key; if( hash_table::HASH_TYPE != "dummy" ) begin $display("%m: hash_type = %s not supported here!", hash_table::HASH_TYPE ); $fatal(); end bucket_num = $urandom_range( max_bucket_num, min_bucket_num ); gen_key = $urandom_range( max_key_value, 0 ); // replace high bits by bucket_num (is needs in dummy hash) gen_key[ KEY_WIDTH - 1 : KEY_WIDTH - BUCKET_WIDTH ] = bucket_num; return gen_key; endfunction


[0;15]



[0;7]



. 







 // testing small amount of buckets with random commands task test_05( ); ht_command_t cmds[$]; $display("%m:"); for( int c = 0; c < 5000; c++ ) begin `CMD_SEARCH ( gen_rand_key( 0, 15, 7 ) ) `CMD_INSERT_RAND ( gen_rand_key( 0, 15, 7 ) ) `CMD_DELETE ( gen_rand_key( 0, 15, 7 ) ) end // ,    :) cmds.shuffle( ); foreach( cmds[i] ) begin send_to_dut_c( cmds[i] ); end endtask


: 







 Cross cg::CMDOP_HISTORY_D2 98.1% 100 Uncovered covered/total bins: 106 108 missing/total bins: 2 108 Cross cg::CMDRES_HISTORY_D2 81.1% 100 Uncovered covered/total bins: 701 864 missing/total bins: 163 864


, bin' , , : 







 // testing only one bucket with random commands task test_06( ); ht_command_t cmds[$]; $display("%m:"); for( int c = 0; c < 1000; c++ ) begin `CMD_SEARCH ( gen_rand_key( 0, 0, 7 ) ) `CMD_INSERT_RAND( gen_rand_key( 0, 0, 7 ) ) `CMD_DELETE ( gen_rand_key( 0, 0, 7 ) ) end cmds.shuffle( ); foreach( cmds[i] ) begin send_to_dut_c( cmds[i] ); end endtask


結果： 







 Cross cg::CMDOP_HISTORY_D2 100.0% 100 Covered covered/total bins: 108 108 missing/total bins: 0 108 Cross cg::CMDRES_HISTORY_D2 99.1% 100 Uncovered covered/total bins: 857 864 missing/total bins: 7 864


, ( , rescode=INSERT_NOT_SUCCESS_TABLE_IS_FULL



)







注 ：









:









""



, .







( ht_res



), "" , . . .







( ) — () .







:









, - .

( ) , /.







, :

head_table



:









data_table



:









empty_ptr_storage



:









:









tables_monitor



, head_table



, data_table



, empty_ptr



.

, , . .







: 







 ... 1195: top_tb.dut.d_tbl.del_eng.print: opcode = OP_DELETE key = 0x01000000 value = 0x0000 head_ptr = 0x001 head_ptr_val = 0x1 1195: top_tb.dut.d_tbl.del_eng.print: IDLE_S -> READ_HEAD_S 1225: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x001 key = 0x01001000 value = 0x1235 next_ptr = 0x002 next_ptr_val = 0x1 1225: top_tb.dut.d_tbl.del_eng.print: READ_HEAD_S -> GO_ON_CHAIN_S 1255: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x002 key = 0x01000001 value = 0x3ff2 next_ptr = 0x000 next_ptr_val = 0x1 1285: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x000 key = 0x01000002 value = 0x5429 next_ptr = 0x004 next_ptr_val = 0x1 1315: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x004 key = 0x01000000 value = 0x1cc0 next_ptr = 0x000 next_ptr_val = 0x0 1315: top_tb.dut.d_tbl.del_eng.print: GO_ON_CHAIN_S -> KEY_MATCH_IN_TAIL_S 1325: top_tb.dut.d_tbl.del_eng.print: WR: addr = 0x004 key = 0x01000000 value = 0x1cc0 next_ptr = 0x000 next_ptr_val = 0x0 1325: top_tb.dut.d_tbl.del_eng.print: KEY_MATCH_IN_TAIL_S -> CLEAR_RAM_AND_PTR_S 1335: top_tb.dut.d_tbl.del_eng.print: WR: addr = 0x004 key = 0x00000000 value = 0x0000 next_ptr = 0x000 next_ptr_val = 0x0 1335: top_tb.dut.d_tbl.del_eng.print: RES: key = 0x01000000 value = 0x0000 rescode = DELETE_SUCCESS chain_state = IN_TAIL 1335: top_tb.dut.d_tbl.del_eng.print: CLEAR_RAM_AND_PTR_S -> IDLE_S 1335: ht_tb.print: IN_MONITOR: key = 0x01000000 value = 0x0000 rescode = DELETE_SUCCESS chain_state = IN_TAIL 1335: top_tb.dut.d_tbl.empty_ptr_storage.print: add_empty_ptr: 0x004 ** Error: ERROR: addr = 0x004. This addr is empty, but ptr is val Time: 1340 ns Scope: top_tb.tm.check_one_addr File: ../tb/tables_monitor.sv Line: 119 ** Error: ERROR: addr = 0x004 key=0x00000000 don't match bucket_num = 0x01 Time: 1340 ns Scope: top_tb.tm.check_one_addr File: ../tb/tables_monitor.sv Line: 127


, ( )!







:









:









おわりに



, , . ( )


IP- ASIC/FPGA -.







:









, . , , .







, RTL-, .







, RTL- :)







ご清聴ありがとうございました！ .







PS：

.

, :









More articles:


All Articles