Welcome

Top: 2 lines / kikurage

Par: 2 lines

Problem Statement

$16$ 個の $32$ bit 整数が、LM0 の先頭部（$m0, $m1, $m2, ..., $m15）に格納されています。

それぞれに $1$ を加え、LM1 の先頭部（$n0, $n1, $n2, ..., $n15）に出力してください。

Explanation

ようこそ MN-Core の世界へ！

MN-Core 2 でのプログラミングを始めるにあたり、最初に最小の演算ブロックである PE（Processing Element）を紹介しようと思います。

最初に雰囲気を掴んでもらうために、$4$ 個の $32$ bit 整数それぞれに $1$ を加える MN-Core 2 アセンブリ（VSM）を紹介します。

iinc $m[0,1,2,3] $n[0,1,2,3]

本当は $1$ 命令で「$8$ 個の」$32$ bit 整数を加算できるのですが、最後に紹介します。

この VSM の意味は、簡単には次のような感じです。

同じ意味で、簡潔に iinc $m0v $n0v と書くこともできます。

より詳しい意味は次の章から順に説明していきます。

「とにかく動かしてみたい！」という方はスキップして実行とコードテストからご覧ください。

LM とアドレス

まず、LM（Local Memory）について説明します。PE の中には、LM と呼ばれる記憶領域が LM0 と LM1 の $2$ つあります。他にも PE 付属の記憶領域として GRF0, GRF1, T レジスタがありますが、まずは LM だけ説明します。

LM0 と LM1 は基本的に同じもので、それぞれ $32$ bit × $4096$ 要素の容量を持ちます。

MN-Core 2 では、この $32$ bit の単位を「単語」と呼びます。語長の名称は他にも「半語」（$16$ bit）や「長語」（$64$ bit）があります。

MN-Core で使用される語長の名称

長語: $64$ bit（長語の整数は Long、浮動小数点数は Double）
単語: $32$ bit（単語の整数は Int、浮動小数点数は Float）
半語: $16$ bit（半語の整数は Short、浮動小数点数は Half）

LM0 のアドレスは、$m0, $m1, ... のように m というキーワードで指定します。LM の「M」と覚えてください。

LM1 のアドレスは、$n0, $n1, ... のように n というキーワードで指定します。M の次のアルファベット「N」と覚えてください。

CPU などでは一般にアドレスは Byte 単位で表現しますが、MN-Core 2 の LM はアドレスの最小単位が単語（$32$ bit）なので、単語単位で表現します。$m0 というと、LM0 の先頭の単語、次の $32$ bit が $m1 です。

また、LM は長語単位で領域を指定することもでき、$lm0 のように "Long" の l を付けて表現します。$lm0 は LM0 の先頭の長語領域、次の $64$ bit が $lm2 です。

LM0上でのデータの並び: 00000001_00000002_00000003_00000004_00000005_00000006 単語指定: | $m0 | $m1 | $m2 | $m3 | $m4 | $m5 | 長語指定: | $lm0 | $lm2 | $lm4 | LM1上でのデータの並び: 00000011_00000012_00000013_00000014_00000015_00000016 単語指定: | $n0 | $n1 | $n2 | $n3 | $n4 | $n5 | 長語指定: | $ln0 | $ln2 | $ln4 |

アドレスは $32$ bit 基準で数えるので、長語の $lm0 の次は $lm2 になります。$lm1 は存在しません。

命令と、サイクル・ステップ

PE の中には、主に整数演算を行う計算ユニットとして ALU があります。

命令は iinc $m0v $n0v のように、[命令の種類] [入力] [出力] の形式で書きます。

[命令の種類] には接頭辞があり、Int を意味する接頭辞 i と、「$1$ を加える」という命令 inc をつなげて iinc という構成です。

$16$ bit 整数を扱うときは Short の s で sinc、$64$ bit 整数を扱うときは Long の l で linc となります。

さて、冒頭で iinc $m[0,1,2,3] $n[0,1,2,3] によって「$4$ 個」の Int をインクリメントできると紹介しました。

実は MN-Core 2 は $1$ 命令で、対象アドレスを変えながら $4$ 回、同じ演算を行います。$1$ 回の演算を「サイクル」、$4$ 回の演算をまとめた $1$ 命令の単位を「ステップ」と呼びます。

$1$ ステップ＝ $4$ サイクル

MN-Core 2 の動作周波数は $750$ MHz なので、$1$ 秒間に $7.5$ 億サイクル動作します。

$m[0,1,2,3] という表記は、$4$ サイクルで、$m0, $m1, $m2, $m3 の $4$ つの単語を順番に計算することを意味します。

$4$ サイクルでアドレスが一定に増加する場合、$m0v1 と、増分を指定した表記も使えます。$m11v3 であれば、$m11, $m14, $m17, $m20 と、$2$ 個飛ばしの単語を指示できます。

v のあとの数値を省略した場合には、連続する要素がアクセスされるように増えていきます。すなわち、$n0v のような単語なら $1$、$ln0v のような長語なら $2$ ずつアドレスが増加します。$n0 のように v も省略すると、すべてのサイクルで同じアドレスにアクセスしますが、$4$ サイクルとも同じ場所への動作が行われるので意図しない挙動に気をつけましょう。

ということで以下の $3$ 命令は、どれも同じ意味を表しています。

linc $lm[0,2,4,6] $ln[0,2,4,6] linc $lm0v2 $ln0v2 linc $lm0v $ln0v

なお、$1$ ステップ内でアクセスするアドレスの組には制約が無いので、$m[314,15,926,53] のような指定も可能です。他のプロセッサなどで SIMD に慣れている方はびっくりしてしまうかもしれませんが、MN-Core 2 の $1$ 命令 $4$ サイクルというのは、時間差で処理していると思ってください。

ということで iinc $m0v $n0v や、 iinc $m[0,1,2,3] $n[0,1,2,3] は、$4$ サイクルかけて $m0, $m1, $m2, $m3 と連続した $4$ つの単語を、順番にそれぞれ $1$ だけ加算して、$n0, $n1, $n2, $n3 に書き込むことになります。

実行とコードテスト

さて、理屈が分かったところで、コードテストで実際に実行してみましょう。

以下の $1$ 行のコードを VSM 欄に貼り付け、Testcase は Welcome を選択し、「実行」ボタンを押しましょう。

iinc $m0v $n0v

Standard Error の最終行と、Standard Output に以下のような出力が表示されるはずです。

------------------- inputs -------------------- [38, 28, 14, 42, 7, 20, 38, 18, 22, 10, 10, 23, 35, 39, 23, 2] ------------------- expect -------------------- [39, 29, 15, 43, 8, 21, 39, 19, 23, 11, 11, 24, 36, 40, 24, 3] ------------------- actual -------------------- [39, 29, 15, 43, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] ------------------- check result -------------------- RESULT MISMATCH: pos=4 actual=0 expected=8 error=-8 RESULT MISMATCH: pos=5 actual=0 expected=21 error=-21 RESULT MISMATCH: pos=6 actual=0 expected=39 error=-39 RESULT MISMATCH: pos=7 actual=0 expected=19 error=-19 ...(中略) RESULT MISMATCH: pos=15 actual=0 expected=3 error=-3

4 value(s) correct, but 12 value(s) mismatch

inputs は今回入力として与えられた $16$ 個の整数です。expect は正解の値で、actual は実行したコードの出力です。

今回 $1$ 命令だけ実行したので、$m0 から $m3 の $4$ つの単語だけが計算され、LM1 に書き込まれました。

check result には、計算結果の正誤が表示されており、$0$-indexed で $4$ 番から $15$ 番までの単語が計算されておらず「RESULT MISMATCH」と表示されています。

VSM を $1$ 行追加して、$m4 から $m7 の $4$ つも計算してみましょう。

iinc $m0v $n0v iinc $m4v $n4v

実行してみると 8 value(s) correct, but 8 value(s) mismatch と、correct が増えるはずです。

この問題は $16$ 個の整数をインクリメントするのが目的なので、$m8 から $m15 を計算する VSM をあと $2$ 行書いてみてください。ACCEPTED!! score=4 と出たら正解です！　この score は、何行で解いたかを示しています。

それでは次に提出をしてみましょう。このページを一番下までスクロールしたところにある提出ボックスに VSM を貼り付けて Submit ボタンを押してみましょう。

Accepted と表示されれば正答です。おめでとうございます！　これで点数、この練習問題では $10$ 点が獲得できます。

自分が提出した内容はメニューバーの「Submissions」からいつでも確認できます。

$1$ サイクルで $64$ bit ぶん計算

さて、コードゴルフに取り掛かりましょう。このコンテストは命令数を削減し、"行数" を減らすと高得点が取れる仕組みになっています（練習問題など一部を除く）。

iinc $m0v $n0v という命令では、$1$ サイクルで $1$ つの単語（$32$ bit）を計算しました。

しかし、実は MN-Core 2 は $1$ サイクルで $64$ bit ぶんを同時に計算することができます。つまり $32$ bit の単語であれば $2$ つ、$16$ bit の半語であれば $4$ つを同時に計算できるのです。

iinc $lm0v $ln0v と、入出力に長語の領域を指定すると、$1$ サイクルで長語ぶんの Int を計算できます。

アドレスを v で省略せずに書くと iinc $lm[0,2,4,6] $ln[0,2,4,6] になります。これを図にすると以下のようになります。

なお、命令の接頭辞の方は iinc と、i のままです。

入力の長さが Long ということで linc と指示してしまうと $64$ bit 整数としての演算が行われるので、$lm0 を $2$ つの $32$ bit 整数ではなく、$1$ つの $64$ bit 整数として計算することになります。

大量の値を計算するときは、単精度でも半精度でも $64$ bit ぶんを一気に計算した方が得なので、入出力は $lm0v のように長語 l を使用することが多いです。

各問題にはパー（目標行数）が設定されています。この問題では $2$ 行以下で Accepted できれば達成となっていますので、ぜひ先程の $4$ 行から命令を削減してみてください！

次の問題はこちらになります。

想定解

想定解（ネタバレ）

$2$ 行解法

iinc $lm0v $ln0v iinc $lm8v $ln8v

Inputs

$X$ ($0 \le X[{i}] \le 50$): Int $lm[0:16] / ((8:1, 2_W:1); B@[PE,MAB,L1B,L2B])
?

Outputs

$Y$: Int $ln[0:16] / ((8:1, 2_W:1))
?

Testcases

testcase.vsm

Submission

ログイン / 新規登録