博博博博 士士士士 論論論論 文文文文 概概概概 要要要要

早稲田大学大学院情報生産システム研究科

博 博

博 士 博 士 士 論 士 論 論 論 文 文 概 文 文 概 概 要 概 要 要 要

論 論

論 論 文 文 文 文 題 題 題 題 目 目 目 目

D a t a - p a t h O p t i m i z a t i o n i n H i g h - l e v e l S y n t h e s i s

高 位 合 成

高 位 合 成 高 位 合 成

高 位 合 成 に お け る に お け る に お け る に お け る デ ー タ パ ス デ ー タ パ ス デ ー タ パ ス デ ー タ パ ス 最 最 最 最 適 化

適 化 適 化

適 化 に に に 関 に 関 関 す る 関 す る す る 研 究 す る 研 究 研 究 研 究

申 請 者

土 井 伸 洋 Nobuhiro Doi

情報生産システム工学専攻 高位検証技術研究

２ ０ ０ ５ 年 １ ２ 月

電 子 回 路 の 微 細 化 技 術 が 急 速 に 進 歩 す る に つ れ 、 設 計 さ れ る 回 路 は ま す ま す 複 雑 か つ 大 規 模 な も の と な っ て き て お り 、 動 画 像 や 音 声 情 報 を リ ア ル タ イ ム で 処 理 す る LSI（ Large Scale Integration, 大 規 模 集 積 回 路 ） で は 数 百 万 か ら 数 千 万 個 も の ト ラ ン ジ ス タ が 集 積 さ れ て い る 。従来 こ の よ う な 大 規 模 LSIを 設 計 す る 際 に は 、 設 計 者 が ハ ー ド ウ ェ ア 記 述 言 語 （ Hardware Description Language,

HDL） を 用 い て レ ジ ス タ 転 送 レ ベ ル （ Register Transfer Level, RTL） の 記 述 を 行 い 、 論 理 合 成 ツ ー ル を 適 用 す る こ と で 目 的 の ネ ッ ト リ ス ト を 生 成 し て い た 。 し か し 、増 え 続 け る 回 路 規 模 に 加 え て 設 計 期 間 の 短 縮 化 と い う 理 由 に よ り 、HDL を 用 い た 回 路 設 計 か ら よ り 抽 象 度 を 高 め た 記 述 言 語 を 用 い た 設 計 手 法 に 注 意 が 払 わ れ る よ う に な っ て き た 。 中 で も 、 C 言 語 な ど の プ ロ グ ラ ミ ン グ 言 語 を 用 い て 、 抽 象 度 の 高 い レ ベ ル で ハ ー ド ウ ェ ア の 機 能 を 記 述 し 、 ネ ッ ト リ ス ト を 自 動 生 成 す る ハ ー ド ウ ェ ア の 高 位 合 成 手 法 の 研 究 開 発 が 盛 ん に 行 わ れ て い る 。

C 言 語 で 記 述 さ れ た ハ ー ド ウ ェ ア の 機 能 は 、 構 文 解 析 と 意 味 解 析 が 行 わ れ た 後 、 制 御 を 表 す コ ン ト ロ ー ル フ ロ ー グ ラ フ と 、 そ の グ ラ フ の 各 節 点 に 対 応 す る 演 算 の 依 存 関 係 を 表 す デ ー タ フ ロ ー グ ラ フ に 変 換 さ れ 、 そ の 上 で 最 適 化 の 処 理 が 行 わ れ る 。 最 適 化 で は 、 と く に デ ー タ フ ロ ー グ ラ フ に お い て 、 演 算 を ど の ク ロ ッ ク で 行 う か を 決 定 す る ス ケ ジ ュ ー リ ン グ と 、 演 算 の 実 演 算 器 へ の バ イ ン デ ィ ン グ が 行 わ れ る 。 こ の と き 、 レ ジ ス タ シ ェ ア リ ン グ と 演 算 器 の シ ェ ア リ ン グ が 行 わ れ る 。ハー ド ウ ェ ア の 実 現 で は 、実行 時 間 と 面 積 が も っ と も 重 要 で あ る 。 C 言 語 で の 機 能 記 述 で は 、 デ ー タ は 整 数 や 浮 動 小 数 点 な ど 事 前 に 定 義 さ れ た 型 で 表 さ れ る 。 こ の 時 、 演 算 は プ ロ セ ッ サ 内 に あ る 一 定 の ビ ッ ト 幅 の 演 算 器 で 行 わ れ る 。 一 方 ハ ー ド ウ ェ ア に よ る 機 能 の 実 現 で は 、 任 意 の ビ ッ ト 幅 の レ ジ ス タ と 演 算 器 を 構 成 可 能 で あ り 、 固 定 長 の ビ ッ ト 幅 と は 相 容 れ な い 。 ま た 、 演 算 器 に 関 し て も 、 任 意 の ビ ッ ト 幅 の 演 算 器 を 構 成 可 能 で あ る と 同 時 に 、 応 用 に 応 じ て 専 用 の 演 算 器 を 構 成 可 能 で あ る 。 ま た 、 整 数 演 算 器 に 比 較 し て 、 浮 動 小 数 点 演 算 器 は 遅 延 お よ び 面 積 の 点 で 大 き く な る の で 、ハー ド ウ ェ ア 化 で は 整 数 (固 定 少 数 点 数 )に 変 換 し て 処 理 さ れ る こ と が 多 い 。

こ れ ま で ビ ッ ト 幅 の 最 適 化 と 浮 動 小 数 点 数 の 固 定 小 数 点 数 へ の 変 換 は 人 手 で 行 わ れ る こ と が 多 か っ た 。 こ の た め 、 ほ と ん ど の 高 位 合 成 系 で は ビ ッ ト 幅 の 指 定 が で き る よ う な 拡 張 が 行 わ れ て い る 。 し か し 、 人 手 で 行 う た め に 最 適 値 に す る の が 困 難 で あ る 他 、 指 定 し た ビ ッ ト 幅 で 十 分 か ど う か の 判 定 に シ ミ ュ レ ー シ ョ ン な ど で 大 き な 労 力 を 必 要 と し た 。 そ こ で 本 論 文 で は 、 浮 動 小 数 点 演 算 を 整 数 演 算 に 変 換 す る 部 分 と 、 そ の 時 の 最 適 な ビ ッ ト 幅 の 自 動 最 適 化 に 取 り 組 み 、 誤 差 解 析 手 法 に 基 づ く 最 適 化 ア ル ゴ リ ズ ム を 提 案 し 、 高 位 合 成 に お け る デ ー タ パ ス の 最 適 化 手 法 を 示 し て い る 。

第 一 章 は 、 導 入 部 と し て 、 高 位 合 成 手 法 の 概 要 と 関 連 す る こ れ ま で の 研 究 に つ い て 述 べ る 。 ま た こ れ ま で の 手 法 の 問 題 点 を 明 確 に し て 、 本 論 文 で 扱 う 問 題 に つ い て 述 べ る と と も に 、 研 究 の 目 的 を 明 確 に す る 。

第 二 章 で は 、 準 備 と し て 、 C言 語 の 構 文 解 析 や 意 味 解 析 、 デ ー タ 型 、 各 デ ー タ 型 の 演 算 器 に つ い て 述 べ る 。 ま た ハ ー ド ウ ェ ア 実 現 の 対 象 で あ る セ ル ベ ー ス の LSIお よ び Look Up Table に 基 づ く FPGA (Field Progarmmable Gate Array)

の 特 徴 に つ い て 述 べ る 。

第 三 章 で は 、 本 論 文 で 提 案 す る 高 位 合 成 シ ス テ ム の 概 要 に つ い て 述 べ る 。 高 位 合 成 で は ま ず 、 構 文 解 析 、 意 味 解 析 に よ り 記 述 の 制 御 情 報 と 演 算 の 情 報 を 抽 出 し 、 グ ラ フ を 用 い て モ デ ル 化 し た コ ン ト ロ ー ル ・ デ ー タ ・ フ ロ ー ・ グ ラ フ (Control Data Flow Graph, CDFG) を 生 成 し 、 そ の 上 で 種 々 の 最 適 化 を 行 う 。 具 体 的 に は 、 定 数 伝 播 、 結 合 則 を 用 い た 演 算 の 均 衡 化 、 演 算 の 実 行 ク ロ ッ ク を 決 定 す る ス ケ ジ ュ ー リ ン グ 、 演 算 の チ ェ イ ニ ン グ 、 パ イ プ ラ イ ニ ン グ 、 演 算 器 と 演 算 を 結 び つ け る バ イ ン デ ィ ン グ な ど で あ る 。 こ こ で は そ れ ら に つ い て 述 べ る と と も に 、C言 語 の デ ー タ 型 の ビ ッ ト ス ト リ ン グ へ の マ ッ ピ ン グ と 、ビ ッ ト 幅 を 決 定 す る 問 題 に つ い て 述 べ 、 ビ ッ ト 幅 が デ ー タ パ ス の 面 積 と 速 度 に 及 ぼ す 影 響 と そ の 最 適 化 問 題 に つ い て 示 す 。 ま た 、 浮 動 小 数 点 型 に つ い て は 、 型 の 変 換 に つ い て も 述 べ る 。

第 四 章 で は 、 浮 動 小 数 点 型 の 固 定 小 数 点 型 へ の 変 換 お よ び ビ ッ ト ス ト リ ン グ へ の マ ッ ピ ン グ に お い て 、 ビ ッ ト 幅 を 決 定 し て デ ー タ パ ス を 最 適 化 す る と い う 問 題 に つ い て 述 べ る と と も に 、 ビ ッ ト 幅 を 決 定 す る ヒ ュ ー リ ス テ ィ ッ ク な 手 法 を 提 案 す る 。 本 手 法 に お い て は 、 従 来 法 で 問 題 と な っ て い た 大 量 の 実 デ ー タ を 用 い た 時 間 の か か る シ ミ ュ レ ー シ ョ ン を な く す た め 、 浮 動 小 数 点 演 算 に お い て 発 生 す る 演 算 誤 差 を 、 区 間 演 算 に よ り 解 析 的 に 求 め る 手 法 を 提 案 し て い る 。 入 力 の デ ー タ フ ロ ー グ ラ フ に 対 し て 、各演 算 で 生 成 す る 誤 差 を 計 算 す る と 同 時 に 、 そ の 誤 差 を 伝 播 さ せ る 処 理 を 行 う 。 誤 差 解 析 に よ り 得 ら れ た 誤 差 と 、 そ の 変 数 で 必 要 と さ れ る 演 算 精 度 の 関 係 で 変 数 （ お よ び 演 算 器 ） の ビ ッ ト 幅 が 決 定 さ れ る 。 一 般 に 出 力 の 演 算 精 度 の み が 指 定 さ れ る こ と が 多 い の で 、 各 演 算 の 必 要 精 度 を 計 算 す る に は 、 外 部 出 力 か ら 外 部 入 力 側 に た ど っ て 決 定 す る 必 要 が あ る 。 そ こ で 本 手 法 で は 、 演 算 の 段 数 と 誤 差 の 値 を 用 い て 、 ヒ ュ ー リ ス テ ィ ッ ク に 演 算 の 必 要 精 度 を 割 り 当 て る と い う 手 法 を 提 案 し て い る 。 提 案 手 法 に よ り 得 ら れ た ビ ッ ト 幅 は 、 す べ て の 入 力 に 対 し て 十 分 な 精 度 を 保 証 す る と 同 時 に 、 シ ミ ュ レ ー シ ョ ン に 基 づ く 手 法 に 比 較 し て 非 常 に 高 速 で あ る と い う 利 点 を 有 す る 。 本 手 法 を い く つ か の 例 題 に 適 用 し た 結 果 で は 、 手 作 業 に よ る 試 行 錯 誤 的 な 最 適 化 で は 簡 単 な プ ロ グ ラ ム に 対 し て も 最 低 で 1時 間 程 度 を 必 要 と し て い た 問 題 に 対

し て 、 数 十 秒 で 最 適 化 を 完 了 で き る こ と を 確 認 し た 。

第 五 章 で は 、 浮 動 小 数 点 型 の 固 定 小 数 点 型 へ の 変 換 お よ び ビ ッ ト ス ト リ ン グ へ の マ ッ ピ ン グ に お い て 、 ビ ッ ト 幅 を 決 定 し て デ ー タ パ ス を 最 適 化 す る と い う 問 題 に つ い て 、 厳 密 な 最 適 解 を 求 め る と い う 問 題 に 取 り 組 み 、 ビ ッ ト 幅 の 最 適 化 を 非 線 形 計 画 問 題 に 帰 着 し て 、 非 線 形 計 画 問 題 の ア ル ゴ リ ズ ム を 適 用 し て 解 く 手 法 を 提 案 し て い る 。 ま た 、 同 時 に 誤 差 の 解 析 に お い て は 正 と 負 の 誤 差 を 分 け て 扱 う 手 法 を 提 案 し て い る 。 非 線 形 問 題 で の 帰 着 に お い て は 、 各 変 数 の 誤 差 を 表 す 誤 差 変 数 を 導 入 し 、 デ ー タ フ ロ ー グ ラ フ 上 で 、 誤 差 変 数 の 式 を 伝 播 し て ゆ く 。 加 減 算 で は 一 次 の 式 と な る が 、 乗 除 算 で は 二 次 以 上 の 項 が 発 生 し 、 非 線 形 の 式 で 定 式 化 す る 必 要 が あ っ た 。 ま た 、 ビ ッ ト 幅 の 決 定 に お い て 、 レ ジ ス タ の 共 有 や 演 算 器 の 面 積 に 関 す る 制 約 を 非 線 形 問 題 に 組 み 入 れ る 手 法 も 提 案 し 、 一 元 的 に 最 適 解 を 得 る こ と が で き る よ う に な っ て い る 。 非 線 形 計 画 問 題 を 解 く ア ル ゴ リ ズ ム と し て は 、 SPF に 基 づ く 手 法 を 用 い て い る 。 本 手 法 を 実 現 し 、 い く つ か の 最 適 化 問 題 に 適 用 し た と こ ろ 、 ビ ッ ト 幅 に つ い て 人 手 に よ る 最 適 化 と 同 程 度 の 最 適 化 結 果 が 非 常 に 短 い 時 間 で 得 ら れ る こ と を 示 し た 。 こ れ ま で の 手 法 で は 、 誤 差 の 解 析 で は 通 常 線 形 近 似 が 用 い ら れ て き た が 、 提 案 手 法 に よ り 、 線 形 近 似 の 必 要 が な く な り 、 厳 密 解 が 得 ら れ る よ う に な っ た 。 さ ら に 、 問 題 を 非 線 形 計 画 問 題 と し て 扱 う こ と で 、 変 数 や 演 算 器 の 制 約 、 演 算 器 共 有 と い っ た 制 約 を 容 易 に 取 り 扱 う こ と が で き る と い う 利 点 も 備 え て い る 。

第 六 章 で は 、 高 位 合 成 に お け る デ ー タ パ ス の 最 適 化 手 法 に つ い て の ま と め と し て 、 提 案 し た 二 つ の 方 式 に つ い て 述 べ る と と も に 、 高 位 合 成 に お け る デ ー タ パ ス の 最 適 化 に 関 す る 今 後 の 課 題 に つ い て 述 べ る 。