Valgrindによる動的バイナリ変換システム

このページでは鋼システムに関する研究について紹介していきます。

ですので、先に並列実行と鋼システムの簡単な説明を読むことをお勧めします。

自動並列処理システム

逐次プログラムを高速化するためにはスレッドレベルの並列処理が有効です。並列処理を行うためには、マルチスレッドコードと呼ばれる並列処理を考慮した形式で記述されているプログラムが必要ですが、マルチスレッドコードを手動で作成するのは困難です。

マルチスレッドコードを自動的に生成してくれるものに並列化コンパイラがあります。通常のコンパイラは高級言語で記述されたソースコードを入力とし、逐次実行用のバイナリコードを出力します。一方、並列化コンパイラは並列処理向けのバイナリコードを出力します。当然ですが、並列化コンパイラはソースコードを必要とします。そのため、ソースコードがないと並列化ができないということになります。

ではバイナリコードからマルチスレッドコードを生成することができた場合はどうでしょうか？バイナリコードは実行可能なプログラムそのものであり、プログラムの実行に必ず必要となります。つまり、ソースコードを参照できないプログラムでも並列化することができるのです。

当研究室では逐次実行向けバイナリコードから並列実行向けのマルチスレッドコードを自動的に生成するシステムの研究開発を行っています。

簡単に説明すると

• ユーザが並列化のことを意識する必要がない

• ソースコードを必要としない

という特徴を持つシステムです。

Valgrindを使ってバイナリ変換を実現

本システムの実現には、逐次プログラムの機械命令を操作するためのバイナリ変換技術が必要になります。バイナリ変換を行うフレームワークにはいくつかありますが、その中でValgrind(http://valgrind.org/)はオープンソースソフトウェアで主にデバッグやプロファイリングツールとして広く利用されています。特徴として、Linux、MacOS X、Android OSの様々なプラットフォーム上で動作します。可能な限り多くのプラットフォームで自動並列処理を実現すれば、より多くのプログラムを並列化できることになります。そこで、他の同様なフレームワークと比べて対応しているプラットフォームが多いValgrindをシステムの基にしています。

Valgrindは、まず入力として与えられたプログラムを中間表現コードというものに変換し、その中間表現コードに対して命令の追加や削除を行います。そして操作した中間表現コードをバイナリコードに変換します。最終的に生成されたバイナリコードを実行することで、元々のプログラムに追加した処理の情報を得ることができます。

中間表現コードに対して命令の操作を行うのはValgrindのプラグインと呼ばれる部分で、ユーザ独自の処理内容を追加することができます。この中間表現コードは機械命令セットに独立であるので各命令セット向けにプラグインを作成する必要はありません。そのため、普通のパソコンだけでなく、例えばAndroid端末等の様々なプラットフォーム上で実行することが可能になります。

自動並列処理機能の実現

Valgrindには元々並列化の機能はないので、自動並列処理を実現するには以下のような機能が必要になります。

• 並列化コード生成

　本システムでは、バイナリコードを自動的に並列化コードに変換します。この時、実行するプログラムの特徴に合わせ最適な並列処理用コードを生成します。ユーザが独自に追加できるプラグインとして並列化機能を実現することで中間表現コードレベルでの並列化が可能になり、機械命令セットに依存することなく並列化することができます。

• スレッド実行制御

　Valgrind自体は逐次実行を行うものなので、マルチスレッド実行に対応させるためには、新たなスレッドの生成、スレッドに対する並列実行処理の割り当て、各スレッドの演算結果の統合等のスレッドを管理する機能が必要になります。この機能により、複数のスレッドでの並列実行が可能になります。

少し難しい内容ですが、自動並列処理の流れを下図に示します。

このシステム上で実行する逐次プログラムが並列化する部分（ループ）に到達すると、Valgrindのバイナリ変換処理によって中間表現コードに変換されます。次に、並列化機能を追加したプラグインで中間表現コードを並列化します。そして、並列化した中間表現コードをバイナリコードに変換します。このとき生成されたバイナリコードは並列実行に対応しているので、それを複数のスレッドで並列実行します。並列実行が終了したら次の基本ブロックの処理に移ります。