C言語自動並列化のための並列構造解析と動的実行制御の実現

C言 語 自動並列化のための並列構造解析 と動的実行制御の実現

遠 山 純 也*1,甲 斐 宗 徳*2

Implementation of Parallelism Analysis and Dynamic Parallel Execution Control for C Programs

Sumiya TOHYAMA *', Munenori KAI * 2

ABSTRACT : In recent years, since it seems that speed up of single processor or single core has been going up to the utmost physical limit, parallel processing by multicore or multiprocessor becomes the mainstream to make the processing speed much higher. On the other hand, developing the effectively parallelized programs is very difficult for software developers. So, it is expected that automatic parallelization of existing sequential programs is accomplished. In this paper, we propose a parallelism analysis method to find parallel structures from original sequential programs, and implement its dynamic parallel execution method for automatically parallelized C programs.

Keywords : Parallel processing, Automatic parallelization, Dynamic execution control

(Received April 8, 2013) 1.は じ め に 2.C言 語 自 動 並 列 化 トラ ン ス レー タ の 概 要 近 年 の コ ン ピ ュー タ に お い て,物 理 的 な 問 題 か ら高 速 化 の 限 界 が 指 摘 され て きて い る。そ の解 決 策 と して,マ ル チ コア や 複 数 の プ ロセ ッサ に よ る並 列 処 理 を行 うこ と で 処 理 ス ピー ドを上 げ る方 法 が あ る。 しか し,並 列 処 理 に よ る処 理 効 果 の 高 い 並 列 実 行 可 能 な プ ロ グ ラム を作 成 す る こ とは プ ロ グ ラム 開 発者 に とっ て 困 難 な もの で あ る。 そ の た め,ど の よ うな 人 に も容 易 に 並 列 効 果 の 高 い 並 列 実 行 可 能 な プ ロ グ ラム を作 成 で き る よ うにす る こ とが 望 ま れ て い る。 そ こで 本研 究 で は 逐 次 の ユ ー ザ プ ロ グ ラ ム を読 み 込 み,元 の プ ロ グ ラム の 実 行 結 果 と変 わ らず 実 行 速 度 の 高 い並 列 プ ロ グ ラ ム に 自動 的 に書 き換 え る"C言 語 自動 並 列 化 トラ ンス レー タ"の 完 成 を 目指 し開 発 を行 っ て い る。 本 論 文 で は 特 に 並 列 実 行 で き るプ ロ グ ラム 構 造 を 特 定 し並 列 実 行 で き る形 式 に 変 更 す る並 列 構 造 解 析 と,解 析 され た 並 列 性 に 応 じて,複 数 の プ ロセ ッサ に 対 す るそ れ らの 処 理 の 割 り振 りを 実 行 時 に 決 定 す る動 的 実 行 制御 を 実 現 した の で 報 告 す る。 C言 語 自動 並 列 化 トラ ン ス レー一一タ とは,C言 語 で 記述 され た 逐 次 実行 可能 な ソー ス プ ロ グラ ム を 読 み 込 み プ ロ グ ラム 内 に 存在 す る 並列 性 を抽 出 し,変 換 を行 うこ とで 並 列 実 行 可 能 な コー ドを 出 力 す る。 ま た,並 列 効果 を高 め るた め に 並列 性 を抽 出 した 後 に,ル ー プ の分 割 や 実行 時 間 の解 析 を用 い た ス ケ ジュ ー リ ング な どの最 適 化 処理 を 行 うこ とで,よ り並列 効果 の 高 い コー ドを 生 成す る。 本研 究 で は分 散 メ モ リ環境 で 実行 で き る コー ドを 出 力 す る こ とで,よ り大 規模 な 並 列 実行 可 能 な 環塊 で利 用 で き る よ うに して い る。 ま た 並 列 実 行 可 能 な プ ロ グラ ム を 出 力す る こ とで,ユ ー ザ に よ る独 自の チ ュ ー ニ ング や コ ン パ イ ラに よる 最適 化 処 理 を施 す こ とが 可 能 とな る。 3.C言 語 自 動 並 列 化 トラ ン ス レー タ 処 理 手 順 *1:理 工 学 研 究 科 理 工 学 専 攻 博 ± 前 期 学 生 *2:理 工 学 研 究 科 理 工 学 専 攻 教 授(kai@st _{,seikei.acjp)} 3.1ソ ー ス プ ログ ラ ム の読 み 込 み, 中 間 デー タ構 造 の 作 成 各解 析 処 理 で は 共 通 の 中 間 デ ー タ構 造 を解 析 し解 析 結 果 を 更 新す る こ とに よ り,処 理 を進 め る。 そ の た め 最初 の 処理 と して,ソ ー ス プ ログ ラム を読 み 込 み,中 間 デ ー

成 践 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) タ構 造 を構 築 す る必 要 が あ る。 こ こで は 今 後 の 解 析 ス テ ップ で 必 要 とな る情 報 を保 存 す る必 要 が あ るた め,元 の ソー ス コー ドの 情 報 や,変 数 の 情 報,プ ロ グ ラム の 制 御 構 造 な ど を中 間 デ ー タ構 造 と して 保 存 す る。 ソー ス プ ロ グ ラム か ら構 文 木 を作 成 す る こ とで,読 み 込 ん だ ソー ス プ ロ グ ラム を 完 全 に 保 存 す る こ とが 出 来 る。 この 構 文 木 に 変 更 を加 え る こ とで プ ロ グ ラム の 変 更 を行 うこ と もで き る。 ま た,構 文 木 だ けで な く変 数 の 情 報 や プ ロ グ ラ ム の 制御 構 造 な どの 情 報 を保 存 し,後 の 解析 処 理 で 利 用 す る。 3.2並 列 性 の 抽 出 実行 結 果 を 変 え る こ とな く並 列 に 処 理 す るた め に は, 並 列 に 実 行 す る こ とが 可 能 な 部 分 を 探 す 必 要 が あ る。 そ れ ぞ れ の 処 理 に 依 存 関係 が あ る場 合,そ の ま ま で は 並 列 に 実行 す る こ とが で き な い(Figurel)。 並 列 実 行 に は変 数 を適 切 に通 信 しな くて は な らな い(フ ロー 依 存)。 そ の た め,並 列 実 行 す る処 理 内 で 必 要 とな る変数 に 関 す る情 報 を解析 す る必 要 が あ る。 ま た,処 理 を実行 す る際 に順 番 を入 れ 替 え る こ とが で きな い 場 合 が あ る。 並 列 実 行 を 行 うこ とで 処 理 を実行 す る順 番 が 入 れ 替 わ る こ とが あ る。 そ の た め,並 列 実行 す る際 に 出 力 な どの 処 理 の 順 番 を 変 え る こ との で きな い 処 理 は 逐 次 に 実行 しな くて は な らな い(逆 ・出力 依 存)。 また,並 列 実 行 で き な い プ ロ グ ラ ム を変 換 し,並 列 実行 で き る形 式 に 変 換 す る こ とで 並 列 性 を抽 出 す る こ と も行 う。 SllX=10 Lt .」IIZ-..〔ヘ

ノ

型

ISlX;10SlY;X 逆依存 へ 出力依存 、 S2X.、 。 ぐノIS2、X.2。 ソ Figure1依 存 の 種 類 3.3最 適 化 元 の ソー ス プ ロ グ ラム を 並 列 に 実行 す るだ けで は 高 い 並 列 効 果 は 望 む こ とが で きな い。 通信 の た め の オ ー バ ー ヘ ッ ドや 他 プ ロセ ス の 処 理 を待 つ こ とで発 生 す る遅 延, 並 列 実 行 す る処 理 に お け る実 行 時 間 の 違 い な どの 問 題 が あ る。 そ れ らの 問題 点 を解 消 す るた め に 最 適化 処 理 を 施 す 必 要 が あ る。 そ れ ぞ れ の 処 理 の 大 き さ を平 滑 化 す る こ とや,処 理 を ま とめ る こ とで 通信 を 減 らす こ とな ど,実 行 時 に よ り高 い 性 能 を 出 す た め の 変 換 を行 う。 3.4コ ー ド生 成 実行 で き る形 式 で 出 力 す る た め に はIEし い 文 法 で あ り, iEし い 処理 手順 に そ っ て 実行 で き る形 式 で 出 力 す る 必 要 が あ る。中間 デ ー タ構 造 か ら実 行 で き る形 式 へ と変 換 し, 並 列 実行 を行 うた め の処 理 を加 え て 出 力す る必 要 が あ る。 4.従 来 の 研 究 と の 比 較 4.1中 間 デー タ構 造 の 構 築 従来 ま で の研 究 で は 中 間 デ ー タ構 造 が解 析 を 行 うご と に構 造 が変 換 され て い た た め,解 析 ご とに独 自の デ ー タ 構 造 を解 析 して い た。 そ の た め類 似 した プ ログ ラム が 多 数 あ り保 守 性 や 拡 張性 が 乏 しい状 態 とな っ て い た。 そ の た め,本 研 究 で は統 一 され た 中 間 デ ー タ構 造 を 作成 す る と こ とか ら始 め た。 統 一 され た 中 間 デ ー タ構 造 を作 成す る こ とに よ り,処 理 間 で の解 析 結 果 の確 認 や,処 理 手順 の 見 直 し,新 た な処 理 を加 え る こ とな ど柔 軟 な 拡 張 を行 うこ とが で き る よ うに な る。 ま た 出 力 時 に の み 専用 の構 造 に変 換す る こ とに よ り複 数 の 出 力形 式 で 出 力 す る こ と が で き る よ うに す る。 そ うす る こ とに よ り,よ り効 率 の 良 い コー ドを 出 力す る こ とや 実行 結果 の 比 較 な ど研 究 開 発 が容 易 に な る(Figure2)。 逐次 プログラム

、

鶉

、唱 ト

構 造

.ノ

ロ

」

並列力 グ.ム

Figure2中 間 デ ー タ 構 造 4.2並 列 実行 モ デ ル の 改 良 従 来 の研 究 で は並 列 実行 可 能 な 処理 の割 り当 て を 静 的 に行 っ て い た。 解 析 結果 を も とに 処理 ご とに 実行 す るプ ロセ ッサ を 決 め,プ ログ ラム 中 に 埋 め 込 む こ とで 並 列 実 行 を行 っ て い た。 この方 法 は 余分 な処 理 手順 な どを含 ま ず 高速 に 実行 す る こ とが で き るが,こ の 手 法 で は 実 行す る 処理 の 大 き さや,並 列 実行 す る プ ロセ ス の状 態 な ど, プ ログ ラム の解 析 で は知 る こ との で き な い 実行 時 の 情報 な どに よ り正確 な割 り当 て を行 うこ とが で き な い。 そ の た め,き ち ん と処理 を均 等 に 分割 す る こ とが で きず 待 ち 時 間 な どの 遅延 の た め効 率 よ く実 行す る こ とが で き な い。 これ を解 決 す る た め に,実 行 時 に 並列 実行 を行 う処 理 を

各 プ ロ セ ス に 対 し 再 割 当 て を 行 う こ と で 高 速 化 を 図 る こ と が 出 来 る よ うに 変 更 し た(Figure3)。 実 行 状況 の通 知 / 処 理 の再 割 当て 管 理 プ ロセス

田

Figure3管 理 プ ロ セ ス の タ ス ク 処 理 再 割 当 て 5.並 列 化 処 理 5.1中 間 デ ー タ 構 造 の 作 成 中 間 デ ー タ構 造 の 作 成 で は,ま ず プ リプ ロセ ス 展 開 を 行 うこ とでincludeされ る標 準 ラ イ ブ ラ リの 検 査 を 行 うこ とや ソー一一ス プ ロ グ ラ ム をC言 語 の ソー ス フ ァ イ ル と して 構 文解 析 を行 うた め の 変 換 を行 う。標 準 ライ ブ ラ リの 検 査 は 必 要 な ライ ブ ラ リがincludeさ れ て い るか,ラ イ ブ ラ リを 追 加 した 際 に 宣 言 が 重複 しな い か を 調 べ る。 プ リプ ロセ ス 展 開 が行 わ れ た プ ロ グ ラム に 対 し構 文 解 析 を行 う。 構 文解 析 で は ま ず 字 句解 析 を行 い 入 力 され るプ ロ グ ラ ム を構 成 す る字 句 を 抽 出 す る。 抽 出 され た 字 句 が どの よ う な 意 味 を 持 つ構 文 規 則 で 構 成 され て い るの か を構 文 解 析 を行 うこ とで 判 定 す る。 構 文 解析 を行 うこ とで 各 構 文 規 則 を表 す構 文 木 を 作 成 し中 間 デ ー タ構 造 へ 保 存 す る。 こ の 構 文 木 は 入 力 され るプ ロ グ ラム 構 造 を保 存 して い るた め,こ の構 文 木 に 対 し解 析 す る こ とで 元 の プ ロ グ ラム 構 造 に 対 応 した解 析 処 理 を行 うこ とが 可 能 とな る。 5.2並 列 構 造 解 析 依 存 解析 で は タ ス ク内 の 依 存解 析 を行 い,そ の解 析 結 果 を 元 に タス ク グ ラ フ を構 築 す る こ とで タス ク間 の 依 存 関 係 を解析 す る。 5.3タ ス ク 内 の依 存 解 析 タス ク内 の 依 存解 析 で は タス ク内 で 使 用 され る変 数 を 依 存 情 報 と共 に 保 管 す る。 依 存 情 報 の 作 成 は 式 を 表 す構 文 木 を解析 し,式 の 演 算 子 か らオ ペ ラ ン ドへ の ア クセ ス を調 べ る。 依 存 情 報 は 識別 子 に対 す るread,writeの 情 報 や 識別 子 が 指 し示 す 変数 が保 存 され る(Figure4)。 ま た ポ イ ンタ解 析 を行 い ポ イ ン タ変 数 の 参 照 先 を 保 存 す る こ とで フ.ログ ラム 上 に 現 れ な い 依 存 情 報 を解 析 す る こ とが 可 能 とな る。 ま た複 数 の タス クが 内 包 され る複 合 タス ク の 場 合,す べ て の 内 包 され る タス クの 依 存 情 報 を 合 成 し た もの とす る こ とで 外 部 か ら複 合 タ ス ク を一 つ の タス ク と して 見 た 場合 に そ の タ ス ク に対 す る 依存 情報 を正 し く 保 存 で きる よ うに した。 ポ イ ンタ解 析 は プ ログ ラム の 実行 前 に プ ログ ラム ソー ス の解 析 を行 な っ て ポ イ ンタ 変数 が どの ロケ ー シ ョ ンに ア クセ スす るの か を解 析 す る ス テ ップ で あ る。 ポ イ ンタ 解 析 を行 わ な い 並列 性 解 析 の仕 様 で は,安 全 の た め ポ イ ン タ変 数 が含 ま れ る ス テ ー トメン トは 逐 次 処理 をす る。 これ は ポ イ ンタ 変数 が様 々 な ロケ ー シ ョン に ア クセ スす る 可 能 性 が あ る た め通 常 の 変 数 のread/write解析 を して 依 存 を調 べ るだ け で はデ ー タ 依存 を 見 抜 け な い か らで あ る。 そ こで ポ イ ン タ変 数 が どの ロケ ー シ ョン を ア クセ スす る の か を解 析 す るポ イ ン タ解 析 を 行 い,ア クセ ス ロケ ー シ ョン を 明確 に す る。 そ の結 果,そ れ ま で 逐 次 処理 しか で き な か っ た一 連 の ス テ ー トメ ン トも並列 性 が 見 つ か る 可 能性 が 出 て く る。

a[i]=b+10;

Figure4プ ロ グ ラ ム 例 に 対 す る 依 存 解 析 例 5.2.1タ ス ク グ ラ フの 構 築 タ ス ク間 の依 存解 析 で は並 列 実行 を 行 うの に 必 要 とな る 各 タ ス ク 間 の 通信 を解 析 す る。 各 タ ス ク 内 の 依存 情報 を使 用 し,そ れ ぞれ の タ ス ク 内 で使 用 され る変 数 を どの タ ス ク を行 っ た プ ロセ ス か ら受 け 取 る べ き か を解 析 す る。 逐 次 プ ログ ラム で の 変数 に は 最後 に変 数 に 対 し代入 を行 っ た ス テ ー トメ ン トで の値 が保 存 され て い る。そ のた め, 並 列 実行 を行 う場合 も同様 に,逐 次処 理 で 最後 に代 入 を 行 っ た ス テ ー トメ ン トを 表す タス クか ら値 を受 け取 る必 要 が あ る。 そ の た め,そ れ ぞ れ の タス ク間 に は そ の 変数 に 対す る依 存 が 存在 して い る。 タ ス ク 間 の 依存 が な い タ ス ク同 士 は 通信 を必 要 と しな い た め,そ れ ぞれ の タ ス ク は 並列 実行 を行 うこ とが 出来 る。 ま た,各 タ ス ク と各依 存 情報 か らタ ス クグ ラフ の構 築 を 行 う(Figure5)。 タス ク グラ フで は各 ノー ドが それ ぞれ の タ ス ク,各 依 存 情報 が エ ッジ とな っ て い る。

成 践 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) Figure5作 成 さ れ た タ ス ク グ ラ フ 6.最 適 化 6.1タ ス ク 粒 度 解 析 並 列 ・依 存 性 解 析 が 終 了 した 時 点 で は,タ ス ク の 初 期 粒 度 は ス テ ー トメ ン トレ ベ ル と し て い る た め,タ ス ク ス ケ ジ ュ ー リ ン グ の ス テ ッ プ で 受 け 取 る タ ス ク 数 は 元 の ソ ー ス コ ー ド中 の ス テ ー トメ ン ト数 に 近 い 数 と な っ て い る_。 そ の た め,ス テ ー トメ ン ト数 が 多 い ソ ー ス コ ー ド を 対 象 と し た 場 合,タ ス ク ス ケ ジ ュ ー リ ン グ に 要 す る 時 間 が 指 数 関 数 的 に 増 大 し て し ま う と い う問 題 が あ る 。 従 来 の 研 究 で は,ス テ ー トメ ン トご と の コ ス ト(変 数 の 個 数)と 依 存 強 度(通 信 に よ っ て 渡 さ な け れ ば な ら な い 変 数 の 個 数)を 考 慮 す る こ と に よ っ て タ ス ク 融 合 を 行 い,タ ス ク 数 を 減 少 す る 解 析 手 法 を 試 作 し た 。そ の 結 果, 全 体 の タ ス ク 数 を 減 少 さ せ,タ ス ク ス ケ ジ ュ ー リ ン グ に 要 す る 時 間 を 短 縮 す る こ と に 成 功 し た 。 本 研 究 で は,プ ロ セ ッ サ 数 に 基 づ く 最 大 並 列 度 を 考 慮 す る た め に,同 時 に 並 列 実 行 可 能 な タ ス ク 同 ± の 融 合 (Parallelタ ス ク 融 合 。 以 下,P融 合 。)は タ ス ク の コ ス ト を 使 用 し て 融 合 を 行 う。 ま た,タ ス ク グ ラ フ に お け る 同 一 エ ッ ジ 上 の タ ス ク 同 ± の 融 合(Sequentialタ ス ク 融 合_。 以 下,S融 合 。)に つ い て は タ ス ク の 依 存 強 度 を 使 用 し て 融 合 を 行 う。 以 上 の2つ の 融 合 を 組 み 合 わ せ た 手 法 を 提 案 す る 。 こ の 提 案 に よ っ て,こ れ ま で 融 合 の 対 象 と し て い な か っ た タ ス ク に つ い て も 融 合 を 可 能 に す る こ と が で き,タ ス ク 数 の 更 な る 減 少 が 期 待 で き る 。 6.2ル ー プ リ ス トラ ク チ ャ リ ン グ ー 般 的 に ,プ ロ グ ラ ム の 実 行 時 間 の ほ と ん ど は ル ー プ 中 で 行 わ れ る 何 ら か の 処 理 に よ っ て 消 費 さ れ て い る 。 し た が っ て,自 動 並 列 化 に 大 き く影 響 し て い る の は 主 に ル ー プ で あ る と 考 え ら れ る 。 従 来 の 研 究 で は,元 のC言 語 で 記 述 さ れ た ソ ー一一ス コ ー ド 中 のfor文 に 対 し て,C言 語 自 動 並 列 化 トラ ン ス レー一一タ の 並列 性 解 析 部 で,並 列 性 解 析 を行 い,解 析 の 結果 に よ っ てル ー プ の 再構 築 が元 の ソー ス コー ドに 対 して行 われ て い た。 本 研 究 で は,新 し く解 析 用 の 「構 文木 構 造 」 が つ く られ た。 本 研 究 で は,ル ー プ リス トラ クチ ャ リ ング の 対象 をfor文 とす る。一 見 並 列 性 の見 えな いfor文に 対 し て構 文 木構 造 を利 用 して 並列 性 解 析 を行 い,そ の解 析 の 結 果 ル ー プ の 再構 築 が 可 能 な らば ル ー プ リス トラク チ ャ リ ング とい う手 法 を 用 い て,構 文 木構 造 に 対 してル ー プ の 再構 築 を 行 う。 構 文木 構 造 を用 い て のル ー プ の 並 列性 解 析,ル ー プ リス トラク チ ャ リン グの 実装,ル ー プ の 再 構 築 に 関 して の構 文 木構 造 の 変 更 を行 うこ とで,最 終 的 に 並列 化 コー ド生成 後,そ の 並列 化 コー ドを 実行 す る際 の 実行 時 間 の短 縮 を狙 う。 6.3通 信 の 最 適 化 逐 次 で 書 か れ た コ ー ドを 実 行 時 間 短 縮 の た め に 自 動 並 列 化 を 行 う場 合,自 動 抽 出 さ れ た タ ス ク が プ ロ セ ッ サ に 割 り 当 て ら れ る 。 各 プ ロ セ ッ サ は そ の タ ス ク処 理 を 行 う た め に 必 要 な 情 報 の 受 け 渡 し,即 ち 通 信 を 行 わ な け れ ば な ら な い 。 こ の 通 信 はMPI(MessagePassingInterface)と い う並 列 化 ラ イ ブ ラ リ を 用 い て 行 う。 先 行,後 続 関 係 に あ る2つ の タ ス ク 間 で デ ー一一タ 依 存 関 係 に よ り送 受 信 し な け れ ば な ら な い デ ー タ が 複 数 あ る 場 合,こ れ ま で の 研 究 で は こ の 情 報 の 受 け 渡 し を1対1プ ロ セ ッ サ 間 通 信 を 複 数 回 行 う こ と で 行 っ て い た 。 ま た,こ の1対1通 信 で は 通 信 を 行 うプ ロ セ ッ サ の 分 だ け セ ッ トア ッ プ(通 信 経 路 確 保)を 必 要 と す る 。 本 研 究 で は,よ り 実 行 時 間 の 高 速 化 を 図 る た め に,プ ロ セ ッ サ 間 の 通 信 部 分 に 着 目 し,MPIの ラ イ ブ ラ リ に 用 意 され て い る,MPIBcastに も適 応 させ る こ と を 目 的 と す る 。 ま た 複 数 デ ー タ の 送 受 信 を 行 わ な く て は な ら な い 場 合 も構 造 体 を 用 い て1つ に ま と め ブn-一 ドキ ャ ス ト通 信 に よ っ て 一 括 で デ ー タ の 送 受 信 を 完 了 させ る こ と が 可 能 と な る 。 し か し 全 て の1対1通 信 を ブ ロ ー ドキ ャ ス トに 置 き換 え る の で は な く1対1通 信 と ブ ロ ー ドキ ャ ス トの 使 い 分 け を 行 う こ と とす る。 こ の ブ ロ ー ドキ ャ ス ト命 令 を 利 用 す る こ と に よ り通 信 時 間 の 短 縮 の メ リ ッ トが 見 込 め,最 終 的 に は プ ロ グ ラ ム 実 行 時 間 の 短 縮 に つ な が る と 考 え ら れ る 。 7.実 行 制 御 7.1処 理 の 関 数 化 並列 実行 を行 うた め に は 各 プ ロセ ス に任 意 の 処理 を 実 行 させ る必 要 が あ る。 しか し,他 の プ ロセ ス に任 意 の処

理 を 実 行 させ る こ とは 難 しい 。 そ れ を実 現 させ るた め に 並 列化 トラ ンス レー タで は 各 処 理 を 関 数 に して 切 り出 す (Figure6)。 関 数 に 切 り出 した 処 理 を 実 行 させ る際 に は 依 存 す る変 数 の 値 が 必 要 とな る。 しか し,元 の プ ロ グ ラ ムか ら切 り だ され て い るた め 局 所 変 数 を使 用 す る こ とが で き な い 。 そ の た め グ ロー バ ル 変数 を使 用 し,各 処 理 間 で 変 数 の 受 け 渡 しを行 う。 ま た,異 な るプ ロセ ス で 実 行 され た 処 理 に 依 存 す る変数 を あ る場 合,通 信 を行 うこ とで 必 要 な 変 数 を 受 け 取 る こ とが 出 来 る。 そ の た め,各 関 数 は 必 要 な 変 数 を受 け取 る受信,実 際 の 処 理 を行 う実 行,代 入 され た 値 を次 の 依 存 す る処 理 に 送 る送 信 の3つ の 処 理 か ら構 成 され る。 列 実行 させ る際 に,他 の プ ロセ ス に任 意 の 処理 を 実行 さ せ るた め に は 関 数 テ ー ブ ル の イ ン デ ッ クス を通 信 に よ り 渡 す必 要 が あ る た め,通 信 の オ ー バ ー ヘ ッ ドが発 生 して しま う。 そ の た め,処 理 を 実 行 前 の段 階 で 分散 させ る こ とで 次 に行 う処 理 を 決 め て お く こ とで よ り高速 に 実行 で き る よ うに す る。 こ こで は,タ ス クの 依存 関係 や処 理 時 間 を 求 め た 実行 時 間解 析 の結 果 を 用 い タ ス クス ケ ジ ュー リ ング に か け る こ とで よ り最 適 な 初期 分散 を 求 め る。 初 期 分散 され た タ ス ク を順 次処 理す る こ とで 元 の プ ロ グラ ム を 並 列 実行 す る こ とが 可能 に な る。

/

＼

だ

/ ＼ ー 、  へ ム 》 新しい関数

⇒)

  新しい関数 → 、.ノ Figure6タ ス ク の 関 数 化 切 りだ さ れ た 関 数 の 関 数 ポ イ ン タ を 配 列 に 保 存 し 関 数 テ ー ブ ル を 作 成 す る 。 全 フ.ロセ ス は 同 一 の 関 数 テ ー ブ ル を 持 ち,保 存 さ れ た 処 理 を 順 次 実 行 す る 。 こ の よ うに す る こ と で 他 の プ ロ セ ス に 任 意 の 処 理 を 実 行 さ せ た い 場 合, 関 数 テ ー ブ ル の イ ン デ ッ ク ス を 渡 す こ と で 任 意 の 処 理 を 行 わ せ る こ と が で き る(Figure7)。 void(*function _table口)0; 関 数 テ ー ブ ル 関 数 化 され たタス ク プ ロ セ スfunction-table[4]O; イ ン デ ック ス に よ るア ク セ ス Figure7タ ス ク の 保 存 と 呼 び 出 し 7.2処 理 の 初 期 分 散 プ ロ グ ラム を並 列 実行 す る際 に よ り高 速 に 動 作 させ る た め に は,適 切 に 処 理 を並 列 実 行 させ る必 要 が あ る。 並 7.3タ ス ク 管 理 初期 分散 は元 の プ ログ ラム を静 的 に解 析 した 結果 か ら 求 め る た め,プ ログ ラム解 析 で は 実行 時 の タス クの 正確 な 処理 時 間 を求 め る こ とが で きな い。 解 析 時 に割 り 当て られ た 処理 を並 列 に 実行 す る だ け で は 高速 化 が 望 め な い 場 合 が あ る。 そ の た め,実 行 時 に 再割 当 て を行 うこ とで よ り高 速 に 実行 す る こ とが 可 能 に な る と期 待 され る。 各 プ ロセ ス が割 り 当て られ た処 理 を 実効 す る 際 に は必 要 な 変 数 を 受 け 取 る 必 要 が あ り,依 存 す る タ ス クが 終 了 して い な くて は な らな い。 依 存す るタ ス ク が処 理 中 の場 合, 他 の依 存 しな い タス クを 先 に 実行 す る こ とや,他 の プ ロ セ ス に割 り当 て られ て い る実行 可 能 な タ ス クを 先 に 実行 す る こ とで 処理 時 間 の無 駄 を 削減 し高 速化 を 図 る。 それ らの 実行 時 の タ ス ク を 管 理す るた め に,そ れ ぞ れ割 り当 て られ た タ ス ク を タ ス ク テ ー ブル と して 管 理す る。 7.3.1タ ス ク テ ー ブル タ ス クテ ー ブ ル に は依 存す るタ ス ク,実 行す るプ ロセ ス,タ ス ク の 実行 状 態 が保 存 され る。 依存 す る タス クは 依 存す る変 数 を どの タ ス クを 実行 した プ ロセ ス か ら受 け 取 る必 要 が あ る の か を保 管 して い る(Tablel)。 実行 す る プ ロセ ス は初 期 分 散 で 割 り 当 て られ た プ ロ セ ス のIDが 最 初 に保 管 され る。 そ して,実 行 時 に 動 的 再割 当 て が行 わ れ た 際 に再 割 り当 て され た プ ロセ ス のIDが 再 登 録 さ れ る。 タ ス クの 実行 状態 は タ ス ク が 実行 前,実 行 中,完 了 の どの状 態 な の か,実 行 可 能 か,依 存す るタ ス ク が 終 了 して い な い た め に 実行 可能 に な っ て い な い の か な どの 情 報 を保 管 す る。 依 存す る変 数 が な い 場合 な どは初 期 状 態 が 実 行 可 能 とな る。 動 的 再割 当 て を す る 際 に 自身 の持 つ タ ス クが 完 了 した 場合 や,依 存 す る タ ス クが 完 了 して い な い た め 実行 で き な い 場合 な どに他 の プ ロセ ス の タス ク を 実行 す る。 そ の 際 に他 の プ ロセ ス の 実行 可 能 タ ス ク を優 先 的 に 実行 す る こ とです ぐに 次 の タ ス クを 実行 で き る。

成 踵 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) Table1タ ス ク 管 理 表 の 例

層1D

引・濫融_繍 覧▼ 一 一 7,F 4■1一 0 0 0.1 1 0 0 4 「 ∠ 3 一 1 2 1 2 -3 4τ 「   1 0 2.3 4.5 5 た(Figure8)。 各 実行 プ ロセ ス は 処 理 の 実 行 状 況 を 管 理 プ ロセ ス に 通知 し,管 理 プ ロセ ス は伝 え られ た 情報 を元 に 再割 当 て を行 い,実 行 プ ロセ ス に再 割 当て を通 知 す る。 この よ うに す る こ とで,各 フ.ロセ ス が 実行 状況 を送 信 す る 際 に 受信 プ ロセ ス が処 理 の 実行 中 で な くな る た め,同 期 が発 生 しな い。 9.並 列 実 行 可 能 な プ ログ ラ ム の 出 力 7.4通 信 の 作 成 並 列 プ ロ グ ラム を実行 す るた め に は 通信 を行 うプ ロ グ ラム の 作 成 を 行 う必 要 が あ る。 通 信 の プ ロ グ ラム は タ ス ク グ ラ フの 全 て の ノー ドに 対 し,そ れ ぞ れ 作 成 す る。 タ ス ク グ ラ フ内 の エ ッ ジは,受 信 タス ク,送 信 タス ク,通 信 情 報 の3つ の 情 報 を 持 っ て い るた め,そ れ ぞ れ の エ ッ ジ に 対 し個 別 のIDを 割 り振 る。IDを 割 り振 られ た エ ッ ジ を通信 の 表 の イ ンデ ッ クス と して 使 用 す る。 そ れ ぞ れ の 通 信 に は 送 信 元 タス クか ら送 られ る情 報 の うち の 受信 タ ス クで 必 要 とな るデ ー タを コ ピー す る必 要 が あ るた め,通 信 プ ロ グ ラム 内 で 通信 が 完 了 した 後,自 身 の 内 部 デ ー タに 変 数 を退避 させ るフ.ログ ラ ムを 作 成 す る必 要 が あ る。 対 比 させ る変 数 をデ ー タ に登 録 して お き コー ドの 出 力 時 に プ ロ グ ラム を構 築 す る。 8.実 行 時 再 割 当 て 実 行 時 に タス クの 再 割 当 て を行 うた め に は 実 行 時 に各 プ ロセ ス の 実 行 状 況 を管 理 す る必 要 が あ る。 そ の た めに は 各 プ ロセ ス は 通 信 を行 い 実行 時 の 情 報 を 共 有 しな くて は な らな い。 しか し,通 信 を行 お うとす る際 に 通 信 を行 う フ.ロセ ス が タ ス クの 実行 中 で は 通 信 を行 うこ とが で き な い 。 そ の た め,実 行 中 に 各 フ.ロセ ス 同 ± が 通 信 を 行 うこ とは 現 実 的 で は な くな る。 そ の 問 題 を解 決 す るた めに 各 プ ロセ ス の 実行 状 況 を 管 理 す るた め の 管 理 プ ロセ ス を 用 意 し,そ の 他 の 処 理 を行 うプ ロセ ス を実行 プ ロセ ス と し 中 間 デ ー タ構 造 で は並 列化 され た構 造 に な っ て い な い た め,中 間 デ ー タ構 造 を 出 力 用 の デ ー タ構 造 に 変換 し出 力 す る 必 要 が あ る。 出 力 用 の デ ー タ構 造 と中 間 デ ー タ構 造 を分 離す る こ とに よ り,一 つ の 出 力 用 の デ ー タ構 造 か ら複 数 の 出 カ プ ログ ラム を作 成す る こ とが 出来 る。 そ の た め,新 しい並 列 実行 の モ デ ルや 出 カ プ ロ グラ ム の 改 良 な どの 開発 を続 け て い く こ とが 出 来 る。 ま た,出 力 す る プ ログ ラム は元 の プ ログ ラム か ら大 き く変 更 され て しま うた め 改 良 す る こ とが難 し くな る とい う問題 点 が あ る。 この 問題 点 を解 決す るた め に は,元 の プ ロ グラ ム構 造 を 大 き く壊 す こ との な い よ う,大 き な変 更 を加 え ず,並 列 実行 で き る 処理 を分 離す る こ とで 目標 を 達 成す る こ とを 目指す 。 9.1実 行 結 果 intmv _{_work} {unsignedinttime) { returntime; } intmainO { inta,b; a=my _{_work{1);} bニmy _work(2}; printf〔1伽%d¥n"、a+b}; returnO; } Figure9入 カ プ ロ グ ラ ム 例 更 新 レ タスク 管 理表 参 照 ・更 新 実行時惰報 Ψ A参 照 再割当 保存7 アルゴリズム 管理プロセス ー 実行時情報 タスク実行状況 ・各実 行 プロセス 静 的 4ス ケジ ュー リング デ ータ 0

○

a 1 2 Figure10作 成 さ れ る タ ス ク グ ラ フ Figure8実 行 時 の 情 報 の 流 れ

Figure9が サ ンプ ル と して 入 力 され る フ ァイ ル に な る。 この フ ァイ ル で は2つ の 変 数 に 初 期 値 を 代 入 し,そ の 合 計 を出 力 す る簡 単 な 例 に な っ て い る。 この 例 で は 処 理 が 少 な く並 列 効 果 は 見 込 め な い が,並 列 実行 が 正 確 に行 わ れ て い る こ と を示 す た め に この 例 を使 用 した 。 この プ ロ グ ラム で は 変数aへ の代 入 と,変 数bへ の 代 入 部 分 は並 列 実 行 可 能 な る。 しか し,合 計 を 出 力 す る箇 所 で は 通 信 を 行 い,適 切 な 通 信 を行 わ な くて は な らな い 。 この プ ロ グ ラム を入 力 し構 築 され る タス ク グ ラ フがFigurelOに な る。 この 図 の ダ ミー タス ク3の 下 に あ る2つ の タス クが 変 数 の 代 入 とな っ て い る。 この2つ の タ ス クの 間 にエ ッジ は な く,並 列 実行 す る こ とが 可 能 に な っ て い る こ とが わ か る。 更 に 下 に あ る2番 の タス クが 合 計 を出 力 す る タス ク とな っ て い て,代 入 を行 う2つ の タ ス クか ら変 数 を通 信 しな くて は 行 けな い こ とを 示 して い る。 lntmV _work(unsignedinttime){ return加me; } voldacpt_funcO(){ call _recv(O); commdataO.a=mV_work〔1); calLsend⊂O}; } vOldacpt _funcl(,{ call_recv(1); comm.datal.b;my _work(2); calLsend(1); } voidacpt _func20{ call _{_recv(2);} printf("%d¥n'㌧comm.data2.a+comm.data2.b); calLsend(2); } Figure11出 力 さ れ る 関 数 unionComm{ struct{ inta; }dataO; struct{ intb; }data1; struct{ inta; intb; }data2; }comm; Figure12通 信 用 の デ ー タ 構 造 FigurelOの タ ス ク グ ラ フ か ら 並 列 プ ロ グ ラ ム を 出 力 す る と,ま ず そ れ ぞ れ の タ ス ク が 関 数 化 さ れ たFigurellの タ ス ク リス トが 出 力 さ れ る 。 こ の 関 数 で は 使 用 さ れ る 局 所 変 数 が 別 の 構 造 体 と な っ て い る 。 そ の 構 造 体 を 示 し た も の がFigurel2の 構 造 体 で あ る 。 こ れ は 各 関 数 間 で の デ ー タ の 受 け 渡 し や_{,他 の プ ロ セ ス と の 通 信 に 使 わ れ る デ} ー タ構 造 に な っ て い る_。 voidstatic _{_workO} { inti; for(i=0;iくTaskTableSize;++i){ if(my _rankニ=task_table[i】11D function _{_table[i](》;} } } Figure13タ ス ク の 実 行 Figurellの よ う な タ ス ク リ ス ト を 実 行 す る 部 分 が Figurel3で 示 す タ ス ク の 実 行 プ ロ グ ラ ム に な る。 こ れ ら の プ ロ グ ラ ム を コ ン パ イ ル す る こ と で 並 列 に 正 し く 実 行 す る こ と が で き た 。 9.2今 後 の課 題 とま とめ 本 研 究 で は,中 間 デ ー タ構 造 を 作成 し,並 列 性 解 析 を 行 うこ とで 並列 性 の抽 出 が 可 能 とな り,並 列 プ ログ ラム を 生成 す る こ とで逐 次 プ ログ ラム と同様 の 出 力 を得 る こ とが で き た。 しか し,こ こで は最 適 化 処理 が行 われ て い な い た め に,多 くの プ ロ グラ ム で 速度 の 向 上 は 見 られ な か っ た。 そ の た め,今 後 の課 題 は並 列 実 行 が可 能 とな っ たの で, よ り高 速 に 動作 す る プ ロ グラ ム を 出 力 す る こ とに な る。 そ の た め に は,各 種 最適 化 を行 うこ とや,実 行 制御 の 改 善 を行 わ な くて は な らな い。 最適 化や,実 行 制 御 の 改 善 の た め に は タス クに か か る処 理 時 間 の 算 出 や,タ ス クの 粒 度 を 大 き くす る こ とで,よ り効 率 良 く実行 を行 うこ と が 必 要 に な る。

参考文献

[1]A.V.エ イ ホ,R.セ シ イ(原 田 賢 一 訳):「 コ ンパ イ ラー 原 理 ・技 法 ・ツ ー ル 」,サ イ エ ン ス 社,2009 [2]中 田 育 男:「 コ ン パ イ ラ の 構 成 と最 適 化 第2版 」,朝 倉 書 店,2009 [3]ParrTerence(伊 藤 真 浩 訳):「 言 語 実 装 パ タ ー ン コ ン パ イ ラ 技 術 に よ る テ キ ス ト処 理 か ら 言 語 実 装 ま で 」,オ ラ イ リー ジ ャ パ ン,2011 [4]蒲 野 茂 幸:「SIMD最 適 化 向 け ソ ー ス コ ー一一ド レ ベ ル で の コ ー ド変 形 」,東京 工 業 大 学 大 学 院 情 報 理 工 学 研 究 科 修 ± 論 文,2008 [5]山 名 淳 司:「GPCに よ る 導 出 原 理 の 最 適 化 」,早 稲 田 大 学 理 工 学 研 究 科 修 ± 論 文,2005 [6]松 本 真 樹,片 野 聡,佐 々 木 敬 秦,大 野 和 彦,近 藤 利 夫,中 島 浩:「 ヘ テ ロ型 大 規 模 並 列 環 境 の 階 層 型 タ ス

成 践 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) ク ス ケ ジ ュ ー リ ン グ の 提 案 と 評 価 」,情報 処 理 学 会 論 文 誌 プ1コ グ ラ ミ ン グ(PRO),2(1),1-17,Jan.2009 [7]美 濃 本 一 浩:「C言 語 自 動 並 列 化 トラ ン ス レー一一タ の 開 発 」,成膜 大 学 工 学 部 工 学 研 究 科 情 報 処 理 専 攻 修 士 論 文,2005 [8]國 枝 義 敏 津 田 孝 夫:「 自 動 ベ ク トル 化 コ ン パ イ ラ の た め の 制 御 関 係 解 析 法 」,情 報 処 理 学 会 論 文 誌,30(9), ll64-ll74,Sep.1989