下に示すソースは、Marcの指手生成器の中のarbiter.vだ。これは、アービトレータ（Chrillyが言うところのコンパレータツリー）を構成する一部品で、指手生成器のクリティカルパスに大きく影響する回路である。ハード探索処理を構成する全てのユニットの中で、指手生成器が最もクリティカルパスが長いとするなら、このロジック如何で探索速度が決まる極めて重要なコンポーネントと言える。

--*** CodeBlue Chess ***
--Arbiter circuit implementation
--------------------------------------------------------------------------------
--fpga express implementation: 20 lut, 0 ff
--replaced if priority structure by comparison
--fpga express implementation: 18 lut, 0 ff
--optimization effort high, optimize for area
--fpga express implementation: 17 lut, 0 ff, 20.64ns delay
--redid priority circuit by hand, optimize high, speed
--fpga express implementation: 16 lut, 0 ff, 14.42ns delay

--tests to perform: noted by "optimize" comment
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
--use ieee.std_logic_arith.all;

entity arbiter is
port (
    invert_pri: in std_logic;
    arb1_in, arb2_in: in std_logic_vector(2 downto 0);      -- (2 downto 0)
    rowcol1_in, rowcol2_in: in std_logic_vector(5 downto 0);--x2,x1,x0,y2,y1,y0
    arb_out: out std_logic_vector(2 downto 0);              -- (2 downto 0)
    rowcol_out: out std_logic_vector(5 downto 0));
end arbiter;

architecture rtl of arbiter is

signal muxval,agtb: std_logic;

begin
--process for agtb
process(arb1_in,arb2_in)
begin
    if arb1_in>arb2_in then
        agtb<='1';
    else
        agtb<='0';
    end if;
end process;

--process for mux_val
process(arb1_in,arb2_in,invert_pri,agtb)
begin
    if invert_pri='1' and (arb1_in/="0000") and (arb2_in/="0000") then
        muxval<=not agtb;
    else
        muxval<=agtb;
    end if;
end process;

--process for arb_out and rowcol_out
process(arb1_in,arb2_in,rowcol1_in,rowcol2_in,muxval)
begin--optimize: try explicit values instead of mux
    if muxval='1' then
    --if arb1_in>arb2_in then
        arb_out<=arb1_in;
        rowcol_out<=rowcol1_in;
    else
        arb_out<=arb2_in;
        rowcol_out<=rowcol2_in;
    end if;
end process;

end rtl;

ソースの冒頭近くにあるMarcが書いたと思われるコメントを見ると、当時の開発環境（恐らくISEの古いバージョン）で合成した時、16LUTsを消費し14.42nsの遅延があったようだ。但し、この数字は昔のデバイスとは言え遅過ぎるので、多分入出力ピン－LUT間遅延も加算されているものと思われる。でなければ14.42ns×６（チェスの場合６レベルツリー接続なので）＝86.52nsとなり、アービトレータだけでここまで遅延が大きいと、まともな速さでは走らない計算になってしまう。

さてこの回路は、駒コード3ビット×２つの入力を比較し、価値の高い方、あるいは逆に低い方を判定し、その駒位置を含めて駒コードを出力する、というものである。これをQuartusII 5.1で合成してRTL viewerで等価回路図を機械的に作らせたのが左下図だ。更にtechnology map viewerを使って作図させ、下中央がStratixIIの場合、右下がCycloneIIの場合の実装上の回路図になった。StratixIIとCycloneIIでtechnology mapが異なるのは、同一メーカでもFPGAのアーキテクチャが微妙に異なる為である（特にLUTの）。

１つのアービタのみに着目すれば、実装上のロジックレベルはStratixIIで２、CycloneIIで３となり、アーキテクチャの違いによる性能比が３：２になることが判るが、ここでは参考例として挙げてみる。回路の具体的な遅延時間は、プロセスは勿論デバイスのスピードグレイドに依存する。１ロジックレベルあたり0.5nsと仮定すると１つのアービタの遅延時間は単純計算でStratixIIで1.0ns、CycloneIIなら1.5ns。これをこのまま将棋用の指手生成器に使って強制的に７レベルツリーで接続してアービトレータを構成した場合のクリティカルパスは、StratixIIで７ns、CycloneIIで10.5nsとなる。が、元々64桝のチェスの為に作られたアービタを、81桝の将棋用として無理矢理用いるのは多少無駄がある。そこでこれを将棋用に最適化することを考えてみる。

-- 多分、次稿は来年頃に続く --

アービタ改造 (1)