メモリジャンプと高速化

高速化プログラミング   
トップ  > メモリジャンプと高速化

メモリジャンプと高速化

■ メモリと高速化

メモリと高速化とは関係なさそうですが、実はCPUの演算よりメモリアクセスのスピードの方が断然遅いです。メモリアクセスが頻繁に行うと、とんでもない遅いプログラムになります。メモリアクセスは遅いといっても、最近のコンピューターにキャッシュメモリが搭載されているので、注意してプログラミングすればメモリアクセスによる実行速度の低下は避けられます。ここではそれについて解説します。まずキャッシュメモリを含めてメモリの種類から説明します。

■ メモリの種類

コンピューターに使われるメモリは表1のように主に4種類に分けられます。レジスターはCPU内にあり、アクセスがとても速いですが、容量は数Byte~数十Byteです。レジスター内のデータしかCPUの演算の対象になりません。高水準言語ではプログラムを書くときは気にする必要はありませんが、コンパイラーがそのプログラムを機械語に翻訳するときは実は必要なデーターを一々メインメモリからレジスターに移動して、演算を行い、その後、またメインメモリに移動させています。

キャッシュメモリについては後述します。

RAMはコンピューターのメインメモリであり、メモリをいうときは一般的にRAMを指します。プログラムを実行するときに必要なデータをすべてRAMに置きます。容量は様々ですが、最近は数GBのものが一般的です。アクセススピードはハードディスクより断然速いですが、レジスターよりは遅いので、表1では中速と書いておきました。

ハードディスクのような外部メモリは容量が非常に大きく、あらゆるデーターを保存できます。アクセススピードはもっとも遅いです。

表1 メモリの種類とその特性
メモリの種類 容量 スピード
レジスター 数Byte 超高速
キャッシュメモリ 数 MB 高速
RAM 数 GB 中速
ハードディスク
(外部メモリ)
数 TB 低速

何かプログラムを実行するときのデータの流れを説明しましょう。まずハードディスクにあるプログラムの機械語やデータをRAMにロードします。RAMにあるプログラムの機械語に従ってデータをレジスターに移動して演算を行いその結果をRAMに戻します。プログラムの実行中は主にRAM⇒レジスター⇒演算⇒レジスター⇒RAMの処理の一連がずっと続いています。

さてCPUの演算処理速度は数GHzに対してRAMのアクセス速度は数百MHz程度です。つまりCPUの演算速度に対してメモリアクセスが非常に遅いわけです。CPUが演算する前に一度RAMからレジスターにデータを移す必要があるので、いくら速いCPUを使ってもプログラムの実行速度はメモリアクセスのスピードに支配されてしまいます。CPUのスピードとメモリのアクセススピードのギャップを埋めるためにキャッシュメモリが登場します。

キャッシュメモリ(cache memory)は容量がRAMよりは少ないですが、アクセススピードはRAMより速いです(高速なので値段も高いため、多くは積めません)。RAMからレジスターへのデータの橋渡しの役割をしています。実際コンピューター内ののデータの流れはRAM⇒キャッシュメモリレジスター⇒演算⇒レジスター⇒キャッシュメモリ⇒RAMとなるわけです。キャッシュメモリはプログラムの実行速度を高めるためですが、上記のデータの流れではRAMのアクセスが残っていない限り、キャッシュメモリを使用する意味がないように見えます。確かにそうです。しかしキャッシュメモリには別の仕組みが施され、そのおかげでプログラムの実行速度は高められます。この仕組みについて次に説明します。

■ キャッシュメモリの役割

CPUがデータを要求するときはRAMからレジスターに移す前に一時的にキャッシュメモリに保存されます。しかしキャッシュメモリに保存されるのは要求されたデータだけではなく、その前後のデータも一緒にキャッシュメモリに保存されます。この仕組みがあるから、プログラムの実行速度が速くなるのです。

絵を使って説明しましょう。図1にはキャッシュメモリを使用しないときのデータの流れを示します。今RAMにサイズが10の配列があるとします。CPUが次々とA1, A2, A3を要求すると、RAMから次々とA1, A2, A3がレジスターに移されます。このとき(遅い)メモリアクセスが3回発生します。

キャッシュメモリなしのデータの流れ
図1 キャッシュメモリなしのデータの流れ

次にキャッシュメモリを使用するときのデータの流れを図2に示します。キャッシュメモリの容量は4個とします。初期状態は図1と同じですが、CPUがA1を要求するときはA1だけではなく、その後ろのデータも合計4個のデータがキャッシュメモリに保存されてから、A1をレジスターに移動されます。このときはメモリアクセスは1回発生します。次にCPUがA2を要求すると、キャッシュメモリにA2が既にあるので、RAMからではなくキャッシュメモリからA2を読み取ります。そのため、高速でデータをレジスターに移せるわけです。A3が要求されるときも同様です。データを3つ要求されましたが、メモリアクセスは実質1回しか発生しません。これでプログラムの実行速度は高められる仕組みです。

キャッシュメモリありのデータの流れ
図2 キャッシュメモリありのデータの流れ

■ メモリアクセスのジャンプがあったら

キャッシュメモリを最大限に利用できればプログラムの実行速度が高められますが、キャッシュメモリが無力なときもあります。それはメモリアクセスにジャンプが頻繁に起こるときです。それを図3を使って説明します。

メモリジャンプが起こるときのデータの流れ
図3 メモリジャンプが起こるときのデータの流れ

例えばA1, A5, A10と飛び飛びしたデータが要求されているとします。A1が要求されたときはA1からA4までキャッシュメモリに保存されます。次にA5が要求されたときはA5がキャッシュメモリにないので、RAMからA5を読み取るしかありません。このときA5と一緒にA8までキャッシュメモリに保存されます。今度A10が要求されると、またそのデータがキャッシュメモリにないので、再度RAMの読み取りが発生します。このようにキャッシュメモリがあるにもかかわらず、3個のデータの要求で3回のメモリアクセスが発生してしまい、キャッシュメモリがないときと変わりません。(実際キャッシュメモリを経由させる分、余分に時間が掛かります。)

キャッシュメモリを有効にするためにメモリアクセスのジャンプを避けなければならないことは分かりました。しかしデータがメモリにどのように配置されるかコンパイラーしか分かりません。配列ならメモリ上の連続的なアドレスに配置されることは分かりますが、よほど特殊な場合を除いて通常、配列のメンバーを順番にアクセスするので、メモリアクセスのジャンプが起こりにくいです。ではメモリアクセスのジャンプは気にしなくても良いではないかと考えがちですが、油断は禁物です。次の例では間違ったコードの書き方をすると、50倍程度プログラムの遅くなるという実測結果が出ています。



はじめに

演算数を減らす

メモリジャンプを減らす

高性能のアルゴリズム

その他



3 4 9 0 1 1