(57)【要約】  本発明は、高性能コンピュータ・システムにおいて、順序制約のある並列タスクから成るアプリケーションをスケジュールすることに関する。コンピュータ・システムは、各々が異なる電圧供給レベルで動作可能な複数のプロセッサを有する。まず、タスクの計算コスト及び通信コストに基づき、タスクの優先順位が決定される。次に、タスクの優先順位に基づき、各タスクにプロセッサ及び電圧レベルの両方を割り当てるが、プロセッサ及び電圧レベルは、プロセッサ及び電圧レベルの異なる組合せにおいて、タスクを実行するためのエネルギ消費及び完了時間と比較した場合に、タスクを実行するためのエネルギ消費及び完了時間を実質的に最小化する。本発明の利点は、スケジューリングが完了時間（メイクスパン）だけでなく、エネルギ消費も考慮することである。本発明の態様は、方法、ソフトウェア、コンピュータのスケジューリング・モジュール、及びスケジュールを含む。
2012504800.tif 000002
【特許請求の範囲】
【請求項１】
アプリケーションが、２つ以上の順序制約のある並列タスクから成り、
異種コンピューティング・システムが、各々が異なる電圧供給レベルで動作可能な複数のプロセッサから成り、
前記タスクの計算コストおよび通信コストに基づいて、前記タスクの優先順位を決定するステップと、
前記タスクの優先順位の順に、各タスクにプロセッサおよび電圧レベルの両方を割り当てるステップであって、プロセッサおよび電圧レベルの異なる組み合わせにおいて、前記タスクを実行するためのエネルギー消費および完了時間を比較した場合に、前記プロセッサおよび前記電圧レベルが、前記タスクを実行するための前記エネルギー消費および前記完了時間を実質的に最小化するステップと、
を含む、前記異種コンピューティング・システムにおいて実行するための前記アプリケーションをスケジュールするための方法。
【請求項２】
タスク、プロセッサ、および電圧レベルの異なる組み合わせについて、実質的に最小化することが前記エネルギー消費および前記完了時間の両方を示すファクタを決定することを含む、請求項１に記載の方法。
【請求項３】
実質的に最小化することが、エネルギー消費の最小化と完了時間の最小化との間の実質的に最良のトレードオフを示すファクタを有する割り当てのための前記組み合わせを選択することを含む、請求項２に記載の方法。
【請求項４】
エネルギー消費を示す前記ファクタを決定することが、その組み合わせの前記電圧レベルにおける、そのタスクの計算コストに基づく、請求項２または請求項３に記載の方法。
【請求項５】
完了時間を示す前記ファクタを決定することが、その組み合わせの前記プロセッサおよび前記電圧レベルにおける、そのタスクの計算コストに基づく、請求項２、請求項３または請求項４に記載の方法。
【請求項６】
完了時間を示す前記ファクタを決定することが、その組み合わせの前記プロセッサおよび前記電圧レベルにおける、そのタスクの推定開始時刻と前記計算コストとの和に基づく、請求項５に記載の方法。
【請求項７】
前記推定開始時刻が、そのタスクに先行する最も影響力の大きいタスクの推定終了時刻と、適切な場合は、前記最も影響力の大きいタスクに割り当てられたプロセッサおよびその組み合わせの前記プロセッサの間の通信コストとに基づく、請求項６に記載の方法。
【請求項８】
完了時間を示す前記ファクタを決定することが、より長い完了時間をもたらすプロセッサおよび電圧レベルの組み合わせにおけるタスクにペナルティを課すことを含む、請求項５、請求項６または請求項７に記載の方法。
【請求項９】
各タスクについて、
プロセッサおよび電圧レベルの異なる組み合わせにおいて、前記タスクのための前記エネルギー消費および前記計算時間を決定するステップと、
ある組み合わせについて、前記決定された計算時間が、前記アプリケーションのメイクスパンの増加を引き起こさず、かつ、前記決定されたエネルギー消費が、前記割り当てられたプロセッサおよび割り当てられた電圧における前記タスクの前記エネルギー消費よりも小さい場合、前記タスクをプロセッサおよび電圧レベルのその組み合わせに割り当て直すステップと
をさらに含む、請求項１から請求項８のいずれか一項に記載の方法。
【請求項１０】
各タスクの前記優先順位は、前記タスクが一部である順序制約のあるタスクの最長経路に沿った、各タスクの計算コストおよび通信コストにそれぞれ基づく、請求項１から請求項９のいずれか一項に記載の方法。
【請求項１１】
各タスクの前記優先順位が、前記タスクのｂレベルまたはｔレベルに基づく、請求項１０に記載の方法。
【請求項１２】
前記スケジューリングに従って前記タスクを実行するステップをさらに含む、請求項１から請求項１１のいずれか一項に記載の方法。
【請求項１３】
前記異種コンピューティング・システムが、マルチプロセッサ・コンピューティング・システムである、請求項１から請求項１２のいずれか一項に記載の方法。
【請求項１４】
前記タスクが異種的である、請求項１から請求項１３のいずれか一項に記載の方法。
【請求項１５】
請求項１から請求項１４のいずれか一項に記載の方法を実行するようにコンピュータを動作させる、コンピュータ読み取り可能な媒体に記録されたコンピュータ命令を含むソフトウェア。
【請求項１６】
請求項１から請求項１１のいずれか一項に記載の方法から生成される異種コンピューティング・システムにおいて、アプリケーションを実行するためのスケジュール。
【請求項１７】
アプリケーションが、２つ以上の順序制約のある並列タスクから成り、
異種コンピューティング・システムが、各々が異なる電圧供給レベルで動作可能な複数のプロセッサから成り、
スケジューリング・モジュールが、
前記タスクの優先順位を、前記タスクの計算コストおよび通信コストに基づいて決定することと、
前記タスクの優先順位の順に、そのタスクにプロセッサおよび電圧レベルの両方を割り当てることであって、プロセッサおよび電圧レベルの異なる組み合わせにおいて、そのタスクを実行するためのエネルギー消費および完了時間に前記タスクを割り当てることを比較した場合に、前記プロセッサおよび前記電圧レベルが、そのタスクを実行するためのエネルギー消費および完了時間を実質的に最小化するように割り当てることと
を行うように動作可能である、
前記異種コンピューティング・システムにおいて実行するための前記アプリケーションをスケジュールするためのスケジューリング・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、異種コンピューティング・システム（ａ  ｈｅｔｅｒｏｇｅｎｅｏｕｓ  ｃｏｍｐｕｔｉｎｇ  ｓｙｓｔｅｍ）において実行するためにアプリケーションをスケジュールすることに関する。詳細には、ただし限定することなく、本発明は、各々が異なる電圧供給レベルで動作可能な複数のプロセッサから成るマルチプロセッサ・コンピュータ・システムにおいて、順序制約のある並列タスク（ｐｒｅｃｅｄｅｎｃｅ  ｃｏｎｓｔｒａｉｎｅｄ  ｐａｒａｌｌｅｌ  ｔａｓｋｓ）から成るアプリケーションをスケジュールすることに関する。本発明の態様は、方法、ソフトウェア、コンピュータのスケジューリング・モジュール、およびスケジュールを含む。
【背景技術】
【０００２】
過去数十年にわたる計算量およびデータ量の激しい増加が、性能の向上に注力するよう、コンピュータ・アーキテクチャの研究者および設計者を促してきた。その結果、マルチコア・マイクロプロセッサ、大容量記憶デバイス、および超高速通信デバイスなど、リソース集約的（ｒｅｓｏｕｒｃｅ−ｉｎｔｅｎｓｉｖｅ  ｔｅｃｈｎｏｌｏｇｉｅｓ）な技術が開発された。これらの強力なリソースの効率的な使用は、数十万もの多数のプロセッサが存在する、たとえばグリッドおよびクラウドなどのマルチプロセッサ・コンピュータ・システム（ＭＣＳ：ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ  ｃｏｍｐｕｔｅｒ  ｓｙｓｔｅｍ）にとっては特に、常に重要な問題であった。
【０００３】
科学分野および工学分野における順序制約のある並列アプリケーションは、最も一般的なアプリケーション・モデルであるので、同種および異種のコンピューティング・システムにおいて、これらのアプリケーションをスケジュールする問題（タスク・スケジューリング）が、過去数十年にわたって広範に研究されてきた。しかし、タスク・スケジューリングにおけるほとんどの努力は、アプリケーション完了時間（メイクスパン／スケジュール長）の最小化および時間計算量の最小化という、２つの問題に集中されてきた。言い換えると、タスク・スケジューリング・アルゴリズムの主な目的は、最小量のスケジューリング時間で、与えられたアプリケーションの最適なスケジュールを生成することである。
【０００４】
特に高性能コンピューティング・システム（ＨＰＣＳ：ｈｉｇｈ−ｐｅｒｆｏｒｍａｎｃｅ  ｃｏｍｐｕｔｉｎｇ  ｓｙｓｔｅｍ）における、スケジューリングの際のエネルギー消費に多くの注意が払われるようになったのは、つい最近のことである。これらＨＰＣＳにおけるエネルギー消費問題は、様々な金銭的、環境的、およびシステムの性能的な懸念をもたらす。サーバによる電力消費に関する最近の研究（非特許文献２）は、関連する冷却設備および補助装置を含む、世界中のサーバの電気使用コストが、２００５年には、７２億米ドルであったことを示している。同研究は、その年の電気消費が、２０００年の電気消費と比較して、２倍であったことも指摘している。明らかに、発電が絡んだ環境問題が存在する。
【０００５】
今日のインテル社製Ｉｔａｎｉｕｍ  ２プロセッサに集積されるトランジスタの数は、約１０億に達している。この比率が継続した場合、将来のインテル社製プロセッサによって生成される（平方センチメートル当たりの）熱は、太陽表面の同じ面積当たりの熱を超過する（非特許文献３）。このことは、システムの信頼性を悪化させ、最終的に貧弱なシステム性能をもたらす可能性を暗示している。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｈ．  Ｔｏｐｃｕｏｕｇｌｕ，  Ｓ．  Ｈａｒｉｒｉ，およびＭ．  −Ｙ．  Ｗｕ，  Ｐｅｒｆｏｒｍａｎｃｅ−Ｅｆｆｅｃｔｉｖｅ  ａｎｄ  Ｌｏｗ−  Ｃｏｍｐｌｅｘｉｔｙ  Ｔａｓｋ  Ｓｃｈｅｄｕｌｉｎｇ  ｆｏｒ  Ｈｅｔｅｒｏｇｅｎｅｏｕｓ  Ｃｏｍｐｕｔｉｎｇ，  ＩＥＥＥ  Ｔｒａｎｓ．  Ｐａｒａｌｌｅｌ  Ｄｉｓｔｒｉｂ．  Ｓｙｓｔ，第１３巻，第３，２６０から２７４頁，２００２年
【非特許文献２】Ｊ．  Ｇ．  Ｋｏｏｍｅｙ，  Ｅｓｔｉｍａｔｉｎｇ  ｔｏｔａｌ  ｐｏｗｅｒ  ｃｏｎｓｕｍｐｔｉｏｎ  ｂｙ  ｓｅｒｖｅｒｓ  ｉｎ  ｔｈｅ  Ｕ．Ｓ．  ａｎｄ  ｔｈｅ  ｗｏｒｌｄ
【非特許文献３】Ｇ．  Ｋｏｃｈ，  Ｄｉｓｃｏｖｅｒｉｎｇ  ｍｕｌｔｉ−ｃｏｒｅ：  ｅｘｔｅｎｄｉｎｇ  ｔｈｅ  ｂｅｎｅｆｉｔｓ  ｏｆ  Ｍｏｏｒｅ’ｓ  ｌａｗ，Ｔｅｃｈｎｏｌｏｇｙ＠Ｉｎｔｅｌ  Ｍａｇａｚｉｎｅ，２００５年７月（ｈｔｔｐ：／／ｗｗｗ．ｉｎｔｅｌ．ｃｏｍ／ｔｅｃｈｎｏｌｏｇｙ／ｍａｇａｚｉｎｅ／ｃｏｍｐｕｔｍｇ／ｍｕｌｔｉ−ｃｏｒｅ−０７０５．ｐｄｆ）
【非特許文献４】Ｍ．Ｒ．  ＧａｒｅｙおよびＤ．Ｓ．  Ｊｏｈｎｓｏｎ，  Ｃｏｍｐｕｔｅｒｓ  ａｎｄ  Ｉｎｔｒａｃｔａｂｉｌｉｔｙ：  Ａ  Ｇｕｉｄｅ  ｔｏ  ｔｈｅ  Ｔｈｅｏｒｙ  ｏｆ  ＮＰ−Ｃｏｍｐｌｅｔｅｎｅｓｓ，  Ｗ．Ｈ．  Ｆｒｅｅｍａｎ  ａｎｄ  Ｃｏ．，２３８から２３９頁，１９７９年
【非特許文献５】Ｄ．  Ｂｏｚｄａｇ，  Ｕ．  ＣａｔａｌｙｕｒｅｋおよびＦ．  Ｏｚｇｕｎｅｒ，  Ａ  ｔａｓｋ  ｄｕｐｌｉｃａｔｉｏｎ  ｂａｓｅｄ  ｂｏｔｔｏｍ−ｕｐ  ｓｃｈｅｄｕｌｉｎｇ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｈｅｔｅｒｏｇｅｎｅｏｕｓ  ｅｎｖｉｒｏｎｍｅｎｔｓ，  Ｐｒｏｃ．  Ｉｎｔ’ｌ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｍｐ．，２００５年４月
【非特許文献６】Ｍ．−Ｙ．  ＷｕおよびＤ．Ｄ．  Ｇａｊｓｋｉ，  Ｈｙｐｅｒｔｏｏｌ：  Ａ  Ｐｒｏｇｒａｍｍｉｎｇ  Ａｉｄ  ｆｏｒ  Ｍｅｓｓａｇｅ−Ｐａｓｓｉｎｇ  Ｓｙｓｔｅｍｓ，  ＩＥＥＥ  Ｔｒａｎｓ．  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ，第１巻，第３，３３０から３４３頁，１９９０年７月
【非特許文献７】Ｒ．Ｅ．  Ｌｏｒｄ，  Ｊ．  Ｓ．  Ｋｏｗａｌｉｋ，およびＳ．  Ｐ．  Ｋｕｍａｒ，  Ｓｏｌｖｉｎｇ  Ｌｉｎｅａｒ  Ａｌｇｅｂｒａｉｃ  Ｅｑｕａｔｉｏｎｓ  ｏｎ  ａｎ  ＭＩＭＤ  Ｃｏｍｐｕｔｅｒ，  Ｊ．  ＡＣＭ，第３０巻，第１，１０３から１１７頁，１９８３年１月
【非特許文献８】Ｔ．Ｈ．  Ｇｏｒｍｅｎ，  ＣＥ．  Ｌｅｉｓｅｒｓｏｎ，  ａｎｄ  ＲＸ．  Ｒｉｖｅｓｔ，  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ａｌｇｏｒｉｔｈｍｓ，  ＭＩＴ  Ｐｒｅｓｓ，１９９０年
【発明の概要】
【課題を解決するための手段】
【０００７】
第１の態様では、本発明は、アプリケーションが、２つ以上の順序制約のある並列タスクから成り、異種コンピューティング・システムが、各々が異なる電圧供給レベルで動作可能な複数のプロセッサから成り、タスクの計算コストおよび通信コストに基づいて、タスクの優先順位を決定するステップと、タスクの優先順位の順に、各タスクにプロセッサおよび電圧レベルの両方を割り当てるステップであって、プロセッサおよび電圧レベルの異なる組み合わせにおいて、そのタスクを実行するためのエネルギー消費および完了時間を比較した場合に、プロセッサおよび電圧レベルが、そのタスクを実行するためのエネルギー消費および完了時間を実質的に最小化するステップとを含む、異種コンピューティング・システムにおいて実行するためのアプリケーションをスケジュールするための方法を提供する。
【０００８】
本発明の利点は、スケジューリングが、完了時間（メイクスパン）ばかりでなく、エネルギー消費も考慮することである。本発明は、完了時間とエネルギー消費の両方のバランスをとる方法で、優先順序順に、特定の電圧レベルにあるプロセッサにタスクを割り当てるために、異種ネットワークの一部を形成するプロセッサの異なるキャパシティを考慮することができる。
【０００９】
タスク、プロセッサ、および電圧レベルの異なる組み合わせについて、実質的に最小化することがエネルギー消費および完了時間の両方を示すファクタを決定することを含むことができる。ファクタは、複数のファクタから成ることができる。
【００１０】
これは、エネルギー消費の最小化と完了時間の最小化との間の実質的に最良のトレードオフを示すファクタを有する割り当てのための組み合わせを選択することを含むことができる。
【００１１】
エネルギー消費を示すファクタを決定することが、その組み合わせの電圧レベルにおける、そのタスクの計算コストに基づくことができる。
【００１２】
完了時間を示すファクタを決定することが、その組み合わせのプロセッサおよび電圧レベルにおける、そのタスクの計算コストに基づくことができる。
【００１３】
完了時間を示すファクタを決定することは、その組み合わせのプロセッサおよび電圧レベルにおける、そのタスクの推定開始時刻と計算コストとの和に基づくことができる。
【００１４】
推定開始時刻が、そのタスクに先行する最も影響力の大きいタスクの推定終了時刻と、適切な場合は、最も影響力の大きいタスクに割り当てられたプロセッサおよびその組み合わせのプロセッサの間の通信コストとに基づくことができる。
【００１５】
完了時間を示すファクタを決定することが、より長いタスク完了時間をもたらすプロセッサおよび電圧レベルの組み合わせにおけるタスクにペナルティを課すことを含むことができる。
【００１６】
本方法は、各タスクについて、プロセッサおよび電圧レベルの異なる組み合わせにおいて、タスクのためのエネルギー消費および計算時間を決定するステップと、ある組み合わせについて、決定された計算時間が、アプリケーションのメイクスパンの増加を引き起こさず、かつ、決定されたエネルギー消費が、割り当てられたプロセッサおよび割り当てられた電圧におけるタスクのエネルギー消費よりも小さい場合、タスクをプロセッサおよび電圧レベルのその組み合わせに割り当て直すステップと、をさらに含むことができる。本発明のこの実施形態の利点は、メイクスパンの増加を伴わずに、エネルギー消費のさらなる低減をもたらすかどうかを識別するために、スケジュールに対する何らかの変更がスケジュールを評価できることである。
【００１７】
各タスクの優先順位は、タスクがその一部である順序制約のあるタスクの最長経路に沿った、各タスクの計算コストおよび通信コストにそれぞれ基づくことができる。各タスクの優先順位が、タスクのｂレベルまたはｔレベルに基づくことができる。
【００１８】
本方法は、スケジューリングに従ってタスクを実行するステップをさらに含むことができる。
【００１９】
異種コンピューティング・システムが、高性能コンピューティング・システムなどのマルチプロセッサ・コンピューティング・システムであり、タスクは、異種的とすることができる。
【００２０】
さらなる態様では、本発明は、上述の方法を実行するようにコンピュータを動作させる、コンピュータ読み取り可能な媒体に記録されたコンピュータ命令を含むソフトウェアを提供する。
【００２１】
さらに別の態様では、本発明は、上述の方法から生成される異種コンピューティング・システムにおいて、アプリケーションを実行するためのスケジュールを提供する。
【００２２】
別の態様では、本発明は、アプリケーションが、２つ以上の順序制約のある並列タスクから成り、異種コンピューティング・システムが、各々が異なる電圧供給レベルで動作可能な複数のプロセッサから成り、スケジューリング・モジュールが、タスクの優先順位を各タスクの計算コストおよび通信コストに基づいて決定することと、各タスクについて、タスクの優先順位に従って、タスクにプロセッサおよび電圧レベルの両方を割り当てることであって、タスクをプロセッサおよび電圧レベルの異なる組み合わせに割り当てることを比較した場合に、そのプロセッサおよび電圧レベルが、タスクを実行するためのエネルギー消費および完了時間を実質的に最小化するように割り当てることを行うように動作可能である、異種コンピューティング・システムにおいて実行するためのアプリケーションをスケジュールするためのスケジューリング・システムを提供する。
【００２３】
本発明の一例を図面を参照して説明する。
【図面の簡単な説明】
【００２４】
【図１】本例で使用される電圧−相対速度ペアを示す表である。
【図２】本例で使用されるアプリケーションの簡単なタスク・グラフを示す図である。
【図３】図１に示されたタスクのｔレベルおよびｂレベルのタスク優先順位を示す表である。
【図４】図１に示されたタスクの計算コストを示す表である。
【図５】本例のエネルギー・モードを示す図である。
【図６】本例のエネルギー・コンシャス・スケジューリング（ＥＣＳ：ｅｎｅｒｇｙ  ｃｏｎｓｃｉｏｕｓ  ｓｃｈｅｄｕｌｉｎｇ）の方法を示し、メイクスパン保存エネルギー低減（ＭＣＥＲ：ｍａｋｅｓｐａｎ−ｃｏｎｓｅｒｖａｔｉｖｅ  ｅｎｅｒｇｙ  ｒｅｄｕｃｔｉｏｎ）を含む図である。
【図７】（ａ）および（ｂ）は、それぞれＨＥＦＴアルゴリズムおよびＤＢＵＳアルゴリズム（従来技術）によって生成された、図１のタスク・グラフのためのスケジュールを概略的に示す図である。
【図８】（ａ）ＭＣＥＲを用いないＥＣＳが使用される本例、および（ｂ）ＭＣＥＲを用いるＥＣＳが使用される本例において生成された、図１のタスク・グラフのためのスケジュールを概略的に示す図である。
【図９】（ａ）ＭＣＥＲを用いないＥＣＳ＋ｉｄｌｅが使用される本例、および（ｂ）ＭＣＥＲを用いるＥＣＳ＋ｉｄｌｅが使用される本例において生成された、図１のタスク・グラフのためのスケジュールを概略的に示す図である。
【図１０】図７、図８、および図９の６つの異なる方法によって生成されたスケジュールのエネルギー消費を比較した表である。
【図１１】以下で詳述される実験において使用されるパラメータを要約した表である。
【図１２】以下で詳述される実験の比較結果を示す表である。
【発明を実施するための形態】
【００２５】
本例では、コンピュータ・クラスタを形成する５０個の異種プロセッサを説明する。プロセッサは、異なる電圧供給レベルで動作することができ、棚に積み重ねられたプロセッサのように、高帯域幅の接続を使用して、一様またはランダムな方法で相互に接続される。コンピュータ・クラスタは、例えば、大規模なデータセットにおける複数のパターン・マッチング解析など、複数の順序制約のある並列可能なタスクから成るアプリケーションの実行を受け持っている。本例では、各タスクについての事前情報が知られており、アプリケーションの性能は、リアルタイムの期限（ｒｅａｌ−ｔｉｍｅ  ｄｅａｄｌｉｎｅｓ）に基づいていない。
【００２６】
本明細書においてスケジューリング・システムとして知られる１つのプロセッサが、スケジュールの生成を受け持っている。スケジューリング・システムは、クラスタの一部を形成することができ、またはクラスタに追加することができる。スケジューリング・システムは、プロセッサ、各プロセッサの可能な電圧レベル、およびタスクについての情報を受け取り、保存することができ、この情報を使用して、以下で説明される方法でスケジュールを生成することができる。スケジューリング・システムはまた、各プロセッサにスケジュールのそれぞれの部分を受け取らせる。すなわち、生成されたスケジュールは、タスクを特定のプロセッサおよび電圧に割り当てる。各タスクは、タスク、そのタスクに割り当てられた電圧レベル、および実行のための時間についての情報を、スケジューリング・システムから直接的または間接的に受け取る。
【００２７】
本例では、メイクスパンばかりでなく、エネルギー消費も考慮する、エネルギー・コンシャス・スケジューリング（ＥＣＳ：ｅｎｅｒｇｙ  ｃｏｎｓｃｉｏｕｓ  ｓｃｈｅｄｕｌｉｎｇ）ヒューリスティックが説明される。このヒューリスティックは、事前予約および周波数−電圧ペアの様々な組を使用して、疎結合のＨＰＣＳに容易に適用することができる。ＥＣＳは、エネルギー消費を低減するために、動的電圧スケーリング（ＤＶＳ：ｄｙｎａｍｉｃ  ｖｏｌｔａｇｅ  ｓｃａｌｉｎｇ）を組み込むように考案されている。これは、スケジュール（メイクスパン）の質とエネルギー消費の間にトレードオフ（ａ  ｔｒａｄｅ−ｏｆｆ）が存在することを意味する。
【００２８】
ＥＣＳは、これら２つの性能上の留意事項のバランスをとりながら、このトレードオフに効果的に対処する。さらに、ＭＣＥＲ技法を使用するエネルギー低減フェーズが、ＥＣＳに組み込まれる。ＭＣＥＲフェーズでは、スケジューリング・フェーズで生成された現在のスケジュールが精査され、そのスケジュールに対する何らかの変更が、メイクスパンの増加を伴わずに、エネルギー消費をさらに低減するかどうかが識別される。ＥＣＳの低い時間計算量にも注目すべきである。
【００２９】
今から、本例で使用される、システム・モデル、アプリケーション・モデル、エネルギー・モデル、およびスケジューリング・モデルについて説明する。
【００３０】
〔システム・モデル〕
本研究において使用される対象システムは、完全に相互接続されたｐ個の異種プロセッサ／マシンの集合Ｐから成る。各プロセッサｐｊ∈Ｐは、ＤＶＳ対応であり、言い換えると、各プロセッサは、異なるＶＳＬ（すなわち異なるクロック周波数）で動作することができる。各プロセッサｐｊ∈Ｐについて、ｖ個のＶＳＬの集合Ｖｊは、ＶＳＬの４つの異なる組の間にランダムおよび一様に分布させられる（図１を参照）。プロセッサは、アイドリング中もエネルギーを消費し、最低電圧が供給されると仮定されるのは、プロセッサがアイドリングしているときである。クロック周波数遷移オーバヘッド（ｃｌｏｃｋ  ｆｒｅｑｕｅｎｃｙ  ｔｒａｎｓｉｔｉｏｎ  ｏｖｅｒｈｅａｄｓ）は、無視し得るほどの時間量（例えば１０μｓ〜１５０μｓ）しか費やさないので、本例では、これらのオーバヘッドについては考慮しない。プロセッサ間通信は、競合が生じないすべてのリンク上で同じ速度で実行されると仮定される。受信側プロセッサ上でタスクが実行されている最中に、メッセージを１つのプロセッサから別のプロセッサに送信できることも仮定され、これは多くのシステムにおいて可能である。
【００３１】
〔アプリケーション・モデル〕
並列プログラムは、一般に、有向非巡回グラフ（ＤＡＧ：ｄｉｒｅｃｔｅｄ  ａｃｙｃｌｉｃ  ｇｒａｐｈ）によって表すことができる。ＤＡＧ  Ｇ＝（Ｎ，Ｅ）は、ｎ個のノードの集合Ｎと、ｅ個のエッジの集合Ｅとから成る。ＤＡＧは、タスク・グラフ（ｔａｓｋ  ｇｒａｐｈ）またはマクロデータフロー・グラフ（ｍａｃｒｏ−ｄａｔａｆｌｏｗ  ｇｒａｐｈ）とも呼ばれる。一般に、ノードは、アプリケーションから分割されたタスクを表し、エッジは、順序制約を表す。タスクｎｉとタスクｎｊの間のエッジ（ｉ，ｊ）∈Ｅは、タスク間通信も表す。言い換えると、タスクｎｉの出力は、タスクｎｊがその実行を開始するために、タスクｎｊに送られなければならない。先行タスクが存在しないタスクは、入口タスクｎｅｎｔｒｙと呼ばれ、一方、出口タスクｎｅｘｉｔは、いかなる後続タスクも有さないタスクである。タスクｎｉの先行タスクのうち、最遅時刻に通信を完了する先行タスクは、タスクｎｉの最も影響力の大きいペアレント（ＭＩＰ：ｍｏｓｔ  ｉｎｆｌｕｅｎｔｉａｌ  ｐａｒｅｎｔ）と呼ばれ、ＭＩＰ（ｎｉ）によって表される。タスク・グラフの最長経路は、クリティカル・パス（ＣＰ：ｃｒｉｔｉｃａｌ  ｐａｔｈ）である。
【００３２】
ｗｉによって表されるタスクｎｉ上の重さは、タスクの計算コストである。加えて、プロセッサｐｊ上におけるタスクの計算コストは、ｗｉ，ｊによって表され、その平均計算コストは、
【数１】
2012504800.tif 000003
によって表される。
【００３３】
ｃｉ，ｊによって表されるエッジ上の重さは、２つのタスクｎｉとｎｊの間の通信コストを表す。しかし、通信コストは、２つのタスクが異なるプロセッサに割り当てられた場合に限って必要とされる。言い換えると、タスクが同じプロセッサに割り当てられた場合の通信コストは、無視することができる。すなわち、０とすることができる。
【００３４】
プロセッサｐｊにおけるタスクｎｉの最早開始時刻および最早終了時刻は、
【数２】
2012504800.tif 000004
によって定義され、ここで、ｐｋは、タスクｎｉのＭＩＰがスケジュールされたプロセッサであり、
【数３】
2012504800.tif 000005
である。
【００３５】
なお、同じプロセッサ上でスケジュールされた別のタスクの実際の終了時刻が、ＥＳＴ（ｎｉ，ｐｊ）よりも遅い場合、ＡＳＴ（ｎｉ，ｐｊ）およびＡＦＴ（ｎｉ，ｐｊ）によって表されるプロセッサｐｊにおけるタスクｎｉの実際の開始時刻および終了時刻が、その最早開始時刻ＥＳＴ（ｎｉ，ｐｊ）および最早終了時刻ＥＦＴ（ｎｉ，ｐｊ）と異なり得る。
【００３６】
タスク挿入を採用する場合、タスクは、順序制約違反が生じない限り、すでにプロセッサに割り当てられた２つの連続するタスクの間のアイドル・タイムスロット（ｔｈｅ  ｉｄｌｅ  ｔｉｍｅ  ｓｌｏｔ）内にスケジュールすることができる。この挿入スキーム（Ｔｈｉｓ  ｉｎｓｅｒｔｉｏｎ  ｓｃｈｅｍｅ）は、粒度の細かいタスクを用いて、通信集約的なタスク・グラフのプロセッサ利用度を高めることに特に貢献する。
【００３７】
簡単なタスク・グラフが、図２に示されており、その詳細が、図３および図４の表に示されている。図３の表に示された値は、２つの頻繁に使用されるタスク優先順位決定方法である、ｔレベルおよびｂレベルを使用して計算されている。なお、計算コストおよび通信コストはともに、すべてのモードおよびリンクにわたって平均されている。タスクのｔレベルは、タスク・グラフの入口タスクからのノードの最長経路に沿った、計算コストと通信コストの和として定義される。タスク自体は、計算から除外される。対照的に、タスクのｂレベルは、タスク・グラフの出口タスクからのタスクの最長経路に沿って、（タスクを包含して）計算コストと通信コストを合算することによって計算される。本例では、ｂレベルが使用される。
【００３８】
通信対計算比（ＣＣＲ：ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｔｏ  ｃｏｍｐｕｔａｔｉｏｎ  ｒａｔｉｏ）は、タスク・グラフが、通信集約的であるか、計算集約的であるか、それともその中間であるかを示す尺度である。与えられたタスク・グラフについて、ＣＣＲは、対象システムにおける平均通信コストを平均計算コストで除算することによって計算される。
【００３９】
〔エネルギー・モデル〕
我々のエネルギー・モデルは、相補型金属酸化膜半導体（ＣＭＯＳ：ｃｏｍｐｌｅｍｅｎｔａｒｙ  ｍｅｔａｌ−ｏｘｉｄｅ  ｓｅｍｉｃｏｎｄｕｃｔｏｒ）論理回路における電力消費モデルから導き出されている。ＣＭＯＳベースのマイクロプロセッサの電力消費は、容量性電力、短絡電力、および漏れ電力の和として定義される。容量性電力（動的電力損失）は、電力消費のうち最も重要なファクタである。容量性電力（Ｐｃ）は、
【数４】
2012504800.tif 000006
として定義され、ここで、Ａは、クロック・サイクル当たりのスイッチの数であり、Ｃは、総キャパシタンス負荷であり、Ｖは、供給電圧であり、ｆは、周波数である。式（３）は、供給電圧が主要なファクタであることを明らかに示している。したがって、電力消費を引き下げるのには、供給電圧の低減が、最も大きく影響する。
【００４０】
プロセッサは、アイドリング中もある量のエネルギーを消費するので、本例で使用される順序制約のある並列アプリケーションを実行するための総エネルギー消費は、直接的および間接的なエネルギー消費から成る。直接的なエネルギー消費５８は、
【数５】
2012504800.tif 000007
として定義され、ここで、Ｖｉは、タスクｎｉが実行されるプロセッサの供給電圧であり、ｗｉ＊は、スケジュールされたプロセッサにおけるタスクｎｉの計算コスト（ｎｉの実行に要する時間量）である。
【００４１】
一方、間接的なエネルギー消費６０は、
【数６】
2012504800.tif 000008
として定義され、ここで、ＩＤＬＥｊは、プロセッサｐｊにおけるアイドリング・スロットの集合であり、Ｖｊ，ｌｏｗは、ｐｊにおける最低供給電圧であり、ｔｊ，ｋは、ｉｄｌｅｊ，ｋについてのアイドリング時間量である。その後、総エネルギー消費は、
【数７】
2012504800.tif 000009
として定義される。
【００４２】
我々のエネルギー・モデルの説明図が、図５に示されている。なお、アイドリング・スロット６０は、タスクが実行されていない（与えられたタスク・グラフの実行中の）任意の期間として定義されている。未使用プロセッサ６２のエネルギー消費は無視できると仮定しているため、エネルギー消費を計算するとき、それらは計算に入っていない。
【００４３】
〔スケジューリング・モデル〕
本例におけるタスク・スケジューリングの問題は、エネルギー消費をできるだけ低く抑えながらメイクスパンを最小化することを目指して、順序制約に違反することなく、ｎ個のタスクの集合Ｎをｐ個のプロセッサの集合Ｐに割り当てるプロセスである。タスク・グラフＧ内のｎ個のタスクのスケジューリングが完了した後では、メイクスパンは、Ｍ＝ｍａｘ｛ＡＦＴ（ｎｅｘｉｔ）｝として定義される。メイクスパンの最小化は不可欠であるが、我々の例におけるＤＡＧのタスクは、リアルタイム・システムのようには、期限に関連しない。我々のスケジューリング・モデルの２つの目的（メイクスパンの最小化およびエネルギー消費の最小化）は、互いに対立するので、スケジューリング決定は、スケジュールの質に対する、各目的の影響を考慮して行われるべきである。
【００４４】
今から、特にＭＣＳのためのタスク・スケジューリングにおける２つの特筆すべき研究について説明し、その後、電力／エネルギーを意識したスケジューリング・アルゴリズムについて説明する。
【００４５】
〔ＭＣＳにおけるスケジューリング〕
一般的なケース（非特許文献４）におけるタスク・スケジューリングの問題のＮＰ困難性のため、ヒューリスティックは、最も広く採用されているスケジューリング・モデルであり、多項式時間よりも短い時間で良好な解をもたらす。ヒューリスティックは、本質的に決定論的なそのオペレーションによって特徴付けられ、スケジューリングの問題の解の選択は、確率論的ではない。異なるヒューリスティック技法の中で、リスト・スケジューリング（ｌｉｓｔ  ｓｃｈｅｄｕｌｉｎｇ）、クラスタリングベース・スケジューリング（ｃｌｕｓｔｅｒｉｎｇ−ｂａｓｅｄ  ｓｃｈｅｄｕｌｉｎｇ）、および誘導ランダム探索（ｇｕｉｄｅｄ  ｒａｎｄｏｍ  ｓｅａｒｃｈ）が、３つの最も普及している手法である。リスト・スケジューリング・ヒューリスティックが、主要なヒューリスティック・モデルである。これは、経験的に、リスト・スケジューリング・アルゴリズムが、他のカテゴリのアルゴリズムと比較して、より低い時間計算量で優位性のある解を生成する傾向にあるためである。
【００４６】
ＨＥＦＴアルゴリズム（非特許文献１）は、低い時間計算量で、他のスケジューリング・アルゴリズムに匹敵するスケジュール長を生成する点で、高い優位性を有する。ＨＥＦＴアルゴリズムは、タスク挿入を伴った、リスト・スケジューリングの２つの典型的なフェーズ（すなわち、タスク優先順位決定およびプロセッサ選択）から成る、リスト・スケジューリング・ヒューリスティックである。
【００４７】
スケジューリングを開始する前に、タスク・グラフ内のすべてのタスクのｂレベル値が、計算され、ｂレベル値の降順で、スケジューリング・リスト内に並べられる。その後、スケジューリング・リスト内の第１のタスクから開始して、各タスクがスケジュールされる。プロセッサ選択フェーズでは、タスクｎｉの終了時刻ＥＦＴ（ｎｉ，ｐｊ）が最小化されるプロセッサｐｊが、挿入ベースの方針を使用して選択される。言い換えると、プロセッサ上ですでにスケジュールされた２つのタスクの間の最早タイムスロットに、タスクを挿入することができるが、その条件として、そのタスクの順序制約に対する違反がなく、スロットがタスクを収容するのに十分な大きさを有する必要がある。ＨＥＦＴの時間計算量は、Ｏ（ｎ  ｌｏｇ  ｎ＋（ｅ＋ｎ）ｐ）の順にある。
【００４８】
ＤＢＵＳアルゴリズム（非特許文献５）は、最初にタスクに対してＣＰベースのリスティングを実行し、タスク重複およびタスク挿入をともに用いてタスクをスケジュールする、重複ベースのスケジューリング・ヒューリスティックである。非特許文献５の実験結果は、特に通信集約的なタスク・グラフについて、ＤＢＵＳの魅力的な性能を示している。
【００４９】
その名前が暗示するように、ＤＢＵＳは、タスク・グラフをボトムアップ方式で辿って、タスク・グラフ内のタスクをスケジュールする。リスティング・フェーズでは、ＤＢＵＳは、最初にタスクのｂレベル値、ｔレベル値、およびｓｔレベル値を計算し、ＣＰタスクを識別する。ＣＰタスクは、ＣＰタスクのチャイルド・タスク（ｃｈｉｌｄ  ｔａｓｋｓ）がＣＰタスクに先行するように、これらＣＰタスクの各々のチャイルド・タスクとともにｔレベルの降順でリスト内に保存される。これらのチャイルド・タスクは、ｓｔレベルの降順で保存される。ｔレベルとｓｔレベルの間の唯一の相違は、ｓｔレベルでは、通信コストが考慮されないことである。リスト内のタスクの順序が、スケジューリング順序を決定する。
【００５０】
スケジューリング・フェーズでは、リスト内の各タスクが、スケジュールされ、すでにスケジュールされたそのチャイルド・タスクの数またはプロセッサの数のうち、どちらか小さい方の数だけ重複される。チャイルド・タスクが割り当てられたプロセッサは、カバーされるべきプロセッサと見なされる。カバーされる各プロセッサについて、スケジュールされるタスクのコピーが、その完了時間を最小化する特定のプロセッサに割り当てられ、その後、最初にスケジュールされたように、先のプロセッサ上のチャイルド・タスクを開始することができる。このプロセスは、カバーされるすべてのプロセッサが実際にカバーされるまで繰り返される。単一のタスク割り当てが２つ以上のプロセッサをカバーすることが可能である。この重複スキームの１つの難点は、プロセッサの数がタスクの数に比べて非常に少ない場合に、スケジュール長の著しい増加が起こることがあることである。これは、タスクの冗長な重複は、タスク自体にとっては有効であり得ても、そのレプリカが、非常に多くの後続の重複をレプリカが誘発させる「カスケード効果（ｃａｓｃａｄｅ  ｅｆｆｅｃｔ）」を引き起こし得るためである。ＤＢＵＳの時間計算量は、Ｏ（ｎ２ｐ２）の順にある。
【００５１】
〔エネルギーを意識したスケジューリング〕
動的電圧スケーリング（ＤＶＳ）、リソース・ハイバネーション（ｒｅｓｏｕｒｃｅ  ｈｉｂｅｒｎａｔｉｏｎ）、およびメモリ最適化を含む様々な技法が、エネルギーを節約するために、研究および開発された。ＣＰＵは、ＨＰＣＳにおける電力消費の主要な源であるので（非特許文献９）、インテル社、ＡＭＤ社、モトローラ社、およびトランスメタ社を始めとする多くのマイクロプロセッサ製造業者は、ＤＶＳに照準を絞った低電力プロセッサの設計に多くの労力を注いできた。ＤＶＳは、プロセッサが、電力消費の低減を目指して、電圧供給レベル（ＶＳＬ：ｖｏｌｔａｇｅ  ｓｕｐｐｌｙ  ｌｅｖｅｌ）を動的に調整することを可能にするが、この低減は、クロック周波数を犠牲にすることと引き換えに達成される。緩やかな管理（ｓｌａｃｋ  ｍａｎａｇｅｍｅｎｔ）／再利用（ｒｅｃｌａｍａｔｉｏｎ）は、ＤＶＳとともにしばしば採用されるスケジューリング技法である。
【００５２】
ほとんどの多目的最適化問題におけるように、問題の性能目的は、互いに対立関係にある可能性が非常に高いので、このスケジューリング例における目標は、パレート最適解（Ｐａｒｅｔｏ−ｏｐｔｉｍａｌ  ｓｏｌｕｔｉｏｎｓ）を見出すことである。言い換えると、与えられたタスク・グラフに対して、本例で提示されるヒューリスティックは、メイクスパンおよびエネルギー消費をともに最小化するスケジュールを生成するが、エネルギー消費の低減は、しばしば供給電圧を引き下げることで行われ、これは、メイクスパンの増加をもたらす。より形式的には、多目的最適化問題は、
【数８】
2012504800.tif 000010
として定義することができ、ここで、Ｓは、実行可能な探索空間であり、ｎ≧２である。
【００５３】
以下では、２つのエネルギー・コンシャス・スケジューリング・ヒューリスティックであるＥＣＳおよびＥＣＳ＋ｉｄｌｅが説明される。これらは、メイン・スケジューリング・パスおよびメイクスパン保存エネルギー低減パスから成る、マルチパス（２パス）アルゴリズムとして説明することができる。
【００５４】
ＥＣＳの動作が、図６に示されている。
【００５５】
エネルギー消費をタスク・スケジューリングに組み込むことは、すでに複雑な問題に別の複雑な層を追加する。リアルタイム・システムとは異なり、本例のアプリケーションは、期限制約を受けない。これは、スケジュールの質の評価が、単純ではなく、むしろ、スケジュールの質は、メイクスパンおよびエネルギー消費の両方を明示的に考慮して、測られるべきであることを示している。この理由で、ＥＣＳは、新規の目的関数として、これら２つの性能上の留意事項を考慮する相対的な優位性（ＲＳ：ｒｅｌａｔｉｖｅ  ｓｕｐｅｒｉｏｒｉｔｙ）を用いるように考案されている。ＶＳＬがｖｊ，ｋであるプロセッサｐｊにおけるタスクｎｉのＲＳ値（またはファクタ）は、
【数９】
2012504800.tif 000011
として定義され、ここで、Ｅ（ｎｉ，ｐｊ，ｖｊ，ｋ）、およびＥ（ｎｉ，ｐ’，ｖ’）は、それぞれ、ｖｊ，ｋを有するｐｊにおけるｎｉのエネルギー消費、およびｖ’を有するｐ’  におけるｎｉのエネルギー消費であり、同様に、２つのタスク−プロセッサ割り当ての最早開始時刻／最早終了時刻は、ＥＳＴ（ｎｉ，ｐｊ，ｖｊ，ｋ）およびＥＳＴ（ｎｉ，ｐ’，ｖ’）、ならびにＥＦＴ（ｎｉ，ｐｊ，ｖｊ，ｋ）およびＥＦＴ（ｎｉ，ｐ’，ｖ’）によって表される。以上のように、ＲＳ値は、エネルギー消費と完了時間の間でトレードオフを行う。
【００５６】
与えられた準備ができたタスクについて、各プロセッサにおけるそのＲＳ値は、そのタスクのためのプロセッサとＶＳＬの現在の最良の組み合わせ（ｐ’およびｖ’）を使用して計算され、その後、最大ＲＳ値が獲得されたプロセッサが、選択される（図６のステップ３〜１５を参照）。
【００５７】
ＥＣＳが行う各スケジューリング決定は、局所最適に限定される傾向があるので、別のエネルギー低減技法（ＭＣＥＲ）が、時間計算量を犠牲にすることなく、ＥＣＳのエネルギー低減フェーズと一体化される（図６のステップ１７〜３１）。この技法は、エネルギー消費を引き下げるには有効な技法であるが、スケジュールが局所最適を脱するのには役立たないことがある。
【００５８】
ＭＣＥＲは、（スケジューリング・フェーズにおいて生成されたスケジュールに対して）行う変更が、スケジュールのメイクスパンを増加させないかどうかを確認されるにすぎない点で、メイクスパン保存則である。ＤＡＧ内の各タスクについて、ＭＣＥＲは、タスク、ホスト、およびＶＳＬの他の組み合わせのいずれかが、現在のメイクスパンを増加させることなく、タスクのエネルギー消費を低減するかどうかをチェックするため、これらの組み合わせのすべてを検討する。
【００５９】
ＥＣＳ＋ｉｄｌｅの動作について、今から説明する。
【００６０】
与えられたスケジュールについて、通常の場合、より短いメイクスパンは、主としてスケジュール内のプロセッサのアイドリング・スロットに関連するエネルギー消費のために、より少ないエネルギー消費をもたらす。この観察は、我々を、間接的なエネルギー消費を組み込むために、先のＲＳ目的関数およびＭＣＥＲ技法に変更を施すことに導く。
【００６１】
先のＲＳ目的関数は、間接的なエネルギー消費の低減に関して、第２項をより効果的にするように改変される。この変更は、最終的なＲＳ値により大きな影響を与えるように、（タスク−プロセッサの２つの組み合わせを比較して）より短いタスク完了時間をもたらすプロセッサ−ＶＳＬマッチを強制する（すなわち、より長いタスク完了をもたらすマッチにペナルティを課す）。
【００６２】
【数１０】
2012504800.tif 000012
【００６３】
ＥＣＳにおける先のＭＣＥＲ技法に施される変更は、そのエネルギー関数に対するものである。すなわち、再割り当て決定は、直接的なエネルギー消費メトリック（Ｅｄ）の代わりに、実際のエネルギー消費メトリック（Ｅａ）に基づいて行われる。供給電圧がｖｊ，ｋであるプロセッサｐｊにおけるタスクｎｉの実際のエネルギー消費は、
【数１１】
2012504800.tif 000013
として定義される。
【００６４】
いくつかの例における修正ＭＣＥＲ技法は、先のＭＣＥＲ技法と同様の方法で、エネルギー消費を低減するが、修正ＭＣＥＲ技法が使用された場合に限って低減がなされる、いくつかの場合が存在する。例えば、供給電圧が１．５０であるプロセッサに割り当てられたタスクが、その計算コストとして１０を有し、１．１０ｖを有する別のプロセッサでは、そのタスクの計算コストが２０になる場合、後者の割り当ての（直接的な）エネルギー消費の方が高いので、オリジナルのＭＣＥＲ技法は、この代替的な割り当てを採用しないと考えられる。しかし、実際のエネルギー消費を考慮する修正ＭＣＥＲ技法は、後者の割り当て（Ｅａ＝１１．４）の方がよりエネルギー効率的であると識別する。このシナリオは、メイクスパンの増加がないことを仮定している。
【００６５】
ＥＣＳ＋ｉｄｌｅの動作について、図６は、本セクションにおいて先に説明された、ＲＳ目的関数およびＭＣＥＲ技法における、２つの相違を有するように示すことができる。ＥＣＳ＋ｉｄｌｅスケジューリングの一例が、図７に示されている。
【００６６】
〔性能解析〕
ここで、ＥＣＳおよびＥＣＳ＋ｉｄｌｅが生成するスケジュールの質的な意味合いについて説明する。
【００６７】
我々のアルゴリズムのエネルギー低減能力を示すために、図２のタスク・グラフについて、ＨＥＦＴおよびＤＢＵＳによって生成された２つのスケジュールを最初に示す。これらのスケジュールは、ＨＥＦＴ（メイクスパン＝８９）およびＤＢＵＳ（メイクスパン＝７３）のそれぞれについて図７に概略的に示されている。それらは、ＤＶＳまたは他の何らかのエネルギー節約技法をスケジューリングに組み込んでいないので、出力されるスケジュールは、メイクスパンを短縮するのと引き換えに、過剰なエネルギーを消費する傾向にある。しかし、エネルギー・コンシャス・スケジューリングについての我々の研究は、この過剰なエネルギー消費は、貧弱なメイクスパンをもたらすことなく低減できることを確認した。
【００６８】
本発明の本例によって生成されたスケジューリングの例が、図８および図９に示されている。メイクスパンは、垂直軸として示され、各プロセッサｐ０、ｐ１、およびｐ２は、独自のカラム（ｃｏｌｕｍｎ）を有する。プロセッサに割り当てられたタスクは、そのプロセッサのカラム上に時間順に記され、タスクの幅は、そのプロセッサにおいてそのタスクに割り当てられた電圧レベルを示す。
【００６９】
ここで、本例のＥＣＳおよびＥＣＳ＋ｉｄｌｅと、先に提案された２つのヒューリスティックＨＥＦＴおよびＤＢＵＳとの間で行った広範な比較評価研究から獲得された結果を提示する。エネルギーに配慮したＥＣＳおよびＥＣＳ＋ｉｄｌｅとエネルギーに無配慮なＨＥＦＴおよびＤＢＵＳの間のこの比較は、本例のエネルギー節約能力を明らかに示している。
【００７０】
〔実験設定〕
ＥＣＳおよびＥＣＳ＋ｉｄｌｅの性能は、ランダムに生成されたアプリケーションと現実世界のアプリケーションという、２つの広範なタスク・グラフの集合を用いて、徹底的に評価された。我々の実験で使用された３つの現実世界の並列アプリケーションは、ラプラス方程式求解機（ｔｈｅ  Ｌａｐｌａｃｅ  ｅｑｕａｔｉｏｎ  ｓｏｌｖｅｒ）（非特許文献６）、ＬＵ分解（非特許文献７）、および高速フーリエ変換（非特許文献８）であった。より総合的な実験とするために、これらのタスク・グラフに対して、多くの変形が施された。タスク・グラフに加えて、様々な異なる特徴のプロセッサが、シミュレーションに適用された。図１１の表は、我々の実験で使用されたパラメータを要約したものである。
【００７１】
４つの異なるアルゴリズム（ＨＥＦＴ、ＤＢＵＳ、ＥＣＳ、ＥＣＳ＋ｉｄｌｅ）を用いて実行された実験の総数は、２８万回（すなわち、アルゴリズム毎に７万２千回）である。具体的には、ランダムなタスク・グラフの集合は、１０種類のグラフ・サイズ、５種類のＣＣＲ、および３種類のプロセッサ異種性設定の組み合わせを用いて生成された、１５０個の基本タスク・グラフから成る。組み合わせ毎に、２０個の変形タスク・グラフが、基本タスク・グラフの特性を保持しながら、ランダムに生成された。これら３０００個のグラフが、６つの異なる数のプロセッサを用いて研究された。３つの現実世界のアプリケーションの各々は、同数の（すなわち１万８千個の）タスク・グラフを使用して研究された。したがって、総数は７万２千である。
【００７２】
各タスク・グラフ内のタスクの計算コストおよび通信コストは、選択された平均計算コストおよび平均通信コストと等しい平均を有するように、一様分布からランダムに選択された。プロセッサ異種性の１００という値は、与えられたシステム内の最高速度のプロセッサと最低速度のプロセッサの間の速度差のパーセンテージとして定義された。現実世界のアプリケーションのタスク・グラフの場合、タスクの数が約１０から６００の範囲にわたり得るように、行列サイズおよび入力点の数を変化させた。
【００７３】
〔比較測定基準〕
一般に、スケジューリング・アルゴリズムによって生成されたタスク・グラフのメイクスパンが、主な性能尺度として使用されるが、この研究においては、我々は、エネルギー消費を別の同じくらい重要な性能尺度と考える。与えられたタスク・グラフについて、そのメイクスパンおよびエネルギー消費の両方を下限に正規化する。下限とは、通信コストを考慮しない、ＣＰ沿いのタスク（すなわちＣＰタスク）のメイクスパンおよびエネルギー消費である具体的には、「スケジュール長比」（ＳＬＲ：ｓｃｈｅｄｕｌｅ  ｌｅｎｇｔｈ  ｒａｔｉｏ）および「エネルギー消費比」（ＥＣＲ：ｅｎｅｒｇｙ  ｃｏｎｓｕｍｐｔｉｏｎ  ｒａｔｉｏ）が、我々の比較の主要な性能測定基準として使用された。形式的に、スケジューリング・アルゴリズムによってタスク・グラフＧのために生成されたスケジュールのメイクスパンＭのＳＬＲ値およびエネルギー消費ＥｔのＥＣＲ値は、
【数１２】
2012504800.tif 000014
【数１３】
2012504800.tif 000015
として定義され、ここで、ＣＰは、ＧのＣＰタスクの集合である。
【００７４】
〔結果〕
我々が行ったシミュレーションの全結果が、図１２の表に要約されている。図１２は、異なるＤＡＧタイプに関わりなく、アルゴリズムＥＣＳおよびＥＣＳ＋ｉｄｌｅの性能が、ＤＢＵＳおよびＨＥＦＴよりも優れていることを明らかに示している。さらに、ＥＣＳおよびＥＣＳ＋ｉｄｌｅは、様々な異なるＣＣＲを用いた場合も、それら２つの先行アルゴリズムよりも性能が優れている。
【００７５】
明らかに、タスク重複の主な目的は、いくつかのタスクを冗長にスケジュールすることによる、通信オーバヘッドの最小化であり、そのことが、最終的にはメイクスパンを低減する。タスク重複は、通信集約的なアプリケーションに対する有効な技法となることができるが、スケジューリング・アルゴリズムへのそのような技法の組み込みは、エネルギー消費が関与する場合は、回避されるべきであるか、または少なくとも慎重に検討されるべきである。ＤＢＵＳは、重複ベースのスケジューリング・アルゴリズムであるので、そのエネルギー消費は、ＥＣＳのエネルギー消費よりもはるかに大きい。
【００７６】
ＥＣＳおよびＥＣＳ＋ｉｄｌｅとＨＥＦＴの間の比較は、特にエネルギー消費に関して、ＥＣＳおよびＥＣＳ＋ｉｄｌｅの有利な性能を再確認させた。なお、これまでに、ＨＥＦＴは、低い時間計算量で、非常に優位的に動作することが明らかにされ、頻繁に採用され、拡張されてきたことに留意されたい。このことは、図１０に示されたＥＣＳおよびＥＣＳ＋ｉｄｌｅの平均ＳＬＲが、１パーセントの余裕を取ったとしても、有力であることを示唆している。
【００７７】
ＥＣＳおよびＥＣＳ＋ｉｄｌｅの主な性能の源は、ＲＳ目的関数の使用であり、ＲＳ目的関数は、メイクスパンおよびエネルギー消費の両方を低減することに貢献する。これらの実験では、ＥＣＳおよびＥＣＳ＋ｉｄｌｅのメイン・スケジューリング・フェーズがＭＣＥＲ技法によって行われた後のスケジュールについて、さらに（平均で）３．４パーセントの改善および３．９パーセントの改善が、エネルギー消費で見られた。これらの低減は、直接的および間接的なエネルギー消費の両方において達成される。
【００７８】
具体的な実施形態において示された本発明に対して、広範に説明された本発明の範囲から逸脱することなく、多くの変形および／または変更を施すことができることが当業者には理解されよう。したがって、本発明の実施形態は、すべての点において、例示的なものと見なされるべきであり、限定的なものと見なされるべきではない。
【図１】
2012504800.tif 000016
【図２】
2012504800.tif 000017
【図３】
2012504800.tif 000018
【図４】
2012504800.tif 000019
【図５】
2012504800.tif 000020
【図６】
2012504800.tif 000021
【図７】
2012504800.tif 000022
【図８】
2012504800.tif 000023
【図９】
2012504800.tif 000024
【図１０】
2012504800.tif 000025
【図１１】
2012504800.tif 000026
【図１２】
2012504800.tif 000027
【国際調査報告】
2012504800.tif 000028
2012504800.tif 000029
2012504800.tif 000030