(57)【要約】【課題】  マルチコアプロセッサで行われるプログラムのコンパイル方法、マルチコアプロセッサのタスクマッピング方法及びタスクスケジューリング方法を提供する。【解決手段】  マルチコアプロセッサで行われるプログラムのコンパイルのときにスクラッチパッドメモリのサイズによってタスクに指定される通信方式を最適化することによって、プログラムの節電性能と動作速度とを向上させうるマルチコアプロセッサで行われるプログラムのコンパイル方法、マルチコアプロセッサのタスクマッピング方法及びタスクスケジューリング方法が開示される。【選択図】      図３
2014078239.tif 000002
【特許請求の範囲】
【請求項１】
ソースプロセッシングエレメントと宛先プロセッシングエレメントとをマッピングする初期解を生成し、前記ソースプロセッシングエレメントから前記宛先プロセッシングエレメントへのタスクの伝送のための通信方式を選択する段階と、
前記初期解に含まれた前記マッピング及び前記通信方式を近似的に最適化する段階と、
前記タスクをスケジューリングする段階と、を含み、
前記通信方式は、コンパイルのときに指定される、マルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項２】
前記初期解は、確率的アルゴリズムを用いて生成する、請求項１に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項３】
前記確率的アルゴリズムは、シミュレーティドアニーリングアルゴリズムである、請求項２に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項４】
前記初期解を生成する段階で、
前記通信方式は、共有メモリを利用した第１通信方式と前記ソースプロセッシングエレメントと前記宛先プロセッシングエレメントとのそれぞれに含まれたスクラッチパッドメモリを利用した第２通信方式とのうちから選択的に指定される、
請求項１乃至３のいずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項５】
前記初期解に含まれた前記マッピング及び前記通信方式を近似的に最適化する段階は、
前記ソースプロセッシングエレメントと前記宛先プロセッシングエレメントとのそれぞれにマッピングされたそれぞれのタスクを再配置する段階をさらに含む、請求項１乃至４のいずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項６】
前記再配置する段階は、
前記ソースプロセッシングエレメントと前記宛先プロセッシングエレメントとにマッピングされたタスクを、０と１との間の第１確率で、他のプロセッシングエレメントに再びマッピングする段階をさらに含む、請求項５に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項７】
前記再マッピングする段階は、
前記他のプロセッシングエレメントにマッピングされた前記タスクを、０と１との間の第２確率で、第２タスクと代替してソースプロセッシングエレメント及び宛先プロセッシングエレメントに再びマッピングする段階をさらに含む、請求項６に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項８】
前記第２タスクは、前記ソースプロセッシングエレメントと前記宛先プロセッシングエレメントとが反対となるようにマッピングされることによって、前記第２タスクが最初にマッピングされた前記タスクを代替可能にし、
前記第２通信方式は、前記宛先プロセッシングエレメントから前記ソースプロセッシングエレメントへの前記第２タスクの伝送のために選択される請求項７に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項９】
前記再びマッピングする段階は、
前記タスクに対して前記第１通信方式と前記第２通信方式とのうちから選択的に指定された前記通信方式を、０と１との間の第３確率で、他の通信方式に変更する段階をさらに含む、請求項６乃至８のいずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１０】
前記初期解に含まれた前記マッピング及び前記通信方式を近似的に最適化する段階は、
貪欲アルゴリズムヒューリスティックを用いて行われる、請求項１乃至９のいずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１１】
前記初期解に含まれた前記マッピング及び前記通信方式を近似的に最適化する段階は、
前記ソースプロセッシングエレメント及び前記宛先プロセッシングエレメントにマッピングされた前記タスクに関するデータのサイズの和が、スクラッチパッドメモリの容量を超過しないように違法性を除去する段階をさらに含む、請求項１乃至１０のいずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１２】
前記違法性を除去する段階は、
前記ソースプロセッシングエレメント及び前記宛先プロセッシングエレメントにマッピングされた前記第２通信方式が指定されたタスクに対して通信方式を前記第１通信方式に変更する段階をさらに含む、請求項１１に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１３】
前記違法性を除去する段階は、
少なくとも前記ソースプロセッシングエレメント及び前記宛先プロセッシングエレメントに対して違法性が除去されるように行われる請求項１１又は１２に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１４】
前記違法性を除去する段階は、
少なくとも前記ソースプロセッシングエレメント及び前記宛先プロセッシングエレメントを含むスクラッチパッドメモリの容量超過が多いプロセッシングエレメントから順に行われる、請求項１１乃至１３のいずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１５】
前記初期解に含まれた前記マッピング及び前記通信方式を近似的に最適化する段階は、
スクラッチパッドメモリに残余空間が存在するプロセッシングエレメントに対して、前記スクラッチパッドメモリの活用度を向上させる段階をさらに含む、請求項１乃至１４いずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１６】
前記活用度を向上させる段階は、
前記特定のプロセッシングエレメントにマッピングされた前記第１通信方式が指定されたタスクに対して、通信方式を前記第２通信方式に変更する段階をさらに含む、請求項１５に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１７】
前記タスクをスケジューリングする段階は、
前記タスクのスケジューリングのための第１時間区間内でスケジューリングを試みる段階と、
前記スケジューリングを試みる段階で、１つのタスクと他のタスクとが重なってスケジューリングが失敗した場合、前記他のタスクとの重なった時間長を求める段階と、
前記第１時間区間と前記重なった時間長の和に相当する第２時間区間内でスケジューリングを再試みる段階と、
をさらに含む請求項１乃至１６いずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１８】
前記タスクをスケジューリングする段階は、
少なくとも１つの前記タスクのうち少なくとも一部が、第１反復遂行間隔をおいて繰り返し行われる場合、少なくとも１つの前記重なった時間長の最小値を求める段階と、
前記第１反復遂行間隔と前記重なった時間長の最小値の和に相当する第２反復遂行間隔とをおいて繰り返し行われるようにスケジューリングを再度試みる段階と、
をさらに含む、請求項１乃至１７いずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項１９】
前記タスクをスケジューリングする段階後に、
スケジューリング結果を評価する段階をさらに含む、請求項１乃至１８いずれか一項に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項２０】
前記スケジューリング結果を評価する段階で得られた評価内容を用いて前記初期解を再び生成する段階、をさらに含む請求項１９に記載のマルチコアプロセッサで行われるプログラムのコンパイル方法。
【請求項２１】
マルチコアプロセッサの複数のプロセッシングエレメントから第１プロセッシングエレメントにタスクをマッピングする段階と、
前記第１プロセッシングエレメントから第２プロセッシングエレメントに前記タスクを０と１との間の第１確率で移動させる段階と、
前記第１確率で再びマッピングされる前記タスクを、０と１との間の第２確率で、前記１つのプロセッシングエレメントではないプロセッシングエレメントの他のタスクと代替する段階と、を含むマルチコアプロセッサのタスクマッピング方法。
【請求項２２】
前記タスクには、第１通信方式及び第２通信方式のうちの１つの通信方式が指定され、前記第１通信方式は、共有メモリを利用し、前記第２通信方式は、前記第２プロセッシングエレメントのスクラッチパッドメモリ、前記第２プロセッシングエレメントのスクラッチパッドメモリ及び前記第３プロセッシングエレメントのスクラッチパッドメモリのうち少なくとも１つを使う請求項２１に記載のマルチコアプロセッサのタスクマッピング方法。
【請求項２３】
前記タスクに指定されるように選択された通信方式を、０と１との間の第３確率で、前記第１通信方式または前記第２通信方式のうち、以前に選択されていない通信方式に変更する段階をさらに含む請求項２２に記載のマルチコアプロセッサのタスクマッピング方法。
【請求項２４】
前記タスクに前記第２通信方式が指定されるように選択された場合、前記第１通信方式に変更して、前記特定のプロセッシングエレメントにマッピングされた少なくとも１つのタスクに関するデータのサイズの和が、前記特定のプロセッシングエレメントのスクラッチパッドメモリの容量を超過しないようにする段階をさらに含む請求項２２又は２３に記載のマルチコアプロセッサのタスクマッピング方法。
【請求項２５】
前記タスクに前記第１通信方式が指定されるように選択された場合、スクラッチパッドメモリに残余空間が存在するプロセッシングエレメントに対して、前記第１通信方式を前記第２通信方式に変更する段階をさらに含む請求項２２乃至２４のいずれか一項に記載のマルチコアプロセッサのタスクマッピング方法。
【請求項２６】
マルチコアプロセッサの２以上のプロセッシングエレメントで行われる２以上のタスクに対して第１時間区間内でスケジューリングを試みる段階と、
前記スケジューリングを試みる段階で、１つのタスクと他のタスクとが重なってスケジューリングが失敗した場合、前記他のタスクと重なった時間長を求める段階と、
前記第１時間区間と前記重なった時間長の和に相当する第２時間区間内でスケジューリングを再度試みる段階と、
を含むマルチコアプロセッサのタスクスケジューリング方法。
【請求項２７】
少なくとも１つの前記タスクのうち少なくとも一部が、第１反復遂行間隔をおいて繰り返し行われる場合、少なくとも１つの前記重なった時間長の最小値を求める段階と、
前記第１反復遂行間隔と前記重なった時間長の最小値の和に相当する第２反復遂行間隔とをおいて繰り返し行われるようにスケジューリングを再度試みる段階をさらに含む、請求項２５に記載のマルチコアプロセッサのタスクスケジューリング方法。
【請求項２８】
タスクに対してマッピング、通信方式及びスケジューリングを含む初期解を生成する段階と、
第１確率に基づいて前記マッピングを変更し、第２確率に基づいて前記通信方式を変更することによって、前記タスクに対する前記初期解を変更する段階と、
前記タスクが他のタスクと重複する場合、計算された重複値によって、前記タスクを再スケジューリングする段階と、
を含むマルチコア再構成可能プロセッサのタスクマッピング及びスケジューリング方法。
【請求項２９】
前記初期解を生成する段階は、
ソースプロセッシングエレメント及び宛先プロセッシングエレメントに前記タスクをマッピングする段階と、
前記タスクを前記ソースプロセッシングエレメントから前記宛先プロセッシングエレメントに伝送するために、共有メモリ通信方式とスクラッチパッドメモリ通信方式とのうち少なくとも１つを選択する段階と、
前記ソースプロセッシングエレメントから前記宛先プロセッシングエレメントに前記タスクを伝送するためのタイミングをスケジューリングする段階と、
をさらに含む請求項２８に記載のマルチコア再構成可能プロセッサのタスクマッピング及びスケジューリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチコアプロセッサで行われるプログラムのコンパイリング、タスクマッピング及びタスクスケジューリング技術に関する。
【背景技術】
【０００２】
マルチコアアーキテクチャーの性能を極大化するためには、マルチコアアーキテクチャーの特性に適したプログラミングが必要である。
【０００３】
マルチコアプロセッサを通じて行われるプログラミングにおいて、マッピングとは、グラフで表現されたアプリケーションの各部分、すなわち、タスクをマルチコア構造の如何なるプロセッシングエレメントで行うか否かを決定する手続きを意味する。
【０００４】
また、スケジューリングとは、具体的なマッピング方法が定められた後、それぞれのタスクがプロセッシングエレメント上で行われる順序とタイミングとを決定する手続きを意味する。
【０００５】
ところが、マルチコア上で行われるマルチコアプログラムは、プログラマーが手作業で作成するには、プログラミングの複雑度があまりにも大きくて、プログラミングの生産性が低いか、プログラムの品質が劣悪であるなどの問題点がある。特に、プログラミングの複雑度を高める要因としては、マッピング及びスケジューリングがある。
【０００６】
特に、マルチコアプログラムは、プログラムの高い複雑度によって、それぞれのコアにマッピングされたタスクに対してソースＰＥ（Ｓｏｕｒｃｅ  Ｐｒｏｃｅｓｓｉｎｇ  Ｅｌｅｍｅｎｔ）と宛先ＰＥ（Ｄｅｓｔｉｎａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｅｌｅｍｅｎｔ）との間に“如何なる通信方式を使うか”をプログラム開発者が直接指定するのに大きな難しさがある。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、マルチコアプロセッサで行われるプログラムのコンパイル方法、マルチコアプロセッサのタスクマッピング方法及びタスクスケジューリング方法を提供することである。
【課題を解決するための手段】
【０００８】
本発明の一側面によるマルチコアプロセッサで行われるプログラムのコンパイル方法は、ソースプロセッシングエレメントと宛先プロセッシングエレメントとをマッピングする初期解を生成し、前記ソースプロセッシングエレメントから前記宛先プロセッシングエレメントへのタスクの伝送のための通信方式を選択する段階と、前記初期解に含まれた前記マッピング及び前記通信方式を近似的に最適化する段階と、前記タスクをスケジューリングする段階と、を含む。
【０００９】
本発明の他の側面によるマルチコアプロセッサのタスクマッピング方法は、マルチコアプロセッサの複数のプロセッシングエレメントから第１プロセッシングエレメントにタスクをマッピングする段階と、前記第１プロセッシングエレメントから第２プロセッシングエレメントに前記タスクを０と１との間の第１確率で移動させる段階と、前記第１確率で再びマッピングされる前記タスクを、０と１との間の第２確率で、前記１つのプロセッシングエレメントではないプロセッシングエレメントの他のタスクと代替する段階と、を含む。
【００１０】
本発明のさらに他の側面によるマルチコアプロセッサのタスクスケジューリング方法は、マルチコアプロセッサの２以上のプロセッシングエレメントで行われる２以上のタスクに対して第１時間区間内でスケジューリングを試みる段階と、前記スケジューリングを試みる段階で、１つのタスクと他のタスクとが重なってスケジューリングが失敗した場合、前記他のタスクと重なった時間長を求める段階と、前記第１時間区間と前記重なった時間長の和に相当する第２時間区間内でスケジューリングを再度試みる段階と、を含む。
【００１１】
本発明のさらに他の側面によるマルチコア再構成可能プロセッサのタスクマッピング及びスケジューリング方法は、タスクに対してマッピング、通信方式及びスケジューリングを含む初期解を生成する段階と、第１確率に基づいて前記マッピングを変更し、第２確率に基づいて前記通信方式を変更することによって、前記タスクに対する前記初期解を変更する段階と、前記タスクが他のタスクと重複する場合、計算された重複値によって、前記タスクを再スケジューリングする段階と、を含む。
【図面の簡単な説明】
【００１２】
【図１Ａ】共有メモリを利用したマルチコアプロセッサのプロセッシングエレメントの間の通信の例を説明する図面である。
【図１Ｂ】共有メモリを利用したマルチコアプロセッサのプロセッシングエレメントの間の通信の例を説明する図面である。
【図２Ａ】メッセージパッシングを利用したマルチコアプロセッサのプロセッシングエレメントの間の通信の例を説明する図面である。
【図２Ｂ】メッセージパッシングを利用したマルチコアプロセッサのプロセッシングエレメントの間の通信の例を説明する図面である。
【図３】本発明の一側面によるタスクのマッピング及び通信方式決定方法を例示したフローチャートである。
【図４】図３の初期解変更段階（ステップＳ１１０）をさらに詳しく示す図面である。
【図５】βの確率でタスクが位置交換する場合を例示した図面である。
【図６】（１−β）の確率でタスクが位置変更する場合を例示した図面である。
【図７】最適化過程の流れの一例を示すフローチャートである。
【図８】モジュロアルゴリズムを利用したインストラクションスケジューリングの手続きを例示したフローチャートである。
【図９】変形されたモジュロアルゴリズムを利用したタスクスケジューリングの手続きを例示したフローチャートである。
【図１０】本発明の一側面による再構成可能なプロセッサで行われるコンパイリング方法の一例を示すフローチャートである。
【図１１】本発明の一側面による再構成可能なプロセッサで行われるコンパイリング方法の他の例を示すフローチャートである。
【図１２】本発明の他の側面による再構成可能なプロセッサのタスクマッピング方法の一例を示すフローチャートである。
【図１３】本発明のさらに他の側面による再構成可能なプロセッサのタスクスケジューリング方法の一例を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、添付した図面を参照して、本発明の実施のための具体例を詳しく説明する。
【００１４】
図１Ａ及び図１Ｂは、共有メモリを利用したマルチコアプロセッサのプロセッシングエレメントの間の通信の例を説明する図面である。
【００１５】
図１Ａと図１Ｂで、同じ図面符号は、同じ構成要素を表わす。
【００１６】
マルチコアプロセッサ内のプロセッシングエレメント１１２ａ、１１２ｂ間では、通信が行われる。図１Ａと図１Ｂで、ＰＥは、共有メモリ１２０を用いて互いに通信を行う。
【００１７】
共有メモリを利用した通信方式は、大きく下記のような段階を通じて行われる。
（１）ソースＰＥ１１２ａが共有メモリにデータを記録する。
（２）共有メモリがソースＰＥ１１２ａにＡＣＫを伝送する。
（３）ソースＰＥ１１２ａが記録を完了した場合、ソースＰＥ１１２ａが宛先ＰＥ１１２ｂに同期パケット（ｓｙｎｃ  ｐａｃｋｅｔ）を伝送する。
（４）宛先ＰＥ１１２ｂが共有メモリに読み取り要請を伝送する。
（５）共有メモリが宛先ＰＥ１１２ｂにデータを伝送する。
【００１８】
この方式は、プログラミングが簡単であり、マルチタスクが容易であるという長所がある。一方、プロセッシングエレメントから共有メモリまでの経路（図２Ｂで、“ｐａｔｈ（ｓｈａｒｅｄ  ｍｅｍｏｒｙ”として図示する）が長い場合が度々発生する点、共有メモリのサイズが大きな点、及び共有メモリの動作速度が比較的遅い点などによって、電力消費量が多く、タスクの遂行速度が遅いという短所がある。
【００１９】
図２Ａ及び図２Ｂは、メッセージパッシングを利用したマルチコアプロセッサのプロセッシングエレメントの間の通信の例を説明する図面である。図２Ａと図２Ｂで、同じ図面符号は、同じ構成要素を表わす。図２Ａと図２Ｂで、ＰＥ１１２ａ、１１２ｂは、それぞれのＰＥ内部のスクラッチパッドメモリ（ＳＰＭ：Ｓｃｒａｔｃｈ  Ｐａｄ  Ｍｅｍｏｒｙ）を用いて互いに通信を行う。すなわち、ソースＰＥ１１２ａは、伝送しなければならないデータを共有メモリ１２０に記録する代わりに、宛先ＰＥ１１２ｂのＳＰＭに直接伝送する。この場合、ソースＰＥ１１２ａから宛先ＰＥ１１２ｂまでの最短経路（図２Ｂで、“ｐａｔｈ（ＰＳＭ）”として図示する）を通じてデータを伝送できるので、共有メモリ１２０を経由する図１Ｂに示された経路（“ｐａｔｈ（ｓｈａｒｅｄ  ｍｅｍｏｒｙ）”）に比べて、伝送時間が短くなる長所を有する。また、ＰＳＭは、共有メモリに比べて、著しく小さな保存容量を有する場合が一般的なので、メッセージパッシングを利用した通信方式は、電力消費量も少ないという長所がある。
【００２０】
一方、ＳＰＭの小さく、限定された保存容量によって、あらゆるメッセージをメッセージパッシングを利用した通信方式で伝送できない短所もある。
【００２１】
すなわち、メッセージパッシングを利用した通信方式を適用する時に得られる利得は、２つのＰＣ間の距離など多様な要因によって変わるので、共有メモリを利用した通信方式とメッセージパッシングを利用した通信方式とのうちの如何なる通信方式を利用するかに関する選択は、マッピング及びスケジューリングのときに共に決定されることが望ましい。
【００２２】
図３は、本発明の一側面によるタスクのマッピング及び通信方式決定方法を例示したフローチャートである。タスクスケジューリングを行うために、最も先に決定しなければならないことは、各ＰＥに対するタスクのマッピング及びタスクに関するソースＰＥと宛先ＰＥとの間の通信方式である。
【００２３】
図３に例示したタスクマッピング及び通信方式決定方法は、一種の確率的アルゴリズムであるシミュレーティドアニーリングアルゴリズム（ＳＡ：Ｓｉｍｕｌａｔｅｄ  Ａｎｎｅａｌｉｎｇ）を基盤としている。
【００２４】
シミュレーティドアニーリングアルゴリズムは、次のような基本的な手続きでなされる。
（１）初期解を生成する。
（２）初期解をランダムに変化させて新規解を得る。
（３）新規解が初期解よりもさらに良ければ、新規解で初期解を代替するが、新規解が初期解よりもさらに良くなければ、所定の確率ｒ（ｒは、０よりも大きく、１よりも小さい）に従って新規解で初期解を代替する。
【００２５】
（１）ないし（３）の手続きを通じて、シミュレーティドアニーリングアルゴリズムは、局所探索アルゴリズム（Ｌｏｃａｌ  Ｓｅａｒｃｈ  Ａｌｇｏｒｉｔｈｍ）よりも優れる解が得られうるという長所がある。
【００２６】
図３のタスクマッピング及び通信方式決定方法は、初期解生成段階（ステップＳ１００）及び初期解変更段階（ステップＳ１１０）を含む。
【００２７】
初期解生成段階（ステップＳ１００）では、各ＰＥに対するタスクマッピング及び各タスクへの関するソースＰＥと宛先ＰＥとの間の通信方式を含む初期解が生成される。
【００２８】
次いで、初期解変更段階（ステップＳ１１０）では、生成された初期解に含まれたタスクマッピング状態及び各タスクの通信方式を変更した新たな解が生成される。
【００２９】
図４は、図３の初期解変更段階（ステップＳ１１０）をさらに詳しく示す図面である。
【００３０】
初期解変更段階（ステップＳ１１０）は、タスク移動段階（ステップＳ１１２）及び通信方式変更段階（ステップＳ１１４）を含みうる。
【００３１】
タスク移動段階（ステップＳ１１２）では、初期解で特定のＰＥにマッピングされたタスクに対して、タスクを移動するか否かが決定される。例えば、αの確率でタスクを特定のＰＥから他のＰＥに移動させることができる（ステップＳ１１２０）。この際、αは、０と１との間の値になる。また、タスクが移動しない確率は、（１−α）になる（ステップＳ１１３０）。
【００３２】
もし、タスクが移動した場合には、再びβの確率で他のＰＥの他のタスクと互いに位置交換させうる（ステップＳ１１２１）。この際、βは、０と１との間の値になる。
【００３３】
図５は、βの確率でタスクが位置交換する場合を例示した図面である。
【００３４】
すなわち、プロセッシングエレメント（ＰＥ０）にｔａｓｋ（０）というタスクがマッピングされ、プロセッシングエレメント（ＰＥ１）にｔａｓｋ（１）というタスクがマッピングされた場合、タスク移動段階（ステップＳ１１２）でβの確率でプロセッシングエレメント（ＰＥ０）にマッピングされるタスクは、ｔａｓｋ（１）に、プロセッシングエレメント（ＰＥ１）にマッピングされるタスクは、ｔａｓｋ（０）に変更される（ステップＳ１１２１）。
【００３５】
一方、（１−β）の確率でタスクの位置は、１つのプロセッシングエレメントから他のプロセッシングエレメントに位置変更されうる。
【００３６】
図６は、（１−β）の確率でタスクが位置変更する場合を例示した図面である。
【００３７】
すなわち、プロセッシングエレメント（ＰＥ０）にｔａｓｋ（０）というタスクがマッピングされた場合、このタスクをプロセッシングエレメント（ＰＥ２）に移動させることができる（ステップＳ１１２２）。
【００３８】
再び図４に戻れば、通信方式変更段階（ステップＳ１１４）では、特定のタスクに対するソースＰＥと宛先ＰＥとの間の通信方式を変更するか否かが決定される。
【００３９】
例えば、γの確率で通信方式が現在の通信方式から他の通信方式に変更されうる（ステップＳ１１４０、ステップＳ１１４２、ステップＳ１１４４）。もし、現在の通信方式がメッセージパッシングを利用した通信方式であれば、共有メモリを利用した通信方式に変更される確率は、γになる。この際、γは、０と１との間の値になる。
【００４０】
また、通信方式変更段階（ステップＳ１１４）で、（１−γ）の確率で特定のタスクの通信方式は変更されないこともある（ステップＳ１１４１、ステップＳ１１４３、ステップＳ１１４５）。
【００４１】
一方、初期解変更段階（ステップＳ１１０）が行われた後の解には、一般的に、追加的な最適化過程が行われる必要がある。
【００４２】
メッセージパッシングを利用した通信方式を使うためのＳＰＭのサイズは、制限されているという点を考慮すると、最適化された解を得るためには、“プロセッシングエレメントがＳＰＭの容量を超過せずとも、ＳＰＭの容量を最大限活用”することが望ましい。
【００４３】
また、特定のタスクに対する通信方式を共有メモリを利用した通信方式の代わりに、メッセージパッシングを利用した通信方式とする場合の利得は、ＰＥ間の通信距離や通信データ量またはＳＰＭ使用量など多様な要因によって変わる点を考慮すると、“共有メモリを利用した通信方式を使うときよりもメッセージパッシングを利用した通信方式を使うときの利得が大きなタスクに対して優先的にメッセージパッシングを利用した通信方式を適用”することが良い。
【００４４】
そのために、ソースＰＥと宛先ＰＥとを有するタスク（ｔ）に対する利得Ｇ（ｔ）を以下の式（１）のように定義することができる。
【００４５】
Ｇ（ｔ）＝（Ｌ×Ａ）／Ｔ      （１）
この際、Ｌは、ソースＰＥから宛先ＰＥまでの通信距離、Ａは、ソースＰＥと宛先ＰＥとの間の通信量、Ｂは、ＳＰＭ使用量の合計を示す。
【００４６】
最適化過程を行うために、ヒューリスティック、特に、貪欲法ヒューリスティックを適用することができる。このような意味で、初期解変更段階（ステップＳ１１０）以後に行われる最適化過程は、近似的最適化過程であると言える。
【００４７】
図７は、最適化過程の流れの一例を示すフローチャートである。図７で示すように、最適化過程は、違法性除去段階（ステップＳ２００）及び活用度向上段階（ステップＳ２１０）を含む。違法性除去段階（ステップＳ２００）では、初期解変更段階（ステップＳ１１０）後の解に含まれたタスクのマッピング及び通信方式に存在する違法性が除去される。
【００４８】
初期解変更段階（ステップＳ１１０）後の解に含まれたタスクのマッピング及び通信方式には、ＳＰＭの容量を超過する（すなわち、“違法な”）プロセッシングエレメントが存在する確率が高い。違法性除去段階では、違法なプロセッシングエレメントの違法性が除去される。
【００４９】
例えば、まず、違法なプロセッシングエレメントを容量超過量が多い順に並べる。次いで、並べられた違法なプロセッシングエレメントにマッピングされた各タスクに対して指定されたメッセージパッシングを利用した通信方式を、違法性が解消されるまで（すなわち、ＳＰＭの容量が超過されないまで）共有メモリを利用した通信方式に変更する。
【００５０】
この際、通信方式を変更しなければならないタスクが複数個である場合には、式（１）で表される利得が低いタスクから変更することが望ましい。
【００５１】
容量超過量が多いプロセッシングエレメントから始めて、あらゆる違法なプロセッシングエレメントに対してタスクの通信方式の変更作業を終えれば、解は適法となる。
【００５２】
次いで、活用度向上段階（ステップＳ２１０）では、プロセッシングエレメントのＳＰＭの残余空間をさらに活用するための手続きが行われる。
【００５３】
違法性除去段階が行われた後には、プロセッシングエレメントのＳＰＭに残余空間があまりにも多く残る問題が発生する恐れがある。これは、初期解のためでも、違法性除去段階で大きな容量を使うタスクの通信方式を共有メモリを利用した通信方式に変更したためでもあり得る。
【００５４】
このようにＳＰＭに残余空間が残っているプロセッシングエレメントに対して、通信方式がタスクの通信方式の活用度向上段階では、まず、プロセッシングエレメントをＳＰＭの残余空間が多く残った順に並べる。次いで、並べられたプロセッシングエレメントにマッピングされた各タスクに対して指定された共有メモリを利用した通信方式を、メッセージパッシングを利用した通信方式に変更する。
【００５５】
この際、通信方式を変更しなければならないタスクが複数個である場合には、式（１）で表される利得が高いタスクから変更することが望ましい。
【００５６】
ＳＰＭの残余空間が多く残ったプロセッシングエレメントから始めて、ＳＰＭの残余空間を活用することができるあらゆるプロセッシングエレメントに対してタスクの通信方式の変更作業を終えれば、ＳＰＭの活用度が以前に比べて向上する。したがって、解は、さらに良好となる。
【００５７】
近似的最適化手続きが行われた後には、スケジューリングが必要である。
【００５８】
マッピングはタスクを行うプロセッシングエレメントを如何に指定するかに対する問題であり、スケジューリングは、タスクを如何なる時点に行うかに対する問題である。
【００５９】
スケジューリングのためのアルゴリズムは、非常に多様に存在するが、ここでは、非循環的アプリケーション（ａｃｙｃｌｉｃ  ａｐｐｌｉｃａｔｉｏｎ）だけではなく、後方連関性（ｂａｃｋｗａｒｄ  ｄｅｐｅｎｄｅｎｃｙ）を有した循環的アプリケーション（ｃｙｃｌｉｃ  ａｐｐｌｉｃａｔｉｏｎ）に対するスケジューリングも支援することができるスケジューリングアルゴリズムを提案する。これを、便宜上、“変形されたモジュロアルゴリズム（Ｍｏｄｉｆｉｅｄ  Ｍｏｄｕｌｏ  Ａｌｇｏｒｉｔｈｍ）”と言う。
【００６０】
モジュロアルゴリズムは、一種の優先順位に基づくスケジューリングアルゴリズム（ｐｒｉｏｒｉｔｙｂａｓｅｄ  ｓｃｈｅｄｕｌｉｎｇ  ａｌｇｏｒｉｔｈｍ）である。モジュロアルゴリズムは、反復遂行がなされるサイクルとサイクルとの間の時間間隔を意味する初期間隔（ＩＩ：Ｉｎｉｔｉａｔｉｏｎ  Ｉｎｔｅｒｖａｌ）を予測して、予測した時間間隔内にあらゆるタスクをスケジューリングすることを試みた後、試みが失敗したとき、反復遂行間隔を少しずつ増やしながら最適の初期間隔を探す。
【００６１】
図８は、モジュロアルゴリズムを利用したインストラクションスケジューリングの手続きを例示したフローチャートである。
【００６２】
本来、モジュロアルゴリズムは、インストラクションをスケジューリングするためのアルゴリズムである。例えば、或る繰り返し行われるルーチンに関する反復遂行間隔は、初期間隔ＩＩ（Ｉｎｉｔｉｎａｌ  Ｉｎｔｅｒｖａｌ）の範囲内で割り当てられる（ステップＳ３００）。この際、特定時間区間（ｔ）内でスケジューリングを行うように条件を付与されうる（ステップＳ３１０）。このような反復遂行間隔及び時間区間を有してスケジューリングが反復的に試みられる（ステップＳ３２０）。試みられたスケジューリングが失敗する場合、時間区間をｔ＋１、ｔ＋２のように１（または、“単位時間”）ずつ増やしながらスケジューリングを再度試みる（ステップＳ３５０）。もし、インストラクションの反復遂行サイクルの間で既定の初期間隔（ＩＩ）内にスケジューリングができないと判断されれば（ステップＳ３４０）、初期間隔を１（または、“単位時間”）ずつ増やして反復遂行間隔を（ＩＩ＋１）に再設定することができる（ステップＳ３６０）。この場合、再び特定時間区間（ｔ）からスケジューリング試みが反復される。
【００６３】
ところが、このような方式は、インストラクションスケジューリングには適するが、タスクスケジューリングに適用する場合には、スケジューリングを行う時間が過度に多く必要となる問題点がある。したがって、インストラクションスケジューリングに使われるアルゴリズムをそのままタスクスケジューリングに適用することはできない。
【００６４】
図９は、変形されたモジュロアルゴリズムを利用したタスクスケジューリングの手続きを例示したフローチャートである。
【００６５】
例えば、或る繰り返し行われるルーチンを有するタスクをスケジューリングするために、反復遂行間隔は初期間隔ＩＩ（Ｉｎｉｔｉｎａｌ  Ｉｎｔｅｒｖａｌ）の範囲内で割り当てられる（ステップＳ４００）。この際、特定時間区間（ｔ）内でスケジューリングを行うように条件を付与されうる（ステップＳ４１０）。このような反復遂行間隔及び時間区間を有してスケジューリングが反復的に試みられる（ステップＳ４２０）。試みられたスケジューリングが失敗する場合、スケジューリングを再度試みる（ステップＳ４５０）。
【００６６】
変形されたモジュロアルゴリズムが、本来のモジュロアルゴリズムと異なる最初の特徴は、所定の時間区間（ｔ）内でスケジューリングを行いながら、特定のタスク（ｔａｓｋ（ａ））が他のタスク（ｔａｓｋ（ｂ））と重なることによって、スケジューリングに失敗する場合、タスクが重なった時間長（ｔｏｖｅｒｌａｐ）を求めるという点である（ステップＳ４２０）。続くタスクスケジューリング試みでは、新たな時間区間を（ｔ＋ｔｏｖｅｒｌａｐ）として設定してスケジューリングを試みる（ステップＳ４５０）。すなわち、本来のモジュロアルゴリズムが単位時間（例えば、“１”）ずつ時間区間を増加させた後、スケジューリングを再度試みる点が異なる。
【００６７】
もし、反復遂行サイクルの間で既定の初期間隔（ＩＩ）内にスケジューリングができないと判断されれば（ステップＳ４４０）、初期間隔を増やして反復遂行間隔を再設定することができる（ステップＳ４６０）。この場合、再び特定時間区間（ｔ）からスケジューリング試みが反復される。
【００６８】
変形されたモジュロアルゴリズムが、本来のモジュロアルゴリズムと異なる二番目の特徴は、初期間隔を再設定しなければならない場合、再設定直前の初期間隔（ＩＩ）で求めた重畳時間（ｔｏｖｅｒｌａｐ）の最小値、すなわち、ｍｉｎ（ｔｏｖｅｒｌａｐ）を求めるという点である（ステップＳ４３２）。続くタスクスケジューリング試みでは、新たな初期間隔を（ＩＩ＋ｍｉｎ（ｔｏｖｅｒｌａｐ））としてスケジューリングを試みる（ステップＳ４４２）。すなわち、本来のモジュロアルゴリズムが、単位時間（例えば、“１”）ずつ初期間隔を増加させた後、スケジューリングを再度試みる点が異なる。
【００６９】
このような２つの特徴を有する変形されたモジュロアルゴリズムを用いてタスクスケジューリングを行うことによって、本来のモジュロアルゴリズムを用いてタスクスケジューリングを行う場合に比べて、スケジューリングの遂行時間を著しく短縮させることができる。一般的に、ｔｏｖｅｒｌａｐは、単位時間よりも長い時間区間であり、ｍｉｎ（ｔｏｖｅｒｌａｐ）も、単位時間よりも長い時間間隔なので、スケジューリングの再度の試み回数が同一である場合、変形されたモジュロアルゴリズムによるスケジューリングが、本来のモジュロアルゴリズムよりも広い時間帯域に対してスケジューリングを試みるためである。
【００７０】
また、このような変形されたモジュロアルゴリズムを用いて得たスケジューリング結果は、本来のモジュロアルゴリズムを用いて得たスケジューリング結果と比較して品質が実質的にほとんど下落しない。
【００７１】
図１０は、本発明の一側面による再構成可能なプロセッサで行われるコンパイリング方法の一例を示すフローチャートである。図１０に例示したように、再構成可能なプロセッサで行われるコンパイリング方法は、初期解生成段階（ステップＳ５００）、近似的最適化段階（ステップＳ５１０）及びスケジューリング段階（ステップＳ５２０）を含んでなる。
【００７２】
初期解生成段階（ステップＳ５００）では、前述したような確率的アルゴリズムを用いて多数のプロセッシングエレメントに対して多数のタスクがマッピングされ、タスクのそれぞれに関するソースプロセッシングエレメントと宛先プロセッシングエレメントとの間の通信方式が指定されるように初期解が生成される。例えば、確率的アルゴリズムとしてシミュレーティドアニーリングアルゴリズムが使われる。また、通信方式は、共有メモリを利用した通信方式とスクラッチパッドメモリを利用したメッセージパッシング通信方式とのうちの何れか１つに指定される。一方、初期解によってマッピングされたタスクの再配置及び／または各タスクに指定された通信方式の変更が、それぞれのタスクに対して確率的になされうる。
【００７３】
近似的最適化段階（ステップＳ５１０）では、初期解に含まれたマッピング及び通信方式を近似的に最適化する。近似的な最適化のために、前述したような最適化のためのヒューリスティックが使われる。
【００７４】
例えば、特定のプロセッシングエレメントにマッピングされたタスクに関するデータのサイズの和が、スクラッチパッドメモリの容量を超過しないように違法性を除去する最適化手続きが行われる。
【００７５】
または、スクラッチパッドメモリに残余空間が存在するプロセッシングエレメントに対して、前記スクラッチパッドメモリの活用度を向上させるように、タスクに指定された通信方式が共有メモリ通信方式からメッセージパッシング通信方式に変更されうる。
【００７６】
スケジューリング段階（ステップＳ５２０）では、複数のタスクに関するスケジューリングが行われる。
【００７７】
タスクをスケジューリングする段階は、スケジューリングを試み、該試みられたスケジューリングが失敗した場合、１つのタスクと他のタスクとの重なった時間長を求めて、スケジューリングに割り当てられた時間区間と重なった時間長の和に相当する新たな時間区間とに基づいてスケジューリングを再度試みる反復的な過程を経て行われる。
【００７８】
図１１は、本発明の一側面による再構成可能なプロセッサで行われるコンパイリング方法の他の例を示すフローチャートである。
【００７９】
初期解生成段階（ステップＳ６００）、近似的最適化段階（ステップＳ６１０）及びスケジューリング段階（ステップＳ６２０）は、それぞれ図１０に示した実施形態の初期解生成段階（ステップＳ５００）、近似的最適化段階（ステップＳ５１０）及びスケジューリング段階（ステップＳ５２０）と同様に行われる。
【００８０】
但し、図１１の実施形態では、スケジューリング（ステップＳ６２０）が行われた後、スケジューリングの結果を評価する手続きがさらに行われる（ステップＳ６３０）。また、スケジューリングの評価結果に基づいて初期解生成段階（ステップＳ６００）で得られた初期解よりも良好な新規初期解を生成し（ステップＳ６４０）、新規初期解に対して再び近似的最適化段階（ステップＳ６１０）及びその後の手続きが反復的に行われる。
【００８１】
図１２は、本発明の他の側面による再構成可能なプロセッサのタスクマッピング方法の一例を示すフローチャートである。図１２に例示した再構成可能なプロセッサのタスクマッピング方法は、タスク再配置段階（ステップＳ７００）及び通信方式変更段階（ステップＳ７１０）を含んでなる。
【００８２】
タスク再配置段階（ステップＳ７００）では、マルチコアプロセッサの複数のプロセッシングエレメントのうち、１つのプロセッシングエレメントにマッピングされたタスクを、０と１との間の第１確率で、他のプロセッシングエレメントに移動させる手続きが行われる。
【００８３】
この際、再び第１確率で再びマッピングされるタスクを、０と１との間の第２確率で、他のプロセッシングエレメントの他のタスクと代替して互いに位置変更する手続きが行われることもある。
【００８４】
通信方式変更段階（ステップＳ７１０）では、プロセッシングエレメントにマッピングされたそれぞれのタスクに指定されたソースＰＥと宛先ＰＥとの間の通信方式を０と１との間の第３確率で変更する手続きが行われる。
【００８５】
このようなタスク再配置及び通信方式変更過程を通じて、さらに望ましいマッピング結果が得られる。
【００８６】
図１３は、本発明のさらに他の側面による再構成可能なプロセッサのタスクスケジューリング方法の一例を示すフローチャートである。図１３に例示したように、再構成可能なプロセッサのタスクスケジューリング方法は、スケジューリング試み段階（ステップＳ８００）、重なった時間長計算段階（ステップＳ８１０）、反復遂行間隔計算段階（ステップＳ８２０）及びスケジューリング再度試み段階（ステップＳ８３０）を含んでなる。
【００８７】
スケジューリング試み段階（ステップＳ８００）では、タスクが第１時間区間内で行われるようにスケジューリングを試みる。もし、１つのタスクと他のタスクとが重なってスケジューリングが失敗した場合、重なった時間長計算段階（ステップＳ８１０）では、重なった時間長が計算され、第１時間区間及び重なった時間長の和に相当する時間長を有する第２時間区間で新たなスケジューリングが試みられる。
【００８８】
また、図１３の実施形態は、繰り返し行われる周期的ルーチンを有した場合にも適用可能なので、タスクのうち少なくとも一部が、第１反復遂行間隔をおいて繰り返し行われる場合、重なった多くの時間長のうち、最小値を求めて、現在の反復遂行間隔と重なった時間長の最小値の和に相当する時間長を新たな反復遂行間隔で設定することができる（ステップＳ８２０）。その後、第２反復遂行間隔及び第２時間区間の条件下でスケジューリングが反復的に再度試みられる（ステップＳ８３０）。
【００８９】
一方、本発明の実施形態は、コンピュータで読み取り可能な記録媒体にコンピュータで読み取り可能なコードとして具現することが可能である。コンピュータで読み取り可能な記録媒体は、コンピュータシステムによって読み取れるデータが保存されるあらゆる種類の記録装置を含む。
【００９０】
コンピュータで読み取り可能な記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光データ保存装置などがあり、また、キャリアウェーブ（例えば、インターネットを介した伝送）の形態で具現するものを含む。また、コンピュータで読み取り可能な記録媒体は、ネットワークで連結されたコンピュータシステムに分散されて、分散方式でコンピュータで読み取り可能なコードとして保存されて実行可能である。そして、本発明を具現するための関数プログラム、コード及びコードセグメントは、本発明が属する技術分野のプログラマーによって容易に推論されうる。
【００９１】
さらに、前述した実施形態は、本発明を例示的に説明するためのものであって、本発明の権利範囲が、特定の実施形態に限定されるものではない。
【産業上の利用可能性】
【００９２】
本発明は、マルチコアプロセッサで行われるプログラムのコンパイル方法、マルチコアプロセッサのタスクマッピング方法及びタスクスケジューリング方法関連の技術分野に適用可能である。
【図１Ａ】
2014078239.tif 000003
【図１Ｂ】
2014078239.tif 000004
【図２Ａ】
2014078239.tif 000005
【図２Ｂ】
2014078239.tif 000006
【図３】
2014078239.tif 000007
【図４】
2014078239.tif 000008
【図５】
2014078239.tif 000009
【図６】
2014078239.tif 000010
【図７】
2014078239.tif 000011
【図８】
2014078239.tif 000012
【図９】
2014078239.tif 000013
【図１０】
2014078239.tif 000014
【図１１】
2014078239.tif 000015
【図１２】
2014078239.tif 000016
【図１３】
2014078239.tif 000017