Mapping Optimization Techniques for Coarse-Grained Reconfigurable Architectures
邦訳：粗粒度再構成可能アーキテクチャCGRAのためのマッピング最適化手法
小島拓也
（慶應義塾大学 訪問研究員／日本学術振興会 特別研究員PD）
------------------ keyword ------------------
粗粒度再構成可能アーキテクチャ
多目的最適化
省電力化
----------------------------------------------
【背景】エネルギー効率に優れる計算機に対する需要
【問題】多様化する用途に応じる最適化手法の欠如
【貢献】多目的最適化を可能にする新たなアルゴリズムを考案
IoTデバイスやウェアラブルデバイスの普及に伴い，画像処理や信号処理などの計算を十分高速に，かつ，バッテリーで長時間稼働できるようなエネルギー効率に優れたデバイスが求められている．
粗粒度再構成可能アーキテクチャ（CGRA: Coarse-Grained Reconfigurable
Architectures）はこのような要求を満たすデバイスとして期待されている．CGRAは多数の演算処理ユニットPE（Processing Element）が相互に接続された構造（図左）を持っており，これを用いて効率的な計算を行う．CGRAで実行する計算はデータフローグラフと呼ばれる演算同士の依存関係を示したグラフで示される（図右上：青い円は1つの演算─たとえば加算や乗算など─を表す）．この計算をCGRAで実行するには，どの演算をどのPEに割り当てるかを決定する必要がある．この操作をマッピングと呼ぶ．このとき，依存し合う演算が割り当てられたPEは互いに接続可能な位置にある必要があり，非効率的な割り当てをしてしまうと高い性能を達成できない，PEが不足し実行できないといった問題を引き起こしてしまう．
したがって，効率的に計算をマッピングする手法が広く研究されている．しかし，既存の手法は最適化の対象が実行時間（性能）など特定の項目に特化しており，多様化する用途に柔軟に対応することができていなかった．たとえば，バッテリー駆動型のデバイスで，あらかじめ決まった時間内で計算を完了すればよいシステムにおいては，その時間よりも早く計算を完了させても意味がない．それよりも時間内に完了し，なるべく消費エネルギーを小さくすることのほうが重要である．
そこで，本研究では計算のマッピングを行う問題を解くために，遺伝的アルゴリズムを採用した．遺伝的アルゴリズムとは，組合せ最適化問題などの解を遺伝子として表現し，生物の進化を模倣した操作を繰り返すことで，より良い解を探索するためのメタヒューリスティクス☆1である．相反する複数の最適化項目を同時に最適化することができるアルゴリズムが存在し，本研究でも同様のアプローチをとっている．たとえば，高い性能を得ようとすれば，通常は消費電力が増加してしまうが，本研究が提案した手法を用いることで，高性能に特化したマッピング，省電力性に特化したもの，いずれの項目もバランスの取れたものなど多種多様なマッピングを解として見つけることができる（図右下）．ユーザはこの中から自身の要求に合うものを選択し利用することができる．
本研究の評価はシミュレーションだけでなく，試作チップを用いた実機測定に基づいている．3種類の異なる試作チップに対して評価を行った結果，既存手法と比較して，提案手法によるマッピングは最大で46%ほどの消費エネルギーを削減できることを示した．
☆1 特定の問題に依存せず，さまざまな最適化問題に対して十分な品質の解が得られる汎用的な解法のこと．本研究で利用している遺伝的アルゴリズムの他に，蟻コロニー最適化，粒子群最適化，焼きなまし法などがある．
（2021年5月30日受付）
（2021年8月15日note公開）
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
取得年月日：2021年3月
学位種別：博士（工学）
大学：慶應義塾大学
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
推薦文：（システム・アーキテクチャ研究会）
簡単なプロセッサによるアレイを構成要素とする粗粒度再構成デバイスは，エネルギー効率が高いことからIoTデバイスなどに利用されている．この論文はこのデバイス上にアプリケーションを搭載する際の最適化手法を確立し，実用的なCADツールを構成した点で高く評価され，海外の著名ジャーナルに掲載された．
小島拓也
研究生活：学部生で慶應義塾大学天野研究室に配属されて以来，博士課程に至るまで継続して粗粒度再構成可能デバイスCGRAに関する研究に従事してきました．この間，関連分野への調査を積極的に行い，研究内容の視野を広げスケールを徐々に拡大させることができ，本研究としてまとめあげることができました．この過程で，研究室の諸先輩方や指導教員の天野英晴教授には自身のアイディアを尊重してくださり，多くのサポートをいただきました．おかげで，主体的に研究活動を行う力が身についたと感じています．今後も見聞を広げることを怠らずに，IT技術の発展に貢献できるよう研究活動に邁進してまいります．