速いプログラムを作る基本は、ループ数を減らすこと、ループ内を軽くすること。

100円のCPUでも1秒間5,000万回計算してくれますが、4K動画に必要な2500万コのLED制御、1コ1計算だとしても1秒間に2コマの紙芝居にしかなりません。 滑らかで美しい映像を計算するためには高速化が欠かせません。

計算で作る美しい映像例「ライフゲーム」、IchigoJamでも「Kubotaさんのライフゲーム - IchigoJam-FAN」にて、高速化チャレンジ中。 100円CPU、Arm Cortex-M0では、足し算、引き算、掛け算と比較して、割り算が150倍遅いことを「IchigoJamマシン語入門」で確認しました。では、普通のPCではどうでしょうか?

MacやWindowsは、Intel/AMDのx64アーキテクチャーが大半です。Intelの資料によると、レイテンシー(ざっくり実行してから結果がでるまでの時間)で、掛け算(MUL)は足し算(ADD)の10倍、割り算(DIV)は足し算の66倍〜80倍ほどかかることがわかります。
インテル ® 64 アーキテクチャーおよび IA-32 アーキテクチャー最適化リファレンス・マニュアル
プログラミング言語、コンパイラーを作る人には必見のこの資料、日本語でここまで用意されているのはスゴイ! ちなみに、ハードウェア除算命令がある Arm Cortex-M3 での掛け算は足し算と変わらず1クロック、除算はその2〜12倍です。(18.2. プロセッサ命令のタイミング - ARM Information Center

どんな環境でもループ内の割り算は少なくするのが得策です。ループ外にもって行けないか、ビットシフトや掛け算で代用できないか検討しましょう。32で割る整数計算は、2進数のビット演算で5bit右にシフトするのと一緒で、速度はどのアーキテクチャーでも1クロックになるのでとても有効です。

掛け算の使用はアーキテクチャーで判断が分かれます。IchigoJamやスマホなど、Armアーキテクチャーでは掛け算が足し算と同様に高速なので、カジュアルに使えますが、PC向けの場合多少命令が増えても、事前計算や、足し算ビット演算などでの代用が有効そう。

IchigoJamでのライフゲーム、1更新が16秒から14.5秒に短縮されたとのこと!Cortex-M0は、構造がシンプルなので速度計算が簡単で、遅い分、効果が体感で分かるのが楽しいです。

ループ内を軽くする手段の一つ、並列化。Intel/AMDのx64には512bitのSIMD命令、AVX-512という512bit(8bit x 32コ)まとめて計算する命令があります。 zmm0〜zmm31という512bitレジスタを使った計算ができるとのことでしたが、残念ながら今使っているMacBookProではちょっと古くて非対応。 AVX2の256bit(ymm0〜ymm15)で足し算(vpaddb = 1クロック)させてみました。(src for Mac on GitHub)

せっかくなら持てる力、フルパワー使いたいですね!もっと長いビット長が計算できるRISC-Vのベクトル拡張も楽しみです。

GPUやFPGAなど、高速化のための様々な技術、必要に応じて楽しく使っていきましょう!

links
- サイズを取るかスピードを取るか、割り算のアルゴリズムとマシン語実装 / IchigoJamではじめるArmマシン語その14
- ハンドアセンブルで高速計算! RISC-V、RV32ICエミュレーターのC言語実装
- MacのGPUでも700倍速! パスワード20文字時代の盾と矛 / さくらクラウドで分散探査する方法
- Macで開発、FPGAで作る4bit学習用CPU「GMC-4」 - Parallels x Ubuntu x Quartus x Verilog

Tweet
クリエイティブ・コモンズ・ライセンス
この作品は「Creative Commons — CC BY 4.0」の下に提供されています。
CC BY / @taisukef / アイコン画像 / プロフィール画像 / RSS