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

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)の3倍、割り算(DIV)は足し算の80倍〜90倍ほどかかることがわかります。
インテル ® 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など、高速化のための様々な技術、必要に応じて楽しく使っていきましょう!

2020-06-29 追記、すみません!執筆時、10倍、66倍〜80倍と記述していたのは異なるCPUIDでの比較をしていました(、ご指摘ありがとうございます! @57tggx さん)。
現行のアーキテクチャーを調べて、比較表を作ってみたところ、下記のようになりました。2008年のNehalemでは、掛け算で10倍、割り算で70-80倍でした。2015年のSkylakeで少し遅くなっています。Ice LakeはSkylakeがベースとの記述があるので、この部分は変わっていないのではないかと思います。

アーキテクチャー,ADD,SAL 左シフト,MUL 下位64bit,MUL 上位64bit,DIV Core 65nm (2006),1,1,6,7,-90 拡張 Core,1,1,6,7,- Nehalem (2008),1,1,3,10,70-80 Westmere (2008),1,1,3,10,70-80 SandyBridge (2011),1,1,3,4,80-90 Ivy Bridge (2012),1,1,3,4,80-95 Haswell (2013),1,1,3,4,80-95 Broadwel (2014),1,1,3,4,80-95 Skylake (2015),1,1,4,5,80-95 Intel® 64 and IA-32 Architectures Optimization Reference Manualより)

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