Shrike-LiteでAtCoder問題を解く(25)：ABC468C - Between P and Q（桁DPで加算器を使い回す）

はじめに

今回は、AtCoder Beginner Contest 468のC問題「Between P and Q」をShrike-Liteへ実装します。

この問題では、2つの順列P、Qの間にある順列の個数を求めます。

Nの最大値は10ですが、順列の総数は最大で10!になります。

すべての順列を生成し、PとQの間にあるか1つずつ確認する方法は、小規模なFPGAへそのまま実装するには重そうです。

そこで今回は、順列をすべて評価せずに答えを求める方法を考え、Shrike-Liteへ実装します。

問題を確認する

1からNまでの数字を1回ずつ含む2つの順列P、Qが与えられます。

条件を満たす順列Rの個数を求めます。

P < R < Q

ここで大小関係は辞書順です。

PがQより大きい場合や、PとQが辞書順で隣り合っている場合、答えは0になります。

制約は次のとおりです。

1 <= N <= 10

N=10のとき、順列の総数は、

10! = 3,628,800

です。

順列の全探索を考える

C++やPythonでの解法として真っ先に思いつくのは、すべての順列に対して P < R < Qであるかどうかを検査する、という全探索だと思います。

ただし、すべての順列を調べるには、最大で約363万個の順列を生成し、それぞれをP、Qと比較する必要があります。

順列を逐次生成する回路は作れそうですが、最大で約363万個を評価するため、処理時間が長くなります。並列化しようとすれば回路規模も大きくなるため、今回のShrike-Lite実装には向いていなさそうです。

では、小規模FPGAでも高速に正答にたどり着くアルゴリズムはありそうでしょうか。

PとQの順位が分かればよい

ここで、すべての順列を辞書順に並べてみます。

先頭の順列の順位は0とします。

例えばN=3なら、次の順番です。

0: 1 2 3
1: 1 3 2
2: 2 1 3
3: 2 3 1
4: 3 1 2
5: 3 2 1

PとQが、この並びの何番目にあるか分かれば、その間にある順列の個数も計算できます。

PとQの順位をそれぞれrank(P)、rank(Q)とすると、答えは次のとおりです。

answer = max(0, rank(Q) - rank(P) - 1)

PとQ自身は数えないため、最後に1を引きます。

PがQより後ろにある場合は0とします。

これなら、約363万個の順列を1つずつ評価する必要はありません。

残る問題は、PとQそれぞれの順位をどのように求めるかです。

桁DPを使って順位を求める

順列を左から1桁ずつ見ます。

現在の数字をcurrent_valueとすると、まだ使っていない数字のうち、current_valueより小さい数字を数えます。

その数字を現在の桁へ置いた場合、残りの桁は自由に並べられます。

残りがremaining桁なら、その並べ方は、

remaining!

通りです。

したがって、各桁では次の値を順位へ加えます。

未使用でcurrent_valueより小さい数字の個数 × remaining!

例えば、

P = (3, 1, 2)

の先頭を見ると、3より小さい未使用数字は1と2の2個です。

残りは2桁なので、

2 × 2! = 4

となります。

3より小さい数字から始まる順列が4個あるため、先頭の桁だけで順位へ4が加算されます。

その後、3を使用済みにして次の桁へ進み、同じ計算を繰り返せば、この順列が何番目になるのかを計算できそうです。

今回は、

• 現在の桁
• すでに使った数字
• 現在までに数えた順列数

を状態として持ち、左から順に更新する処理を、桁DPとして考えます。

FPGAへ比較的小規模に実装できそうか

順位計算に必要な情報を確認します。

Nは最大10なので、使用済み数字の記録は10bitで足ります。

順位の最大値は10! - 1なので、順位と回答は22bitで保持できます。

必要な階乗値も0!から9!までの10個だけです。

さらに、PとQの順列全体を保存する必要はありません。

入力された数字を左から順に処理し、使用済み状態と順位だけを更新すればよさそうです。

FPGAでは、候補数字を1つずつ確認し、未使用ならremaining!を加える方法が向いていそうです。

これなら、個数を数える回路や乗算器を用意せず、同じ加算器をFSMで繰り返し使えます。

Pの順位を保存した後に作業状態を初期化すれば、同じ順位計算回路をQにも使えます。

順列の全評価は難しそうでしたが、順位計算へ置き換えると、小規模なFPGAにも収まりそうな構成が見えてきました。

FPGAでは使用済み状態をbitで持つ

使用済みの数字は、10bitのused_maskで管理します。

used_mask[0] : 数字1
used_mask[1] : 数字2
...
used_mask[9] : 数字10

数字xを処理した後は、次のbitを立てます。

used_mask[x - 1] = 1

今回必要な主な状態は次のとおりです。

状態	用途
used_mask	使用済み数字
digit_index	現在の桁
current_value	現在処理している数字
candidate	確認中の候補数字
rank_work	計算中の順位
rank_p	Pの順位

順位の最大値は10! - 1なので、rank_work、rank_p、回答は22bitで保持できます。

個数を数えず、加算器を使い回す

C++やPythonでは、未使用で小さい数字の個数を数え、その個数と階乗を掛ける実装が自然です。

count × remaining!

しかし、FPGAで同じ計算をそのまま並列化すると、

• 候補数字を同時に比較する回路
• 使用済みbitを数える回路
• 個数と階乗を掛ける回路

が必要になります。

今回は、候補数字をFSMで1つずつ確認します。

candidate = 1
candidate = 2
candidate = 3
...

候補が未使用なら、そのたびに同じ階乗値をrank_workへ加えます。

if candidate is unused:
    rank_work += remaining!

つまり、

count × remaining!

を、次の処理へ置き換えます。

remaining!をcount回加算する

候補数字は最大でも9個です。

SPI通信は4MHz、FPGA内部クロックは50MHzなので、1byteを受信する間に約100クロックあります。

1byteには順列要素が2個入っています。

候補走査は1要素あたり最大9回です。前後の状態遷移を含めても、約100クロックある受信間隔には十分収まります。

今回は転送待ち時間を利用し、同じ22bit加算器を繰り返し使います。

PとQでも同じ回路を使う

P用とQ用の順位計算回路は別々に作りません。

Pを処理した後、その順位だけをrank_pへ保存します。

rank_p = rank_work

続いて、

used_mask = 0
rank_work = 0
digit_index = 0

として作業状態を初期化し、同じFSMでQを処理します。

共有するのは次の部分です。

• used_mask
• rank_work
• current_value
• candidate
• digit_index
• 階乗値の選択回路
• 22bit加算器
• 順位計算FSM

PとQを同時に処理する必要はないため、順位計算回路を2組用意する必要もありません。

今回の実装では、

1. 1桁内の候補数字で加算器を使い回す
2. PとQで順位計算回路全体を使い回す

という2段階の共有を行っています。

階乗値は定数として持つ

必要な階乗値は0!から9!までです。

この程度であれば、BRAMへ保存せず、case文による定数選択回路で十分でしょう。

残り桁数に応じて、case文で定数を選択します。

実コードでは、N - 現在位置 - 1から残り桁数を求めています。

reg [21:0] factorial_value;
always @(*) begin
    case (n_reg - digit_index - 4'd1)
        4'd0: factorial_value = 22'd1;
        4'd1: factorial_value = 22'd1;
        4'd2: factorial_value = 22'd2;
        4'd3: factorial_value = 22'd6;
        4'd4: factorial_value = 22'd24;
        4'd5: factorial_value = 22'd120;
        4'd6: factorial_value = 22'd720;
        4'd7: factorial_value = 22'd5040;
        4'd8: factorial_value = 22'd40320;
        4'd9: factorial_value = 22'd362880;
        default: factorial_value = 22'd0;
    endcase
end

SPIでPとQを送る

通信にはSPIテンプレートV3を使用します。

基本的な流れはこれまでと同じです。

RESET
RESET_ACK
START
START_ACK
N
P
Q
STATUS
ANSWER

Nは1byteで送ります。

PとQの各要素は1から10なので、4bitに収まります。

そこで、2要素を1byteへ詰めます。

byte[7:4] = 先の要素
byte[3:0] = 次の要素

例えば、

P = (1, 3, 2)

なら、次の2byteになります。

0x13, 0x20

Nが奇数の場合、最後の下位4bitは0で埋めます。

PとQは、それぞれ別のバーストで送信します。

MicroPython側では、次のように2要素ずつ詰めています。

def pack_permutation(permutation):
    packed = bytearray((len(permutation) + 1) // 2)

    for index in range(0, len(permutation), 2):
        upper = permutation[index]
        lower = 0
        if index + 1 < len(permutation):
            lower = permutation[index + 1]
        packed[index // 2] = (upper << 4) | lower

    return packed

FPGA側では、受信したbyteを上位4bit、下位4bitの順に処理します。

順位計算FSM

順位計算の中心は、候補数字を順番に確認するST_SCAN_CANDIDATEです。

ST_SCAN_CANDIDATE: begin
    if (rx_data_strobe)
        protocol_error <= 1'b1;

    if (candidate < current_value) begin
        if (!used_mask[candidate - 4'd1])
            rank_work <= rank_work + factorial_value;
        candidate <= candidate + 4'd1;
    end else begin
        state <= ST_MARK_USED;
    end
end

1クロックで確認する候補は1個だけです。

未使用ならrank_work + factorial_valueを実行し、同じ22bit加算器を次の候補でも使います。

候補走査が終わると、ST_MARK_USEDで現在の数字をused_maskへ記録し、次の桁へ進みます。

Pの最後まで処理した場合は、rank_workをrank_pへ保存します。その後、作業用レジスタを初期化してQへ切り替えます。

if (sequence_phase == 1'b0) begin
    rank_p         <= rank_work;
    rank_work      <= 22'd0;
    used_mask      <= 10'd0;
    digit_index    <= 4'd0;
    current_value  <= 4'd0;
    candidate      <= 4'd0;
    nibble_select  <= 1'b0;
    sequence_phase <= 1'b1;
    state          <= ST_WAIT_SEQUENCE_BYTE;
end else begin
    state <= ST_CALC_ANSWER;
end

Qの最後まで処理すると、順位差から回答を求めます。

if (rank_work > (rank_p + 22'd1))
    answer <= rank_work - rank_p - 22'd1;
else
    answer <= 22'd0;

PがQより大きい場合や、辞書順で隣接している場合も、この判定で0になります。

AIに実装を依頼する

今回も、仕様をまとめてAIへ実装を依頼しました。

依頼内容の要点は次のとおりです。

• SPIテンプレートV3を維持する
• PとQは4bitずつパックして送る
• 使用済み数字は10bitのused_maskで管理する
• 未使用数字の個数を並列に数えない
• 乗算器を使わない
• 候補数字をFSMで1個ずつ確認する
• 同じ22bit加算器を繰り返し使う
• PとQで順位計算回路を共有する
• PとQ全体をメモリへ保存しない
• コード内の説明コメントは日本語にする

完成したコードは以下にあります。

第25回コード全文

合成結果

ForgeFPGA Workshopで合成した結果は次のとおりです。

CLB LUTは375個、使用率は33.48%でした。

P用とQ用に別々の順位計算回路を用意せず、加算器も候補走査で繰り返し使用したため、Shrike-Liteへ十分収まっています。

Timing Analysis

50MHz、周期20nsの制約を設定しています。

項目	結果
WNS	+2.952ns
TNS	0ns
Achievable Period	17.047ns
Achievable Frequency	58.661MHz

WNSは正の値となり、50MHz制約を満たしました。

今回の最長経路でも、20nsに対して約3nsの余裕があります。

候補数字を一度に並列処理せず、1クロックずつ加算する構成は、回路面積だけでなくタイミング面でも扱いやすい結果になりました。

実機試験

Shrike-Liteへ書き込み、SPI 4MHzで実機試験を行いました。

期待値は、未使用数字のリスト内位置と階乗の乗算で求めています。FPGA側の逐次加算とは別の計算方法です。

smaller_count = available.index(value)
rank += smaller_count * factorial(len(permutation) - index - 1)
available.pop(smaller_count)

結果は次のとおりです。

SUMMARY TOTAL=11 PASS=11 FAIL=0 PASS

公式サンプル3件に加えて、次のケースを確認しています。

• N=1
• PとQが同じ
• PとQが辞書順で隣接
• PがQより大きい
• Pが最小順列
• Qが最大順列
• N=10
• 最大値付近
• 追加の混合ケース

最大ケースの結果は次のとおりです。

NAME=n10_minimum_to_maximum
N=10
P=(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
Q=(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
RESULT=3628798
EXPECT=3628798
VALID=1
ERROR=0
PASS=1
TIME_US=5035
POLL_COUNT=1

10!個の順列からPとQ自身を除くため、答えは次の値です。

3,628,800 - 2 = 3,628,798

24bitの応答として正しく受信できました。

11ケースすべてでPOLL_COUNT=1でした。

PとQの送信が終わった時点で順位計算もほぼ完了しており、最初のポーリングで回答を取得できています。

実測時間は約3.3msから5.0msでした。

この時間にはRESET、ACK確認、SPI転送、MicroPython側の処理も含まれています。

今回のまとめ

今回は、ABC468Cを桁DPでShrike-Liteへ実装しました。

使用済み数字を10bitで管理し、候補数字を1つずつ走査することで、同じ22bit加算器を繰り返し使用しました。PとQの順位計算にも同じ回路を使っています。

CLB LUTは375個、WNSは+2.952nsとなり、50MHz制約を満たしました。実機試験は11件すべてPASSしています。

順列の全探索では難しそうだった問題も、順位計算へ置き換えることでShrike-Liteへ収めることができました。

次回

次回も、AtCoder問題をShrike-Liteへ実装しながら、ソフトウェアのアルゴリズムをFPGAへどのように置き換えられるか試していきます。

---

前回：
Shrike-LiteでAtCoder問題を解く(24)：ABC468B④ - PLLでタイミング違反を解消する

次回：
Shrike-LiteでAtCoder問題を解く(26)：Interlude - ABC469の各問題をFPGA目線で見てみる

今回の全コード：
第25回コード全文