Grid環境における適応型スケジューリングの検討

全文

(1)2004−EVA−10 （5）. 社団法人情報処理学会研究報告 IPSJ SIG Technical Report. 2004／8／1. Grid 環境における適応型スケジューリングの検討井上悠佑 † , 小板隆浩 †† , 福田晃 † ゲノムアプリケーション InterProScan は，たんぱく質シーケンスの解析に広く利用されている．しかし，多数のたんぱく質シーケンスを複数のツールで解析には膨大な処理が必要とされるため， Grid 環境のような大規模な処理環境が必要とされる．我々はこれまで，InterProScan を対象として，多数の計算機を有効に利用可能とするスケジューリング機能を実装してきた．しかし，これまでの評価結果から， 1 つのスケジューリング方式に固定するのではなく，Grid 環境の状況に応じて，スケジューリング方式を使い分ける方策が有効と考えられる．本研究では，Grid 環境の状況に応じてスケジューリング機能を変更する適応型スケジューリングの検討をおこなう．. Adaptive Scheduling Scheme on the Grid Environment Yusuke Inoue† , Takahiro Koita†† , and Akira Fukuda† InterProScan is widely used as useful genomic application. However, very long execution time is the most important problem to analyze many protein sequences with multiple genome applications. To reduce InterProScan’s execution time, use of large-scale computer environment like the Grid environment can be considered. We implemented the scheduling schemes for the Grid environment until now. As a result of evaluation, it is eﬀective for a scheduling scheme to change its policy with the situations of the Grid environment, dynamically. In this paper, we describe an adaptive scheduling scheme on the Grid environment.. はじめに. 1. Grid とは，ネットワークに接続された様々な計. InterProScan は，EBI1) （European Bioinformatics Institute）が開発したゲノムアプリケーションである．InterProScan は，たんぱく質シーケンスを複数のデータベースに対し，複数の解析ツールを実行することにより解析処理をおこなう．複数の解析処理を同時におこなうので，単一の解析処理では得られない解析結果が得られることが多く，有用なゲノムアプリケーションとして広く利用されている．しかし，複数の解析処理を同時に実行するため，単一の解析処理に比べ非常に多くの処理能力が必要とされる．既存の InterProScan には，小規模な分散処理環境向けに単純なスケジューリング機能が実装されている．実装されているスケジューリング機能は，インストール時に指定した計算機に，指定した解析処理を固定的に割り当てる．PC クラスタや小規模な分散処理環境であれば，既存のスケジューリング機能でも問題はない．しかし，Grid 環境のような大規模な処理環境では，多数の計算機の処理能力を十分に利用できないため，InterProScan は効率良く実行されず，応答時間の大幅な増加が予想される． † ††. 算機資源を利用可能にする基盤技術である．Grid 環境とは，広域ネットワーク上の計算機資源を多数利用し，PC クラスタ以上の処理能力や大きな記憶領域を有する大規模な計算機環境である．多数のたんぱく質シーケンスを解析する場合，Grid 環境のような高い処理能力を持つ大規模な計算機環境で InterProScan を効率良く実行することが必要である．. Grid 環境で InterProScan を効率良く実行するには，アプリケーションや計算機の情報を考慮し，適切に解析処理を割り当てるスケジューリング機能が重要である．我々はこれまで，InterProScan が Grid 環境の多数の計算機を有効に利用できるスケジューリング機能を実装し，実 Grid 環境における有効性を評価してきた．これまでの評価結果から，我々の実装したスケジューリング機能は，環境内の負荷などの状況によって有効な方式が異なることが分かった．本研究では，我々がこれまで実装してきたスケジューリング機能を，Grid 環境の状況に応じて有効な方式に切り替える適応型スケジューリングの検討をおこなう．本稿では，我々が実装してきたス. 九州大学 Kyushu University 同志社大学 Doshisha University. ケジューリング機能の概要と，適応型スケジューリング実現のための方策について検討する．適応. 1 −25−.

(2) 表 1: InterProScan の解析処理データベース解析ツール. 解析処理. blprodom. PRODOM. BlastProDom. coil. Coiled-Coil. ncoils. fps. PRINTS. FingerPRINTScan. hmmpfam. PFAM. HMMPfam. hmmpir. PIRSF. HMMPfam. hmmsmart. SMART. HMMPfam. prfs. PROSITE profile. Pfscan. scpr. PROSITE. ScanRegExp. seg. Seg. Seg. tigrfam. TIGFAMs. HMMPfam. 型スケジューリングの実現により，実 Grid 環境である OBIGrid. 2). （Open BioInformatics Grid）で. の効率の良い InterProScan の実行を目指す．. 2. 既存の InterProScan には，各解析処理を同時に. InteProScan は，既存の解析ツールやデータベースを複数組み合わせて解析をおこなう統合ゲノムアプリケーションである．InterProScan はたんぱく質シーケンスの解析を，解析ツールとデータベース・解析命令を記述したスクリプトなどで実行する．InterProScan の各解析処理はそれぞれ独立しており，全ての解析処理が終了すると解析結果は 1 つにまとめられ TXT 形式・XML 形式・HTML 形式などで出力される．図 1 に InterProScan の構成を示す．. Protein Sequence. Databases PRODOM Coiled-Coil PRINTS PFAM PIRSF SMART ProSITE profile PROSITE Seg TIGFAMs. こなうことで，複数の解析結果を出力したり，解析結果を比較することができる．. InterProScan. Scanning tools BlastProDom ncoils Finger PrintScan HMMPfam HMMPfam HMMPfam Pfscan ScanRegExp Seg HmmPfam. 処理と呼ぶ．InterProScan は複数の解析処理をお. result result result result result result result result result result. Common Object. TXT HTML XML. 図 1: InterProScan の構成. 実行するためのスケジューリング機能が実装されている．このスケジューリング機能による解析処理の割り当ては，インストール時に，1 つの解析処理に対して 1 台の計算機を固定的に指定し，以後変更しない．例えば，解析処理 hmmpfam をある計算機 X で実行するように指定した場合，解析処理 hmmpfam は全て計算機 X で実行される．既に計算機 X で解析処理が実行されている場合や，他により高い処理能力をもつ計算機がある場合にも，解析処理. hmmpfam は常に計算機 X に割り当てられる．つまり，InterProScan は 10 種類の解析処理から構成されており，1 つの解析処理を 1 台の計算機に割り当てても最大 10 台の計算機しか利用できないため，多数の計算機があっても有効に利用できないという問題点がある．. 3. InterProScan は，解析ツールとデータベースの組み合わせにより，10 種類のアプリケーショから構成される．表 1 に InterProScan の解析ツールとデータベースの組み合わせを示す．以後，本稿では InterProScan を構成するアプリケーションを解析 2 −26−. 予備評価. InterProScan のスケジューリング機能を実装するため，InterProScan の各解析処理の基本的な特徴を評価する．各解析処理の実行時間を計測し，全実行時間に占める割合を調べる．また，評価に用いる OBIGrid の各計算機での InterProScan の実行時間を調べる．.

(3) 3.1. 実行時間の割合. は VPN で接続され Grid 環境を構築している．. InterProScan は，複数の独立実行可能な解析処理からなる．解析処理の実行時間が大きく異なる場合，アプリケーションの情報として適切に利用すれば，効率良く InterProScan を実行できることが期待される．ここでは，各解析処理の実行時間と InterProScan の全実行時間に占める割合を調べた．評価には，1 台の計算機 (Celeron,1.3GHz) を用いた．表 2 に，各解析処理の実行時間と全実行時間に占める割合を示す．. OBIGrid のうち大阪産業大学と理化学研究所の 2 サイトの計算機を用い InterProScan を実行した．各サイトの計算機の性能はそれぞれ異なるが，同一サイト内の計算機は同じ性能である．用いる計算機は，大阪産業大学の計算機 5 台，理化学研究所の計算機 5 台である．表 3 に各サイトの計算機 1 台で InterProScan を実行したとき実行時間を示す．表 3: 各サイトの実行時間サイト実行時間 [秒]. 表 2: 各解析処理の実行時間解析処理実行時間 [秒] 割合 [%]. blprodom. 3.18. 0.45. coil. 0.03. 0.01. fps. 10.05. 1.45. hmmpfam. 423.02. 61.07. hmmpir. 18.73. 2.70. hmmsmart. 23.11. 3.34. prfs. 21.48. 3.10. scpr. 7.94. 1.15. seg. 0.02. 0.00. tigrfam. 185.17. 26.73. 295.4. 大阪産業大学. 351.0. スケジューリング機能. 4. 我々がこれまで実装してきたスケジューリング機能の概要について述べる．Fixed 方式，Random 方式，Load 方式，Adaptive 方式のスケジューリング機能 3) ，ジョブマネージャ4) を実装した．. 4.1. 表 2 より，解析処理 hmmpfam が，InterProScan の全実行時間の 6 割以上を占めることが分かる．それに対し，他の解析処理はいずれも割合は低い．異なる処理能力の計算機で各解析処理の実行時間を調べた場合，各解析処理の実行時間は異なるが，全実行時間に対する各解析処理の実行時間の割合はほぼ同じであった．解析処理 hmmpfam を，処理能力の高い計算機で実行すれば，実行時間を短縮できる可能性があることが分かる．. 3.2. 理化学研究所. 計算機の処理能力. Fixed 方式は，InterProScan に実装されている既存のスケジューリング機能である．Fixed 方式は，インストール時に解析処理を実行する計算機を指定する．指定された計算機は，以後固定的に解析処理が割り当てられる．ここでは，理化学研究所の計算機 5 台と大阪産業大学の計算機 5 台の計 10 台の計算機に 1 つずつ解析処理を実行する計算機として指定した．予備調査で調べた各解析処理の負荷の大きさをもとに，10 種類の解析処理のうち負荷の大きい解析処理の上位 5 つは理化学研究所の計算機に，下位 5 つは大阪産業大学の計算機に 1 つずつ割り当てるようにした． 4.2. 次に，評価環境である OBIGrid の計算機と InterProScan 実行時間の関係を評価する．OBIGrid とはバイオインフォマティクスの推進を目的に立ち上げられた Grid 環境である．各サイトが計算機を提供し，実 Grid 環境を構築している．2004 年 6 月現在，OBIGrid の参加サイト数は 28 であり， 300 台以上の計算機が接続されている．各サイト. 3 −27−. Fixed 方式. Random 方式. Random 方式は，Grid 環境全ての計算機を対象に各解析処理をランダムに割り当てる．複数のたんぱく質シーケンスを同時に解析する場合も，解析処理はランダムに割り当てられるため特定の計算機に集中せず，応答時間が短縮できると考えられる．しかし，Random 方式は解析処理の負荷や計算機の処理能力を考慮していない．.

(4) 表 4: 解析処理と計算機の分類解析処理計算機. hmmpfam. 4.3. High/Low. 理化学研究所. High. blprodom，coil，fps， hmmpir，hmmsmart，prfs，大阪産業大学 scpr，seg，tigrfam. Low. Load 方式. Adaptive 方式では，解析処理 hmmpfam を理化学研究所の計算機に優先的に割り当てる．それ以外の解析処理は大阪産業大学の計算機に優先的に割り当てる．それぞれのサイトの全ての計算機で CPU 使用率が高く予想応答時間が増加している場合は，優先されていないサイトの計算機に解析処理を割り当てる．Adaptive 方式は，処理能力の高い計算機には負荷の大きい解析処理を割り当て，処理能力の低い計算機には負荷の小さい解析処理を割り当てるのが特徴である．. Load 方式は，予備調査で調べた各計算機の実行時間 (Texec ) と CPU 使用率 (Ucpu ) をもとに，各計算機の予想応答時間 (Testimate ) を算出し，予想応答時間をもとにスケジューリングを行う．各計算機の予想応答時間は次の式で与えられる． Testimate = Texec × (. 1 ) 1 − Ucpu. 予想応答時間は，計算機の処理能力と，計算機の CPU 利用率より与えられる．InterProScan を. 4.5. 実行する場合，各計算機の予想応答時間を算出し，. ジョブマネージャ. ジョブマネージャは，投入された多数のジョブ. 最も予想応答時間が短い計算に解析処理を割り当. を適当な計算機に割り当てる．複数のユーザが計. てる．. 算機を利用する場合や複数のジョブが投入される. 4.4. Adaptive 方式. 場合，ジョブマネージャが利用される．. Adaptive 方式は，基本的には Load 方式と同じ. InterProScan の解析処理を複数の計算機で分散. 方式である．しかし，Adaptive 方式では計算機の. 実行させる 4 つのスケジューリング機能の実装に. 処理能力に加え，解析処理の負荷も考慮してスケ. ついて述べた．ジョブマネージャは，1 つのたんぱ. ジューリングをおこなう．Adaptive 方式は，各計. く質シーケンスの解析を 1 つのジョブとみなして. 算機の平均応答時間と CPU 使用率をもとに各計. 1 台の計算機に割り当て，InterProScan を 1 台の計算機で逐次実行させる．ジョブマネージャにより，InterProScan の解析処理を 1 台の計算機で逐次実行させる場合，解析処理を分散実行することによる応答時間の短縮は望めない．しかし，オーバヘッドは解析処理を分散実行するより小さい．解析処理を分散実行する実行方式を実装した InterProScan で少数のたんぱく質シーケンスを解析する場合，オーバヘッドが生じても解析処理を分散実行することにより，応答時間を短縮することができると考えられる．しかし，多数のたんぱく質シーケンスを解析する場合，逆に，オーバヘッドにより応答時間が増加すると考えられる．計算機の選択は Load 方式のスケジューリング機. 算機の予想応答時間を算出し解析処理を割り当てる点は，Load 方式と同じである．しかし，各解析の割り当て方式が Load 方式と異なる．. Adaptive 方式では，解析処理を負荷の大きい High の解析処理と負荷の小さい Low の解析処理に分類する．具体的には，InterProScan の全実行時間の 6 割を占める解析処理 hmmpfam を High の解析処理，他の解析処理を Low の解析処理に分類する．また，計算機も処理能力に応じて処理能力の高い High の計算機と処理能力の低い Low の計算機に分類する．具体的には，InterProScan の実行時間が短かった理化学研究所の計算機を High の計算機，大阪産業大学の計算機を Low の計算機に分類する．表 4 に解析処理と計算機の分類を示す．. 4 −28−.

(5) 能と同様に，最も予想応答時間が短い計算機を選. こなわなかった．. 択するようにした．. Random 方式は，Fixed 方式よりも平均応答時間は短い．特定の解析処理が特定の計算機に集中せず，負荷の大きい解析処理も評価環境全体の計算機に分散され平均応答時間が短くなっている．. 5. 性能評価前章で述べた 5 つのスケジューリング機能の得. 失について，OBIGrid で評価した．各方式の有効性と検討すべき課題について述べる．評価環境は，. 3.2 節と同じである．ランダムに InterProScan を生成し，Grid 環境に投入した．平均投入間隔は指数分布に従う．負荷率を変化させ，InterProScan を 100 個投入したときの平均応答時間を求めた．ここで負荷率とは，平均投入間隔により与えられ，計算機環境内の InterProScan の混雑度を表す指標であり，負荷率 100%は，もうそれ以上 InterProScan を処理することができない状態を表す．ここでの負荷率は，3.2 節の結果より算出した．図 2 に，各負荷率に対するスケジューリング機能とジョブマネージャの平均応答時間を示す． 2000. Fixed Random Load Adaptive ジョブマネージャ. 1500. )秒 ( 間時 1000 答応均平. Load 方式は，Fixed 方式と Random 方式に比べ平均応答時間が短かい．また，負荷が高いときでも平均応答時間の増加が抑えられた．Load 方式は，常に計算機の情報を利用して，解析処理の割り当てをおこなうため，全ての計算機が有効に利用されているためと考えられる． Adaptive 方式は，Load 方式と比べ，少しだけ平均応答時間を短縮することができた．これは評価環境が小さく，理化学研究所と大阪産業大学の計算機の性能の差が小さいためである．この結果， Adaptive 方式の長所が活かせなかったため，Load 方式と大きな差が出なかったと考えられる．なお，異なる評価環境で評価した場合，負荷率が低いときは Load 方式と平均応答時間に大きな差は出なかったのに対し，負荷率が高いときは解析 hmmpfam を優先的に処理能力の高い計算機に割り当てることにより，平均応答時間が Load 方式に比べ短くなる結果を得ている．ジョブマネージャを用いて InterProScan を実行. 500. した場合，負荷率が低いときと高いときの平均応答 0. 0. 10. 20. 30. 40. 50. 60. 70. 負荷率 (%) 図 2: 平均応答時間. 80. 90. 時間の差が最も小さい．負荷率が低いとき，ジョブ. 100. マネージャは解析処理を分散実行するスケジューリング機能に比べ平均応答時間は長い．しかし，負荷率が高くなっても平均応答時間の増加はスケジュー. 既存の InterProScan のスケジューリング機能で. リング機能に比べて低く抑えることができ，負荷. ある Fixed 方式は，負荷率が 20%を超えると平均. 率が高いときは最も平均応答時間が短かった．解. 応答時間が急激に増加している．これは各解析処. 析処理を分散実行しても応答時間の短縮が望めな. 理を常に同じ計算機で実行した結果，特定の計算. い高負荷時には，ファイルの転送や遠隔の計算機. 機に負荷の大きい解析処理が集中したためと考え. へ実行命令などのオーバヘッドを短縮することで. られる．特に，解析処理 hmmpfam が 1 台の計算. 平均応答時間を短く抑えることができた．. 機に集中するため，負荷率が低くても平均応答時間が急激に増加している．Fixed 方式の処理能力. 6. 適応型スケジューリング. は，特定の計算機に特定の解析処理が集中するた. これまでの評価結果から，負荷率が低いときは. め，評価環境の処理能力は実際の処理能力は理論. Adaptive 方式のスケジューリング機能が，負荷率が高いときはジョブマネージャが，それぞれ最も短い応答時間となること示した．Grid 環境内に処理が少ない低負荷時は，空いている計算機が多いため InterProScan の分散実行が有効であり，処理が多い. 上の処理能力より低い．負荷率 30%以上では，評価環境全体から見れば負荷率は低くても，実際に解析処理が割り当てられる計算機から見ると負荷率は 100%を超えているため，これ以上は評価をお. 5 −29−.

(6) 高負荷時は不用意に分散せず 1 つの InterProScan を 1 台の計算機で逐次実行することが有効である．つまり,Grid 環境内の負荷に応じて方式を切り替える適応型スケジューリングが有効と考えられる．しかし，実際に Grid 環境内の負荷を正確に把握することは難しく，何らかの指標を負荷の代替値として用いる必要がある．適応型スケジューリングを検討する場合，まず，何を指標にスケジューリング方式を切り替えるか決める必要がある．指標として以下のものが考えられる．. これまでの評価から，負荷値と実行待ちの InterProScan の数には，ある程度の相関性があることが分かっている．これを利用すると，実行待ちの InterProScan の数を閾値として利用する方法が考えられる．この方法の場合，他ユーザの処理や計算機構成の変更も実行待ち InterProScan として反映されるが，待ち InterProScan の数は環境内の状況の変化にゆるやかにしか反応しないため，ある程度のオーバヘッドを生じる可能性がある．. 7. まとめと今後の課題ゲノムアプリケーション InterProScan を対象に，. • Grid 環境の部分情報. 我々がこれまで実装してきたスケジューリング機. • たんぱく質シーケンス数. 能を，Grid 環境の状況に応じて有効な方式に切り替える適応型スケジューリングの実現方法につい. • 待ち InterProScan の数. て検討した．基本的には，負荷状況に応じて方式切. Grid 環境の部分情報とは，Grid 環境を構成する一部の計算機の処理能力や負荷・解析処理の実行状況である．これはユーザのプロセスだけではなく，他のユーザのプロセスも考えられる．全ての計算機の正確な情報が分かれば，負荷正確に算出できるが，全ての計算機の正確な情報を把握することは難しい．そこで，一部の計算機の部分情報をもとに，Grid 環境の負荷情報を推定することが考えられる．しかし，どれだけの計算機の情報を利用するか，また計算機の何の情報を利用するか，などについてはさらなる検討が必要である．計算機の負荷が一番効果的と予想されるが，どのように計算機負荷を集めて利用するかについても多様な実装が考える．これについても実評価による検討が必要である． InterProScan では，一般的にたんぱく質シーケンス数と必要な処理量は，ほぼ一定である．Grid 環境で，利用計算機が一定ならば，ある一定のシーケンス数を閾値として，方式を切り替えることが考えられる．この方法では，解析中のシーケンス数と各方式の応答時間の関係について予め評価する必要がある．しかし，同様の多数シーケンスセットに対して，繰り返し解析をおこなうような場合に対しては，最も適切な方式を常に選択できることが期待される．他ユーザの処理や計算機構成が頻繁に変わるような場合には，再び閾値を調査する必要がある．. り替えることが良いことが分かるが，何をもって負荷とするかについては，さらなる検討が必要である．特に Grid 環境は，多種多様な構成と状況が考えられる．負荷を反映する有効な指標を決定するには，実評価による検討が必要である．今後の課題としては，負荷値指標の有効性の検討と，それぞれの指標を取り入れた適応型スケジューリングの実装を予定している．. 参考文献 1) EBI, http://www.ebi.ac.uk/. 2) OBIGrid, http://www.obigrid.org/. 3) Yusuke Inoue, Takahiro Koita, and Akira Fukuda, ”Performance Evaluation of Scheduling Schemes for a Genomic Application on OBIGrid”, Proc. The 2nd IASTED International Conference on Communications, Internet, & Information Technology (CIIT 2003), 2003. 4) 井上悠佑, 小坂隆浩, 福田晃, 「Grid 環境における簡易ジョブマネージャの試作と評価」, 第 4 回九州大学情報基盤センター研究集会, pp.49– 56, 2003.. 6」 −30−.

(7)