MN-Core Challenge #1 に参加してました。この手のコンテストは久々でしたがまあまあ善戦できたんじゃないでしょうか。
最終結果は2位で最短賞もほとんど獲っていないので私が解説を書いてもしょうがないかなと思っていたのですが、そすうぽよさんの参加記を見ると似たような行数でも方針の違いがあったりして面白かったのでちょっとだけ解説を書いておきます。
問題解説
公式解説とそすうぽよさんの解説を踏まえたうえで差分がありそうなところをいくつか。
コンテスト参加者向けのつもりで書いているので問題概要やアーキテクチャについての話は省略しています。必要であれば公式資料などをあたってください。
Mod 3 (9 lines)
Standings を見ると 10 lines 解がちらほら出てきています。
おそらく imm → ALU → MAU → ALU くらいの処理しかできないと思われるので適当に処理の形を ior (浮動小数点数化) → fvfma (何らかの変換) → iand (下位ビットのマスク) と決め打ちします。そして浮動小数点数化に使用するビットパターンを f"1.5" (仮数部が3の倍数かつ最下位8ビットが0となるような適当な数) に固定して fvfma で使用する乗数と渡し方を総当たりで試してみると候補が見つかるのでそれを使うと imm×3 + ior×4 + iand×4 (fvfma は ALU 命令と並行して処理) で11行解が得られます。
ここから定数 (imm) を削減していきます。まず、浮動小数点数化に使うパターンと fvfma で使う乗数を共通化します。これは X の範囲が狭く乗数の精度はそれほど求められないことからまだ候補が存在すると考えられ、実際に探索してみるといくつかの候補が見つかります。これで imm が1回減って10行となります。
最後に iand で使うマスク (ui"3") をなんとかします。定数を用意してからマスクの値が必要になるまでの間3ステップほどMAUが空いているのでそこでマスクを作ることを考えます。定数の MSB 側半語と LSB 側半語をそれぞれ半精度浮動小数点数として解釈してみます。 LSB 側は 0b11×2^k の形になる候補が多いことと、 MSB 側も単精度に拡張すると下位14ビットは必ず0になることから、指数部の差が22となるような組だとそれらを加算することで下位16ビットが 0b??000000_00000011 となるような値が得られるはずです。
実際に探索してみると下位16ビットが 0x8003 となるものがいくつか見つかり、さらにそのうち一部は fvfma の結果の下から15ビット目が立つことが無いようなので、これをマスクとして利用することでさらに imm をひとつ削減でき9行となります。
imm ui"0x3eaa9300" $ln32/1000
ior $lm0v $aluf $ls0v ; hvpassa $aluf $lr0v $lt ; l1bmd $aluf $lb0 ; noforward
ior $lm8v $aluf $ls8v ; hvpassa -$aluf $omr1 ; ; noforward
ior $lm16v $aluf $ls16v ; fvadd/$imr1 $t -$r1 $r0v ; ; noforward
ior $lm24v $aluf $ls24v ; fvfma $ls0v $ln32 -$ls0v $nowrite ; l1bmd $lb0 $nowrite
iand $mauf $lr0 $ln0v ; fvfma $ls8v $lbf -$ls8v $nowrite ; l1bmd $lb0 $nowrite
iand $mauf $lr0 $ln8v ; fvfma $ls16v $lbf -$ls16v $nowrite ; l1bmd $lb0 $nowrite
iand $mauf $lr0 $ln16v ; fvfma $ls24v $lbf -$ls24v $nowrite
iand $mauf $lr0 $ln24v
定数の探索に用いたプログラム:
// g++ -O3 -mfma search.cpp
#include <limits>
#include <cstdio>
#include <cstdint>
inline float u2f(uint32_t x){
union {
uint32_t u;
float f;
} u;
u.u = x;
return u.f;
}
inline uint32_t f2u(float x){
union {
uint32_t u;
float f;
} u;
u.f = x;
return u.u;
}
inline float h2f(uint32_t x){
const uint32_t s = (x >> 15u) & 0x01u;
const uint32_t e = (x >> 9u) & 0x3fu;
const uint32_t m = x & 0x01ffu;
if(e == 0x3fu){ return std::numeric_limits<float>::infinity(); }
if(e == 0x00u){ return 0.0f; }
const uint32_t fe = 0x7fu + e - 0x1fu;
const uint32_t f = (s << 31u) | (fe << 23u) | (m << (23u - 9u));
return u2f(f);
}
int main(){
for(uint64_t i = 0; i < (1ull << 32); i += 256ull){
const auto magic = static_cast<uint32_t>(i);
const auto magicf = u2f(magic);
const auto hi = h2f(magic >> 16u);
const auto lo = h2f(magic & 0xffffu);
const auto mask = f2u(hi + lo) & 0xffffu;
bool fail = false;
for(uint32_t j = 0; j < 256; ++j){
const auto x = u2f(j | magic);
if((f2u(x * magicf - x) & mask) != j % 3){
fail = true;
break;
}
}
if(!fail){
printf("Found: 0x%08x => 0x%08x\n", magic, f2u(hi + lo));
}
}
return 0;
}
Count up (26 → 24 lines)
下図のようなビット列を作って、毎ステップ 1 << 12 を加算しつつ L2BM へ向けて送っていきます。 L2BM のスループットに追いつくには1ステップあたり1サイクル分の出力で十分なので、サイクル方向に増加する列を作らず1サイクル目のみが有効な計算を行うようにすると楽になります。
+------------+-------------+--------+-------------+------------+-----+
| $peid[5:3] | $l1bid[2:1] | $l2bid | $l1bid[0:0] | $peid[2:0] | 0b0 | + [1, 2]
+------------+-------------+--------+-------------+------------+-----+
L2BM や DRAM への転送はチューニングしようがなさそうなのでなんとかして上のビット列生成処理を短くしていきます。
素直に書くと ALU がすぐに詰まってしまうので以下に挙げる処理を他のユニットにオフロードしていきます。
- 定数の生成
- 種になる定数
ui"0xcc0e0006"を最初のimmで用意しておく - 1: 種 (非ゼロの何か) を
l1bmriorに通す - 2:
0xcc0e0000_00000001と表される倍精度浮動小数点数を2乗したものの下位 32 bit-
0xcc0e000は種の上位ビットをマスク付きコピーする -
0x0000001は1を作った時に一緒にコピーしておく
-
- 6: シフト量として使うので種をそのまま使う
-
0x0000cc0e: 種を詰めた半精度浮動小数点数行列を転置して上位ビットをマスクしつつ読む
- 種になる定数
- ビットシフト
- 全 MAB で同じ値を用いる場合
l1bmriiaddを4ビット左シフトとして利用できる
- 全 MAB で同じ値を用いる場合
コンテスト中は packbit 命令の存在を忘れてしまっていて26行で最短タイ、コンテスト後に packbit を使うように修正して24行となりました。PFN解は23行らしいのであと1行。
# step : 3 (12-15)
# peid_hi : 2 (10-12)
# l1bid_hi : 2 (8-10)
# l2bid : 3 (5-8)
# l1bid_lo : 1 (4-5)
# peid_lo : 3 (1-4)
# word : 1 (0-1)
# 0:
# $r[0-5] = 0xcc0e0006
imm ui"0xcc0e0006" $lr0v/1110
# 1:
# ALU: $aluf = $peid << 6
# L1BM: $lbi = 1
# MAU: $omr1 = 0x5555
ilsl $peid $aluf $nowrite ; l1bmrior $aluf $lb0 ; ; hvpassar $aluf $omr1 ; hmwrite $aluf $llx0
# 2:
# ALU: $lt = ($peid << 6) | $peid
# L1BM: $s[0-3] = 1
# $lr4 = 0xcc0e0006_00000001
ior $peid $aluf $lt ; ; l1bmm $lbi $ls0v/1100 $r5 ; ; hmwrite $llr0 $llx8
# 3:
# ALU: $aluf = $l1bid >>> 1
# L1BM: $lbi = 1 << 4
# MAU: $lr4 = 0xcc0e0000_000000001
# $s[4-5] = 0x0000cc0e (peid_mask)
ibsr $l1bid $lbf $nowrite ; l1bmriiadd $lbf $lbi ; ; hvpassar $lm0 $r[4,6,6,6]/$imr1 ; hmread/$imr1 $llx0 $ls4
# 4:
# ALU: $ls8 = $l2bid << 1 | ($l1bid & 1)
# L1BM: $lbi = l1bid_hi << 4
# $lbf = 1 << 4
# MAU: $omr2 = 0x3333
ipackbit $l2bid $aluf $ls8/1000 ; l1bmriiadd $aluf $lbi ; l1bmm $lbi $nowrite ; fvpassa $lr0e $omr2
# 5:
# ALU: $lt = ($peid << 7) | ($peid << 1)
# L1BM: $lbi = 1 << 8
# $lbf = l1bid_hi << 4
# MAU: $mauf = 0x????????_00000002
ipackbit $lt $lm0 $lt ; l1bmriiadd $lbf $lbi ; l1bmm $lbi $nowrite ; dvmulu $lr4 $lr4 $nowrite
# 6:
# ALU: $aluf = (l1bid_hi << 4) | ($l2bid << 1) | l1bid_lo
# L1BM: $r[6-7] = 1 << 8
# MAU: $s3 = 2
ior $ls8 $lbf $nowrite ; ; l1bmm $lbi $lr[6,8,8,8] ; dvfmad $lr4 $lr4 $mauf $ls[2,6,6,6]/$imr2
# 7:
# ALU: $aluf = (($peid << 7) | ($peid << 1)) & peid_mask (= (peid_hi << 10) | (peid_lo << 1))
# L1BM: $lbi = (l1bid_hi << 8) | ($l2bid << 5) | (l1bid_lo << 4)
iand $lt $ls4 $nowrite ; l1bmriiadd $aluf $lbi
# 8:
# ALU: $aluf = ((peid_hi << 10) | (peid_lo << 1)) + word
# L1BM: $lbi = 1 << 12
# $lbf = (l1bid_hi << 8) | ($l2bid << 5) | (l1bid_lo << 4)
iadd $aluf $ls2 $nowrite ; l1bmriiadd $lr6 $lbi ; l1bmm $lbi $nowrite
# 9:
# ALU: $aluf = ((peid_hi << 10) | (l1bid_hi << 8) | ($l2bid << 5) | (l1bid_lo << 4) | (peid_lo << 1)) + word
# L1BM: $lt = 1 << 12
iadd $aluf $lbf $nowrite ; ; l1bmm $lbi $lt
# Write to DRAM
iadd $aluf $lbf $nowrite ; l1bmd $aluf $lb0
iadd $aluf $lt $nowrite ; l1bmd $aluf $lb256
iadd $aluf $lt $nowrite ; l1bmd $aluf $lb512
iadd $aluf $lt $nowrite ; l1bmd $aluf $lb768 ; l2bmd $lb0 $lc0
iadd $aluf $lt $nowrite ; l1bmd $aluf $lb0 ; l2bmd $lb256 $lc256
iadd $aluf $lt $nowrite ; l1bmd $aluf $lb256 ; l2bmd $lb512 $lc512
iadd $aluf $lt $nowrite ; l1bmd $aluf $lb512 ; l2bmd $lb768 $lc768
; l1bmd $aluf $lb768 ; l2bmd $lb0 $lc1024
; l2bmd $lb256 $lc1280
; l2bmd $lb512 $lc1536
; l2bmd $lb768 $lc1792
nop
mvd/n2048 $lc0 $p0@0
mvp/n16384 $p0@0 $d0@0
Transpose MAB (17 → 16 lines, テストケース依存)
以下のような命令列を用いると各 MAB が4行×4列分のデータを持つようにデータをシャッフルすることができます。
lpackbit $subpeid $ls0 $t
l1bmm4@0 $lmt0v8 $lb0
l1bmm4@1 $lmt0v8 $lb64
l1bmm4@2 $lmt0v8 $lb128
l1bmm4@3 $lmt0v8 $lb192
l1bmd $lb0 $lr0v
このとき各 MAB の $mabid/4 を i 、 $mabid%4 を j とすると、シャッフル後の MAB はそれぞれ [j*4, j*4+1, j*4+2, j*4+3] 行目 [i*4, i*4+1, i*4+2, i*4+3] 列目のデータを持っています。最終的に各 MAB が持っていてほしいデータを集めようとすると $mabid/4 が等しい MAB 同士で通信すればよさそうです。以下のように l1bmm4 とその折り返しで全対全交換のようなことができるので、これで各 MAB が欲しいデータを持っている状態を作ることができます。
l1bmm4@0 $lr0v $lbi
l1bmm4@1 $lr0v $lbi ; l1bmm4 $lbi $nowrite # $mabid%4==0 となる MAB からのデータが得られる
l1bmm4@2 $lr0v $lbi ; l1bmm4 $lbi $nowrite # $mabid%4==1 となる MAB からのデータが得られる
l1bmm4@3 $lr0v $lbi ; l1bmm4 $lbi $nowrite # ...
; l1bmm4 $lbi $nowrite # ...
ただし、最終的に欲しいデータは $mabid%4 番目の PE に渡ってくるためそれを PE0 に渡すために行列積を使います。ここでブロックフロート化を挟み仮数部の下位数ビットが落ちるためテストケース依存解となります。 (意図的に作らないとこれが通るような入力にはそうそうならないような気はしますが……)
例のごとく packbit の存在を忘れていたため余分な imm がありコンテスト中は17行、コンテスト後に修正して16行となりました。
lpackbit $subpeid $ls0 $t
imm i"3" $s3/1000
; l1bmm4@0 $lmt0v8 $lb0
land $mabid $ls2 $nowrite ; l1bmm4@1 $lmt0v8 $lb64
lxor $subpeid $aluf $omr1 ; l1bmm4@2 $lmt0v8 $lb128
; l1bmm4@3 $lmt0v8 $lb192
immu/$imr1 ui"0x3ff00000" $nowrite
dbfn $aluf $nowrite
dmwrite $aluf $lx0 ; l1bmd $lb0 $lr0v
l1bmm4@0 $lbf $lbi
l1bmm4@1 $lr0v $lbi ; l1bmm4 $lbi $nowrite
l1bmm4@2 $lr0v $lbi ; l1bmm4 $lbi $nowrite ; dbfn $lbf $nowrite
l1bmm4@3 $lr0v $lbi ; l1bmm4 $lbi $nowrite ; dbfn $lbf $nowrite ; dmmulu $lx $aluf $ln0v
; l1bmm4 $lbi $nowrite ; dbfn $lbf $nowrite ; dmmulu $lx $aluf $ln8v
; dbfn $lbf $nowrite ; dmmulu $lx $aluf $ln16v
; dmmulu $lx $aluf $ln24v
Inversion Small (10 → 9 lines)
公式解説で存在がほのめかされていた9行解ができたのでとりあえず貼っておきます。
もともと packbit およびベースレジスタなしで10行だったため、 tails さんの解を参考にこれらの要素を導入することでコンテスト中から1行削れて9行になりました。
lpackbit $mabid $ls0 $lmb
imm ui"0xbf003f00" $nowrite
lpackbit $subpeid $ls0 $lt ; hvpassa $aluf $lr0v $omr1 ; hmwrite $aluf $lx0
lpassa $lm0 $nowrite
lsub $aluf $lmt4064v8 $r0v/$imr1
imm ui"0x4800fc00" $nowrite
hmfma $lx $llr[4,4,4,0]r $aluf $lls0v
l1bmriiadd $mauf $lb0
l1bmm $lbi $n1/$imr1
Inversion (35 lines)
おそらく最短にたどり着ける方針ではないのですが、部分的には面白い要素もありそうなのでこちらも解説します。
公式解説でも言及がある通り値を比較する回数が多い点が問題になるのですが、値を比較するための sub の回数を減らすために Short としてパッキングしてスループットを倍にする方針を取っています。パッキング結果を使いまわすために各 PE は j 方向に連続する 16 要素と k 方向に連続する 8 要素をそれぞれパッキングしつつ GRF に置いていきます。
k 側のデータは下位半語を上位半語に複製したもので良いため、以下のように生成することができます。
# 2長語アクセスのMSB側長語を16ビットシフトしつつ、LSB側長語をそのままコピー
# シフトされていないMSB側長語はL1BM折り返しレジスタに入れておく
ibsl $llmt0v $lbf $llr16v ; l1bmd $llmt0v $lbi
# MSB側長語のシフトしていない側をシフトしつつコピーした部分に重ねる
; l1bmd $lbi $lr16v4/$imr2
# LSB側長語をシフトしつつすでにコピーした部分に重ねる
ibsl $lr18v4 $ls0 $lr18v4/$imr1
j 側のデータは上位下位で異なる要素に由来する値を持っており、4つの長語を取ってきたときに8つ分の連続したデータが得られるように並んでいる必要があります。
ここでは積極的に2長語アクセスを用いたいのですがその場合は要素の並びが若干きれいではなくなります。例えば k が [8, 15] の範囲、 j が [0, 15] の範囲を取るとき、以下のようにコピー・シフトを行うと、各 k について k もしくは k-1 を最後の要素とする連続した8要素を得ることができます。
# +----+----+----+----+----+----+----+----+----+
# LSB | 0 | 1 | 4 | 5 | 8 | 9 | 12 | 13 | |
# +----+----+----+----+----+----+----+----+----+
# MSB | | | | | | | | | |
# +----+----+----+----+----+----+----+----+----+
lpassa $llmt3968v8 $lls16v
# +----+----+----+----+----+----+----+----+----+
# LSB | 0 | 1 | 4 | 5 | 8 | 9 | 12 | 13 | |
# +----+----+----+----+----+----+----+----+----+
# MSB | | 2 | 3 | 6 | 7 | | | | |
# +----+----+----+----+----+----+----+----+----+
ibsl $lmt[3972,3974,3980,3982] $lbf $ls18v/$imr1
# +----+----+----+----+----+----+----+----+----+
# LSB | 0 | 1 | 4 | 5 | 8 | 9 | 12 | 13 | |
# +----+----+----+----+----+----+----+----+----+
# MSB | | 2 | 3 | 6 | 7 | 10 | 11 | 14 | 15 |
# +----+----+----+----+----+----+----+----+----+
ibsl $lmt[3988,3990,3996,3998] $lr0 $ls26v/$imr1
これで ALU 処理5ステップ分でデータのパッキングが完了しました。
あとは比較結果を MAU で累積していけば OK です。ここで、ワード方向のSIMDの結果である2つの要素を縮約しながら累積していきたいため行列積を使うことになります。このとき下図のように対角線上の4x4ブロックのみがそれぞれ同じ値を持ち残りは0となるような行列を作りたいのですが、これは MADPE を使うと MAU のみで作ることができます。
2^-4 2^-4 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2^-4 2^-4 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2^-4 2^-4 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2^-4 2^-4 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 2^-4 2^-4 0 0 0 0 0 0 0 0 0 0
0 0 0 0 2^-4 2^-4 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2^-4 2^-4 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2^-4 2^-4 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 2^-4 2^-4 0 0 0 0 0 0
0 0 0 0 0 0 0 0 2^-4 2^-4 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 2^-4 2^-4 0 0 0 0
0 0 0 0 0 0 0 0 0 0 2^-4 2^-4 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 2^-4 2^-4 0 0
0 0 0 0 0 0 0 0 0 0 0 0 2^-4 2^-4 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 2^-4 2^-4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 2^-4 2^-4
hvpassar $ln[8,8,12,12]j0 $nowrite
hvaddr $ln[8,8,12,12]j1 -$maufe $nowrite ; hmwrite $mauf $ly0
hvpassar $ln[10,10,14,14]j2 $nowrite ; hmwrite $mauf $ly4
hvaddr $ln[10,10,14,14]j1 -$maufe $nowrite ; hmwrite $mauf $ly12
; hmwrite $mauf $ly8
ここまでのパーツを組み合わせると以下のようになり、35行となりました。
imm ui"0x37009004" $llr4/ll1000
llsl $l2bid $aluf $lt ; hvpassar $aluf $omr1 ; hmwrite $aluf $llx0 ; l1bmr4iiadd $aluf $lb0
llsl $l1bid $llr4 $lr2/1000 ; hvpassar -$llr4 $omr2 ; hmwrite $llr4 $llx8 ; l1bmm4 $lbi $ls0/1000
ibsl $llmt0v $lbf $llr16v ; hmread $llx0 $n[10,15,32,32] ; l1bmd $llmt0v $lbi
ladd $lt $lr2 $lt ; hmread $llx0 $lls[4,8,8,8] ; l1bmd $lbi $lr16v4/$imr2
ibsl $lr18v4 $ls0 $lr18v4/$imr1
lpassa $llmt3968v8 $lls16v ; hvpassar $ln[8,8,12,12]j0 $nowrite ; l1bmm4 $lb0 $lr0/1000
ibsl $lmt[3972,3974,3980,3982] $lbf $ls18v/$imr1 ; hvaddr $ln[8,8,12,12]j1 -$maufe $nowrite ; hmwrite $mauf $ly0 ; l1bmd $ls4 $lb0
ibsl $lmt[3988,3990,3996,3998] $lr0 $ls26v/$imr1 ; hvpassar $ln[10,10,14,14]j2 $nowrite ; hmwrite $mauf $ly4 ; l1bmr4siadd $ls6 $lbi
ssub $lr16 $ls18v $omr3 ; hvaddr $ln[10,10,14,14]j1 -$maufe $nowrite ; hmwrite $mauf $ly12 ; l1bmm4 $lbi $lt
ssub $lr18 $ls18v $omr3 ; l1bmd/$imr3 $lb0 $nowrite ; hmwrite $mauf $ly8
ssub $lr20 $ls20v $omr3 ; l1bmd/$imr3 $lb0 $nowrite ; hmfmar $ly -$lbf $lte $nowrite
ssub $lr22 $ls20v $omr3 ; l1bmd/$imr3 $lb0 $nowrite ; hmfmar $ly -$lbf $maufe $nowrite
ssub $lr24 $ls22v $omr3 ; l1bmd/$imr3 $lb0 $nowrite ; hmfmar $ly -$lbf $maufe $nowrite
ssub $lr26 $ls22v $omr3 ; l1bmd/$imr3 $lb0 $nowrite ; hmfmar $ly -$lbf $maufe $nowrite
ssub $lr28 $ls24v $omr3 ; l1bmd/$imr3 $lb0 $nowrite ; hmfmar $ly -$lbf $maufe $nowrite
ssub $lr30 $ls24v $omr3 ; l1bmd/$imr3 $lb0 $nowrite ; hmfmar $ly -$lbf $maufe $nowrite
; l1bmd/$imr3 $lb0 $nowrite ; hmfmar $ly -$lbf $maufe $nowrite
; hmfmar $ly -$lbf $maufe $lr32v
sadd $mauf $lr26v $nowrite
sadd $aluf $lr28v $nowrite
sadd $aluf $lr30v $ls32v
l1bmd $aluf $lb0
nop
nop
nop
l2bmriiadd $lb192 $lc0
nop
mvriiadd/n64 $lc0 $d0
mvb/n64 $d0 $lc0
nop
nop
l2bmb $lc0 $lb192
nop
l1bmd $lb0 $ln0/$imr2