高品質分散実行環境のための 計算・ネットワーク資源のグローバルスケジューリング手法 竹 房 あ つ 子ݽ 工 藤 知 宏ݽ 中 田 田 中 秀 良 基ݽ 夫ݽ 高品質分散実行環境の構築に際し,ユーザの要求を満たす高品質資源群を適切に確保しつつ,グ リッド上の資源群を有効活用するためには,グローバルスケジューリングが重要な課題となる.本稿 では,高品質分散実行環境の構築を目的とした計算・ネットワーク資源のオンライングローバルスケ ジューリング手法を提案する.提案手法では,ユーザの計算機及びネットワークに関する資源要求に 対して,複数資源マネージャからある時間帯における動的資源情報を入手し,その情報から複数の予 約プランを組合せ最適化問題を解くことにより作成する.シミュレーションによる評価により,提案 手法の有効性を示す. À Ë Ñ Ó ¹ÕÙ Ð ØÝ ÐÓ ×ØÖ Ø×Ù Ó Ì Ð Ë ÙØ ÙÐ Ò Ó Ü ÙØ ÓÒ Ù× ¸ ݽ ÓÑÔÙØ Ò Ò ÒÚ ÖÓÒÑ ÒØ× À ÑÓØÓ Æ Ò Ó× ¸ ݽ ݽ Ó Ì Ò Æ ØÛÓÖ ÌÓÑÓ Ê ×ÓÙÖ × ÓÖ ÖÓ ÃÙ Ó Ý½ ÐÓ Ð × ÙÐ Ò × Ñ ØÓ × Ø × Ý Ö ÕÙ Ö Ñ ÒØ× ÖÓÑ Ù× Ö× Ò Ö ×ÓÙÖ Ñ Ò ×ØÖ ØÓÖ× × ÓÒ Ó Ý ××Ù × ÓÖ ÓÒ×ØÖÙØ Ò ¹ÕÙ Ð ØÝ ×ØÖ ÙØ Ü ÙØ ÓÒ ÒÚ ÖÓÒÑ ÒØ × ÓÒ Ú Ò Ö × ÖÚ Ø ÓÒ׺ Ï ÔÖÓÔÓ× Ò ÓÒÐ Ò ÐÓ Ð × ÙÐ Ò × Ñ ÓÖ ÓØ ÓÑÔÙØ Ò Ò Ò ØÛÓÖ Ö ×ÓÙÖ × ÓÖ Ø Ø ÔÙÖÔÓ× º ÓÖ Ù× Ö Ö ×ÓÙÖ Ö ÕÙ Ö Ñ Òظ Ø ÔÖÓÔÓ× × Ñ ×ÓÐÚ ÓÑ Ò Ø ÓÒ Ð ÓÔØ Ñ Þ Ø ÓÒ ÔÖÓ Ð Ñ ØÓ Ø ÖÑ Ò ÑÙÐØ ÔÐ Ö × ÖÚ Ø ÓÒ ÔÐ Ò× Ý Ù× Ò ÝÒ Ñ Ö ×ÓÙÖ Ò ÓÖÑ Ø ÓÒ ÖÓÑ Ö ×ÓÙÖ Ñ Ò Ö׺ Ì × ÑÙÐ Ø ÓÒ Ö ×ÙÐØ× × ÓÛ « Ø Ú Ò ×× Ó ÓÙÖ ÐÓ Ð × ÙÐ Ò × Ñ º ½º はじめに グリッドとネットワーク資源管理技術により,複数 管理組織の提供する多様な資源で構成される高品質分 散実行環境を動的に構築することが可能になった.特 に,帯域が保証されたパスネットワークを資源のひと つとして,計算機やストレージ等の資源と同時に確保 し,利用する試みが国内外で複数行われている½µß¿µ . 高品質分散実行環境を提供するには,各資源を管理 する資源マネージャ が,性能保証機能と同時確 保のための事前予約機能を有することが前提となる. 計算資源のみを対象としたマルチクラスタの同時確保 µ µ では, グリッドスケジューラや バッチキュー予測サービスのように各ローカルスケ ジューラのキューの利用状況の取得または予測により, 事前予約機能がない状況での同時確保を実現してい る.しかしながら,これらの手法は複数資源が同時に ´Êŵ ÃÇ Ä É ÌË Ý½ 産業技術総合研究所 Ù×ØÖ Ð Ë Ò Ò Æ Ø ÓÒ Ð ÁÒ×Ø ØÙØ Ó Ì ÒÓÐÓ Ý ´ ÁË̵ Ú Ò ÁÒ¹ 利用可能になることを保証するものではないため,資 源利用に対する課金が発生する場合はユーザが不利益 を被るおそれがある.よって,複数資源の同時確保を 確実に実現するためには事前予約が重要な機能であり, 我々は,性能保証および事前予約機能を有する資源マ ネージャと連携し,高品質分散実行環境を構築・利用 するための 資源管理フレームワーク µ を開 では,グローバル資源コーディ 発している. ネータ が複数 と連携してユーザの要求す る資源群を確保する. ユーザの要求を満たす高品質資源群を適切に確保 しつつ,グリッド上の資源群を有効活用するために は, におけるスケジューリング(グローバルス ケジューリングと呼ぶ)手法が重要な課題となる.ユー ザの観点では,指定した性能を保証する資源群を 早い時刻に確保する, 価格の安い資源群を確保す る, 価格が高くても品質 可用性等 優先で確保 する,等の選択肢がありうる.一方,資源管理の観点 では,上記を考慮することに加え, 複数資源提供 省エネや連 者に対して平等に負荷を割り当てる, Ö ÊË Ö ÊË ´ Ê µ ÊÅ Ê ´µ ´µ ´µ ´ µ ´ µ ´ µ ②③④⑤ ⑥④⑦⑧④③⑨ ❴ ❵❨❪❬❛❜ ❝❞❡❢ ❏❑ ❆ ■ ❴ ❵❨❡❪❬❛❜ ●❍ ❴ ❄ ❄❅ ❝❞❡❢ ❵❨❪❬❛❜ ❇❈❉❊❋ ❝❞❡❢ ▲▼◆❖◗❋❘❙❘▼◆❘❚❯◗ ❱❲❳❳ ❨▼❘◗❋❘❙❘ ▼◆❘❚❯◗ ❇❲❳❳ ❩❬◆▼❘❭❪ ❱ ❫❭❬◆ ✪✫✬✭ ✮ ✯✣✭✰✥✱ ✲✳✴✵✶✷✸✹✺ ✌✍ ✍ ❃ ❂✳✶✼ ✄✎✏ ✁✂✄☎✆✝✁ ✸✴✸✹✷✿ ✻✼✽✶ ✻✼✽✶ ✔✄✓✟✠✄✆✟✓✞ ✁✂✄☎✆✝✁ ✑✄✄✆✒ ✟✓✏✠✄✆ ✕✡✂✠✁✖ ☛✔✕☞ ✁✞✟✂✠ ✆✡ ☛ ☞ ☛✌ ✑☞ ✾✷✿✳❀✿❁✳❀✳❂✺ ✲✳✴✵✶✷✸✹✺ ✻✼✽✶ ✻✼✽✶ ✜✘✚ ✘✘ ✚✘✙ ✗✘✙ ✚✘✙ ✛✘✙ ✢✣✤✥✦✧ ★ 図 ½ ✜✘✚ ✙✛ ✙✛ ✚✘✙ ✗✘✙ ✘✘ ✢✣✤✥✦✧ ✩ ✛✘✙ ✚✘✙ ´ µ ÊÅ グローバルスケジューリングモデル 資源管理フレームワークの概要 高品質分散実行環境構築・利用のため,我々は図 ½ に示す資源管理フレームワーク の開発を 進めている.本フレームワークは資源管理システム µ ,資源レジストリ ,資源モニタリング µ システム で構成される.図中の , は一組織,あるいは連携関係の複数組織を表し,ユー ザに対して管理組織を跨った高品質分散実行環境を事 前予約に基づいて提供する. はグローバル資源コーディネータ と 各資源を管理する資源マネージャ で構成され, と が連携してユーザに高品質分散実行環境 を提供する.図 における , , は, それぞれネットワーク,計算,ストレージの を表 す. は複数存在し,複数 が階層的に連携 して,あるいは独立した 間で競合して各ユーザ の要求する資源を確保する. のうち,グローバ ルスケジューリング機能(プランナ)をもつものが, ¾º½ Ö ÊË ´ÊÅ˵ ´Êʵ ´Å˵ ÊÅË Ê ÊÅ Ê ¾ ユーザの資源要求とプランナによる予約プラン ↕➙➛ ➛↔↕ ➡➜➣ ➠➈➥➢ ➤↕➞ 資源管理フレームワークの概要 携関係から,特定の資源に優先的に割り当てる, ユーザのサービスレベルにより,高レベルのユーザが 確実に資源確保できるように配慮する,等の方針が考 えられる.これらの多様な指標を考慮しつつ,分散す る計算資源および拠点間ネットワーク資源を同時確保 するための適切なグローバルスケジューリング手法に 関する議論は不十分である. 本研究では,高品質分散実行環境の構築を目的とし た計算・ネットワーク資源のオンライングローバルス ケジューリング手法を提案し,シミュレーションでの 評価により,その有効性を示す.提案するグローバル スケジューリング手法は,ユーザの計算機及びネット ワークに関する資源要求に対して,複数 から利 用可能な資源情報を入手し,複数の予約プランを組合 せ最適化問題を解くことにより作成する.評価では, ユーザの要求と資源管理要件に対し,提案手法が有効 であり,その予約成功率が高いことを示す. ¾º 図 ⑥④③④⑤⑩❶⑨❷❸❹ ❺❻❶❹ ❾❿➀➁➂➃ ➅ ❣❤✐❥❧ ❑ ❆ ■❏ ❼❽ ❍ ❣❤✐❥♠ ● ❇❈❉ ❊❋ ❄❅ ❄ ❣❤✐❥❦ ❾ ❿➀➁➂➃ ➄ ❣✐♥♦✐♣❤q❥ rstt ✉✈✇♣❤q❥ ①stt ÓÑ Ò ´Êŵ ½ ´ Ê µ ÆÊÅ ÊÅ ËÊÅ ÊÅ Ê Ê Ê ➭➯ ➉➊➋ ➊➌ ➒➎➓➐➑ ➆➣→ ➲➯ ➲➯ ➆➣↔ ➆➣➈ ➪➶ ↕➝→ ➆➇→ ➪➹ ➳➯ ➆➇➈ ➫➈➝ ↕➜→ 図 ¿ →➟➵ ¹Ð Ñ ➉➊➋➊➌ ➍➎➏➐➑ と ➸➺➚➼➽ ➸➺➻➾➽ ➸➺➻➳➽ ➸➺➻➼➽ ➔➍ ➸➺➻➭➽ ➸➺➚➳➽ ➸➺➚➾➽ ➞➤➇ ➠➥➈↔➢ ➈➦➧➨➦➩➦ ➥➝➣ ➠➡➦➘➨➴➷➬➢ ➝↕➞ ÒÄÁ ÀÌ Ò ➟➝➣ ➠➙➡→➡➢ の実験における資源構成 Ê または 資源確保の予約プランを決定し,下位の に対して資源確保手続きを行う. は,各 の所在や各 の管理する資源の 静的な情報 総 コア数, 拠点間のパスとその 容量,など を, または下位の から収集し, に提供する.ある時刻に利用可能な動的資源の情 報は, が各 から直接取得する.我々は が商用サービスとして資源提供することも想定してお り,その場合,各 は動的資源情報をすべて公開す ることはできないためである. では,予約された資源で構成される高品質分散 実行環境の稼働時の資源利用状況をユーザに提供する. この情報をもとに,ユーザは確保した資源の安定稼働 の確認や,余剰資源や高負荷資源のための再構成を行 及び各 は再構成を行うための手段を提 う. 供し,具体的な再構成方針はユーザが決定する. ¾º¾ ユーザの資源要求 我々はこれまでマルチサイトの資源とその間のパス ネットワークを同時に確保して高品質分散実行環境を 動的に構築し,その上でアプリケーションを実行する 試みを行ってきた½µ¸¾µ¸ µ.事例として, お よび で実装された力学シミュレーション, ビデオデータのライブストリーム通信が挙げられる. 本研究のグローバルスケジューリング手法では,これ らのアプリケーションで必要とされる多様な資源の同 時確保のための予約プランの作成を目的とし,予約時 刻の異なるワークフロータイプの資源確保は今後の課 題とする. 図 ¾ にユーザの資源要求(左)と,その要求から のプランナが生成する予約プラン(右)の例を ÊÅ ÊÊ ´ µ Ê Ê ÊÅ ÈÍ» ÊÅ ÊÅ ¾ ÊÊ ÊÅ ÊÅ ÊÅ ÅË Ê ÅÈÁ Ê ÊÅ Ö ÊÈ À 示す.計算資源の要求では,計算サイト数,各サイト での (コア)数,属性情報( ,実行環境等) を,ネットワーク資源要求では要求する拠点間の帯域, レイテンシ,その他の属性情報 メディアタイプ,可 用性等 を指定する.また,各資源に対して時刻の要 求を指定することができる.図 は,本研究で対象 とする同時確保要求であり,全資源の確保時間帯を直 ËÌ , 接,または ÄËÌ , パラメタにより指定す る. ËÌ は最も早い開始時刻,ÄËÌ は最も遅い開始 時刻, は予約時間幅を示しており,ÄËÌ が最 終的なデッドライン(締切時刻)に相当する. のプランナは,ユーザの資源要求を受け取る と,図 ¿ のような資源群から適切な資源群を選定し, µ 予約プランを作成する.図 は, および 米国 プロジェクトによる 実証実験 実験 で用いられた資源群を示して いる¾µ .図 右の予約プラン例では,割り当てられた 計算資源 , , と計算資源間のネット ワーク経路,および資源を確保する開始時刻と終了時 刻が決定される.予約プランにおける資源間のネット ワーク経路は,実際のルータやスイッチで構成される ネットワークのトポロジを表すものではなく,抽象化 管理下の具体 されたトポロジを表す.これは, 的なネットワークの構成は一般に公開されないためで ある.すなわち, つのドメイン内のネットワーク資 源を利用する場合は つのパスで,複数ドメインを跨 る場合は複数のパスで経路が構成される.図 では, 間の経路は つのネットワークドメイン 内のパスで表されるが, 間の経 路は を経由して と の つの パスで構成される. ÈÍ ÇË ¾ ÌÑ ´ µ ÖÐ ×ØËØ ÖØÌ Ñ ´ ÙÖ Ø ÓÒ ´ µ µ Ä Ø ×ØËØ Öع · Ê ¿ ¹Ð Ñ ÓÑÔÙØ Ò µ ÒÄÁ ÀÌ Ò ´ Ä Ä ¾ ËØ ËØ ËØ ÆÊÅ ½ ½ Ë Ø ¹Ë Ø ÓÑ Ò½ ½ ¿º ½ ÓÑ Ò½ ¾ Ë Ø ¹Ë Ø ÓÑ Ò¾ ¾ グローバルスケジューリング手法 スケジューリングの手順と方針 における資源確保手順は以下の通りである. 静的資源情報をあらかじめ から取得する. ユーザの資源要求を受け取る. のプランナで資源要求に対する予約プラ ンを複数作成する.この際,プランナは動的資源 情報を資源提供候補となる各 に問い合わせる. から複数 への問い合わせは同時に行うた め,この遅延は Ç となる µ . プランナの作成した予約プランから, と 複数 が連携して資源を確保する. 確保が成功した場合は終了,失敗した場合はそ の情報をユーザに提供し,ユーザは新たな条件で再 度資源要求を行う. 本研究では,手順 で予約プランを作成するオンラ イングローバルスケジューリング手法を提案する.グ ¿º½ ½º ¾º ¿º Ê ÊÊ Ê Ê º º ÊÅ ´½µ ÊÅ ¿ ÊÅ Ê áä ÞÑÒÓãØ áäåÑÒÓãØ áäæÑÒãØ áäçÑÒãØ ➮➱✃❐❒❮ Ù Ïà áäßÑÒãØ á ÑÒÓãØ äà áäÜÑÒãØ ÏÚ ÑÛÓÔÕÖ×Ø ➮➱✃❐❒❮ ❰ ´ µ Ïß áâÐÑÒãØ áä ÚÑÒãØ ÏÐ ÑÒÓÔÕÖ×Ø 図 ÏÜ ÑÝÓÔÕÖ×Ø áäèÑÒãØ ÏÞ ÑÝÓÔÕÖ×Ø 資源グラフ ½ ローバルスケジューリングでは, 節で述べたように, ユーザは資源要求に加え, 時刻優先, 価格優 先,または 品質優先の方針で予約プランの作成を 求める.一方, の資源管理者は, 複数 に対して平等に負荷を割り当てる, 省エネや組織 間連携のため,特定の資源を優先する, ユーザの サービスレベルを考慮する,という方針が考えられる. これらの多様な指標を考慮しつつ,計算・ネットワー ク資源の予約プランを作成するため,グローバルスケ ジューリングを組合せ最適化問題として解く.また, それを事前予約に適用する. ¿º¾ 組合せ最適化問題に基づくスケジューリング 図 のような実際の資源構成を抽象化し,図 に 示すような有向グラフ Î として資源群を表 す.Î は の点の集合, は の枝の集合であり, グラフの各点 ÚÕ は計算資源サイトまたはネットワー クドメイン間の交換点を,各枝 ·Ö または Ó Ô が提供する資源間のパスを表 Ö Ô Ó は各 す.図 では,パスは つの ドメイン および から提供されており,Ú¼ を始点,Ú½ を終点とする枝を ·¼ ,Ú½ を始点,Ú¼ を終点とする 枝を ¼ で表す.グラフの点および枝の括弧内は,提 供可能な (コア)数および帯域であり,それぞ れ Û Î ,Û と表す.図 では,Ú¾ , Ú¿ はドメイン間交換点であり,利用可能な は存 在しない.同様に,遅延,可用性など,その他の属性 情報パラメータを追加することができる.また,提供 および帯域の単位あたりの価値を,それぞ する れ Ú Î ,Ú と表す.Û および Ú は, ·Ö Ö で共有する. 次に,資源要求を完全グラフ Ö ÎÖ Ö で表す. ÎÖ は必要とする計算資源サイト(点)の集合, Ö は ÎÖ 間を結ぶ枝の集合を示す.また, Ö に必要な 数および帯域をそれぞれ Ö ÎÖ ,Ö Ð Ð Ö と する. 以上のパラメータから,以下の変数を整数計画法で 求めることで予約プランを決定する. ´µ ´µ Ê ´ µ ¿ ´ ´ µ ÓÑ Ò¾ ´µ ´ µ ´ µ µ ´ ÆÊÅ ¾ µ ÆÊÅ ÈÍ ´ ¾ µ ´ ¾ µ ÈÍ ´ ¾ µ ´ ¾ µ ÓÑ Ò½ ÈÍ ´ ´ ¾ µ Ü Ý Ð ¾ ¼½ ¾ ¼½ ´ µ ÈÍ ´¾ µ ´¾ ¾ µ ´½µ ´ µ¾ ¾ ´ µ¾ ¾ µ ´¾µ Î Ñ Ò Ð ÊÅ Ó Ô ÎÖ Ñ Ò Ö Ó Ô Î ÎÖ ここで,資源要求されるサイトに対して選択される計 算資源サイトの要素 Ü は ,その他のサイトは と なる.また,資源要求されるネットワークに対して選 ½ ¼ ½ 択されるパスの要素 Ý Ð は ,使用されないパスの要 素は となる. 節のスケジュール方針を 価格優先とした場 合,目的関数と制約条件は次のように表せる. ¼ ¿º½ ´µ Å Ò Ñ Þ ¡ Ú ¾ ¾ Ö ¡ · Ü ËÙ Ú ¾ ¾ ÎÖ Î Ö Ð ¡ Ö Ð ¡ Ý Ð ´¿µ ¾ ¾ ÎÖ ¾ Î Î Ü ¾ ÎÖ Î ½ ´µ ½ ´µ Ü ¡ Ö ¾ Ü ¾ Ð Ö ¾ ¾ ¾ Ð Ö Ð Ó Ô Î Ñ Ò ¼ ¼µ ¼µ Ö Ð Ö Ð ¡ Ý Ö ÜÑ Ô ¾ Ñ ´ ´ ´µ ´µ Û Ð Ý´Ò Ñµ ´Ó Ôµ ¾ ÜÑ Ó ´¿µ ½ ´ ¼ ´ Ð Ö ´ µ¾ Ð Ò Ý ¾ Ý´Ñ Òµ ´Ó Ôµ Î Ñ Ö Ð Ö Ð ¼µ ¼µ ´µ ´µ ´ µ ¿º¿ ´ µ ´ µ ´µ ´µ ½ ´µ ´µ ´µ ÈÍ ´µ ¾ ´µ ´µ ½ ÈÍ ½ ½ ¾ ´µ ´ µ ½ ½ ½ ´µ ¼ ½ ¾º¾ Ò 式 の目的関数は,選択する計算・ネットワーク資 源の価格の合計を最小化することを表している.また, 時刻優先の場合も同様に計算する.ただし, 節 でユーザ方針の反映方法を述べる. 品質優先の場 合は,目的関数をユーザの満たす品質が高くなるよう に設定する.一方,資源管理者の方針 および を満たすには,それぞれの方針に従って資源に重みづ けし,別の目的関数を加える. の方針については, 動的資源情報取得時に各ユーザのサービスレベルに即 した情報を取得することで反映することができるため, 別の目的関数の設定は不要である. 式 ∼ は計算資源に関する制約条件,式 ∼ はネットワーク資源に関する制約条件を示す.式 は,要求サイト に割り当てられる実際のサイト は つのみであること,式 は,各資源サイト は 資源要求の中で つ以上割り当てられないことを表 す.式 は,各資源サイト が要求される 数 以上の を提供可能であることを示している. 式 は,要求サイト間のパス Ð の帯域の確保要求 がある場合は,Ý Ð の総和が 以上に,ない場合は になることを表す.すなわち,ドメイン内のパスが選 択される場合には , ドメインに跨るパスが選択さ れる場合は となる.式 は,各パス が要求され る帯域以上の帯域を提供可能であることを示す. ´µ ´µ ¿º¾ Î Ò ¼ ´µ ´µ Û ÎÖ ¾ ½ Ø ØÓ ¾ ´µ 式 は,流量保存則½¼µ を応用して導く.流量保存 則とは,グラフ上の 拠点間の経路上の各点において, 流入する流量と流出するが流量の差が,供給量と等し くなることを示す.すなわち,流量を とすると,始 点の供給量は ,終点の供給量は ,通過点の供給 量は となる.式 では,パス Ð の帯域確保要求が ある場合,各要求パス Ð Ó Ô (Ó はパス Ð の始点,Ô はパス Ð の終点)と計算資源サイトおよび交換点を含 む資源上の各点 Ñ に対して,流量 として流量 保存則を適用する.すなわち,Ñ が Ð の始点であれば, 式 の値は ,終点であれば ,通過点であれば となる.この際,Ñ が始点ならば ÜÑ Ó ,終点な らば ÜÑ Ô となるので,式 の値を ÜÑ Ó ÜÑ Ô として表すことができる.これにより,Ü と Ý Ð を 関連付ける. 提案する組合せ最適化問題に基づくスケジューリン グ手法は,事前予約がない場合のグローバルスケジュー リングにも適用可能である.また,特定のサイトや条 件をユーザがあらかじめ指定している場合にも,容易 に適用することができる. ¿º¿ 事前予約への適用 次に,事前予約への適用について述べる. 節の手 法は,ある時間帯における予約プランを作成するもの であるが,ユーザの資源要求では,確保する時間帯は 節で述べたように直接時間帯が指定される場合と, ËÌ ,ÄËÌ , で範囲指定される場合がある.前者 は,動的資源情報を取得する際にユーザの指定した時 刻を指定して利用可能な資源を問い合わせ,取得した 情報をもとに 節の手法を用いて予約プランを作成 すればよい.一方,後者は ËÌ ÄËÌ の時間帯 の中から,確保可能な資源を探索しなければならない. 我々は商用サービスを考慮して, プロジェ クトで規定している資源予約インタフェース を用いている. では,各 における詳細 な予約テーブルを公開しない代わりに,指定した時刻 における利用可能な資源情報を提供している.このイ ンタフェースに基づき,以下の手順で予約プランを決 定する. ËÌ ÄËÌ から予約時間帯候補を等間隔 に Æ 個選ぶ. 資源候補となりうる各 に対し,Æ 個の時 間帯の動的情報を一度に問い合わせる. の情報から 節の手法を用い,それぞれの 候補の予約プランを Ò 個 Ò Æ 決定する. 決定した Ò 個の予約プランから,ユーザの方針 に従って最終的な予約プランを決定する. では,予約時間帯候補数 Æ を大きく設定するほど最 適な資源群の選択ができるが,オンラインスケジュー リングでは応答時間とのトレードオフがあるため,予 約時間帯の候補数 Æ はあらかじめ規定する. では,我々の用いる バージョン では ¼ ¿º¾ ¸ · ℄ ¹Ð Ñ Æ˹ÏËÁ ½º ÊÅ Æ˹ÏËÁ · ℄ ¾º ÊÅ ¿º ¾ º ¿º¾ ´ µ ½ ¾ Æ˹ÏËÁ ¿ õö éêë êì òîóðñ õ÷ ôí éêë êì íîïðñ 図 Success Ratio (Success / Total) 1 シミュレーション環境 0.9 0.8 0.7 0.6 UserA N UserA S UserB N UserB S 0.5 0.4 øùúûý 図 表 ½ øùúûþ 0 øùúûÿ 図 資源要求の種類 サイト数»ドメイン ドメイン交換点 ÈÍ 数 ½¸ ÆÊÅ ¿¸ ÊÅ ½¼ »ÂƸ ¿»Â˸ ¿»ÍË ½ ´ÂƸ Â˸ Í˵¸ ÈÍ 単価 ÂÆ ¸ ½ ¸ ¿¾¸ ÍË ¸ ½ ¸ ¿¾ ¾ ´ÂƸ Â˵ ¸ ÂË ¸ ½ ¸ ¿¾ ¸ ½ 帯域 Ô×℄ 帯域単価 ドメイン内 ドメイン内 ½¼¸ 交換点接続 ¸ 交換点接続 ¾¼ ¿ ÄËÌ ËÌ ¹ ´一様分布µ ¢ ¿ ´½µ ´µ ´µ ´µ Ê 提案手法の評価 シミュレーションモデル 本手法の有効性を示すため,シミュレーションによ る評価を行う.シミュレーション環境は, 実験 で用いた図 を想定し, つのネットワークドメイン と つのドメイン交換点で構成される図 のような 環境を用いた.簡略化のため図 では各ドメインに対 º½ ¿ 200 400 600 800 Time [min] 1000 1200 1400 資源確保成功率の比較 ´平均到着間隔 Ñ Ò℄µ して つの計算サイトを示したが,ドメイン内のサイ ト数は表 ½ のようになっている.ドメイン内のサイト 黒丸 間は完全グラフで接続され,ドメイン内の各交 換点 白丸 とドメイン内の全サイトもそれぞれ接続 されている. シミュレーション設定の概要を表 に示す.シミュ レーションでは, と が つの に対 して資源予約要求をする.資源要求の種類は, 実験のアプリケーションを想定し,図 のいずれかを 生成するようにした.各ユーザにおける資源要求設定 は両方とも表 に従う.最初の 時間までに各ユー ザの資源要求が到着し,それぞれ次の 時間の時間 帯の中から資源の予約を要求をする. での予約時間帯候補数 Æ は とし,各候補 に対して確保コストが最小となる組合せを探索する. ソルバにはフリーの を用いた½½µ .また,候補間での優先順位は 時間優先とした.実験では, に対してサービス レベル が低い場合も想定した.具体的には, が低い場合は各 の利用可能な資源のうち,半分 までしか要求できないようにした. º¾ 評 価 結 果 図 ,図 に平均到着間隔が および における, と の資源要求に対するグロー バルスケジューリングの成功率を示す.図 の方がよ ´ ½ ¿ ¾ UserA N UserA S UserB N UserB S 0.5 ¾ わせを同時に行うことができるため,これによるオー バヘッドは小さい. では Æ 個の動的資源情報に対して独立に予約プ ランを決定することができるため, に要する遅延も Æ によらず Ç とすることができる. の Ò 個の予約プランの優先順位は,ユーザの方針 に従って決定する. 時刻優先であれば, ËÌ に近 い順に Ò 個の予約プランをソートする. 価格優先 または 品質優先の場合は,それぞれのパラメータ で優位な順にソートする.各予約プランに対して は順次確保を試みて,ユーザの方針を反映させる. ¿ 0.6 図 ¸ ½¼ ´ポアソン到着µ ½ 回の問い合わせオペレーションで複数条件の問い合 º 0.7 0 平均要求到着間隔 ¿ ¿¼¸ ¼¸ ½¾¼ ´一様分布µ ½¸ ¾¸ ¸ ´一様分布µ 予約時間幅 Ñ Ò℄ 予約 ÈÍ 数 予約帯域 Ô×℄ 1000 1200 1400 0.8 Í× Ö ¸ Í× Ö ÌÝÔ ½¸¾¸¿¸ 800 0.9 0.4 資源要求設定 ユーザ 資源要求の種類 平均要求到着間隔 Ñ Ò℄ 600 1 環境設定 Ê 400 資源確保成功率の比較 ´平均到着間隔 ½¼ Ñ Ò℄µ シミュレーション設定 ÊÅË 構成 200 Time [min] Success Ratio (Success / Total) øùúûü Ä Ä µ ´ µ Í× Ö ½ ½ Í× Ö ½ ¾ Ê Ê Ä Ä ¾ ½¼ ÄÈà ´ ÆÍ Ä Ò Ö ÈÖÓ Ö Ñ¹ Ñ Ò Ã Øµ ´Ëĵ Í× Ö Í× Ö ÊÅ Í× Ö ½¼ Ñ Ò℄ ËÄ Ñ Ò℄ り負荷が高い場合を表している.横軸は資源要求受 付時刻,縦軸は各資源要求の割り当てが終了した時 点での割り当て成功率である.各プロットの白抜きは の結果,黒塗りは の結果であり,三角 /四角 は の設定の有/無を示す. 図 で なしの場合の と を比較す ると,成功率はほぼ同程度であることが分かる.一方, ありの場合では, の成功率は最終的に から とやや下がっているのに対し, の成 功率は から に著しく低下していた.図 で より負荷の高い場合で比較すると, では から と上がっているのに対し, では から と低下していた.これにより, の設定に より低 のユーザの確保率を下げることが可能であ り,負荷が高い状況では,他のユーザの成功率を上げ ることが示唆された. 全資源利用可能時間に対する要求する資源確保の 割合(資源要求率)は,平均到着間隔が のと きで は は帯域は (確定するパスがド メイン間とドメイン内で 対 であるとした場合), では と であり,非常に高負荷な環 境設定で実験を行っている.すなわち, の場 合は計算資源では のところで資源要求率が となるが,その際の予約成功率は なしの場 合で , とも, 以上であり,提案手法で は高い予約成功率を示すことが分かった. Í× Ö ´Ëµ ËÄ Í× Ö ´Æµ ËÄ ËÄ Í× Ö Í× Ö ¼º ½ ¼º Í× Ö ¼º Í× Ö Í× Ö ËÄ ¼º ¼º ¾ ËÄ ÈÍ ½º¿ Ñ Ò℄ ¾º ½ ½º ¿ ¼º ½ ½ ½ ¼º ¼º ½ ¼º ½¼ Ñ Ò℄ ½¼ Ñ Ò℄ ½¼ Ñ Ò℄ ½¼¼ ±℄ Í× Ö º Í× Ö ËÄ ¼º 関連研究 ÎÁÇÄ Ö ÊË ¿µ では,我々の と同様に計算資 源とネットワーク資源を事前予約に基づき同時に確保 することを目的としたシステム開発を進めているが, そのグローバルスケジューリングのアルゴリズムに関 する研究は十分に行われていない. 安藤ら½¾µ は,本研究同様,複数計算・ネットワー ク資源を確保するための予約プランを生成する予約ア ルゴリズムを提案している.提案するアルゴリズムは 資源群を無向グラフで表し,バックトラック法により 資源群を探索する.我々の研究は高品質分散実行環境 構築を目的としているため,コアロケーションのため の手法を提案しているが,安藤らのアルゴリズムでは ワークフローにも対応する.ただし,バックトラック 法を用いているため,適切な解を探索する精度は低い. º ま と め 本研究では,高品質分散実行環境の構築を目的とし た計算・ネットワーク資源のオンライングローバルスケ ジューリング手法を提案し,シミュレーションでの評 価により,その有効性を示した.提案するグローバル スケジューリング手法では,ユーザの計算機及びネッ トワークに関する資源要求に対して,複数資源マネー ジャから利用可能な資源情報を入手し,組合せ最適化 問題を解くことにより予約プランを作成する.評価で は,提案手法はユーザの要求と資源管理要件に対して 有効に機能し,予約成功率が高いことを示した.今後 は様々な環境下での,より詳細な評価実験を行う. 謝辞 本研究の一部は,情報通信研究機構 の委託研究「ダイナミックネットワーク技術の研究開 発」により実施した. ´ÆÁ ̵ 参 考 文 献 ½µ Ì Ù× ¸ º Ø Ðº ¹Ð Ñ ÓÓÖ Ò Ø ÓÒ Ó Ö Ë ÙÐ Ö Ò Ä Ñ È Ø Ë Ö¹ Ú ÓÚ Ö ÅÈÄ˸ ÙØÙÖ Ò Ö Ø ÓÒ ÓÑÔÙع Ò ËÝ×Ø Ñ׸ ÎÓк¾¾´¾¼¼ µ¸ ÔÔº ß ´¾¼¼ µº ¾µ Ì ÓÖÔ ¸ ˺ʺ Ø Ðº ¹Ð Ñ Ò ÒÄÁ À̹ Ò ÏÖ ÔÔ ÁÒ Å Ð Û Ö Ó¹ ÐÐÓ Ø Ò ÓÑÔÙØ Ò Æ ØÛÓÖ Ê ×ÓÙÖ × ÖÓ×× Â Ô Ò Ò Ø Í˸ ÈÖÓº Ö Æ Ø×¾¼¼ ´¾¼¼ µº ¿µ ÖÞ¸ º Ø Ðº Ó¹ ÐÐÓ Ø ÓÒ Ó ÓÑÔÙØ Ò Æ ØÛÓÖ Ê ×ÓÙÖ × Ò Ø ÎÁÇÄ Ì ×Ø ¸ ÌÊ ¼¼ ½¸ ÓÖ Ö ´¾¼¼ µº µ ÅÓ Ñ ¸ Àº Ò Ô Ñ ¸ º ÜÔ Ö Ò × Û Ø Ø ÃÇ Ä Ó¹ ÐÐÓ Ø Ò Ë ÙÐ Ö Ò ÅÙÐØ ÐÙ×Ø Ö׸ ÈÖÓº Ø Á » Å ÁÒسРËÝÑÔº ÓÒ ÐÙ×Ø Ö ÓÑÔÙØ Ò Ò Ø ÊÁ ´ Ö ¾¼¼ µ ´¾¼¼ µº µ ÆÙÖÑ ¸ º¸ Ö Ú ¸ º Ò ÏÓÐ× ¸ ʺ É ÌË ÉÙ Ù ÓÙÒ × ×Ø Ñ Ø ÓÒ ÖÓÑ Ì Ñ Ë Ö ×¸ ÈÖÓº ½¿Ø ÏÓÖ × ÓÔ ÓÒ ÂÓ Ë ÙÐ Ò ËØÖ Ø ¹ × ÓÖ È Ö ÐÐ Ð ÈÖÓ ×× Ò ´¾¼¼ µº µ 竹房,中田,工藤,田中,関口:多様な資源を 事前予約で同時確保するためのグリッドコアロ ÊË, ケーションシステムフレームワーク Ö 情報処理学会論文誌コンピューティングシステム ´ ˾¼µ, ÎÓк ¸ ÆÓºËÁ ½ ¸ ÔÔº¿¾ß ¾ ´¾¼¼ µº µ Ì Ù× ¸ º Ø Ðº × Ò Ó ÓÑ Ò ÙØ ÓÖ Þ Ø ÓÒ¹ × À Ö Ö Ð ×ØÖ ÙØ Ê ×ÓÙÖ ÅÓÒ ØÓÖ Ò ËÝ×Ø Ñ Ò ÓÓÔ Ö Ø ÓÒ Û Ø Ê ×ÓÙÖ Ê × ÖÚ Ø ÓÒ¸ ÈÖÓº ÀÈ × ¾¼¼ ´ Ò ÔÖ Òص ´¾¼¼ µº µ ÃÙ Ó ¸ ̺ ÊÁ ÓÑÔÙØ Ò Ò ÖÓÐ Ó Ô ÓØÓÒ Ò ØÛÓÖ ×¸ ÈÖÓº ËÈÁ × È × ¬ ÇÔØ Ð ÓÑÑÙÒ Ø ÓÒ× ´ ÈÇ ¾¼¼ µ¸ ÎÓк ½¿ ¸ ½¿ ½¿ ´¾¼¼ µº µ ¹Ð Ñ : ØØÔ »»ÛÛÛº ¹Ð Ñ ºÒ Ø»º ½¼µ Ù ¸ ʺú¸ Å Ò ÒØ ¸ ̺ĺ Ò ÇÖÐ Ò¸ º º Æ ØÛÓÖ ÐÓÛ× Ì ÓÖݸ Ð ÓÖ Ø Ñ׸ Ò Ô¹ ÔÐ Ø ÓÒ׸ ÈÖ ÒØ À ÐÐ ´½ ¿µº ½½µ ÄÈà ´ ÆÍ Ä Ò Ö ÈÖÓ Ö ÑÑ Ò Ã Øµ ØØÔ »»ÛÛÛº ÒÙºÓÖ »×Ó ØÛ Ö » ÐÔ » ÐÔ º ØÑк ½¾µ 安藤誠士郎,合田憲人:グリッド上の事前予約 スケジューリング手法の性能評価,情報処理学会 研究報告 ¾¼¼ ¹ÀÈ ¹½½¿,ÔÔº¿ ß ¾ ´¾¼¼ µº
© Copyright 2025 ExpyDoc