Graph Drawing

最近グラフ描画に興味が出てきた。興味が有るといってもDAG限定だけれど。

 

GraphVizのdotとかdagre.jsとかMSAGLとか色々ソフトはあるんだけれどノードとエッジの数が増えるとレイアウトが完了するまでに非常に時間が掛かる…。並列計算が難しい分野なのだろうか？

 

https://www.youtube.com/@PhilippKindermann/videos

色々なグラフのアルゴリズムについて解説する動画がある。ありがたい…。

 

http://graphdrawing.org/

研究者向けのサイトみたい。

 

CUDA SharedMemory

CUDAのSampleにimmaTensorCoreGemmというのがあり、CUDA 10から導入されたWarp Matrix Multiply and Accumulate (WMMA) APIを使ってuint8_tのGEMM演算を行っている。

github.com

SharedMemoryのサイズが一定以上なら compute_gemm_imma という kernel を呼び出し、そうでないなら simple_wmma_gemm_imma を呼び出す。自分が今使っている環境だと compute_gemm_imma を実行する場合は 110TOPS ぐらい出るけれど、simple_wmma_gemm_imma を実行する場合は 30TOPS ぐらいしか出ない。という事で shared memory を使わないで global memory だけだと演算器の性能を引き出せていない事が確認出来た。

async-copy を使えばもっと性能を引き出せるんだろうけど、CUDA Toolkit 11.2 時点では使われていない。bf16TensorCoreGemm では使われているので是非 immaTensorCoreGemm でも使うようにしてほしい。なお bf16TensorCoreGemm では以下のような処理性能になった。

コマンドライン引数 selected_kernel TOPS
kernel=0 bf16mma_shmem_gemm_async_copy 52.68
kernel=1 bf16mma_shmem_gemm 49.48
kernel=2 simple_bf16mma_gemm 14.64

実行するとグラフィックボードのファンが勢い良く回転するのでブーストクロックによって数値は少し変動しそう。

実行結果から判断できるのはやはり Shared Memory を使わないと性能は引き出せないという事と、async-copy を使う事で僅かに性能を改善出来る事。async-copy の効果が想像していたより少なく感じるけど、消費電力を改善する効果があるという事なので使えるなら使った方が良いだろう。

wccftech.com

の記載によると Peak INT8 Tensor TOPS は 284/568 という事だけれど実際に自分の環境でサンプルを動かすと110TOPSくらいしか出ないので演算器のピーク性能を引き出すプログラムを書くのは簡単ではなさそう。なおサンプルコードのGEMMのTOPSの算出式は M×N×K×2÷処理時間の秒÷1e12

CUDA 非同期コピー

developer.nvidia.com

CUDA 11.1 からグローバルメモリからシェアードメモリにコピーする際に非同期コピーが使えるようになった。今までのやり方ではレジスタを経由していたようだ。ちょっとDSPのDMA転送っぽいけどglobalからsharedへの一方通行だったり多次元転送に対応していなかったりL2,L1 Cacheを経由したり等の違いは気になる。とはいえ演算と並行してメモリ転送が行えるのでストール対策として良さそう。Ampere以降のアーキテクチャでしか使えない新しい機能なので、これもCUDA 11.2 で追加された Stream Ordered Memory Allocator のように性能を出来る限り無駄なく引き出したい用途向けな気がする。

CUDA

前書き

久々にNVIDIAのCUDAを使う事になったので色々と使い方を調べて知識を更新する事にした。開発者向けの資料は https://docs.nvidia.com/cuda/index.html

なおCUDAの初期版がリリースされたのが June 23, 2007; 13 years ago らしい。

  

NVIDIAのGPUと同じような演算性能のハードウェアをPCで扱うとなるとAMDのGPUをROCmで扱うのだろうけどそちらはまだ扱った事が無い。資料は https://rocmdocs.amd.com/en/latest/

 

Intelも来年にXe-HPGのGPUをリリースするみたいだけれど10年後に継続しているだろうか？oneAPIのData Parallel C++という言語でコードを書くようだ。CPUやFPGA向けにも同じ言語やAPIを使えるらしい。

 

CUDAのAPIには Runtime API と Driver API が存在していて Driver API の方がローレベルなAPIで Runtime API は Driver API を使って実装しているらしい。

https://stackoverflow.com/a/254521

 

tech-blog.optim.co.jp

上のページに分かりやすくまとめられていた。

調査

自分の理解を深めるために色々なAPIを調査してメモをしていく。ほぼレファレンスに書かれている事の和訳になってしまうけれど…。

 

現時点で最新の CUDA Toolkit v11.2.0 が参照元。

5. Modules

色々なモジュールがあるので気になるものについてメモ。メモリ関連について今のところ一番気になるけれどその他についてはまだまださっぱりな状態。

5.1. Device Management

デバイス管理用のAPI

5.3. Error Handling

エラー情報の取得

5.4. Stream Management

ストリームの管理用API

5.5. Event Management

イベント管理用API

5.7. Execution Control

実行制御用

5.9. Memory Management

この中からメモリ確保用のAPIについて列挙してみる。

  • cudaMalloc
  • cudaMalloc3D
  • cudaMalloc3DArray
  • cudaMallocArray
  • cudaMallocHost
  • cudaMallocManaged
  • cudaMallocMipmappedArray

  • cudaMallocPitch

一番基本的なのは cudaMallocでこれはデバイス側にメモリを確保する。ホストとデバイス間でメモリ転送をするには cudaMemcpy を呼び出して明示的に行う必要がある。

 

cudaMalloc3D は3次元のサイズまで指定して確保する事が出来る。デバイスのメモリアライメント制約を考慮した確保をしてくれるので2Dや3Dの確保を行う場合にはこれか cudaMallocPitch を使う事が推奨されている。

 

cudaMallocArray はCUDA配列を確保するAPIでテクスチャメモリを確保する為に使うようだ。

 

cudaMalloc3DArray は cudaMalloc3D のCUDA配列版だろうか？テクスチャメモリを使いたい場合に使用するのかな？

 

cudaHostAlloc はホストにページロックしたメモリを確保するAPIで malloc で確保したメモリと比べると cudaMemcpy によるメモリ転送が高速に行える。

 

cudaMallocManaged は CUDA6 から導入された Unified Memory という仕組みで管理されるメモリを確保するAPIが存在する。お手軽そうだけど複数GPU構成の時には色々と注意が必要そう。

developer.nvidia.comに性能を引き出すための解説が書かれていた。

 

cudaMallocMipmappedArray はMIPMAPされた配列を確保する。

 

cudaMallocPitch は2D画像用で行アライメントを取ったメモリ確保を行う。

 

次にメモリ転送用のAPIについて列挙する。

  • cudaMemcpy
  • cudaMemcpy2D
  • cudaMemcpy2DArrayToArray
  • cudaMemcpy2DAsync
  • cudaMemcpy2DFromArray
  • cudaMemcpy2DFromArrayAsync
  • cudaMemcpy2DToArray
  • cudaMemcpy2DToArrayAsync
  • cudaMemcpy3D
  • cudaMemcpy3DAsync
  • cudaMemcpy3DPeer
  • cudaMemcpy3DPeerAsync
  • cudaMemcpyAsync
  • cudaMemcpyFromSymbol
  • cudaMemcpyFromSymbolAsync
  • cudaMemcpyPeer
  • cudaMemcpyPeerAsync
  • cudaMemcpyToSymbol
  • cudaMemcpyToSymbolAsync

数が多いのでそれぞれについて調べてメモするのは諦める。非同期系の転送はストリーム関連のAPIと組み合わせて使う事になると思う。

 

メモリ設定系のAPIは以下の通り

  • cudaMemset
  • cudaMemset2D
  • cudaMemset2DAsync
  • cudaMemset3D
  • cudaMemset3DAsync
  • cudaMemsetAsync

引数で各バイトを初期化する値を指定出来る。

5.11. Stream Ordered Memory Allocator

developer.nvidia.com

CUDA 11.2 で追加されたAPIなので使いどころは限られているような気がする。最先端で性能を引き出したい用途向けだろうか…。

ストリーム指定があるAPIで初回の cudaMallocAsync 呼び出しではOSからメモリ確保を行い、cudaFreeAsync 呼び出しのメモリ解放の際はOSに返却せずにCUDAのドライバによって管理されるメモリプールに片づけて、次のcudaMallocAsync 呼び出しでメモリプールから再利用が可能なら再利用を行う。

5.27. Texture Object Management

テクスチャは書き込み専用

5.28. Surface Object Management

サーフェスは書き込みも行える

5.29. Version Management

ドライバとランタイムのバージョン取得用

5.30. Graph Management

x.momo86.net

なにやらストリームをグラフとして記述し実行する機能のようだ。

developer.nvidia.com

複数のカーネル実行の手続きをCPUから一まとめで行えるようにする事でオーバーヘッドを削減する事が出来るとの事。CUDA 10 から使えるようになった機能で一般向けのGPUだとGeForce RTX 2080 Ti とかのGeForce 20 seriesが該当する。これも新しめの機能なので性能を引き出したい最先端の用途向けな気がする。GeForce GTX 1080 Ti の演算性能もまだまだ十分に高いと思うので少し古めのGPUでも動くように対応しておいた方が良さそうな気はする。

5.31. C++ API Routines

C++ template関数群。

5.32. Interactions with the CUDA Driver API

Driver APIとRuntime APIの間の色々なやり取りについて

5.35. Data types used by CUDA Runtime

CUDA Runtimeによって使われるデータ型が列挙されている。

struct、union、Cプリプロセッサの#define、typedef、enum

ここよりヘッダファイル見たほうが良いかも？

雑感

CUDAのAPIは歴史と共に色々と積み重なっていて単純明快とはいえないと思う。デザインが破綻しないように見直しはきちんと行っているようで色々と [DEPRECATED] されているのはそれの表れだろうか…。

 

当初DirectXやOpenGLのハードウェアアクセラレーションをするのがGPUの目的だったけれど、平行投影でPixel Shaderを使えば汎用の演算用途にも使えると色々な人が気づいてGPGPUというアイデアが提唱されて少ししてからCUDAが登場した。汎用CPUで処理するのには荷が重い演算を一般人が購入出来る価格帯のGPUで行えるように開発用のツールキットが整備されている状況はありがたい。

TI C7000 情報

Texas Instruments の C6x シリーズ DSP の後継の C7x について、インターネットで収集した情報を記載する。

 C6x シリーズの中でも KeyStone アーキテクチャの C66x コアを載せたDSPの性能は周波数やコア数によって違うけれど、9.6 ～ 179 GFLOPS だそうだ。QMPYSP という命令が 4 個の単精度浮動小数点数の乗算を行えて、M1とM2ユニットそれぞれで実行できるので1クロックに8個の乗算が出来るとすると、600 MHz × 8 だと 4800 MFLOPS なので、乗算だけじゃなくて L1,L2,S1,S2 ユニットで行う DADDSP 命令での加算もカウントしているようだ。メモリから値を読み書きする LDDW と STDW 命令はそれぞれ 8 バイトの読み書きが出来て D1,D2 ユニットで行うので 1 クロックで合計 16 バイトの読み書きが出来る。1クロックに読み込み 8 バイト & 書き込み 8 バイトとかも可能。

1クロックにVLIWでパックして発行出来る命令数は最大 8 命令。なので演算 6 命令もコンスタントに発行しつづけられるわけはなく、「レジスタに読み書きする値を置きっ放しの完全な理論値です、本当にありがとうございました。」的な数値だろう…。実性能はよっぽどカリカリチューニングしないと半値八掛け二割引き。それはともかくこのプロセッサ、融合積和演算命令が無いのが勿体ない…。

http://www.ti.com/processors/digital-signal-processors/c6000-floating-point-dsp/overview.html

https://e2e.ti.com/support/processors/f/791/t/485503?About-the-GFLOPS-number-of-C66x-DSP-

C66x の登場時期を把握していないけれど2010年頃なのかな？製造プロセスは 28nm らしいので、ハイエンドのスマフォに使われるチップが 7nm で製造されている事を考えると電力性能比的にどんどんと時代遅れになってきている。絶対的な性能に関しても、もうすぐ2020年になるんだし 1TFLOPS 以上の性能の製品をリリースしないと GPU や DSPブロックをたくさん積んだFPGAへの置き換えが進んでしまうと思う。

さてTIの次世代DSPの C7x の予想話に戻ると、まもなく 2019年の10月になるけれどC7000 のコード生成ツールのドキュメントがリリースされていた事が最近分かった。

http://www.ti.com/tool/C7000-CGT

まだISAの情報が載ったドキュメントが無いけれど、PCホスト環境でエミュレート実行とかが出来るようにしてるらしい。intrinsics 用のヘッダファイルも色々あるけどなんか記述が中途半端に思えるのは気のせいだろうか？ 公式のドキュメントから読み取れる事は色々あるけれど、詳しい内容が知りたいので下記の特許情報を参照する事にした。

United States Patent Application Kind Code Title
20190095204 A1 Cache Management Operations Using Streaming Engine
20180322061 A1 Streaming engine with compressed encoding for loop circular buffer sizes
20190095205 A1 Cache Preload Operations Using Streaming Engine
20190073222 A1 Streaming engine with cache-like stream data storage and lifetime tracking
20170153959 A1 Streaming engine with deferred exception reporting
20180246855 A1 Reconfigurable matrix multiplier system and method
20180253402 A1 Implementing Fundamental Computational Primitives Using A Matrix Multiplication Accelerator (MMA)
20180246855 A1 Reconfigurable matrix multiplier system and method
2018126099 A1 Streaming engine with separately selectable element and group duplication
20190243646 A1 Variable Latency Instructions
20190188151 A1 Two address translations from a single table look-aside buffer read
20190187986 A1 Transposing a Matrix Using a Streaming Engine
20190187903 A1 Streaming engine with fetch ahead hysteresis
20190171455 A1 Streaming engine with stream metadata saving for context switching
20170168898 A1 Streaming engine with error detection, correction and restart
20190102178 A1 Converting a Stream of Data Using a Lookaside Buffer
20180322061 A1 Streaming engine with compressed encoding for loop circular buffer sizes
20190026111 A1 Dual data streams sharing dual level two cache access ports to maximize bandwidth utilization

依存性の管理

モジュールの中の要素の調整でファイル更新をすると依存関係の巻き添えが起きて大分待たされる事になって辛い。
コンパイラがEntity単位で内容が更新されたかどうかとそれぞれの依存性を把握していれば防げるのだろうか？
まぁそんなのは夢物語だからファイル分割を気を付けるべきなんだけど…。

 

リンク時最適化が上手く効いてくれるならヘッダにコードを置く必要性が薄くなるかも？でもこれも期待薄だろうなぁ。。人が工夫を凝らす事で詰め込む事は出来るんだろうけど試行錯誤しやすくするのにも知恵が必要だ…。

 

C++ の module について思い浮かんで検索したら下記のサイトがヒットした。

https://vector-of-bool.github.io/

 

依存関係はグラフで図示すれば分かりやすいのかもしれないけれど、色々な切り口があるからどう表現すれば良いのだろうか？

 

ノイマン型アーキで人間が試行錯誤して作り上げたものはなかなかに複雑で立派だけど、この方向性でずっと行くべきなのかというと躊躇する。

 

何かしらの僅かなコストと引き換えに手間を大きく省けるならそこに価値が生まれるのでうまいやり方を見つけたい。

 

 

BeagleBoard x15

BeagleBoard x15 を購入した。

https://beagleboard.org/getting-started

の説明を読んでセットアップ

SDカードにイメージを焼き込む

まずはSDカードのイメージをダウンロード 

現時点の BeagleBoard x15 の最新イメージは、「Debian 9.5 2018-10-07 4GB SD LXQT」 のようだ。Etcher というSDカードにイメージを書き込むプログラムが紹介されていてそれをインストールする事でSDカードへのイメージの書き込みは簡単に行う事が出来た。

電源について 

ちなみに BeagleBoard x15 は 12V5A(60W) の電源が必要で DCコネクタの規格は 内径 2.5mm 外径 5.5mm のようだ。手持ちのACアダプタに12V5Aのものが無かったので Tosmisy というメーカーのものを 1500 円くらいで購入した。色々なジャックに対応する為に交換可能なプラグが8種類ぐらい付属品で付いてくる。しかし話が逸れるけど、ACアダプタって電圧と電流の組み合わせの分だけ数が多くて嫌になるなぁ。。USB PDで全部賄えるようになったら良いんだけど…。

デバッグケーブル

USB変換COMケーブルはラズパイ用のを購入。

(赤) USB5V
(黒) GND
(緑) TxD ロジックレベル(約3.3V)
(白) RxD ロジックレベル(約3.3V)

となっているようで、ボード側の方は Quick Start Guide の説明を見ると

PIN番号 1 グラウンド
PIN番号 4 受信
PIN番号 5 送信
となっている。PIN1に黒、PIN4に緑、PIN5に白、のメスのジャンパワイヤを挿したら Teraterm で電文が見れるようになった。

CCSで開発

まず新規に Target Configuration File を作成する。

  • Connection に Blackhawk XDS560v2-USB System Trace Emulator を指定
  • Board or Device に GPEVM_AM572X を指定
  • Beagle Board x15 の電源投入もしくはリセット直後に、デバッグケーブルのターミナルで Press SPACE to abort autoboot in 2 seconds と表示されるのでスペースキーを打って Linux 側のブートを止める

上記の手順でC66x DSP用のプログラムをデバッグ出来るようになった。

Linuxと連携

Linux上でDSPと通信するには Processor SDK の IPC を使う必要がある。

http://software-dl.ti.com/processor-sdk-linux/esd/docs/latest/linux/Foundational_Components_IPC.html#ipc-quick-start-guide