図面 (/)

技術 並列化コンパイル方法、並列化コンパイラ、及び、電子装置

出願人 株式会社デンソー
発明者 鍋田重仁鈴木範幸
出願日 2015年2月5日 (4年5ヶ月経過) 出願番号 2015-021112
公開日 2016年8月8日 (2年11ヶ月経過) 公開番号 2016-143377
状態 特許登録済
技術分野 特別なプログラム実行装置
主要キーワード マクロフロー 分割ループ 融合アルゴリズム コスト推定値 グローバル最適化 実行管理テーブル データフロー処理 プロセッサクラスタ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2016年8月8日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (6)

課題

並列化プログラム品質の維持や管理を容易にする

解決手段

シングルプロセッサステムにより実行され、条件付コンパイルにより入力情報に応じてコンパイル対象とするか否かが切り替えられる複数の部分から構成される一連記述である条件付記述が含まれている逐次プログラムは、入力情報に関わらず複数のマクロタスクに分割される。その後、並列実行可能なマクロタスクのうちの全部又は一部を異なるプロセッサユニット割り当て、マルチプロセッサシステムにより実行される並列化プログラムが生成されるが、このとき、1の条件付記述に基づく処理に対応する複数のマクロタスクは、同一のプロセッサユニットに割り当てられる(S110)。

概要

背景

マルチコアプロセッサが搭載された車載装置において、各コアに機能を分散させることでスループットを向上させることが知られている(非特許文献1)。また、シングルコアプロセッサ用のプログラム逐次プログラム)から、マルチコアプロセッサにより並列処理可能な並列化プログラムを生成する並列化コンパイラが知られている。

概要

並列化プログラムの品質の維持や管理を容易にするシングルプロセッサステムにより実行され、条件付コンパイルにより入力情報に応じてコンパイル対象とするか否かが切り替えられる複数の部分から構成される一連記述である条件付記述が含まれている逐次プログラムは、入力情報に関わらず複数のマクロタスクに分割される。その後、並列実行可能なマクロタスクのうちの全部又は一部を異なるプロセッサユニット割り当て、マルチプロセッサシステムにより実行される並列化プログラムが生成されるが、このとき、1の条件付記述に基づく処理に対応する複数のマクロタスクは、同一のプロセッサユニットに割り当てられる(S110)。

目的

本発明は、並列化プログラムの品質の維持や管理を容易にすることを目的とする

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

シングルプロセッサステムにより実行されるプログラムであって、条件付コンパイルにより入力情報に応じてコンパイル対象とするか否かが切り替えられる複数の部分から構成される一連記述である条件付記述が含まれている逐次プログラムに記述された処理を、前記入力情報に関わらず複数のマクロタスクに分割する分割手順と(S210)、前記マクロタスク間のデータ依存性に基づき、マルチプロセッサシステムを構成する複数のプロセッサユニットにより並列実行可能な前記マクロタスクを抽出する抽出手順と(S220)、それぞれの前記マクロタスクをいずれかの前記プロセッサユニットに割り当てる処理であって、並列実行可能な前記マクロタスクのうちの全部又は一部を、異なる前記プロセッサユニットに割り当て、前記マルチプロセッサシステムにより実行される並列化プログラムを生成するスケジューリング手順と(S110)、を備え、前記スケジューリング手順において、1の前記条件付記述に基づく処理に対応する複数の前記マクロタスクを、同一の前記プロセッサユニットに割り当てること、を特徴とする並列コンパイル方法

請求項2

請求項1に記載の並列化コンパイル方法において、異なる前記プロセッサユニットに割り当て可能な複数の前記マクロタスクに対応する処理に係る前記条件付記述に関する報知を行う報知手順(S130)をさらに備えること、を特徴とする並列化コンパイル方法。

請求項3

請求項1又は請求項2に記載の並列化コンパイル方法において、前記並列化プログラムの性能を検証する検証手順(S120)をさらに備えること、を特徴とする並列化コンパイル方法。

請求項4

請求項1から請求項3のうちのいずれか1項に記載の並列化コンパイル方法において、前記並列化プログラムの性能を検証する検証手順(S120)と、前記検証手順での検証結果から前記並列化プログラムの性能が一定の水準に達しない場合には、異なる前記プロセッサユニットに割り当て可能な複数の前記マクロタスクに対応する処理に係る前記条件付記述に関する報知を行う報知手順(S130)と、をさらに備えることを特徴とする並列化コンパイル方法。

請求項5

シングルプロセッサシステムにより実行されるプログラムであって、条件付コンパイルにより入力情報に応じてコンパイル対象とするか否かが切り替えられる複数の部分から構成される一連の記述である条件付記述が含まれている逐次プログラムに記述された処理を、前記入力情報に関わらず複数のマクロタスクに分割する分割手段と(S210)、前記マクロタスク間のデータ依存性に基づき、マルチプロセッサシステムを構成する複数のプロセッサユニットにより並列実行可能な前記マクロタスクを抽出する抽出手段と(S220)、それぞれの前記マクロタスクをいずれかの前記プロセッサユニットに割り当てる処理であって、並列実行可能な前記マクロタスクのうちの全部又は一部を、異なる前記プロセッサユニットに割り当て、前記マルチプロセッサシステムにより実行される並列化プログラムを生成するスケジューリング手段として(S110)、コンピュータを動作させることを特徴とし、前記スケジューリング手段は、1の前記条件付記述に基づく処理に対応する複数の前記マクロタスクを、同一の前記プロセッサユニットに割り当てること、を特徴とする並列化コンパイラ(1)。

請求項6

シングルプロセッサシステムにより実行されるプログラムであって、条件付コンパイルにより入力情報に応じてコンパイル対象とするか否かが切り替えられる複数の部分から構成される一連の記述である条件付記述が含まれている逐次プログラムに記述された処理を、前記入力情報に関わらず複数のマクロタスクに分割する分割手順と(S210)、前記マクロタスク間のデータ依存性に基づき、マルチプロセッサシステムを構成する複数のプロセッサユニットにより並列実行可能な前記マクロタスクを抽出する抽出手順と(S220)、それぞれの前記マクロタスクをいずれかの前記プロセッサユニットに割り当てる処理であって、並列実行可能な前記マクロタスクのうちの全部又は一部を、異なる前記プロセッサユニットに割り当て、前記マルチプロセッサシステムにより実行される並列化プログラムを生成するスケジューリング手順と(S110)、を備え、前記スケジューリング手順において、1の前記条件付記述に基づく処理に対応する複数の前記マクロタスクを、同一の前記プロセッサユニットに割り当てること、を特徴とする並列化コンパイル方法により生成された前記並列化プログラムにより動作する前記マルチプロセッサシステムを備えることを特徴とする電子装置(20)。

技術分野

0001

本発明は、並列コンパイル方法並列化コンパイラ、及び、電子装置に関する。

背景技術

0002

マルチコアプロセッサが搭載された車載装置において、各コアに機能を分散させることでスループットを向上させることが知られている(非特許文献1)。また、シングルコアプロセッサ用のプログラム逐次プログラム)から、マルチコアプロセッサにより並列処理可能な並列化プログラムを生成する並列化コンパイラが知られている。

先行技術

0003

K Seo,J Yoon,J Kim,T Chung,K Yi,N Chang、「Coordinated implementation and processing of a unified chassis control algorithm with multi-central processing unit」、JAUTO1346IMechE、2009年、Vol.224 Part D

発明が解決しようとする課題

0004

ここで、逐次プログラムにおいて、条件コンパイルスイッチにより仕向地等に応じてコンパイル対象となる記述を選択する場合がある(条件付コンパイル)。並列化コンパイラを用いてこのような逐次プログラムから並列化プログラムを生成する場合、一般的に、まず、条件コンパイルスイッチに基づき逐次プログラムの中からコンパイルの対象となる部分が特定され、該部分から並列化プログラムが生成される。

0005

しかしながら、コンパイルの対象となる部分が変更されると、逐次プログラムを構成するマクロタスク間のデータ依存性制御依存性が変化する可能性がある。これにより、条件付コンパイルスイッチが設けられた一連の記述に基づく複数の処理が、異なるプロセッサコア割り当てられる場合がある。

0006

このような場合、同一の逐次プログラムから生成された仕向地等の異なる複数の並列化プログラムが、同一の逐次プログラムから生成され、同等の機能を有するにも関わらず、各プロセッサコアに割り当てられる処理内容が大きく異なる可能性がある。その結果、品質の維持や並列化プログラムの管理が困難になる。

0007

本発明は、並列化プログラムの品質の維持や管理を容易にすることを目的とする。

課題を解決するための手段

0008

本発明の一側面である並列化コンパイル方法は、シングルプロセッサステムにより実行されるプログラムであって、条件付コンパイルにより入力情報に応じてコンパイル対象とするか否かが切り替えられる複数の部分から構成される一連の記述である条件付記述が含まれている逐次プログラムに記述された処理を、入力情報に関わらず複数のマクロタスクに分割する分割手順と(S210)、マクロタスク間のデータ依存性に基づき、マルチプロセッサシステムを構成する複数のプロセッサユニットにより並列実行可能なマクロタスクを抽出する抽出手順と(S220)、それぞれのマクロタスクをいずれかのプロセッサユニットに割り当てる処理であって、並列実行可能なマクロタスクのうちの全部又は一部を、異なるプロセッサユニットに割り当て、マルチプロセッサシステムにより実行される並列化プログラムを生成するスケジューリング手順と(S110)、を備え、スケジューリング手順において、1の条件付記述に基づく処理に対応する複数のマクロタスクを、同一のプロセッサユニットに割り当てる。

0009

このような構成によれば、スケジューリング手順により条件付記述を全て含んだ状態で逐次プログラムから並列化プログラムが生成される。そして、入力情報を設定することで、該並列化プログラムにおける条件付記述の中からコンパイルの対象外となる部分を除去し、入力情報に対応する種別の並列化プログラムを生成することができる。

0010

スケジューリング手順により生成された段階の並列化プログラムでは、1の条件付記述に基づく各処理は、同一のプロセッサユニットに割り当てられる。このため、入力情報を設定することで仕向地等の異なる複数の種別の並列化プログラムが生成される場合であっても、各種別の並列化プログラムの共通性をより一層高めることができ、その結果、並列化プログラムの品質の維持や管理が容易になる。

0011

なお、この欄及び特許請求の範囲に記載した括弧内の符号は、1つの態様として後述する実施形態に記載の具体的手段との対応関係を示すものであって、本発明の技術的範囲を限定するものではない。

図面の簡単な説明

0012

自動並列化コンパイラがインストールされたPCの構成を示すブロック図である。
自動並列化処理フローチャートである。
ソフト構造解析処理のフローチャートである。
車載装置の構成を示すブロック図である。
具体例における逐次プログラムや割当情報の説明図である。

実施例

0013

以下、本発明の実施形態について図面を用いて説明する。なお、本発明の実施の形態は、下記の実施形態に何ら限定されることはなく、本発明の技術的範囲に属する限り種々の形態を採りうる。

0014

[本実施形態について]
1.自動並列化コンパイラについて
本実施形態の自動並列化コンパイラは、組込みシステム向けのシングルプロセッサシステム用のソースプログラム(逐次プログラム)から、組込みシステム向けのマルチプロセッサシステム用の並列化プログラムを生成する機能を有している。

0015

1−1.自動並列化コンパイラの設計概念
本実施形態の自動並列化コンパイラは、以下の機能を有している。
(1)マルチグレイン並列処理
(2)コンパイル時のスタティックスケジューリングコードの挿入
(3)実行時のダイナミックスケジューリングコードの生成
(4)階層型マクロデータフローの実現
(5)マクロタスクの分割/融合,Loop distribution/interchange等の並列性抽出
(6)データローカライズによるデータ転送効率の向上
(7)コンパイラによる電力削減
1−2.自動並列化コンパイラの内部処理
自動並列化コンパイラは、Front End(FE),Middle Path(MP),Back End(BE)の3つのステージを有している。各ステージは実行形態として独立しており、FE,MPから生成される中間言語によりコード授受が行われる。

0016

なお、FEは、逐次プログラムのソースコード字句解析構文解析を行い、MPにおいてparse可能な中間言語を生成する部位である。FEの生成する中間言語は、基本的に4つのオペランドを持つ解析木(parse tree)で表現されており、全体として1つのブロックを形成していて構造化は行われていない。

0017

また、MPは、制御依存性解析・データ依存性解析・最適化等を行う部位であり、そのデータを用いて粗粒度・中粒度・近細粒度並列化のマルチグレイン並列処理を行う。
また、BEは、MPが生成した並列化中間言語を読み込んで実際のマシンコードを生成する部位である。当該部位は、ターゲットとなっているマルチコアアーキテクチャアセンブラコードを生成するBEの他、OpenMP用の並列化FortranコードやCコードを生成するBEを有している。さらには、当該部位は、後述する並列化APIによりメモリ配置データ転送を含めて並列化したコードを生成するBE等、多様なアーキテクチャに対応したコードを出力するBEを有している。

0018

1−3.自動並列化コンパイラの並列性解析
自動並列化コンパイラは、逐次プログラムを、基本ブロック(BB),繰り返しブロック(RB),サブルーチンブロック(SB)の3種類の粗粒度タスク(マクロタスク(MT))に分割するマクロデータフロー処理を行う。

0019

しかし、マクロデータフロー処理では、プログラムの形状によってはプロセッサ利用効率が上がらず、十分な粗粒度並列性が抽出できないという問題点がある。
そこで、自動並列化コンパイラでは、従来の単階層マクロデータフロー処理手法を拡張し、MT内部に対してマクロデータフロー処理を階層的に利用する階層型マクロデータフロー処理を採用している。階層的マクロデータフロー処理では、MTの階層的な定義を行い、各階層のマクロタスクに対してマクロタスク間の並列性の解析を行う。

0020

マクロフローグラフMFG)の生成>
自動並列化コンパイラは、まず、生成された各階層のマクロタスクに対して、マクロタスク間の制御依存性とデータ依存性を解析する。この解析結果は、マクロフローグラフ(MFG)として表される。

0021

マクロタスクグラフ(MTG)の生成>
MFGは、マクロタスク間の制御依存性とデータ依存性を表すが、並列性は表していない。並列性を抽出するためには、各マクロタスクに対し、制御依存性とデータ依存性の両方を考慮した最早実行可能条件解析を行う必要がある。最早実行可能条件とは、そのMTが最も早い時点で実行可能になる条件であり、次のような実行条件から求められる。

0022

(1)MTiがMTjにデータ依存するならば、MTjの実行が終了するまでMTiは実行できない。
(2)MTjの条件分岐先が確定すれば、MTjの実行が終了しなくても、MTjに制御依存するMTiは実行できる。

0023

したがって、最早実行可能条件の一般形は次のようになる。
(MTiが制御依存するMTjがMTiに分岐する)
AND
((MTiがデータ依存するMTk(0≦k≦|N|))が終了)OR(MTkが実行されないことが決定する))
マクロタスクの最早実行可能条件は、マクロタスクグラフ(MTG)で表される。

0024

1−4.マルチグレイン並列処理
自動並列化コンパイラでは、従来のループ並列化に加え、ループ間サブルーチン間における粗粒度タスク間の並列性を利用する粗粒度タスク並列処理や、ステートメント間の並列性を利用する近細粒度並列処理を効果的に組み合わせたマルチグレイン並列処理(参考文献1(本多弘樹, 岩田雅彦,原博徳、「Fortranプログラム粗粒度タスク間の並列性検出手法」、電子情報通信学会論文誌、1990年)参照)を実現している。

0025

<粗粒度タスク並列処理>
自動並列化コンパイラは、BB,RB,SB等のMT間の制御依存性とデータ依存性を表現したマクロフローグラフ(MFG)を生成し、さらに、MFGから最早実行可能条件解析により引きだしたMT間の並列性を、マクロタスクグラフ(MTG)として表現する(参考文献1,参考文献2(笠原,合田,吉田,岡本,本多、「Fortranマクロデータフロー処理のマクロタスク生成手法」、信学論、1992年、Vol.J75-D-I、No.8、pp.511-525)参照)。

0026

その後、自動並列化コンパイラは、MTG上のMTを、1つ以上のプロセッサエレメント(PE)をグルーピングしたプロセッサグループPG)に割り当てる。
<中粒度並列処理>
PGに割り当てられたMTが、DOALLループ、或いはイタレーションベルで並列処理が可能なものであれば、そのMTには、プロセッサクラスタ内のプロセッサによって中粒度並列処理がなされる。この中粒度並列処理は、DOループイタレーション間の並列性を利用する並列処理のことであり、マルチプロセッサにおける並列処理では最も一般的なものである。

0027

<近細粒度並列処理>
ステートメントレベルの近細粒度タスクに対する並列処理を、近細粒度並列処理という。これによって、依存の無いステートメントも並列実行が可能になり、実行時間が短縮される。

0028

1−5.マクロタスクスケジューリング
粗粒度タスク並列処理では、各階層で生成されたマクロタスクは、PGに割り当てられて実行される。どのPGにマクロタスクを割り当てるかを決定するスケジューリング手法として、下記のダイナミックスケジューリングとスタティックスケジューリングがあり、これらは、マクロタスクグラフの形状や実行時非決定性等を元に選択される。

0029

<ダイナミックスケジューリング>
条件分岐等の実行時不確定性が存在する場合には、ダイナミックスケジューリングによって実行時にマクロタスクをPGに割り当てる。ダイナミックスケジューリングルーチンは、マクロタスクの終了や分岐方向の決定に応じてマクロタスク実行管理テーブルを操作し、各マクロタスクの最早実行可能条件を検査する。

0030

マクロタスクが実行可能であれば、レディキューにマクロタスクが投入される。レディキュー内のマクロタスクは、その優先順位に従ってソートされ、レディキューの先頭のマクロタスクが、アイドル状態のプロセッサクラスタに割り当てられる。

0031

また、ダイナミックスケジューリングコード生成時には、一つの専用のプロセッサがスケジューリングを行う集中スケジューリング方式と、スケジューリング機能を各プロセッサに分散した分散スケジューリング方式を、使用するプロセッサ台数,システムの同期オーバーヘッドに応じて使い分けることができる。

0032

<スタティックスケジューリング>
一方、スタティックスケジューリングは、マクロタスクグラフがデータ依存エッジのみを持つ場合に使用され、自動並列化コンパイラが、コンパイル時にPGへのマクロタスクの割り当てを決める方式である。

0033

スタティックスケジューリングは、実行時スケジューリングオーバーへッドを無くし、データ転送と同期のオーバーへッドを最小化することが可能であるため、粒度の細かいタスクのスケジューリングに対しても効果的に利用できる。

0034

また、スタティックスケジューリングの際、タスクのコストは自動並列化コンパイラでのタスクコスト推定値を適用するが、自動並列化コンパイラのプロファイル自動フィードバック機能を用いることで、実コストでタスクスケジューリングを行うことも可能である。

0035

プロファイル自動フィードバック機能を用いる場合、第1フェーズとして、逐次プログラムをMTに分解し、MT毎にプロファイラ関数を挿入して逐次プログラムを生成する。このプロファイラ関数では、タスク実行コスト(clock cycle)とタスク実行回数計測する。このプロファイラ関数が挿入された逐次プログラムを一度ターゲットとなるマシン上で実行することで、ターゲットとなるマシン上でのタスク実行コストとタスク実行回数の情報を持つファイルを出力する。

0036

そして、第2フェーズにて、この出力ファイルと逐次プログラムを入力として、実コストに基づきスケジューリングした並列化プログラムが生成される。
1−6.データローカライゼーション
自動並列化コンパイラは、プログラム全域に渡るキャッシュ最適化を行うことが可能である。自動並列化コンパイラは、ループ間などの並列性を解析した後、ループ間にデータ依存があることが分かると、依存があるループ間でのキャッシュのグローバル最適化試みる(参考文献3(特許第4177681号公報)参照)。

0037

具体的には、各ループでアクセスされる配列を調査し、同一の分割ループは同一の配列部分にアクセスするように調整することにより、同一の分割ループを同一プロセッサに割り当てる。これにより、同一の分割ループでは、全ての配列データがキャッシュ上で再利用されるようになる。

0038

また、このローカライズ技術は、
(1)任意のサイズのローカルメモリ或いは分散共有メモリが与えられた時に、DMA(DTU)(参考文献4(特許第4476267号公報)参照)を用いアクセスされる前に、前記プロセッサに近接したローカル或いは分散共有メモリに事前ロードし、プログラム全域で再利用する。

0039

(2)送付先メモリ一杯の場合には、送付先プロセッサのDTUが、メモリからの掃き出し優先順位に従ってデータを共有メモリ等へ掃き出したことを同期フラグで知らされたら、自動的に空いたメモリにデータを転送する。

0040

(3)将来再利用されるデータであるが、暫くの間使用されず、メモリの領域を開ける必要がある場合には、CPUによるタスク実行の裏側でDTUが当該データを集中共有メモリ待避し、使用時までに再ロードする。

0041

といったローカルメモリ管理,データ転送技術へと進化している(参考文献5(英国特許第2478874号明細書)。
1−7.並列化プログラムの生成
自動並列化コンパイラにおける並列化プログラムの生成は、自動並列化API(参考文献7(早稲田大学、「Optimally Scheduled Advanced Multiprocessor Application Program Interface」、2008年)参照)を用い、並列化C或いは並列化Fortranのような、source-to-sourceで並列化を行うことが可能である。

0042

この場合には、自動並列化コンパイラは、様々なプラットフォームにおいて並列化プログラムを実行可能とするため、後述する自動並列化API標準解釈系を用いて、各プロセッサ用のC或いはFortranのディレクティブ部分をランタイムライブラリコールに変換する。その後、自動並列化コンパイラは、各プロセッサ用のコードを逐次コンパイラでコンパイルしてバイナリを生成し、このバイナリをリンクすると、対象となるマルチプロセッサ上で並列化プログラムを実行可能となる。

0043

2.組み込みシステム用の逐次プログラムの並列化手順と手法
次に、組み込みシステム用の逐次プログラムの特徴について述べ、本実施形態の自動並列化コンパイラによる並列化手法について説明する。なお、組み込みシステムとは、例えば、車載装置であっても良いし、車載装置以外の電子装置であっても良い。また、逐次プログラムは、モデルベース設計により自動生成されたもの(一例として、MathWork社のMatlab(登録商標),Simulink(登録商標)にて自動生成されたもの)であっても良い。

0044

自動並列化コンパイラは、条件分岐と代入文により構成され、処理が細かい逐次プログラムに対して、インライン展開リネーミングを行い、並列性を抽出する。また、リアルタイム性順守するために条件分岐隠蔽のためのタスク融合を行い、オーバーヘッドが低くなるようにスタティックスケジューリングを行う。さらに、実コストでスタティックスケジューリングを行うために、プロファイル自動フィードバック機能を適用しても良い。

0045

また、逐次プログラムにおいて、条件コンパイルスイッチ(プリプロセッサへの命令)により、仕向地や機能やハードウェアの構成等が異なる組み込みシステムの各種別に応じてコンパイルの対象となる記述を選択する条件付コンパイルが行われる場合がある。このような場合、逐次プログラムの各条件コンパイルスイッチの引数として、いずれかの種別に対応する情報(仕向地等を示す情報)を設定することで、逐次プログラムから、該種別に対応するバイナリコードが生成される。なお、条件付コンパイルスイッチの引数に応じてコンパイル対象とするか否かが切り替えられる複数の部分から構成される一連の記述を、条件付記述と記載する。

0046

これに対し、本実施形態の自動並列化コンパイラは、条件付コンパイルによるコンパイル対象の選択を無視し、逐次プログラムの全ての部分を対象としてマクロタスクの分割や並列性の抽出やスタティックスケジューリング等を行い、並列化プログラムを生成する。その後、並列化プログラムから、条件付コンパイルによりコンパイルの対象外となる記述を特定し、該記述を除いた状態で、マルチコアプロセッサを動作させるためのバイナリデータを生成する。さらに、自動並列化コンパイラは、スタティックスケジューリングにおいて、1の条件付記述に基づく全処理に対応するマクロタスクについては、全て同一のPGに割り当てる。

0047

2−1.自動並列化コンパイラの動作環境等について
自動並列化コンパイラ1は、例えば、DVD,CD−ROMUSBメモリメモリカード(登録商標)等の光ディスク磁気ディスク半導体製メモリ等として構成された記憶媒体18に記憶された状態で、ユーザに提供される(図1参照)。無論、ネットワークを経由してユーザに提供されても良い。

0048

そして、自動並列化コンパイラ1がインストールされたパーソナルコンピュータ(PC)10は、自動並列化コンパイル装置として動作する。PC10は、ディスプレイ11,HDD12,CPU13,ROM14,RAM15,入力装置16,読取部17等を備える。

0049

ディスプレイ11は、CPU13から受けた映像信号を、ユーザに対して映像として表示する。
また、入力装置16は、キーボードマウス等から構成され、ユーザが操作することにより、その操作に応じた信号をCPU13に出力する。

0050

また、読取部17は、自動並列化コンパイラ1等が記憶された記憶媒体18からデータを読み取る部位である。
また、RAM15は読み出し書き込み可能揮発性メモリであり、ROM14は読み出し専用不揮発性メモリであり、HDD12は読み出し,書き込みが可能な不揮発性メモリである。ROM14,HDD12には、CPU13が読み出して実行するプログラム等が予め記憶されている。

0051

また、RAM15は、CPU13がROM14,HDD12に記憶されたプログラムを実行する際に、そのプログラムを一時的に保存するための記憶領域や、作業用のデータを一時的に保存するための記憶領域として用いられる。

0052

また、CPU13は、OSをHDD12から読み出して実行し、HDD12に記録されている各種プログラムをOS上のプロセスとして実行する。また、CPU13は、このプロセスにおいて、必要に応じて入力装置16から信号の入力を受け付け、ディスプレイ11に映像信号を出力し、RAM15,HDD12に対してデータの読み出し/書き込みの制御を行う。

0053

また、PC10には、読取部17を介して記憶媒体18から読み取られた自動並列化コンパイラ1がインストールされており、自動並列化コンパイラ1は、HDD12に保存され、OS上のプロセスとして実行されるアプリケーションの1つとなっている。

0054

なお、この自動並列化コンパイル装置は、車載装置等といった組み込みシステム向けの並列化プログラムの開発に用いられる。しかしながら、これに限定されることは無く、例えば情報家電等といった様々な用途の組込みシステム向けの並列化プログラムの開発や、組込みシステム以外の他の用途の並列化プログラムの開発に用いることができる。

0055

2−2.自動並列化処理について
次に、条件付コンパイルがなされる逐次プログラムに基づき並列化プログラムを生成する自動並列化処理について、図2のフローチャートを用いて説明する。なお、条件付コンパイルにより、該逐次プログラムからは、条件コンパイルスイッチにて参照される引数の値に対応する種別の組み込みシステムに搭載されるバイナリデータが生成される。また、本処理は、PC10にて動作している自動並列化コンパイラ1がユーザからの指示に応じて開始する。

0056

S100では、自動並列化コンパイラ1は、逐次プログラムに記述されている条件コンパイルスイッチに基づき、逐次プログラムから条件付記述を特定し、S105に処理を移行する。

0057

S105では、自動並列化コンパイラ1は、ソフト構造解析処理(図3参照)を実行し、MTGを生成し、S110に処理を移行する。
S110では、自動並列化コンパイラ1は、ソフト構造解析処理で生成されたMTGに基づきスタティックスケジューリングを行う。これにより、並列実行可能なマクロタスクの全部又は一部が異なるPGに割り当てられ(該割り当ての結果を示す情報を割当情報とする)、並列化プログラムが生成される。この時、1の条件付記述に基づく処理に対応するマクロタスクは、全て同一のPGに割り当てられる。

0058

なお、並列化プログラムでは、各条件付記述に対応する記述に対し、逐次プログラムにおける該条件付記述に設定されていた条件コンパイルスイッチと同等の内容の条件コンパイルスイッチが設定されている。このため、並列化プログラムの条件コンパイルスイッチの引数をいずれかの種別に対応する値に設定すると、該種別に対応する並列化プログラムとなる。

0059

また、自動並列化コンパイラ1は、スタティックスケジューリングにおいて、プロファイル自動フィードバック機能により各マクロタスクを実行する際の実コスト(一例として処理時間)を特定しても良い。そして、各条件付記述に基づく処理に対応するマクロタスクを同一のPGに割り当てつつ、各PGの処理負荷が同程度となるように、並列実行可能なマクロタスクを各PGに割り当てても良い。

0060

また、この時、自動並列化コンパイラ1は、並列化プログラムを様々なプラットフォームで動作させるため、自動並列化API標準解釈系を用いて、自動並列化APIが加えられた並列化プログラムをランタイムライブラリが実装された並列化プログラムに変換しても良い。

0061

S115では、自動並列化コンパイラ1は、各条件付記述に基づく処理に対応するマクロタスクを特定すると共に、ソフト構造解析処理で生成されたMTGに基づき、各々の条件付記述について、対応する各マクロタスクが並列化可能であるか否かを判定する。そして、マクロタスクを並列化可能と判定された条件付記述を特定し、S120に処理を移行する。

0062

S120では、自動並列化コンパイラ1は、並列化プログラムの性能を検証する。具体的には、例えば、自動並列化コンパイラ1は、各マクロタスクの処理時間を特定すると共に、各PGについて、該PGに割り当てられた全マクロタスクの処理時間の総和を算出しても良い。この時、他のPGでの処理の終了を待つ必要があるPGについては(例えば、データ依存性を有するマクロタスクに対応する処理が他のPGで行われる場合等)、待ち時間を算出し、該待ち時間をPGの処理時間の総和に加算する。そして、各PGの処理時間の総和うち、最大値(並列実行時間)を特定し、これを検証結果としても良い。

0063

この他にも、例えば、同様にして並列実行時間を算出すると共に、全マクロタスクの処理時間の総和(最大処理時間)を、シングルコアプロセッサが逐次プログラムを実行した際の処理時間として算出しても良い。そして、並列実行時間を最大処理時間で除算した値を、低減率(並列化により処理速度がどの程度向上するかを示す値)として算出し、これを検証結果としても良い。

0064

なお、自動並列化コンパイラ1は、生成された並列化プログラムの性能の検証結果を報知しても良い。
S125では、自動並列化コンパイラ1は、並列化プログラムの性能の検証結果に基づき、並列化プログラムの性能が一定の水準に達しているか否かを判定する。具体的には、例えば、並列実行時間が予め定められた閾値以下である場合や、低減率が予め定められた閾値以下である場合等には、並列化プログラムの性能が一定の水準に達しているとみなしても良い。この他にも、例えば、並列実行時間と低減率の双方が閾値以下である場合には、並列化プログラムの性能が一定の水準に達しているとみなしても良い。そして、肯定判定が得られた場合には(S125:Yes)、S130に処理を移行し、否定判定が得られた場合には(S125:No)、S135に移行する。

0065

S130では、自動並列化コンパイラ1は、S115で特定された条件付記述(対応する各マクロタスクの並列化が可能である条件付記述)を示すレポートを生成し、HDD12に保存する。なお、1の条件付記述に基づく処理に対応する並列化可能な複数のマクロタスクを示すレポートを生成しても良いし、該条件付記述と該マクロタスクの双方又は一方をディスプレイ11に表示しても良い。

0066

S135では、自動並列化コンパイラ1は、並列化プログラムに記述されているコンパイラスイッチを解析し、解析結果に応じた処理を行うプリプロ処理を実行する。この時、条件コンパイルスイッチに基づき、並列化プログラムの中から、引数に対応する種別にてコンパイルの対象となる記述を特定し、S140に移行する。

0067

S140では、自動並列化コンパイラ1は、並列化プログラムにおけるコンパイルの対象となる記述から、マルチコアプロセッサを動作させるためのバイナリデータを生成し、本処理を終了する。

0068

2−3.ソフト構造解析処理について
次に、逐次プログラムからMTGを生成するソフト構造解析処理について、図3のフローチャートを用いて説明する。本処理は、自動並列化処理にて実行される。

0069

S200では、自動並列化コンパイラ1は、逐次プログラムに対し、インライン展開(サブルーチンをコールする記述を、該サブルーチンにて定義されている処理の記述に置き換える)を行い、S205に移行する。組み込みシステム用の逐次プログラムは、一般的に処理が細かく、粗い粒度での並列化が困難であるが、インライン展開を行うことで、サブルーチン内の並列性をも有効活用できるようになる。

0070

S205では、自動並列化コンパイラ1は、ローカル変数リネームを行う。例えばSimulinkモデルから自動生成された逐次プログラム等では、ROM使用量削減のため、多くの箇所で同じローカル変数が繰り返し使用される場合があり、これにより、並列性解析の際にデータ依存があると特定され、並列性が十分引き出せなくなってしまう。そこで、使い回しされているローカル変数のリネームが行われる。

0071

具体的には、自動並列化コンパイラ1は、逐次プログラムの各関数内において、同一名称のローカル変数が用いられている複数の処理ブロックを特定すると共に、特定した各処理ブロックにおいて独自の名称のローカル変数が用いられるよう、逐次プログラムを改変する。

0072

なお、処理ブロックとは、例えば、ループ処理や、if文やswitch-case文等の分岐処理のステートメントと、これに付随する代入文等から構成される記述の集合体であっても良い。また、このほかにも、例えば、逐次プログラムを生成したSimulinkモデルにおける各ブロックに対応する記述の集合体を、処理ブロックとしても良い。

0073

S210では、自動並列化コンパイラ1は、これらの処理がなされた逐次プログラムをマクロタスクに分割する。そして、各マクロタスク間のデータ依存性と制御依存性を解析してMFGを生成し、S215に移行する。

0074

S215では、自動並列化コンパイラ1は、MFGが示す制御依存性に基づき、異なるマクロタスクに分岐するマクロタスクを始端タスクとして特定する。また、自動並列化コンパイラ1は、該始端タスクを始点として順次実行される複数の一連の処理の全てにおいて共通して実行されるマクロタスクのうち、最初に実行されるものを終端タスクとして特定する。

0075

そして、自動並列化コンパイラ1は、特定した始端タスクと、該始端タスクを始点とする処理における終端タスクと、該始端タスクの実行後であって、該終端タスクの実行前に実行される全てのマクロタスクとを、1つのマクロタスクに融合させ(タスク融合)、S220に移行する。

0076

なお、マクロタスクの粒度を細かくするためには、S215での処理のように、始端タスクを始点として順次実行される複数の一連の処理の全てにおいて共通して実行されるマクロタスクのうち、最初に実行されるマクロタスクを終端タスクとして特定するのが好適である。しかし、これに限らず、これらのマクロタスクのうち、2番目以降に実行されるいずれか一つのマクロタスクを終端タスクとして特定しても良い。

0077

組み込みシステム(特に車載装置)向けの逐次プログラムは、ループ構造が少ないため、近細粒度並列化か粗粒度タスク並列化を適用することが考えられるが、実行オーバーヘッドを小さく抑えるため、自動並列化コンパイラ1は、粗粒度タスク並列化を適用する。

0078

また、逐次プログラムでは、各マクロタスクのコストは数10クロック程度であるが、自動並列化コンパイラ1によりダイナミックスケジューリングを行った場合には、通常数10から数100クロックのオーバーヘッドが生じる。このため、ダイナミックスケジューリングは、逐次プログラムには不向きである。

0079

しかしながら、条件分岐を持つマクロタスクは、その実行時に動的に分岐先が決定されるため、そのままでは、コンパイル時にプロセッサコアを割り当てるスタティックスケジューリングが適用できないという問題がある。

0080

そこで、自動並列化コンパイラ1は、タスク融合アルゴリズムにより、条件分岐をもつマクロタスクと、その分岐先のマクロタスクまでを1つの粗粒度タスク(Blockタスク)に融合するタスク融合を行う。タスク融合を行うことで、MFGは制御依存性が無い状態となり、スタティックスケジューリングが可能となる。

0081

S220では、自動並列化コンパイラ1は、タスク融合がなされたMFGに基づき、各マクロタスクの最早実行可能条件を解析し、MTGを生成する。そして、本処理を終了する。

0082

3.車載装置の構成について
次に、本実施形態の自動並列化コンパイラ1により生成された並列化プログラムにより動作する車載装置20の構成について説明する(図4参照)。無論、自動並列化コンパイラ1は、車載装置20に限らず、同様の構成を有する様々な電子装置を動作させる並列化プログラムを生成可能である。

0083

車載装置20は、マルチコアプロセッサ21,通信部22,センサ部23,入出力ポート24等を備える。
マルチコアプロセッサ21は、ROM21aと、RAM21bと、複数のPE21c,21d…等を有している。

0084

また、ROM21aは、自動並列化コンパイラ1により生成された並列化プログラム21a−1(バイナリデータ)が保存されている。マルチコアプロセッサ21は、並列化プログラム21a−1に従い動作し、車載装置20を統括制御する。

0085

また、RAM21bは、PE21c,21d…等によりアクセスされる部位である。
また、通信部22は、車内LAN等を介して接続された他のECUと通信を行う部位である。

0086

また、センサ部23は、制御対象等の状態を検出するための各種センサから構成される部位である。
また、入出力ポート24は、制御対象を制御するための各種信号送受信を行う部位である。

0087

[具体例について]
次に、本実施形態の自動並列化コンパイラ1により並列化プログラムを生成する処理の具体例について説明する。以下の説明において、処理A等といった記載がなされるが、これは、各種演算代入や分岐処理や関数コール等からなる一連の処理の記述を意味する。

0088

本具体例では、2種類の引数(“CSW1,2”)を参照する条件付コンパイルが行われる逐次プログラム300に基づき並列化プログラムが生成される(図5参照)。並列化プログラムは、2つのPE(第1,第2コア)を有するマルチコアプロセッサにて実行され、各マクロタスクは、これらのコアに割り当てられる。なお、図中、逐次プログラム300には“処理A〜E”の処理が含まれているが、これら以外の処理がさらに含まれていても良い。

0089

逐次プログラム300では、“処理B及びC”,“処理D及びE”が条件付記述となっている。条件コンパイルスイッチ301により、“処理B”と“処理C”のうちの一方がコンパイルの対象として選択され、条件コンパイルスイッチ302により、“処理D”と“処理E”のうちの一方がコンパイルの対象として選択される。具体的には、“CSW1=A”の場合には“処理B”が、“CSW1≠A”の場合には処理Cがコンパイルの対象として選択される。また、“CSW2=B”の場合には“処理D”が、“CSW2≠B”の場合には処理Eがコンパイルの対象として選択される。

0090

自動並列化コンパイラ1は、自動並列化処理のS100にて、逐次プログラム300の“処理B及びC”,“処理D及びE”の各々を条件付記述として特定する。
また、S105(ソフト構造解析処理)では、自動並列化コンパイラ1は、“処理A〜E”の各々を異なるマクロタスク(“A”〜“E”)に分割し、MTGを生成する。なお、マクロタスク“A”〜“E”は、それぞれ、“処理A〜E”に対応する。

0091

そして、S110において、自動並列化コンパイラ1は、生成されたMTGに基づきスタティックスケジューリングを行う。A〜Dパターン310〜313は、該スタティックスケジューリングにより生成される可能性のある割当情報を示している。

0092

スタティックスケジューリングにより、マクロタスクである“B,C”,“D,E”は、同じコアに割り当てられる。Aパターン310では、“B,C”は第1コアに、“D,E”は第2コアに割り当てられ、Bパターン311では、“B,C”は第2コアに、“D,E”は第1コアに割り当てられる。また、Cパターン312では、“B,C”及び“D,E”は第1コアに割り当てられ、Dパターン313では、“B,C”及び“D,E”は第2コアに割り当てられる。

0093

ここで、タスク融合により、1の条件付記述に基づく処理に対応するマクロタスクの一部と、該条件付記述の前後の記述に基づく処理に対応するマクロタスクが、1つのマクロタスクに融合される場合も想定される。このような場合、自動並列化コンパイラ1は、スタティックスケジューリングにおいて、融合されたマクロタスクと、該条件付記述に対応する残りのマクロタスクとを、1つのコアに割り当てる。

0094

より詳しく説明すると、上記具体例においては、タスク融合の結果、“A”,“B”が1のマクロタスク(マクロタスクA+B)に融合される可能性もある。このような場合には、“C”とマクロタスクA+Bとが同一のコアに割り当てられる。

0095

また、タスク融合により、1の条件付記述に基づく処理に対応するマクロタスクの一部と、該条件付記述の前後の条件付記述に基づく処理に対応するマクロタスクの一部(又は全部)が、1つのマクロタスクに融合される場合も想定される。このような場合においても、自動並列化コンパイラ1は、スタティックスケジューリングにおいて、融合されたマクロタスクと、上記条件付記述に対応する残りのマクロタスクとを、1つのコアに割り当てる。

0096

より詳しく説明すると、上記具体例においては、タスク融合の結果、“C”,“D”が1のマクロタスク(マクロタスクC+D)に融合される可能性もある。このような場合には、“B”と“E”とマクロタスクC+Dとが同一のコアに割り当てられる。また、上記具体例において、タスク融合の結果、“C”〜“E”が1のマクロタスク(マクロタスクC+D+E)に融合される可能性もある。このような場合には、“B”とマクロタスクC+D+Eとが同一のコアに割り当てられる。

0097

なお、本具体例における条件付記述(“処理B,C”や“処理D,E”)は、1の引数を参照する条件付コンパイルスイッチにより、コンパイル対象とするか否かが切り替えられる2つの部分からなる一連の記述として構成されている。しかしながら、これに限らず、条件付記述は、2以上の引数を参照する条件付コンパイルスイッチにより構成されていても良いし、コンパイル対象とするか否かが切り替えられる3以上の部分から構成されていても良い。

0098

[効果]
本実施形態の自動並列化コンパイラ1は、条件付記述を全て含んだ状態の逐次プログラムに基づきスタティックスケジューリング等を行い、並列化プログラムを生成する。そして、条件コンパイルスイッチの引数に応じて条件付記述の中からコンパイルの対象外となる部分を並列化プログラムから除去し、入力情報に対応する種別の並列化プログラムを生成する。

0099

スタティックスケジューリングが行われた段階の並列化プログラムでは、1の条件付記述に基づく各処理は、同一のPGに割り当てられる。このため、条件コンパイルスイッチの引数を設定することで仕向地等の異なる複数の種別の並列化プログラムが生成される場合であっても、各種別の並列化プログラムの共通性をより一層高めることができ、その結果、並列化プログラムの品質の維持や管理が容易になる。

0100

ここで、1の条件付記述に対応する各処理を異なるPGに割り当て可能(並列化可能)である場合には、これらの処理が同一のPGに割り当てることで、並列化プログラムの性能が低下してしまう。

0101

これに対し、自動並列化コンパイラ1は、対応する複数のマクロタスクを並列化可能な条件付記述を特定すると共に、並列化プログラムの性能を検証する。そして、並列化プログラムの性能が一定の水準に達しない場合には、対応するマクロタスクを並列化可能な条件付記述を示すレポートを生成することで、該条件付記述をユーザに報知する。

0102

これにより、本実施形態の自動並列化処理を行った結果、十分な性能の並列化プログラムを得られなかった場合には、ユーザは、上記レポートに基づき、並列化プログラムの性能を向上させるための対策を講じることができる。

0103

[他の実施形態]
以上、本発明の実施形態について説明したが、本発明は上記実施形態に限定されることなく、種々の形態を採り得る。

0104

(1)本実施形態の自動並列化処理では、並列化可能な条件付記述が特定される(S115)と共に、生成された並列化プログラムの性能が検証され(S120)、性能が一定の水準に達しない場合には、並列化可能な条件付記述を示すレポートが生成される(S130)。

0105

しかしながら、生成された並列化プログラムの性能に関わらず、並列化可能な条件付記述を示すレポートを生成するようにしても良い。このような場合であっても、ユーザは、該レポートに基づき、並列化プログラムの性能をさらに向上させるための対策を講じることができる。

0106

また、並列化可能な条件付記述を特定すること無く、生成された並列化プログラムの性能の検証結果を報知しても良い。こうすることにより、本実施形態の自動並列化処理によりどの程度の性能の並列化プログラムが得られたかを把握することができ、自動並列化コンパイラ1の利便性を高めることができる。

0107

(2)本実施形態の自動並列化コンパイラ1は、ソフト構造解析処理のS200にて逐次プログラムのインライン展開を行うと共に、S205にてローカル変数のリネームを行うが、これらの処理の双方または一方を行わない構成としても良い。このような場合であっても、逐次プログラムの構造によっては、同様の効果が得られる。

0108

(3)上記実施形態における1つの構成要素が有する機能を複数の構成要素として分散させたり、複数の構成要素が有する機能を1つの構成要素に統合させたりしても良い。また、上記実施形態の構成の少なくとも一部を、同様の機能を有する公知の構成に置き換えてもよい。また、上記実施形態の構成の一部を省略してもよい。また、上記実施形態の構成の少なくとも一部を、他の上記実施形態の構成に対して付加又は置換してもよい。なお、特許請求の範囲に記載した文言のみによって特定される技術思想に含まれるあらゆる態様が本発明の実施形態である。

0109

(4)上述した自動並列化コンパイラや自動並列化コンパイル装置の他、自動並列化コンパイラを記憶した媒体や、自動並列化コンパイラにより行われる処理に相当する方法等、種々の形態で本発明を実現することもできる。

0110

[特許請求の範囲との対応]
上記実施形態の説明で用いた用語と、特許請求の範囲の記載に用いた用語との対応を示す。

0111

自動並列化コンパイラ1が並列化コンパイラの一例に、車載装置20が電子装置の一例に相当する。
また、PGや、具体例におけるPE(第1,第2コア)が、プロセッサユニットの一例に相当する。

0112

また、自動並列化処理のS110が、スケジューリング手順,スケジューリング手段の一例に、S120が検証手順検証手段の一例に、S130が報知手順,報知手段の一例に相当する。

0113

また、ソフト構造解析処理のS210が、分割手順,分割手段の一例に、S220が、抽出手順,抽出手段の一例に相当する。
また、条件コンパイルスイッチの引数の値が、入力情報の一例に相当する。

0114

1…自動並列化コンパイラ、10…PC、11…ディスプレイ、12…HDD、13…CPU、14…ROM、15…RAM、16…入力装置、17…読取部、18…記憶媒体、20…車載装置、21…マルチコアプロセッサ、21a…ROM、21b…RAM、21c,21d…プロセッサエレメント(PE)、22…通信部、23…センサ部、24…入出力ポート。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ