Shrike-LiteでAtCoder問題を解く(22)：ABC468B② - 配列実装を試す

Last updated at 2026-07-30Posted at 2026-07-29

はじめに

前回は、ABC468B「Corridor Watch」を、配列を保持しないストリーム処理で実装しました。

Shrike-LiteでAtCoder問題を解く(21)：ABC468B - Corridor Watch

ガードマンの監視範囲を左から順に処理し、まだ数えていない区間だけを加算することで、100マス分の状態を回路内へ保持せずに答えを求めています。

ただし、この問題を素直に考えると、

100マス分の監視状態を用意する
ガードマンを見つけたら、その周囲を監視済みにする
最後に未監視のマスを数える

という配列を使うことを最初に思いつくでしょう。

今回はあえて、この素朴な配列更新方式をFPGAへ実装して、その結果を見ることにします。

今回の方針

今回の実装では、各マスの状態を1bitで保持します。

1：未監視
0：監視済み

START後に100要素をすべて1へ初期化します。

文字列Sを左から受信し、Gを受信した位置をiとすると、次の範囲へ0を書き込みます。

max(0, i-D) ～ min(M-1, i+D)

すべての文字を受信し、範囲更新が完了した後、アドレス0～M-1を順番に確認します。

値が1の要素数が答えです。

通信仕様

SPI通信は、これまで使用してきたSPIテンプレートV3を使います。

SPIクロック：4MHz
CPOL：0
CPHA：0
データ幅：8bit
ビット順：MSB first

入力順序は前回と同じです。

RESET
NOP
START
M
D
S[0] ～ S[M-1]
NOPによる回答ポーリング

文字列Sは、次の値へ置き換えて送信します。

'.' = 0x00
'G' = 0x01

回答形式も前回と同じです。

bit 7   ：VALID
bit 6:0 ：ANSWER

SPI通信速度と処理速度を考える

実装を依頼する前に、SPI通信速度とFPGA側の処理速度を確認しておきます。

Gを受信した場合、最大では100要素の更新が必要です。

今回は1クロックにつき1要素ずつ更新するため、50MHz動作では最大100クロック、時間にすると2µsかかります。

100クロック ÷ 50MHz = 2µs

一方、SPIは4MHz、8bit通信です。

1byteの転送時間も2µsです。

8bit ÷ 4MHz = 2µs

つまり最大負荷では、

1byteを受信する時間：約2µs
受信したGを処理する時間：約2µs

となり、ほぼ同じです。

実際の回路では状態遷移などもあるため、現在の更新が終わる前に次のデータを受信する可能性も考えておいた方がよさそうです。

そこで今回は、更新処理中もSPI受信を継続し、次の更新要求を1件だけ保留できる構成にします。

AIに実装を依頼する

今回も、仕様書と参照実装を用意し、AIへ実装を依頼しました。

主な依頼内容は次のとおりです。

100要素の監視状態を回路内のFFへ保持する
START後に配列を逐次初期化する
Gを受信したら監視範囲を1要素ずつ更新する
更新中もSPI受信を継続し、次の更新要求を1件だけ保留する
最後の更新完了後に全要素を集計する

とりあえずは、配列をFFとして保持するように依頼しました。

これまでの回答回路作成で普通に使ってきた方法ですね。

生成されたソースコードは以下にあります。

第22回ソースコード(FF実装)

コードの内容を確認してから、ForgeFPGA Workshopでの回路合成とBitstream生成に進みましょう。

100bitのFF配列コードを確認する

生成されたコードでは、監視状態を100bitのレジスタとして保持しています。

reg [99:0] watched;

watched[0]からwatched[99]までが廊下の各マスに対応し、

1：未監視
0：監視済み

として使います。

START後は、1クロックにつき1要素ずつ1を書き込み、100要素を初期化します。

Gを受信すると、現在位置iから、

max(0, i-D) ～ min(M-1, i+D)

の範囲を求め、対象要素へ1クロックずつ0を書き込みます。

watched[update_address] <= 1'b0;

前節で考えたように、実行中の更新とは別に、次の更新範囲を1件だけ保持します。

reg       pending_valid;
reg [6:0] pending_start;
reg [6:0] pending_end;

現在の更新が終わると、保留していた範囲へ切り替えます。

最後の文字を受信した後も、更新中または保留中の処理が残っている間は集計を開始しません。

すべての更新が終わったら、watched[0]からwatched[M-1]までを順番に確認し、1のまま残っている要素を数えます。

最後の加算結果を確実に回答へ反映するため、集計終了後にはPREPARE_REPLYを1クロック挟んでいます。

つまり今回のFF版は、

100bitの状態保持
＋ 範囲更新
＋ 1件保留
＋ 最終集計

という比較的素直な構成です。

では、この回路がShrike-Liteへ実際に収まるのか、ForgeFPGA Workshopで確認してみます。

ForgeFPGA Workshopで合成する

続いてForgeFPGA Workshopで合成しました。

論理合成は進みましたが、Placementで停止しました。

その時のForgeFPGA WorkshopのBitstream Logは以下の通りです。

回路が多すぎて収納できません、と言われていますね。

100bitだけでも入らないのか

100bitという数字だけを見ると、それほど大きくありません。

しかし、実際には配列本体だけでなく、次の回路も必要です。

逐次初期化器
範囲更新器
更新要求の保留バッファ
受信文字位置の管理
最終集計器
SPI受信FSM
回答生成回路
異常検出

さらに、可変アドレスで100bitの配列を読み書きするため、書き込み先を選ぶデコーダや読み出し用の選択回路も必要になります。

Shrike-Liteで使用されているForge FPGAは1120 LUTの小規模デバイスです。

100bitのFF配列は、それ単体では小さく見えても、問題処理全体と組み合わせると無視できない大きさになるようです。

Distributed RAMを使う

普通に配列をFFで実装すると回路が大きすぎて配置・配線ができない、という問題の解決策を考えます。

ここではFFに置いていた配列を、Distributed RAMに配置する方法を試してみます。

Distributed RAMとは

Distributed RAMは、FPGA内部のLUTを小容量のRAMとして利用する仕組みです。

通常、LUTは論理演算に使われますが、メモリとして利用できるようにも設計されています。

そのため、小さな配列を多数のFFで保持する場合と比べて、効率よく配置できることが期待できます。

今回の実装では、1クロックごとに1アドレスの読み書きを進められます。

一方で、専用BRAMほど大きな容量を持てるわけではありません。

Distributed RAMを増やせば、その分だけLUTやCLBをメモリとして使用するため、論理回路に使えるリソースも減ります。

ただし、今回のような100bit程度の小さな配列では、かなりメリットがありそうです。

Distributed RAMの難しいところ

Distributed RAMを使ううえで少し厄介なのが、Verilogでの記述方法です。

ForgeFPGA Workshopでは、Verilog上で「この配列をDistributed RAMとして使う」と直接指定できません。

Verilogの記述内容から、合成ツールが「この配列はDistributed RAMだ」と推論してくれた場合、Distributed RAMとして配置される仕組みになっています。

どのような記述なら確実に推論されるのかを自分で一から探るのはかなり大変そうです。

そこで今回はRenesasの公式アプリケーションノート、

AN-FG-018 How to use distributed memory as a RAM

にある実装例を参考にしてみます。

Distributed RAMとして推論させる

Renesasの公式サンプルを見ると、Distributed RAMの記述にはいくつか特徴があります。

メモリ本体をreg配列として宣言する
書き込みはクロック同期で、Write Enableが有効なときに1アドレスを更新する
読み出しもクロック同期で行う
配列全体をRESETで一括初期化しない
メモリアクセス部分を比較的単純な形にしている

これらがDistributed RAMとして推論されるための必須条件だと確認できているわけではありません。

そこで今回は、Renesasの公式例になるべく近い形での実装を試してみます。

実際にDistributed RAMとして推論されたかどうかは、合成後のFloorplanで確認します。

同期読み出しへ対応する

FF配列は1bitごとに独立したレジスタで構成されているため、指定したbitを直接読み書きできます。

しかし、Distributed RAMでの読み書きには、アドレスの指定と、クロックに合わせた制御が必要です。

そこで、Distributed RAM版では、読み出しアドレスを設定するクロックサイクルと、読み出しデータを集計するクロックサイクルを分けることにします。

最終集計は、概念的には次の流れです。

読み出しアドレスを設定
↓
読み出しデータが有効になるまで待つ
↓
値が1なら未監視数を加算
↓
次のアドレスへ進む

最後の要素を加算した結果が回答へ反映されるよう、返信準備用の状態も1クロック挟むことにします。

今回のDistributed RAM構成

論理上の構成は次のとおりです。

深さ：128
幅  ：1bit
使用アドレス：0～99

100要素ですが、アドレス幅を7bitとし、128×1bitのメモリとして記述します。

FF版の制御構造は可能な範囲で維持し、監視状態の保存先と、同期読み出しに必要なタイミングだけを変更する方針とします。

AIに変更を依頼する

方針が決まったところで、FF版をベースにDistributed RAM版への変更をAIへ依頼します。

主な依頼内容は次のとおりです。

100bitのFF配列を128×1bitのDistributed RAMへ置き換える
Renesas公式サンプルの記述方法を参考にする
START後の初期化、範囲更新、1件保留の処理はできるだけFF版を維持する
Distributed RAMの同期読み出しに合わせて、最終集計処理を変更する
合成後にDistributed RAMとして配置される構成を目指す

一方、今回は次のような変更は行わないように依頼します。

問題のアルゴリズムを変更しない
大きなFIFOや別のメモリを追加しない
SPI通信仕様を変更しない
BRAMは使用しない

つまり、できるだけFF版の処理を残したまま、監視状態の保存先だけをDistributed RAMへ置き換える方針です。

生成されたコードを確認する

生成されたmain.vのうち、今回のDistributed RAM化に直接関係する部分を確認します。

コード全文は以下で公開します。

第22回コード全文②（Distributed RAM版）

128×1bitのDistributed RAMを記述する

まず、監視状態を保持するRAM本体です。

reg [0:0] mem_ram [127:0];

always @(posedge i_wr_clk) begin
    if (i_wr_en)
        mem_ram[i_wr_addr] <= i_wr_data;
end

always @(posedge i_rd_clk) begin
    if (!i_rst_n)
        o_rd_data <= 1'b0;
    else if (i_rd_en)
        o_rd_data <= mem_ram[i_rd_addr];
end

FF版の、

reg [99:0] watched;

とは異なり、128個の1bit要素を持つRAMとして記述されています。

問題で使用するのはアドレス0～99だけです。

書き込みと読み出しは、それぞれEnableとアドレスを指定してクロック同期で行います。

また、RESETで初期化しているのは読み出しデータ用のo_rd_dataだけで、mem_ram本体を一括初期化する処理はありません。

初期化と範囲更新で書き込みポートを共有する

RAMへの書き込みは、START後の初期化と、Gを受信した後の範囲更新で共用しています。

assign ram_write_enable =
    init_active || (!init_active && update_active);

assign ram_write_address =
    init_active ? init_address : update_address;

assign ram_write_data =
    init_active ? 1'b1 : 1'b0;

初期化中は1を書き込み、すべてのマスを未監視状態へ戻します。

範囲更新中は0を書き込み、対象となるマスを監視済みにします。

どちらの場合も、指定したアドレスへ1クロックずつ書き込む構成です。

同期読み出しで最終集計する

すべての更新が終わると、アドレス0～M-1を順番に読み出して未監視のマスを数えます。

COUNT_WATCHED: begin
    // 未発行アドレスを同期読み出しポートへ1クロック1件で提示する。
    if (!count_last_issued) begin
        count_data_valid <= 1'b1;
        if (count_address + 7'd1 >= m_reg) begin
            count_last_issued <= 1'b1;
        end else begin
            count_address <= count_address + 7'd1;
        end
    end

    // 1クロック前に提示したアドレスのデータだけを集計する。
    if (count_data_valid) begin
        if (ram_read_data[0])
            answer_count <= answer_count + 7'd1;

        if (count_last_issued) begin
            count_data_valid <= 1'b0;
            state            <= PREPARE_REPLY;
        end
    end
end

count_addressで読み出しアドレスを提示し、そのデータを次のクロックでanswer_countへ加算しています。

FF版のように配列のbitを直接参照するのではなく、前節で考えた同期読み出しに合わせて、アドレスの提示と集計を分けた形です。

最後のデータを集計した後はPREPARE_REPLYへ進み、最終加算結果を回答へ反映してから返信します。

これで、今回確認したかったDistributed RAMへの置き換え部分は把握できました。

続いてForgeFPGA Workshopで合成し、本当にDistributed RAMとして配置されるか確認します。

合成結果

Distributed RAM版は、ForgeFPGA Workshopで合成・配置に成功しました。

早速、Floorplanで確認をしてみます。

左側の2区画のCLBにメモリらしき配置が見えますね。1区画を拡大してみます。

RAM-64 dual-portの表示が見えます。1区画当たり64bit、2区画で128bitのDistributed RAMが配置されたようです。

Bitstream Logも確認してみます。

Resource usages:
 Type=L: Capacity=140 Utilized=53 NumInst=45. [ChainLen=1]=37 [ChainLen=2]=8
 Type=M: Capacity=40 Utilized=2 NumInst=2. [ChainLen=1]=2
 Type=IOB: Capacity=184 Utilized=6 NumInst=6.

先ほどはFPGAに入りきらなかった Type=L(Logic)の使用数は大きく減り、代わりにType=M(Memory)が2個確保されていることが読み取れます。

これで、配列がDistributed RAMとして配置されたことも確認できました。

実際のリソースレポートは以下の通りです。

かなり余裕のある配置になっているようですね。

Timing Analysis

50MHz、20ns制約に対する結果は次のとおりです。

WNS                  +6.293ns
TNS                   0ns
Achievable Period    13.706ns
Achievable Frequency 72.961MHz
Logic stage           6

十分な余裕で50MHz制約を満たしています。

実機試験

生成したbitstreamをShrike-Liteへ書き込み、MicroPythonから4MHz SPIで試験しました。

公式サンプル3件と追加8件の合計11件を実行し、すべてPASSしました。

SUMMARY PASS=11 FAIL=0 RESULT=PASS

最大負荷ケース、

M=100
D=99
S="G"を100文字

の処理時間は約6.6msでした。

FF配列版とDistributed RAM版を比較する

今回の結果をまとめると、次のようになります。

項目	FF配列版	Distributed RAM版
アルゴリズム	素朴な配列方式	素朴な配列方式
論理配列	100×1bit	128×1bit
主な保存先	FF	Distributed RAM
Placement	失敗	成功
Type=L	164で容量超過	53
Type=M	0	2
4k BRAM	0	0
実機試験	実施不可	11件PASS