Blog
MN-Core™ コンパイラチームの西川 剛史です。今回は弊社が現在開催中のプログラミングコンテスト MN-Core Challenge をご紹介します。
MN-Core Challenge について
MN-Core Challenge には全20問の問題があり、A+B を計算する問題から、転倒数を計算する複雑な問題までの様々な問題があります。
参加者はそれぞれの問題に沿った動作となるよう、MN-Core シリーズの第 2 世代である MN-Core 2 で動くアセンブリを記述し、その行数の短さを競います。
MN-Core Challenge には現在500人以上の方にご挑戦いただいており、下図のようにほぼ毎日いずれかの問題で最短行数が更新されています。
図1 各問題のTopの行数の遷移 ※縦軸は9/12時点の最短行数を100%としたときの比率
コンテストは 2024/9/23 24:00:00 (JST) まで開催されていて、優秀な成績を修めた方々には総額100万円以上の賞金が進呈されます。
上位入賞者にはさらにコンパイラエンジニア採用で選考過程の一部免除のオファーもいたします。
今からでもまだ上位を狙うチャンスはありますので、奮ってご参加いただければと思います。
MN-Core 2 の特徴
MN-Core 2 では行数の短さが実行速度に直結します。
理由は単純で、MN-Core 2 には分岐命令やジャンプ命令がなく、前から順番に1行ずつ実行されるだけだからです。
分岐命令については、代わりにマスクレジスタが存在します。ジャンプ命令については、事前に計算したいサイズが分かっていることが多く、基本的にはループアンローリングで対処します。本当に必要な場合には、ホストとデータをやり取りして、ホスト側から供給する命令を切り替えることになります。
例題: Plus 2
さて、例題「Plus 2」を見てみましょう。この例題は入力に 2 を加えて出力する問題で、練習問題として実際に出題されています。
具体的には、レジスタに格納された整数 $lm0v, $lm8v, $lm16v, $lm24v, $lm32v それぞれに 2 を加えて $ln0v, $ln8v, $ln16v, $ln24v, $ln32v に出力する問題です。
ちょうど 1 を加える linc 命令があるので、中間結果を $lr0v に置いて2回ずつ使ってみます（15行）。
書き込んだ値はすぐに使えないので nop が挟まってしまっています。そこで、計算順序を入れ替えてみます（10行）。
整数加算命令 ladd もあります。即値を1回だけ作って使いまわしてみましょう（7行）。
このように、スループットを改善して行数を縮めることができます。さらに工夫して nop を除去できればより短くすることもできます。
Plus2の問題説明内では、このように行数を縮めていく過程がチュートリアル形式で解説していますので、ぜひトライしてください。
コードゴルフの楽しさ
「Plus 2」では命令順のパズルや使用する命令の改善によって高速化できましたが、問題の性質を利用するなどしてそもそものロジックを改善することで短くできる問題も多数出題されています。
命令セットを把握することも重要ですが、その上でひらめきがどの問題においても重要で、1問の中にたいてい複数のひらめきが存在します。
どれか1つに気付くたびに短くなっていくので、コードゴルフの楽しさを味わっていただけたらと思います。
おわりに
MN-Core Challenge は 2024/9/23 24:00 (JST) まで開催しています。
一部複雑な問題はありますが、「整数乗算命令がない中で整数を7倍する」といった程度の問題が大半となっておりますので気軽にご挑戦ください。
一方で最後には、配点0点で本選順位には影響しませんが、ラスボス FizzBuzz もご用意しておりますので腕に自信のある方はぜひご挑戦いただければと思います。
