Skip to content

Instantly share code, notes, and snippets.

@tomoaki0705

tomoaki0705/adventCalendar2019-02.md

Last active February 14, 2022 08:24
Show Gist options
  • Save tomoaki0705/929d994303b5e598c3f86fae14443317 to your computer and use it in GitHub Desktop.
Save tomoaki0705/929d994303b5e598c3f86fae14443317 to your computer and use it in GitHub Desktop.
Download ZIP
NEON完全リファレンスを書いているお話
Raw
adventCalendar2019-02.md

NEON完全リファレンスを書いているお話

TL;DR

NEONとは。SIMDとは。

  • NEONとは、ArmのSIMD拡張命令の名前
  • SIMDとは、Single Instruction Multiple Dataの略で、ベクトル演算命令のこと
  • 複数のデータを同時に処理できる。ただしリファレンス的な情報が少なく、他のコードや実行結果から命令の中身を推測することが多々ある。

「完全」とはこれいかに

  • 現状、Arm社の公式サイトに乗っているNEONの命令を全て乗せるべく頑張ってるので「完全」。
  • タイトルの発案は @dandelion1124 先生です

vaddq と vqaddq って何が違うんだっけ

いきなり読者に優しくないすっ飛ばし方をしていますが、vaddqもvqaddqも、どちらもNEONの命令です。

この2つの命令は字面が似てるだけあって、似た計算をするのですが、一体どういう計算をするのか、ほとんどの人にはぱっとわからないと思います。

そこで、以下の2枚の画像を見比べてください。

  • vaddq命令の挙動 vaddq

  • vqaddq命令の挙動 vqaddq

1枚目がvaddq、2枚目がvqaddqです。 1枚目の画像のうち、12番目から16番目の要素 (注意：画像内の要素は一番右側が1番目、一番左側が16番目と数えます。理由は割愛) は、計算結果が255を超えます。 通常のC/C++だと、数字が越えた文はオーバーフローしてまた0から数え直されます。(規約を読んだわけではないので、実装依存かも。厳密なところは割愛) つまり(255+10)%256 = 9 という計算が行われ、計算結果が9になります。

一方で、vqaddqで同じデータを処理した場合、計算結果は255となります。 このように計算結果がオーバーフローした場合の挙動に差があります。 一般的にこの様な演算を「飽和演算」とか「飽和加算」とか言ったりします。

この挙動をいちいち公式サイトのマニュアルから調べるより、わかりやすいでしょ？と言うのが本書を書き始めた動機です。 Armの公式サイトには「Saturating Adding」とだけ書かれていて、まぁそれはそれで必要最低限で簡潔ではあるのだけれど、結局細かい挙動は分からなかったりします。

vld3q ってどんな命令だっけ

私がこよなく愛する命令、vld3q_u8です。 私が毎日仕事で使うマシンはx86系のCPUですが、x86系のCPUには未だ存在しないこのvld3q命令。 多くを語る前に次の図をご覧下さい。

神

どうでしょう。あまりに美しくて

「vld3q、いいよね…」

「いい…」

って感じになります。

これがどこで役に立つかと言うと、画像処理のフィルタリングをする一部の処理です。 RGBの画像はメモリ上に各ピクセルごと、各色の成分ごとに保存されます。 そうなると、赤(R)成分の、隣の赤は、3つ隣に存在します。 ベクトル演算するためには非常に面倒な並びになっています。 そこで、このvld3q命令を使うと、R成分、G成分、B成分ごとに分けてレジスタに格納してくれます。

飛び飛びに要素を抜き出して並べ替える命令をgather/scatter命令と言いますが、x86系のgather/scatter命令は2の乗数でしか使えない、という制約があります。つまり1,2,4要素ごとに並べ替えはできるけれど、3要素ごとに並べ替える命令は存在しないのです。 それが「え？当然あるけど？」と言わんがごとく存在するあたり、「NEON、いいよね…」「いい…」となるのです。

手前味噌ですが、vld3qに関する愛は3年前にも語っているので、そちらもよろしければ御覧ください。

Universal Intrinsic の紹介 - Qiita

執筆のためにやっていること

執筆にはRe:VIEWを使ってます。 ただし、執筆する部分の殆どは、前述の図を作るところだと理解しています。 また、手作業で、あんな沢山の図形、数字を描くのは狂気の沙汰です。

なので、Graphvizと、CMakeを使ってそのあたりを補完しています。

Graphviz

Graphviz 万歳!

Graphvizは、グラフを実際の画像ファイルに落とすツールで、描くグラフの種類によって、複数のツールが同梱されています。 本書ではその中のdotツールを使って図を描画しています。

dotによる通常の描画

dot 言語、もしくは dot ツールは、階層的な情報を描画するために向いています。 先程のvld3qも良いのですが、ここでは例として、[1:12]の整数における、約数の関係を使います。 下図が自身と約数の関係を描画したグラフです。

自身の約数を表すグラフ

例えば、12は約数として1,2,3,4,6 (と12) があるので、12から、12の約数へ矢印が伸びています。(自分自身への矢印は割愛) このようにdot言語で記述するだけでGraphvizが自動的に画像にしてくれます。

ノードの配置も適切に行ってくれます。先程の図ですは、約数の数が多い数ほど画像の上部に配置され、すべての数の約数となる「1」が最下部に、その次の段には素数が並んでいます。

また、エッジの描画にも特徴があり、可能な限りノードの上を通らないようにエッジが迂回しています。

Graphviz、すごい。ばんざい！

きれいに揃えるために

Graphvizは自動的にレイアウトと描画をやってくれるのですが、本書における使い方を考えると、配置を固定したいノードが多数あります。

  • 各要素の並び順は大切
  • 同じベクタ変数内の要素は同じ段に並んで欲しい
  • srcやdstなど、各ベクタ変数にラベルを付けたい。

本来は配置を考えずにうまいことGraphvizが画像を描画してくれるのですが、どうにか制約を付けないと本書には意味がありません。 自動でやってくれる配置を半手動にしなきゃいけなくなるのですが、色々hackして頑張っているところです。

hackのポイント

難しいのは左右の並べ替えです。 Graphvizは内部で配置の最適化っぽいことをやっているので、結果がどう出てくるかはdot言語の書き方にも依存します。

前述のvaddq命令レベルであれば、あまり難しくはありません。 基本的に要素ごとに接続して記述し、ベクタ変数内の要素を末尾から先頭への順番でdot言語で記述すると、先の図が生成されます。 ファイル内で出現した順序にも弱い制約が発生するため、簡単な図であればこのように並べ替えができます。

大変なのはvld3qを始めとする、並べ替えを伴う命令です。 gather/scatter命令だけでなく、shuffle/transpose命令も問題です。 ファイル内で記述する順番を変えても、Graphvizが最適化して接続するノード間をなるべく近づけようとします。 結果、ファイル内の記述順番を無視して配置が行われ、先程の美しい図は生成されません。

それよりも「強い」制約を課すことで意図的に並べ替えを制御します。

先程の約数を表す関係は、以下の dot 言語で記述できます。

digraph div
{
rankdir=TB
ranksep=2;
node_01[label="1"];
node_02[label="2"];
node_03[label="3"];
node_04[label="4"];
node_05[label="5"];
node_06[label="6"];
node_07[label="7"];
node_08[label="8"];
node_09[label="9"];
node_10[label="10"];
node_11[label="11"];
node_12[label="12"];
node_12 -> node_01;node_12 -> node_02;node_12 -> node_03;node_12 -> node_04;node_12 -> node_06;
node_11 -> node_01;
node_10 -> node_01;node_10 -> node_02;node_10 -> node_05;
node_09 -> node_01;node_09 -> node_03;
node_08 -> node_01;node_08 -> node_02;node_08 -> node_04;
node_07 -> node_01;
node_06 -> node_01;node_06 -> node_02;node_06 -> node_03;
node_05 -> node_01;
node_04 -> node_01;node_04 -> node_02;
node_03 -> node_01;
node_02 -> node_01;
}

この状態だと、例えば素数の並びがバラバラです。 素数だけでも、左から昇順で並べるようにしてみます。

この場合はrank=same属性を付けながら各ノードに順位付けをします。 先程のdotファイルの途中に、以下のような記述を追加します。

{rank=same;node_02;node_03;node_05;node_07;node_11;}
node_02->node_03->node_05->node_07->node_11[style=invis];

冒頭の rank=same で、そのあとに並ぶノード達の rank を同一とします。 ここでいうランクは、画像中の上下の位置だと思ってください。 つまり前述の2行は

  • 「ノードの、2,3,5,7,11は同一の高さに設定する」
  • 「2->3->5->7->11の順に高さを変えること」

という矛盾した2つの制約を記述しているのです。 エラーになるかと思いきや、Graphvizでは左右の順番に制約をつけることで、前述のグラフを描いてくれます。

  • 素数を左から昇順に並び替えた図 修正後の図

先程の図と違い、素数が左右の方向でソーティングされたのが分かるかと想います。 原理的にはこう言うHackを使ってノードの並び順を整列しています。

いつ出るの？

今の所技術書典8 (2020年2月29日、3月1日開催) に向けて執筆していますよ！ 予定日は「どちらか1日」で申し込んでるので、日程のうちどちらかになるかは未定ですよ！

ポケットリファレンス的な感じで、50p.、500円ぐらいを想定しています。。。 想定していました。 想定していたのですが、、、何かArm様の公式サイトから解説する命令を抽出していたら、全体の1/10を抽出した時点で40p.突破してるんですが。。。。 今回は紙媒体無しで出店しようか今から悩んでます (まだ当選してないのに)

自己紹介

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment