実行条件解析による並列化スケジューリングの効率化

• Item type: SIG Technical Reports(1)
• 公開日: 2009-05-21
• タイトル: 実行条件解析による並列化スケジューリングの効率化
• タイトル / 言語: en
• タイトル: An Efficient Scheduling for Multiprocessor System using Condition Analysis
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 三菱電機株式会社先端技術総合研究所
• 著者所属: 三菱電機株式会社先端技術総合研究所
• 著者所属(英): en
• 著者所属(英): Mitsubishi Electric Corporation Advanced Technology R&D Center
• 著者所属(英): en
• 著者所属(英): Mitsubishi Electric Corporation Advanced Technology R&D Center
• 著者名: 南出, 英明; 佐々木, 賢一
• 著者名(英): Hideaki, Minamide; Kenichi, Sasaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 消費電力を抑えつつ高い実行性能を得るには，マルチプロセッサによる並列処理が有効である．プログラムの並列化では，プログラムをタスクに分割し，各タスクの実行時間とタスク間の依存関係を基に，総実行時間が最短となるようにスケジューリングを行う．一般に，タスクの実行時間は入力に依存し，各タスクの実行時間の間には相関がある．このため，ある入力に対して最適なスケジューリングが，他の入力に対しても最適であるとは限らない．そこで本研究では，全ての入力に対して，最悪実行時間が最短となるものを最適なスケジュールと定義する．スケジューリングや最悪実行パスの解析はNP問題であるが，タスク間での実行時間の相関を解析し計算量を抑制する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Parallel processing on multiprocessors is a promising approach to performance enhancement with low-power consumption. When parallelizing a program for multiprocessors, the program is first partitioned into a set of tasks, and then the tasks are scheduled based on their execution times and inter-dependencies in order to minimize the total execution time on the multiprocessors. In general, the execution times of tasks depend on their inputs, and there exist correlations among the execution times of the tasks. Therefore, an optimal scheduling for a certain input is not always optimal for a different input. In this paper, we define an optimal schedule as the one whose worst-case execution time is the minimum. In order to obtain the optimal schedule, scheduling and worst-case path analysis, each of which is an NP problem, need to be done simultaneously. This paper proposes an efficient technique for this problem, which carefully analyzes the correlations of tasks' execution times to reduce the solution space.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2009-CSEC-45, 号 24, p. 1-7, 発行日 2009-05-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会