再帰的なデータ構造を扱うC言語プログラムのためのデータ依存解析手法の提案

再 帰 的 な デー タ構 造 を扱 うC言

語 プ ログ ラム の た め の

デ ー タ依 存 解 析 手 法 の 提 案

武 市

和 真*1,甲

斐

宗 徳*2

AMethodofDataDependencyAnalysisfbrCProgramwithRecursiveDataStructures

KazumaTAKECHI*1,MunenoriKAI*2

ABSTRACT:Recently,thenecessityforparallelprogramminghasbeenincreasedwiththerapidspread

ofmulticore/multiprocessorsystems.However,itisdiflicultforaprogrammertocreateahighly-effective

andhigh-performanceparallelprogram.So,wearedevelopingtheautomatictranslatorfromCprogramsto

parallelprogramsusingMPI(MessagePassingInterface).Inourconventionalautomaticparallelismanalysis

ofCprogramwithpointervariables,itwasabletoanalyzethedatadependenciesofonlythepointer

variablesdeclaredexplicitlyinthecode.Inthisresearch,wehavefirstappliedtheShapeanalysistoC

programswithpointervariablesforgettingtoknowtheformoftherecursivedatastructUreswhichwillbe

allocatedandconstnlcteddynamicallyatthetimeofexecution.Then,usingtheresultoftheanalysis,we

cananalyzethedatadependenciesofrecursivedatastructUres,suchaslinkedlistorbinarytreestructUres,

anddetectmoreparallelismfromCprogram.

Keywordsparallelprocessing,parallelismanalysis,automaticprogramtranslator,recursivedatastructUres

(ReceivedMarch31,2014)

1.は じ め に

近 年 の マ ル チ コア 化 に よ り並 列 コ ン ピ ュー テ ィ ン グの

必 要性 が 高 ま っ て い る。 並 列 コ ン ピ ュー テ ィ ン グで は 複

数 の プ ロセ ッサ や コア を 効 率 よ く協 調 させ る並 列 プ ロ グ

ラ ム で あ れ ば 十 分 な 計 算 処 理 性 能 を得 られ るが,そ

うで

な け れ ば 逐 次 処 理 に 比 べ て 処 理 性 能 を低 下 させ て しま う

可 能性 が あ る。 そ の た め 並 列 コ ン ピ ュー テ ィ ン グで 高 い

処 理性 能 を 得 るに は,逐 次 プ ロ グ ラ ミン グの 知 識 に加 え

て 並 列 プ ログ ラ ミ ン グの 知 識 が 必 要 とな る。 これ は 開 発

者 に とっ て負 担 が 大 き くな る と考 え られ る。

この よ うな 問題 を解 決 す るた め の 手 段 と して 逐 次 プ ロ

グ ラム を 自動 で 並 列 プ ロ グ ラム に 変 換 す る 自動 並 列 化 ト

ラ ンス レー タ の利 用 が 望 ま れ る。 何 故 な ら,逐 次 プ ロ グ

ラム の 自動 並 列 化 が 可 能 に な れ ば 既 存 の 逐 次 プ ロ グ ラム

*1:理 工 学 研 究 科 理 工 学 専 攻 博 士 前 期 学 生 *2:理 工 学 研 究 科 理 工 学 専 攻 教 授(kai@st _{.seikei.ac.jp)}

を 手軽 に利 用 で き る と考 え られ るか らで あ る。

ま た,C言

語 で は ポ イ ン タ を使 用 した 自 由な 記 述 が 可

能 で あ り,並 列 性 の解 析 が 困難 で あ る。 そ こで 本研 究 で

は この ポ イ ン タ に 注 目 し並 列 性 の解 析 を行 う。

2.C言

語 自 動 並 列 化 トラ ン ス レ ー タ の 概 要

C言 語 自動 並列 化 トラ ンス レー タで は 中間 デ ー タ構 造

を 生成 す る。 そ してC言 語 で 記 述 され た 逐 次 実 行 可 能 な

ソー ス プ ログ ラム を読 み 込 み,構 文 木構 造 を解 析 し抽 象

構 文 木 と して 中 間 デ ー タ構 造 に保 存 す る。 この 中間 デ ー

タ構 造 に対 して プ ロ グ ラム 内 に 存在 す る並 列性 を抽 出 し,

中 間デ ー タ構 造 に 並列 化 の た め の 情 報 を保 存 して 抽 象 構

文 木 の 更新 を行 っ て い く。 最 後 に 中間 デ ー タ構 造 の抽 象

構 文 木 と並 列 化 の た め の情 報 を使 い 並 列 プ ロ グ ラム の 出

力 を行 う。 ま た,並 列 効 果 を 高 め るた め に 並 列性 を抽 出

した後 に,ル ー プ の分 割 や 実行 時 間 を 用 い た ス ケ ジ ュー

リン グ な どの最 適 化 処理 を行 うこ とで,よ

り並 列 効 果 の

高 い コ ー ドの 生 成 を 行 う[1]。 本 研 究 で は,共 有 メ モ リ と 分 散 メ モ リの 両 方 の メ モ リ 方 式 に 対 応 し た 並 列 プ ロ グ ラ ミ ン グ ラ イ ブ ラ リ MPI(MessagePassingInterface)を 使 う こ と で,大 規 模 な 並 列 実 行 環 境 で も利 用 可 能 に す る こ と を 目標 と して い る 。 ま た 並 列 実 行 可 能 な プ ロ グ ラ ム を ソ ー ス コ ー ドレ ベ ル で 生 成 す る こ と に よ り機 種 非 依 存 で,ユ ー ザ に よ る 独 自 の チ ュ ー ニ ン グ や コ ン パ イ ラ に よ る 最 適 化 処 理 を 施 す こ と が 可 能 に な る[1]。

3.C言

語 自 動 並 列 化 トラ ン ス レー タ の 処 理 手 順

C言 語 で正 しく記 述 され た 逐 次 ソー スコー ド 畢 入力 C言 語 自 動 並 列 化 トラン ス レー タ 生成 、 、_ 中 間 デ ータ構 造 の 作 成 、一 データ依存解析 _{読 込み}

に

追加 ・更新 タスク粒度解 析 タスクスケ ジュー リング 並 列 コー ド生成 出 力 MPIを 使 った 並 列 ソー ス コー ド 中 間 デー タ構 造 元 のソースコードの 抽象 構文 木 自動並 列化の ため の情報

4.デ

ー タ 依 存 解 析

デ ー タ依 存 関係 が存 在 す る タス クは 処 理 す る順 番 が 変

わ っ て しま う と結 果 も変 わ っ て しま うた め,逐 次 処 理 を

行 わ な くて は な らな い。 この デ ー タ依 存 関係 を解 析 す る

た め に それ ぞれ の タ ス ク 内 で メ モ リ ロケ ー シ ョ ンの ア ク

セ ス属 性 を解 析 す る。 メ モ リ ロケ ー シ ョ ンの ア クセ ス 属

性 に は読 み込 み(read),書 き込 み(write)が あ り,こ の組 み

合 わせ か ら3種 類 の デ ー タ依 存 関係 を解 析 す る こ とが で

き る。Figure4.1で は いず れ も変 数Xに よ るデ ー タ依 存 関

係 が発 生 して い るた め逐 次 実行 す る必 要 が あ る。

蟹)綿

鯉 ら

竃〉鮮 濁 〉轡 ら

Figure4.1デ ー タ 依 存 関 係 の 種 類

逆 に これ らの よ うな デ ー タ依 存 関係 が 無 けれ ば タス ク

同 士 は並 列 性 が あ る とみ なす こ とが 出 来 る。

5.ポ

イ ン タ 解 析

Figure3.1C言 語 自動 並 列 化 トラ ンス レー タ の 処 理 手 順

Figure3.1はC言

語 自動 並 列 化 トラ ン ス レー タ の 処 理

手 順 を 示 した もの で あ る。 最 初 に 逐 次 プ ロ グ ラム を読 み

込 み,構 文解 析 に よ り抽 象 構 文 木 を持 っ た 中間 デ ー タ構

造 の 生 成 を行 う。 以 降 の 処 理 は この 中間 デ ー タ構 造 に対

して行 う。

中 間 デ ー タ構 造 生 成 後 は 中間 デ ー タ構 造 に対 して 並 列

化 可 能 箇 所 を解 析 す るた め に デ ー タ依 存 解 析 を行 う。 初

期 段 階 で は タ ス ク粒 度 が ス テ ー トメ ン ト単 位 で あ るた め

タ ス ク数 が 多 く,後 述 す る タス クス ケ ジ ュー リン グ に時

間 が か か っ て しま う。 そ の た め タス ク粒 度 解 析 を行 うこ

とで タ ス ク 数 を 適 切 に 減 少 させ る。 タス ク粒 度 解 析 を行

っ た 後 は 処 理 を ま とめ る こ とに よ り通 信 回 数 を減 らす な

ど,実 行 時 間 を 短 縮 す るた め の 変 換 を行 うた め に タス ク

ス ケ ジ ュ ー リン グを 行 い,各 プ ロセ ッサ に対 して タス ク

を適 切 に割 り当 て る。 こ こで は タス ク粒 度 解 析 を行 う前

の 段 階 な の で タ ス ク とは ス テ ー トメ ン トの こ とを 指 す 。

以 上 の解 析 結 果 の 情 報 を 持 っ た 中間 デ ー タ構 造 を基 に

コー ド生 成 を行 うこ とで 並 列 プ ロ グ ラム が 生 成 され る。

し か し,4の 方 法 だ け で は ポ イ ン タ を 用 い た プ ロ グ ラ ム に 対 す る デ ー タ 依 存 解 析 を 行 え な い 。Figure5.1は Figure4.1のXの 部 分 を ポ イ ン タ 変 数 が 指 し て い る メ モ リ ロ ケ ー シ ョ ン へ の ア ク セ ス に 書 き 換 え た も の で あ る。 こ の 場 合,ポ イ ン タ 変 数PとQが 同 じ ロ ケ ー シ ョ ン を 指 し て い る な ら ば そ れ ぞ れ の タ ス ク 間 に デ ー タ 依 存 関 係 が 成 り 立 っ 。 し か し,ポ イ ン タPとQが 同 じ ロ ケ ー シ ョ ン を 指 し て い な け れ ば そ れ ぞ れ の タ ス ク 問 に デ ー タ 依 存 関 係 は 発 生 し な い 。 こ の よ う に ポ イ ン タ は 様 々 な ロ ケ ー シ ョ ン に ア ク セ ス す る 可 能 性 が あ り,プ ロ グ ラ ム の 実 行 時 ま で は ポ イ ン タ が ど の ロ ケ ー シ ョ ン に ア ク セ ス す る か が 不 明 の 場 合 が あ る 。 そ の た め,単 に コ ー ドに 記 述 さ れ て い る 変 数 を 静 的 に 読 ん で デ ー タ 依 存 関 係 を 調 べ る こ と は で き な い[2]。 以 上 の 理 由 か ら,ポ イ ン タ 解 析 を 行 わ な い 従 来 の デ ー タ 依 存 解 析 で は,実 行 結 果 を 正 し く 得 る た め に ポ イ ン タ 変 数 に ア ク セ ス す る ス テ ー トメ ン トは 必 ず 逐 次 処 理 を行 う も の と判 定 す る 。

蔀)

曜)

晶)

'Q=20

析 が不 可能 だ っ た。

structlist{

}

inti; StrUCtliSt*nxt; Figure5.3リ ス ト構 造 に 使 う構 造 体 Figure5.1ポ イ ン タ が あ っ た 場 合 こ の 問 題 に 対 し,points-to解 析 を 行 い,ポ イ ン タ が 指 し て い る ロ ケ ー シ ョ ン を 明 ら か に す る こ と に よ り,新 た な 並 列 性 の 解 析 が 可 能 に な る 。

5.1従

来 の ポ イ ンタ 解 析

従 来 の ポ イ ン タ解 析 で はSSA(静 的 単 一 代 入)形 式 を 使

っ て ポ イ ンタ解 析 を 行 っ て い た[4]。この 方 式 で は ポ イ ン

タ が 代 入 され る度 に 新 しい ポ イ ン タ を定 義 しそ れ ぞ れ に

どの 変 数 を 指 す の か と言 う情 報 を 付 与 して 解 析 す る 。

Figure5.2は 実 際 にSSA形 式 に書 き換 え た例 で あ る。

1:P=(structlist*)malloc(sizeofてstructlist)); 2:x=P; 3:fbr(i=0;i<N;i++) { 4:temp=(structlist*)malloc(sizeofてstructlist)); 5:x->nxt=temp; 6:x=x->nxt; } 7:x->nxt=0; int★p,aニ5,bニ6,cニ7,dニ8'

ii≡

勢__2騒

鱗;SSA形

式に

講

Figure5.2SSA形 式 へ の 書 き 換 え と デ ー タ 依 存 解 析 こ う してSSA形 式 に 書 き 換 え た そ れ ぞ れ の ポ イ ン タ 変 数 に そ れ ぞ れ の 指 し 先 の 変 数 を 保 存 す る 。Figure5.2の 例 の 場 合,plは 変 数a,p2は 変 数cを 指 して い る と い う情 報 を 保 存 す る。1行 目 でplがwriteさ れ3行 目で 使 わ れ て い る た め に こ れ ら の デ ー タ 依 存 関 係 を 認 識 す る 。 同 様 に4 行 目 と5行 目 の デ ー タ 依 存 関 係 を 認 識 す る 。そ し てplは aを 指 し て い る の で2行 目 と3行 目の デ ー タ 依 存 関 係 を 認 識 す る。 書 き 換 え 後,図 中 右 側 の 矢 印 で 示 さ れ る よ う な デ ー タ 依 存 関 係 が 認 識 さ れ る こ と に な る 。 し か し,従 来 のC言 語 自 動 並 列 化 ト ラ ン ス レー タ で は ポ イ ン タ 変 数 の 指 し 先 と し て 変 数 の み を 扱 っ て い た 。 こ れ だ け で は ポ イ ン タ 解 析 を 行 っ て 並 列 性 を 見 い だ せ る プ ロ グ ラ ム が 動 的 な メ モ リ確 保 を 行 わ な い も の に 限 ら れ て し ま う。 例 え ばFigure5.3の よ う な 他 の オ ブ ジ ェ ク トを 指 す ポ イ ン タ を 持 つ 再 帰 的 な 構 造 体 が あ り,こ の 構 造 体 を 使 っ たFigure5.4の よ う な プ ロ グ ラ ム を 実 行 し た 場 合,リ ス ト 構 造 が 構 成 さ れ る 。 従 来 のC言 語 自 動 並 列 化 トラ ン ス レ ー タ で はFigure5 _{.4に 対 す る デ ー タ 構 造 の 依 存 関 係 の 解} Figure5.4リ ス ト構 造 の 作 成 5.2Shape解 析 Figure5.5の よ う な プ ロ グ ラ ム で ポ イ ン タ が ア ク セ ス し て い る ロ ケ ー シ ョ ン を 解 析 す る た め の 解 析 手 法 と し て Shape解 析 が 挙 げ られ る[4]。Shape解 析 と は プ ロ グ ラ ム を 実 行 せ ず に 動 的 に 割 り 当 て ら れ た デ ー タ の 特 性 を解 析 す る 技 術 で あ る 。Figure5.5の よ うな リス ト構 造 や 二 分 木 等 の 動 的 メ モ リ確 保 に よ り 作 成 さ れ る 再 帰 的 な デ ー タ構 造 の 形 状 を 解 析 す る。 これ に よ りポ イ ン タ が ど の ロ ケ ー シ ョ ン を 指 し て い る の か を 明 ら か に し,新 し い 並 列 性 の 検 出 が 可 能 に な る 。

鱒訓 哩難`く む

二分木 Figure5.5再 帰 的 な デ ー タ 構 造 5.2.1Shapeグ ラ フ と ノ ー ド 再 帰 的 な デ ー タ 構 造 を 表 現 す る た め にFigure5.6の よ う なShapeグ ラ フ を 作 成 す る 。Shapeグ ラ フ 内 の 円 は 動 的 に 確 保 し た 領 域 を 示 す ノ ー ドで あ り,矢 印 は ポ イ ン タ の 指 し先,つ ま り ロ ケ ー シ ョ ン の リ ン ク で あ る。 ノー ド Figure5.6Shapeグ ラ フ 5.2.1.1要 約(summarize)と 実 体 化(materialize) 再 帰 的 な デ ー タ 構 造 は 実 行 時 ま で ど の よ うな 規 模 に な る か は 不 明 で あ る 。 こ の よ う な 問 題 に 対 し て 要 約

(summarize)や 実 体 化(materialize)を 行 う こ と で あ ら ゆ る 規 模 の 再 帰 的 な デ ー タ 構 造 に 対 し て 対 応 で き る よ う に す る。Figure5.7は 要 約 の 一 例 で あ る 。 こ の 図 の 上 部 に 描 か れ て い るShapeグ ラ フ の 四 角 で 囲 ま れ た 部 分 は ど の ポ イ ン タ に も 指 さ れ て い な い 。 よ っ て こ れ ら の ノ ー ド に 対 し て 要 約 を 行 う こ と で 一 つ に ま と め た ノ ー ドで 表 現 し た 。 P「 q P「 q P q 体化 P コ 、6

賞{宣

Figure5.7要 約 の 様 子 P q 体化 P Figure5.8実 体 化 の 様 子 逆 にShape解 析 で 要 約 さ れ た ノ ー ドを 使 用 す る 際 は 実 体 化 を 行 う。Figure5.8は 実 体 化 の 一 例 で あ る 。 こ の 時 r=p->nxtと い う よ う なpが 指 し て い る ノ ー ド の メ ン バ を 代 入 す る よ うな 式 に よ っ て ポ イ ン タ を 更 新 した 場 合,要 約 さ れ た ノ ー ドを 指 そ う と す る 。 しか し,要 約 さ れ た ノ ー ドはFigure5 _{.7か ら 分 か る よ う に 実 際 に は 複 数 の ノ ー} ドで あ る。 そ の た め,こ の よ うに 要 約 さ れ た ノ ー ドを 指 そ う と す る よ うな タ ス ク を 解 析 す る 場 合 は 実 体 化 を 行 い, 要 約 さ れ た ノ ー ドか ら 一 つ の ノ ー ドを 取 り出 す 。 5.3Shape解 析 の 実 装 5.3.1ノ ー ドの 実 装 従 来 のC言 語 自動 並 列 化 トラ ン ス レ ー タ で は ポ イ ン タ の 指 し 先 と し て 変 数 し か 存 在 して い な か っ た 。 そ の た めShape解 析 で ノ ー ドを 定 義 し動 的 に 確 保 し た 領 域 を 表 現 す る た め に 抽 象 化 し た ロ ケ ー シ ョ ン を 定 義 して,ロ ケ ー シ ョ ン を 継 承 す る 形 で ノ ー ドを 定 義 し た_。 5.3.2リ ン ク 情 報 points-to解 析 で ポ イ ン タ と ロ ケ ー シ ョ ン の 関 係 を 参 照 す る た め に リ ン ク 情 報 を 保 存 す る。こ の リ ン ク 情 報 に は, ど の ポ イ ン タ に 指 され て い る か,ポ イ ン タ の 指 し 先,ノ ー ドの 場 合 は 要 約 を 行 っ て い る の か の 情 報 が 含 ま れ て い る 。 従 来 の 研 究 で はSSA形 式 で 新 し い 変 数 を 定 義 し,そ れ ぞ れ の 変 数 に こ の リ ン ク 情 報 に 相 当 す る 情 報 を保 存 し て い た が 今 回 は ロ ケ ー シ ョ ン を キ ー,リ ン ク 情 報 を値 と

し たmapに 保 存 す る 。 こ れ でShape解 析 後 のpoints-to解

析 で 同 じ ロ ケ ー シ ョ ン を キ ー と し て ス テ ー ト メ ン ト ご と に 異 な る リ ン ク 情 報 に ア ク セ ス す る こ と が 可 能 に な る。 5.3.3ス テ ー トメ ン トの 追 跡 とShapeグ ラ フ の 保 存 こ の よ う な ロ ケ ー シ ョ ン を キ ー,リ ン ク 情 報 を値 と し たmapをShapeグ ラ フ と し て 扱 い,ス テ ー トメ ン ト ご と に 保 存 し てpoints-to解 析 で 使 用 す る 。 中 間 デ ー タ構 造 か ら ス テ ー トメ ン トの 追 跡 を 行 い,ポ イ ン タ に 関 連 す る ス テ ー トメ ン トな らShapeグ ラ フ の 更 新 を 行 う。 5.3.4ル ー プ で のShapeグ ラ フ の 更 新 ル ー プ 文 に 対 し て ス テ ー トメ ン トの 追 跡 とShapeグ ラ フ の 更 新 を 行 う際 は,イ テ レ ー シ ョ ン の 最 後 で 要 約 を 行 っ た 後 に 終 了 条 件 を 満 た す か,前 イ テ レ ー シ ョ ン の 形 状 と 比 較 しShapeグ ラ フ の 変 化 を 見 込 め な く な る ま で イ テ レ ー シ ョ ン の 頭 に 戻 り追 跡 を 続 行 す る。こ の よ うにShape グ ラ フ の 変 化 を 見 込 め な く な る こ と を 安 定 化 と 呼 ぶ こ と に し た 。Figure5.4の プ ロ グ ラ ム に 対 す る ス テ ー トメ ン ト の 追 跡 とShapeグ ラ フ の 更 新 を 例 に し て 説 明 す る 。 5.3.4.1要 約 の 様 子 Figure5.9はFigure5.4の1周 目 のShapeグ ラ フ の 変 化 で あ る 。 こ の よ う に4行 目で ノ ー ドの 作 成,5行 目 で ノ ー ドの リ ン ク,6行 目 で ポ イ ン タ の 更 新 を行 っ てShapeグ ラ フ の 更 新 を 行 っ て い く。 Xptemp

4溢(ち

作成

5

6

xptemp

蕊

Pxtemp

髄

ポ インタの書 き換えリンク Figure5.9Figure5.4の1周 目 で のShapeグ ラ フ の 変 化 こ の ル ー プ の ス テ ー トメ ン トの 追 跡 とShapeグ ラ フ の 更 新 を 行 う こ と で3周 目 と4周 目 の ス テ ー トメ ン トの 最 後 でFigure5.10の よ う なShapeグ ラ フ が 得 られ る 。

pxtemp

⑩11⑫<蚤

P xtemp temp-temp

需,⑩

・

㊦

安 定 化 ノー ド13を要 約 ノー ド12を要 約 4周 目 Figure5.4の3周 目 と4周 目 のShapeグ ラ フ 3周 目 Figure5.10 3周 目の 最 後 の ス テ ー トメ ン トのShapeグ ラ フ で は ノ ー ド11と ノ ー ド12が ど の ポ イ ン タ 変 数 に も 指 さ れ て お ら ず 連 続 し て い る 。 よ っ て こ れ ら の ノ ー ドは 要 約 を 行 い 一 つ の ノ ー ドで 表 現 す る 。 要 約 を 行 う際 に,ど の ノ ー ド を 要 約 した の か を 保 存 しpoints-to解 析 で 同 じ ロ ケ ー シ ョ ン で あ る 可 能 性 の あ る ノ ー ド を 解 析 す る 。4周 目 も 同 様 に ノ ー ド11と ノ ー ド13を 要 約 す る 。 3周 目 と4周 目で 同 じ形 状 で あ る こ と を 解 析 す る の で こ の ル ー プ で の ス テ ー トメ ン トの 追 跡 を 終 了 す る 。 ま た Figure5.10は あ く ま で も ル ー プ の3周 目以 降 のShapeグ ラ フ で あ る。 し か し,実 行 時 に ル ー プ が3周 以 上 す る と は 限 ら ず0∼2周 目 の 場 合 も あ る 。 そ の た め,Figure5.llの よ うな0∼2周 目 で 得 ら れ たShapeグ ラ フ に 対 して も 以 降 の ス テ ー トメ ン トの 追 跡 でShape解 析 を 行 う。

0周

圖

1周

2周

Pxtemp

"

pxtemp

⊥ 一_こ淫

rr■7/u∼ 「u Figure5.110∼2周 目 のShapeグ ラ フ 5.3.4.2実 体 化 の 様 子 Figure5.4の プ ロ グ ラ ム の 続 き で あ るFigure5.12の プ ロ グ ラ ム に 対 す る ス テ ー トメ ン トの 追 跡 とShapeグ ラ フ の 更 新 を 例 に し て 安 定 化 す る ま で の 実 体 化 の 様 子 を 説 明 す る。

max=0;

for(x=P;x!=0;x=x->nxt){

if(max<x->i)

max=X->1;

Figure5.12リ ス ト構 造 か ら最 大 値 を 求 め る プ ロ グ ラ ム Figure5.13はFigure5.12で1周 目終 了 時 の 再 代 入 式 に 対 す る ス テ ー トメ ン トの 追 跡 を 行 っ た 際 のShapeグ ラ フ の 変 化 で あ る。 再 代 入 式 はx=x->nxtで あ る の で,xを 上 書 き し,元 々xが 指 して い た ノ ー ド10の メ ン バnxtで 指 して い る ノ ー ドで あ る ノ ー ド11を 指 す よ う に す る 。 し か し, 5.2.1.1で も 記 述 し た よ うに 要 約 さ れ た ノ ー ドは 複 数 の ノ ー ドを ま と め た も の で あ る の で_{,要 約 さ れ た ノ ー ドか ら} 一 つ の ノ ー ドを 取 り 出 す 。 つ ま り2個 以 上 で あ る ノ ー ド 11に 対 し て 実 体 化 を 行 い 一 つ の ノ ー ド12を 取 り出 す 。 そ し て ポ イ ン タ 変 数xは こ の ノ ー ド12を 指 す よ うに す る。

(亜)-11

1個 以 上 Figure5.13Figure5.12で の1周 目 の 再 代 入 式 で の Shapeグ ラ フ の 変 化 こ う し て 一 度 実 体 化 し て ノ ー ドを 一 つ 取 り出 し た ノ ー ドは2個 以 上 を ま と め て い る 状 態 か ら1個 以 上 を ま と め て い る ノ ー ド と な る。 以 降,ノ ー ド11の 実 体 化 を行 う際 は ノ ー ドllが 要 約 され て い な い 場 合 と 要 約 さ れ て い る 場 合,つ ま り ノ ー ド11が1個 で あ る 場 合 と2個 以 上 の 状 態 と 場 合 分 け を 行 っ てShapeグ ラ フ の 更 新 を 行 っ て い く こ と に な る 。 そ の 様 子 をFigure5.14で 示 す 。

⑩ 題 一(

ノー ド11が要 約 ノー ド11が要 約 され てい る され ていな い

①

一

煙 〉⑬<釜

3周 目 ノー ド11が要 糸1 され ていな い 安定,1・ 一・あ 一⑭(釜 ① 一({)・[(lii}) ノー ド11が 要約 され て いない

(匝〉(釜

Figure5.14Figure5.12で の2周 目 以 降 のShapeグ ラ フ の 変 化 ノ ー ドllを3周 目 で 要 約 さ れ て い な い も の と し て 解 析 す る 。 つ ま り,リ ス ト構 造 の 要 素 が3つ だ っ た 場 合 は xが 全 て の 要 素 を 確 認 した 後 に 終 了 条 件 を 満 た し て ル ー フ.での ス テ ー トメ ン トの 追 跡 を 終 了 す る。ノ ー ド11が 要 約 さ れ て い る も の と し てShapeグ ラ フ の 更 新 を 続 け て い っ た 場 合,5周 目 で4周 目 と 同 じ 形 状 のShapeグ ラ フ と な り安 定 化 し た と解 析 し こ の ル ー プ で の ス テ ー トメ ン トの

追 跡 を 終 了 す る。 ま たFigure5.15は5周 目で の 要 約 前 のShapeグ ラ フ で あ る。 ノ ー ド14及 び ノ ー ド15は 両 方 共 ノ ー ドllか ら 実 体 化 し た も の で あ る 。 実 体 化 は 複 数 に ま と め ら れ た ノ ー ドか ら 一 つ の ノ ー ド を 取 り 出 す た め 違 うIDの ノ ー ドで も 同 じ ロ ケ ー シ ョ ン で あ る 可 能 性 が あ る 。 そ の た め Figure5.15の よ うに 違 う ロ ケ ー シ ョ ン で あ る こ と が 明 ら か で あ る 場 合 はpoints-to解 析 で ポ イ ン タ が そ れ ぞ れ 違 う ロ ケ ー シ ョ ン を 指 し て い る こ と を 示 す た め に ノ ー ド14 と ノ ー ド15が 違 う ロ ケ ー シ ョ ン で あ る と 言 う情 報 を 付 与 し て お く。 ノー ド11か ら実 体 化 ノー ド14と は 違 うロケ ー シ ョン

6.並

列 性 の 解 析

ノー ド11か ら実 体 化 ノー ド15と は 違 うロ ケ ー シ ョン

噸〉参 ⑭ 〈奪

〉㊦

px Figure5.15Figure5.12の 追 跡5周 目 で の 要 約 前 の Shapeグ ラ フ ま た4周 目及 び5周 目で ノ ー ド11を 単 体 と し て 実 体 化 し た 場 合,Figure5.16の よ うにShapeグ ラ フ が 変 化 し,リ ス ト構 造 の 全 て の 要 素 を 確 認 し た 上 で 終 了 条 件 を 満 た す 。

(亘 》12

面

Figure5.163周 目 以 降 で ノ ー ド11が 要 約 さ れ て い な い 場 合 作 成 す る 部 分 が 実 行 時 に0∼1周 で の リス ト構 造,つ ま り リ ス ト構 造 の 要 素 数 が1∼2個 だ っ た 場 合 のShapeグ ラ フ に 対 し て ス テ ー トメ ン トの 追 跡 を 行 っ た 結 果 はFigure 5.17と な る 。 つ ま り,い ず れ の 場 合 も リス ト構 造 の 全 て の 要 素 を 確 認 す る こ と が 分 か る 。 2個 だった場 合 1個 だった場 合

餓

①

ー

以 上 の よ う にShape解 析 を 行 い 中 間 デ ー タ 構 造 に そ れ ぞ れ の タ ス ク で のShapeグ ラ フ を 明 ら か に し保 存 す る 。こ れ に よ りpoints-to解 析 で も こ の 情 報 を 参 照 で き る よ うに な る 。 つ ま り,Shapeグ ラ フ の 情 報 を 参 照 し ポ イ ン タ が ど の ロ ケ ー シ ョ ン を 指 し て い る の か の 情 報 が 参 照 可 能 に な り,こ の 情 報 と4で 述 べ た よ うな デ ー タ 依 存 解 析 と組 み 合 わ せ る こ と に よ っ て 再 帰 的 な デ ー タ 構 造 に 対 し て も デ ー タ 依 存 解 析 が 可 能 に な る_。 Figure5.12の4周 目及 び5周 目 で のShapeグ ラ フ か ら 二 つ の イ テ レ ー シ ョ ン の 最 後 のShapeグ ラ フ は 同 じ形 状 で は あ る が4周 目 でxが 指 し て い る ノ ー ドのIDは14で あ り, 5周 目 で 指 し て い る ノ ー ドは ノ ー ド14で あ る こ と が 分 か る 。 これ ら はFigure5.15で 解 析 し た 情 報 か ら 異 な る ロ ケ ー シ ョ ン を 指 し て い る こ と が 分 か る_{。 つ ま り,3周 目 以} 降,デ ー タ 依 存 解 析 時 にxが 指 し て い る ロ ケ ー シ ョ ン が イ テ レ ー シ ョ ン ご と に 異 な る事 を 解 析 で き た 。 これ は ス カ ラ エ ク ス パ ン シ ョ ン の 特 殊 ケ ー ス で あ る 。 つ ま りFigure6.1の よ う に リ ス ト構 造 を プ ロ セ ッ サ ご と に 区 切 っ て 並 列 処 理 で そ れ ぞ れ の リ ス ト構 造 で 最 大 値 を 求 め た 後 に そ れ ぞ れ の プ ロ セ ッ サ で の 最 大 値 の 中 か ら さ ら に 最 大 値 を 求 め る こ と で 逐 次 実 行 と 同 じ 結 果 を 出 す こ と が 可 能 で あ る。

●6

畢

分 割(それ ぞれ の プロセッサ でリスト構 造 の 生 成)

● →ai)_●_6

畢

それ ぞ れ のプロセッサ で最大 値 を 求 め る処 理 を行う

⑭

…o

畢

それぞれの最大値の中で

の最大値を求める

⑭EO

逐 次実 行 と同 じ 結 果 Figure6.1Figure5.12の 並 列 化 案 Figure5.12を 並 列 化 し た も の がFigure6.2で あ る 。 そ れ ぞ れ の フ.ロセ ス で 元 の リ ス ト構 造 の 要 素 数 を プ ロ セ ス 数 で 割 っ た 数 だ け の リ ス ト構 造 を 作 成 し デ ー タ を 入 力 し て い た も の とす る。 そ れ か ら そ れ ぞ れ の プ ロ セ ス で 最 大 値 を 求 め た 後 にMPIReduce命 令 で 全 て の プ ロ セ ス の 最 大 値 の 中 で の 最 大 値 を 求 め る こ と が 出 来 る。 Figure5.17リ ス ト構 造 が1個 か2個 だ っ た 場 合

〃元 の コ ー ド と 同 じ で そ れ ぞ れ の プ ロ セ ス で 最 大 値 を 求 め る fbr(x=p;x!=0;x=x->nxt){ ifてmax<x->i) max=X->1; } 〃MASTERに 計 算 結 果 を 集 め る MPI _{_Reduce(&max,&recv,1,MPI_INT,MPI_MAX,MAS} TER,MPI _{_COMM_WORLD);}

⑦

⑩(⑱

⑭

oldtablenptrnewtable

⑦(③

一

⑱

一く

⑳ ・

一くii])'

optr Figure6.2Figure5.12の 並 列 化 エ イ トマ   7.hmmerに 対 す るShape解 析 本 研 究 の 評 価 と し て 使 っ た 逐 次 プ ロ グ ラ ム はhmmerで あ る。hmmerはSPECCPU2006[6]の ベ ン チ マ ー ク ー つ で あ り遺 伝 子 配 列 の 検 索 を 行 う。Figure7.1はhmmerの 一 部 を 書 き 換 え た も の で あ り リ ス トoldtableを 逆 順 に し た リス ト,newtableが 得 ら れ る。 Figure7.3 6周 目 7周 目

6周 目で ノー ド14が

要 約 され て いな い も

の と して実 体 化 した場 合

つ ま り,Figure7.1の プ ロ グ ラ ム 実 行 時 に リス ト構 造 が い くつ で あ っ た と し て も リ ス ト構 造 を 逆 順 に す る こ と を解 析 で き た 事 に な る。 こ の よ う に ベ ン チ マ ー ク に 対 し て もShapeグ ラ フ を 構 築 し ポ イ ン タ が ど の ロ ケ ー シ ョ ン を 指 す の か が 明 ら か に な りデ ー タ 依 存 解 析 で 使 う こ と が 可 能 に な っ た 。 new _{_table-malloc(sizeof(遺 伝 子 の リ ス ト));} optr=old _table; while(optr!=0){ nptr=new _{_table;} new _{_table=optr;} optr=optr->nxt; new _{_table->nxt=nptr;} } Figure7.1hmmerの 一 部 こ れ に 対 し てShape解 析 を 行 っ た と こ ろ,イ テ レー シ ョ ン 内 部 の3行 目 の タ ス ク で のShapeグ ラ フ の 更 新 を 行 う 際 に 複 数 の ノ ー ド と し て 実 体 化 を 続 け た 場 合,Figure7.2 の よ うに5周 目 と6周 目の イ テ レー シ ョ ン 終 了 時 に 同 じ 形 状 と な り安 定 化 し た 。 ま た,Figure7.3の よ う に 一 回 で もIDが14の ノ ー ドを 一 個 の ノ ー ド と し て 実 体 化 す れ ば い ず れ はoptrが14に 移 動 し 次 に0を 指 し ス テ ー トメ ン トの 追 跡 は 終 了 す る 。 8.終 わ り に

今 回 の 研 究 でShapeグ ラ フ を構 築 し再 帰 的 なデ ー タ構

造 の形 状 が解 析 可能 に な り,そ の 中で ポ イ ン タが どの ロ

ケ ー シ ョン を指 して い るの か,指 す 可 能性 が あ るの か を

解 析 で き る よ うに な っ た。 これ に よ りこれ ま で 不 明 だ っ

た並 列 性 が解 析 可能 に な っ た。 そ して,リ ス ト構 造 を分

割 しそれ ぞれ の プ ロセ ッサ で 処理 す る例 を示 した。 さ ら

に 実 際 にベ ン チ マ ー ク に 対 して解 析 した と こ ろ,Shape

解 析 をす る こ とが 可能 で あ る こ とを確 認 した。

この よ うにイ テ レー シ ョ ンや タ ス ク ご とのShapeグ

ラ

フ の変 化 が 明 らか に な りデ ー タ依 存 関係 が 分 か る よ うに

な っ た こ とで 人 手 に よ る並列 化 は 可 能 に な っ た。 今 後 の

課 題 と して は 並列 コー ドの 自動 生成 に 対応 させ る こ とで

あ る。 ま た イ ンタ プ ロシ ー ジ ャに 対応 させ る こ とで よ り

多 くの プ ログ ラム に 対応 させ る事 が で き る よ うに す る こ

とが考 え られ る。

①(⑱

一

⑰ 一

一(嘩D

optrnptr oldtable

⑳

⑭newtable

17'⑬

一⑯

一(麺)

optr ・ldt・bl・ ⑩(ll>ppt「newt・bl・ 5周 目

安定化

6周 目 Figure7.2Figure7.1に 対 す るShape解 析 の 一 部

9.参

考 文 献

[1]KazuhiroMinomoto:"ImplementationsofAutomatic TranslatorfromCprogramtoParallelProgramsusing MPI",修 士 論 文,成 膜 大 学 工 学 部 工 学 研 究 科 情 報 処 理 専 攻,2005. [2]SumiyaTohyama:"lmplementationsofParallelism AnalysisandDynamicExecutionControllerfbr AutomaticallyParallelizingSequentialCPrograms",修

士 論 文,成 膜 大 学 工 学 部 工 学 研 究 科 情 報 処 理 専 攻, 2013. [3]MaseMasayoshi:"StudiesonAutomaticParallelization andLowPowerOptimizationofCProgramsonMulticore Processors",早 稲 田 大 学 大 学 院 基 幹 理 工 学 理 工 学 専 攻 博 士 論 文,2011. [4]武 市 和 真:"C言 語 自 動 並 列 化 ト ラ ン ス レ ー タ の 開 発 一 静 的 単 一 代 入 形 式 を 用 い た ポ イ ン タ の 依 存 解 析 の 実 装 一"卒 業 論 文,成 瞑 大 学 理 工 学 部 情 報 科 学 科,2011 [5]AdrianTineo,et.al:``ANewStrategyforShapeAnalysis BasedonCoexistentLinkSets.",Proceedingsofthe InternationalConferenceParCo2005,PP.13-16,2005 [6]FUJITSU:"WHITEPAPERベ ン チ マ ー ク の 概 要".2006 htt://'.fuiitsu.com/latfb㎜/server/rimer/erforman ce/pdfアbenchmark-overview-speccpu2006jp.pdf