成 瞑 大 学 理 工 学 研 究 報 告
J.Fac.Sci.Tech.,SeikeiUniv.
Vol.51No.1(2014)pp.35-42
再 帰 的 な デー タ構 造 を扱 う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.は
を 手軽 に利 用 で き る と考 え られ るか らで あ る。
じめ に
ま た,C言
近 年 の マ ル チ コア 化 に よ り並 列 コ ン ピ ュー テ ィ ン グの
語 で は ポ イ ン タ を使 用 した 自 由な 記 述 が 可
能 で あ り,並 列 性 の解 析 が 困難 で あ る。 そ こで 本研 究 で
必 要性 が 高 ま っ て い る。 並 列 コ ン ピ ュー テ ィ ン グで は 複
は この ポ イ ン タ に 注 目 し並 列 性 の解 析 を行 う。
数 の プ ロセ ッサ や コア を 効 率 よ く協 調 させ る並 列 プ ロ グ
ラ ム で あ れ ば 十 分 な 計 算 処 理 性 能 を得 られ るが,そ
うで
2.C言
語 自 動 並 列 化 トラ ン ス レ ー タ の 概 要
な け れ ば 逐 次 処 理 に 比 べ て 処 理 性 能 を低 下 させ て しま う
可 能性 が あ る。 そ の た め 並 列 コ ン ピ ュー テ ィ ン グで 高 い
C言 語 自動 並列 化 トラ ンス レー タで は 中間 デ ー タ構 造
処 理性 能 を 得 るに は,逐 次 プ ロ グ ラ ミン グの 知 識 に加 え
を 生成 す る。 そ してC言 語 で 記 述 され た 逐 次 実 行 可 能 な
て 並 列 プ ログ ラ ミ ン グの 知 識 が 必 要 とな る。 これ は 開 発
ソー ス プ ログ ラム を読 み 込 み,構 文 木構 造 を解 析 し抽 象
者 に とっ て負 担 が 大 き くな る と考 え られ る。
構 文 木 と して 中 間 デ ー タ構 造 に保 存 す る。 この 中間 デ ー
この よ うな 問題 を解 決 す るた め の 手 段 と して 逐 次 プ ロ
タ構 造 に対 して プ ロ グ ラム 内 に 存在 す る並 列性 を抽 出 し,
グ ラム を 自動 で 並 列 プ ロ グ ラム に 変 換 す る 自動 並 列 化 ト
中 間デ ー タ構 造 に 並列 化 の た め の 情 報 を保 存 して 抽 象 構
ラ ンス レー タ の利 用 が 望 ま れ る。 何 故 な ら,逐 次 プ ロ グ
文 木 の 更新 を行 っ て い く。 最 後 に 中間 デ ー タ構 造 の抽 象
ラム の 自動 並 列 化 が 可 能 に な れ ば 既 存 の 逐 次 プ ロ グ ラム
構 文 木 と並 列 化 の た め の情 報 を使 い 並 列 プ ロ グ ラム の 出
力 を行 う。 ま た,並 列 効 果 を 高 め るた め に 並 列性 を抽 出
*1:理
工 学 研 究 科 理 工学 専 攻 博 士 前 期 学 生
*2:理
工 学 研 究 科 理 工 学 専 攻 教 授(kai@st
した後 に,ル ー プ の分 割 や 実行 時 間 を 用 い た ス ケ ジ ュー
リン グ な どの最 適 化 処理 を行 うこ とで,よ
.seikei.ac.jp)
一35一
り並 列 効 果 の
成 践 大 学 理 工 学 研 究 報 告
4.デ
高 い コ ー ドの 生 成 を 行 う[1]。
本 研 究 で は,共
Vol.51No.1(2014.6)
ー タ依 存解 析
有 メ モ リ と 分 散 メ モ リの 両 方 の メ モ リ
デ ー タ依 存 関係 が存 在 す る タス クは 処 理 す る順 番 が 変
方 式 に 対 応 し た 並 列 プ ロ グ ラ ミ ン グ ラ イ ブ ラ リ
規模な並
わ っ て しま う と結 果 も変 わ っ て しま うた め,逐 次 処 理 を
列 実 行 環 境 で も利 用 可 能 に す る こ と を 目標 と して い る 。
行 わ な くて は な らな い。 この デ ー タ依 存 関係 を解 析 す る
ま た 並 列 実 行 可 能 な プ ロ グ ラ ム を ソ ー ス コ ー ドレ ベ ル で
た め に それ ぞれ の タ ス ク 内 で メ モ リ ロケ ー シ ョ ンの ア ク
生 成 す る こ と に よ り機 種 非 依 存 で,ユ
ー ザ に よ る独 自の
セ ス属 性 を解 析 す る。 メ モ リ ロケ ー シ ョ ンの ア クセ ス 属
チ ュ ー ニ ング や コ ンパ イ ラに よ る最 適 化 処 理 を施 す こ と
性 に は読 み込 み(read),書 き込 み(write)が あ り,こ の組 み
が 可 能 に な る[1]。
合 わせ か ら3種 類 の デ ー タ依 存 関係 を解 析 す る こ とが で
MPI(MessagePassingInterface)を
使 う こ と で,大
き る。Figure4.1で は いず れ も変 数Xに よ るデ ー タ依 存 関
3.C言
語 自 動 並 列 化 トラ ン ス レー タ の 処 理 手 順
係 が発 生 して い るた め逐 次 実行 す る必 要 が あ る。
C言 語 で正 しく記 述 され た
逐 次 ソー スコー ド
畢
入力
蟹)綿
鯉ら
C言 語 自 動 並 列 化 トラン ス レー タ
中 間 デ ータ構 造 の 作 成
データ依存解析
タスク粒度解 析
タスクスケ ジュー リング
、一 生成
、
、
竃〉鮮 濁 〉轡 ら
_
中 間 デー タ構 造
読 込み
に
追加 ・更新
元 のソースコードの
抽象 構文 木
Figure4.1デ
ー タ依 存 関係 の種 類
自動並 列化の ため
の情報
逆 に これ らの よ うな デ ー タ依 存 関係 が 無 けれ ば タス ク
並 列 コー ド生成
同 士 は並 列 性 が あ る とみ なす こ とが 出 来 る。
出力
MPIを 使 った 並 列 ソー ス コー ド
5.ポ
Figure3.1C言
イ ンタ解 析
語 自動 並 列 化 トラ ンス レー タ の 処 理 手 順
し か し,4の
Figure3.1はC言
語 自動 並 列 化 トラ ン ス レー タ の 処 理
方 法 だ け で は ポ イ ンタ を 用 い た プ ロ グ ラ
ム に 対 す る デ ー タ 依 存 解 析 を 行 え な い 。Figure5.1は
手 順 を 示 した もの で あ る。 最 初 に 逐 次 プ ロ グ ラム を読 み
Figure4.1のXの
部 分 をポ イ ン タ変数 が 指 して い る メモ リ
込 み,構 文解 析 に よ り抽 象 構 文 木 を持 っ た 中間 デ ー タ構
ロ ケ ー シ ョ ン へ の ア ク セ ス に 書 き 換 え た も の で あ る。
こ の 場 合,ポ イ ン タ 変 数PとQが
造 の 生 成 を行 う。 以 降 の 処 理 は この 中間 デ ー タ構 造 に対
して行 う。
同 じ ロケ ー シ ョ ン を指
して い る な らば それ ぞれ の タ ス ク間 に デ ー タ依 存 関係 が
中 間 デ ー タ構 造 生 成 後 は 中間 デ ー タ構 造 に対 して 並 列
成 り 立 っ 。 し か し,ポ イ ン タPとQが
同 じ ロケ ー シ ョン を
化 可 能 箇 所 を解 析 す るた め に デ ー タ依 存 解 析 を行 う。 初
指 して い な けれ ば それ ぞれ の タス ク問 に デ ー タ依 存 関係
期 段 階 で は タ ス ク粒 度 が ス テ ー トメ ン ト単 位 で あ るた め
は発 生 しな い。
タ ス ク数 が 多 く,後 述 す る タス クス ケ ジ ュー リン グ に時
この よ うに ポ イ ンタ は様 々 な ロケ ー シ ョ ンに ア クセ ス
間 が か か っ て しま う。 そ の た め タス ク粒 度 解 析 を行 うこ
す る 可 能 性 が あ り,プ
とで タ ス ク 数 を 適 切 に 減 少 させ る。 タス ク粒 度 解 析 を行
が どの ロケ ー シ ョ ンに ア ク セ ス す るか が 不 明 の 場 合 が あ
っ た 後 は 処 理 を ま とめ る こ とに よ り通 信 回 数 を減 らす な
る 。 そ の た め,単
ロ グ ラム の 実行 時 ま で は ポ イ ン タ
に コ ー ドに 記 述 さ れ て い る 変 数 を 静 的
ど,実 行 時 間 を 短 縮 す るた め の 変 換 を行 うた め に タス ク
に 読 ん で デ ー タ 依 存 関 係 を 調 べ る こ と は で き な い[2]。 以
ス ケ ジ ュ ー リン グを 行 い,各 プ ロセ ッサ に対 して タス ク
上 の 理 由 か ら,ポ
を適 切 に割 り当 て る。 こ こで は タス ク粒 度 解 析 を行 う前
存 解 析 で は,実
の 段 階 な の で タ ス ク とは ス テ ー トメ ン トの こ とを 指 す 。
に ア ク セ ス す る ス テ ー トメ ン トは 必 ず 逐 次 処 理 を行 う も
の と判 定 す る 。
以 上 の解 析 結 果 の 情 報 を 持 っ た 中間 デ ー タ構 造 を基 に
コー ド生 成 を行 うこ とで 並 列 プ ロ グ ラム が 生 成 され る。
一36一
イ ンタ解 析 を行 わ な い 従 来 の デ ー タ依
行 結 果 を 正 し く得 るた め に ポ イ ン タ変 数
成 践 大 学 理 工 学 研 究 報 告
Vol.51No.1(2014.6)
析 が不 可能 だ っ た。
曜)
structlist{
inti;
蔀)
StrUCtliSt*nxt;
}
晶)
'Q=20
Figure5.3リ
Figure5.1ポ
ス ト構 造 に 使 う構 造 体
イ ンタ が あ った 場 合
1:P=(structlist*)malloc(sizeofてstructlist));
こ の 問 題 に 対 し,points-to解
析 を 行 い,ポ
イ ン タが 指
し て い る ロ ケ ー シ ョ ン を 明 ら か に す る こ と に よ り,新
2:x=P;
3:fbr(i=0;i<N;i++)
た
{
な 並 列性 の解 析 が 可 能 に な る。
4:temp=(structlist*)malloc(sizeofてstructlist));
5:x->nxt=temp;
6:x=x->nxt;
5.1従
来 の ポ イ ンタ 解 析
}
7:x->nxt=0;
従 来 の ポ イ ン タ解 析 で はSSA(静 的 単 一 代 入)形 式 を 使
っ て ポ イ ンタ解 析 を 行 っ て い た[4]。この 方 式 で は ポ イ ン
Figure5.4リ
ス ト構 造 の 作 成
タ が 代 入 され る度 に 新 しい ポ イ ン タ を定 義 しそ れ ぞ れ に
5.2Shape解
どの 変 数 を 指 す の か と言 う情 報 を 付 与 して 解 析 す る 。
析
Figure5.5の
Figure5.2は 実 際 にSSA形 式 に書 き換 え た例 で あ る。
よ うな プ ロ グ ラ ム で ポ イ ン タ が ア ク セ ス
して い る ロケ ー シ ョ ンを解 析 す るた め の解 析 手 法 と して
int★p,aニ5,bニ6,cニ7,dニ8'
Shape解 析 が 挙 げ られ る[4]。Shape解
実 行 せ ず に 動 的 に 割 り 当 て ら れ た デ ー タ の 特 性 を解 析 す
ii≡
勢__2騒
鱗;SSA形
析 とは プ ロ グ ラム を
る 技 術 で あ る 。Figure5.5の
式に
よ うな リス ト構 造 や 二 分 木 等
の 動 的 メ モ リ確 保 に よ り 作 成 さ れ る 再 帰 的 な デ ー タ構 造
講
の 形 状 を 解 析 す る。 これ に よ りポ イ ン タ が ど の ロ ケ ー シ
Figure5.2SSA形
ョ ン を 指 し て い る の か を 明 ら か に し,新
式 へ の 書 き換 え とデ ー タ 依 存 解 析
しい 並 列性 の 検
出 が 可能 に な る。
こ う してSSA形
式 に 書 き換 え たそ れ ぞれ の ポ イ ン タ変
数 に そ れ ぞ れ の 指 し 先 の 変 数 を 保 存 す る 。Figure5.2の
の 場 合,plは
変 数a,p2は
を 保 存 す る。1行
鱒訓 哩難`く む
例
変 数cを 指 して い る と い う情 報
目 でplがwriteさ
れ3行
二分木
目で 使 わ れ て い
Figure5.5再
る た め に こ れ ら の デ ー タ 依 存 関 係 を 認 識 す る 。 同 様 に4
行 目 と5行
目 の デ ー タ 依 存 関 係 を 認 識 す る 。そ し てplは
aを 指 し て い る の で2行
目 と3行
認 識 す る。 書 き 換 え 後,図
5.2.1Shapeグ
目の デ ー タ 依 存 関 係 を
来 のC言
ラ フ と ノー ド
再 帰 的 な デ ー タ 構 造 を 表 現 す る た め にFigure5.6の
中右 側 の 矢 印 で 示 され る よ う
な デ ー タ 依 存 関係 が認 識 され る こ とに な る。
し か し,従
帰 的 な デ ー タ構 造
う なShapeグ
語 自 動 並 列 化 ト ラ ン ス レー タ で は
ラ フ を 作 成 す る 。Shapeグ
ラフ内の円は動的
に 確 保 し た 領 域 を 示 す ノ ー ドで あ り,矢
ポ イ ンタ 変 数 の 指 し先 と して 変 数 の み を扱 っ て い た 。 こ
指 し先,つ
よ
印 は ポ イ ン タの
ま り ロ ケ ー シ ョ ン の リ ン ク で あ る。
れ だ け で は ポ イ ンタ 解 析 を 行 っ て 並 列 性 を見 い だ せ るプ
ロ グ ラ ム が 動 的 な メ モ リ確 保 を 行 わ な い も の に 限 ら れ て
ノー ド
し ま う。
例 え ばFigure5.3の
イ ン タ を 持 つ 再 帰 的 な 構 造 体 が あ り,こ
たFigure5.4の
ラ フ
の 構 造 体 を使 っ
よ う な プ ロ グ ラ ム を 実 行 し た 場 合,リ
5.2.1.1要
ス ト
約(summarize)と
実 体 化(materialize)
語 自 動 並 列 化 トラ ン ス レ
再 帰 的 な デ ー タ 構 造 は 実 行 時 ま で ど の よ うな 規 模 に な
.4に 対 す る デ ー タ 構 造 の 依 存 関 係 の 解
る か は不 明 で あ る。 こ の よ うな 問 題 に 対 し て 要 約
構 造 が 構 成 さ れ る 。 従 来 のC言
ー タ で はFigure5
Figure5.6Shapeグ
よ う な 他 の オ ブ ジ ェ ク トを 指 す ポ
一37一
成 践 大 学 理 工 学 研 究 報 告
(summarize)や
す る た め に リ ン ク 情 報 を 保 存 す る。こ の リ ン ク 情 報 に は,
実 体 化(materialize)を 行 う こ と で あ ら ゆ る
ど の ポ イ ン タ に 指 され て い る か,ポ
規模 の 再 帰 的 な デ ー タ 構 造 に 対 して 対 応 で き る よ うにす
る。Figure5.7は
イ ン タ の 指 し 先,ノ
ー ドの 場 合 は 要 約 を 行 っ て い る の か の 情 報 が 含 ま れ て い
要 約 の一 例 で あ る。 この 図 の 上 部 に描 か
れ て い るShapeグ
Vol.51No.1(2014.6)
ラ フ の 四 角 で 囲 ま れ た部 分 は どの ポ イ
る 。 従 来 の 研 究 で はSSA形
式 で 新 し い 変 数 を 定 義 し,そ
ンタ に も指 され て い な い 。 よっ て これ らの ノー ドに対 し
れ ぞ れ の 変 数 に こ の リ ン ク 情 報 に 相 当 す る 情 報 を保 存 し
て 要 約 を 行 う こ と で 一 つ に ま と め た ノ ー ドで 表 現 し た 。
て い た が 今 回 は ロ ケ ー シ ョ ン を キ ー,リ
P
q
し たmapに
P
保 存 す る 。 こ れ でShape解
ン ク 情 報 を値 と
析 後 のpoints-to解
析 で 同 じ ロケ ー シ ョ ンを キ ー と して ス テ ー トメ ン トご と
コ 、6
に 異 な る リ ン ク 情 報 に ア ク セ ス す る こ と が 可 能 に な る。
体化
5.3.3ス
P「
テ ー トメ ン トの 追 跡 とShapeグ
こ の よ う な ロ ケ ー シ ョ ン を キ ー,リ
q
賞{宣
Figure5.7要
たmapをShapeグ
テ ー トメ ン トな らShapeグ
P
イ ン タに 関 連 す るス
ラ フ の 更 新 を 行 う。
q
5.3.4ル
体化
ー プ で のShapeグ
ラ フの 更 新
ル ー プ 文 に 対 し て ス テ ー トメ ン トの 追 跡 とShapeグ
フ の 更 新 を 行 う際 は,イ
q
と 比 較 しShapeグ
ラ
テ レー シ ョ ンの 最 後 で 要約 を行
っ た 後 に 終 了 条 件 を 満 た す か,前
P「
テ ー トメ ン ト ご と
析 で 使 用 す る 。 中 間 デ ー タ構 造 か
ら ス テ ー トメ ン トの 追 跡 を 行 い,ポ
P
ン ク 情 報 を値 と し
ラ フ と し て 扱 い,ス
に 保 存 し てpoints-to解
約 の 様 子
ラ フの 保 存
イ テ レー シ ョ ンの 形 状
ラ フ の 変 化 を見 込 め な くな る ま で イ テ
レ ー シ ョ ン の 頭 に 戻 り追 跡 を 続 行 す る。こ の よ うにShape
Figure5.8実
体化の様子
グ ラ フ の変 化 を 見 込 め な くな る こ とを 安 定 化 と呼 ぶ こ と
に し た 。Figure5.4の
逆 にShape解
析 で 要 約 さ れ た ノ ー ドを 使 用 す る 際 は 実
体 化 を 行 う。Figure5.8は
r=p->nxtと
約 さ れ た ノ ー ドを 指 そ う と す る 。 しか し,要
5.3.4.1要
約 の様 子
あ る 。 こ の よ う に4行
約 され た ノ
ら分 か る よ うに 実 際 に は複 数 の ノー
ドで あ る。 そ の た め,こ
ラ フ の 更新 を例 に して説 明す る。
Figure5.9はFigure5.4の1周
代 入 す る よ うな 式 に よ っ て ポ イ ン タ を 更 新 した 場 合,要
.7か
の 追 跡 とShapeグ
実 体 化 の 一 例 で あ る。 この 時
い う よ う なpが 指 し て い る ノ ー ド の メ ン バ を
ー ドはFigure5
プ ロ グ ラ ム に 対 す る ス テ ー トメ ン ト
ドの リ ン ク,6行
目 のShapeグ
ラ フの 変 化 で
目で ノ ー ドの 作 成,5行
目で ノー
目 で ポ イ ン タ の 更 新 を行 っ てShapeグ
ラ
フ の 更 新 を 行 っ て い く。
の よ うに 要 約 さ れ た ノ ー ドを 指
そ う と す る よ うな タ ス ク を 解 析 す る 場 合 は 実 体 化 を 行 い,
Xptemp
要 約 さ れ た ノ ー ドか ら 一 つ の ノ ー ドを 取 り出 す 。
4溢(ち
作成
蕊
xptemp
5.3Shape解
析 の実装
5.3.1ノ
5
ー ドの 実 装
従 来 のC言
6
Figure5.9Figure5.4の1周
析 で ノ ー ドを 定 義 し動 的 に 確 保 し た 領 域 を 表
現 す る た め に 抽 象 化 し た ロ ケ ー シ ョ ン を 定 義 して,ロ
ー シ ョ ン を 継 承 す る 形 で ノ ー ドを 定 義 し た
髄
Pxtemp
語 自動 並 列 化 トラ ン ス レ ー タ で は ポ イ ン
タ の 指 し 先 と し て 変 数 し か 存 在 して い な か っ た 。 そ の た
めShape解
ポ インタの書 き換え
目 で のShapeグ
ラ フの 変 化
ケ
こ の ル ー プ の ス テ ー トメ ン トの 追 跡 とShapeグ
。
更 新 を 行 う こ と で3周
5.3.2リ
リンク
ン ク情 報
後 でFigure5.10の
points-to解 析 で ポ イ ン タ と ロ ケ ー シ ョ ン の 関 係 を 参 照
一38一
目 と4周
よ う なShapeグ
ラフの
目 の ス テ ー トメ ン トの 最
ラ フ が 得 られ る 。
成 践 大 学 理 工 学 研 究 報 告
pxtemp
い る ノ ー ドで あ る ノ ー ド11を
xtemp
P
Vol.51No.1(2014.6)
⑩11⑫<蚤
指 す よ う に す る 。 し か し,
5.2.1.1で も 記 述 し た よ うに 要 約 さ れ た ノ ー ドは 複 数 の ノ
ー ドを ま と め た も の で あ る の で
temp-temp
一 つ の ノ ー ドを 取 り 出 す
需,⑩
ノー ド12を要 約
・
㊦
安定化
3周
目 と4周
目 のShapeグ
目の 最 後 の ス テ ー トメ ン トのShapeグ
ー ド11と
ノ ー ド12が
以 上 で あ る ノー ド
そ し て ポ イ ン タ 変 数xは こ の ノ ー ド12を
4周 目
Figure5.4の3周
。 つ ま り2個
11に 対 し て 実 体 化 を 行 い 一 つ の ノ ー ド12を
取 り出 す 。
ノー ド13を要 約
3周 目
Figure5.10
,要 約 さ れ た ノ ー ドか ら
指 す よ うに す る。
ラ フ
ラフでは ノ
どの ポ イ ン タ変 数 に も指 され て お
ら ず 連 続 し て い る 。 よ っ て こ れ ら の ノ ー ドは 要 約 を 行 い
一 つ の ノ ー ドで 表 現 す る
。 要 約 を 行 う際 に,ど
の ノー ド
(亜)-11
を 要 約 した の か を 保 存 しpoints-to解 析 で 同 じ ロ ケ ー シ ョ
ン で あ る 可 能 性 の あ る ノ ー ド を 解 析 す る 。4周
に ノ ー ド11と
ノ ー ド13を
1個 以 上
目も同 様
Figure5.13Figure5.12で
要 約 す る。
の1周
Shapeグ
3周
目 と4周
目で 同 じ形 状 で あ る こ と を 解 析 す る の で
こ の ル ー プ で の ス テ ー トメ ン トの 追 跡 を 終 了 す る 。 ま た
Figure5.10は
あ く ま で も ル ー プ の3周
フ で あ る。 し か し,実
限 ら ず0∼2周
よ うな0∼2周
目の 再 代 入 式 で の
ラ フの 変 化
目以 降 のShapeグ
行 時 に ル ー プ が3周
こ う し て 一 度 実 体 化 し て ノ ー ドを 一 つ 取 り出 し た ノ ー
ラ
ドは2個
以 上 す る とは
て い る ノ ー ド と な る。 以 降,ノ
目 の 場 合 も あ る 。 そ の た め,Figure5.llの
目 で 得 ら れ たShapeグ
の ス テ ー トメ ン トの 追 跡 でShape解
以 上 を ま と め て い る 状 態 か ら1個
は ノ ー ドllが
ラ フ に 対 して も 以 降
場 合,つ
析 を 行 う。
ー ド11の
ま り ノ ー ド11が1個
で あ る 場 合 と2個
状 態 と 場 合 分 け を 行 っ てShapeグ
Pxtemp
"
Figure5.110∼2周
以上の
ラ フ の 更新 を行 っ て い
示す。
2周
1周
圖
実 体 化 を行 う際
要 約 され て い な い 場 合 と 要 約 さ れ て い る
く こ と に な る 。 そ の 様 子 をFigure5.14で
0周
以 上 をま と め
pxtemp
⑩ 題 一(
⊥ 一_こ淫
rr■7/u∼
目 のShapeグ
「u
ラ フ
①
ノー ド11が要 約
ノー ド11が要 約
され てい る
され ていな い
一
煙 〉⑬<釜
3周 目
5.3.4.2実
ノー ド11が要 糸1
され ていな い
体化の様子
Figure5.4の
プ ロ グ ラ ム の 続 き で あ るFigure5.12の
安定,1・
グ ラ ム に 対 す る ス テ ー トメ ン トの 追 跡 とShapeグ
プ ロ
一・
あ
一⑭(釜
(匝〉(釜
ラ フの
ノー ド11が 要約
され て いない
更 新 を 例 に して 安 定 化 す るま で の 実 体 化 の 様 子 を説 明 す
①
る。
max=0;
for(x=P;x!=0;x=x->nxt){
if(max<x->i)
max=X->1;
一({)・[(lii})
Figure5.14Figure5.12で
ノ ー ドllを3周
Figure5.12リ
の2周
目 以 降 のShapeグ
ラ
フの 変 化
ス ト構 造 か ら最 大 値 を 求 め る プ ロ グ ラ ム
析 す る 。 つ ま り,リ
目で 要約 され て い な い もの と して解
ス ト構 造 の 要 素 が3つ
だった場合は
xが 全 て の 要 素 を 確 認 した 後 に 終 了 条 件 を 満 た し て ル ー
Figure5.13はFigure5.12で1周
目終 了 時 の 再 代 入 式 に
フ.での ス テ ー トメ ン トの 追 跡 を 終 了 す る。ノ ー ド11が
対 す る ス テ ー トメ ン トの 追 跡 を 行 っ た 際 のShapeグ
ラフ
約 さ れ て い る も の と し てShapeグ
の 変 化 で あ る。 再 代 入 式 はx=x->nxtで
あ る の で,xを
上書
っ た 場 合,5周
き し,元 々xが 指 して い た ノ ー ド10の
メ ン バnxtで 指 して
目 で4周
要
ラ フ の 更新 を続 け て い
目 と 同 じ 形 状 のShapeグ
ラ フ とな
り安 定 化 し た と解 析 し こ の ル ー プ で の ス テ ー トメ ン トの
一39一
成 践 大 学 理 工 学 研 究 報 告
6.並
追 跡 を 終 了 す る。
ま たFigure5.15は5周
る。 ノ ー ド14及
目で の 要 約 前 のShapeグ
び ノ ー ド15は
Vol.51No.1(2014.6)
列性 の解 析
ラ フで あ
両 方 共 ノ ー ドllか
ら実
以 上 の よ う にShape解
析 を行 い 中 間 デ ー タ 構 造 に そ れ
体化 した もの で あ る。 実 体 化 は 複 数 に ま と め られ た ノー
ぞ れ の タ ス ク で のShapeグ
ドか ら 一 つ の ノ ー ド を 取 り 出 す た め 違 うIDの
れ に よ りpoints-to解 析 で も こ の 情 報 を 参 照 で き る よ うに
ノ ー ドで
ラ フ を 明 ら か に し保 存 す る 。こ
も同 じロケ ー シ ョンで あ る可 能性 が あ る。 そ の た め
な る 。 つ ま り,Shapeグ
Figure5.15の
の ロケ ー シ ョ ンを指 して い るの か の 情報 が 参 照 可 能 に な
よ うに 違 う ロ ケ ー シ ョ ン で あ る こ と が 明 ら
か で あ る 場 合 はpoints-to解 析 で ポ イ ン タ が そ れ ぞ れ 違 う
り,こ
ロ ケ ー シ ョ ン を 指 し て い る こ と を 示 す た め に ノ ー ド14
合 わせ る こ とに よっ て 再 帰 的 な デ ー タ構 造 に 対 して もデ
と ノ ー ド15が
ー タ依 存 解 析 が 可能 に な る
違 う ロ ケ ー シ ョ ン で あ る と 言 う情 報 を 付
の 情 報 と4で
ラ フの 情 報 を参 照 しポ イ ン タが ど
。
与 し て お く。
Figure5.12の4周
ノー ド11か ら実 体 化
ノー ド15と は 違 うロ ケ ー シ ョン
述 べ た よ うな デ ー タ 依 存 解 析 と組 み
目及 び5周
目 で のShapeグ
つ の イ テ レ ー シ ョ ン の 最 後 のShapeグ
ノー ド11か ら実 体 化
ノー ド14と は 違 うロケ ー シ ョン
は あ る が4周
ラ フ は 同 じ形 状 で
目 でxが 指 し て い る ノ ー ドのIDは14で
5周 目 で 指 し て い る ノ ー ドは ノ ー ド14で
噸〉参 ⑭ 〈奪
〉㊦
る 。 これ ら はFigure5.15で
px
ラ フか ら二
解 析 した 情 報 か ら異 な る ロケ
ー シ ョン を指 して い る こ とが 分 か る
Figure5.15Figure5.12の
追 跡5周
Shapeグ
。 つ ま り,3周
目で の 要 約 前 の
あ り,
あ る こ とが 分 か
目以
降,デ ー タ 依 存 解 析 時 にxが 指 し て い る ロ ケ ー シ ョ ン が イ
ラ フ
テ レ ー シ ョ ン ご と に 異 な る事 を 解 析 で き た 。
ま た4周
目及 び5周
目で ノ ー ド11を
し た 場 合,Figure5.16の
よ うにShapeグ
これ は ス カ ラ エ ク ス パ ン シ ョ ン の 特 殊 ケ ー ス で あ る 。
単体 と して実 体 化
つ ま りFigure6.1の
ラ フ が 変 化 し,リ
ス ト構 造 の 全 て の 要 素 を 確 認 し た 上 で 終 了 条 件 を 満 た す 。
よ う に リ ス ト構 造 を プ ロ セ ッ サ ご と
に 区 切 っ て 並 列 処 理 で そ れ ぞ れ の リ ス ト構 造 で 最 大 値 を
求 め た後 に それ ぞれ の プ ロセ ッサ で の 最 大値 の 中か ら さ
(亘 》12
らに最 大 値 を 求 め る こ とで 逐 次 実行 と同 じ結 果 を出 す こ
と が 可 能 で あ る。
面
Figure5.163周
●6
畢
目 以 降 で ノ ー ド11が
● →ai)_●_6
要 約 され て い な
い場 合
畢
作 成 す る 部 分 が 実 行 時 に0∼1周
り リ ス ト構 造 の 要 素 数 が1∼2個
で の リス ト構 造,つ
ま
だ っ た 場 合 のShapeグ
ラ
⑭
それ ぞ れ のプロセッサ で最大 値 を
求 め る処 理 を行う
…o
畢
それぞれの最大値の中で
の最大値を求める
フ に 対 し て ス テ ー トメ ン トの 追 跡 を 行 っ た 結 果 はFigure
5.17と な る 。 つ ま り,い
分 割(それ ぞれ の プロセッサ
でリスト構 造 の 生 成)
⑭EO
ず れ の 場 合 も リス ト構 造 の 全 て
逐 次実 行 と同 じ
結果
の 要 素 を確 認 す る こ とが 分 か る。
餓
2個 だった場 合
1個 だった場 合
Figure6.1Figure5.12の
Figure5.12を
並 列 化 案
並 列 化 し た も の がFigure6.2で
あ る。 そ れ
①ー
ぞ れ の フ.ロセ ス で 元 の リ ス ト構 造 の 要 素 数 を プ ロ セ ス 数
で 割 っ た 数 だ け の リ ス ト構 造 を 作 成 し デ ー タ を 入 力 し て
い た も の とす る。 そ れ か ら そ れ ぞ れ の プ ロ セ ス で 最 大 値
を 求 め た 後 にMPIReduce命
令 で 全 て の プ ロセ ス の 最 大
値 の 中 で の 最 大 値 を 求 め る こ と が 出 来 る。
Figure5.17リ
ス ト構 造 が1個
か2個
だ った 場 合
一40一
成 践 大 学 理 工 学 研 究 報 告
〃元 の コ ー
Vol.51No.1(2014.6)
ドと 同 じで そ れ ぞ れ の プ ロセ ス で 最 大 値
⑦
を求 め る
fbr(x=p;x!=0;x=x->nxt){
6周 目
⑩(⑱
⑭
ifてmax<x->i)
max=X->1;
}
oldtablenptrnewtable
〃MASTERに
MPI
計算 結 果 を集 め る
⑦(③
_Reduce(&max,&recv,1,MPI_INT,MPI_MAX,MAS
TER,MPI
一
⑱
_COMM_WORLD);
一く
⑳ ・
一くii])'
7周 目
optr
Figure6.2Figure5.12の
Figure7.3
並 列 化
6周 目で ノー ド14が 要 約 され て いな い も
の と して実 体 化 した場 合
エ イ トマ 7.hmmerに
対 す るShape解
析
つ ま り,Figure7.1の
プ ロ グ ラ ム 実 行 時 に リス ト構 造 が い
くつ で あ っ た と し て も リ ス ト構 造 を 逆 順 に す る こ と を解
本 研 究 の 評 価 と し て 使 っ た 逐 次 プ ロ グ ラ ム はhmmerで
あ る。hmmerはSPECCPU2006[6]の
り遺 伝 子 配 列 の 検 索 を 行 う。Figure7.1はhmmerの
書 き 換 え た も の で あ り リ ス トoldtableを
ト,newtableが
析 で き た 事 に な る。
ベ ンチ マ ー クー つ で あ
こ の よ う に ベ ン チ マ ー ク に 対 し て もShapeグ
一部 を
築 しポ イ ン タ が どの ロケ ー シ ョ ンを 指 す の か が 明 らか に
逆 順 に し た リス
な りデ ー タ 依 存 解 析 で 使 う こ と が 可 能 に な っ た 。
得 ら れ る。
8.終
new
_table-malloc(sizeof(遺
optr=old
ラ フ を構
伝 子
の
リ ス
わ りに
ト));
_table;
今 回 の 研 究 でShapeグ ラ フ を構 築 し再 帰 的 なデ ー タ構
while(optr!=0){
nptr=new
new
_table;
造 の形 状 が解 析 可能 に な り,そ の 中で ポ イ ン タが どの ロ
_table=optr;
ケ ー シ ョン を指 して い るの か,指 す 可 能性 が あ るの か を
optr=optr->nxt;
new
_table->nxt=nptr;
解 析 で き る よ うに な っ た。 これ に よ りこれ ま で 不 明 だ っ
}
た並 列 性 が解 析 可能 に な っ た。 そ して,リ ス ト構 造 を分
Figure7.1hmmerの
割 しそれ ぞれ の プ ロセ ッサ で 処理 す る例 を示 した。 さ ら
一 部
に 実 際 にベ ン チ マ ー ク に 対 して解 析 した と こ ろ,Shape
こ れ に 対 し てShape解
ン 内 部 の3行
析 を 行 っ た と こ ろ,イ テ レー シ ョ
目 の タ ス ク で のShapeグ
解 析 をす る こ とが 可能 で あ る こ とを確 認 した。
ラフ の 更 新 を行 う
この よ うにイ テ レー シ ョ ンや タ ス ク ご とのShapeグ
ラ
際 に 複 数 の ノ ー ド と し て 実 体 化 を 続 け た 場 合,Figure7.2
フ の変 化 が 明 らか に な りデ ー タ依 存 関係 が 分 か る よ うに
の よ うに5周
な っ た こ とで 人 手 に よ る並列 化 は 可 能 に な っ た。 今 後 の
目 と6周
目の イ テ レー シ ョ ン 終 了 時 に 同 じ
課 題 と して は 並列 コー ドの 自動 生成 に 対応 させ る こ とで
形 状 と な り安 定 化 し た 。
ま た,Figure7.3の
よ う に 一 回 で もIDが14の
一 個 の ノ ー ド と し て 実 体 化 す れ ば い ず れ はoptrが14に
動 し 次 に0を
あ る。 ま た イ ンタ プ ロシ ー ジ ャに 対応 させ る こ とで よ り
ノ ー ドを
移
多 くの プ ログ ラム に 対応 させ る事 が で き る よ うに す る こ
とが考 え られ る。
指 し ス テ ー トメ ン トの 追 跡 は 終 了 す る 。
①(⑱
9.参
一
⑰ 一
一(嘩D
5周 目
optrnptr
oldtable
[1]KazuhiroMinomoto:"ImplementationsofAutomatic
⑳
17'⑬
⑭newtable
一⑯
安定化
TranslatorfromCprogramtoParallelProgramsusing
MPI",修
一(麺)
士 論 文,成
膜 大 学 工学 部 工 学 研 究 科 情 報 処
理 専 攻,2005.
optr
・ldt・bl・
考 文献
⑩(ll>ppt「newt・bl・
6周 目
[2]SumiyaTohyama:"lmplementationsofParallelism
AnalysisandDynamicExecutionControllerfbr
Figure7.2Figure7.1に
対 す るShape解
AutomaticallyParallelizingSequentialCPrograms",修
析 の 一 部
一41一
成 践 大 学 理 工 学 研 究 報 告
士 論 文,成
膜 大 学 工 学 部 工 学 研 究 科 情 報 処 理 専 攻,
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
一42一
Vol.51No.1(2014.6)

市川市民としてのあり方、後編

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