はじめに
前回は、SPIテンプレートV2を使ってABC467Aを実装しました。
今回は、AtCoder Beginner Contest 467のC問題をShrike-Liteへ実装します。
ABC467Cでは、Nが最大200000です。
問題を解くためのFPGA側の回路は比較的簡単ですが、最大ケースでは大量の入力データをRP2040からFPGAへ渡す必要があります。
今回はABC467Cの初回として、最初から通信量を減らすことは考えず、素朴な方法で実装してみます。
最初にNを送信
A_1を送信
(A_(i+1), B_i)を1組ずつ、1byteで送信
そのうえで、AtCoderの実行時間制限と同じ2秒間に、何サンプル程度まで処理できるかをMicroPython側で測定します。
これまではShrike-Liteの「小さなFPGAが載っているボード」という面を中心に見てきました。
ABC467Cの実装では、FPGAへデータを供給するRP2040側の処理にも注目してみましょう。
今回やること
今回の内容は次のとおりです。
- ABC467Cをストリーム処理できる簡単なFPGA回路を作る
-
A_(i+1)とB_iを1組ずつ、1byteで送信する - 公式サンプルと追加ケースで機能を確認する
- 2秒程度で処理できる
Nを指数探索と二分探索で求める - 実行時間のばらつきを考慮し、結果は100単位の推定値として扱う
素朴な実装で今後の改善と比較するための基準値を測定します。
また、AtCoderを題材にしているのに、FPGAの実装ばかりでアルゴリズムの話が全くない、と感じる方もいらっしゃると思いますので、ほんのちょっとだけそれらしい内容を入れてみます。
ABC467Cの問題
長さNの数列Aと、長さN-1の数列Bが与えられます。
A_iへ1を加える操作を好きな回数行い、すべてのi=1,2,...,N-1について、次の条件を満たすために必要な最小操作回数を求めます。
(A_i + A_(i+1)) mod M = B_i
C問題では、M=2に固定されています。
制約は次のとおりです。
2 <= N <= 200000
M = 2
0 <= A_i <= 1
0 <= B_i <= 1
Nと答えは、どちらも18bitで表現できます。
M=2なのでXORとして考える
操作後のA_iを、2で割った余りとしてX_iとします。
M=2では、加算の剰余とXORは同じ結果になります。
(X_i + X_(i+1)) mod 2 = B_i
X_i XOR X_(i+1) = B_i
したがって、X_iとB_iが分かれば、次の値は一意に決まります。
X_(i+1) = X_i XOR B_i
X_1として考えられる値は0または1の二つがあります。
CPUやMCUで二つの候補を別々に更新すると、その分だけ処理量が増えます。
一方、FPGAでは、今回のような小さな処理であれば二つの候補を同時に更新でき、1サンプルあたりのクロック数を増やさずに処理できます。
そのため今回の実装では、FPGAに次の2候補を同時並列に計算させます。
候補0：X_1 = 0
候補1：X_1 = 1
各候補について、現在のX_iと操作回数だけを保持します。
X_(i+1)を計算し、元のA_(i+1)と異なる場合は操作回数を1増やします。
X_(i+1) = X_i XOR B_i
X_(i+1) == A_(i+1) なら加算なし
X_(i+1) != A_(i+1) なら操作回数を1増やす
最後に、二つの候補の操作回数の小さい方を答えとします。
この方法では、AやBの配列全体をFPGAへ保存する必要はありませんので、BRAMは使用しません。
RP2040とFPGAの役割分担
今回の役割分担は次のようにします。
| 処理 | 担当 |
|---|---|
| テストケースと期待値を保持する | RP2040 |
Nを18bitに分割して送信する |
RP2040 |
A_1を送信する |
RP2040 |
A_(i+1)とB_iを1byteに詰めて送信する |
RP2040 |
X_1=0とX_1=1の2候補を同時に処理する |
FPGA |
| 各候補の操作回数を数える | FPGA |
| 小さい方の操作回数を18bitで返信する | FPGA |
| 返信値と期待値を比較する | RP2040 |
| 処理時間を測定する | RP2040 |
2秒程度で処理できるNを探索する |
RP2040 |
問題の答えそのものはFPGAが計算します。
RP2040は入力データの送信、結果確認に加え、今回はベンチマークの探索も担当します。
素朴なSPI送信仕様
MOSIはSPIテンプレートV2と同じく、上位3bitをコマンド、下位5bitをデータとして使用します。
bit 7 bit 5 bit 4 bit 0
+--------------------+----------------------------+
| COMMAND[2:0] | DATA[4:0] |
+--------------------+----------------------------+
コマンド一覧
3bitのコマンドをすべて使用します。
| コマンド | 値 | DATAの内容 |
|---|---|---|
NOP |
000 |
未使用。答えの受信に使用 |
SEND_N_17_15 |
001 |
N[17:15] |
SEND_N_14_10 |
010 |
N[14:10] |
SEND_N_9_5 |
011 |
N[9:5] |
SEND_N_4_0 |
100 |
N[4:0] |
SEND_A1 |
101 |
bit0=A_1
|
SEND_PAIR |
110 |
bit1=A_(i+1)、bit0=B_i
|
RESET |
111 |
内部状態を初期化 |
Nの送信
最大値200000を扱うため、Nは18bitで保持します。
5bitのDATAへ次の4byteに分けて送信します。
1byte目：N[17:15] 3bit
2byte目：N[14:10] 5bit
3byte目：N[9:5] 5bit
4byte目：N[4:0] 5bit
A_(i+1)とB_iを1byteで送る
A_iとB_iは、どちらも0または1です。
SEND_PAIRのDATAは次のようにします。
DATA bit1 = A_(i+1)
DATA bit0 = B_i
MicroPython側では、次の式で1byteを作成します。
data = ((a_next & 0x01) << 1) | (b & 0x01)
tx = (SEND_PAIR << 5) | data
入力データを圧縮したり、複数サンプルをまとめて送ったりはしません。
N-1組のデータについて、spi_exchange()を1回ずつ呼び出します。
MISOで18bitの答えを返す
答えは最大Nですので、18bit必要です。
今回は3byteに分けて返信します。
1byte目：bit7=VALID、bit1:0=ANSWER[17:16]
2byte目：ANSWER[15:8]
3byte目：ANSWER[7:0]
1byte目の形式は次のとおりです。
bit 7 bit 6 bit 2 bit 1 bit 0
+--------+------------------+---------------+
| VALID | reserved | ANSWER[17:16] |
+--------+------------------+---------------+
FPGAは最後のSEND_PAIRを受信した時点で答えを確定し、最初の返信byteをtx_dataへ設定します。
RP2040はNOPを3回送信し、3byteを順番に受信します。
SPI通信シーケンス
1ケースの通信は次の順番です。
RESET
NOP
Nを4byteで送信
A_1を1byteで送信
N-1回繰り返し:
A_(i+1)とB_iを1byteで送信
NOP ← ANSWER[17:16]とVALID
NOP ← ANSWER[15:8]
NOP ← ANSWER[7:0]
MOSIの入力部分だけで、送信byte数は次のようになります。
N送信 : 4byte
A_1送信 : 1byte
PAIR送信 : N-1 byte
合計 : N+4 byte
RESETと直後のNOPを除き、答えの受信に使うNOPまで含めると、測定対象は合計N+7回の1byte SPI送受信です。
SPIテンプレートV2をコピーする
第12回で作成したatcoder_spi_template_v2をコピーし、ABC467Cの素朴実装用プロジェクトを作成します。
abc467c_naive/
├── abc467c_naive.ffpga
├── bitstream/
│ └── abc467c_naive.bin
├── ffpga/
│ └── src/
│ ├── main.v
│ └── spi_target.v
└── firmware/
└── micropython/
└── abc467c_naive_test.py
今回もspi_target.vは変更しません。
問題固有処理では、SPIテンプレートV2のrx_data_strobeを使用します。
AIへVerilog実装を依頼する
main.vの作成は、AIへ次のように依頼しました。
Shrike-LiteでABC467C - Adjacent Sums (easy)を実装するため、
atcoder_spi_template_v2のmain.vを元に、
abc467c_naive用のmain.vを作成してください。
spi_target.vは変更しないでください。
Verilogで実装し、SystemVerilog固有構文は使用しないでください。
ABC467Cの制約は次のとおりです。
- 2 <= N <= 200000
- M = 2
- A_iは0または1
- B_iは0または1
M=2なので、操作後の値Xについて、
X_(i+1) = X_i XOR B_i
として処理できます。
X_1=0とX_1=1の二つの候補を同時に処理してください。
各候補について、現在のX_iと操作回数だけを保持し、
A配列とB配列は保持しないでください。
MOSIはbit7:5をCOMMAND、bit4:0をDATAとします。
コマンド：
- NOP = 3'b000
- SEND_N_17_15 = 3'b001
- SEND_N_14_10 = 3'b010
- SEND_N_9_5 = 3'b011
- SEND_N_4_0 = 3'b100
- SEND_A1 = 3'b101
- SEND_PAIR = 3'b110
- RESET = 3'b111
Nは18bitで保持してください。
SEND_A1のDATA[0]をA_1として受信してください。
X_1=0の候補とX_1=1の候補について、A_1と異なる候補の操作回数を1にしてください。
SEND_PAIRのDATAは次の形式です。
- DATA[1] = A_(i+1)
- DATA[0] = B_i
SEND_PAIRを受信するたびに、二つの候補について次を行ってください。
- next_value = current_value XOR B_i
- next_valueとA_(i+1)が異なる場合は操作回数を1増やす
N-1個目のSEND_PAIRを受信したクロックで、
二つの候補の操作回数の小さい方を18bitの答えとして確定してください。
MISOは答えを3byteで返信してください。
- 1byte目：bit7=VALID、bit1:0=ANSWER[17:16]
- 2byte目：ANSWER[15:8]
- 3byte目：ANSWER[7:0]
最後のSEND_PAIR受信時に1byte目をtx_dataへ設定し、
以後のNOP受信ごとに2byte目、3byte目を準備してください。
RESETではすべての問題固有レジスタとtx_dataを初期化してください。
問題固有処理はrx_data_strobeを条件に1回だけ実行してください。
main.vを全文提示してください。
今回の記事とコードの草稿作成にはAIを使用しています。
Verilogコード
実装したmain.vは次のとおりです。
(* top *) module main (
// ===== 共通部分：Shrike-LiteとSPIの外部端子 =====
(* iopad_external_pin, clkbuf_inhibit *) input clk,
(* iopad_external_pin *) output clk_en,
(* iopad_external_pin *) input rst_n,
(* iopad_external_pin *) input spi_ss_n,
(* iopad_external_pin *) input spi_sck,
(* iopad_external_pin *) input spi_mosi,
(* iopad_external_pin *) output spi_miso,
(* iopad_external_pin *) output spi_miso_en
);
// ===== 共通部分：内部クロックとSPI送受信データ =====
assign clk_en = 1'b1;
wire [7:0] rx_data;
wire rx_data_strobe;
reg [7:0] tx_data;
// ===== 問題ごとに変更する部分 =====
// ABC467C - Adjacent Sums (easy)
// M=2なので、最終的なA_1を0または1と仮定した2候補を並列に更新する。
// 各候補について、現在値と操作回数だけを保持し、配列は保持しない。
localparam NOP = 3'b000;
localparam SEND_N_17_15 = 3'b001;
localparam SEND_N_14_10 = 3'b010;
localparam SEND_N_9_5 = 3'b011;
localparam SEND_N_4_0 = 3'b100;
localparam SEND_A1 = 3'b101;
localparam SEND_PAIR = 3'b110;
localparam RESET = 3'b111;
reg [17:0] n_value;
reg [17:0] pair_count;
reg value0;
reg value1;
reg [17:0] cost0;
reg [17:0] cost1;
reg [17:0] answer_reg;
reg [1:0] reply_index;
reg answer_ready;
// SEND_PAIRのDATAは、bit1=A_(i+1)、bit0=B_i。
wire pair_a;
wire pair_b;
wire next_value0;
wire next_value1;
wire [17:0] next_cost0;
wire [17:0] next_cost1;
wire [17:0] next_answer;
wire final_pair;
assign pair_a = rx_data[1];
assign pair_b = rx_data[0];
// M=2では加算剰余はXORと同じ。
assign next_value0 = value0 ^ pair_b;
assign next_value1 = value1 ^ pair_b;
assign next_cost0 = cost0 + ((next_value0 != pair_a) ? 18'd1 : 18'd0);
assign next_cost1 = cost1 + ((next_value1 != pair_a) ? 18'd1 : 18'd0);
assign next_answer = (next_cost0 <= next_cost1) ? next_cost0 : next_cost1;
// pair_countは処理済みPAIR数。N=2なら最初のPAIRが最終PAIRになる。
assign final_pair = (pair_count == (n_value - 18'd2));
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
n_value <= 18'd0;
pair_count <= 18'd0;
value0 <= 1'b0;
value1 <= 1'b1;
cost0 <= 18'd0;
cost1 <= 18'd0;
answer_reg <= 18'd0;
reply_index <= 2'd0;
answer_ready <= 1'b0;
tx_data <= 8'h00;
end else if (rx_data_strobe) begin
case (rx_data[7:5])
NOP: begin
// 答えは3byteで返す。
// 1byte目: bit7=VALID, bit1:0=ANSWER[17:16]
// 2byte目: ANSWER[15:8]
// 3byte目: ANSWER[7:0]
if (answer_ready) begin
case (reply_index)
2'd0: begin
tx_data <= answer_reg[15:8];
reply_index <= 2'd1;
end
2'd1: begin
tx_data <= answer_reg[7:0];
reply_index <= 2'd2;
end
default: begin
tx_data <= 8'h00;
reply_index <= 2'd0;
answer_ready <= 1'b0;
end
endcase
end else begin
tx_data <= 8'h00;
end
end
SEND_N_17_15: begin
n_value[17:15] <= rx_data[2:0];
end
SEND_N_14_10: begin
n_value[14:10] <= rx_data[4:0];
end
SEND_N_9_5: begin
n_value[9:5] <= rx_data[4:0];
end
SEND_N_4_0: begin
n_value[4:0] <= rx_data[4:0];
end
SEND_A1: begin
// A_1の最終値を0と仮定する候補と、1と仮定する候補を開始する。
value0 <= 1'b0;
value1 <= 1'b1;
cost0 <= rx_data[0] ? 18'd1 : 18'd0;
cost1 <= rx_data[0] ? 18'd0 : 18'd1;
pair_count <= 18'd0;
answer_reg <= 18'd0;
reply_index <= 2'd0;
answer_ready <= 1'b0;
tx_data <= 8'h00;
end
SEND_PAIR: begin
value0 <= next_value0;
value1 <= next_value1;
cost0 <= next_cost0;
cost1 <= next_cost1;
pair_count <= pair_count + 18'd1;
if (final_pair) begin
answer_reg <= next_answer;
reply_index <= 2'd0;
answer_ready <= 1'b1;
tx_data <= {1'b1, 5'b00000, next_answer[17:16]};
end
end
RESET: begin
n_value <= 18'd0;
pair_count <= 18'd0;
value0 <= 1'b0;
value1 <= 1'b1;
cost0 <= 18'd0;
cost1 <= 18'd0;
answer_reg <= 18'd0;
reply_index <= 2'd0;
answer_ready <= 1'b0;
tx_data <= 8'h00;
end
default: begin
// 3bitコマンドをすべて使用しているため通常は到達しない。
end
endcase
end
end
// ===== 共通部分：SPI Targetモジュール =====
spi_target #(
.CPOL(1'b0),
.CPHA(1'b0),
.WIDTH(8),
.LSB(1'b0)
) u_spi_target (
.i_clk(clk),
.i_rst_n(rst_n),
.i_enable(1'b1),
.i_ss_n(spi_ss_n),
.i_sck(spi_sck),
.i_mosi(spi_mosi),
.o_miso(spi_miso),
.o_miso_oe(spi_miso_en),
.o_rx_data(rx_data),
.o_rx_data_valid(),
.o_rx_data_strobe(rx_data_strobe),
.i_tx_data(tx_data),
.o_tx_data_hold()
);
endmodule
問題固有回路が保持する主な状態は次のとおりです。
N 18bit
処理済みPAIR数 18bit
現在値 1bit × 2候補
操作回数 18bit × 2候補
答え 18bit
返信位置 2bit
配列やBRAMは使用しません。
AIへMicroPython実装を依頼する
次に、機能テストとベンチマークを行うabc467c_naive_test.pyを作成します。
今回はFPGA側よりも、RP2040側の処理内容が多くなります。
AIへ依頼した内容は次のとおりです。
Shrike-LiteでABC467Cの素朴実装をテストする
MicroPythonプログラムを作成してください。
atcoder_spi_template_v2_test.pyを参考にして、
abc467c_naive_test.pyを新規作成してください。
bitstream名はabc467c_naive.binです。
SPI設定、ピン設定、FPGAリセット処理、
1byteのSPI送受信処理は既存テンプレートと同じにしてください。
SPIは1MHz、CPOL=0、CPHA=0とします。
コマンド：
- NOP = 0b000
- SEND_N_17_15 = 0b001
- SEND_N_14_10 = 0b010
- SEND_N_9_5 = 0b011
- SEND_N_4_0 = 0b100
- SEND_A1 = 0b101
- SEND_PAIR = 0b110
- RESET = 0b111
Nは18bit値として4byteに分割して送信してください。
SEND_PAIRのDATAは次の形式にしてください。
- bit1 = A_(i+1)
- bit0 = B_i
1ケースでは、次の順番で通信してください。
1. RESET
2. Nを4byteで送信
3. A_1を送信
4. i=1からN-1まで、A_(i+1)とB_iの組を1byteで送信
5. NOPを3回送信して18bitの答えを受信
返信の形式：
- 1byte目：bit7=VALID、bit1:0=ANSWER[17:16]
- 2byte目：ANSWER[15:8]
- 3byte目：ANSWER[7:0]
公式サンプル3件と、追加テスト2件を実行してください。
各ケースについてNAME、N、RX、VALID、EXPECT、RESULT、
PASSまたはFAIL、TIME_USを1行で表示してください。
全機能テストがPASSした後、
2秒以内で処理できるNの目安を測定してください。
ベンチマーク入力はAもBもすべて0とし、答えは0としてください。
巨大な配列は確保せず、同じSEND_PAIR byteをN-1回送信してください。
測定範囲には、N送信、A_1送信、PAIR送信、答え受信を含め、
bitstream書き込みとRESETは含めないでください。
各測定の直前にgc.collect()を実行し、
GCの時間は測定へ含めないでください。
最初にN=1024から倍々に増やす指数探索を行い、
初めて2秒を超えた区間を見つけてください。
その区間に対して二分探索を行い、
2秒以内だったNと2秒を超えたNが隣接するまで探索してください。
MicroPythonの実行時間にはばらつきがあるため、
探索結果を厳密な最大値とは扱わないでください。
2秒以内だった側のNを100単位で四捨五入し、
次の形式で推定値を表示してください。
SEARCH_BOUNDARY PASS_N=... FAIL_N=...
BENCHMARK_ESTIMATE ESTIMATED_N_AROUND_2S=... ROUND_UNIT=100
途中の指数探索はEXPAND、二分探索はBINARYとして、
N、TIME_US、VALID、ANSWER、PASSまたはFAILを表示してください。
MicroPythonコード
実装したabc467c_naive_test.pyは次のとおりです。
from machine import Pin, SPI
import gc
import time
import shrike
# ===== 共通部分：bitstream名とShrike-Liteのピン設定 =====
BITSTREAM = "abc467c_naive.bin"
SCK = 2
CS = 1
MOSI = 3
MISO = 0
FPGA_RESET = 14
# ===== ベンチマーク設定 =====
TIME_LIMIT_US = 2_000_000
MIN_N = 2
MAX_N = 200_000
INITIAL_N = 1_024
ESTIMATE_UNIT = 100
# ===== 共通部分：FPGAへのbitstream書き込みとリセット =====
shrike.reset()
shrike.flash(BITSTREAM)
reset_pin = Pin(FPGA_RESET, Pin.OUT, value=1)
reset_pin.value(0)
time.sleep_ms(100)
reset_pin.value(1)
time.sleep_ms(100)
# ===== 共通部分：SPI Masterの初期化 =====
cs = Pin(CS, Pin.OUT, value=1)
spi = SPI(
0,
baudrate=1_000_000,
polarity=0,
phase=0,
bits=8,
firstbit=SPI.MSB,
sck=Pin(SCK),
mosi=Pin(MOSI),
miso=Pin(MISO)
)
# ===== 共通部分：1byteのSPI送受信 =====
def spi_exchange(value):
tx = bytes([value])
rx = bytearray(1)
cs.value(0)
spi.write_readinto(tx, rx)
cs.value(1)
return rx[0]
# ===== ABC467C固有処理 =====
NOP = 0b000
SEND_N_17_15 = 0b001
SEND_N_14_10 = 0b010
SEND_N_9_5 = 0b011
SEND_N_4_0 = 0b100
SEND_A1 = 0b101
SEND_PAIR = 0b110
RESET = 0b111
def make_command(command, data=0):
return (command << 5) | (data & 0x1F)
def send_n(n):
spi_exchange(make_command(SEND_N_17_15, (n >> 15) & 0x07))
spi_exchange(make_command(SEND_N_14_10, (n >> 10) & 0x1F))
spi_exchange(make_command(SEND_N_9_5, (n >> 5) & 0x1F))
spi_exchange(make_command(SEND_N_4_0, n & 0x1F))
def reset_problem():
# RESETの処理結果を次のNOPでSPI送信側へ反映させる。
spi_exchange(make_command(RESET))
spi_exchange(make_command(NOP))
def receive_answer():
rx_hi = spi_exchange(make_command(NOP))
rx_mid = spi_exchange(make_command(NOP))
rx_lo = spi_exchange(make_command(NOP))
valid = (rx_hi >> 7) & 0x01
answer = ((rx_hi & 0x03) << 16) | (rx_mid << 8) | rx_lo
return valid, answer, (rx_hi, rx_mid, rx_lo)
def send_pair(a_next, b):
# DATA bit1=A_(i+1), bit0=B_i
data = ((a_next & 0x01) << 1) | (b & 0x01)
spi_exchange(make_command(SEND_PAIR, data))
def run_test_case(name, a_values, b_values, expected):
n = len(a_values)
reset_problem()
# 測定直前にGCを実行し、ヒープ状態をなるべく揃える。
# GCの実行時間はTIME_USに含めない。
gc.collect()
start_us = time.ticks_us()
send_n(n)
spi_exchange(make_command(SEND_A1, a_values[0]))
for i in range(n - 1):
send_pair(a_values[i + 1], b_values[i])
valid, result, rx_bytes = receive_answer()
elapsed_us = time.ticks_diff(time.ticks_us(), start_us)
passed = valid == 1 and result == expected
status = "PASS" if passed else "FAIL"
print(
"NAME={} N={} RX=[0x{:02X},0x{:02X},0x{:02X}] VALID={} "
"EXPECT={} RESULT={} {} TIME_US={}".format(
name,
n,
rx_bytes[0],
rx_bytes[1],
rx_bytes[2],
valid,
expected,
result,
status,
elapsed_us
)
)
return passed
# ベンチマークではAもBもすべて0とする。
# 答えは常に0で、配列を確保せず同じPAIR byteをN-1回送信できる。
PAIR_ZERO = make_command(SEND_PAIR, 0)
def measure_zero_case(n, label="SEARCH"):
reset_problem()
# 各測定の直前にGCを実行する。
# reset_problem()後、計測開始前に行うことでGC時間を除外する。
gc.collect()
start_us = time.ticks_us()
send_n(n)
spi_exchange(make_command(SEND_A1, 0))
for _ in range(n - 1):
spi_exchange(PAIR_ZERO)
valid, answer, _ = receive_answer()
elapsed_us = time.ticks_diff(time.ticks_us(), start_us)
correct = valid == 1 and answer == 0
within_limit = correct and elapsed_us <= TIME_LIMIT_US
print(
"{} N={} TIME_US={} VALID={} ANSWER={} {}".format(
label,
n,
elapsed_us,
valid,
answer,
"PASS" if within_limit else "FAIL"
)
)
return within_limit, elapsed_us, correct
def find_upper_bound():
# いきなり大きなNを測ると、1回のFAILに長時間かかる。
# まず指数探索で2秒を超える最初のNを探す。
n = INITIAL_N
last_pass = MIN_N
while True:
if n > MAX_N:
n = MAX_N
passed, _, correct = measure_zero_case(n, "EXPAND")
if not correct:
raise RuntimeError("FPGA reply error during benchmark")
if not passed:
return last_pass, n
last_pass = n
if n == MAX_N:
return MAX_N, MAX_N
n *= 2
def binary_search_limit(low_pass, high_fail):
if low_pass == MAX_N:
return MAX_N, None
low = low_pass
high = high_fail
# 実測値にはばらつきがあるが、目安を得るため最後まで二分探索する。
# lowは直近のPASS、highは直近のFAILとして扱う。
while high - low > 1:
mid = (low + high) // 2
passed, _, correct = measure_zero_case(mid, "BINARY")
if not correct:
raise RuntimeError("FPGA reply error during benchmark")
if passed:
low = mid
else:
high = mid
return low, high
def round_to_estimate_unit(value):
# 100単位で四捨五入する。
estimated = (
(value + (ESTIMATE_UNIT // 2)) // ESTIMATE_UNIT
) * ESTIMATE_UNIT
if estimated < MIN_N:
return MIN_N
if estimated > MAX_N:
return MAX_N
return estimated
# ===== 機能テスト =====
TEST_CASES = [
(
"official_sample_1",
[1, 1, 1],
[1, 1],
1
),
(
"official_sample_2",
[1, 1],
[0],
0
),
(
"official_sample_3",
[0, 0, 0, 1, 1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 0, 1, 0],
4
),
(
"all_zero",
[0, 0, 0, 0, 0],
[0, 0, 0, 0],
0
),
(
"two_elements_mismatch",
[0, 1],
[0],
1
),
]
reset_problem()
pass_count = 0
for name, a_values, b_values, expected in TEST_CASES:
if run_test_case(name, a_values, b_values, expected):
pass_count += 1
fail_count = len(TEST_CASES) - pass_count
print(
"FUNCTION_SUMMARY PASS={} FAIL={} TOTAL={}".format(
pass_count,
fail_count,
len(TEST_CASES)
)
)
if fail_count != 0:
raise RuntimeError("Functional test failed")
# ===== 2秒前後となるNの推定 =====
# MicroPythonの実行時間にはばらつきがあるため、厳密な最大値とは扱わない。
# 指数探索と二分探索で得た境界を100単位に四捨五入して表示する。
low_pass, high_fail = find_upper_bound()
raw_pass_n, raw_fail_n = binary_search_limit(low_pass, high_fail)
estimated_n = round_to_estimate_unit(raw_pass_n)
if raw_fail_n is None:
print(
"SEARCH_BOUNDARY PASS_N={} FAIL_N=NONE".format(raw_pass_n)
)
else:
print(
"SEARCH_BOUNDARY PASS_N={} FAIL_N={}".format(
raw_pass_n,
raw_fail_n
)
)
print(
"BENCHMARK_ESTIMATE ESTIMATED_N_AROUND_2S={} ROUND_UNIT={}".format(
estimated_n,
ESTIMATE_UNIT
)
)
Verilogを合成する
main.vを保存したら、ForgeFPGA Workspaceで合成とbitstream生成を行います。
Synthesize
↓
Generate Bitstream
生成したFPGA_bitstream_MCU.binを、次の名前へ変更します。
abc467c_naive.bin
合成結果
合成後のリソースレポートは次のとおりでした。
問題固有処理は、二つの候補について1bitの現在値と18bitの操作回数を更新するだけです。
18bitの加算、比較、カウンタ、3byte返信の制御を含めても、LUT使用率は約28%でした。
今回は回路面積の最適化よりも、素朴な実装を基準として動かすことを優先します。
実機で動作確認する
abc467c_naive.binとabc467c_naive_test.pyをShrike-Liteへ配置し、Thonnyから実行します。
最初に公式サンプル3件と追加テスト2件を実行します。
すべてPASSした場合だけ、2秒前後となるNの探索へ進みます。
実行結果
[shrike_fpga] flashing: abc467c_naive.bin
[shrike_flash] FPGA programming done.
NAME=official_sample_1 N=3 RX=[0x80,0x00,0x01] VALID=1 EXPECT=1 RESULT=1 PASS TIME_US=1844
NAME=official_sample_2 N=2 RX=[0x80,0x00,0x00] VALID=1 EXPECT=0 RESULT=0 PASS TIME_US=1663
NAME=official_sample_3 N=10 RX=[0x80,0x00,0x04] VALID=1 EXPECT=4 RESULT=4 PASS TIME_US=3175
NAME=all_zero N=5 RX=[0x80,0x00,0x00] VALID=1 EXPECT=0 RESULT=0 PASS TIME_US=2161
NAME=two_elements_mismatch N=2 RX=[0x80,0x00,0x01] VALID=1 EXPECT=1 RESULT=1 PASS TIME_US=1685
FUNCTION_SUMMARY PASS=5 FAIL=0 TOTAL=5
EXPAND N=1024 TIME_US=147402 VALID=1 ANSWER=0 PASS
EXPAND N=2048 TIME_US=293703 VALID=1 ANSWER=0 PASS
EXPAND N=4096 TIME_US=591460 VALID=1 ANSWER=0 PASS
EXPAND N=8192 TIME_US=1187389 VALID=1 ANSWER=0 PASS
EXPAND N=16384 TIME_US=2374551 VALID=1 ANSWER=0 FAIL
BINARY N=12288 TIME_US=1792124 VALID=1 ANSWER=0 PASS
BINARY N=14336 TIME_US=2085700 VALID=1 ANSWER=0 FAIL
BINARY N=13312 TIME_US=1939427 VALID=1 ANSWER=0 PASS
BINARY N=13824 TIME_US=2012071 VALID=1 ANSWER=0 FAIL
BINARY N=13568 TIME_US=1975485 VALID=1 ANSWER=0 PASS
BINARY N=13696 TIME_US=1993751 VALID=1 ANSWER=0 PASS
BINARY N=13760 TIME_US=2003219 VALID=1 ANSWER=0 FAIL
BINARY N=13728 TIME_US=1998708 VALID=1 ANSWER=0 PASS
BINARY N=13744 TIME_US=2001184 VALID=1 ANSWER=0 FAIL
BINARY N=13736 TIME_US=2000026 VALID=1 ANSWER=0 FAIL
BINARY N=13732 TIME_US=1999201 VALID=1 ANSWER=0 PASS
BINARY N=13734 TIME_US=1999690 VALID=1 ANSWER=0 PASS
BINARY N=13735 TIME_US=1999764 VALID=1 ANSWER=0 PASS
SEARCH_BOUNDARY PASS_N=13735 FAIL_N=13736
BENCHMARK_ESTIMATE ESTIMATED_N_AROUND_2S=13700 ROUND_UNIT=100
機能テストは5件すべてPASSしました。
FPGA側の回答回路は、期待どおりに動作しています。
MicroPython実装 - 2秒前後となるNを指数探索する
今回の素朴実装がどの程度のNまで動くかは、実行前には分かりません。
最初から制約の中央であるN=100000を測定すると、2秒を大幅に超えた場合に長時間待つことになります。
そこで、最初は次のように倍々に増やします。
1024
2048
4096
8192
16384
...
これは指数探索です。
今回の結果では、8192は2秒以内、16384は2秒超過でした。
EXPAND N=8192 TIME_US=1187389 PASS
EXPAND N=16384 TIME_US=2374551 FAIL
これにより、2秒の境界が8192と16384の間にあることが分かります。
二分探索で境界へ近づく
指数探索で見つけた区間に対して、二分探索を行います。
12288 → PASS
14336 → FAIL
13312 → PASS
13824 → FAIL
...
最後は、次のようになりました。
BINARY N=13734 TIME_US=1999690 PASS
BINARY N=13735 TIME_US=1999764 PASS
BINARY N=13736 TIME_US=2000026 FAIL
1回の実行結果だけを見ると、境界は13735と13736の間です。
ただし、これは厳密な最大値としては扱いません。
厳密な最大値ではなく推定値とする
RP2040上のMicroPythonでは、同じ処理を実行しても時間に多少のばらつきがあります。
測定前にgc.collect()を実行してヒープの状態をなるべく揃えていますが、1byteごとのPython関数呼び出しや一時オブジェクト生成を含むため、境界付近の数件を厳密に決めることにはあまり意味がありません。
実際、測定方法を細かくして複数回の中央値で判定しようとすると、測定の前半と後半で実行時間の傾向が変わることもありました。
今回は、素朴実装の性能の桁を知ることが目的です。
そこで、二分探索自体は最後まで行いますが、得られたPASS側の境界を100単位で四捨五入し、推定値として表示します。
SEARCH_BOUNDARY PASS_N=13735 FAIL_N=13736
BENCHMARK_ESTIMATE ESTIMATED_N_AROUND_2S=13700 ROUND_UNIT=100
今回の結論は次のとおりです。
素朴な1byte単位送信では、
2秒で処理できるのは約13700サンプル
制約上限はN=200000ですので、この実装のままでは2秒以内に最大ケースを処理できません。
FPGAは待っている時間の方が長い
FPGA側では、1byteを受信するたびに、二つの候補についてXOR、比較、カウンタ更新を行います。
この処理はFPGAの数クロックで完了します。
一方、RP2040側では、各サンプルについて次の処理を繰り返しています。
Python関数を呼ぶ
送信用bytesを作る
受信用bytearrayを作る
CSをLowにする
1byteのSPI送受信を行う
CSをHighにする
今回測定したのは、FPGA単体の計算速度ではありません。
MicroPythonのループ
+ Python関数呼び出し
+ SPI API呼び出し
+ RP2040とFPGA間の1byte通信
+ FPGA側の逐次処理
を合わせた、Shrike-Lite全体の処理時間です。
FPGA側の回路をパイプライン化したり、同じ処理を複数並べたりしても、次の1byteが届くまで待っている状態では、システム全体の速度はほとんど変わりません。
今回の結果を見る限り、まず手を入れるべきなのはFPGAの計算回路ではなく、RP2040からFPGAへデータを渡す部分のようです。
次回以降、ボード上の配線だけで通信するという縛りの中で、Shrike-Lite全体の処理パフォーマンスをどこまで引き上げられるか試してみます。
今回のまとめ
今回は、ABC467Cを素朴なストリーム処理で実装しました。
M=2なので、操作後の値はXORで次のように求められます。
X_(i+1) = X_i XOR B_i
X_1=0とX_1=1の二候補を同時に処理することで、配列やBRAMを使わずに答えを求められました。
入力は、最初にNとA_1を送り、その後はA_(i+1)とB_iを1組ずつ、1byteで送信しました。
FPGA側の機能テストはすべてPASSしました。
一方、RP2040上のMicroPythonから1byteずつSPI送受信を行う方法では、2秒で処理できるサンプル数は約13700という結果になりました。
制約上限 : 200000
今回の推定値 : 約13700
今回の条件では、問題を解く回路よりも、データを回路へ供給する部分がシステム全体の性能を左右していました。
今回は速くすることを考えず、今後の改善と比較するための基準値を作ることができました。
次回
次回は、今回の素朴実装を基準にして、RP2040側のSPI転送方法を改善します。
1byteごとにspi_exchange()を呼び出す方法を見直し、複数byteを1つの転送データパッケージとしてまとめて送信します。
あわせてSPIクロックを引き上げ、安定して転送できる速度を確認したうえで、2秒間に処理できるNがどこまで伸びるか測定します。お楽しみに。
前回：Shrike-LiteでAtCoder問題を解く(13)：ABC467A - さっそくSPIテンプレートV2を使ってみる
次回：Shrike-LiteでAtCoder問題を解く(15)：RP2040側でSPI転送を高速化する