UNIXシェルの並列化により最大34倍高速化する「PaSh」、米MITなどが開発 プログラム結果も正確：Innovative Tech

[山下裕毅，ITmedia]

Innovative Tech：

このコーナーでは、テクノロジーの最新研究を紹介するWebメディア「Seamless」を主宰する山下裕毅氏が執筆。新規性の高い科学論文を山下氏がピックアップし、解説する。

　米ペンシルベニア大学、米MIT、ポーランドのXIV Staszic High School、米国の研究機関Aarno Labs、米Stevens Institute of Technologyによる研究チームが開発した「Practically Correct, Just-in-Time Shell Script Parallelization」は、UNIXシェルで実行されるプログラムの速度を精度を保証しながら劇的に加速させるシステムだ。

　このシステムはUNIXシェルにおいて、スクリプトを先読みして並列化を行う。これによりプログラム結果を正確な上で最大34倍高速化し、Webインデックスや自然言語処理、データ解析などのタスクを実行することが可能になる。

プログラムを並列化することにより、UNIXシェルで実行されるプログラムの速度を上げる技術を作成した

　「PaSh」と呼ぶこの新しいシステムは、現在でも広く使われているプログラミング環境であるUNIXシェルで実行されるプログラムを高速化するものだ。

　シェルスクリプトを正しく並列化することは、何十年にもわたって研究者が取り組んできた茨の道である。UNIXシェルは多言語スクリプトを可能にするが、その柔軟で動的な構造のため、従来の手法では並列化が困難であった。

　プログラムの並列化は、ある部分が他の部分に依存しているため、コンポーネントの実行順序が決められており、順序を間違えるとプログラムが失敗してしまう。

　プログラムが単一の言語で記述されている場合、ユーザーはその機能と、並列化できるコンポーネントを決定するのに役立つ言語に関する明確な情報を持っているが、UNIXシェルのスクリプトには存在しない。ユーザーは、コンポーネント内で何が起こっているかを簡単に確認したり、並列化に役立つ情報を抽出したりすることができないわけだ。

　この問題を解決するために、PaShは前処理として、並列化可能だと思われるコンポーネントに簡単な注釈を挿入し、プログラムの実行中に各構成要素に到達した瞬間に、その部分の並列化を試みる。

　これによりプログラムの動作を事前に予測することができ、上記問題を解決に導く。このようにプログラムの構成要素を“ジャストインタイム”で並列化することで、事前に並列化しようとする従来の手法に比べて、より多くのコンポーネントを効率的に高速化できる。

　その一方で、速くできても正確でなければならない。研究チームは古典的なプログラムから最新のプログラムまで、数百のスクリプトでPaShをテストし、1つも壊れないことを実証した。また並列化されていないスクリプトと比較した場合、平均で6倍、最大で34倍近く高速化できることが確認された。

Source and Image Credits: Konstantinos Kallas, Tammam Mustafa, Jan Bielak, Dimitris Karnikis, Thurston H.Y. Dang, Michael Greenberg, and Nikos Vasilakis.“Practically Correct, Just-in-Time Shell Script Parallelization”