C言 語
一 タス ク粒 度 に
自動 並 列 化 トラ ンス レー タの 開 発
着 目 した コ ー ド リス トラ ク チ ャ リン グ 手 法 の 実 現 一
近 藤
竜 也*1,甲
斐
宗 徳*2
ImplementationofParallelCodeGeneratorunderStaticExecutionControlandProposalof
PerformanceTuningToolforAutomaticParallelizingTranslatorforCPrograms
TatsuyaKONDO*1,MunenoriKAI*2
ABSTRACT:InourautomaticparallelizingtranslatorfbrsequentialCprogramswithMPI,asetofall
statementsinablockscopeisdefinedasacompoundtask.Inthispaper,atfirst,weimplementeda
parallelismanalyzerfbrtheinnerlevelsofhierarchyofscopesinanycompoundtask.Byusingthisanalyzer,
weanalyzedsingleloopsandnestedloopswhoseprocessingtimemaytakethemostoftotalprocessing
timeofaprogramingeneral.Althoughitseemsthataloophasnoparallelismataglance,theloopmaybe
restructuredtohaveparallelismbyeliminatingdatadependencies,calledloopdistribution.Inaddition,in
ordertoreducemoreprocessingtimeoffbr-loops,acoderestmctUringmethod,thathasextractthe
efficiencyofcachememory,hasbeenimplemented.Theseimplementationresultinreducingparallel
processingtimeremarkably.
Keywords:Parallelizingtranslator,Codegenerator,Parallelprocessing,Looprestructuring
(ReceivedMay27,2017)
1.は じ め に2.C言
語 自 動 並 列 化 トラ ン ス レー タ
プ ログ ラム の 持 つ 並 列 性 を 自動 検 出 し最 小 実 行 時 間 で
並 列 処 理 す るた め に は 、 タ ス クス ケ ジ ュー リン グ を行 う
必 要 が あ る。 そ して 無 駄 な 通 信 オ ー バ ヘ ッ ドを減 ら し最
適 な タ ス ク ス ケ ジ ュー リン グ結 果 をで き る限 り短 時 間 で
得 るた め に は 、 タ ス クを 適 切 な 粒 度 に ま と め上 げ て お く
必 要 が あ る。
タ ス クの適 切 な粒 度 を 求 め るた め に は 、 プ ロ グ ラム の
全 て の 階 層構 造 を解 析 して 、 コー ドの リス トラ クチ ャ リ
ング を行 い な が らタ ス ク粒 度 を調 整 して 決 定 して い く必
要 が あ る。
本研 究 で は 、 そ の た め の ソー ス コー ドの リス トラ クチ
ャ リン グ手 法 を 実 現 す る こ とを 目的 とす る。
*1:理 工 学 専 攻 博 士 前 期 課 程 学 生 *2:理 工 学 研 究 科 理 工 学 専 攻 教 授(kai@st .seikei.ac.jp)ソフ トウェ ア研 究 室 で 開発 中の 自動 並 列 化 トラ ンス レ
ー タ田(以 下
、 トラ ンス レー タ)は 、C言 語 で 記 述 され た
逐 次 実行 可能 な ソー ス プ ロ グ ラム を 読 み 込 み 、 プ ロ グ ラ
ム に 内 在 す る並 列 性 を 自動 抽 出 し、MPIに よ る 並 列 実 行
用 コー ドを埋 め 込 む こ とで 並 列 実行 可 能 な コー ドへ 変 換
し、 出力 す る こ とを 目指 して い る。
2.1並
列 化 トラ ンス レー タ の構 造
図2.1は
トラ ンス レー タの 処 理 手順 を表 して い る。 初
期 作 業 と して入 力 され た逐 次 プ ロ グ ラム か ら 中間 デ ー タ
構 造 を作 成 し、初 期 状 態 で は ス テ ー トメ ン トレベ ル と し
て い る タ ス ク 間 の デ ー タ依 存解 析 と制御 依 存解 析 に よ り
並 列 性 を抽 出す る。 この 中 間 デ ー タ構 造 に は 、 元 の ソー
ス コー ドと等 価 で あ るタ ス クの構 文木 構 造 、 ま た 並 列 化
に お い て使 用 され るデ ー タ依 存 関係 な ど様 々 な 情 報 が 格
納 され る。
中盤 の 作 業 と して 、 タ ス クの 実 行 時 間 と依 存 関 係 を考
慮 し、 タ ス ク の 適 切 な粒 度 を求 め る タス ク粒 度 解 析 を行
う。 トラ ンス レー タ で は 、 内 部 で タス クス ケ ジ ュー リン
グ を 実行 し、 タ ス クに 対 して プ ロセ ッサ の 割 り当て を静
的 に行 う。 一 般 的 に 細粒 度 タス クに お い て は タス ク にか
か る実行 時 間 よ りも通 信 に か か る処 理 時 間 の 方 が 大 きい
とい う場 合 が 多 い 。 この よ うな 無 駄 な 通 信 を削 除 す るた
め に 、 タ ス ク粒 度解 析 で は タス クの粒 度 をス テ ー トメ ン
トレベ ル で あ る初 期粒 度 か ら粗 粒 度 へ 調 整 す る。 ま た タ
ス ク の総 数 を減 らす こ とで 強NP困 難 な 組 合 せ 最 適 化 問
題 で あ るタ ス クス ケ ジ ュー リン グに か か る時 間 を削 減 す
る こ とが 可 能 とな る。
最 終 段 階 で は 、 各 解 析 ・変 換 処 理 が 完 了 した 中間 デ ー
タ構 造 か ら並 列 プ ロ グ ラム を 自動 生 成 し出 力 す る。
タスクス ケジュー リン グ勿
→:生
成
→:読
み 込み
→:書
き込 み
図2.1ト ラ ン ス レー タ 処 理 手 順 2.2タ ス ク に つ い て ト ラ ン ス レ ー タ に 読 み 込 ま れ た ソ ー ス コ ー ドは 、 解 析 器 に よ っ て タ ス ク と 呼 ば れ る コ ー ドセ グ メ ン トに 分 解 さ れ る。 タ ス ク の 初 期 粒 度 は 一 部 を 除 き ス テ ー トメ ン ト レ ベ ル で あ る。 ス テ ー トメ ン ト レ ベ ル の タ ス ク 以 外 に も 、 ブ ロ ッ ク ス コ ー プ と制 御 フ ロ ー 文 を 持 つifタ ス ク 、forタ ス ク や 、ユ ー ザ 定 義 関 数 、main関 数 を 示 すfUnctionタ ス ク と い っ た タ ス ク を マ ク ロ タ ス ク と し て 定 義 す る 。 2.3デ ー タ の 依 存 関 係 デ ー タ の 依 存 関 係 は 、 プ ロ グ ラ ム を 並 列 化 す る 妨 げ と な る も の で あ る 。 デ ー タ の 依 存 関 係 に は 「フ ロ ー 依 存 」 「逆 依 存 」 「出 力 依 存 」 の3種 類 が あ る 。 フ ロ ー 依 存 と は 、先 行 す る ス テ ー トメ ン トでWriteさ れ て い る 変 数 が そ の 後 続 の ス テ ー トメ ン トでReadさ れ て い る 場 合 に 発 生 す る 。 逆 依 存 と は 、 先 行 ス テ ー トメ ン ト でReadさ れ て い る 変 数 が そ の 後 続 ス テ ー ト メ ン トで Writeさ れ て い る 場 合 に 発 生 す る 。 出 力 依 存 と は 、 あ る ステ ー トメ ン トに お い て 並 べ 替 えを行 うこ とに よっ て 最 終
的 に そ の変 数 に期 待 す る値 が 変 わ っ て しま う場 合 に 起 こ
る。 これ らの依 存 関係 を 図2.2に 示 す 。
1; b=a+2; 3; 図2.2デ ー タ 依 存 関 係 の 例 2.4タ ス ク グ ラ フ に つ い て タ ス ク 問 に は 依 存 関 係 に 基 づ く 先 行 制 約 が あ り、 そ の 関 係 を 図2.3の よ うに 表 現 し た 有 向 グ ラ フ を タ ス ク グ ラ フ と 呼 ぶ 。 タ ス ク は ノ ー ドで 、 先 行 ・後 続 関 係 は 有 向 エ ッ ジ で 表 す 。 図2.3タ ス ク グ ラ フ の 例2.5タ
ス ク粒 度 解 析 に つ い て
トラ ン ス レー タ で は 、依 存 ・並列 性 解 析 が行 わ れ た 時
点 で タ ス ク の初 期 粒 度 は ス テ ー トメ ン トレベ ル で あ る。
つ ま り、存 在 す るタ ス ク数 は 元 の ソー ス コー ドの ス テ ー
トメ ン ト数 に相 当す る。 そ の た め 大 規模 な ソー ス コー ド
に な る ほ どタ ス ク数 は増 え 、 タス クス ケ ジ ュー リン グ を
行 う際 に 、 そ の 求解 時 間 は タ ス ク数 に 対 して 指数 関数 的
に増 大す る。 ま た 、初 期 粒 度 の タス ク グ ラ フに お い て は
タ ス ク 間 の通 信 回数 も増 大 し、 並 列 プ ロ グ ラム 実行 の 際
に 大 き な オ ーバ ヘ ッ ドとな る。 そ の た め タス クの 総数 を
減 らす 必 要 が あ り、 トラ ンス レー タで は そ の た め の 手 段
と して タ ス ク融 合 手 法 を組 み込 ん で き た。
3.現
在 の トラ ン ス レー タ の 問 題 点
現 在 の トラ ン ス レ ー タ で は 解 析 対 象 をmain関 数 に 書 か れ て い る 第 一 階 層 の も の に 限 定 し て い る。 そ の た め 、 ユ ー ザ 定 義 関 数 やfor文 と い っ た ブ ロ ッ ク は そ れ 自 身 を1つの タ ス ク とみ な して い る。 しか し、 実 際 は そ の タス ク に
は ス テ ー トメ ン トレベ ル の タス クが 内 在 し、 並 列 性 が あ
る。 本年 度 の研 究 で は 、 そ の よ うな 階 層 構 造 にお け る全
て の 階 層 に 対 して解 析 を 行 うこ とに よっ て 、 よ り多 くの
並 列性 を抽 出 し、 並 列 処 理 に よ るプ ロ グ ラム の 実 行 時 間
の減 少 を 目的 とす る。
3.1コ ン パ ウ ン ドタ ス ク に 対 す る 並 列 性 解 析 の 拡 張 今 ま で の ト ラ ン ス レ ー タ は 解 析 対 象 をmain関 数 に 限 定 し て い た た め 、 タ ス ク グ ラ フ はmain関 数 を 第 一 階 層 で タ ス ク グ ラ フ 化 し た1つ の み を 生 成 して い た 。 今 年 度 は 既 に 実 装 さ れ て い るmain関 数 の タ ス ク グ ラ フ に 加 え て 、 ユ ー ザ 定 義 関 数 やfor文 な ど ブ ロ ッ ク で 表 さ れ て い る コ ン パ ウ ン ドタ ス ク の タ ス ク グ ラ フ 化 を 実 装 した 。 こ れ ら の コ ン パ ウ ン ドタ ス ク の タ ス ク グ ラ フ を サ ブ タ ス ク グ ラ フ と 定 義 す る。 複 数 の タ ス ク グ ラ フ を サ ブ タ ス ク グ ラ フ と して 登 録 す る こ と が 可 能 で あ り、 各 サ ブ タ ス ク グ ラ フ は タ ス ク グ ラ フ 化 さ れ た 自 身 の タ ス クIDと 紐 付 け られ て い る 。 そ の た め 、main関 数 の タ ス ク グ ラ フ を 解 析 して い る 中 で コ ン パ ウ ン ドタ ス ク に た ど り着 い た 際 に 、 そ の タ ス ク を 表 す サ ブ タ ス ク グ ラ フ の 内 部 ま で 階 層 的 に 解 析 を 行 う こ と が 可 能 で あ る。 ま た 、 各 サ ブ タ ス ク グ ラ フ は 自 身 の コ ン パ ウ ン ドタ ス ク 情 報(ユ ー ザ 定 義 関 数 やforタ ス ク な ど)を 併 せ て 保 持 す る。 図3.1に サ ブ タ ス ク グ ラ フ の 例 を 示 す 。main関 数 の タスクグ ラフ
サ ブタス クグ ラフ:
Sタ
ス ク番 号3,for
タスク番 号
善
図3.1サ ブ タ ス ク グ ラ フ の 例サ ブ タ ス ク グ ラフ を 作 成 す る こ とに よ り、 今 ま で は 解
析 を 行 っ て い な か っ た コ ンパ ウ ン ドタス クの 内 部 の タス
ク群 に 対 して解 析 が 可 能 とな り、 全 階 層 構 造 に対 して 解
析 が 可 能 とな っ た とい え る。 これ に よ り、 前 年 度 ま で に
実 装 され て い た解 析 がmain関 数 に 対 して だ けで な く、 ユ
ー ザ 定 義 関数 に 対 して も適 用 可 能 とな っ た
。
本 研 究 で は 主 に 、 プ ロ グ ラム の 実 行 時 間 の 大 半 を 占 め
る と言 わ れ るfor文 に よ るル ー プ 処 理 に 対 して 並 列 性 の
向 上 を 図 る。
4.ル
ー プ リ ス トラ ク チ ャ リ ン グ
一 見並 列 処 理 が で き そ うに な いル ー プ に 対 して
、 ル ー
プ 内 の依 存 関係 を解 析 し、依 存 関係 を解 消 す る こ とに よ
っ て 、
並 列 処 理 可 能 なル ー プ に再 構 築 で き る場 合 が あ る。
ル ー フ.を再 構 築す るた め の 手 法 と してル ー プ リス トラ ク
チ ャ リ ン グ[2]手
法 が挙 げ られ る。 本 研 究 で は 、並 列 性 の
向 上 を 図 るル ー プ デ ィス トリ ビ ュー シ ョ ン とル ー プ 自身
の処 理 時 間 の短 縮 を 図 るル ー プ の ブ ロ ッ ク化 を実 装 した 。
4.1ル ー プ の 解 析 に つ い て 4.1.1イ テ レー シ ョ ン とDOALL処 理 イ テ レ ー シ ョ ン と は 、1回 ル ー プ が 回 る 毎 に 行 わ れ る 1セ ッ トの ス テ ー トメ ン ト群 の こ と で あ る。 イ テ レ ー シ ョ ン 間 に 依 存 が 無 く,ル ー プ の 制 御 変 数 の 値 に お け る イ テ レ ー シ ョ ン を 全 て 並 列 に 実 行 す る こ と をDOALL処 理 と い う。DOALL処 理 が 可 能 な ル ー フ.の例 を 図4.1に 示 す 。 イテ レー ション DOALL処 理 可 能i=oの と きi=1の と きi=2の とき
a【0】=blO】+c【01;a【1]=b【1】+c【1】;a【2】=b【2】+cl21; a【o】++;al11++;a【2】++; 図4.1イ テ レー シ ョ ン とDOALL処 理 の 例 4.1.2イ テ レー シ ョ ン 内 ・イ テ レー シ ョ ン 間 依 存 各 イ テ レ ー シ ョ ン で 発 生 す る依 存 の こ と を イ テ レ ー シ ョ ン 内 依 存 と い う。 イ テ レ ー シ ョ ン 内 依 存 は 、DOALL処 理 を 行 っ た と し て も 、 他 の イ テ レ ー シ ョ ン に 影 響 を 与 え る こ と な く 実 行 で き る依 存 の こ と で あ る。 制 御 変 数 の 増 減 に よ り発 生 す る依 存 の こ と を イ テ レ ー シ ョ ン 間 依 存 と い う。 配 列 変 数 を 例 に と る と,同 じ シ ン ボ ル で イ ン デ ッ ク ス が 違 う場 合 に 発 生 す る 依 存 で あ る 。 イ テ レ ー シ ョ ン 問 依 存 が 存 在 す る と 、DOALL処 理 を 行 う こ と が で き な い 。 図4.2に イ テ レ ー シ ョ ン 内 依 存 と イ テ レ ー シ ョ ン 間 依 存 の 例 を 示 す 。
・ゆ イテ レーション内依 存 → イテレーション間依 存 i=oの とき ・【9⑭c【01; 1; for`i=0;iく3;i++⊃{ a【i】=bIi]+cIil; b【i】=1; c【i+11++; 図4.2イ テ レー シ ョ ン 内 ・間 依 存 の 例 4.2ル ー プ デ ィ ス トリ ビ ュ ー シ ョ ン ル ー プ デ ィ ス ト リ ビ ュ ー シ ョ ン と は 、 ル ー プ を 複 数 に 分 割 す る こ と に よ り並 列 性 を 上 げ る 手 法 で あ る 。 ル ー プ デ ィ ス ト リ ビ ュ ー シ ョ ン は 前 方 へ の イ テ レ ー シ ョ ン 間 依 存 が 存 在 し な い 場 合 に 適 用 可 能 で あ り、 分 割 後 の ル ー プ をDOALL処 理 可 能 な ル ー プ と し て 構 築 で き る 場 合 が あ る。 ま た 、1つ の ル ー プ を 複 数 の ル ー プ へ と 分 割 す る こ と に よ っ て 内 部 階 層 の 並 列 性 を 上 位 階 層 で 利 用 す る こ と が 可 能 に な る 場 合 が あ る。 図4.3は ル ー プ デ ィ ス ト リ ビ ュ ー シ ョ ン を 適 用 す る こ と に よ っ て ル ー プ の 内 部 階 層 に あ る 並 列 性 を 上 位 階 層 で 利 用 を 可 能 と す る イ メ ー ジ を 示 す 。 ル ー プ 内 に あ る1-1∼2-2は そ の ル ー プ に 内 在 す る ス テ ー トメ ン トを 表 し て い る。 実 装 し た ル ー プ デ ィ ス ト リ ビ ュ ー シ ョ ン の 処 理 手 順 は 、 ま ず 変 数 の シ ン ボ ル 単 位 で の ル ー プ の 分 割 を 行 い 、 そ の 後 に 配 列 変 数 の イ ン デ ッ ク ス に 注 目 して ル ー プ の 分 割 を 行 う。 う に 分 割 を 行 う。 複 数 の ス テ ー トメ ン ト に お い てReadの み で 使 用 さ れ て い る シ ン ボ ル に つ い て は 複 数 のfor文 で 実 行 す る よ う に 分 割 す る こ と が 可 能 で あ る。 こ の 分 割 に よ っ て 、for文 をDOALL処 理 可 能 なfbr文 へ と 再 構 築 で き る 場 合 が あ る。 図4.4は 使 用 し て い る 変 数 シ ン ボ ル に よ っ て 、1つ の ル ー プ を2つ の ル ー プ に 分 割 し て い る 例 で あ る。 分 割 前 の ル ー プ はDOALL処 理 が 不 可 能 で あ り逐 次 処 理 を 行 わ な け れ ば な ら な い が 、分 割 後 の2つ 目 の ル ー プ はDOALL 処 理 が 可 能 と な っ た 。 for⊂i=0;iくN;i++){ a【+1】=b【i】+c[i 瑠:lli】+bli】; e【 】=b【i】+c【i】; } for{i=0;i<N;i++⊃{ ali+1】=b【i】+c【i1; .dli】=a【i1+b【i];
⇒}細
for{i=0;iくN;i++⊃{ e【i】=b[i】+c【i】; }ゆ
EコEl]回
[≡コE≡]
図4.3ル ー プ デ ィ ス ト リ ビ ュ ー シ ョ ン に よ る 並 列 性 の 変 化 の 例 4.2.1シ ン ボ ル 単 位 で の ル ー プ 分 割 イ テ レ ー シ ョ ン 内 の ス テ ー トメ ン トに お け る 各 変 数 シ ン ボ ル のRead/Writeを 解 析 し 、 使 用 され て い る シ ン ボ ル に よ っ て イ テ レ ー シ ョ ン を 複 数 の ス テ ー トメ ン ト群 に 分 割 す る。 同 一 シ ン ボ ル を 使 用 し て い る 複 数 の ス テ ー トメ ン トに 関 し て は 、イ テ レ ー シ ョ ン 内 に そ の シ ン ボ ル にWriteし て い る ス テ ー トメ ン トが 存 在 す る 場 合 は 、 そ の シ ン ボ ル を 使 用 す る ス テ ー トメ ン ト群 は 同 一 のfor文 で 実 行 す る よ図4.4変
数 の シ ンボ ル に よ っ てル ー プ を分 割 す る例
4.2.2イ ン デ ッ ク ス 単 位 で の ル ー プ 分 割 イ テ レ ー シ ョ ン 内 の 各 ス テ ー トメ ン トで 使 用 さ れ る 配 列 変 数 に お い て 、Read/Writeさ れ る イ ン デ ッ ク ス を 解 析 す る 。 同 一 シ ン ボ ル を 使 用 し て い る複 数 の ス テ ー トメ ン トに お い て 、 前 方 へ の イ テ レ ー シ ョ ン 間 依 存 が 存 在 し な い 場 合 、そ れ ら の ス テ ー トメ ン ト群 は 複 数 のfor文 で 実 行 す る よ う に 分 割 す る こ と が 可 能 で あ る。 イ テ レ ー シ ョ ン 間 依 存 の 方 向 に つ い て は イ ン デ ッ ク ス の 大 小 関 係 か ら 判 断 す る 。 た だ し 、 分 割 後 のfbr文 に 依 存 関 係 は 存 在 す る 。こ の 分 割 に よ っ て 、for文 をDOALL処 理 可 能 なfor文 と へ 再 構 築 で き る場 合 が あ る。 図4.5は 変 数 の イ ン デ ッ ク ス に よ っ て 、 図4.4の 分 割 後 の1つ 目 の ル ー プ を さ ら に2つ に 分 割 し た 図 で あ る 。 逐 次 実 行 を し な け れ ば な ら な か っ た ル ー プ が 、 分 割 す る こ と に よ っ て 共 にDOALL処 理 が 可 能 な2つ の ル ー プ と な っ た 。 for⊂i=0;i<N;i++){
謂 調荷}
a【 】++; } for⊂i=0;i<N;i++,{ a【i+1】=b【i】+c【i】;●●ゆ 鰍
k嗣{
d【i】=a【i】+b【i】; a【il++; }図4.5変
数 の イ ンデ ック ス によ って ルー プを分 割す る例
4.3ル ー プ の ブ ロ ッ ク 化 上 記 で 説 明 し た ル ー プ デ ィ ス ト リ ビ ュ ー シ ョ ン に よ っ て 、 並 列 性 の 向 上 が 期 待 で き る 。 そ れ に 併 せ て,forル ー プ 自 体 の 処 理 時 間 の 短 縮 を 目的 と した ル ー プ の ブ ロ ッ ク 化 を 実 装 し た 。
4.3.1ブ
ロッ ク化 の 概 要
ブ ロ ック 化 とは 配 列 の ア クセ ス 範 囲 を局 所 化 す る こ と
に よっ て 処 理 の 高 速化 を 図 る最 適 化 手 法 で あ る。CPUは 、
高 速 で 小 容 量 の 記 憶 装 置 と、 低 速 で 大 容 量 の 記 憶 装 置 を
組 み 合 わ せ た メモ リ階層 構 造[31を使 用 して い る。 メ モ リ
の 階 層構 造 を 図4.6に 示 す 。
図4.6メ モ リ の 階 層 構 造上位 層 に あ る記 憶 装 置 ほ ど高 速 な 代 わ りに容 量 が 小 さ
く,下 位 層 に あ る記 憶 装 置 ほ ど低 速 な 代 わ りに容 量 が 大
き い。 演 算 装 置 が 必 要 とす るデ ー タが 上位 層 に保 存 され
て い な け れ ば そ の 下 の 層 の 記 憶 装 置 に 保 存 され て い るか
を調 べ,最 終 的 に は 低 速 な メ イ ンメ モ リにあ るデ ー タ に
ア ク セ ス す る こ とに な る。 そ の た め,一 度 高 速 な 記 憶 装
置 に保 存 した デ ー タ を 再利 用 す る こ とが で きれ ば 、 メイ
ンメ モ リに ア クセ ス す る回 数 を減 らす こ と に繋 が り、 処
理 の 高 速化 が 期 待 で き る。
ブ ロ ック 化 を 適 用 す る こ とに よ りデ ー タの ア クセ ス を
局 所 的 に す る こ とに よっ て 、 メ イ ンメ モ リと比 べ て 高 速
に ア ク セ ス が 可 能 な キ ャ ッシ ュメ モ リ上 にあ るデ ー タ を
再利 用 す る こ とが で き る。
ブ ロ ッ ク化 を 適 用 して 効 果 が 得 られ る例 と して,行 列
積 の 計 算 が 挙 げ られ る。 行 列 積 の 計 算 に お け るデ ー タの
ア ク セ ス(1行
分)を 図4.7に 示 す 。図 の 細 い 矢 印 は1要
素 を 求 め るた め の繰 り返 し,太 い 矢 印 は 求 め る要 素 の 繰
り返 しを 表 す 。 この とき,1要
素 を求 め るた めの デ ー タ
が す べ て キ ャ ッシ ュ に 収 ま りき らな い 場 合 、 次 の 要 素 を
求 め る際 に は1度
キ ャ ッシ ュ に入 れ た行 列Aの 値 が 追 い
出 され て しま っ て い る。 そ の た め キ ャ ッ シ ュ上 の デ ー タ
を 再利 用 で き な い。
そ の よ うな 場 合 に 、 計 算 をブ ロ ッ ク ご と に行 う、 ル ー
プ の ブ ロ ッ ク 化 を 適 用 す る。 図4.7の 行 列 積 の 計 算 に ブ ロ ッ ク 化 を 適 用 し た 例 を 図4.8に 示 す 。 図4.8は 行 列 の 大 き さnの 半 分 の 大 き さ で ブ ロ ッ ク 化 を 行 っ て い る 。こ の ブ ロ ッ ク の 大 き さ を ブ ロ ッ ク 幅 と い う。産=・1魯 価
k■
鴇⇒
CAB図4.7行
列 積 の 計 算 に お ける デ ー タ ア ク セ ス
こ の ブ ロ ッ ク 化 を 行 う こ と に よ っ て 、Cl1ブ ロ ッ ク 内 の 計 算 はCl1=All×Bll+A12×B21と な る 。 同 時 に 使 用 す る3ブ ロ ッ ク が 全 て キ ャ ッ シ ュ に 収 ま る 場 合 、C11ニ All×Bllの 計 算 後 にCl1+=A12×B21の 計 算 を す る と き に は 、キ ャ ッ シ ュ にCl1の デ ー タ が 残 っ て い る 。 し た が っ て 、c11は キ ャ ッ シ ュ 内 の デ ー タ を 再 利 用 す る こ と が 可 能 で あ り 、 メ イ ン メ モ リ へ の ア ク セ ス 数 を 減 ら す こ と が で き る 。ψ圃 圃
霧8鯛
図4.8ブ ロ ッ ク 化 を 適 用 した 例 4.3.2ブ ロ ッ ク 化 を 適 用 す る 条 件 ブ ロ ッ ク 化 を 適 用 す る 際 に は 、そ のfor文 が ブ ロ ッ ク 化 に よ る 効 果 を 得 られ る の か と い う点 と ブ ロ ッ ク 幅 の 大 き さ を 考 慮 す る 必 要 が あ る。 キ ャ ッ シ ュ に デ ー タ を 格 納 す る と き は 単 一 の デ ー タ の み を 格 納 す る の で は な く 、 あ る連 続 デ ー タ 単 位 ご と に 格 納 す る 。 そ の た め 、 行 列 の 和 の 計 算 の よ うな 、 常 に 連 続 デ ー タ に ア ク セ ス す る よ うな 計 算 に 対 し て は ブ ロ ッ ク 化 を 行 っ て も効 果 が 得 られ な い 。 む し ろ ブ ロ ッ ク を 作 る こ と に よ っ て キ ャ ッ シ ュ に 入 っ て い る デ ー タ を 無 視 し て し ま う こ と に な り 、 処 理 時 間 が 長 く な っ て し ま う。 そ の よ う なfor文 に 対 して ブ ロ ッ ク 化 は 適 用 し な い 。 ブ ロ ッ ク 幅 の 大 き さ は 同 時 に 使 用 す る ブ ロ ッ ク が 全 て キ ャ ッ シ ュ に 収 ま る 大 き さ で 最 大 の 値 と す る。 ま た 、 ブ ロ ッ ク 幅 は 元 の 行 列 の 大 き さ を 割 り切 れ な け れ ば な ら な い 。 計 算 式 を 図4.9に 示 す 。1イテ レーションの実 行に必要 なメモリ数xブ ロック内の繰 り返 し数 くキ ャッシュサイズ 5.評 価 図4.9ブ ロ ッ ク 幅 の 計 算 式 評 価 方 法 は 、for文 を 含 む ソ ー ス コ ー ド に 対 して トラ ン ス レ ー タ に よ る ル ー プ リス トラ ク チ ャ リ ン グ 手 法 を 適 用 す る。 こ れ に よ っ て プ ロ グ ラ ム の 実 行 時 間 が 短 縮 さ れ る か を 評 価 す る。 実 験 環 境 は 以 下 の と お りで あ る 。 -CPU:lntel(R)Xeon(R)E5-4640@2 .40GHz -OS:OS:CentOS6 .5 -L2キ ャ ッ シ ュ:256000Byte -L3キ ャ ッ シ ュ:20480000Byte 5.1予 備 実 験1 予 備 実 験1で はfor文 を 含 む ソ ー ス コ ー ド に 対 して トラ ン ス レ ー タ に よ る ル ー プ デ ィ ス ト リ ビ ュ ー シ ョ ン を 適 用 す る。 適 用 す る こ と に よ っ て 、for文 に 内 在 す る 並 列 性 を 抽 出 で き 、プ ロ グ ラ ム の 実 行 時 間 が 短 縮 す る か を 調 べ る 。 実 験 に 使 用 し た ソ ー ス コ ー ドは 、 同 一 のfbr文 内 に 並 列 に 実 行 可 能 な 行 列 積 の 計 算 が2つ あ り、 そ のfor文 を2回 記 述 し て い る。計 算 を 行 う行 列 は1000×1000の 大 き さ と 5000×5000の 大 き さ の2つ の パ タ ー ン で 実 験 を 行 っ た 。 デ ィ ス ト リ ビ ュ ー シ ョ ン 適 用 に よ る 実 行 時 間 の 変 化 を 図5.1に 示 す 。 並 列 実 行 す る こ と に よ っ て 実 行 時 間 が 1000×1000の 行 列 で は 約43%、5000×5000の 行 列 で は 約49%短 縮 さ れ た 。 こ れ は 、 行 列 を 大 き く す る こ と に よ っ て 計 算 時 間 と 、 そ の 前 後 に 必 要 な 通 信 に か か る 時 間 と の 比 率 が 大 き く な っ た た め だ と 考 え ら れ る 。 ま た 、 プ ロ グ ラ ム の 処 理 を 均 等 に2並 列 に 処 理 す る た め 、 行 列 を 大 き く し続 け て も 減 少 率 は50%に 近 似 す る も の と 考 え ら れ る。 分 割な し (逐次)(秒) 分 割 あり (2並 列)(秒) 分割時間 (秒) 減 少率(%) 1000*1000行 列 31」42725 17.755210 0.0113690 42.951091 5000*5000行 列 6737.930035 3407.550380 0.0113690 49.427172 図5.1デ ィ ス ト リ ビ ュ ー シ ョ ン 適 用 に よ る 実 行 時 間 の 変 化 5.2予 備 実 験2 予 備 実 験2で はfor文 を 含 む ソ ー ス コ ー ド に 対 して トラ ン ス レ ー タ に よ る ル ー プ の ブ ロ ッ ク 化 を 適 用 す る こ と に よ っ て 、 プ ロ グ ラ ム の 実 行 時 間 が 短 縮 す る か を 調 べ る 。 実 験 に 適 用 し た ソ ー ス コ ー ドに はfor文 が2つ あ る 。1つ 目 のfor文 で は 、2つ の 行 列 を 適 当 な 値 に 初 期 化 す る 。2つ 目 のfor文 で は そ れ ら の 行 列 の 積 を 計 算 す る 。 計 算 を行 う 行 列 はfloat型 で 、1000×1000の 大 き さ と5000×5000の 大 き さ の2つ の パ タ ー ン で 実 験 を 行 っ た 。 図5.2に ブ ロ ッ ク化 を適 用 し た2つ のfor文 を 示 す 。 初 期 化 を し て い るfbr文 は デ ー タ ア ク セ ス が 連 続 し て い る デ ー タ に 対 す る も の な の で 、 ブ ロ ッ ク化 を適 用 し て い な い こ と が わ か る 。 ま た 、for文 の 上 部(プnグ ラ ム 内 の 変 数 宣 言 部)に ブ ロ ッ ク 幅 を 表 す 変 数(BLKO)とfbr文 の 制 御 変 数 用 の 変 数(ii,jj,kk)が 追 加 で 宣 言 され て い る 。図4.8 の 計 算 式 で ブ ロ ッ ク 幅 を 計 算 す る と 、L2キ ャ ッ シ ュ に 収 ま る ブ ロ ッ ク 幅 は25、L3キ ャ ッ シ ュ に 収 ま る ブ ロ ッ ク 幅 は100と な る 。 ntBLKO=25; ntii; ntjj; ntkk; for(i=0;i〈NUM;i十 ÷){ for(j=0;j〈NU鰯;j++){ a[i]〔j]=j; b[i][j]=-」; } } gotti隠oofday(&s,四ULL); for(ii=0;ii<岡U闇;ii+=BLKO){ for(jjニ0;jj<四U図;jj+=BLKO){ for(kk=0;kk<肘U凹;kk+=BLKO){ for(i=ii;i〈ii十8LKO;i十 十){ for(j=jj;j〈jj+8LKO;j++){ for(kニkk;k〈kk寺8しKO;k十 十){ c[i][j]+=a[i][k]宰b[k][」]; } } } } } } otti隠eofda(&e四ULL)・ 図5.2ブ ロ ッ ク 化 を 適 用 した コ ー ド ブ ロ ッ ク 化 適 用 に よ る 実 行 時 間 の 変 化 を 図5.3に 示 す 。 こ の 実 験 の ソ ー ス コ ー ドは 並 列 実 行 可 能 な 部 分 が 無 い た め 、 並 列 処 理 は 行 っ て い な い 。 ま た 実 行 時 間 の 計 算 は 行 列 積 の 計 算 を 行 うfbr文 の 部 分 の み で あ る 。 ブ ロ ッ ク 化 を 適 用 す る こ と に よ っ て 、1000×1000の 行 列 で は 約9%、 5000×5000の 行 列 で は 約44%実 行 時 間 が 短 縮 さ れ た 。 ブロック化なし(秒) ブロック化あり(秒) ブロック化時間(秒) 減少率{%} 1000*1000行 列 (プロツク幅25) 4.752734 4308241 0.004643 9.254673 1000*1000行 列 (プロツク幅100) 4.752734 4.297442 0.004643 9.481889 5000*5000行 列 (プロツク幅25) 961541800 544.968487 0.004981 43322956 5000*5000行 列 (ブロック幅100) 961.541800 537.317177 0.004981 44.118689
図5.3ブ
ロ ック 化 適 用 に よ る 実 行 時 間 の 変 化
5.3評 価 実 験 評 価 実 験 で は 、 ベ ン チ マ ー ク プ ロ グ ラ ム に 対 して トラ ン ス レ ー タ に よ る ル ー プ リス トラ ク チ ャ リ ン グ 手 法 を 適 用 し た 。 ベ ン チ マ ー ク に はUnixBenchテ ス トの1つ で あ るDhrystoneベ ン チ マ ー ク[41を使 用 し た 。Dhrystoneベ ン チ マ ー ク は 整 数 演 算 を 行 うプnグ ラ ム で 、1秒 間 に メ イ ン ル ー プ を 回 っ た 回 数 で 性 能 を 評 価 す る ベ ン チ マ ー ク で あ る。 Dhrystoneベ ン チ マ ー ク に 対 し て ト ラ ン ス レ ー タ に よ る ル ー プ リス ト ラ ク チ ャ リ ン グ を 適 用 す る 場 合 と しな い 場 合 で の ル ー プ 回 数 の 比 較 を 図5.4に 示 す 。 ル ー プ デ ィ ス ト リ ビ ュ ー シ ョ ン に よ っ て メ イ ン ル ー プ を 小 さ く す る こ と に よ り、ル ー プ の 繰 り返 し 回 数 を 約10%増 や す こ と が で き た 。 そ の 際 に メ イ ン ル ー プ か ら 分 割 さ れ た ル ー プ は 並 列 に 実 行 さ れ て い る。 リストラクチャリングなし (回) リストラクチャリング あり (回) ループ回数 増加 率 (%) 実行時間1秒 30,247,558 33,738,730 11.541996 実行 時間10秒 305,533,741 344,341,531 12.701638 実行 時間60秒 1,833,388,952 2,081,591,217 13.537894
