s5a_minute

**********************************************************************
セッション：S5a
テーマ：スーパーコンピュータが組込みシステムに降りてくる！〜新時代の高性能組込みシステムのSIMD／ベクトル処理の要点を押さえる
講師：山崎進北九州市立大学
日時：2021/09/03(金) 15:10～16:20
参加人数：14名
**********************************************************************

■背景

スーパーコンピュータで培われた並列計算技術が組込みシステムに降りてきたのは今に始まったことではない
・1994年のPlayStation、2000年のPlayStation2
・2021年3月、次期ArmアーキテクチャのArmv9の発表
-富岳で用いられるベクトル命令 SVE/SVE2が採用
・RISC-V
-ベクタ拡張を搭載したD1 chip搭載のIoTボードが市販
-2021年6月、高性能RISC-VチップをIntelが作ると発表

SIMD(Single Instruction Multi Data)はArmv9、RISC-Vに先んじて普及した
・現行のArmv8アーキテクチャに搭載
・GPUもSIMDアーキテクチャ
・Arm MailやNVIDIA Jetsonなどの、GPU搭載のIoTも一般的に

■SIMD/ベクトル処理を活用するには

○一般的な答え
スーパーコンピュータで培われてきた技術に由来するBLAS/LAPACKという線形代数に基づくライブラリと、それを活用するOSSライブラリを利用する
<理由>
・人智の限りを尽くしてSIMD/ベクトル処理を極限まで活用できるようにチューニングされている
・これを超えるものを容易に開発は出来ない。

○ライブラリ活用の時の懸念
・メモリやストレージにサイズがかかるのではないか？
・原理や仕組みが分からないと安心して使えない
・リアルタイム制約はどうなっているのか？

■SIMDの考え方

○並列処理の分類
・SISD(Single Instruction Single Data：単一命令単一データ):並列ではない
・SIMD(Single Instruction Multi Data：単一命令複数データ)
・MISD(Multi Instruction Single Data：複数命令単一データ):これに該当するものはほとんどない
・MIMD(Multi Instruction Multi Data：複数命令複数データ)

○MIMDとは？
・異なる動作を出来るユニットに並列処理をさせる方式
・マルチコアCPUと言われる場合はこの方式、コアが独立している
・複数の狩猟犬が個別に動いて連携して狩りをするようなイメージ
・SIMDと比べて並列度を稼ぎにくい
-研究段階では千個以上のコアを持つものもあるが、市販のCPUのコア数は数十～百数個程度

○SIMDとは？
・同一の動作を行うユニットに並列処理をさせる方式
・田植えを大人数で同時に行うようなイメージ
・CPUのSIMD命令やGPUで採用されている方式
・並列度を稼ぎやすい
-1000以上の並列度を持つGPUが市販されている

○CPUのSIMD命令
・固定長のビット幅SIMDレジスタで演算
-Intel SSE、ARM NEON(ARMv8)は128ビット
-Intel AVX/AVX2は256ビット
-Intel AVX-512は512ビット

・SIMDレジスタを区切って使用
-整数なら、符号付き/なしの設定と、8/16/32/64ビットの区切り方
-浮動小数点なら16ビットの半精度、32ビットの単精度、64ビットの倍精度

利点
・実現が容易である
-整数の加減程度なら、区切ったビット位置で加算回路のキャリー/ボローを伝播させないようにすればよい
-乗算回路や浮動小数点演算もそれらを並べれば良いだけ
欠点
・SIMD命令を使わないと性能は上がらない
-アセンブリプログラミング、またはSIMD命令のコード生成に対応したコンパイラが必須
・ビット幅が違うと機械語命令の互換性がない
-ビット幅を変える際にはプログラミングやコンパイルを改めて行うことが必要

・最近のClangやGCCはループに対して、自動的にSIMD命令を使うようにコード生成するように設定されている

○ベクトル命令
・分類上はSIMD
・SIMD命令と異なり、ベクトルレジスタ幅が変わってもプログラミングやコンパイルとやり直す必要が無い
-ベクトルレジスタ幅はCPUによるが、ループ回数などのパラメータを設定する専用の命令があるため

■SIMD化による効果

モノクロ化の画像フィルタを題材にしたサンプルプログラムを題材にする
（サンプルプログラムのGithub https://github.com/zacky1972/simd_sample）
<行った処理>
8ビット符号なし整数→32ビット符号なし整数→32ビット浮動小数点
→（R,G,B）<= 0.299*r + 0.587*g + 0.144*b →小数点以下を四捨五入
→32ビット符号なし整数→8ビット符号なし整数

Auto-vectorization（C言語のデフォルトの最適化技法）とIntrinsic（手動でSIMD命令をCで記述）の2種類の最適化技法を比較した

SIMD命令を手動で記述して最適化を図った場合、Auto-vectorizationの2～5倍の高速化効果があった

■メモリ配置

○AoS（Array of Structures）
・構造体の配列
・SIMD化しにくい
-構造上飛び飛びに参照する必要がある
-RGBが8ビットずつの例では、3バイトずつ飛ばし飛ばしでr、g、bをロードし、モノクロ化の係数をかける
・NEONにはこの問題に対応したロード・ストア命令が備わっている
-3バイトずつ読み飛ばしてSIMDレジスタに格納していくロード命令ld3qなど

○SoA（Structure of Arrays）
・配列の構造体
・SIMD化しやすい
-8ビット配列の値をいくつかまとめて処理する形にしやすい
-SEE・NEONは128ビット(8ビット×16個)、AVX2は256ビット(8ビット×32個)、AVX-512は512ビット(8ビット×64個)でまとめる

Auto-vectorizationを使うならSoAのスタイルでメモリ配置した方が無難
・ARMv8/NEONの場合、3バイト飛ばしのロード・ストア命令により、構造体のサイズによってはSoAとAoSの速度が同等、もしくはAoSの方が若干速くなることもある

■SIMD命令の活用の要点

○モノクロ化の流れ
1 ロード
2 8ビットを16ビットに拡張し、上位と下位に分割
3 16ビットを32ビットに拡張し、上位と下位に分割
4 32ビット整数を32ビット浮動小数点に変換
5 積演→積和演算→積和演算
6 32ビット浮動小数点を四捨五入して32ビット整数に変換
7 32ビットを16ビットに縮小し、上位と下位を統合
8 16ビットを8ビットに縮小し、上位と下位を統合
9 ストア

・この流れは定石化しそうなので、マクロ化できると良さそう

・CPUのレジスタ数を超えないようにスケジューリングする
・ハンガリアン記述的なアプローチ（変数に型を明記する）だと分かりやすくなる
・Intel SSE/AVXよりもNEONの方が命名規則が分かりやすく、プログラミングしやすい

■OpenBLASにおけるSIMD処理プログラミングのヒント

BLAS・・・基本線形代数サブプログラム
OpenBLAS・・・最適化されたBLASのライブラリ、BSDライセンスで公開されている
（ソースコード https://github.com/xianyi/OpenBLAS）
・使い勝手よりスピードを追求しつつ、かつ汎用性がある

○GEMM（行列と行列の積）の場合
・データ型に合わせて最適化される
-SGEMM（単精度版）
-DGEMM（倍精度版）
-CGEMM（複素数単精度版）
-ZGEMM（複素数倍精度版）
・行列の乗算、転置、スカラー倍、加算を同時に実行し、大域的に最適化できる

・アセンブリコードでの例
-演算カーネルをCPUアーキテクチャやサイズで場合分けする
-マクロなどの定義により同じようなコード列を再利用する
-内側ループを展開して速度の向上を図る

■まとめ
・SIMDは同じ動作をする計算ユニットに並列処理をさせる方式
-CPUのSIMD命令、ベクトル命令、GPUがこれにあたる

・CPUのSIMD命令は固定長のビット幅のSIMDレジスタで演算を行う
・SIMDレジスタのビット幅の違いによる機械語命令の互換性がない
-そのため、SIMD命令のビット幅を変える際にはプログラミングやコンパイルをやり直す必要がある
・ベクトル命令はレジスタ幅が変わってもプログラミングやコンパイルをやり直す必要がない

・SIMD命令を手で記述して最適化を行うと、Auto-vectorizationに比べて2～5倍の高速化効果がある
・Auto-vectorizationを使う場合は、メモリ配置をSoA（配列の構造体）のスタイルにする方が無難そう

・定石パターンをマクロ化すると良さそう
・CPUのSIMD/ベクトルレジスタ数を超えないようにスケジューリングする（メモリへの書き戻しを行わない）
・変数に型を明記するとわかりやすい
・NEONは命名規則が分かりやすく、プログラミングしやすい

・スピードを追求しつつ、汎用性があるようにAPIを設計する
・演算カーネルをCPUアーキテクチャやサイズで場合分けする
・マクロなどの定義により同じようなコード列を再利用する
・内側ループを展開して速度の向上を図る

■最後に
・手動でSIMD命令を書くのは必要最低限にすべき。
・どれほど、どのように再利用されるのかを分析してAPIを設計すべき。
・メンテナンス要員を常に確保する必要がある。
・最新の命令に対応し続けることが必要。SIMD命令を一度書いて終わりではいけない。
・並列処理の長けたElixirのプログラムからSIMD命令・マルチコア並列コードの生成に関する研究会を進めている。

■質疑応答
Q1
変数を型に明記するとあるが、最近はエディタや開発環境がサポートしてくれるものも多い。今回の場合はサポートはあるのか。
A1
あるにはある。だが、同じものを表すものの、型が違う変数が出てくるため、変数名を変えないと区別できない。

Q2
ベクトル命令に関して、ベクトル化することでキャッシュのヒット率・効率がよくなるなどの効果はあるのか。
A2
あると思う。複数ポインタによるキャッシュの衝突などがあって効率が良くなっているというのが可能性として考えられる。これを示すにはキャッシュのヒット率を解析する必要がある。

Q3
サンプルでのRGB読み込みをより最適化する手法はないか。
A3
ロードの時に一定のビット数で区切ってまとめてロードすることで最適化を図っている。これ以上最適化を図るなら、ライブラリを作るか、Cではない言語を使うしかない。
現在はNumPyに準ずるコードや、ある程度のデータをデータ構造としてひとまとまりにして、それをアセンブリ言語に直接生成するという手法を考えている。

Q4
現在作られているNumPyに準ずるコードでまだ足りない部分はあるか。
A4
機械学習の上位で用いていたデータ構造をElixirにそのまま移植できるようなものを作っている。pythonで積み上げられた考え方をElixirに差し替えられるようにしたい。

Q5
並列性を出す際に、リストやタプルなどの集合的なデータを並列化していくと思うが、ElixirVMとvectorizationを上手いこと合わせつつ実現できそうなのか。
A5
できると考えているが、整合性などについて研究・検証の最中である。ErlangVMは大きなバルクのデータを持つには不向きなので、そこを検証していく必要がある。

Q6
自分で書いたライブラリを呼ぶのと、GPUにオフロードするのは手間は変わらないと思ったがどうなのか。
A6
GPUへのオフロードは実現済みだが、メモリ転送やコンパイルに時間がかかるなどの欠点がある。小さなデータの処理はCPUで行うと行った、CPUとGPUでの分業を行うのが理想的だと考えている。最適な配置を求められるくらいに研究が進めば望ましい。