博士論文審査結果報告書

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

博士論文審査結果報告書

論 文 題 目

L e a k a g e P o w e r 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

申 請 者

情報生産システム工学専攻 最適化技術研究

2014 年 9 月

2

半 導 体 集 積 回 路 の 複 雑 さ が 増 大 す る に つ れ て 、 設 計 期 間 の 短 縮 が 大 き な 問 題 と な り 、 高 位 合 成 へ の 期 待 が 高 ま っ て い る 。 高 位 合 成 と は C 言 語 な ど に よ る 回 路 の 動 作 レ ベ ル 記 述 と 設 計 の 制 約 条 件 か ら 、 回 路 構 造 の 記 述 を 自 動 的 に 生 成 す る も の で あ る 。 高 位 合 成 に お い て 、 近 年 、 特 に 重 要 な 課 題 と な っ て い る の が 消 費 電 力 の 削 減 で あ る 。 特 に 、 半 導 体 の プ ロ セ ス 技 術 の 微 細 化 に よ り 、 動 作 と は 関 係 無 く ト ラ ン ジ ス タ の 内 部 か ら 漏 れ 出 す “ リ ー ク 電 流 ” に 基 づ く リ ー ク 電 力 が L S I の 総 消 費 電 力 の 大 き な 比 率 を 占 め る よ う に な っ て い る 。 リ ー ク 電 力 削 減 の 代 表 的 な 手 法 と し て 、( 1 ) 動 作 し て い な い 回 路 へ の 給 電 を 止 め る パ ワ ー ゲ ー テ ィ ン グ 手 法 と 、( 2 ) ト ラ ン ジ ス タ の リ ー ク 電 力 に 大 き な 影 響 を 与 え る 閾 値 電 圧 ( T h r e s h o l d V o l t a g e ) を 調 整 す る 手 法 が 知 ら れ て い る 。

本 研 究 で は 、 高 位 合 成 に お け る 、 演 算 器 毎 の ト ラ ン ジ ス タ の 閾 値 電 圧 調 整 に よ る リ ー ク 電 力 削 減 問 題 に 取 り 組 ん で い る 。 こ れ は 、 閾 値 電 圧 を 上 げ る と 回 路 動 作 が 遅 く な る か わ り に リ ー ク 電 力 が 減 少 し 、 閾 値 電 圧 を 下 げ る と そ の 逆 に な る 特 性 を 活 か し て 、 各 演 算 器 の 閾 値 電 圧 を 調 整 す る こ と に よ り 、 要 求 性 能 を 満 た す 範 囲 内 で 、L S I の リ ー ク 電 力 を 最 小 化 す る 問 題 で あ る 。こ の 問 題 に 対 し て 、 こ れ ま で 、 ( 1 ) 最 大 フ ロ ー ア ル ゴ リ ズ ム に 基 づ く 手 法 ( L i n , I S Q E D 2 0 1 1 ; W a n g , I E E E T a n s . C A D 2 0 0 2 ) 、 ( 2 ) ク リ テ ィ カ ル パ ス お よ び 非 ク リ テ ィ カ ル パ ス の 抽 出 に よ る 手 法 ( M o h a n t y , I E T C D T 2 0 0 8 ) 、 ( 3 ) 重 み 付 き 最 大 独 立 集 合 ( M W I S ) に 基 づ く 手 法 ( T a n g , D A C 2 0 0 5 ) な ど が 提 案 さ れ て い る 。 し か し 、 ( 1 ) は 高 位 合 成 よ り も 下 位 の 設 計 段 階 で あ る ゲ ー ト レ ベ ル で の 最 適 化 手 法 で あ り 電 力 削 減 効 果 が 限 定 的 で あ る 。( 2 ) は 高 位 合 成 で の 最 適 化 を 扱 っ て い る も の の 、使 用 可 能 な リ ソ ー ス ( 演 算 器 ) に 関 す る 制 約 条 件 を 考 慮 し て い な い 。 ( 3 ) の 手 法 は 高 位 合 成 を 対 象 と し 、 こ れ ら の 内 で は 最 も 現 実 に 即 し て い る が 、各 々 の 演 算 器 が 実 行 す る 演 算 の 集 合 、 す な わ ち リ ソ ー ス シ ェ ア リ ン グ を 固 定 し て 解 い て い る た め 、 探 索 範 囲 が 制 限 さ れ 、 解 の 品 質 に 問 題 が 残 る 。

本 論 文 で は 、 高 位 合 成 の 主 要 な 問 題 で あ る 、 ス ケ ジ ュ ー リ ン グ 問 題 と レ ジ ス タ 割 当 て 問 題 を 対 象 と し 、 閾 値 電 圧 を 最 適 化 す る こ と に よ っ て リ ー ク 電 力 を 削 減 す る 3 種 類 の 新 し い 手 法 を 提 案 し て い る 。 以 下 に 、 各 章 ご と の 概 要 を 述 べ 、 評 価 を 加 え る こ と と す る 。

第 １ 章 “ I n t r o d u c t i o n ” で は 、 ま ず 、 ス ケ ジ ュ ー リ ン グ 問 題 や 、 演 算 器 、 レ ジ ス タ 等 の 回 路 を 構 成 す る リ ソ ー ス の 割 り 付 け 問 題 な ど 、 L S I の 高 位 レ ベ ル 設 計 の 一 連 の 問 題 を 紹 介 し て い る 。 次 に 、 リ ー ク 電 流 の 原 因 と な る い く つ か の 要 素 を 紹 介 し 、 リ ー ク 電 力 最 小 化 に 関 す る 既 存 手 法 を 紹 介 し て い る 。

第 2 章 “ M i n - c u t - B a s e d L e a k a g e P o w e r - A w a r e S c h e d u l i n g i n H L S ” で は 、 高 位 合 成 に お い て 、 閾 値 電 圧 の 調 整 に よ り リ ー ク 電 力 を 最 小 化 す る ス ケ ジ ュ ー リ ン グ 問 題 を 扱 っ て い る 。 こ の 問 題 は 、 演 算 の デ ー タ 依 存 関 係 を 表 す D F G ( D a t a F l o w G r a p h ) 、使 用 可 能 な 演 算 器 の 種 類 、個 数 、閾 値 電 圧 ( H i g h , L o w の 2 種 類 ) 、

3

お よ び 生 成 す る 回 路 の 目 標 性 能 ( 処 理 に 要 す る 総 制 御 ス テ ッ プ 数 ) が 与 え ら れ た と き 、 目 標 性 能 に 関 す る タ イ ミ ン グ 制 約 と 、 使 用 可 能 演 算 器 に 関 す る リ ソ ー ス 制 約 の も と で 、 リ ー ク 電 力 を 最 小 化 す る 各 演 算 の 実 行 制 御 ス テ ッ プ と 演 算 器 の 閾 値 電 圧 を 決 定 す る こ と で あ る 。

本 章 で は 、 ま ず 、 全 て の 演 算 器 の 閾 値 電 圧 を h i g h と し た 初 期 解 か ら 出 発 し 、 演 算 器 の 閾 値 電 圧 を 調 整 す る こ と に よ り 、 タ イ ミ ン グ と リ ソ ー ス の 制 約 を 満 た す 解 を 求 め る 2 段 階 の 手 法 を 提 案 し て い る 。 初 期 解 で は 、 リ ー ク 電 力 は 最 小 と な る が 、 タ イ ミ ン グ 制 約 が 満 足 さ れ る と は 限 ら な い 。 そ こ で 、 ま ず 第 1 段 階 で は 、ク リ テ ィ カ ル パ ス 上 の 演 算 器 の 閾 値 電 圧 を 逐 次 H i g h か ら L o w に 変 更 す る こ と に よ り 、 リ ソ ー ス 制 約 を 考 慮 し つ つ 、 タ イ ミ ン グ 制 約 を 満 足 さ せ て い る 。 こ の 処 理 に お け る 課 題 は 次 の 2 点 で あ る 。 ( 1 ) D F G 上 の ク リ テ ィ カ ル パ ス が 複 数 個 あ る 場 合 、 一 つ の パ ス 長 を 短 縮 し て も 、 全 体 の ク リ テ ィ カ ル パ ス 長 が 短 縮 さ れ る と は 限 ら な い こ と と 、( 2 ) こ の 段 階 で は 各 演 算 を 実 行 す る 制 御 ス テ ッ プ が 未 定 の た め 、必 要 な リ ソ ー ス の 評 価 が 難 し い こ と で あ る 。そ こ で 、( 1 ) の ク リ テ ィ カ ル パ ス の 処 理 に つ い て は 、 全 て の ク リ テ ィ カ ル パ ス で 構 成 さ れ る グ ラ フ 上 で 最 小 カ ッ ト を 計 算 し 、 カ ッ ト 中 の す べ て の 演 算 の 閾 値 電 圧 を 一 括 し て 調 整 す る こ と に よ り 、 回 路 全 体 の ク リ テ ィ カ ル パ ス 長 の 短 縮 を 図 っ て い る 。 ま た 、 ( 2 ) の リ ソ ー ス の 見 積 も り に つ い て は 、 タ イ ミ ン グ 制 約 か ら 、 各 演 算 の 割 当 可 能 制 御 ス テ ッ プ の 範 囲 ( 以 下 、 m o b i l i t y と 呼 ぶ ) を 計 算 し 、 必 要 な リ ソ ー ス を 確 率 的 に 評 価 し て い る 。 こ の 評 価 の も と で 、 最 も 効 率 的 に ク リ テ ィ カ ル パ ス 長 を 短 縮 可 能 な 演 算 集 合 を 逐 次 選 定 し 、 閾 値 電 圧 を H i g h か ら L o w に 変 更 し て い る 。

第 2 段 階 で は 、 既 存 の ス ケ ジ ュ ー リ ン グ ア ル ゴ リ ズ ム で 各 演 算 の 実 行 制 御 ス テ ッ プ を 決 定 し 、 必 要 リ ソ ー ス の 正 確 な 評 価 を 行 い 、 リ ソ ー ス 制 約 違 反 が あ る 場 合 は 、更 に 、演 算 器 の 閾 値 電 圧 を 逐 次 H i g h か ら L o w に 変 更 す る こ と で リ ソ ー ス 制 約 を 満 た し て い る 。計 算 機 実 験 で は 、本 手 法 は 、既 存 の M W I S に 基 づ く 手 法 ( T a n g , D A C 2 0 0 5 ) に 比 べ 、 リ ー ク 電 力 が 約 3 4 % 、 計 算 時 間 が 約 5 5 % 削 減 さ れ た こ と を 示 し て い る 。 解 の 品 質 と 計 算 時 間 の 両 面 で 既 存 手 法 を 凌 駕 し た こ と は 、 本 手 法 の 有 効 性 を 示 す も の で あ り 、 評 価 す る こ と が で き る 。

第 3 章 “ M o b i l i t y O v e r l a p - R e m o v a l - B a s e d L e a k a g e P o w e r - A w a r e S c h e d u l i n g i n H L S ” で は 、 各 演 算 の m o b i l i t y の 重 複 を 除 去 す る こ と に よ り 、 よ り 正 確 な リ ソ ー ス の 見 積 り 手 法 と , そ れ に 基 づ く リ ー ク 電 力 の 最 小 化 手 法 を 提 案 し て い る 。 第 2 章 の 手 法 は 、 G r e e d y な ア ル ゴ リ ズ ム で あ り 、 高 速 で は あ る が 生 成 さ れ る 解 の 品 質 に 改 良 の 余 地 が あ っ た 。

本 章 で は 、 使 用 リ ソ ー ス の 評 価 を よ り 精 密 に 行 う 手 法 お よ び 、 そ れ に 基 づ く 逐 次 改 良 に よ る 最 適 化 手 法 を 提 案 し て い る 。高 位 合 成 の ス ケ ジ ュ ー リ ン グ で は 、 D F G の 各 枝 の 両 端 ノ ー ド に は デ ー タ 依 存 関 係 の 制 約 が あ る た め 、 こ の 制 約 を 考 慮 し て 処 理 を 行 う 必 要 が あ る が 、も し 両 者 の m o b i l i t y に 重 複 が 無 け れ ば 、デ ー タ 依 存 関 係 の 制 約 は 自 動 的 に 満 足 さ れ る 。 そ こ で 、 デ ー タ 依 存 関 係 の あ る 二 つ

4

の 演 算 の 間 で m o b i l i t y の 重 複 が あ っ た 場 合 、そ の 重 複 部 分 を ２ 分 割 し 、そ れ ぞ れ の 演 算 に 分 配 す る こ と で m o b i l i t y の 重 複 を 除 去 す る 手 法 を 検 討 し て い る 。こ の 場 合 、 ス ケ ジ ュ ー リ ン グ の 自 由 度 は 減 少 す る が 、 D F G で 定 義 さ れ る デ ー タ 依 存 関 係 制 約 の 考 慮 が 不 要 と な り 、 必 要 な リ ソ ー ス の よ り 正 確 な 評 価 が 可 能 と な る と 同 時 に 、 ス ケ ジ ュ ー リ ン グ が 容 易 と な る 。 本 章 で は 、 重 複 し た m o b i l i t y の 分 割 位 置 を 逐 次 変 更 し な が ら 、 焼 き な ま し 法 に よ る 最 適 化 を 行 う 手 法 を 提 案 し て い る 。 本 手 法 は 第 2 章 の 手 法 に く ら べ 、 ア ル ゴ リ ズ ム の 性 格 上 、 計 算 時 間 は 増 加 す る が 、 リ ー ク 電 力 を 約 2 . 5 % % 削 減 し て い る 。 M o b i l i t y 除 去 に よ る 最 適 化 手 法 は 、 独 創 的 な も の で あ り 、 評 価 す る こ と が で き る 。

第 4 章 “ S i m u l t a n e o u s L e a k a g e P o w e r a n d R e g i s t e r - A w a r e S c h e d u l i n g i n H L S ” で は 、第 3 章 で 提 案 し た 手 法 を 拡 張 し 、リ ー ク 電 力 の 最 小 化 と レ ジ ス タ 数 の 最 小 化 を 同 時 に 考 慮 す る 手 法 を 検 討 し て い る 。 変 数 の 値 を 保 持 す る レ ジ ス タ は リ ー ク 電 力 の 要 因 の 一 つ と な っ て い る こ と か ら 、変 数 間 で レ ジ ス タ を 共 有 し 、 レ ジ ス タ 数 を 削 減 す る こ と は 重 要 で あ る 。 し か し 、 レ ジ ス タ 共 有 の た め に は 、 ス ケ ジ ュ ー リ ン グ の 処 理 に お い て 、各 変 数 の ラ イ フ タ イ ム ( 変 数 の 値 が 設 定 さ れ て か ら 最 後 に 使 用 さ れ る ま で の 期 間 ) を 評 価 す る 必 要 が あ る た め 、こ れ ま で 有 効 な 手 法 は 提 案 さ れ て い な か っ た 。

本 手 法 で は 、 ま ず 、 第 ３ 章 の 手 法 と 同 様 、 デ ー タ 依 存 関 係 の あ る 演 算 の 間 の m o b i l i t y を 除 去 す る が 、 そ の 際 、 必 要 な リ ソ ー ス だ け で な く 、 変 数 の ラ イ フ タ イ ム を 評 価 す る こ と で 必 要 な レ ジ ス タ 数 を 確 率 的 に 見 積 も っ て い る 。 そ し て 、 リ ソ ー ス と レ ジ ス タ 数 の 重 み 付 き の 和 を 考 慮 し 、 焼 き な ま し 法 に 基 づ い て 最 適 化 を 行 う 手 法 を 提 案 し て い る 。計 算 機 実 験 で は 、本 手 法 は 第 ２ 章 の 手 法 に 比 べ 、 レ ジ ス タ 数 を 約 2 4 % 削 減 し て い る 。 本 章 で 提 案 し た 手 法 は 、 高 位 合 成 の ス ケ ジ ュ ー リ ン グ で レ ジ ス タ 数 削 減 を 考 慮 す る 新 し い 手 法 で あ り 、 計 算 機 実 験 で そ の 効 果 が 確 認 さ れ て い る こ と か ら 、 新 規 性 、 有 効 性 を 評 価 す る こ と が で き る 。

第 5 章 “ C o n c l u s i o n a n d F u t u r e W o r k ” で は 「 閾 値 電 圧 調 整 に よ る リ ー ク 電 力 最 小 化 」 に 関 す る 研 究 成 果 の 総 括 と 、 残 さ れ た 課 題 に つ い て 述 べ て い る 。

以 上 が 、 本 論 文 の 概 要 で あ る が 、 要 約 す れ ば 、 本 論 文 は 、 今 後 、 ま す ま す 重 要 と な る L S I の 低 消 費 電 力 化 に 対 し て 、 閾 値 電 圧 を 調 整 す る こ と に よ っ て リ ー ク 電 力 を 削 減 す る 3 種 類 の 独 創 的 な 手 法 を 提 案 し て い る 。 こ れ ら の 手 法 は 、 今 後 の シ ス テ ム L S I の 高 位 レ ベ ル 設 計 自 動 化 の 進 展 に 大 き く 貢 献 す る も の で あ る 。 よ っ て 、 本 論 文 は 、 博 士 ( 工 学 ) の 学 位 論 文 と し て 価 値 あ る も の と 認 め る 。

2 0 1 4 年 7 月 2 1 日

主 査 早 稲 田 大 学 教 授 博 士 ( 工 学 ) ( 大 阪 大 学 ) 吉 村 猛 早 稲 田 大 学 教 授 工 学 博 士 ( 東 北 大 学 ) 渡 邊 孝 博 早 稲 田 大 学 教 授 工 学 博 士 ( 京 都 大 学 ) 木 村 晋 二