2026-06-15

MN-Core2 MAB間1024要素ソート

概要

前回の記事では、PE内で64要素をソートするコードについて説明しました。

今回は、さらに、L1B内のMAB間方向に16個のPEを使い、1024要素を降順ソートしてみます。

制約

型や入力については前回と同じです。出力は、同じ場所($ln[0:128])ながら、最大の64要素をMAB0, 次に大きい64要素をMAB1, ... 最小の64要素をMAB15に書き込みます。これが実際使いやすいかどうかは不明です。なお、入力を含め、実行前にメモリにあるあちこちの値を破壊してしまっているので、ご注意ください。

MAB内のPE4つの間ではソートは行っていませんが、それぞれ独立にMAB間方向でソートできるように書いているので、L1Bごとに、1024要素のソートを並列で4つできることになります。本記事では、各MAB内にPEが1つずつしかないかのような書き方をしていますが、話を簡単にするためだとご理解ください。

コード

840行と、ブログに貼るには難がある分量になってしまったので、GitHubに貼りました。

説明

コードを大まかな19段のPhaseに分けました。全体の構造としてはマージソートですが、マージ方法を工夫しています。

1要素→64要素

Phase 1, 2

入力をGRFにコピーし、ソートします。PE内で64要素をソートしており、この部分は前回の記事のコードとほぼ同じです。

64要素→128要素

MAB0と1, 2と3, 4と5というように、2つずつマージします。それぞれが64要素を持っているので、結果は128要素になります。ここではまだ、Sorting Networkですべてのソートをします。

Phase 3

各MAB内のソート済みの配列の中で、(0-indexで)偶数番の要素を偶数番のMABに、奇数番の要素を奇数番のMABに分配します。これができるのが、Odd-Even mergesortの強みです。

Phase 4

Phase 2と同じコードでソートします。

Phase 5, 6

奇数番のMABから偶数番のMABに64要素を送り、偶数番のMABで隣接要素間をソートして、128要素のソートを完成させます。残念ながら、奇数番のMABは意味のある計算をしていません。

128要素→256要素

MABを4つずつ4グループに分けて、256要素のソートをします。二分探索を用いて、マージに必要な行数を減らしています。詳しくは後で説明します。

Phase 7

偶数番のMABから、4つのMABに放送します。各PEでは、128要素からなるソート済み配列がAとBの2本、$lm[2:258]と$lm[262:518]に配置されます。転送スループットを上げるため、無理やり2長語にまとめているので、お目汚しもいいところという感じです。

Phase 8

二分探索により、256要素のうち、最大の16要素、最大の32要素、...、最大の256要素(つまり全部)が、Aのいくつの要素を含むかを求めます。これをΣとします。

Phase 9

256要素を大きい方から16要素ごとに区切った、16本の未ソートの小配列を得ます。各PEは64要素を処理するので、サイクル方向に4本の小配列を並べて扱うと無駄がありません。 Phase 8で求めた配列Σを後ろに1つずらしてΣから引きます。すると、小配列内に、Aからいくつの要素が入るか( a個とします)を求めることができます。 Bからは 16 - a 個取ってくればいいので、AとBのどの位置からいくつの要素を取ってくればいいかわかります。

読み出しの手順は以下のようになっています。

Aのうち、値が小さい方*1から大きい方に向けて8要素を取得し、配列Pに順方向で書き込む。
a≤8 ならB、a>8 ならAを選ぶ。値が大きい方から8要素を取得し、配列Qに順方向で書き込む。
a=16 なら8要素、そうでなければ (16 - a)%8 要素を、Bの値が小さい方から取得し、配列Pに逆方向で書き込む。

Phase 10

Phase 9で取得した小配列の16要素をソートします。小配列を16本繋げて読めばソート済み256要素の配列になります。

さて、配列PはAから来た要素とBから来た要素が逆方向から書き込まれたので、仮に値をプロット表示したとすると、∧ という形をしているはずです。なお、値が同じで踊り場ができる場合や、／とか＼という形になる場合も考えられますが、今回の議論を妨げるものではありません。

このような形の数列は、前回も使わせて頂いたBatcherのレポートにあるとおり、Bitonic の要件を満たします。レポートによれば、Bitonic の要件はもうちょっと緩い*2そうですが、今回そのことを利用することはできませんでした。

ともかく、Bitonic な列を Monotonic 、今回の場合は広義単調減少にするのには、Bitonic Sort が使えます。8要素では、Odd-Even Mergesortが比較スワップを19回必要とするのに対し、Bitonic Sortにすれば12回で済みます。これで配列Pがソートできました。

配列Qはすでにソート済みです。ただし、一般にPの要素との順序は示せないので、PとQのマージにはおとなしくOdd-Even Mergesortを使います。

256要素→512要素

8個のMAB間で512要素のソートをします。値を放送するのに、l1bmd+8を使って双方向に値を転送したいので、少し変則的にはなりますが、

MAB 0, 1, 2, 3, 8, 9, 10, 11
MAB 4, 5, 6, 7, 12, 13, 14, 15

の2群に分けます。

Phase 11

4個のMAB間で値を放送したのち、l1bmd+8で郡内に共有します。

Phase 12

Phase 8と同じことですが、配列の長さが倍になっているので、1回多く繰り返す必要があります。

Phase 13, 14

Phase 9, 10とほぼ同じです。群の分け方のせいで、Σを後ろに1つずらすのに、l1bmd+1とl1bmd+5が混在しています。

512要素→1024要素

Phase 15, 16, 17, 18が含まれますが、新しいことは何もないので、省略します。

このあとPhase 19で答えをLM1に書き込んで終了です。

二分探索

Phase 8の説明で後回しにした二分探索について説明します。Phase 12, 16でも、回数を増やして同じことをしていますが、以下の説明では、Phase 8を前提とした数値を使います。

初期値

二分探索を始める前に、初期値を設定します。実際のコードでは、転送にやたらと行数が必要なので、暇を持て余しているALUやMAUなどにのんびり計算させています。

記号	メモリ上の位置	計算式	備考
M	`$lr80v`	`($mabid&3)32 + $cycle8 + 8`	L≤M<U
L	`$ls80v`	`max(0, M*2 - 128)`
U	`$ls88v`	`min(M*2 + 1, 129)`
C	`$lr88v`	`M*4 + 261`
1	`$ln0`	定数`0x0000-0000-0000-0001`
S_max	`$lm0`	定数`0x7FFF-FFFF-FFFF-FFFF`	番兵
S_min	`$lm518`	定数`0xFFFF-FFFF-FFFF-FFFF`	番兵

$cycleは、サイクル方向に0, 1, 2, 3となる定数のことです。

S_maxはAの最初の要素の1つ前、S_minはBの最後の要素の次に配置されます。

また、M, L, Uの値は、長語の最下位の半語に入り、その上の半語には、0x3F80を書き込んでおきます。上位の単語の値はなんでも構いません。

繰り返し

求めたいのは、AとBを合わせた256要素から最大のN要素を取り出したとき、そのなかにAから来た要素がいくつ含まれるか、ということでした。最終的にMがその個数になるように、可能性のある範囲を絞りこんでいきます。 L≤M<Uという関係は常に成り立ちますが、これがL=M, U=M+1となれば、個数を特定できたことになります。

Python風に書くと、繰り返しは以下のようになります。なお、AとBは、メモリ配置の関係で、1-indexになっています。私の頭がそうであるわけではありません。また、サイクル方向の並列処理は無視しています。

for i in range(8):
    if A[M[i]] >= B[N-M[i]+1]:
        L[i+1] = M[i]
        M[i+1] = floor((M[i] + U[i]) / 2)
        U[i+1] = U[i]
    else:
        L[i+1] = L[i]
        M[i+1] = floor((M[i] + L[i]) / 2)
        U[i+1] = M[i]

このうち1回をVSMに書き直すと、以下のようになります。

isub $lr88v $t $t; l1bmd+0 $lmt0 $lbi
l1bmd $lbi $nowrite
dmax $lbf $lmt2 $omr1; fvmul $lr80v $ls80v $t; l1bmd+0 $lr80v $lbi
slsr $mauf $ln0 $lr80v; fvmul $lr80v $ls88v $t/$imr1; l1bmd+0 $lr80v $lbi; l1bmd $lbi $ls80v/$imr1
slsr $mauf $ln0 $lr80v/$imr1; l1bmd+0 $ls88v $lbi; l1bmd $lbi $ls88v
l1bmd $lbi $ls88v/$imr1

開始時点で$tの最下位の半語には、M*2が*3 入っています。従って、1行目・2行目では、A[M[i]]を読み出し、$tにC - M[i]を書き込んでいます。LM0上で、C - M[i] + 2は、B[N - M[i] + 1]のアドレスと等しく解釈されます*4。

3行目では、ALUがA[M[i]]とB[N-M[i]+1]の比較を行い、MAUはM[i] + L[i]の計算をします。M[i] + L[i]は、M[i+1] * 2の候補なので、$tに書き込んでおきます。

4行目では、ALUがM[i] + L[i]からfloor((M[i] + L[i]) / 2)を計算し、暫定的にM[i+1]の値としておきます。なお、0x3F80の部分はシフトされると困るので、ilsr命令ではなくslsr命令とすることで、最下位の半語のみがシフトされるようにしています。MAUはM[i] + U[i]を計算し、比較の結果に応じて、$t(≒M[i+1] * 2)を上書きします。$lbi→PEの折り返し転送では、L[i+1]を、同様に比較の結果に応じて、M[i]とします。

5行目では、ALUがfloor((M[i] + U[i]) / 2)を条件が真ならM[i+1]に書き込みます。$lbi→PEの折り返し転送では、U[i+1]にM[i]を代入します。これは条件が偽だった場合のみすべきことなので、真なら6行目で元のU[i]を書き戻すことになります。

MAUによる整数加算

M[i] + L[i]とM[i] + U[i]は、MAUによって計算していますが、これは今回必要な値が小さいからできることです。具体的には、fvmul命令を用いて、(1 + α)(1 + β) = 1 + (α + β) + αβを計算し、α + βの部分のみが最下位の半語に現れるようにしています。αβは十分に小さいので、なかったことにできます*5。

fvadd命令では、答えが2 + (α + β)となってしまい、浮動小数点数の表現方法から、α + βの部分が下位に1ビットシフトされてしまいます。それだけなら実際この後計算していることなのでよいのですが、このシフトで追い出された1ビットが1だった場合、丸めが悪さをして、求めたい答えと異なる値になってしまうことがあります。また、加算するたびに上位の半語にある指数が変化してしまうのも不便なので、今回のような用途には使えません。

評価・展望

二分探索を利用して、多要素のマージを細かい問題に切り分けることができました。真面目に計算していないのですが、全部Sorting Networkで書いた場合に比べて、少なくとも100行程度は削れているはずです。

前回今回とDouble型でやってきましたが、単語長型はともかく、半語長型のソートでは、Sorting Networkのようにスループットを上げることができず、二分探索を含め、間接参照を使う方法は不利になるかもしれません。

*1:降順なので後ろの方

*2:∨という形でもBitonic。また、Bitonicな列を任意の位置で2本の部分列に切って、それぞれの部分列の向きを変えずに順番を入れ替えた列もまたBitonic。例えば、4321がBitonicなら、43/21と切って、2143としてもBitonic性を失わないらしいです。

*3:もしくは M*2 + 1 が

*4:長語アクセスの際、アドレスの最下位ビットが切り捨てられる動作を利用しています。

*5:マニュアルによれば、MN-Core2では、このうち最下位の数ビットは本当に計算していないらしいですが、今回は関係ありません。

2026-06-05

MN-Core2 PE内64要素ソート

概要

MN-Core2でソートを行うコードの需要が存在しうるということを風の噂で聞いたので、最短の方法を探しています。足掛かりとして、各PE内でdouble型の64要素をソートしてみました。

制約

霞から取り出したものなので、他のものも考えるつもりではいます。

入出力

LM0の入力をソートし、LM1に降順で出力 $lm[0:128] → $ln[0:128] 値のみをソートし、キー(連想配列)などは気にしない。

比較・転送

ALUのdmax, dminの両命令を使用して比較、与えられた各要素のビット列は変更しない。

dmax, dminは、±∞やNaNを下位ビットで区別してくれます。一方で、非正規化数の範囲と±0とは全て同一の値として扱われます。この性質上、キーがなくても安定ソートかどうかで結果が変わりうるのですが、今回は気にしないことにします。 MAUのdvaddを使って比較することもできるのですが、正規化数同士の比較でも、差が非正規化数になって失敗しうること、NaNを∞と同様に扱ってしまうことなど、ALU命令に比してもさらに緩いので、今回は使いません。

Sorting Network

ソートアルゴリズムにもいろいろありますが、MN-Coreは普通のCPUなんかと勝手が違うので、特性を把握したうえで相性のよいものを選びます。 128要素以上についてはまた記事を改めますが、64要素以下ではSorting Networkが最も優秀であると思います。

Sorting Networkの中にも種類がありますが、性能と、他のアルゴリズムと接ぐのに都合がよいことから、Batcher Odd-Even Merge Sortを使うことにしました。以下その前提で話を進めます。

Batcherのレポート

余談ですが、このレポート面白いので、お時間があれば読んでみてください。58年前のコンピュータにおける優先順位がよく表れていると思います。特に、値をMSBからシリアルに流して、比較を行わせるというアイデアは、言われてみれば納得なのですが、まだまだ回路が高価だった時代を偲ばせます。1ビット進めるのに40nsらしいですが、1968年のECLはもう少し速くできるはずなので、安めのものか、TTL以前の回路のことかと思います。

構造

骨格はマージソートと同じで、短いソート済み列を繋げて伸ばしていきます。ただし、マージを行うのに、先頭から1つずつ選択していく教科書の方法では、計算回数が少なくても並列性がなく、スループットが出ません。今回のコードはPE内のみですが、MN-Coreはその高い計算能力に比べて間接参照能力が貧弱なので、多少効率が悪くても多数の命令を発行したほうが早く終わります。具体的には、ちょうどいい位置の値を比較して、必要ならスワップする、ということを繰り返していると、なぜか要素がソートされます。これがSorting Networkです。各比較とスワップは、決まったアドレスの値を参照するだけなので、間接参照を必要としません。「いい位置」とはなんなのか、言葉で説明するよりも図を見てもらったほうが早いと思います。便利なサイトがあったので、借ります。6を入力して実行すると、今回求めたいグラフが得られます。左側に64個の入力が並んでおり、右側に向けてあみだくじの要領で進みます。この際、縦の辺が分岐していたら、あみだくじのように問答無用で渡るのではなく、その辺の上下の頂点にそれぞれ左側から来た値を比較スワップし、さらに右に流していきます。このサイトに6でなくてもっと小さい値を入れると、小問題に対するグラフを出してくれます。64要素のグラフも、左側に1→2→4→8→16とマージする小問題があるのがわかるでしょう。

スワップ

スループットをあげるため、比較は1回で済むなら1回で済ませたいです。以下のコードで、$ls0vと$lr8vの間で、実質的に1行に4回の比較スワップを行えます。

dmax $ls0v $lr8v $lr8v $omr1; l1bmd+0 $lr8v $lbi
l1bmd $lbi $ls0v/$imr1

$lr8vに両者のうち大きい値が書き込まれますが、$lr8vが選ばれた場合、何もしないでそのままにしておきます。$ls0vの値が選ばれるときは、スワップをしなくてはいけないので、マスクを利用して条件付き書き込みを行っています。

レジスタ

この方式で問題となることの一つは、1サイクルの中で同一レジスタの違うアドレスから値を読み出すことはできないため、レジスタに対する値の配置をうまく調整する必要があることです。今回は叩き台なので、紙にグラフを描いてフィーリングでやりました。数式で表せないとスケールしないので、今後の課題です。

コード

dpassa $llm0v $llr0v
dpassa $llm16v $llr16v
dpassa $llm32v $llr32v
dpassa $llm48v $llr48v
dpassa $llm64v $lls0v
dpassa $llm80v $lls16v
dpassa $llm96v $lls32v
dpassa $llm112v $lls48v
dmax $ls[0,6,10,12] $lr[0,6,10,12] $lr[0,6,10,12] $omr1; l1bmd+0 $lr[0,6,10,12] $lbi
dmin $ls[2,4,8,14] $lr[2,4,8,14] $lr[2,4,8,14] $omr2; l1bmd+0 $lr[2,4,8,14] $lbi; l1bmd $lbi $ls[0,6,10,12]/$imr1
dmin $ls[16,22,26,28] $lr[16,22,26,28] $lr[16,22,26,28] $omr1; l1bmd+0 $lr[16,22,26,28] $lbi; l1bmd $lbi $ls[2,4,8,14]/$imr2
dmax $ls[18,20,24,30] $lr[18,20,24,30] $lr[18,20,24,30] $omr2; l1bmd+0 $lr[18,20,24,30] $lbi; l1bmd $lbi $ls[16,22,26,28]/$imr1
dmin $ls[32,38,42,44] $lr[32,38,42,44] $lr[32,38,42,44] $omr1; l1bmd+0 $lr[32,38,42,44] $lbi; l1bmd $lbi $ls[18,20,24,30]/$imr2
dmax $ls[34,36,40,46] $lr[34,36,40,46] $lr[34,36,40,46] $omr2; l1bmd+0 $lr[34,36,40,46] $lbi; l1bmd $lbi $ls[32,38,42,44]/$imr1
dmax $ls[48,54,58,60] $lr[48,54,58,60] $lr[48,54,58,60] $omr1; l1bmd+0 $lr[48,54,58,60] $lbi; l1bmd $lbi $ls[34,36,40,46]/$imr2
dmin $ls[50,52,56,62] $lr[50,52,56,62] $lr[50,52,56,62] $omr2; l1bmd+0 $lr[50,52,56,62] $lbi; l1bmd $lbi $ls[48,54,58,60]/$imr1
dmin $ls[4,6,8,10] $lr[6,4,10,8] $lr[6,4,10,8] $omr1; l1bmd+0 $lr[6,4,10,8] $lbi; l1bmd $lbi $ls[50,52,56,62]/$imr2
dmax $ls[2,0,14,12] $lr[0,2,12,14] $lr[0,2,12,14] $omr2; l1bmd+0 $lr[0,2,12,14] $lbi; l1bmd $lbi $ls[4,6,8,10]/$imr1
dmax $ls[22,20,26,24] $lr[20,22,24,26] $lr[20,22,24,26] $omr1; l1bmd+0 $lr[20,22,24,26] $lbi; l1bmd $lbi $ls[2,0,14,12]/$imr2
dmin $ls[16,18,28,30] $lr[18,16,30,28] $lr[18,16,30,28] $omr2; l1bmd+0 $lr[18,16,30,28] $lbi; l1bmd $lbi $ls[22,20,26,24]/$imr1
dmax $ls[38,36,42,40] $lr[36,38,40,42] $lr[36,38,40,42] $omr1; l1bmd+0 $lr[36,38,40,42] $lbi; l1bmd $lbi $ls[16,18,28,30]/$imr2
dmin $ls[32,34,44,46] $lr[34,32,46,44] $lr[34,32,46,44] $omr2; l1bmd+0 $lr[34,32,46,44] $lbi; l1bmd $lbi $ls[38,36,42,40]/$imr1
dmin $ls[52,54,56,58] $lr[54,52,58,56] $lr[54,52,58,56] $omr1; l1bmd+0 $lr[54,52,58,56] $lbi; l1bmd $lbi $ls[32,34,44,46]/$imr2
dmax $ls[50,48,62,60] $lr[48,50,60,62] $lr[48,50,60,62] $omr2; l1bmd+0 $lr[48,50,60,62] $lbi; l1bmd $lbi $ls[52,54,56,58]/$imr1
dmin $ls[2,14,22,26] $lr[2,14,22,26] $lr[2,14,22,26] $omr1; l1bmd+0 $lr[2,14,22,26] $lbi; l1bmd $lbi $ls[50,48,62,60]/$imr2
dmax $ls[6,10,18,30] $lr[6,10,18,30] $lr[6,10,18,30] $omr2; l1bmd+0 $lr[6,10,18,30] $lbi; l1bmd $lbi $ls[2,14,22,26]/$imr1
dmax $ls[34,46,54,58] $lr[34,46,54,58] $lr[34,46,54,58] $omr1; l1bmd+0 $lr[34,46,54,58] $lbi; l1bmd $lbi $ls[6,10,18,30]/$imr2
dmin $ls[38,42,50,62] $lr[38,42,50,62] $lr[38,42,50,62] $omr2; l1bmd+0 $lr[38,42,50,62] $lbi; l1bmd $lbi $ls[34,46,54,58]/$imr1
dmax $ls[4,2,6,0] $lr[0,6,2,4] $lr[0,6,2,4] $omr1; l1bmd+0 $lr[0,6,2,4] $lbi; l1bmd $lbi $ls[38,42,50,62]/$imr2
dmin $ls[8,14,10,12] $lr[12,10,14,8] $lr[12,10,14,8] $omr2; l1bmd+0 $lr[12,10,14,8] $lbi; l1bmd $lbi $ls[4,2,6,0]/$imr1
dmin $ls[16,22,18,20] $lr[20,18,22,16] $lr[20,18,22,16] $omr1; l1bmd+0 $lr[20,18,22,16] $lbi; l1bmd $lbi $ls[8,14,10,12]/$imr2
dmax $ls[28,26,30,24] $lr[24,30,26,28] $lr[24,30,26,28] $omr2; l1bmd+0 $lr[24,30,26,28] $lbi; l1bmd $lbi $ls[16,22,18,20]/$imr1
dmin $ls[32,38,34,36] $lr[36,34,38,32] $lr[36,34,38,32] $omr1; l1bmd+0 $lr[36,34,38,32] $lbi; l1bmd $lbi $ls[28,26,30,24]/$imr2
dmax $ls[44,42,46,40] $lr[40,46,42,44] $lr[40,46,42,44] $omr2; l1bmd+0 $lr[40,46,42,44] $lbi; l1bmd $lbi $ls[32,38,34,36]/$imr1
dmax $ls[52,50,54,48] $lr[48,54,50,52] $lr[48,54,50,52] $omr1; l1bmd+0 $lr[48,54,50,52] $lbi; l1bmd $lbi $ls[44,42,46,40]/$imr2
dmin $ls[56,62,58,60] $lr[60,58,62,56] $lr[60,58,62,56] $omr2; l1bmd+0 $lr[60,58,62,56] $lbi; l1bmd $lbi $ls[52,50,54,48]/$imr1
dmax $ls[10,12,18,20] $lr[12,10,20,18] $lr[12,10,20,18] $omr1; l1bmd+0 $lr[12,10,20,18] $lbi; l1bmd $lbi $ls[56,62,58,60]/$imr2
dmin $ls[4,2,28,26] $lr[2,4,26,28] $lr[2,4,26,28] $omr2; l1bmd+0 $lr[2,4,26,28] $lbi; l1bmd $lbi $ls[10,12,18,20]/$imr1
dmin $ls[44,42,52,50] $lr[42,44,50,52] $lr[42,44,50,52] $omr1; l1bmd+0 $lr[42,44,50,52] $lbi; l1bmd $lbi $ls[4,2,28,26]/$imr2
dmax $ls[34,36,58,60] $lr[36,34,60,58] $lr[36,34,60,58] $omr2; l1bmd+0 $lr[36,34,60,58] $lbi; l1bmd $lbi $ls[44,42,52,50]/$imr1
dmax $ls[14,10,12,22] $lr[12,10,14,20] $lr[12,10,14,20] $omr1; l1bmd+0 $lr[12,10,14,20] $lbi; l1bmd $lbi $ls[34,36,58,60]/$imr2
dmin $ls[4,2,6,28] $lr[6,2,4,30] $lr[6,2,4,30] $omr2; l1bmd+0 $lr[6,2,4,30] $lbi; l1bmd $lbi $ls[14,10,12,22]/$imr1
dmax $ls[18,20,38,34] $lr[18,22,36,34] $lr[18,22,36,34] $omr1; l1bmd+0 $lr[18,22,36,34] $lbi; l1bmd $lbi $ls[4,2,6,28]/$imr2
dmin $ls[26,30,44,42] $lr[26,28,46,42] $lr[26,28,46,42] $omr2; l1bmd+0 $lr[26,28,46,42] $lbi; l1bmd $lbi $ls[18,20,38,34]/$imr1
dmin $ls[46,52,50,54] $lr[44,54,50,52] $lr[44,54,50,52] $omr1; l1bmd+0 $lr[44,54,50,52] $lbi; l1bmd $lbi $ls[26,30,44,42]/$imr2
dmax $ls[36,62,58,60] $lr[38,60,58,62] $lr[38,60,58,62] $omr2; l1bmd+0 $lr[38,60,58,62] $lbi; l1bmd $lbi $ls[46,52,50,54]/$imr1
dmax $ls[8,4,14,2] $lr[0,12,6,10] $lr[0,12,6,10] $omr1; l1bmd+0 $lr[0,12,6,10] $lbi; l1bmd $lbi $ls[36,62,58,60]/$imr2
dmax $ls[10,6,12,0] $lr[2,14,4,8] $lr[2,14,4,8] $omr2; l1bmd+0 $lr[2,14,4,8] $lbi; l1bmd $lbi $ls[8,4,14,2]/$imr1
dmin $ls[16,28,22,26] $lr[24,20,30,18] $lr[24,20,30,18] $omr1; l1bmd+0 $lr[24,20,30,18] $lbi; l1bmd $lbi $ls[10,6,12,0]/$imr2
dmin $ls[18,30,20,24] $lr[26,22,28,16] $lr[26,22,28,16] $omr2; l1bmd+0 $lr[26,22,28,16] $lbi; l1bmd $lbi $ls[16,28,22,26]/$imr1
dmin $ls[32,44,38,42] $lr[40,36,46,34] $lr[40,36,46,34] $omr1; l1bmd+0 $lr[40,36,46,34] $lbi; l1bmd $lbi $ls[18,30,20,24]/$imr2
dmin $ls[34,46,36,40] $lr[42,38,44,32] $lr[42,38,44,32] $omr2; l1bmd+0 $lr[42,38,44,32] $lbi; l1bmd $lbi $ls[32,44,38,42]/$imr1
dmax $ls[56,52,62,50] $lr[48,60,54,58] $lr[48,60,54,58] $omr1; l1bmd+0 $lr[48,60,54,58] $lbi; l1bmd $lbi $ls[34,46,36,40]/$imr2
dmax $ls[58,54,60,48] $lr[50,62,52,56] $lr[50,62,52,56] $omr2; l1bmd+0 $lr[50,62,52,56] $lbi; l1bmd $lbi $ls[56,52,62,50]/$imr1
dmin $ls[8,4,14,2] $lr[2,14,4,8] $lr[2,14,4,8] $omr1; l1bmd+0 $lr[2,14,4,8] $lbi; l1bmd $lbi $ls[58,54,60,48]/$imr2
dmax $ls[18,30,20,24] $lr[24,20,30,18] $lr[24,20,30,18] $omr2; l1bmd+0 $lr[24,20,30,18] $lbi; l1bmd $lbi $ls[8,4,14,2]/$imr1
dmax $ls[34,46,36,40] $lr[40,36,46,34] $lr[40,36,46,34] $omr1; l1bmd+0 $lr[40,36,46,34] $lbi; l1bmd $lbi $ls[18,30,20,24]/$imr2
dmin $ls[56,52,62,50] $lr[50,62,52,56] $lr[50,62,52,56] $omr2; l1bmd+0 $lr[50,62,52,56] $lbi; l1bmd $lbi $ls[34,46,36,40]/$imr1
dmin $ls[8,4,14,2] $lr[6,10,2,14] $lr[6,10,2,14] $omr1; l1bmd+0 $lr[6,10,2,14] $lbi; l1bmd $lbi $ls[56,52,62,50]/$imr2
dmax $ls[22,26,18,30] $lr[24,20,30,18] $lr[24,20,30,18] $omr2; l1bmd+0 $lr[24,20,30,18] $lbi; l1bmd $lbi $ls[8,4,14,2]/$imr1
dmax $ls[20,24,38,42] $lr[26,22,40,36] $lr[26,22,40,36] $omr1; l1bmd+0 $lr[26,22,40,36] $lbi; l1bmd $lbi $ls[22,26,18,30]/$imr2
dmax $ls[34,46,36,40] $lr[46,34,42,38] $lr[46,34,42,38] $omr2; l1bmd+0 $lr[46,34,42,38] $lbi; l1bmd $lbi $ls[20,24,38,42]/$imr1
dmin $ls[10,6,56,52] $lr[4,8,54,58] $lr[4,8,54,58] $omr1; l1bmd+0 $lr[4,8,54,58] $lbi; l1bmd $lbi $ls[34,46,36,40]/$imr2
dmin $ls[62,50,58,54] $lr[50,62,52,56] $lr[50,62,52,56] $omr2; l1bmd+0 $lr[50,62,52,56] $lbi; l1bmd $lbi $ls[10,6,56,52]/$imr1
dmin $ls[8,4,14,2] $lr[12,6,10,2] $lr[12,6,10,2] $omr1; l1bmd+0 $lr[12,6,10,2] $lbi; l1bmd $lbi $ls[62,50,58,54]/$imr2
dmax $ls[28,22,26,18] $lr[24,20,30,18] $lr[24,20,30,18] $omr2; l1bmd+0 $lr[24,20,30,18] $lbi; l1bmd $lbi $ls[8,4,14,2]/$imr1
dmax $ls[30,20,24,44] $lr[26,22,28,40] $lr[26,22,28,40] $omr1; l1bmd+0 $lr[26,22,28,40] $lbi; l1bmd $lbi $ls[28,22,26,18]/$imr2
dmax $ls[38,42,34,46] $lr[36,46,34,42] $lr[36,46,34,42] $omr2; l1bmd+0 $lr[36,46,34,42] $lbi; l1bmd $lbi $ls[30,20,24,44]/$imr1
dmin $ls[10,6,12,56] $lr[14,4,8,60] $lr[14,4,8,60] $omr1; l1bmd+0 $lr[14,4,8,60] $lbi; l1bmd $lbi $ls[38,42,34,46]/$imr2
dmin $ls[52,62,50,58] $lr[54,58,50,62] $lr[54,58,50,62] $omr2; l1bmd+0 $lr[54,58,50,62] $lbi; l1bmd $lbi $ls[10,6,12,56]/$imr1
dmax $ls[36,40,16,8] $lr[38,44,0,24] $lr[38,44,0,24] $omr1; l1bmd+0 $lr[38,44,0,24] $lbi; l1bmd $lbi $ls[52,62,50,58]/$imr2
dmax $ls[28,4,22,14] $lr[12,20,6,30] $lr[12,20,6,30] $omr2; l1bmd+0 $lr[12,20,6,30] $lbi; l1bmd $lbi $ls[36,40,16,8]/$imr1
dmax $ls[26,2,18,10] $lr[10,18,2,26] $lr[10,18,2,26] $omr1; l1bmd+0 $lr[10,18,2,26] $lbi; l1bmd $lbi $ls[28,4,22,14]/$imr2
dmax $ls[30,6,20,12] $lr[14,22,4,28] $lr[14,22,4,28] $omr2; l1bmd+0 $lr[14,22,4,28] $lbi; l1bmd $lbi $ls[26,2,18,10]/$imr1
dmin $ls[54,60,32,56] $lr[52,56,48,40] $lr[52,56,48,40] $omr1; l1bmd+0 $lr[52,56,48,40] $lbi; l1bmd $lbi $ls[30,6,20,12]/$imr2
dmin $ls[44,52,38,62] $lr[60,36,54,46] $lr[60,36,54,46] $omr2; l1bmd+0 $lr[60,36,54,46] $lbi; l1bmd $lbi $ls[54,60,32,56]/$imr1
dmin $ls[42,50,34,58] $lr[58,34,50,42] $lr[58,34,50,42] $omr1; l1bmd+0 $lr[58,34,50,42] $lbi; l1bmd $lbi $ls[44,52,38,62]/$imr2
dmin $ls[46,54,36,60] $lr[62,38,52,44] $lr[62,38,52,44] $omr2; l1bmd+0 $lr[62,38,52,44] $lbi; l1bmd $lbi $ls[42,50,34,58]/$imr1
dmin $ls[40,48,16,8] $lr[56,32,2,26] $lr[56,32,2,26] $omr1; l1bmd+0 $lr[56,32,2,26] $lbi; l1bmd $lbi $ls[46,54,36,60]/$imr2
dmin $ls[28,4,22,14] $lr[14,22,4,28] $lr[14,22,4,28] $omr2; l1bmd+0 $lr[14,22,4,28] $lbi; l1bmd $lbi $ls[40,48,16,8]/$imr1
dmax $ls[24,0,34,58] $lr[8,16,48,40] $lr[8,16,48,40] $omr1; l1bmd+0 $lr[8,16,48,40] $lbi; l1bmd $lbi $ls[28,4,22,14]/$imr2
dmax $ls[46,54,36,60] $lr[60,36,54,46] $lr[60,36,54,46] $omr2; l1bmd+0 $lr[60,36,54,46] $lbi; l1bmd $lbi $ls[24,0,34,58]/$imr1
dmin $ls[26,2,16,8] $lr[8,16,6,30] $lr[8,16,6,30] $omr1; l1bmd+0 $lr[8,16,6,30] $lbi; l1bmd $lbi $ls[46,54,36,60]/$imr2
dmin $ls[28,4,22,14] $lr[10,18,2,26] $lr[10,18,2,26] $omr2; l1bmd+0 $lr[10,18,2,26] $lbi; l1bmd $lbi $ls[26,2,16,8]/$imr1
dmax $ls[40,48,38,62] $lr[58,34,48,40] $lr[58,34,48,40] $omr4; l1bmd+0 $lr[58,34,48,40] $lbi; l1bmd $lbi $ls[28,4,22,14]/$imr2
dmin $ls[26,2,18,10] $lr[14,22,4,28] $lr[14,22,4,28] $omr3; l1bmd+0 $lr[14,22,4,28] $lbi; l1bmd $lbi $ls[40,48,38,62]/$imr4
dmax $ls[42,50,34,58] $lr[60,36,54,46] $lr[60,36,54,46] $omr1; l1bmd+0 $lr[60,36,54,46] $lbi; l1bmd $lbi $ls[26,2,18,10]/$imr3
dmax $ls[46,54,36,60] $lr[58,34,50,42] $lr[58,34,50,42] $omr2; l1bmd+0 $lr[58,34,50,42] $lbi; l1bmd $lbi $ls[42,50,34,58]/$imr1
dmin $ls[30,6,16,8] $lr[8,16,12,20] $lr[8,16,12,20] $omr1; l1bmd+0 $lr[8,16,12,20] $lbi; l1bmd $lbi $ls[46,54,36,60]/$imr2
dmin $ls[28,4,22,14] $lr[6,30,10,18] $lr[6,30,10,18] $omr2; l1bmd+0 $lr[6,30,10,18] $lbi; l1bmd $lbi $ls[30,6,16,8]/$imr1
dmin $ls[26,2,18,10] $lr[2,26,14,22] $lr[2,26,14,22] $omr1; l1bmd+0 $lr[2,26,14,22] $lbi; l1bmd $lbi $ls[28,4,22,14]/$imr2
dmin $ls[30,6,20,12] $lr[4,28,8,16] $lr[4,28,8,16] $omr2; l1bmd+0 $lr[4,28,8,16] $lbi; l1bmd $lbi $ls[26,2,18,10]/$imr1
dmax $ls[40,48,44,52] $lr[62,38,48,40] $lr[62,38,48,40] $omr1; l1bmd+0 $lr[62,38,48,40] $lbi; l1bmd $lbi $ls[30,6,20,12]/$imr2
dmax $ls[38,62,42,50] $lr[60,36,54,46] $lr[60,36,54,46] $omr2; l1bmd+0 $lr[60,36,54,46] $lbi; l1bmd $lbi $ls[40,48,44,52]/$imr1
dmax $ls[34,58,46,54] $lr[58,34,50,42] $lr[58,34,50,42] $omr1; l1bmd+0 $lr[58,34,50,42] $lbi; l1bmd $lbi $ls[38,62,42,50]/$imr2
dmax $ls[36,60,40,48] $lr[62,38,52,44] $lr[62,38,52,44] $omr2; l1bmd+0 $lr[62,38,52,44] $lbi; l1bmd $lbi $ls[34,58,46,54]/$imr1
dmin $ls[16,8,28,4] $lr[24,12,20,6] $lr[24,12,20,6] $omr1; l1bmd+0 $lr[24,12,20,6] $lbi; l1bmd $lbi $ls[36,60,40,48]/$imr2
dmin $ls[22,14,26,2] $lr[30,10,18,2] $lr[30,10,18,2] $omr2; l1bmd+0 $lr[30,10,18,2] $lbi; l1bmd $lbi $ls[16,8,28,4]/$imr1
dmin $ls[18,10,30,6] $lr[26,14,22,4] $lr[26,14,22,4] $omr1; l1bmd+0 $lr[26,14,22,4] $lbi; l1bmd $lbi $ls[22,14,26,2]/$imr2
dmin $ls[20,12,24,24] $lr[28,8,16,16] $lr[28,8,16,16] $omr3; l1bmd+0 $lr[28,8,16,16] $lbi; l1bmd $lbi $ls[18,10,30,6]/$imr1
dmax $ls[56,44,52,38] $lr[48,40,60,36] $lr[48,40,60,36] $omr2; l1bmd+0 $lr[48,40,60,36] $lbi; l1bmd $lbi $ls[20,12,24,24]/$imr3
dmax $ls[62,42,50,34] $lr[54,46,58,34] $lr[54,46,58,34] $omr1; l1bmd+0 $lr[54,46,58,34] $lbi; l1bmd $lbi $ls[56,44,52,38]/$imr2
dmax $ls[58,46,54,36] $lr[50,42,62,38] $lr[50,42,62,38] $omr2; l1bmd+0 $lr[50,42,62,38] $lbi; l1bmd $lbi $ls[62,42,50,34]/$imr1
dmax $ls[60,40,48,32] $lr[52,44,56,0] $lr[52,44,56,0] $ln[0,0,0,0] $omr1; l1bmd+0 $lr[52,44,56,0] $lbi; l1bmd $lbi $ls[58,46,54,36]/$imr2
dmax $ls[16,56,8,44] $lr[48,24,40,12] $lr[48,24,40,12] $omr2; l1bmd+0 $lr[48,24,40,12] $lbi; l1bmd $lbi $ls[60,40,48,32]/$imr1
dmax $ls[28,52,4,38] $lr[60,20,36,6] $lr[60,20,36,6] $omr1; l1bmd+0 $lr[60,20,36,6] $lbi; l1bmd $lbi $ls[16,56,8,44]/$imr2
dmax $ls[22,62,14,42] $lr[54,30,46,10] $lr[54,30,46,10] $omr2; l1bmd+0 $lr[54,30,46,10] $lbi; l1bmd $lbi $ls[28,52,4,38]/$imr1
dmax $ls[26,50,2,34] $lr[58,18,34,2] $lr[58,18,34,2] $omr1; l1bmd+0 $lr[58,18,34,2] $lbi; l1bmd $lbi $ls[22,62,14,42]/$imr2
dmax $ls[18,58,10,46] $lr[50,26,42,14] $lr[50,26,42,14] $omr2; l1bmd+0 $lr[50,26,42,14] $lbi; l1bmd $lbi $ls[26,50,2,34]/$imr1
dmax $ls[30,54,6,36] $lr[62,22,38,4] $lr[62,22,38,4] $omr1; l1bmd+0 $lr[62,22,38,4] $lbi; l1bmd $lbi $ls[18,58,10,46]/$imr2
dmax $ls[20,60,12,40] $lr[52,28,44,8] $lr[52,28,44,8] $omr2; l1bmd+0 $lr[52,28,44,8] $lbi; l1bmd $lbi $ls[30,54,6,36]/$imr1
dmax $ls[24,48,0,0] $lr[56,16,32,32] $lr[56,16,32,32] $omr3; l1bmd+0 $lr[56,16,32,32] $lbi; l1bmd $lbi $ls[20,60,12,40]/$imr2
dmin $ls[32,16,56,8] $lr[2,50,26,42] $lr[2,50,26,42] $omr1; l1bmd+0 $lr[2,50,26,42] $lbi; l1bmd $lbi $ls[24,48,0,0]/$imr3
dmin $ls[44,28,52,4] $lr[14,62,22,38] $lr[14,62,22,38] $omr2; l1bmd+0 $lr[14,62,22,38] $lbi; l1bmd $lbi $ls[32,16,56,8]/$imr1
dmin $ls[38,22,62,14] $lr[4,52,28,44] $lr[4,52,28,44] $omr1; l1bmd+0 $lr[4,52,28,44] $lbi; l1bmd $lbi $ls[44,28,52,4]/$imr2
dmin $ls[42,26,50,2] $lr[8,56,16,32] $lr[8,56,16,32] $omr2; l1bmd+0 $lr[8,56,16,32] $lbi; l1bmd $lbi $ls[38,22,62,14]/$imr1
dmin $ls[32,16,56,8] $lr[6,54,30,46] $lr[6,54,30,46] $omr1; l1bmd+0 $lr[6,54,30,46] $lbi; l1bmd $lbi $ls[42,26,50,2]/$imr2
dmin $ls[44,28,52,4] $lr[10,58,18,34] $lr[10,58,18,34] $omr2; l1bmd+0 $lr[10,58,18,34] $lbi; l1bmd $lbi $ls[32,16,56,8]/$imr1
dmin $ls[38,22,62,14] $lr[2,50,26,42] $lr[2,50,26,42] $omr1; l1bmd+0 $lr[2,50,26,42] $lbi; l1bmd $lbi $ls[44,28,52,4]/$imr2
dmin $ls[42,26,50,2] $lr[14,62,22,38] $lr[14,62,22,38] $omr2; l1bmd+0 $lr[14,62,22,38] $lbi; l1bmd $lbi $ls[38,22,62,14]/$imr1
dmin $ls[34,18,58,10] $lr[4,52,28,44] $lr[4,52,28,44] $omr1; l1bmd+0 $lr[4,52,28,44] $lbi; l1bmd $lbi $ls[42,26,50,2]/$imr2
dmin $ls[46,30,54,6] $lr[8,56,16,32] $lr[8,56,16,32] $omr2; l1bmd+0 $lr[8,56,16,32] $lbi; l1bmd $lbi $ls[34,18,58,10]/$imr1
dmin $ls[32,16,56,8] $lr[12,60,20,36] $lr[12,60,20,36] $omr1; l1bmd+0 $lr[12,60,20,36] $lbi; l1bmd $lbi $ls[46,30,54,6]/$imr2
dmin $ls[44,28,52,4] $lr[6,54,30,46] $lr[6,54,30,46] $omr2; l1bmd+0 $lr[6,54,30,46] $lbi; l1bmd $lbi $ls[32,16,56,8]/$imr1
dmin $ls[38,22,62,14] $lr[10,58,18,34] $lr[10,58,18,34] $omr1; l1bmd+0 $lr[10,58,18,34] $lbi; l1bmd $lbi $ls[44,28,52,4]/$imr2
dmin $ls[42,26,50,2] $lr[2,50,26,42] $lr[2,50,26,42] $omr2; l1bmd+0 $lr[2,50,26,42] $lbi; l1bmd $lbi $ls[38,22,62,14]/$imr1
dmin $ls[34,18,58,10] $lr[14,62,22,38] $lr[14,62,22,38] $omr1; l1bmd+0 $lr[14,62,22,38] $lbi; l1bmd $lbi $ls[42,26,50,2]/$imr2
dmin $ls[46,30,54,6] $lr[4,52,28,44] $lr[4,52,28,44] $omr2; l1bmd+0 $lr[4,52,28,44] $lbi; l1bmd $lbi $ls[34,18,58,10]/$imr1
dmin $ls[36,20,60,12] $lr[8,56,16,32] $lr[8,56,16,32] $omr1; l1bmd+0 $lr[8,56,16,32] $lbi; l1bmd $lbi $ls[46,30,54,6]/$imr2
dmin $ls[32,16,56,8] $lr[24,40,12,60] $lr[24,40,12,60] $omr2; l1bmd+0 $lr[24,40,12,60] $lbi; l1bmd $lbi $ls[36,20,60,12]/$imr1
dmin $ls[44,28,52,4] $lr[20,36,6,54] $lr[20,36,6,54] $omr1; l1bmd+0 $lr[20,36,6,54] $lbi; l1bmd $lbi $ls[32,16,56,8]/$imr2
dmin $ls[38,22,62,14] $lr[30,46,10,58] $lr[30,46,10,58] $omr2; l1bmd+0 $lr[30,46,10,58] $lbi; l1bmd $lbi $ls[44,28,52,4]/$imr1
dmin $ls[42,26,50,2] $lr[18,34,2,50] $lr[18,34,2,50] $omr1; l1bmd+0 $lr[18,34,2,50] $lbi; l1bmd $lbi $ls[38,22,62,14]/$imr2
dmin $ls[34,18,58,10] $lr[26,42,14,62] $lr[26,42,14,62] $omr2; l1bmd+0 $lr[26,42,14,62] $lbi; l1bmd $lbi $ls[42,26,50,2]/$imr1
dmin $ls[46,30,54,6] $lr[22,38,4,52] $lr[22,38,4,52] $omr1; l1bmd+0 $lr[22,38,4,52] $lbi; l1bmd $lbi $ls[34,18,58,10]/$imr2
dmin $ls[36,20,60,12] $lr[28,44,8,56] $lr[28,44,8,56] $omr2; l1bmd+0 $lr[28,44,8,56] $lbi; l1bmd $lbi $ls[46,30,54,6]/$imr1
dmin $ls[40,24,32,16] $lr[16,32,48,24] $lr[16,32,48,24] $ln[4,4,4,8] $omr1; l1bmd+0 $lr[16,32,48,24] $lbi; l1bmd $lbi $ls[36,20,60,12]/$imr2
dmin $ls[56,8,44,28] $lr[40,12,60,20] $lr[40,12,60,20] $ln12v4 $omr2; l1bmd+0 $lr[40,12,60,20] $lbi; l1bmd $lbi $ls[40,24,32,16]/$imr1
dmin $ls[52,4,38,22] $lr[36,6,54,30] $lr[36,6,54,30] $ln28v4 $omr1; l1bmd+0 $lr[36,6,54,30] $lbi; l1bmd $lbi $ls[56,8,44,28]/$imr2
dmin $ls[62,14,42,26] $lr[46,10,58,18] $lr[46,10,58,18] $ln44v4 $omr2; l1bmd+0 $lr[46,10,58,18] $lbi; l1bmd $lbi $ls[52,4,38,22]/$imr1
dmin $ls[50,2,34,18] $lr[34,2,50,26] $lr[34,2,50,26] $ln60v4 $omr1; l1bmd+0 $lr[34,2,50,26] $lbi; l1bmd $lbi $ls[62,14,42,26]/$imr2
dmin $ls[58,10,46,30] $lr[42,14,62,22] $lr[42,14,62,22] $ln76v4 $omr2; l1bmd+0 $lr[42,14,62,22] $lbi; l1bmd $lbi $ls[50,2,34,18]/$imr1
dmin $ls[54,6,36,20] $lr[38,4,52,28] $lr[38,4,52,28] $ln92v4 $omr1; l1bmd+0 $lr[38,4,52,28] $lbi; l1bmd $lbi $ls[58,10,46,30]/$imr2
dmin $ls[60,12,40,24] $lr[44,8,56,16] $lr[44,8,56,16] $ln108v4 $omr2; l1bmd+0 $lr[44,8,56,16] $lbi; l1bmd $lbi $ls[54,6,36,20]/$imr1
dmin $ls48 $lr32 $lr32 $ln124 $omr3; l1bmd+0 $lr32 $lbi; l1bmd $lbi $ls[60,12,40,24]/$imr2
dpassa $ls[32,16,56,8] $ln[2,6,10,14]; l1bmd $lbi $ls48/$imr3
dpassa $ls[44,28,52,4] $ln[18,22,26,30]
dpassa $ls[38,22,62,14] $ln[34,38,42,46]
dpassa $ls[42,26,50,2] $ln[50,54,58,62]
dpassa $ls[34,18,58,10] $ln[66,70,74,78]
dpassa $ls[46,30,54,6] $ln[82,86,90,94]
dpassa $ls[36,20,60,12] $ln[98,102,106,110]
dpassa $ls[40,24,48,0] $ln[114,118,122,126]

展望

前後の転送命令を無視すれば、比較の数(543回)から導かれる行数の限界、146行にあと1行というところまで近づけました。いったんこの問題はここでやめて、この問題をMAB間方向のPE16個に渡る1024要素のソートへと改題したものを解いてみようと思っています。Sorting Networkをそのまま使うと効率が悪く、問題を分割することでコードを削ることができます。できたらまた記事を書きます。

2026-05-05

MN-Core Challenge - Count Up 21行

MN-Core Challenge

2024年8月末から9月末にかけて開催されていた、コードゴルフのコンテストです。

Count Up

DRAM($d0@0)に、32ビット整数を1, 2, 3, ... 32768 と、32768個書き込む問題です。これまで、PEで生成した値をそのまま転送すると決め打ちしていて、23行より短くならなかったのですが、方針を変えて21行解を見つけました。

方針

PEから16384長語をそのままDRAMに送ろうとすると、L1BM→L2BMの転送がボトルネックとなります。また、各所で結合する際にレイアウトがめちゃくちゃになるため、PEで煩雑な計算を行ってから送り出す必要があります。そこで、L2BM→PDMや、L2BM→DRAMの縮約命令を使って、小さい種から切り貼りで値を作ることを考えます。

種	生成方法	長さ(長語単位)	繰り返し回数
A	Bを128回複製	128	128	1,1,3,3,5,5,7, .. ,255,255	1,1,3,3,5,5,7, .. ,255,255	～	1,1,3,3,5,5,7, .. ,255,255
B	PE	128	1	1,1,3,3,5,5,7, .. ,255,255
C	Dを8倍延長	16384	1	0,1,0,1, .. , 0,1	256,257,256,257, .. , 256,257	～	32512,32513,32512,32513, .. , 32512,32513
D	E+G	2048	1	0,1,0,1, .. , 0,1	256,257,256,257, .. , 256,257	～	32512,32513,32512,32513, .. , 32512,32513
E	Fを16回複製	128	16	[0]×16,[256]×16, .. , [1792]×16	[0]×16,[256]×16, .. , [1792]×16	～	[0]×16,[256]×16, .. , [1792]×16
F	PE	128	1	[0]×16,[256]×16, .. , [1792]×16
G	Hを8倍延長	2048	1	0,1,0,1, .. , 0,1	2048,2049,2048,2049, .. , 2048,2049	～	30720,30721,30720,30721, .. , 30720,30721
H	PE	256	1	0,1,0,1, .. , 0,1	2048,2049,2048,2049, .. , 2048,2049	～	30720,30721,30720,30721, .. , 30720,30721

見苦しい表ですみません。A+Cで答えが得られます。

延長

L2BM→PDMの結合命令mvdでは、8個のL2BMから値を読み出して結合します。放送と組み合わせて、16長語の塊を128長語に延長することができます。 abcd が aaaaaaaabbbbbbbbccccccccdddddddd になると思ってください。

複製

DRAM間接参照機能を使うことで、簡単に複製ができます。複製したい値をDRAMに書き込んでおきます。そして、その先頭アドレスの16分の1をDAR(DRAMアドレスレジスタ)に繰り返し書き込みます。このアドレスを繰り返し使うことで、DRAMの同じ箇所から何度も値を読み出せます。 abcd が abcdabcdabcdabcd になると思ってください。

今回のコードでは、BとFを複製します。l2bmdarw命令が、転送スループット4アドレス/行と遅すぎるので、F用の16個のアドレスしか書き込めません。B用のアドレスは、コンテストの設定上最初から書き込まれている0を使っています。F用のアドレスは、$d128@0にFを書き込んだので、16分の1の、8を書き込みます。

PE

PEでは、上表のB, F, Hを生成します。 Bは、前半の64長語を($peid<<1)+1で計算し、後半はそれに128を足して求めます。

Fは、(($l1bid&6) << 7) + (($mabid&0xC) << 8)で求めたいです。同じ値を16長語続けないといけないので、いくつかのビットを無視します。しかし、iand命令などを使うと行数が増えてしまいます。 $mabidについては、4×4縮約命令のl1bmr4fminを使って、下位2ビットが00の値を得られます。なお、この命令は単精度浮動小数点数の最小値を返しますが、値の最上位ビットが0であり、正規化も行われないことから、整数として解釈した最小値と同じ結果になります。 $l1bidについては、l2bmr2fminによって、奇数番のL1から来た値を使わないことで実現しています。

Hは、ほぼFの8倍なのですが、BもFも長語内の2単語が同じ値なので、このままだと 1,2,3,4, .. 32767,32768 ではなくて、 1,1,3,3, .. ,32767,32767 になってしまいます。つまり、後ろ側の単語にのみ1を加算する必要があります。linc命令でもいいのですが、1行増えるので、マスクを使い、後ろの単語の最上位3ビットを001としておくことで、3ビットのバレル左シフトによって、最下位のビットが立つようにしています。

コード

21行です。

imm ui"0x3FC1C208" $llt $s1
ilsl $mabid $aluf $nowrite; hvpassar -$aluf $omr1; l1bmr4ior $aluf $lb1024
slsl/$imr1 $l1bid $lltr $lr0v; fvpassa -$llt $nowrite; l1bmr4fmin $aluf $lbi
ipackbit $peid $mauf $t; fvmul $t $t $lr8; l1bmm4 $lbi $nowrite
iadd $lr0 $lbf $ls0v/$imr1; l1bmd+0 $aluf $lb0; l2bmriiadd $lb1024 $lc1024
iadd $t $lr0v $nowrite; l1bmd+0 $aluf $lb256
ibsl/$imr1 $ls0 $lr8 $nowrite; l1bmd+0 $aluf $lb512; l2bmdars $lc1024@.0 $dar0; l2bmdarw
l1bmd+0 $aluf $lb768; l2bm@1 $lb0 $lc128; l2bmdarw
l2bmr2fmin $lb256 $lc256; l2bmdarw
l2bm@1 $lb512 $lc192; l2bmdarw
l2bmr2fmin $lb768 $lc768
nop
mvd/n256 $lc768 $p0@0
mvp/n256 $lc128@0.0 $d0@0
mvp/n18432nd8 $di0@0 $lc0@0.0
mvp/n2048 $p0@0 $lc0@0.1
mvr2iiadd/n2048 $lc0@0 $p0@0
mvb/n2048 $p0@0 $lc0
mvd/n2048 $lc0 $p0@0
mvp/n16384 $p0@0 $lc2048@0.1
mvr2iiadd/n16384 $lc2048 $d0

雑記

MOV

ALUの入力を精度縮減できることと、GRFの読み書きは同時に違うアドレスに対して行ってもよいことに、今更気付きました。

そうなると、コンテストでは、大量の値をMOVしたいのに命令がなくて困りそうです。ALU, MAUは計算させたい、L1の$lbiを経由すると2行かかる、行列レジスタを経由するとさらに転置されてしまう、などそれぞれに癖があります。想定されている使い方ではないということなのでしょうが、浮動小数点数の積和など、「複雑な」命令が安売りされているのに比べて、そのまま転送するだけの簡単な経路くらいあってほしいと思ってしまいます。思ったときに思った場所に値がないのが痒いです。だいぶ異なる話ですが、昔、x64は複雑だからと思ってx86を勉強していたときに、レジスタが足りず、スタックと相談するのが常だったのと感覚が似ています。難しいというよりは面倒で、計算のことを考えたいのに、「つまらない」ことで煩わされるのがストレスになるようです。もちろん、MN-Coreの方は、128ビットの値を各所に引き回すと配線がひどそうですし、見合う利益もなさそうです。コンテストの視点からでは、実用性に繋がらない機能を欲しがってしまいます。

エミュレータ

PDMのデバッグ出力がきちんと表示されないので、転送が行われていないと勘違いしてしまいました。エミュレータは使われていない気配がします。

2025-08-16

MN-Core Challenge 追加問題

MN-Core Challenge

mncore-challenge.preferred.jp

2024年8月末から9月末にかけて開催されていた、コードゴルフのコンテストでした。開催していただきありがとうございました。 Preferred Networks社のコンピュータであるMN-Core 2のアセンブリを書いて、所定の動作をより少ない行数で実現すると高得点になります。

まず、sosuupoyoさんとlogicmachineさんの解説をお読みください。

primenumber.hatenadiary.jp

qiita.com

問題は19問+FizzBuzzでしたが、コンテスト後に5問の追加がありました。

私は参加したものの、途中でメンタルが保たなくなって逃げ出してしまいました。2025年の6月末に追加問題とmod 3を解いてみまして、他の問題は私には縮められそうにないなので、2025/8/15時点で私が最短を取っている分を記事にします。

コンテストの問題

Plus 2

20個のLongに2を足すだけの問題です。テストケース依存解があると聞いて、生成しやすい値から作っていくと、5行でできました。もちろんずるです。

Lesseq

Floatが1以上かどうかによって場合分けする問題です。1以上のときのみ、LM1(n)に0x7FFFFFFFを書き込んでやります。

idec $msb1 $lr4v; fvadd $lm32v $lm32v $nowrite
frelu2 $mauf $aluf $ln32v; hvfma $llm0vr $llm0vr -$llm0v $omr1
fpassa $llr4 $lln0v/$llimr1; hvfma $llm16vr $llm16vr -$llm16v $omr2
fpassa $llr4 $lln16v/$llimr2

relu2を使うのは、Floatでの2の表現の最上位4ビットが0100で、2未満なら0011以下になるので、上から3つめのビットで判別可能だということです。本当は0000と0001の可能性も考えるべきなのですが、入力の制約があって、それほど小さい値は入ってこないようになっています。

Square Sum

Doubleを2乗して、和を求める問題です。乗算はMABでしかできないので、各MABに分担して2乗を計算させてから、縮約命令でまとめます。サイクル方向の加算がちょっと面倒です。絶妙に要素数が少ないのと、ALUが役に立たないので、これが限界だと思います。

ipackbit $mabid $lr0 $lt
nop
dvmulu $lmt0v32 $lmt0v32 $nowrite
dvfmau $lmt128v32 $lmt128v32 $mauf $nowrite
dvfmad $lmt0v32 $lmt0v32 $mauf $nowrite
dvfmad $lmt128v32 $lmt128v32 $mauf $lr8v
nop
dvadd $mauf $lr[10,0,0,12] $nowrite
l1bmrdfadd $mauf $lbi
l1bmm $lbi $lr[8,64,64,64]
dvadd $lr[0,0,0,8] $lbf $ln[64,64,64,0]

Mod 3

Intを3で割った余りを求めますが、実は8ビット分の値しか入力されないので、うまくやるとFloatの積和で余りを含むビット列を作れます。詳しくはlogicmachineさんの記事をお読みください。コンテスト中の私はそんなこと不可能だと決めつけてしまっていました。

imm ui"0x00000003" $t
imm ui"0x452ad551" $llr16v
smax $llm0v $aluf $lls0v; hvpassa $aluf $omr1; l1bmd+0 $aluf $lb0
smax $llm16v $llr16v $llr16v; fvfma $aluf $llr16v -$aluf $nowrite; l1bmd+0 $llr16v $lbi; l1bmd $lbi $ls2v4/$imr1
iand $mauf $t $ln0v4; fvfma $aluf $lbf -$aluf $nowrite; l1bmd $lbi $lr18v4/$imr1
iand $mauf $t $ln16v4; fvfma $ls2v4 $lbf -$ls2v4 $nowrite; l1bmd $lb0 $nowrite
iand $mauf $t $ln2v4; fvfma $lr18v4 $lbf -$lr18v4 $nowrite
iand $mauf $t $ln18v4

sosuupoyoさんの他の問題の解を見て、浮動小数点数のヘッダを乗せるのにsmaxを使えることを知り、マスクと併用することでiaddやiorなどを2行減らせました。ただ、どうしても3を生成できなかったので、immが1行増えて、8行になりました。

追加問題

Hello, world!

DRAMにHello, world!を書き込む問題です。

「ヌル終端の必要がない」というのは、つまり0x21まで合っていれば、その後にどんなゴミが入っていても構わない、ということです。含みのある表現なので、探すと、最初の0x48656C6Cをちょっと捻って生成できることがわかります。

0x21はShort, Float, Doubleのどれで解釈してもとても小さい値になってしまいますが、短い型で解釈するとより大きい値を意味するので、Doubleの0x3AをFloatの0x13に読み換えます。そして、指数部を変えるのには、MAB→L1BMと、L1BM→L2BMのhalf加算縮約を併せて、0x0E00を加算できるのが強力です。なお、3行目のfvaddはマスクを反転しているだけです。

imm ui"0x3A655E6C" $lr0 $t
idec $subpeid $omr1; dvpassar $aluf $r1
imm ui"0x61725E64" $r0/$imr1; fvadd -$aluf -$t $omr2
imm ui"0x612C1277" $r1v2/$imr2
l1bmrhfadd $lr[16,16,16,0] $lb36
nop # この行にnop以外の命令を書くとエラーになります
nop # なんで?
l2bmrhfadd $lb16 $lc32
mvp/n64 $lc64@0.0 $d0@0

なぜですか?

Bit Reverse

1024ビットのビット列を、逆順に並べ替える問題です。

関数型言語の練習問題で、配列の逆転をするときのように、分割しつつ再帰的に計算します。 16個のMAB間で入力が放送されているので、Short内の逆転は、贅沢に各MABに1ビットずつのシフト(ローテート, バレルシフト)をしてもらいます。

spassa $mabid $lr16/1000
sbsl $lm0v $aluf $nowrite; l1bmd-1 $aluf $lbi
sand $msb1 $aluf $nowrite; l1bmrsor $lr16 $lbi; l1bmd-1 $lbi $nowrite
sbsl $aluf $lbf $nowrite; l1bmm $lbi $nowrite
sand $peid $lbf $omr1; l1bmrsbor $aluf $lbi
imm s"0x3E10" $nowrite; l1bmm $lbi $nowrite
ibsl $lbf $aluf $nowrite; hvmulr $aluf $aluf $nowrite
lbsl $aluf $mauf $lr8v
msr $aluf $ln[6,4,2,0]
msl $lr8v $ln[6,4,2,0]/$imr1

FizzBuzz PE

FizzBuzzの気分を少しだけ味わえる問題です。本質的には全然違って、mod 3のおまけ問題です。

ここでは愚直に浮動小数点数化した後、1/3と1/5を掛けて、下位ビットに0が並ぶものを倍数と判定しています。探したら同様に便利な数が見つかるのかもしれないので、今回解いた問題の中で一番最短解の自信がないです。

1行に複数のマスクレジスタからの読み出しがあってはならないので、最後の即値書き込みと、MAUで3の倍数と5の倍数の論理積を得る部分は、順番を調整しています。

imm ui"0x3EAAAAAB" $lr32/1000
iadd $lm0v $aluf $nowrite; l1bmd+0 $lm0v $lbi
imm ui"0x00000078" $t; fvadd $aluf -$lr32 $ls0v; l1bmd $lbi $ln0v
imm ui"0x3E4CCCCD" $ls40; fvmul $mauf $lr32 $nowrite
iand $mauf $t $omr1; fvmul $ls0v $aluf $nowrite
iand $mauf $t $omr2; fvpassa/$imr1 $lr32 $nowrite
imm ui"0x0000BBBB" $ln0v/$imr2; fvpassa/$imr2 $mauf $nowrite
imm ui"0x0000FFFF" $ln0v/$imr1; fvadd $mauf -$ls40 $omr3
imm ui"0xFFFFBBBB" $ln0v/$imr3

Log 2

2の冪のIntが与えられて、log2を取る問題です。

Fuyuruさんの解答を、mod 3と同様の手法で縮めただけです。

シフト変位の0x17 (= 23)は、

0v4,16v4についてはsaddで足してからfvaddで引く
2v4については、マスクで無傷の入力から、hvpassarの正規化が効いて0にされた値を引く
18v4については、マスクで無傷の入力から、やはりマスクで0の値を引く

となって、結果には影響しません。

imm ui"0x0B808017" $t
sadd $llm0v $aluf $lls0v $omr1; hvpassar -$aluf $lr32; l1bmd+0 $aluf $lbi
sadd $llm16v $t $llr16v; fvadd $aluf -$t $nowrite; l1bmd+0 $t $lbi; l1bmd $lbi $ls2v4/$imr1; 
ilsr $mauf $t $ln0v4; fvadd $aluf -$t $nowrite; l1bmd $lbi $lr18v4/$imr1 $ls32v/$imr1
ilsr $mauf $t $ln16v4; fvadd $ls2v4 $lr32 $nowrite; 
ilsr $mauf $t $ln2v4; fvadd $lr18v4 -$ls32v $nowrite
ilsr $mauf $t $ln18v4

HSV2RGB

本記事のメインディッシュです。HSV色空間の色をRGB色空間に移します。他の問題とは異なる趣で、コンテストには入れづらそうです。

switchをそのまま実装すると長くなるのですが、よく見てみると、出力のr,g,bへのv,q,p,tの割り振りは、2つずつずれています。さらに、MAB間で入力が放送されているので、r,g,bにそれぞれMAB2,0,4を使って、同時に計算してもらいます。

r: . . v q p p t v . .
g: t v v q p p . . . .
b: . . . . p p t v v q

計算は、v,q,p,tそれぞれの値を計算してから求めるのではなくて、一番面倒なtを計算しておいて、そこから差分を引いていく形で実現しています。遠回りですが、最初はALUに負荷がかかっているため、MAUでtを計算するのは問題ありません。差分は、LUTからシフトとrelu系命令で選択します。上の表がきれいなので、このLUTが32ビットに収まっています。なお、mod 6を取る代わりに、i=6を許容しています。

v×sはあらかじめ計算しておきます。以下のコードで、reluのあたりを引き回されている$lr16vがそれです。v×s×fは必要な時に積和命令で計算できるので、単独では計算しません。 relu3は、MAB0,2,4ではマスクの生成、MAB11,13,15ではv×sの選択を担います。

以下が14行解です。

imm ui"0x43004300" $lr0v
fvmul $alufe $lm0v6 $lr8v
ffloor $mauf $ls0v; l1bmd+0 $lm4v6 $lbi
imm ui"0x10423880" $t; l1bmd $lbi $nowrite
fftoi $ls0v $nowrite; fvmul $lm2v6 $lbf $lr16v
iadd $mabid $aluf $nowrite
ilsl $t $aluf $t; fvadd -$ls0v $lr8v $lr8v
frelu3 $aluf $lr16v $omr1; fvfma $lr16v $mauf $lm4v6 $ls24v
filrelud/$imr1 $t $lr16v $nowrite; fvadd $mauf -$lr16v $ls32v; l1bmd-11 $aluf $lbi
fvfma -$aluf $lr8v $mauf $nowrite; l1bmd-11 $lbi $nowrite
fvadd $lbf $mauf $ln2v6 $t
l1bmm@4 $mauf $lbi
l1bmm@2 $t $lbi; l1bmm $lbi $ln4v6
l1bmm $lbi $ln0v6

12行解を引っ張って伸ばしたものなので当然ですが、スカスカです。前半ではMAUが余り、後半ではALUが余っているところに着目します。

まず、前半では、ALUの命令のうち、整数化のfftoiを、MAU側での大きな定数の加算で実現できるので、1行削れます。

後半では、LM1(n)への書き込みが1行空いているので、MAB2で計算しているrの結果をここに押し込みます。とはいえ、MAB2のfvaddの結果を、次の行のMAB0で使うことはできません。これを待たず、途中からMAB0のALUを使って計算します。そして、MAB2のfilreludの結果は間に合うので、これとの(積)和を取って書き込むことになります。

ALUで計算すべきは、v + v×s×f (Uとします) かv - v×s + v×s×f (= t)かの選択になります。加算はできないので、計算しておいた値から選びます。使えるのはALUの2行ですから、マスクを生成して、書き込み、ハザードを回避して読み込み、とすると1行足りません。計算式を見ると、0 ≤ t ≤ U の関係が成り立つはずです。

	reluの出力	max(relu, t)
tが必要なとき	-0	t
Uが必要なとき	U	U

というわけで、reluとmaxを使うと2行で選択できます。わざわざtから差分を引く形で計算していたのは、この不等式が成立する値をベースにしたいためでした。なお、relu0だとMAB16(ありません)を参照しないといけなくなってしまうので、relu2を使いました。

12行解です。

imm ui"0x43004300" $lr0v
filrelud $msb1 $aluf $nowrite; fvmul $alufe $lm0v6 $lr8v
ffloor $mauf $ls0v; fvmulr $aluf $aluf $nowrite; l1bmd+0 $lm4v6 $lbi
imm ui"0x10423880" $t; hvfma $mauf $lr0vr $aluf $nowrite; l1bmd $lbi $nowrite
iadd $mabid $mauf $nowrite; fvmul $lm2v6 $lbf $lr16v
ilsl $t $aluf $t; fvadd -$ls0v $lr8v $lr8v
frelu3 $aluf $lr16v $omr1; fvfma $lr16v $mauf $lm4v6 $ls24v; l1bmm@14 $aluf $lbi
filrelud/$imr1 $t $lr16v $nowrite; fvadd $mauf -$lr16v $ls32v; l1bmd-11 $aluf $lbi; l1bmm $lbi $nowrite
frelu2 $lbf $ls24v $nowrite; fvfma -$aluf $lr8v $mauf $nowrite; l1bmm@2 $aluf $lbi; l1bmd-11 $lbi $nowrite
fmax $aluf $ls32v $lr64v; fvadd $lbf $mauf $ln2v6 $t; l1bmm $lbi $nowrite
fvfma -$lbf $lr8v $aluf $ln0v6; l1bmm@4 $mauf $lbi
l1bmm $lbi $ln4v6

終わり

私は1次元しか考えられず、パズル能力も弱いので、ビットをごちゃごちゃと動かす問題と比較的相性がよさそうに思います。作問も解答も各々の傾向が出ていて面白いです。

読んでいただいた方、またコンテストや解説を用意していただいた方々、ありがとうございました。