行列積高速化の心構え

こんにちは。やまもとです。

noteで書いていた記事「行列積計算を高速化してみた」があまりにも長いので、今後、ポイントをまとめて行きたいと思います。実際に、高速化していく方法やサンプルコードは、noteの記事をご覧ください。noteの記事では、インテル製CPUを搭載したMacBook Proで、理論上の最高FLOPSの95~97%ほどの速度が出ました。OpenBLASと比べると3~4%ほど低い結果とはいえ、このくらいの速度を出すノウハウはウェブで検索しても見たことがありません。noteの記事は有料なので全部を見る人は少ないでしょうが、日本の技術力の底上げにつながれば嬉しいです。

今回は、やまもとが行列積計算を超高速化したときの、思考法というか心構えを書いてみたいと思います。この心構えは、行列積計算以外の超高速化作業でも、同じかもしれません。

1 心構えのリスト
2 まとめ

心構えのリスト

経験上、行列積のような高速化を考える場合、通常のプログラミングとは違う考え方が必要だと思っています。やまもとの場合、どのように考えているかを列挙してみると次のようになりました。

コードの可読性は諦める
コードの可搬性は諦める
コンパイラの最適化は非効率と考える
はじめからアセンブラを意識する
余分なメモリアクセスを徹底的に排除する
キャッシュメモリを最大限に利用する
高速化の途中でスピードが落ちてもそのまま突き進む

以降では、各項目について説明します。

コードの可読性は諦める

通常のシステム開発だと、誰が見ても分かるように、コードの可読性はとても重要です。これは、最初のプログラム開発者と、後にメンテナンスやアップデートを行う開発者が異なるためです。一般的に、他人の作ったプログラムは、解読にとても時間がかかります。もし、コードの可読性が低いと、メンテナンスや緊急対応時に解読に時間がかかり、素早い対応をできなくしてしまいます。これは、とても非効率です。

しかし、可読性を維持したまま高速化するのは、限りなく難しいプログラミングになります。やまもとの感覚では、不可能だと思います。そのため、高速化を追求する場合は、可読性を犠牲にするしかありません。常識的なプログラマーなら、これはちょっと嫌な感覚ではないでしょうか？でも、仕方ありません。そうしないと速くならないのです。

コードの可搬性は諦める

通常のソフトウェア開発では、どんなコンピュータでも動作するソフトウェアが理想的です。そうでないと、コンピュータごとにプログラムを開発し直さなければならず、開発費用や開発期間が余計にかかってしまいます。これを回避するため、Java言語ではコンピュータの違いを吸収するバーチャルマシン（JavaVM）を使用していますし、LLVMのようなコンパイラ開発環境では抽象木からマシン語に変換する部分を抽象化しています。歴史的にみると、プログラミング言語は抽象度を上げていく大きな流れがあり、最近ではコードすら不要なNoCodeサービスによってソフトウェアを開発するようになってきています。

しかし、極限の高速化は、コンピュータの機能を最大限活用しなければ達成できません。逆に、可搬性を維持するには、各コンピュータの共通機能しか使えないため、最大限に活用することを犠牲にしなければなりません。このようなトレードオフがあるため、高速化する場合は可搬性を諦めざるをえません。これも、プログラマーにとっては嫌な感覚だと思います。

コンパイラの最適化は非効率と考える

コンパイラは、ソースコードを実行ファイルにコンパイルするとき、プログラムが高速に動作するように最適化してくれます。ほとんどのコンパイラでは、-O2とか-O3とオプションを指定することで、最適化の程度をコントロールすることができます。

しかし、コンパイラにはできない最適化があります。それは、計算結果を変えてしまう恐れのある改変です。例えば、ループ内部で行っている処理をループ外部に移動するといった変更は、人間の目で見ると可能な変更でも、ソースコードだけからは判断が難しく、計算結果を変えてしまいかねないためコンパイラはなかなかできません。このようなアグレッシブな最適化を行うオプションを持つコンパイラも存在しますが、コンパイラ依存になってしまうため、いつも効率的なプログラムになるとは限らなくなってしまいます。

はじめからアセンブラを意識する

Pythonなどのインタープリタ言語やJavaのようなバーチャルマシンを使った言語、C言語のような高級言語でプログラミングする場合、アセンブラ言語を意識することはほとんどないでしょう。ソフトウェア開発を効率的にするためには、人間には理解し難いマシン語やアセンブラ言語を、人間が理解しやすいプログラミング言語にした方が良いに決まっています。これは、人間が理解し難い部分をインタープリタやバーチャルマシンやコンパイラが担当し、見えなくしてくれていることで実現しています。

しかし、高速化のためにコンピュータの機能を最大限使用しようと考えると、CPUの機能を直接指定できるアセンブラ言語のレベルで考えていく必要があります。そうすると、命令セットアーキテクチャ（ISA）やレジスタ、パイプライン、さらにはCPUの中で行われる処理といった知識が必要になってきます。そのため、極限の高速化は、プログラミングスキルとCPUの知識とCPUを最大限活用するノウハウが必要になり、一般のプログラマーよりは高度なスキルが要求されます。

余分なメモリアクセスを徹底的に排除する

一般的に、「パソコンはメモリを増やせば処理が速くなる」と考えられています。これはメモリ容量が増えることで、メモリ上のデータをストレージに一時退避するページング処理が少なくなることで、体感上の処理速度が上がることに起因しています。これに対し、メモリアクセス速度は、メモリ容量が増えるとデータを探す手間が増えるため、一般的には遅くなります。

また、CPUの処理速度がナノ秒レベルなのに対し、メモリアクセス速度は数百ナノ秒もあり、CPUの処理速度に比べて極端に遅いことが多いです。そのため、CPUは高速なキャッシュメモリ階層を搭載しています。キャッシュメモリの容量が小さいのは、前述の通り、容量が増えるとアクセス速度が遅くなるためです。

CPUから見るとメモリは物凄く遅い（これを「遠い」と言います）ため、メモリアクセスは高速化の一番の障害になります。そのため、必要最小限のメモリアクセスになるように、余分なメモリアクセスは徹底的に排除する必要があります。逆に言うと、メモリアクセスを最小限にするだけでも、そこそこ高速化することができます。

キャッシュメモリを最大限に利用する

現代のCPUは、メモリアクセス速度の遅さを軽減するために、キャッシュメモリを２〜３階層で搭載しています。キャッシュメモリは、メインメモリより近くに設置されていて、キャッシュメモリ上にデータがあるとメインメモリまでアクセスしないですむため、データの取り出しが高速になります。遠くの倉庫に行くより、近くの倉庫から荷物を持ってくる方が早いのと同じことです。ただし、その容量は比較的小さく、基本的に保持するデータを選択することができません。これは、malloc関数なので明示的に保持するデータを指定できるメモリ（メインメモリ）とは対照的です。

キャッシュメモリは新しいデータが必要になると古いデータを消してしまうため、キャッシュメモリが保持するデータを何度も再利用するには、キャッシュメモリ容量に合わせてデータサイズを制限する必要があります。また、キャッシュメモリでは、キャッシュラインという直線的データ単位で保持しているため、キャッシュラインに沿ってデータを使うようにすると高速化されます。例えば、ランダムアクセスと呼ばれるメモリアクセスが必要なアルゴリズムは、このキャッシュラインを全く有効利用できないため、極端に遅くなります。

高速化の途中でスピードが落ちてもそのまま突き進む

やまもとの経験上、高速化のためにプログラムを改変をしても、速度が変わらなかったり、逆に遅くなってしまったりすることがあります。このとき、多くの場合、その改変は間違っていたと判断して、別の改変を試みたり、諦めてしまうようです。しかし、そのまま突き進むと、突然スピードアップすることがままあります。

例えば、スピードを遅くしている原因（ボトルネック）が複数あった場合、一つのボトルネックを解消しても、全体のスピードはほとんど変化がありません。しかし、そのまま突き進み、全てのボトルネックを解消した瞬間、一気にスピードが上がります。

また、現状のアルゴリズムを大きく修正した場合、最初は元のアルゴリズムに比べて遅くなることもあります。しかし、そのまま突き進むと、大きく変更したおかげで、元のアルゴリズムの限界を超えて、スピードがグッと上がることもありました。

しかしながら、「ボトルネックがいくつあるのか」や「変更したアルゴリズムで本当に速くなるのか」は、予め知る方法がありません。そのため、理論を拠り所として「理論上は速くなるはず」という信念を貫き通す必要があります。