English

並列アルゴリズム

1個のプロセッサに複数のコアを搭載したマルチコアプロセッサが普及し、パーソナルコンピュータでさえも並列計算機として利用できるようになりました。そこで、ディペンダブルシステム学研究室では、マルチコアプロセッサを効率よく利用する並列アルゴリズムを研究しています。

マルチコアプロセッサでは、コア内部の処理に比べ外部メモリへのアクセスが低速であるため、多段のキャッシュなど階層的なメモリ構造を用いるのが一般的になっています。下の図で、L2は外部メモリより高速にアクセスできる全コアが共有するキャッシュで、L1はより高速な各コア専用のキャッシュです。各コアは、一度アクセスしたデータをキャッシュに格納し、キャッシュに格納したデータには高速にアクセスすることが可能です。しかし、高速なキャッシュに格納できるデータ量には限界があり、古いデータや他プロセスがアクセスしたデータはキャッシュからアクセスすることはできません。

マルチプロセッサを効率よく利用するには、キャッシュを効率よく利用することが重要です。そのためには、データ構造や処理の並列化などキャッシュの動作を考えて、並列アルゴリズムを設計する必要があります。