MN-Core 2の機械語ゴルフに入門する

今週の水曜日にMN-Core勉強会があり、そこでMN-Core 2のエミュレータが公開されたようです。 そこで、MN-Core 2の機械語アセンブリ言語がvsmと呼ばれているらしい?)のコードゴルフをやってみます。 MN-Core 2の機械語なんて書いたことないので、丁寧に勉強していきます。

入門書を読む

MN-Core2 vsm ゴルフ · GitHub

この入門書に書いてある、hello.vsm(下記コード)を見ながらやっていきます。

imm ui"0" $n0
imm ui"0x48656c6c" $r2
imm ui"0x6f2c2077" $r3
imm ui"0x6f726c64" $r0
imm ui"0x21000000" $r1

sor $subpeid $n0 $omr1
nop
lpassa $lr2 $lr0/$imr1

nop/2

# d get $lr0n0c0b0m0 1

l1bmrsbor $llr0v $llb0
nop/3

# d get $lb0n0c0b0 1

l2bmrsbor $lb0 $lc0

# d get $lc0n0c0 1

nop/3
mvp/n64i01 $lc0@.0 $p0
nop; wait i01

読み解いていきます。

定数定義

imm ui"0" $n0
imm ui"0x48656c6c" $r2
imm ui"0x6f2c2077" $r3
imm ui"0x6f726c64" $r0
imm ui"0x21000000" $r1

ここは雰囲気でわかりますが、即値を代入する命令が並んでいるようです。 ちゃんとマニュアルを読んでいくと、

  • 即値はALUがimm命令により出力する値である。ダブルクオートが必須なので注意する。(3.2.2 即値)
  • imm命令のオペランドにできるのは)単精度および半精度整数(3.2.2 即値)
    • 単精度整数というのは32bit整数のことを指しているらしい(1.3 語長と演算精度)
  • ペイロードとなるリテラルの解釈は、<integer-number-literal>の場合……(3.2.2 即値)
    • <integer-number-literal>はどこにも定義されていなくて詳細不明
  • $[(l|ll)(r|s|m|n)<addr>によりSRAMが参照できる(?)(3.4.3 Debug get文)
    • より厳密な定義は3.6.1に書かれているようだけれど……
    • 基本的には以下を覚えておけば良さそう?

というわけで以下のような感じのようです。

imm ui"0" $n0          # LM1[0]  = (u32)0
imm ui"0x48656c6c" $r2 # GRF0[2] = (u32)"Hell"
imm ui"0x6f2c2077" $r3 # GRF0[3] = (u32)"o, w"
imm ui"0x6f726c64" $r0 # GRF0[0] = (u32)"orld"
imm ui"0x21000000" $r1 # GRF0[1] = (u32)"!\0\0\0"

PE番号判別

sor $subpeid $n0 $omr1
nop

早速よくわかりません。

subpeidは、自身のPE番号を示す2bit値だそうです(3.6.1.20 固定値入力オペランド)。 SIMDではなくスカラで頑張ろうということでしょうか。

sor命令は、半精度('s'hort)のビット論理和(or)命令のようです(3.6.12 ALU命令式・表3.9・表3.10)。 この命令は、output is all 0の時、フラグが1になるようです(表3.11)。 つまり、PE番号が0の時だけフラグが1となり、PE番号が1~3の場合にはフラグが0になるようです。

どうやら、PE番号に依存したマスクを作る命令だったようです。 PE番号が0のPEだけ動かしていくといった感じのようです。

ここにnop命令が必要な理由は分かりませんでした。

命令間で適切にステップ数を空けなければならない場合がある。(3.6.3 ハザードの回避)

とあるので、nop命令が必要な局面があることは分かりますが、マスクレジスタについてこのような待ちが必要な状況が存在するのか、明確な記述は見つけられませんでした。 ただ、

マスクレジスタは通常のデータではなくフラグを保持する特殊なPEメモリであり、(3.6.2 マスクレジスタ

PE メモリへの書き込みを伴う命令は完了まで6サイクルを要する。(3.6.3.8 PEメモリ書き込み ⇒ PEメモリ読み出し)

とあるので、マスクレジスタについてもGRFと同様6サイクルの待ち時間が必要なのかもしれません。 次節の場合と異なりnop命令が一つで済んでいるのは、「iサイクル目(i=0,1,2,3)用」のマスクレジスタ、のような仕組みになっているからだと思われます(参考:3.6.2 マスクレジスタ における「サイクル方向」の記述)。 つまり、「0サイクル目用」への書き込みは第0サイクル、読み出しはnop命令が一つあれば第8サイクル、と7サイクル空き、6サイクルの待ち時間を満たせるからと思われます(「1サイクル目用」「2サイクル目用」「3サイクル目用」もまったく同様です)。

(2024/02/26 20:13追記ここから) Jun Makinoさんから、Xにて以下の指摘をいただきました。

実際、このnopを取り除いても正しく動作しました。 なんかアセンブルエラーになる気がしていましたが、勘違いか何か他の要因でのアセンブルエラーだったのかもしれません。 したがって、正しくは「マスクレジスタはPEメモリではあるが、次のステップで読み出すことが可能である。」となるようです。 (2024/02/26 20:13追記ここまで)

VLIW命令セットの機械語を書いたことがないので、このようなnopを入れないと正しく動かないみたいなことが書かれているマニュアルを見ていると新鮮です。

sor $subpeid $n0 $omr1 # M[1] = PEID == 0 ? 1 : 0
nop # マスクレジスタへの書き込みは6サイクル待つ必要がある(?)ので1NOP

条件転送

lpassa $lr2 $lr0/$imr1

nop/2

lpassa命令は、倍精度('l'ong)のコピー命令のようです(3.6.12 ALU命令式)。 なぜpassaなのかはよくわかりませんが、GRAPE-DRの論文[1]に記載されているGRAPE-DRアセンブリ*1にもpassaが出現する(何の命令であるかは不明)ので、伝統のある命令名のようです。

(2024/02/26 20:13追記ここから) 百千万億 萬(つもいよろず)さんからXにて以下の指摘をいただきました。

passa命令は、pass a(a入力をそのまま転送)の意味のようです。 (2024/02/26 20:13追記ここまで)

/$imr1は、その直前に書かれているオペランド$lr0=GRF0[0])への書き込みをマスクレジスタ1番によりマスクする、といった意味のようです。 $omr1$imr1で別表現ですが、これは「マスクレジスタの書き込み時は、$omr<addr>」「マスクレジスタを使う時は$imr<addr>」という使い分けになっているだけで、同じマスクレジスタを指しているようです。

マスクはマスクレジスタ書き込み時にも適用できることに注意する。(3.5.1.13 omr - マスクレジスタへの書き込み)

と書いてあるので、この時に見間違えないように表記を変えているのでしょうか。

また、GRFのアドレスは32bit単位で指定するようですが(3.6.1.10 r - GRF0)、長語(64bit)で転送しているため、GRF0[2]を読み出しているように見えてGRF0[2~3]を読み出しているようです。 同じく、GRF[0]に書き込んでいるようで、GRF[0~1]に書き込んでいるようです。 これも明示的な記述がなくてわかりませんでしたが、普通のメモリと同じくそうなっているのだと思います。

結局、GRF0[2~3]の値をGRF0[0~1]に書き込む(ただし、PE番号が0の場合のみ)、ということのようです(出力オペランドが後ろのようです。これは出力オペランドが複数になりうる(3.6 PE命令文)ことへの対応でしょうか?)。 これにより、PE番号0の場合はGRF0[0~1]が"Hello, w"に、PE番号1~3の場合はGRF0[0~1]が(そのまま変わらず)"orld!\0\0\0"になった状態になりました。 なかなか技巧的ですね。

さて、この操作の後にnop/2があります。 このnopの後に続く/は、nop命令を何回繰り返すかを示すようです。

GRF0/GRF1に書き込んだ後は、データ競合により1ステップ空けてからでないと同じアドレスからは読み出しを開始できない。(3.6.3.8 PEメモリ書き込み ⇒ PEメモリ読み出し)

とのことなので、nop命令が一つ必要なのはわかりますが、二つ必要なのは不思議です。 これはどうやら、

PE命令は1命令でL2B以下全体を4サイクル制御する(1.2 機械語命令概観)

に由来するようです。 この文章は分かりづらいですが、要するにPE命令は長さ4のベクトル命令であるということだと思います。 これにより、GRF0[0]へ第28サイクル、第29サイクル、第30サイクル、第31サイクルに書き込みアクセスされることになります。 nop命令が一つだと、この後第36サイクルにGRF0[0]からの読み出しが発生します。 これは間が6サイクル空いていないので、データ競合となります(3.6.3.8 PEメモリ書き込み ⇒ PEメモリ読み出し)。 実際、lpassa $lr2 $lr0/0100に変えてみるとnop命令が一つでもアセンブルエラーとはなりませんでした(参考:3.6.3.8 PEメモリ書き込み ⇒ PEメモリ読み出し)。

結局、ステップの後半でGRF0[0]周辺に書き込みアクセスしなければよいわけです。 そこで、後述のストライドアクセス指定を使ってlpassa $lr2v4 $lr0v4/$imr1としてみたところ、nop命令が一つでもアセンブルエラーとなりませんでした。 やはり、本質的にはnop命令が一つでも大丈夫なようです。 これはMN-Core 2の機械語ゴルフでnop命令を減らすテクニックとなるかもしれません。

lpassa $lr2 $lr0/$imr1 # GRF0[2~3] -> GRF0[0~1] if M[1] 

nop/2 # 最低6サイクル空ける必要があるためnopを二つ

L1Bへの転送

l1bmrsbor $llr0v $llb0
nop/3

(後ろに$llで始まるオペランドが来る)l1bmrsbor命令は、L1B命令の縮約命令(3.6.8.13 l1bmr<rrn_opcode> - 2長語16x1縮約)で、半精度('s'hort)のbitwise logical or(bor)演算指定のもののようです(3.5.5 縮約演算指定)。

各L1BMについて、各MAB配下の4PEからサイクルあたり2長語ずつを読み出し、MAB方向には縮約、PE方向には結合してL1BMにサイクルあたり8長語で書き込む。(3.6.8.12 l1bmr<rrn_opcode> - 1長語16x1縮約)

と書いてありますが意味が分かりません。 まず、「縮約」というのは「総和を求める」とかそういう操作のことのようです。 「MAB方向」「PE方向」というのがどの方向のことを言うのかはよくわかりませんが、疑似コードを見る限り、次の操作を行うようです(3.3 疑似コードによる命令動作の記述 に記法が載っている)。

  • 以下を4サイクルくりかえす。以下は第iサイクルの動作を記述する(i = 0, 1, 2, 3)。ストライド指定などによりiに依存しうる。
    • L1B配下の16個のMABに対し、各MABの0番目のPEの<src>~<src+1>(64bit)に書かれた値の総和(など)を求め、L1Bメモリの<addr_b + 8 * i>番地に書き込む
    • L1B配下の16個のMABに対し、各MABの0番目のPEの<src+2>~<src+3>(64bit)に書かれた値の総和(など)を求め、L1Bメモリの<addr_b + 8 * i + 4>番地に書き込む
    • L1B配下の16個のMABに対し、各MABの1番目のPEの<src>~<src+1>(64bit)に書かれた値の総和(など)を求め、L1Bメモリの<addr_b + 8 * i + 1>番地に書き込む
    • L1B配下の16個のMABに対し、各MABの1番目のPEの<src+2>~<src+3>(64bit)に書かれた値の総和(など)を求め、L1Bメモリの<addr_b + 8 * i + 5>番地に書き込む
    • L1B配下の16個のMABに対し、各MABの2番目のPEの<src>~<src+1>(64bit)に書かれた値の総和(など)を求め、L1Bメモリの<addr_b + 8 * i + 2>番地に書き込む
    • L1B配下の16個のMABに対し、各MABの2番目のPEの<src+2>~<src+3>(64bit)に書かれた値の総和(など)を求め、L1Bメモリの<addr_b + 8 * i + 6>番地に書き込む
    • L1B配下の16個のMABに対し、各MABの3番目のPEの<src>~<src+1>(64bit)に書かれた値の総和(など)を求め、L1Bメモリの<addr_b + 8 * i + 3>番地に書き込む
    • L1B配下の16個のMABに対し、各MABの3番目のPEの<src+2>~<src+3>(64bit)に書かれた値の総和(など)を求め、L1Bメモリの<addr_b + 8 * i + 7>番地に書き込む

<src>には$llr0vが指定されています。 このうしろについているvは、ストライドアクセスを意味するようです。 インクリメント量が省略された表記であり、アクセス語長での1語分(3.6.1.10 r - GRF0)ずつのストライドアクセス(つまりストリームアクセス)を指定しているようです。

結局、

  • L1Bメモリの0番地には、PE番号0のPEのGRF0[0~1](64bit)から読み出した値が書かれる(16個全部のMABが同じ値をL1Bに送って、それが全部ビット毎論理和されるので結局値は変わらない)
    • つまり、"Hello, w"が書き込まれる
  • L1Bメモリの1番地には、PE番号1のPEのGRF0[0~1](64bit)から読み出した値が書かれる(同)
    • つまり、"orld!\0\0\0"が書き込まれる
  • L1Bメモリの2番地には、PE番号2のPEのGRF0[0~1](64bit)から読み出した値が書かれる(同)
    • つまり、"orld!\0\0\0"が書き込まれる
  • L1Bメモリの3番地には、PE番号3のPEのGRF0[0~1](64bit)から読み出した値が書かれる(同)
    • つまり、"orld!\0\0\0"が書き込まれる
  • L1Bメモリの4番地には、PE番号0のPEのGRF0[2~3](64bit)から読み出した値が書かれる(同)
    • つまり、"Hello, w"が書き込まれる
  • L1Bメモリの5番地には、PE番号1のPEのGRF0[2~3](64bit)から読み出した値が書かれる(同)
    • つまり、"Hello, w"が書き込まれる
  • L1Bメモリの6番地には、PE番号2のPEのGRF0[2~3](64bit)から読み出した値が書かれる(同)
    • つまり、"Hello, w"が書き込まれる
  • L1Bメモリの7番地には、PE番号3のPEのGRF0[2~3](64bit)から読み出した値が書かれる(同)
    • つまり、"Hello, w"が書き込まれる

となって先頭に"Hello, world!\0"が完成しました(近くのメモリを破壊していますが)。

GRF[2] = "Hell", GRF[3] = "o, w", GRF[0] = "orld", GRF[1] = "!\0\0\0"のようなミドルエンディアン的なレジスタの使い方をしていたのは、こういう理由だったのですね。

また、今度はnop/3が挿入されています。 これは次のL2Bメモリへの転送までに10サイクル空ける必要がある(3.6.3.6 PE → L1BM転送 ⇒ L1BM → L2BM転送/内部マルチキャスト)ためのようです。

l1bmrsbor $llr0v $llb0 # L1BM[0] = PE[0].GRF[0~1], L1BM[1] = PE[1].GRF[0~1], ...
nop/3 # 10サイクル待つ必要がある

L2Bへの転送

l2bmrsbor $lb0 $lc0
nop/3

同じパターンですね。L1Bメモリの内容をL2Bメモリに転送しています。

nopが三つ必要な理由は分かりませんでした。 さすがにnopが一つもないとアセンブルエラーになります(たぶん4サイクルでは浮動小数点数加算での縮約は無理なのでしょう)が、nopが一つあればアセンブルエラーにはなりませんでした。 caddyを用いたジャッジでも問題なく動作したため、一つで十分と思われます。

l2bmrsbor $lb0 $lc0 # L2BM[0] = L1BM[0], L2BM[1] = L1BM[1], ...
nop/3 # 1つは必要だけれど3つはいらない(?)

出力(メモリへの書き込み)

mvp/n64i01 $lc0@.0 $p0
nop; wait i01

(第一オペランド$lcで始まり、第二オペランド$pではじまり@がつかない)mvp命令は、L2Bメモリの内容をPDMに転送する命令です(3.5.8.5 L2BM → PDM並列個別転送命令)。 ここで、PDMとはPCIe Interface Unit Data Memoryのことで、SRAMだそうです(1.1 構成)。 第0番グループのPDMはホストとPCIeインタフェースで接続(1.1 構成)されるらしいので、ここがMN-Core 2的な入出力になるのでしょう。 命令の動作としては、0番のL2Bについて、L2Bメモリの0番地から64bit値を64個、PDMの0番地に書き込む、という動作になるようです。

これだけでは実際にはデータの転送が終わっていない段階でプログラムが終了してしまうのでしょう。 これをふせぐために、wait i01があるようです。 wait命令を使うことで、mvpが終わるのを待つことができるようです(3.6.13 wait - PE命令にMV命令を待機させる)。 どれを待つかも柔軟に指定できるようで、mvp命令の後ろに書かれているi01部分が指定されています。 タグは0番はだめ(3.6.13 wait - PE命令にMV命令を待機させる)らしいので、1番を使っているのでしょう。

mvp/n64i01 $lc0@.0 $p0 # PDM[0] = L2B[0].L2BM[0~63]
nop; wait i01 # データの転送完了を待つ

まとめると、以下のような感じです。

imm ui"0" $n0          # LM1[0]  = (u32)0
imm ui"0x48656c6c" $r2 # GRF0[2] = (u32)"Hell"
imm ui"0x6f2c2077" $r3 # GRF0[3] = (u32)"o, w"
imm ui"0x6f726c64" $r0 # GRF0[0] = (u32)"orld"
imm ui"0x21000000" $r1 # GRF0[1] = (u32)"!\0\0\0"

sor $subpeid $n0 $omr1 # M[1] = PEID == 0 ? 1 : 0
nop # マスクレジスタへの書き込みは6サイクル待つ必要がある(?)ので1NOP

lpassa $lr2 $lr0/$imr1 # GRF0[2~3] -> GRF0[0~1] if M[1] 

nop/2 # 最低6サイクル空ける必要があるためNOPを二つ

l1bmrsbor $llr0v $llb0 # L1BM[0] = PE[0].GRF[0~1], L1BM[1] = PE[1].GRF[0~1], ...
nop/3 # 10サイクル待つ必要がある

l2bmrsbor $lb0 $lc0 # L2BM[0] = L1BM[0], L2BM[1] = L1BM[1], ...
nop/3 # 1つは必要だけれど3つはいらない(?)

mvp/n64i01 $lc0@.0 $p0 # PDM[0~63] = L2B[0].L2BM[0~63]
nop; wait i01 # データの転送完了を待つ

ゴルフしていく

出力の仕組みが分かったので、簡単なゴルフ問題から解いていきます。

anarchy golf - echo

1Byteのvsmファイルで正答できます。 一応endless問題なのでネタバレしないようにしておきます(といっても256通りしかないんですが)。

anarchy golf - Lower ASCII value

Post mortemの中で、出力を並列に計算できる問題です。 入力を読んだ後に計算する必要がありますが、計算の単位は2Byteなので二冪でありMN-Core 2の機械語コードで処理するのが容易そうです。

データレイアウトを考える

並列に計算できるのはいいですが、入力の2Byteが出力の1Byteに対応するので、「分配したデータをそのまま結合するとレイアウトを含めて同一のデータが上位階層に完成するようになっている。」(1.2 機械語命令概観)と相性が悪いのをどうにかしないといけなさそうです。 幸い、「L1BM 側アクセス速度と PE 側アクセス速度がともに同じである転送命令は同一の種別となる。同一種別の転送ではレイアウトが保たれる。」(3.6.8.2 L1BM命令式種別と折り返し動作)と書いてあり、逆に言えばアクセス速度が異なる転送命令を組み合わせればデータレイアウトを変えることができそうです。

表3.8をにらんでもよくわからないので、L1BM→PEの転送モードの動作を書き出してみました。

L1BM→PE(行き)

  • 1長語PE放送:L1BMの64bitを、64個あるPEに配る。並列処理には向かなさそう
  • 2長語PE放送:L1BMの連続する128bitを、64個あるPEに配る。並列処理には向かなさそう
  • 1長語16x1MAB放送:L1BMの連続する256bitを、16個あるMABに配る。各MAB内の4つのPEは、おのおの異なる64bitを受け取る。最悪これを使えば16個あるMABが全部同じ動作をしてHello, world!みたいな感じに出力を作れそう
  • 2長語16x1MAB放送:L1BMの連続する512bitを、16個あるMABに配る。各MAB内の4つのPEは、おのおの異なる128bitを受け取る
  • 1長語4x4MAB放送:L1BMの連続する1024bitを、MAB4個のグループ(4つある)に配る。グループ内のPE(16個ある)はおのおの異なる64bitを受け取る
  • 2長語4x4MAB放送:L1BMの連続する2048bitを、MAB4個のグループ(4つある)に配る。グループ内のPE(16個ある)はおのおの異なる128bitを受け取る
  • 分配:L1BMの連続する4096bitが読み出され、64個あるPEはおのおの異なる64bitを受け取る

データレイアウトを考える(再)

以下の組み合わせを使えばうまくいきそうともくろみました。

  • L1BM→PEでは、「2長語4x4MAB放送」を使う。L1BM側速度32に対してPE側速度2
    • 最高速なのは「分配」(64:1)だが、半分サイズで受け取る命令が存在しないので、入力と出力でデータレイアウトを変えることができない
    • 4倍無駄に同じ計算をすることになるがしょうがない
  • PE→L1BMでは、「1長語4x4MAB縮約」を使う。L1BM側速度16に対してPE側速度1
    • 対応する命令の半分のサイズを受け取る

コードを書く

データ読み込み部分

上記方針だと、L1Bあたり2048bit(256Byte)を処理して128Byteを生成することができます。 入力は500Byteくらいなので、2サイクルで全部の処理が完了します。 PE命令が長さ4のベクトル命令なので、4長語の処理まではノーコストです。 PEの担当する処理がちょうど2長語×2サイクル、なのでいいかんじです。

まず、上記方針であっているかデバッグプリントで調べます。

mvp/n64i01 $p0 $lc0@.0
nop; wait i01

l2bmb $lc0 $lb0
nop/3

l1bmm4 $llb0 $llr0v
nop/3

d get $lr0n0c0b0 2

これを実行した結果、PEでは以下のように受け取れたようです。

  • MAB番号0, 1, 2, 3のPE0のGRF[0~1] = 0x4974206973206120 = "It is a "
  • MAB番号0, 1, 2, 3のPE1のGRF[0~1] = 0x706572696F64206F = "period o"
  • MAB番号0, 1, 2, 3のPE2のGRF[0~1] = 0x6620636976696C20 = "f civil "
  • MAB番号0, 1, 2, 3のPE3のGRF[0~1] = 0x7761722E20526562 = "war. Reb"
  • MAB番号0, 1, 2, 3のPE0のGRF[2~3] = 0x656C207370616365 = "el space"

……

  • MAB番号4, 5, 6, 7のPE0のGRF[0~1] = 0x696464656E206261 = "idden ba"(64Byte目付近)

……

  • MAB番号0, 1, 2, 3のPE0のGRF[4~5] = 0x7265642073706163 = "red spac"(256Byte目付近)

……

  • MAB番号12, 13, 14, 15のPE2のGRF[6~7] = 0x2E2E2E2E00000000 = "....\0\0\0\0"(末尾)

えー、そういう感じで分配されるのかぁ。 連続する2長語がGRF[0~3]に入ることを期待していましたが、そうではなくて、連続する4長語が4つのPEのGRF[0~1]に入り、その次の連続する4長語が4つのPEのGRF[2~3]に入り、その次の連続する4長語は次のMABに送られて……という感じのようです。 つまり、AoSではなくSoAになっています。 まぁ計算機の命令セットとしてはSoAの方が簡単なので、そういう仕組みになっているのでしょう。

PE内ロジック

ここからPE内のロジックを記述していきます。 8bitシフトとマスクを使って整えた後、min命令を16bit×4のSIMD命令として使えばきれいに書けそうです。

即値付きの演算命令なんていう高級(?)なものはないようなので、シフト量とマスクは定数としておいておく必要があります。 ここで、即値を置く場所が重要です。 なぜなら、

複数の命令式が同一のPEオペランドから読み出している場合、それら全てでアクセスする領域が全サイクルで同一である(3.6.4 並列実行条件)

という制約があるからです。 この記述は意味不明ですが、命令をバンドル(VLIW命令)にまとめられる条件として、同じPEメモリ(GRF0とかLM1とか)に対して2read以上ができないということを意味しているようです(MN-Core Architecture Deep Diveの50ページ付近)。 明示的には書かれていないですが、この制約は2オペランド命令の第一オペランドと第二オペランドが同じPEメモリであってはいけないという制約にもなっているようです(実際アセンブルエラーになりますし、SRAM回路的にもそれが自然です)。

さて、smin命令を使うところまで書きました。 同一のPEオペランドが使えないというのがなかなか厳しい制約です(自分でバンク調停をやっていることになるので)。 LMは書き込みから読み込みまで2ステップ空けなければならず、GRFは書き込みから読み込みまで1ステップ空ければよいので、二オペランド命令を使う時は

  • 第一のステップで、LMに書き込む
  • 第二のステップで、GRFに書き込む
  • 第三のステップは、おやすみ(nop
  • 第四のステップで、LMとGRFをオペランドにして命令を実行

とやればポート衝突とデータ競合と1read制約を全部満たせていいかんじです。

imm us"8" $ln0
imm us"0xff" $lm0

mvp/n64i01 $p0 $lc0@.0
nop; wait i01

l2bmb $lc0 $lb0
nop/3

l1bmm4 $llb0 $llr0v
nop/3

# d get $lr0n0c0b0 2

llsr $lr0v $ln0 $ls0v
land $lr0v $lm0 $ln10v
land $ls0v $lm0 $lr10v
nop
smin $ln10v $lr10v $ls10v
nop

……。 "immop can't output to LM0"というエラーが出てしまいました。 そのような記述はソフトウェア開発者マニュアルは見当たりませんでしたが、アセンブルエラーになるのでそうなのでしょう。

即値命令が発行されているならば LM0 がアクセスされていない(3.6.4 並列実行条件)

との記載がありました。並列実行条件じゃないじゃん!わかりづらすぎる……。

マスク値をLM1に移動させます。 その影響で他の部分のレジスタ割り付けも変わってしまいました。

imm us"8" $ln0
imm us"0xff" $ln2

mvp/n64i01 $p0 $lc0@.0
nop; wait i01

l2bmb $lc0 $lb0
nop/3

l1bmm4 $lb0 $llr0v
nop/3

# d get $lr0n0c0b0 2

llsr $lr0v $ln0 $ls0v
land $lr0v $ln2 $lm10v
land $ls0v $ln2 $lr10v
nop
smin $lm10v $lr10v $ls10v
nop

d get $lr0n0c0b0m0p0 1
d get $ls0n0c0b0m0p0 1
d get $lm10n0c0b0m0p0 1
d get $lr10n0c0b0m0p0 1
d get $ls10n0c0b0m0p0 1

うまくいっていそうです。

次に、データをパックしなおします。 今は16bitのデータが4つで64bitになっていますが、これを8bitのデータ4つで32bitの状態に直します。

# 定数定義に追加

imm ui"0xffff" $ln4
imm us"16" $ln6

# さっきのコードのつづき

land $ls10v $ln4 $lm20v
ilsr $ls10v $ln0 $lr20v
nop
lor $lr20v $lm20v $ls20v
nop
llsr $ls20v $ln6 $lr30v
nop
lor $ls20v $lr30v $lm30v
nop/2

d get $ls10n0c0b0m0p0 1
d get $lm20n0c0b0m0p0 1
d get $lr20n0c0b0m0p0 1
d get $ls20n0c0b0m0p0 1
d get $lr30n0c0b0m0p0 1
d get $lm30n0c0b0m0 1

nopだらけになりましたが、とりあえずコードは書けました。 こういう密な依存があるときはnopが避けがたいのかなと思っていましたが、どうやら$alufというオペランドを指定することでフォワーディングを受け取れるようです(3.6.1.16 aluf - ALU演算結果フォワーディング)。 また、フォワーディングに渡すだけで終了する(PEメモリには書き込まない)場合は$nowriteをデスティネーションに指定する必要があるようです(3.6.1.19 nowrite - フォワーディング用ダミー出力)。 これを使って以下のように書き換えることができました。

imm us"8" $ln0
imm us"0xff" $ln2
imm ui"0xffff" $ln4
imm us"16" $ln6


mvp/n64i01 $p0 $lc0@.0
nop; wait i01

l2bmb $lc0 $lb0
nop/3

l1bmm4 $llb0 $llr0v
nop/3

# d get $lr0n0c0b0 4

llsr $lr0v $ln0 $nowrite
land $aluf $ln2 $lr10v
land $lr0v $ln2 $nowrite
smin $aluf $lr10v $ls10v

land $aluf $ln4 $lr20v
ilsr $ls10v $ln0 $nowrite
lor  $aluf $lr20v $ls20v
llsr $aluf $ln6 $nowrite
lor  $aluf $ls20v $lr30v
nop

d get $lr30n0c0b0m0 2

いいかんじです。

MAB内PE間データ交換

以下の交換をやって、結果の順序を合わせます。

  • PE[0].GRF0[31v4] → PE[0].GRF1[30v2](passa
  • PE[1].GRF0[31v4] → PE[0].GRF1[31v2](msr
  • PE[2].GRF0[31v4] → PE[1].GRF1[30v2](msr
  • PE[3].GRF0[31v4] → PE[1].GRF1[31v2](msr×2)
  • PE[0].GRF0[33v4] → PE[2].GRF1[30v2](msl×2)
  • PE[1].GRF0[33v4] → PE[2].GRF1[31v2](msl
  • PE[2].GRF0[33v4] → PE[3].GRF1[30v2](msl
  • PE[3].GRF0[33v4] → PE[3].GRF1[31v2](passa

これには、以下の順序で命令を並べれば最小命令数になりそうです(問題の入力が短いためベクトル長2で十分であることや、msr×2とmsl×2が同じであることを生かせば、同じPEへの転送や2個となりのPEへの転送を統合してもう一命令ずつ減らせるかもしれません)。

ipassa $r31v4 $s30v2 if PE == 0 (don't care = 1,2,3)
imsr $r31v4 $s31v2 if PE == 0 (don't care = 1,2,3)
ipassa $aluf $s30v2 if PE == 1 (don't care = 2,3)
imsr $aluf $s31v2 if PE == 1 (don't care = 2,3)

ipassa $r33v4 $s31v2 if PE == 3 (don't care = 2)
imsl $r33v4 $s30v2 if PE == 3 (don't care = 2)
ipassa $aluf $s31v2 if PE == 2
imsl $aluf $s30v2 if PE == 2

このマスクを作っていきます。 以下のようにすると前準備なしで必要なマスクが作れます。 また、$alufを除いては副作用がありません。

idec $subpeid $omr1 # [1,2,3]
idec $aluf $omr2 # [2,3]
iand $aluf $aluf $omr3 # [2]

# ↓確認用↓

zero $r0v
ipassa $n4 $r1/$imr1
ipassa $n4 $r2/$imr2
ipassa $n4 $r3/$imr3

d geth $r0n0c0b0m0 4

で、実行してみるとNo valid operation in this line.と怒られます。 どうやらmsr/msl命令は長語の転送しかないという罠を踏んだようです。

例えばmslの演算種別はuntypedなので精度指定は付けられず、(3.6.12 ALU命令式)

交換は長語でやって、短語単位での位置調整(インタリーブするように並べ替え。アンパックというらしい)は別の命令でやることにします。

lpassa $lr30v2 $ls30v
msr $lr30v2 $ls40v
lpassa $aluf $ls30v/$imr1
msr $aluf $ls40v/$imr1

lpassa $lr32v2 $ls40v/$imr2
msl $lr32v2 $ls30v/$imr2
lpassa $aluf $ls40v/$imr3
msl $aluf $ls30v/$imr3
nop
ipassa $s31v2 $s40v2

これではだめだった

で、このコードをcaddyで動かしてみると、先頭の方は正しい答えなのですが、行が変わったあたりから出力が変です。 どうも2Byteを取る組み合わせがおかしいっぽい挙動をしていて、改行コードの違い("\012"と"\015\012"の違い)が原因かと思いましたが、どうやらこの問題は行ごとに解かないといけない問題だった ようです。 つまり、input1の一行目It is a period of civil war. Rebel spaceships, striking from a hidden base, have won their first victory against the evil Galactic Empire.\nは改行文字を含めて奇数文字ですが、次の行は仕切り直して"Du/ri/ng/ t/he/..."の組み合わせで解かなければいけません。

よく確認しておくべきでした。

これに対処するためには、自分の担当文字列に'\n'が何個あるかを数え、それを自分より後ろの文字列の担当者に伝えて適切な量だけシフトすればよさそうです。 つまりprefix sumですが、MAB間の直接通信はないっぽく、縮約や結合はできてもprefix sumを計算するモードはないようなので、全対全の通信(実際には基数4での縮約と放送?)が必要そうです。

また、シフトではみ出した分の“袖交換”も必要です。 一気にたくさん転送するタイプのL1BM命令にはアライン制約があり、ちょっとだけずれた部分を転送するというのが無理そうです。 これに対しては、分配(3.6.8.20 l1bmd - 分配)命令についているラウンドロビンずらし機能を行きでは使って帰りでは使わないみたいなことをすると、ずらしたデータをL1Bメモリ内に生成することができそうです。

ただ、これを完全に実装するのはものすごい労力がかかりそうなのであきらめました。 MN-Core 2の機械語を手で書くことの無謀さがわかってきました。 とりあえず、PE内でのprefix sumだけ実装しました。

prefix sumの実装

以下のような感じでprefix sumできるようです(PEが担当する8文字中、奇数文字目4か所のうちには高々一つの改行しか存在しないと仮定しました。これはテストケースでは満たされます*2)。

なんだか便利そうなTレジスタ(Temporary Registerの略だそうです:1.2 機械語命令概観)をこれまで使っていなかったので、たくさん使ってみました。 書き込んでから読めるまでに1ステップ空けなければいけないので、使い勝手はGRFとあまり変わりませんが、使ってないアドレスに捨てないといけないとか、第一オペランドと第二オペランドを違うPEメモリにしないといけないとかの制約がゆるくなるので楽できます。 1ステップ空けないといけない制約は、そもそも直前のステップの結果は$alufでとれるのであまり気になりません。むしろ、「次の命令と次の次の命令で使いたい」みたいなときに二か所目として使えていいかんじです。 逆に、うしろにvっていうのがつかないのでベクトル命令なのかスカラ命令なのかわかりづらいのがやや不満です。

imm us"0x0a00" $ln8
imm us"0xff00" $ls8
imm us"1" $ln10

# d get $lr0n0c0b0 4

land $lr0v $ls8 $nowrite       # 偶数バイト目をマスク
sxor $aluf $ln8 $omr4          # 2Byteごとに0x0a00であればMR4[i] = 1
zero $ls0v                     # ゼロクリア(たぶん初期化時に0になっているけれど、MR4が利用できるまでに時間が余っているので)
spassa $ln10 $ls0v/$imr4 # 0x0aの所だけを1にする
zero $llt                      # ゼロクリア(たぶん初期化時に0になっているけれど、GRF0[0~7]が利用できるまでに時間が余っているので)
lpassa $ls0v $omr5             # 奇数文字目のどこにも0x0aがなければMR5=1(8Byte単位のマスク)
linc $lt $ls50v                # 64bit整数としての1を作る(imm命令では作れない※)
zero $ls50v/$imr5              # マスク付きの0書き込み=奇数文字目のどこかに0x0aがあれば1のまま
nop                            # $ls50vが利用可能になるまで待つ
msl $ls50v $lt                 # 次の8Byteを担当するPEに渡す
ladd $ls50v $aluf $lr50v/$imr1 # PE番号が1,2,3なら足す
msl $lt $lt                    # 受け取ったのをさらに次の8Byteを担当するPEに渡してT regは上書き
ladd $lr50v $aluf $lr50v/$imr2 # PE番号が2,3なら足す
msl $lt $lt                    # 受け取ったのをさらに次の8Byteを担当するPEに渡してT regは上書き
ladd $lr50v $aluf $lr50v/$imr2 # PE番号が2, 3なら足して……
nop                            # $lr50vが利用可能になるまで待つ
lsub $lr50v $lt $lr50v/$imr3   # PE番号が2なら引く(合わせて、PE番号が3なら足したことになる)

# d get $lr50n0c0b0 4 # 通信完了!

※imm命令のuはunsignedではなくupperの意味っぽい。imm命令を短語書き込みで使えばよかったのかも?

マスクレジスタを使っている部分は、LMへのTレジスタ間接アクセス(3.6.1.6 m - LM0 (ベースアドレスレジスタ書き込みを除く))を使うともう少し短くできるのかもしれません。

他のアイデア

浮動小数点数演算は使わないからマニュアルを読まなくていいかなと思っていたんですが、どうも行列演算ユニットがそれなりに便利に使えるようなので、これをうまく使うと命令数が減らせるのかもしれません(整数命令ばかりやる場合は余っているので)。 まず、4つのPEではMAUを共有しているっぽい(明確な記載はないが行列レジスタ書き込み命令や行列ベクトル積和演算命令はそのように動作するみたい:3.6.10 行列レジスタ書き込み命令式・3.6.9.2 dmfma - 倍精度行列ベクトル積和演算の基本動作)ので、適切な行列を事前に入れておけば、これを無理やり使ったシャッフルやprefix sumが可能なのかもしれません。 また、行列レジスタ転置読み出しというのが存在して(3.6.1.14 x, y - 行列レジスタ。命令名は行列レジスタ読み出し命令っぽい:3.6.11 行列レジスタ読み出し命令式。非常にわかりづらいが、どうも書いたデータをそのまま読み出すことはできなくて転置読み出ししかできないみたい)、これを使うと他のPEが書いたデータが手に入るっぽいので、これを使ったデータ交換も可能なのかもしれません。

水平方向命令は存在しないのかなと思っていましたが、ブロックフロート化命令(3.6.12.11 bfe, bfn - ブロックフロート化命令)は横方向のデータと相互作用のあるSIMD命令なので、これを使うと語長を読み替えてマスクレジスタを作って……みたいなことをしなくてもうまくできる可能性があります。 うまい感じに奇数バイト目が重要で半精度浮動小数点数の指数部になっているのも、いいかんじです。 でもこれってもしかしてPE内で閉じてないで4つのPEが相互作用する命令だったりするのでしょうか? 明確な記述がなくてわかりませんが、倍精度用の命令が1長語読み出して1長語出力する命令であるからには何らかの作用があるはず(相互作用がなければ恒等変換なので無意味)、と思うと多分そうなっているのでしょう。 幸い、この問題の入力は32Byte中にも二つ以上の改行文字があることはないので、それでも使えそうです。 PE方向に縮約するL1BM命令は存在しないので、これは便利かもしれません。

上で書いた後気づいたんですが、ゼロフラッシュマスク(3.6.2.2 ゼロフラッシュマスク適用)が存在するのでゼロ初期化はいらなかったようです。

あと気づいたんですが、ゴルフ的には$nowriteよりも$tで捨てたほうが短くなりますね。 また、$ltなどとは書かなくていいようです(3.6.1.12 t - T レジスタ)。

anarchy golf - hello world

くやしいのでHello, world!のゴルフをやります。 一応endlessの問題ですが、shinhさんも公開していますし、そもそもそんなぎりぎりまで詰めた解でもなさそうなので(Preferred Networks社内でMN-Core機械語を日夜(?)書いている方々に勝てるわけがありません)、参加者が増えることを期待して、公開することにします。

とりあえずshinhさんの解をもとにして、以下のような感じにしてみました。

sor $subpeid $r0 $omr1
imm i"0x6f726c64" $r0
imm f"0x1p-61" $r1
imm f"234929.69" $r0/$imr1
imm i"0x6f2c2077" $r1v/$imr1
nop
l1bmd $lr0 $lb0
nop/3
l2bmd $lb0 $lc0
nop
mvd/n64 $lc0 $p0@0

結構怪しいコードができました。 まず一行目では、エミュレータが初期化時にゼロクリアしていると思われる(実機では何が入っているか保証されなさそうな)$r0を読み出すことで、即値0を作る手間を省いています。 これを仮定出来ない場合、zero $tが一命令かつ文字数も少なくてよさそうです。 基本的にはここで作ったPE=0の時だけ書き込まれないマスクを使って出力文字列を作っていくのですが、いったん書いてからlpassaで上書きするのではなく、imm命令の出力をそのままマスク書き込みする感じにしました。 あと、即値のu指定はいらなかったようです。これは何に使うんだろう?

また、完全に無意味なゴルフテクニックですが、0x21000000は縮められます。 0x21000000は10文字ですが553648128とすれば9文字です。 さらに、今回は末尾が全部0なので浮動小数点数としてみなせば仮数部が空っぽということで、浮動小数点数リテラルを使えば短く書くことができます。 絶対値がかなり小さい数なので十進数で書くとかえって長くなりますが、十六進浮動小数点数リテラルがうまくはまり、7文字にすることができます。 234929.69も同様で、10文字が9文字に減らせます。仮数部が24bitなので十進八桁で指定できて、残りの指数部を小数点の位置でエンコードしているので縮まっているようです。

$r1vとしているのは、上で話したハザードをよけるテクニックです。 これにより、命令数が1つ減ります。 また、ゴルフ的にも、vで1文字増えますがnop/2nopになって2文字減るので、合計で1文字縮まります。

PEからL1Bに送り出すのは、ニーモニックが短いl1bmd命令を使うことにしました。 また、語長も短くていいので、$lr0とすることで、lを削減できます。

最後のMV命令は、mvd命令を使うと@.0@0にできて1文字削減できます。

また、少なくともcaddyの環境では、最後のウェイトは特に必要ないようです。 これは、caddyが後ろにつけるnop; wait i02で待ってくれることが原因かもしれません。

このソースコードは、末尾に改行コードがないと正しく動作しません。 これは、caddyが後ろにつけるfと連結されてしまうからです。 caddyが後ろにつけているcefといった命令(dのようなデバッグコマンドの一種?)の説明はソフトウェア開発者マニュアルにはなかったので、これが何なのかはわかりませんでした。

これにより、185Byte(28/127/30)、11命令の解答を作ることができました。

比較的ゴルフ出来そうなPost mortemな問題

基本的には、以下の条件を一つでも満たすと、MN-Core 2の機械語コードで出力を作るのはかなり面倒そうです。

  • (一入力が「複数ケース」的な場合)ケースごとに入力長が異なる
  • 出力の各行の長さが異なる
  • 出力の各行の長さが同じでも、その長さが入力に応じて変化する(二冪で変化する場合は除く)

以下では、そのような条件を満たさない、比較的MN-Core 2の機械語コードに優しそうな問題を集めてみました。 だれか挑戦してみてください。

anarchy golf - Permutations

Post mortemの中で、出力を並列に計算できそうな問題です。 この問題は入力がなく、計算により出力を構築する問題です。 一行12文字(改行文字含む)の出力を720行すれば正答できるので、比較的MN-Core 2の機械語で解くのが容易そうです。 ただ、64と比較的大きな二冪の倍数ですが、全体としては二冪ではないため、それなりに面倒そうです。

anarchy golf - Missing Digit

Post mortemの中で、出力を並列に計算できそうな問題です。 この問題は入力から出力を計算する問題です。 一行あたり10文字(改行文字含む)を読み2文字(改行文字含む)出力する問題なので、比較的MN-Core 2の機械語で解くのが容易そうです。 処理の単位が10Byteで二冪ではないため、それなりに面倒そうです。

anarchy golf - Digit depth

Post mortemの中で、出力を並列に計算できそうな問題です。 この問題は入力長と出力長が同じ、文字列変換の問題です。 括弧のネスト段数に応じて出力文字を変えるという問題なので、prefix sumアルゴリズム(対数段の通信)で解くことができます。 MN-Core 2のアセンブリを直書きして性能を引き出すために習得しないといけない技能の勉強にはもってこいという感じがします。 ただ、ゴルフ的には、問題サイズが小さいので直列にやった方が縮まりそうな気はします……。

もうちょっと面倒そうな問題

先ほど挙げた条件を多少満たしているものの、なんとかなりそうな問題を集めてみました。

anarchy golf - The 9801 debacle

ぶっちゃけ数を0から9999まで出力するみたいな問題です。 leading zeros付きで出力すればよいので出力単位もそろっていて並列計算可能です。 むずかしいのは入力に応じて出力の単位が8Byte/6Byte/4Byteと変化する部分ですが、二冪が2つ含まれる3通りなので比較的なんとかなるかもしれません。

anarchy golf - Morse decode

モールス信号を解読する問題です。 “袖”付きで入力をPEに持ってくれば、出力を計算すること自体は可能です。 むずかしいのは入力の何バイト目と出力の何バイト目が対応しているのか自明でないことですが、これもprefix sumとかでなんとかするのでしょう。

まとめ

参考文献

[1] J. Makino, K. Hiraki, M. Inaba, Proc. of the 2007 ACM/IEEE Conf. on Supercomput. 21(18), 1-11.
[2] K. Namura, et al., 2021 Symposium on VLSI Circuits, 35(89), 1-2.

*1:「MN-CoreはGRAPE-DRの拡張である」とMN-Coreの論文[2]に記載されていました。

*2:競プロerへ:あなごるは高々三つ与えられるテストケースさえあっていれば良いという文化です。他の提出へのチャレンジ(いわゆるHack)はありません(乱数を利用した提出へのチャレンジとしてのリジャッジは有効化されている問題もあります)。そもそも問題文がものすごく曖昧だし……。