成 瞑 大 学 理 工 学 研 究 報 告
J.Fac.Sci.Tech.,SeikeiUniv.
Vol.51No.1(2014)pp.27-34
C言
語 プ ログ ラ ム の た め の ソ ー ス コ ー ド静 的 メ ト リク ス を 利 用 した
タス ク粒度解析手法
小林
裕 昌*1,甲
斐
宗 徳*2
TaskGranularityAnalysisMethodUsingStaticMetricsofSourceCodefbrCPrograms
HiromasaKobayashi*1,MunenoriKai*2
ABSTRACT:InthefirstphaseofourautomaticparallelizingtranslatorfbrCprogram,asourcecodeis
decomposedintoasetoftasksofthegranularityofastatementlevelattheminimum.Inthenextphase,
taskschedulingwhichdeterminesstaticallybywhichprocessorthesetasksareprocessedisperformed.
Sincethistaskschedulingisacombinatorialoptimizationproblem,itisimportantfbrittosuppressthe
numberoftaskswhichconstitutestheprogram.Therefbre,uselessparallelismisremovedusingthe
infbrmationaboutthedependenciesamongtasksandtaskcost,andthetaskgranularityanalysisisrequired
inordertomaketaskgranularityreasonable.However,sinceitisnecessarytoanalyzetheprocessingtime
ofataskonlyusingtheinformationacquiredfromasourcecode,exactcostmaybeunabletobeassigned
inthetimeanalysisusingtheconventionalcomputationalcomplexityanalysis.So,inthispaper,themethod
ofaimingattheimprovementinaccuracyofexecutiontimeanalysisisproposedbyapplyingstaticmetrics
ofsourcecode.
Keywords:automaticparallelizingtranslator,taskgranularity,taskscheduling,executiontimeanalysis,
staticmetricsofsourcecode
(ReceivedMarch31,2014)
1.は
必 須 で あ る と言 え る。
じめ に
しか し,並 列 プ ログ ラ ミ ン グを 用 い て も,効 率 的 な ソ
子計算
ー ス コー ドを 作成 で き な け れ ば ,処 理 速 度 を向 上 させ る
機,す な わ ち コ ン ピ ュ ー タ の 存 在 が 大 き く 関 わ っ て お り,
こ とは難 し く,そ の た め に は 通 常 の プ ロ グ ラ ミ ン グの 知
と り わ けCPU(CentralProcessingUnit)の
識 の他 に,専 門 的 な知 識 が 必 要 とな り,非 常 に難 易 度 の
技 術 分 野 に お け る 驚 異 的 な 成 長 の 背 景 に は,電
進 化 が多大 な影
高 い技 術 で あ る こ とが伺 え る。
響 を 及 ぼ して い る こ とは 間 違 い な い 。
CPUの
性 能 を 向 上 させ る た め の 方 法 と し て は,動
作周
以 上 の よ うな こ とか ら,並 列 プ ロ グ ラム の 必 要性 が 高
こ数 年 で 周 波
ま っ て き て い るに も関 わ らず,効 率 の 良 い 並 列 プ ロ グ ラ
数 を 上 げ る こ とは 限 界 に 近 付 い て い る。 そ こで 性 能 向 上
ム の作 成 に は プ ログ ラマ に 大 き な負 担 が か か る とい う問
に 対 す る解 決 策 と し て,複
題 が発 生 して い る と言 え る。 この 問題 点 を本研 究 の 背 景
波 数 を 上 げ る こ と が 代 表 的 で は あ る が,こ
数 の プ ロセ ッサ を用 い て 並 列
と した。
動 作 さ せ る と い う考 え が 主 流 と な っ て き て い る 。 そ の た
め,プ
ロ グ ラ ム を 効 率 よ く 並 列 処 理 さ せ る た め に は,並
2.C言
列 プ ログ ラ ミ ン グを 用 い て プ ロ グ ラム を作 成 す る こ とが
*1:理
工 学 研 究 科 理 工学 専 攻 博 士 前 期 課 程 学 生
*2:理
工 学 研 究 科 理 工 学 専 攻 教 授(kai@st
語 自 動 並 列 化 トラ ン ス レー タ
C言 語 自動 並 列 化 トラ ン ス レー タ[1]とは,C言
語 で記
述 され た逐 次 実行 可能 な ソー ス プ ロ グ ラム を読 み 込 み プ
.seikei.ac.jp)
一27一
成 践 大 学 理 工 学 研 究 報 告
ロ グ ラム 内 に存 在 す る並 列 性 を抽 出 し,MPI(Message
2.2タ
Vol.51No.1(2014.6)
ス ク グ ラ フに つ い て
PassingInterface)に よ る 並 列 実 行 用 コー ドを埋 め 込 む こ
本 ト ラ ン ス レ ー タ に 読 み 込 ま れ た ソ ー ス コ ー ドは,解
とで 並 列 化 コー ドを 出 力 す る。 ま た,並 列 効 果 を高 め る
析 器 に よ っ て タ ス ク と 呼 ば れ る コ ー ドセ グ メ ン トに 分 解
た め に 並 列性 を 抽 出 した 後 に,ル ー プ の 分 割 や 実 行 時 間
され る 。 タ ス ク 間 に は 依 存 関 係 が 存 在 し,こ れ ら の 先 行 ・
の解 析 を 用 い た ス ケ ジ ュー リン グな どの 最 適 化 処 理 を行
後 続 関 係 を エ ッ ジ で 表 し,タ
うこ とで,よ
を タ ス ク グ ラ フ と 呼 ぶ 。 ま た,ス
り並 列 効 果 の 高 い コー ドを 生 成 す る。
本研 究 で 開発 して い る並 列 化 トラ ンス レー タ で は,ま
タ ス ク 以 外 に も,ブ
だ 実 用 的 な 自動 並 列 化 が 存 在 して い な いC言 語 に 対 して
つifタ ス ク,forタ
並 列化 を行 い,MPIが
すfunctionタ
す る こ とで,よ
挿 入 され た 並 列 プ ロ グ ラム を生 成
り様 々 な 並 列 実 行 可 能 環 境 で 利 用 で き る
ス ク同 士 を つ な い だ グ ラ フ
テ ー トメ ン ト レ ベ ル の
ロ ッ ク ス コ ー プ と制 御 フ ロ ー 文 を 持
ス ク や,ユ
ー ザ 定 義 関 数,main関
数 を示
ス ク とい っ た タ ス ク を マ ク ロ タ ス ク と して
定 義 す る 。 図2は
タ ス ク グ ラ フ の一 例 を示 す 。
よ うに して い る。 ま た 並 列 化 ソー ス コー ドを出 力 す る こ
とで,開 発 段 階 で は ユ ー ザ に よ る独 自の チ ュー ニ ン グや
コ ンパ イ ラに よ る最適 化 処 理 を 施 す こ とが 可 能 とな る。
以 上 の よ うな 特 徴 を 持 ち プ ロ グ ラム の 実 行 性 能 向 上 を
実 現 す るC言 語 自動 並 列 化 トラ ンス レー タ の完 成 を 最 終
目的 とす る。
2.1ト
図1は
ラ ンス レー タ 処 理 手 順
並 列 化 トラ ン ス レ ー タ の 処 理 手 順 を 表 わ して い
図2タ
る。
スクグラ フ の一例
Cソースコード
畢
3.タ
ス ク粒 度解 析
中間データ構造の作成
並 列 性 ・依 存 解 析 が 終 了 した 時 点 で は,一 部 を除 き,
タ ス ク の初 期 粒 度 は ス テ ー トメ ン トレベ ル で あ るた め,
タ ス ク の数 は ソー ス コー ド内 の ス テ ー トメ ン ト数 に 相 当
す る。 す な わ ち ス テ ー トメ ン ト数 が 多 い ソー ス コー ドが
対 象 で あ る場 合,多
畢
くの タ ス クは 細粒 度 の タス クで あ る
た め,タ ス ク数 も大 き くな る。 一般 的 に,並 列 処 理 を行
並 列 化 コード(MPI)
う こ とに よ り発 生す る通 信 の オ ー バ ーヘ ッ ドは,処 理 時
図1並
列 化 トラ ンス レー タ 処 理 手 順
間 に 大 き な影 響 を及 ぼ し,細 粒 度 タ ス クに 関 して は 逐 次
処 理 を行 っ た方 が 良 い場 合 が 多 い。 そ れ ど こ ろか,タ ス
ク ス ケ ジ ュ ー リ ング が組 み合 わせ 最 適 化 問題 で あ るた め,
初 期 作 業 と して 入 力 され た 逐 次 プ ロ グ ラム か ら 中間 デ
ー タ構 造 を 作 成 した の ち ,そ れ に 対 す る,並 列 性 解 析 を
探 索解 法 の過 程 に お い て 大 量 の組 合 せ が発 生 し,求 解 時
行 うこ とで 並 列性 を抽 出 す る[21。
間 が指 数 関数 的 に増 大す る。 この た め,ス テ ー トメ ン ト
中盤 の 作 業 と して,タ ス クの 実 行 時 間 と依 存 関 係 を考
数 が 多 く存 在 す る ソー ス コー ドが 対象 で あ る場 合,無 駄
慮 し,タ ス ク の 適 切 な粒 度 を求 め る タス ク粒 度 解 析 を行
な並 列 性 を省 き,タ ス ク を適 切 な粒 度 に ま とめ る作 業 は
う。 現 段 階 の 本 トラ ンス レー タで は,内 部 で 簡 易 的 な タ
必 須 と言 え る。
ス ク ス ケ ジ ュ ー リン グを 実 行 し タス クに 対 して プ ロセ ッ
前 年 度 で は,タ ス ク粒 度 の調 整 に 用 い る個 々 の タス ク
サ の割 り当 て を 静 的 に 行 う。 タス ク粒 度 解 析 とは,タ ス
コス トを ス テ ー トメ ン ト内 の メ モ リア クセ ス命 令 ,通 信
ク ス ケ ジ ュ ー リン グの 効 率 を上 げ るた め に必 要 な 作 業 と
に か か る オ ーバ ーヘ ッ ドを依 存 強度(通 信 に よっ て 渡 さ
な り,詳 しい説 明 は3章 で行 う。
な けれ ば な らな い 変数 の個 数)と
い う代 替案 を提案 し,
プ ロセ ッサ数 に基 づ く最 大 並列 度 を 考慮 した タス ク融 合
最 終 段 階 で は,各 解 析 ・変 換 処 理 が 完 了 した 中間 デ ー
タ構 造 か ら並 列 プ ロ グ ラム を 作 成 し出 力 す る。
とい うア ブ.ロー チ に よっ て粒 度 を 求 め た[3]。
本 研 究 で は,タ ス クの持 つ様 々 な 要 素 を考 慮 し,よ
一28一
り
成 践 大 学 理 工 学 研 究 報 告
Vol.51No.1(2014.6)
詳 細 な タ ス ク の 実 行 時 間 を 見 積 も る こ とが 可 能 な メ トリ
ク ス を 提案 す る。
3.1タ
ス ク の 種 類 と解 析 方 法 に つ い て
本 ト ラ ン ス レ ー タ で は,タ
ス クの 最 小 単 位 をス テ ー ト
メ ン ト レ ベ ル と し て い る 。 ま た,ス
}
テ ー トメ ン トレ ベ ル
の タ ス ク を 条 件 文 や 制 御 文 と み な し,そ
れ らの タス クの
組 み 合 わ せ をifやfbrと い っ た 専 用 の 構 造 に 当 て は め る こ
と に よ っ て 制 御 フ ロ ー 構 文 を 構 成 し て い る 。 こ の,条
図4Compoundタ
件
3.1.3ifタ
文 や 制 御 文 とい っ た タ ス ク を ま と め た タ ス ク群 を
Controlタ ス ク と定 義 す る 。 関 数 や 構 造 体 と い っ た タ ス ク
も 同 じ く,仮
引 数,ロ
これ ら の タ ス ク の コ ス トは,コ
れ らを 前 述 の とお り
よ っ て 決 定 され る 。 図5で
コ ー プ で 囲 ま れ た タ ス ク 群,基
ロ ッ クス
本 的 な 種 類 のMacroタ
ン トロール タス クの コス
ト と,最 も 実 行 コ ス トの 大 き いCompoundタ
ス ク と呼ぶ 。
こ こ で は ス テ ー トメ ン トレ ベ ル の タ ス ク,ブ
スク
ス ク を 組 み 合 わ せ た 条 件 判 定 を 行 う制 御 フ ロ ー 文 で あ る 。
と ブ ロ ッ ク ス コ ー フ.で囲 ま れ た タ ス ク 群 の 組 み 合 わ せ と
Macroタ
ス ク,if-elseタ ス ク,switchタ
これ ら の タ ス ク は,コ ン ト ロ ー ル タ ス ク とCompoundタ
ー カ ル 変 数 とい っ た す べ て の 変 数
い っ た も の で 構 成 さ れ て お り,そ
ス ク の 一例
ス クの 総 和 に
は,基 本 的 なif-elseタ ス ク の 例
を示 して い る。
ス
ク の解 析 方 法 を 示 す。
3.1.1Expressionタ
スク
本 ト ラ ン ス レ ー タ に お け る タ ス ク の 最 小 単 位 で あ り,
基 本 的 な 式 を 表 現 し て い る 。 代 入 文 や,制
い っ た も の が こ のExpressionタ
御 フ ロー 文 と
ス ク と し て 扱 わ れ る 。こ れ
ら タ ス ク の 情 報 は 木 構 造 に よ っ て 保 管 さ れ て い る 。 図3
で は,代 入 文 で あ るExpressionタ
ス ク の 一 例 を 示 して い る 。
図5if-elseタ
3.1.4forタ
草二2+1
ス ク の 一例
ス ク,whileタ ス ク
これ ら の タ ス ク は,コ ン ト ロ ー ル タ ス ク とCompoundタ
ス ク を 組 み 合 わ せ た 反 復 制 御 を 行 う制 御 フ ロ ー 文 で あ る 。
図3Expressionタ
ス ク の 一 例
これ ら の タ ス ク の コ ス トは,コ
ト とCompoundタ
3.1.2Compoundタ
スク
本 ト ラ ン ス レ ー タ で は,ブ
ス ク の 総 和 で あ る 。 ま た,回
て い る場 合 は,Compoundタ
ロ ッ クス コー プ 内 に宣 言 さ
乗 算 し,判
れ て い る タ ス ク 群 を ま と め て 一 つ の タ ス ク と して 扱 う。
は,forタ
ン トロー ル タス クの コス
数が判明 し
ス ク の コ ス トに 反 復 回 数 を
明 し て い な い も の は 乗 算 を 行 わ な い 。 図6で
ス ク の 一 例 を 示 して い る 。
ifタ ス ク やfbrタ ス ク と い っ た マ ク ロ タ ス ク は,Compound
タ ス ク と,制 御 フ ロ ー 文 で あ るExpressionタ
ス クの 組 み 合
わ せ に よ り構 成 さ れ て い る 。ま た,ユ ー ザ 定 義 関 数 やmain
関 数 と い っ たfUnctionタ ス ク もCompoundタ
数,変
数 宣 言 さ れ たsymbolで
Compoundタ
ス ク と,仮
引
構 成 され て い る 。 図4は,
ス クの 一 例 を 示 して い る。
図6forタ
3.1.5functionタ
ス ク
こ れ ら の タ ス ク は,ユ
一29一
ス ク の 一例
ー ザ 定 義 関 数,main関
数 とい っ
成 践 大 学 理 工 学 研 究 報 告
Vol.51No.1(2014.6)
た 関 数 タ ス ク で あ る。 通 常 の タ ス ク と 異 な り,Compound
0応 用 メ ト リ ク ス
タ ス ク と 引 数,変
>CBF(couplingbetweenfunctions)
数 宣 言 とい っ たsymbolリ
ス トを 持 つ 。
こ れ ら の タ ス ク の コ ス ト はfunctionタ
ス ク の 持 つ
Compoundタ
対 象 の タ ス ク と依 存 関 係 の あ る タ ス ク の 数
ス ク の 一 回 分 の イ タ レー シ ョ ンの コ ス トと
等 し い も の と 定 義 す る。ま た,functionタ
ス ク はCompound
タ ス ク が 持 つ タ ス ク 群 の 依 存 関 係 を 解 析 し,生
タ ス ク グ ラ フ を 持 つ 。 図7は,基
>CBFが
高 い ほ ど 、他 の タ ス ク に 依 存 し て い る こ と
を 示 し 、 複 雑 で コ ス トが か か る こ と を 示 唆 し て い
成 され た
る。
本 的 なfUnctionタ ス ク の
>WMT(weightedmethodspertask)
タ ス ク の複 雑 さの総 和
例 を 示 し て い る。
>WMTが
高 い ほ ど複 雑 な タ ス ク と な り、 コ ス トが
高 い こ と を 示 唆 し て い る。
〉 複 雑 さ の 総 和 と は 、McCabeの
サ イ ク ロマ チ ッ ク
数 と い う循 環 的 複 雑 度 を 示 し て い る。 循 環 的 複 雑
度 と は 、 プ ロ グ ラ ム 中 の 分 岐/合 流 点 を ノ ー ド、 そ
の他 の部 分 を エ ッジ と した とき 、
ノ ー ドの 数(v)、 エ ッ ジ の 数(e)か ら 、e-v+2
と い う式 で 求 め た 値 と な る。
図5functionタ
>RFT(responseforatask)
ス ク の 一例
タ ス ク 内 で 呼 び 出 され るCompoundタ
3.2静
的 メ トリ ク ス を 用 い た タ ス ク の 実 行 時 間 解 析
>RFTが
一 般 的 に 細 粒 度 で あ る ソ ー ス コ ー ドの 実 行 時 間 を 正 確
に 見 積 も る こ と は 難 し い 。 そ こ で,本
持 つ 要 素 に 加 え,タ
ス ク
こ と を 示 唆 し て い る。
行時間解析
3.3各
を 行 う。 そ の た め に 必 要 な 要 素 を 応 用 メ ト リ ク ス と 定 義
し て 解 析 を 行 う。
以 下 は,ど
大 き い ほ ど 、 呼 び 出 すCompoundタ
の 回 数 が 多 い こ と を 示 し 、 複 雑 で コ ス トが か か る
研 究 で は タス クの
ス ク の 属 性 を 考 慮 し,実
ス ク の 回数
メ ト リ ク ス を 使 用 し た コ ス トの 算 出 方 法
前 述 ま で に紹 介 した メ トリ クス を そ の ま ま の数 値 で使
の タ ス クで も適 用 され る基 本 メ トリクス を
用 す る こ と は 難 し く,各
メ ト リ ク ス を 使 用 し た コ ス トの
示 す。
算 出 を 行 う必 要 が あ る。こ こ で は,そ の 算 出 方 法 を 示 す 。
○ 基 本 メ ト リク ス
以 下 の 式 で はnは タ ス クID,Nを
>1、OC(linesofcode)
0基 本 メ ト リ ク ス
●LOCを
タ ス ク の 持 つ ア セ ン ブ リ コ ー ドに お け る ス テ ッ プ 数
>NOV(numberofvariables)
利 用 し た コ ス トの 算 出 方 法
タ ス ク グ ラ フ 内 に あ る タ ス ク のLOCを
タ ス ク の 持 つ 変数 の 数 を 計 測 す るメ ト リクス
実 行 時 間 解 析 と 同 義 で あ り,変
これ は,ア
数 の 個 数 を表 す 二 つ
セ ン ブ リ コ ー ド全 体 か ら 見 た 各 タ ス ク の
持 っ コ ー ドの 割 合 を 示 し て い る。
の メ ト リク ス の 合 計 と な る 。 二 つ の メ ト リ ク ス の 詳
LOCCost(n)=ΣC
100×Loc(n)
し い 内 容 は 次 に 説 明 を 行 う。
.。L。c(k)'"(1)
●NOVを
>NTV(numberoftaskvariables)
タ ス ク の 持 つ ク ラス 指 定 子 が 付 い て い る変 数 の 数
LOC内
ス ク やhmctionタ
とKemerer氏
NOVCost(n)=
が 提 案 し た ソ フ トウ
ト リ ク ス[41を元 に,タ
割 合 を算 出す る。
タ ス ク の 持 つ 命 令 群 の 中 の メ モ リア ク セ
100×
ス ク とい った
ス ク に 適 用 さ れ る メ ト リ ク ス を 示 す 。こ
ェ ア メ ト リク ス で あ るCKメ
に お け るNOVの
ス 命 令 の 割 合 を 示 し て い る。
タ ス クの 持 つ ク ラス 指 定 子 が 付 い て い な い 変 数 の 数
れ は,Chidamber氏
利 用 し た コ ス トの 算 出 方 法
これ は,各
>NIV(numberofinstancevariables)
次 に 示 す の は,ifタ
合 計 し,
対 象 と な る タ ス ク の 割 合 を 算 出 す る。
これ は 前 年 度 の トラ ンス レー タに 採 用 され て い た
Compoundタ
全 体 の タ ス クIDと す る 。
〈10v(n)
oc(n)
…(2)L
0応 用 メ ト リ ク ス
ス
>CBF,WMT,RFTを
利 用 し た コ ス トの 算 出 方 法
クの 実 行 時 間 に 関 わ る と考 え られ る複 雑 度 を算 出 す
これ ら の 応 用 メ ト リ ク ス は,LOCと
る メ ト リク ス で あ る。
グ ラ フ 内 に お け る各 タ ス ク の 割 合 を 算 出 す る。
一30一
同 じ く,タ
ス ク
Vol.51No.1(2014.6)
成 践 大 学 理 工 学 研 究 報 告
100×1!llmt(η)
1!V"τCo∫
張 し た ス ケ ジ ュ ー リ ン グ ア ル ゴ リ ズ ム を 使 用 し て い る。
亡(η)=ΣC
.。 伽
100×Rプ
組 み
込 ま れ て い る 高 精 度 タ イ マ 「lnvariantTSC」 を シ リア ラ イ
100×Cわ
プ(η)CBFC
憂
.。Cbf(k)'0'(4)
OS亡(η)=Σ
RFTCo∫
時 間 計 測 関 数 は,intel(R)Xeon(R)CPUE5-4640に
亡(k)'00(3)
ズ す る こ と な く 呼 び 出 せ るRDTSCP命
令 を使 用 した。
亡(η)
亡(η)=ΣC
4.1.1実
.。 脚)'"(5)
験1:ス ケ ジ ュー リ ング 結 果 の 比 較
この 実験 で は,ス ケ ジ ュ ー リ ン グを行 っ た 結 果 を用 い
ま た,タ
て相 対 的 な 比較 を行 う。 比較 対 象 は,本 提案 手 法 で コス
ス ク コ ス トは 以 上 の 式 の 総 和 と な る 。
トを設 定 した 際 の ス ケ ジ ュ ー リ ン グ結 果 に お け る減 少 率
TaskCost=(1)+(2)+(3)+(4)+(5)
と,実 際 に計 測 した 実行 時 間 を コス トと して 設 定 した 際
こ れ ら の 割 合 と い っ た 重 み 付 け は,LOCやNOVと
た ソ ー ス コ ー ドの 物 理 的 な 情 報 と,依
の ス ケ ジ ュ ー リ ング結 果 の減 少 率 で あ る。 な お,こ
い っ
存 関 係 とい っ た 理
こで
は各 ベ ン チ マ ー クの最 大 並 列度 を 考 慮 しプ ロセ ッサ 台 数
論 的 な 情 報 か ら 算 出 さ れ た コ ス トの 価 値 を 同 等 に し,タ
を4台
ス ク の 相 対 的 な コ ス トを 算 出 す る こ と を 狙 っ て い る 。
と し,探 索 時 間 は10秒
で設 定 しス ケ ジ ュー リン
グ を行 っ た。これ は,最 適 解 が10日
4.性
部 分 の分 枝 限 定 法 に よ る枝 切 りが行 わ れ て い た こ とに よ
以 上 の 探 索 を行 っ て
も得 られ な か っ た こ とに加 え,お お よそ10秒
能評価
ほ どで 大
る もの で あ る。
本 章 で は,前 述 の解 析 手 法 を並 列 化 トラ ンス レー タ に
実 装 し,求 め られ た コス トと,実 際 の タス クの 実 行 時 間
表1ス
ケ ジ ュ ー リン グ結 果 に お け る減 少 率 の 比較
との 相 対 的 な 比 較 を 行 うた め,以 下 の 実 験 を行 った 。 な
逐次 実行
提 案コス トによる
お,紙 面 の都 合 上,本 実 験 で は タス ク粒 度 解 析 にお け る
baSIcmath
スケ ジュー ル 長
実時間(RDTSC)
実 行 時 間解 析 の み を 適 用 した 場 合 を示 して お り,タ ス ク
himeno
実時間(RDTSC)
提 案コス トによる
スケ ジュー ル 長
susan(S)
susan(e)
susan(C)
験概 要
本 提 案 手 法 が 実 装 さ れ た 並 列 化 トラ ン ス レー タ が 生 成
し た ス ケ ジ ュ ー ル 長,並
つ の 実 験 を 行 う。 実 験1で
少 率 を 比 較 し,実
験2で
列 プ ロ グ ラム を用 い て 以 下 の 二
は,ス
は,実
1,282,034,208
減 少率(%)
3,214
29,800
669,126,938
4,347
スケ ジュー ル 長
susan
4.1実
866β48,263
提 案コス トによる
粒 度 最 適 化 は行 っ て い な い
並 列実行
4,582
22,800
2,134
50,909
1,282,006,033
265
233
0,002
12075472
実時間(RDTSC)
実時間(RDTSC)
実時間(RDTSC)
提案コストによる
NasBench(IS) スケジュール長
359.067β89
358,045,623
0.2846999
81,608,665
80,457,236
1.4109151
40,029,505
38,907,192
2.8037144
55,984,147
55,876,623
0.1920615
実 時間(RDTSC)
1,785,007
1,784,952
00030812
ケ ジ ュー リン グ長 の 減
験1で
得 られ た ス ケ ジ ュ
4.1.2実
ール 長 の 減 少 率 と並 列 実 行 した 際 の 減 少 率 を比 較 し
験2:実
行時間の減少率の比較
こ の 実 験 で は,実
,提
際 に 逐 次 実 行 を 行 っ た 実 行 時 間 と,
案 手 法 の 有 効 性 の 検 証 を 行 う。 実 験 環 境 と 使 用 す る ベ ン
生 成 され た 並 列 プ ロ グ ラ ム の 実 行 時 間 を 比 較 し 減 少 率 を
チ マ ー ク は 以 下 の 通 りで あ る 。
算 出す る。 な お 元 の ソー ス プ ロ グ ラム と生 成 され た ソー
・実 験 環 境
ス コ ー ドは 共 にmpiccで
コ ン パ イ ル し て お り,オ プ シ ョ ン
マ シ ン仕 様
の 設 定 も 同 じ で あ る。 ま た,ス
ケ ジ ュ ー リ ン グ を行 っ た
OS:CentOS6.5
際 と 同 じ設 定 で あ る プ ロ セ ッ サ 数4で
並 列 実 行 を行 っ た。
CPU:intel(R)Xeon(R)[email protected]×4
表2実
実 装 メ モ リ:256GB
・使 用 し た ベ ン チ マ ー ク
lMiBenchVersion1.0:basicmath
逐 次実行(秒) 並列 実行(秒) 減 少 率(%)
basicmath
_large.c
susan(S)
susan(e)
susan(C)
2MiBenchVersion1.0:susan.c
3姫
野 ベ ン チ マ ー ク(dynamicallocateversion)
4NASParallelBenchmarks:IS(size'S')
ま た,本
行 時 間 に お け る減 少 率 の 比較
トラ ンス レー タ で は 早 稲 田大 学 笠 原 氏 に よ る
DF/IHS(DepthFirst/lmplicitHeuristicSearch)を
信 を 考 慮 し た 組 合 せ 探 索 が で き る よ うに,当
元 に,通
74,549
52,776
29.20568
0.16530238
0.161720437
2.16690358
0.036015911
0.040963003
一13
0.017626467
0.018816229
一6 .7498582
himeno
50.81711283
50.34413226
0.93075059
NasBench
0.029267821
0.029942926
一2 .3066465
.735851
表2で 減 少 率 が マ イ ナ ス とな っ て い る個 所 は 実行 時 間
が増 加 して い る こ とを表 して い る。
研究室で拡
一31一
成 践 大 学 理 工 学 研 究 報 告
この こ とか ら,よ り詳 し く構 造 を解 析 し,実 行 時 間 を
な お 元 の ソー ス プ ロ グ ラム と生 成 され た ソー ス コー ド
は 共 にmpiccで
コ ン パ イ ル し て お り,オ プ シ ョ ン の 設 定 も
同 じ で あ る。ま た,プ ロ セ ッ サ 数4で
Vol.51No.1(2014.6)
推 測 す る必 要 が あ る と言 え る。
並 列 実 行 を行 った 。
〉 ま とめ
4.2考
察
4.2.1ス
実 験1よ
以 上 の 結 果 か ら,提
案 手 法 が 大 規模 か つ 外 部 の 要 因 に
ケ ジ ュー リン グ結 果 の 比 較 に お け る考 察
よっ て演 算 の 内容 が 変化 す るタ ス クに な るほ ど精 度 が 低
り,提 案 手 法 か ら求 め られ た コス トを利 用 し
く な り,そ
れ に よ る誤 差 が 生 じ る もの と考 え られ る 。
た ス ケ ジ ュ ー リン グ結 果 と,実 際 に 実 時 間 を測 定 し,そ
susanベ
こか ら得 られ た 値 を タ ス ク コス トと して 割 り当て た 際 の
Benchmarksに
ス ケ ジ ュ ー リング 結 果 の 比 較 を 行 っ た 。
め られ る 。basicmathに
》basicmathベ
と な っ た が,約7%の
ンチ マ ー ク につ い て
回 数 不 明 の ル ー プ も少 な く どの マ シ ン環 境 で 動 作 させ
ン チ マ ー ク,姫
野 ベ ン チ マ ー ク,NASParallel
関 し て は,更
な る実行 時 間解 析 の 改 良 が 求
関 し て は,最
も誤 差 の 少 な い 結 果
誤 差 が あ っ た 。 こ れ は,暫
定解 で あ
る こ と が 誤 差 を 生 む 原 因 の 一 つ で あ る と考 え られ る。
て も計 算 内 容 が 同 一 の もの に な る とい う特 徴 か ら,誤 差
4.2.2実
は 最 も少 な い とい う結 果 に な っ た 。 これ は,basicmathの
よ うな 計 算 を 行 うプ ロ グ ラム で あ れ ば 本 提 案 手 法 は 有 効
行 時 間 の 減 少 率 の 比 較 に お け る考 察
実験2で
は,実 際 に 対象 の ベ ンチ マ ー ク を逐 次 で 実行
で あ る と考 え られ る。
した場 合 の 実行 時 間 と,本
>susanベ
され た並 列 化 コー ドの 実行 時 間 を 比較 し減 少 率 を算 出 し
ンチ マ ー ク につ い て
トラ ンス レー タに よっ て 生 成
入 力 され る画 像,オ プ シ ョンに よっ て 演 算 の 内 容 が 変 化
た。 また,実 験1の 表5.1と 実 験2の 表5.2か
ら,ス ケ ジ
す る とい う特 徴 か ら,ソ ー ス コー ドの 内 容 だ けで 実 行 時
ュ ー リン グ 上 の減 少 率 と実 際 の 実行 時 間 の減 少 率 の 比 較
間 の 判別 を行 う本 提 案 手 法 は あ ま り有 効 で な い と考 え ら
を行 っ た。
れ る。 この よ うな ベ ンチ マ ー クに 対 して は,今 後 の 実 行
時 間解 析 の 改 良 の他 に,本
トラ ンス レー タ に昨 年 度 搭 載
>basicmathベ
され た 動 的 実 行 制御 を 行 う並 列 プ ロ グ ラム が 有 効 で あ る
ンチ マ ー ク につ い て
実験1の 結 果 と同 じ くス ケ ジ ュー リン グ結 果 の減 少 率
と言 え る。
と実 際 の プ ログ ラム の減 少 率 との誤 差 が 最 も少 な い。 以
》 姫 野 ベ ンチ マ ー ク に つ い て
上 の こ とか ら,提 案 手 法 で ス ケ ジ ュー リ ン グ を行 い,そ
4⊥1の
実 験 の 中 で最 も誤 差 大 き い結 果 とな っ て い る。
の結 果 を元 に 生成 した 並列 化 コー ドが ほ ぼ狙 っ た 通 りの
原 因 は,マ シ ンの ス ペ ッ クに よっ て 演 算 の 内 容 が 変 化 す
並 列 実行 で あ る こ とを示 し,こ れ は提 案 手 法 に よ り高 い
るベ ンチ マ ー ク とい う特 徴 で あ る点 に加 え,計 算 を行 う
精 度 で 実行 時 間 を概 算 で き た こ とを 示 して い る と考 え ら
関数 に 渡 す 引 数 に よっ て 繰 り返 し回 数 が 変 化 す る とい う
れ る。
プ ログ ラム の性 質 上,本 提 案 手 法 に 対 す る相 性 が 非 常 に
>susanベ
悪 い とい う点 が 上 げ られ る。 これ は,同 一 の 関 数 で あ る
ンチ マ ー ク につ い て
実験1に
も記 した とお り,本 提案 手 法 に よ る実行 時 間
こ とか らそ れ らの タ ス クの コス トは 引 数 に関 わ らず 同 値
解 析 で は,実 際 の処 理 時 間 を概 算 す る こ とは難 し く,そ
で あ る とみ な され るか らで あ る。
れ に伴 っ て ス ケ ジ ュ ー リ ン グ結 果 か ら得 られ た減 少 率 と
この こ とか ら,同 一 の 関 数 で あ っ て もそ の 引 数 に よ っ
実 際 に 実行 を行 っ た 際 の減 少 率 に は誤 差 が 生 じて い る。
て 実行 時 間 が 変 化 す る とい う性 質 を考 慮 す べ きで あ る と
これ は,本 提 案 手 法 に よ る タス クの 重 み 付 けが うま くい
考 え られ る。
かず,タ
》NASParallelBenchmarksに
ついて
ス ク ス ケ ジ ュ ー リ ン グ部 分 に お い て適 切 な 並 列
性 を 生 かす こ とが で き な か っ た か ら と考 え られ る。
この ベ ンチ マ ー クに 関 して も無 視 で きな い 誤 差 が 発 生
ま た,susan(e)とsusan(c)に 関 して は,並 列 実 行 を行 うこ
して しま っ て い る。 これ は,本 提 案 手 法 の 性 質 上 最 も複
とに よ り実行 時 間 が増 加 して しま っ て い る。 この原 因 に
雑 で 大 規模 な構 造 を して い るル ー プ 文 に 対 して コス トを
関 して は,ま
重 く設 定 して しま うとい う点 が 原 因 に な っ て い る と考 え
〉姫 野ベ ン チ マ ー ク に つ い て
とめ に お い て考 察 を行 う。
られ る。 実 際 に 動 作 させ た 結 果,条 件 分 岐 が 多 く最 も大
実 際 に並 列 実行 を行 っ た 際 に僅 か な が ら実行 時 間 の 減
規模 な ル ー プ 文 よ りも,す べ て の 値 を一 つ ず つ 比 較 す る
少 に成 功 した。 内部 で は,計 算 を行 う関 数 が ボ トル ネ ッ
簡 潔 な ル ー プ 文 が ボ トル ネ ッ ク とな っ て い る こ とが 判 明
ク とな っ て お り,そ の タ ス ク以外 は す べ て 細粒 度 の タス
した。
ク で あ る。 した が っ て,計 算 を行 うタス ク を処 理 す るプ
一32一
成 践 大 学 理 工 学 研 究 報 告
ロ セ ッ サ が 実 行 時 間 の 大 部 分 を 占 め て お り,そ
の他のプ
ロ セ ッ サ は ほ と ん ど ア イ ドル 状 態 で あ る 。 ま た,ボ
ネ ッ ク と な る 関 数 は 上 記 で も 示 し た 通 り,引
を 行 う場 合 の ス ケ ジ ュ ー リ ン グ 方 法 と い っ た 技 術 が 未 成
トル
熟 で あ る た め 実装 の段 階 に 至 っ て い な い。
2.MPI命
数 に よっ て
繰 り返 し 回 数 が 変 わ り,演 算 を 行 う処 理 時 間 が 変 動 す る 。
こ の よ うな プ ロ グ ラ ム 場 合,susanと
グ 結 果 か ら 得 ら れ た 減 少 率 と,実
最 低 限 の 通 信 を 行 う命 令 の み で あ る 。 本 来 で あ れ ば
MPIGather,MPIReduceと
ケ ジ ュー リン
MPIBarrierと
際 に 並 列 実 行 した 際 の
い っ た 集 団 通 信 命 令,
い っ た 命 令 を 適 切 に使 用 しな けれ ば 効 率
の 良 い コ ー ドの 生 成 は 不 可 能 で あ る。過 去 の 研 究 に よ り,
減 少 率 に 誤 差 が 生 じ て い る。
>NASParallelBenchmarksに
令 の 選 択 と挿 入
今 年 度 の ト ラ ン ス レ ー タ で 出 力 さ れ る 並 列 化 コ ー ドは,
同 じく提 案 手 法 で は
実 行 時 間 を 推 測 す る こ と が 困 難 で あ り,ス
Vol.51No.1(2014.6)
ついて
こ の ベ ン チ マ ー ク に 関 し て も,susanベ
MPIGather,MPIReduceの
ンチ マ ー ク と同
れ て き た が,ど
使 用 す るた め の 技術 は研 究 さ
の よ うな 条 件 で 命 令 を 挿 入 す る の か と い
っ た こ とが 問題 とな り実装 に は 至 っ て い な い。
じ く 並 列 実 行 を 行 う こ と に よ り実 行 時 間 が 増 加 して しま
っ て い る。 こ れ もsusanベ ン チ マ ー ク と 同 じ く 適 切 な タ ス
ク コ ス トの 見 積 も りが 出 来 な か っ た こ と が 原 因 の 一 っ と
以 上 の結 果 か ら,本 提 案 手 法 が 有 効 な プ ロ グ ラム は 一 部
考 え ら れ る。 ま た,ボ
存 在 す る もの,動 的 に演 算 の 処理 量 が 変化 す る タス ク に
トル ネ ッ ク と な っ て い る 粗 粒 度 タ
ス ク と細粒 度 タ ス ク との 差 が 非 常 に 大 き く無 駄 な 並 列 性
対 して は依 然 と して対 策 が必 要 で あ る と考 え られ る。
が 多 くあ る こ とが 実 行 時 間 の 増加 に 繋 が っ て い る と考 え
ら れ る。 こ れ に 関 し て は,タ
5.ま
ス ク粒 度 最 適 化 部 分 で あ る
とめ と今 後 の課 題
タ ス ク 融 合 が 有 効 で あ る と考 え られ る。 そ れ 以 外 の 原 因
に 関 し て は 以 下 の ま と め で 考 察 を 行 う。
本 研 究 で は,タ ス ク コス ト算 出 の た め の メ ト リクス を
提 案 し,タ ス ク粒 度 解 析 に お け る実行 時 間解 析 の 拡 張 を
》 ま とめ
行 っ た。
以 上 の 結 果 か ら,本
トラ ンス レー タで 想 定 して い た 特
結 果 と して,前 年 度 の メ モ リア クセ ス命 令 だ け を考 慮
徴 と一 致 す るbasicmathベ ンチ マ ー ク に 関 し て は 提 案 手
した計 算 量解 析 と比 べ,ソ ー ス コー ド静 的 メ ト リクス を
法 が 有 効 で あ る と言 え る。 しか し,入 力 され る値 に よ っ
利 用 す る こ とに よ りタ ス ク の もつ性 質 を よ り詳 し く解 析
て 演 算 の 回数 が 変 わ る とい っ た 性 質 の プ ロ グ ラム に対 し
す る こ とが 出来,精 度 の 向 上 に成 功 した。
て は 提案 手 法 で は 不 十 分 で あ る こ とが 考 え られ る。
本 提 案 手 法 に お け る今 後 の課 題 は 以 下 の 二 つ が 上 げ ら
ま た,実 際 に 通信 遅延 を 考 慮 した 静 的 タス クス ケ ジ ュ
ー リング を行 い ,そ の 結 果 を元 に 並 列 化 コー ドを出 力 し
れ る。 一 つ は,こ
こで示 した コス トメ ト リクス に プ ライ
た が 実行 時 間 が 増加 して しま う場 合 が 存 在 した 。 この こ
な 見積 も りを行 え る可能 性 が あ る。 二 つ 目は,こ の メ ト
とに 関 して は,提 案 手 法 が 有 効 に 作 用 しな か っ た 以 外 に
リク ス を導 入 した こ とに よっ て タス ク粒 度 最適 化 の 結 果,
オ リテ ィ を設 定 し重 み づ け を す る こ とに よ り,よ り詳 細
トラ ンス レー タ 全 体 の 問題 と して 以 下 の こ とが 原 因 と し
タ ス ク ス ケ ジ ュ ー リ ング の 求解 時 間,出 力 され た プ ロ グ
て あ げ られ る。
ラ ム の並 列 実行 した 際 の 実行 時 間 に 対 して どの よ うな影
1.main関
響 を 与 え て い るか を よ り詳 し く実 験 し,メ
数 のみ の並 列 化
今 年 度 の トラ ンス レー タ で は,並 列 化 を行 う部 分 が プ
ト リクス の 改
良,選 択 を行 っ て い く必 要 が あ る。
nグ ラム 中 のmain関 数 だ けで あ る。 これ は 各 関 数 や ル ー
プ 文 な どの タ ス クに 対 して は そ れ 以 上 の 並 列 性 解 析 を行
参考文献
わ ず 一 っ の タ ス ク と して 扱 い,そ の 呼 び 出 しを行 うmain
関 数 の み を 並 列 処 理 す る とい うもの で あ る。 しか し,多
[1]美 濃 本
一 浩:"C言
語 自動 並 列 化 トラ ンス レー タ
くの プ ログ ラム は 関 数 や ル ー プ 文 が ボ トル ネ ッ ク とな っ
の 開発",修 士 論 文,成 膜 大 学 工 学 部 工 学研 究 科 情 報
て お りそ れ らの タ ス クに 対 して 並 列 処 理 を行 わ な い 限 り
処 理 専攻,2005.
速 度 の 向 上 は 見 込 め な い。
[2]遠 山
実 際 に ボ トル ネ ッ ク と思 わ れ る タス ク に対 して 並 列 性
純 也:"C言
語 自動 並 列 化 にお け る並 列性 解
析 と動 的 実行 制 御",修 士 論 文,成 膜 大 学 工 学 部 工 学
を抽 出 す る こ とは 現 時 点 で 可 能 とな っ て い るが,そ の タ
研 究科 情 報 処 理 専攻,2013.
ス ク に 対 して どの よ うに して 適 切 な 数 の プ ロセ ッサ を割
り当 て るの か,特 定 の タス ク を複 数 の プ ロセ ッサ で 処 理
一33一
成
[3]竹
本
拓 未:"最
践
大
学
理
工
大 並 列 度 を考 慮 した タ ス ク粒 度 解
析 手 法 の 提 案 と 評 価",学
士 論 文,成
膜 大 学 理 工 学 部
情 報 科 学 科,2013.
[4]S.R.ChidamberandC.EKemerer,``Ametricssuitefbr
object-orienteddesign".IEEETrans.onSoftware
Engineering,20(6),PP.476-493,1994
一34一
学
研
究
報
告
Vol.51No.1(2014.6)

市川市とその30%の人々

カリスマリーダーはどこにいる？