高品質分散実行環境のための 計算・ネットワーク資源のグローバルスケジューリング手法 竹 房 あ つ 子ݽ 工 藤 知 宏ݽ 中 田 田 中 秀 良 基ݽ 夫ݽ 高品質分散実行環境の構築に際し，ユーザの要求を満たす高品質資源群を適切に確保しつつ，グ リッド上の資源群を有効活用するためには，グローバルスケジューリングが重要な課題となる．本稿 では，高品質分散実行環境の構築を目的とした計算・ネットワーク資源のオンライングローバルスケ ジューリング手法を提案する．提案手法では，ユーザの計算機及びネットワークに関する資源要求に 対して，複数資源マネージャからある時間帯における動的資源情報を入手し，その情報から複数の予 約プランを組合せ最適化問題を解くことにより作成する．シミュレーションによる評価により，提案 手法の有効性を示す． À Ë Ñ Ó ¹ÕÙ Ð ØÝ ÐÓ ×ØÖ Ø×Ù Ó Ì Ð Ë ÙØ ÙÐ Ò Ó Ü ÙØ ÓÒ Ù× ¸ ݽ ÓÑÔÙØ Ò Ò ÒÚ ÖÓÒÑ ÒØ× À ÑÓØÓ Æ Ò Ó× ¸ ݽ ݽ Ó Ì Ò Æ ØÛÓÖ ÌÓÑÓ Ê ×ÓÙÖ × ÓÖ ÖÓ ÃÙ Ó Ý½ ÐÓ Ð × ÙÐ Ò × Ñ ØÓ × Ø × Ý Ö ÕÙ Ö Ñ ÒØ× ÖÓÑ Ù× Ö× Ò Ö ×ÓÙÖ Ñ Ò ×ØÖ ØÓÖ× × ÓÒ Ó Ý ××Ù × ÓÖ ÓÒ×ØÖÙØ Ò ¹ÕÙ Ð ØÝ ×ØÖ ÙØ Ü ÙØ ÓÒ ÒÚ ÖÓÒÑ ÒØ × ÓÒ Ú Ò Ö × ÖÚ Ø ÓÒ׺ Ï ÔÖÓÔÓ× Ò ÓÒÐ Ò ÐÓ Ð × ÙÐ Ò × Ñ ÓÖ ÓØ ÓÑÔÙØ Ò Ò Ò ØÛÓÖ Ö ×ÓÙÖ × ÓÖ Ø Ø ÔÙÖÔÓ× º ÓÖ Ù× Ö Ö ×ÓÙÖ Ö ÕÙ Ö Ñ Òظ Ø ÔÖÓÔÓ× × Ñ ×ÓÐÚ ÓÑ Ò Ø ÓÒ Ð ÓÔØ Ñ Þ Ø ÓÒ ÔÖÓ Ð Ñ ØÓ Ø ÖÑ Ò ÑÙÐØ ÔÐ Ö × ÖÚ Ø ÓÒ ÔÐ Ò× Ý Ù× Ò ÝÒ Ñ Ö ×ÓÙÖ Ò ÓÖÑ Ø ÓÒ ÖÓÑ Ö ×ÓÙÖ Ñ Ò Ö׺ Ì × ÑÙÐ Ø ÓÒ Ö ×ÙÐØ× × ÓÛ « Ø Ú Ò ×× Ó ÓÙÖ ÐÓ Ð × ÙÐ Ò × Ñ º ½º はじめに グリッドとネットワーク資源管理技術により，複数 管理組織の提供する多様な資源で構成される高品質分 散実行環境を動的に構築することが可能になった．特 に，帯域が保証されたパスネットワークを資源のひと つとして，計算機やストレージ等の資源と同時に確保 し，利用する試みが国内外で複数行われている½µß¿µ ． 高品質分散実行環境を提供するには，各資源を管理 する資源マネージャ が，性能保証機能と同時確 保のための事前予約機能を有することが前提となる． 計算資源のみを対象としたマルチクラスタの同時確保 µ µ では， グリッドスケジューラや バッチキュー予測サービスのように各ローカルスケ ジューラのキューの利用状況の取得または予測により， 事前予約機能がない状況での同時確保を実現してい る．しかしながら，これらの手法は複数資源が同時に ´Êŵ ÃÇ Ä É ÌË Ý½ 産業技術総合研究所 Ù×ØÖ Ð Ë Ò Ò Æ Ø ÓÒ Ð ÁÒ×Ø ØÙØ Ó Ì ÒÓÐÓ Ý ´ ÁË̵ Ú Ò ÁÒ¹ 利用可能になることを保証するものではないため，資 源利用に対する課金が発生する場合はユーザが不利益 を被るおそれがある．よって，複数資源の同時確保を 確実に実現するためには事前予約が重要な機能であり， 我々は，性能保証および事前予約機能を有する資源マ ネージャと連携し，高品質分散実行環境を構築・利用 するための 資源管理フレームワーク µ を開 では，グローバル資源コーディ 発している． ネータ が複数 と連携してユーザの要求す る資源群を確保する． ユーザの要求を満たす高品質資源群を適切に確保 しつつ，グリッド上の資源群を有効活用するために は， におけるスケジューリング（グローバルス ケジューリングと呼ぶ）手法が重要な課題となる．ユー ザの観点では，指定した性能を保証する資源群を 早い時刻に確保する， 価格の安い資源群を確保す る， 価格が高くても品質 可用性等 優先で確保 する，等の選択肢がありうる．一方，資源管理の観点 では，上記を考慮することに加え， 複数資源提供 省エネや連 者に対して平等に負荷を割り当てる， Ö ÊË Ö ÊË ´ Ê µ ÊÅ Ê ´µ ´µ ´µ ´ µ ´ µ ´ µ ②③④⑤ ⑥④⑦⑧④③⑨ ❴ ❵❨❪❬❛❜ ❝❞❡❢ ❏❑ ❆ ■ ❴ ❵❨❡❪❬❛❜ ●❍ ❴ ❄ ❄❅ ❝❞❡❢ ❵❨❪❬❛❜ ❇❈❉❊❋ ❝❞❡❢ ▲▼◆❖◗❋❘❙❘▼◆❘❚❯◗ ❱❲❳❳ ❨▼❘◗❋❘❙❘ ▼◆❘❚❯◗ ❇❲❳❳ ❩❬◆▼❘❭❪ ❱ ❫❭❬◆ ✪✫✬✭ ✮ ✯✣✭✰✥✱ ✲✳✴✵✶✷✸✹✺ ✌✍ ✍ ❃ ❂✳✶✼ ✄✎✏ ✁✂✄☎✆✝✁ ✸✴✸✹✷✿ ✻✼✽✶ ✻✼✽✶ ✔✄✓✟✠✄✆✟✓✞ ✁✂✄☎✆✝✁ ✑✄✄✆✒ ✟✓✏✠✄✆ ✕✡✂✠✁✖ ☛✔✕☞ ✁✞✟✂✠ ✆✡ ☛ ☞ ☛✌ ✑☞ ✾✷✿✳❀✿❁✳❀✳❂✺ ✲✳✴✵✶✷✸✹✺ ✻✼✽✶ ✻✼✽✶ ✜✘✚ ✘✘ ✚✘✙ ✗✘✙ ✚✘✙ ✛✘✙ ✢✣✤✥✦✧ ★ 図 ½ ✜✘✚ ✙✛ ✙✛ ✚✘✙ ✗✘✙ ✘✘ ✢✣✤✥✦✧ ✩ ✛✘✙ ✚✘✙ ´ µ ÊÅ グローバルスケジューリングモデル 資源管理フレームワークの概要 高品質分散実行環境構築・利用のため，我々は図 ½ に示す資源管理フレームワーク の開発を 進めている．本フレームワークは資源管理システム µ ，資源レジストリ ，資源モニタリング µ システム で構成される．図中の ， は一組織，あるいは連携関係の複数組織を表し，ユー ザに対して管理組織を跨った高品質分散実行環境を事 前予約に基づいて提供する． はグローバル資源コーディネータ と 各資源を管理する資源マネージャ で構成され， と が連携してユーザに高品質分散実行環境 を提供する．図 における ， ， は， それぞれネットワーク，計算，ストレージの を表 す． は複数存在し，複数 が階層的に連携 して，あるいは独立した 間で競合して各ユーザ の要求する資源を確保する． のうち，グローバ ルスケジューリング機能（プランナ）をもつものが， ¾º½ Ö ÊË ´ÊÅ˵ ´Êʵ ´Å˵ ÊÅË Ê ÊÅ Ê ¾ ユーザの資源要求とプランナによる予約プラン ↕➙➛ ➛↔↕ ➡➜➣ ➠➈➥➢ ➤↕➞ 資源管理フレームワークの概要 携関係から，特定の資源に優先的に割り当てる， ユーザのサービスレベルにより，高レベルのユーザが 確実に資源確保できるように配慮する，等の方針が考 えられる．これらの多様な指標を考慮しつつ，分散す る計算資源および拠点間ネットワーク資源を同時確保 するための適切なグローバルスケジューリング手法に 関する議論は不十分である． 本研究では，高品質分散実行環境の構築を目的とし た計算・ネットワーク資源のオンライングローバルス ケジューリング手法を提案し，シミュレーションでの 評価により，その有効性を示す．提案するグローバル スケジューリング手法は，ユーザの計算機及びネット ワークに関する資源要求に対して，複数 から利 用可能な資源情報を入手し，複数の予約プランを組合 せ最適化問題を解くことにより作成する．評価では， ユーザの要求と資源管理要件に対し，提案手法が有効 であり，その予約成功率が高いことを示す． ¾º 図 ⑥④③④⑤⑩❶⑨❷❸❹ ❺❻❶❹ ❾❿➀➁➂➃ ➅ ❣❤✐❥❧ ❑ ❆ ■❏ ❼❽ ❍ ❣❤✐❥♠ ● ❇❈❉ ❊❋ ❄❅ ❄ ❣❤✐❥❦ ❾ ❿➀➁➂➃ ➄ ❣✐♥♦✐♣❤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 2024 ExpyDoc
