動的再構成可能なパイプライン型アーキテクチャ向け配置配線手法

(1)

動的再構成可能なパイプライン型アーキテクチャ向け配置配線手法

肥塚真由子

電気通信大学大学院情報システム学研究科博士（工学）の学位申請論文

2013 ^年 3 ^月

(2)

動的再構成可能なパイプライン型アーキテクチャ向け配置配線手法

博士論文審査委員会

主査渡辺俊典教授

委員本多弘樹教授

委員吉永努教授

委員古賀久志准教授

委員近藤正章准教授

(3)

著作権所有者

肥塚真由子

2013

(4)

Mayuko Koezuka Abstract

Recently, high-deﬁnition and multifunctional mobile computers have been developed.

These battery-powered mobile computers require large processing power with low power consumption and small area. Dynamically Reconﬁgurable Architecture (DRA) has been proposed to meet these needs in recent years. Compilers for DRA need to map processing operations to DRA. Therefore, we present an algorithm that places and routes processing represented by a directed acyclic graph (DAG) in DRA. A typical structure of DRA includes array architecture and pipeline architecture. The pipeline architecture has fewer data paths than the array type architecture, and attracts attention as the architecture which realizes small area and low power consumption.

This paper chooses the pipeline architecture as the target architecture. However, it is diﬃcult to apply placement and routing (P&R) algorithm for the array architectures to pipeline architectures, because the pipeline architecture has low degree of freedom of P&R. Here, Simulated Annealing (SA) is known as the typical P&R algorithm for the array architectures. On the other hand, simple full search algorithm is hard to solve the problem in realistic time, since the computational complexity increases exponentially, as the size of pipeline architecture increases.

Therefore, we propose a P&R algorithm using the pruning method according to data path restriction of the pipeline architecture. This algorithm searches alternately placement and routing for every pipeline stage. The main functions of this algorithm consist of the candidate solution pruning according to data path restriction of the input DAG, the search direction prediction, and the function to remove non-search nodes.

Furthermore, we propose to introduce a complexity index calculated from the input DAG and the target architecture size to enable the prediction of the possibility to discover

(5)

by using this prediction, which increases the overall availability of the compiler systems wherein the proposed algorithm works.

In the evaluation, we compare the proposed P&R algorithm with SA in terms of the search time and the rate of the solution discovery. Moreover, we conﬁrmed the eﬀectiveness of the main functions of our algorithm. Then, we evaluated the search time for various sizes of the pipeline architectures to show the scalability of the proposed P&R algorithm.

We concluded that meta-heuristics algorithms like SA are not applicable to the pipeline architecture with severe restrictions and that the proposed algorithm which uses the ar- chitectural restrictions is valid.

(6)

肥塚真由子

概要

近年，携帯端末機等における高機能化に伴い，これらの機器向けのLSIに要求される処理能力が増大している．また，高性能に加え，低消費電力，小面積なアーキテクチャへの要求も高まっている．これらの要求を満たす解の１つとして，動的再構成可能なアーキテクチャが提案されている．動的再構成可能なアーキテクチャ向けのコンパイラでは，処理演算をアーキテクチャにマッピングする技術が必要となる．そこで，本論文では処理を Directed Acyclic

Graph（DAG）で表現されたデータフローグラフに変換し，これを動的再構成可能なアーキテ

クチャに配置配線する手法を提案する．動的再構成可能なアーキテクチャとして，代表的なものにパイプラン型とアレイ型の２種類があるが，パイプライン型アーキテクチャは，アレイ型アーキテクチャと比較して配線が少なく，小面積・低消費電力を実現するアーキテクチャとして注目されている．そこで，本論文ではターゲットアーキテクチャとしてパイプライン型アーキテクチャを採用した．しかしながら，パイプライン型アーキテクチャは配線が少なく配置配線の自由度が低いため，アレイ型アーキテクチャに適用されている配線自由度の高さを利用した既存手法（シミュレーテッドアニーリング）を適用することは困難である．また，単純な全探索手法を導入した場合も，パイプラン型アーキテクチャ規模が大きくなるにつれ探索範囲が非常に広くなり，計算量が指数関数的に増大し現実的な時間内で解を得るのは困難になる．そこで，本論文ではパイプライン型アーキテクチャの配線制約による枝刈り手法を用いた配置配線手法を提案する．これは，パイプライン段毎に演算の配置と配線を交互に探索していく問題であり，入力DAGの配線制約を用いた探索領域の枝刈り，探索方向予測，探索不要ノード削除機能を併用している．さらに，入力DAGとターゲットアーキテクチャ規模から算出する複雑度指標を導入し，探索解発見率や探索時間を予測可能とした．これによって探索の上限時間設定を可能にし，本方式を含むコンパイラシステム全体の可用性を向上させた．実験評価では，アレイ型アーキテクチャのマッピング探索で用いられているシミュレーテッドアニーリングと提案手法において，マッピング探索の実行時間とマッピング探索解の発見率を比較した．

(7)

イプラインに適用可能であるかどうかを検証するため，アーキテクチャのパラメータを変化させた上で提案手法を適用し，マッピング探索の実行時間の比較を行った．その結果，アーキテクチャのような配置や配線制約の厳しいアーキテクチャにおいては，シミュレーテッドアニーリングのようなメタヒューリスティクスアルゴリズムを用いることは困難であり，逆に制約による探索範囲の削減による提案手法が有効であることが示され，コンパイルフローの可用性向上が可能となった．

(8)

図目次

1.1 Dynamically Reconﬁgurable Architecture (DRA) . . . 9

1.2 FlexSword^TM アーキテクチャ . . . 10

1.3 DRAによるアプリケーション実装 . . . 12

1.4 DRAコンパイラフロー . . . 14

1.5 アレイ型アーキテクチャ . . . 17

1.6 パイプライン型アーキテクチャ . . . 17

2.1 パイプライン型アーキテクチャモデル . . . 21

2.2 PE間接続の配線パターンライブラリ . . . 22

2.3 ALU . . . 23

2.4 DAG . . . 25

4.1 FlexSword^TM コンパイラにおけるフィードバック機構 . . . 33

4.2 PreProcessフロー . . . 35

4.3 PreProcessによるFWDノード追加 . . . 38

4.4 入力DAG . . . 40

4.5 配線パターン(PE3) . . . 41

4.6 ALU位置(PE3) . . . 42

4.7 マッピング結果 . . . 43

4.8 探索対象ノード，探索非対象ノード . . . 44

4.9 PostProcess : 探索非対象ノードの配置配線 . . . 45

5.1 全探索アルゴリズムと提案手法における探索パターン数比較 . . . 48

(12)

5.2 提案手法とのマッピング解発見率比較（ALU=2） . . . 51

5.5 提案手法とのマッピング解発見率比較（PE=2） . . . 55

5.10 提案手法とのマッピング解発見率比較（PEC=2） . . . 61

5.13 Search Nodes Selectionにおける探索解発見率（PE=2） . . . 65

5.18 Search Direction Decision機能検証（PE = 2，手法OFF-Bottom-） . . . 71

5.19 Search Direction Decision機能検証（PE = 2，手法OFF-Top-） . . . 72

5.26 Search Direction Decision機能検証（PE = 10，手法OFF-Bottom-） . . 79

5.27 Search Direction Decision機能検証（PE = 10，手法OFF-Top-）. . . 80

5.28 ALU数毎のマッピング解発見率 . . . 83

5.29 PE数毎のマッピング解発見率 . . . 84

5.30 PEC数毎のマッピング解発見率 . . . 85

(13)

5.31 複雑度検証 (ALU=2) . . . 87

5.32 複雑度検証 (ALU=4) . . . 88

5.33 複雑度検証 (ALU=8) . . . 89

5.34 複雑度検証 (PE=2) . . . 90

5.35 複雑度検証 (PE=4) . . . 91

5.36 複雑度検証 (PE=6) . . . 92

5.37 複雑度検証 (PE=8) . . . 93

5.38 複雑度検証 (PE=10) . . . 94

5.39 複雑度検証 (PEC=2) . . . 95

5.40 複雑度検証 (PEC=4) . . . 96

5.41 複雑度検証 (PEC=8) . . . 97

5.42 複雑度検証 (PEC=16) . . . 98

5.43 複雑度指標を用いたフィードバック機構. . . 101

5.44 複雑度検証 (PE=6) . . . 104

5.45 実行時間(T)毎のP&R累計推定時間（シナリオ1）. . . 106

5.46 実行時間(T)毎のP&R累計推定時間（シナリオ2）. . . 107

5.47 Feedback Checker活用フロー . . . 108

(14)

表目次

5.1 ALU数毎のマッピング解発見率 . . . 50

5.2 PE数毎のマッピング解発見率 . . . 54

5.3 PEC数毎のマッピング解発見率 . . . 60

5.4 枝刈り手法評価 : Search Direction Decision . . . 81

5.5 Search Node SelectionによるPE削減数 . . . 99

5.6 フィードバックによるP&R推定実行時間 . . . 105

(15)

第 1 ^章

はじめに

1.1 本研究の背景と目的

本研究の目的は，近年需要が高まってきている携帯端末機の中心となるLSIの実現である．

携帯端末機ではメディア処理や無線などのアプリケーションが処理され，これはフィルタ処理やバタフライ演算から成るループ処理形式により実現される．そこで，このような処理に適合するLSIの開発が必要とされており，適応するLSIとして，Dynamically Reconﬁgurable

Architecture (DRA) が存在する．DRA を動作させるために実行コードが必要となるが，実

行コードを手動で生成することは困難であるため，DRA 向けのコンパイラが必要となる．コンパイラの主要処理の1つとして配置配線手法が必要とされているが，既存手法でのアプローチが困難であるため，フィルタ処理やバタフライ演算に特化したDRA向けの配置配線について，新たな手法の提案が必要とされている．以上の内容について，次節より詳細を述べる．

1.1.1 LSI 市場の動向

近年，携帯端末機等における高機能化に伴い，これらの機器向けのLSIに要求される処理能力が増大し，高性能に加え，低消費電力，小面積なアーキテクチャへの要求が高まってきている．また，携帯端末機等においてメディア処理や無線などのアプリケーションが用いられており，これらのアプリケーションでは規格変更が多く行われるため，柔軟性を持ったアーキテクチャの開発も求められている．既存の汎用プロセッサのみを用いた場合，柔軟性の要求を満たすことができるが，高性能，低消費電力，小面積の要求を満たすことができなくなる．また，

(16)

専用ハードウェアを用いれば高性能，低消費電力の要求を満たすことは出来るが，一方で開発コストの増大，アプリケーションの規格変更等に対する柔軟性に欠け，再利用性が低いという欠点が浮上する [1]．

1.1.2 Dynamically Reconfigurable Architecture (DRA)

これらの問題を解決する方法の1 つとして，図1.1に位置されるDynamically Reconﬁg- urable Architecture (DRA)が提案されている [2] [3]．再構成可能なアーキテクチャとして

汎用汎用汎用汎用プロセッサプロセッサプロセッサプロセッサ

Dynamically Dynamically Dynamically Dynamically Reconfigurable Reconfigurable Reconfigurable Reconfigurable Architecture ArchitectureArchitecture Architecture

専用HW

・高性能

・小面積

・低消費電力柔軟性

図1.1 Dynamically Reconfigurable Architecture (DRA)

Field-Programmable Gate Arrays (FPGA) も存在しているが，構成情報のロードにはミリ秒単位の時間を必要とするため，マイクロ秒単位で構成情報をロードするDRAはより動的な切り替えに向いていることが分かる [4]．さらに，粗粒度DRAの構成情報は，細粒度FPGA の構成情報よりも 1/10-1/100ほど小さいことが知られている [5]．このことから，DRA は，

専用ハードウェアに近い演算能力と消費電力を持つ，小面積で柔軟性を持つプログラマブルなアーキテクチャだということがわかる．そこで，本論文では，アプリケーションの規格変更に依存しにくく，アプリケーションのライフサイクルに依存しないDRAをターゲットとして採用する．

1.1.3 パイプライン処理

メディア処理や無線等で扱われる処理，特に動画圧縮規格H.264や高速フーリエ変換FFT では，フィルタ処理やバタフライ演算に対する最適化が性能向上に重要であることが知られて

(17)

いる．フィルタ処理やバタフライ演算はデータが入力される度に決まった演算処理を行うため，ループ実行される．同一処理をループ実行する場合，ソフトウェアパイプラインによる最適化が有効となる．ソフトウェアパイプラインは，複数ステップで構成される処理を並行して同時に行う処理であり，これにより命令を並列実行することが可能となり，高性能や低消費電力が実現される．DRAで用いられる構造は，主にアレイ型とパイプライン型の2つが挙げられる．これらについては後の節で詳細を述べるが，ソフトウェアパイプラインを最適化するにはパイプライン型が有用である．パイプライン型のユニットを保持するDRAの1つとして FlexSword^TM [6]のアーキテクチャを図1.2に示す．

Host Processor

データ用メモリ

パイプライン型パイプライン型パイプライン型パイプライン型

ユニットユニットユニットユニット-0 データ書き込み

データ書き込みデータ書き込みデータ書き込み

制御部制御部制御部制御部

接続インタフェース

ユニット間バッファユニット間バッファユニット間バッファユニット間バッファ動的再構成可能なユニット

(ユニットごとに独立制御)

コード用メモリ

ユニットユニットユニットユニット-1 並列データ型

並列データ型並列データ型並列データ型

ユニットユニットユニットユニット-0 並列データ型

並列データ型並列データ型並列データ型

ユニットユニットユニットユニット-1 プログラムコードの流れ

データの流れ

FlexSword

図1.2 FlexSword^TMアーキテクチャ

FlexSword^TM は，Host Processorから接続インタフェースを通じてHost Processorから処理を指示される．入力データはデータ用メモリから読み込まれ，ユニット間バッファを介して5つのDRAユニットで処理を行い，再びデータ用メモリに書き戻される．ユニット間バッファにより，パイプライン型ユニットや並列データ型ユニットを任意の順序に実行可能になるため，多くの処理を実行可能となる．また，コード用メモリに5つのDRAユニットの実行時に必要な構成情報を保持している．

(18)

1.1.4 ^{コンパイラ構成}

FlexSword^TM などの DRA を動作させるためには実行コードが必要となるが，この実行

コードを手作業で生成することは一般に困難なため，通常コンパイラを用いて生成される．コンパイラは，ソースコードを入力として，いくつかのフェーズを経た後にオブジェクトコード

（実行コード）を出力する．フェーズは，「字句解析」，「構文解析」，「中間コード生成」，「コード最適化」，「コード生成」の5つのフェーズに分けられる．「字句解析」はプログラムをトークンに分割するフェーズであり，「構文解析」はトークン間の関係を調べ，データフローグラフなどの構文木を生成するフェーズである．「中間コード生成」フェーズでは，構文木の意味を解析し内部的なコードである中間コードが生成される．「コード最適化」では，中間コードを変形することで，効率的なプログラムに変換を行う．最後に，「コード生成」フェーズで，

最適化された中間コードをターゲットアーキテクチャのアセンブリ言語などのオブジェクトコード（実行コード）に変換する．コンパイラの性能とは，効率的な実行コードを出力できるかどうかであり，これは「コード最適化」での効率的な変換に依存している．「コード最適化」で代表的な最適化アイテムとして，レジスタ割り当て，命令選択など命令スケジューリングなどが挙げられる．本論文では，命令スケジューリングに含まれる，配置配線問題について議論していくが，ここで，命令スケジューリングに関する関連研究について言及しておく．命令スケジューリングの問題には，命令間に依存のない独立スケジューリングと，別の命令の結果データを受信しなければ処理を実行できないDAGスケジューリングが存在する．さらに，

スケジューリングの前に全ての命令情報が得られているオフラインスケジューリングと，スケジュールをするにしたがって命令の情報が与えられるオンラインスケジューリングの違いが大きい．今回ターゲットアプリケーションとしているストリーミング処理は，命令間に依存があるためDAG スケジューリングが該当する．また，ターゲットアーキテクチャである DRAは，DRAが事前に構成情報をメモリに保存しておき，実行時に構成情報を呼び出して動的に構成を切り替えていく構造であるため，オフラインスケジューリングに分類される．オフラインのDAGスケジューリングで多く用いられている手法はレベルスケジューリングであり，Mapping Heuristic (MH) [7]，Generalized Dynamic Level (GDL) [8]，BestImaginary

Level (BIL) [9]の3つである．これらは同一のユニットで構成されるアーキテクチャに対し

て，レベルを定義した上でEarliest Completion Time (ECT) [10]の手法を用いてスケジュー

(19)

リングを行っている．ECTは処理が完了する時刻が最も早いユニットに命令を割り当てる手法である．レベルスケジューリング以外にも多様な手法が提案されている．Clustering for Heterogeneous Processors (CHP) [11]は関連の強い命令同士をクラスタリングしてからクラスタ単位でマシンに割り当てるが，同一のユニットのみを想定している．また，クリティカルパスをできるだけ 1台の速いユニットに割り当てる方針でスケジュールを構成する手法には Heterogeneous Critical Path Fast Duplication (HCPFD) [12], Bubble Scheduling and Allocation (BSA) [13], Critical-Path-on-a-Processor (CPOP) [14]などがある．ユニットがすべて同一の場合にはクリティカルパスを1つの速いユニットに割り当てるのは自然であるが，異種ユニットに対して適用するには限界がある．内部の配置配線も含めた命令スケジューリングについては，Simulated Annealing (SA) [15]などの一般的な最適化手法を用いた例もあるが，計算量の観点から，ごく小規模な問題にしか適用できない．

1.1.5 DRA におけるアプリケーション実装

DRAでは，図1.3のように，実行コードに従って次々と構成情報を選択し，演算を行う演算器や演算器間を接続する経路の構成を高速に変更することが可能である．

DRA

アプリケーションプログラムアプリケー

ションプログラムアプリケー

ションプログラム

構成情報構成情報構成情報構成情報保存メモリ保存メモリ保存メモリ保存メモリ

I/Oデータデータデータデータ保存メモリ保存メモリ保存メモリ保存メモリ

データーフローグラフ

（DAG）生成と分割

配置配線実行順序

構成情報や実行順序をメモリに保存

DRA構成を動的に切り替えて実行

DAG

分割結果構成情報

図1.3 DRAによるアプリケーション実装

(20)

アプリケーションプログラムをDRA上に実装する場合，まずアプリケーションプログラムをデーターフローグラフに変換し，これを元に，割り当てたいユニット毎にデーターフローグラフを分割する．分割したグラフの実行順序のスケジューリングと共に，分割グラフをDRA の持つユニットの構成に合わせて配置配線を行うことで構成情報が生成される．構成情報はメモリ上に保存され，DRAの構成を動的に切り替える際に呼び出されることになる．また，入出力データ（IOデータ）もまた，メモリ上に保存され，DRAの動的構成変換の際に，適宜呼び出される．このような作業は一般にコンパイラによって行われる．これらステップを手作業で行った場合，開発コストが増大してしまうため，DRA向けの構成情報を自動生成するコンパイラが必要となる [16]．中でも命令スケジューリングに含まれる配置配線については，アーキテクチャ構成によっては手法が確立されていない場合も多い．本論文でターゲットとするストリーミング処理を考えた場合，ストリーミング処理は一方向のみのデータ転送で実現できるため，この処理を実現するためのアーキテクチャは，パイプライン型など必ずしも多くの配線を必要としない．そのため，命令スケジューリングだけでなく配置配線においても配置配線制約，命令間の依存関係やメモリ制約が厳しくなり，既存手法の適用は困難となる．

DRA向けのコンパイラを考えるにあたり，その探索空間の大きさが問題となる．大規模な解空間に対して探索を行う場合，解空間を単純に探索した場合，現実的な時間での解取得は困難となる．そこで，コンパイルの探索問題を分割することで，探索空間を分割し，実行時間の短縮を図る必要がある．そのため，コンパイルフローを配置配線問題やスケジューリング問題などに分割し，現実時間での実行コード生成を実現させる方法が考えられている．一般的には，プログラム言語をコンパイラ中間言語へと変換するフロントエンド，ハードウェアとソフトウェアの分割を行うミドルエンド，最後にスケジューリングやマッピングを行うバックエンドに分割される [17]．そこで，実際に設計されているアーキテクチャを用いて，コンパイル分割の例を説明する．DRA向けのコンパイラでは，同種のユニット群から成る DRA向けのコンパイラと，異種のユニット群から成るDRA 向けのコンパイラが存在する [18]．いずれのコンパイラにおいても，実行コードを生成するためには，大規模な解空間に対して探索を行う必要があるが，現実的な時間での解取得は困難である [19]．特に，異種ユニットから成るDRAでは，アーキテクチャ構造が異なるユニット内のマッピングやユニット単位でのクラスタリングとスケジューリングにおいて，同種のユニットで構成されるDRA よりも問題が複雑になる場合が多い [20]．そこで，本論文で対象とするアーキテクチャは，一般的に複雑

(21)

とされる異種のユニット群から成る DRAを用いる．異種のユニット群から成るDRA には FlexSword^TM [6]，ADRES [21]やMXP5800 [22]などが挙げられる. そこで，DRAで考慮されるコンパイラの各分割問題について図1.4のコンパイルフロー図について見ていく．

データ依存解析データ依存解析データ依存解析データ依存解析ソースプログラムソースプログラムソースプログラムソースプログラム

データフローグラフデータフローグラフデータフローグラフデータフローグラフ

実行コード実行コード実行コード実行コードクラスタリングクラスタリングクラスタリングクラスタリング

演算・ユニット対応情報演算・ユニット対応情報演算・ユニット対応情報演算・ユニット対応情報

配置・配線配置・配線配置・配線配置・配線

構成情報構成情報構成情報構成情報

ユニットスケジューリングユニットスケジューリングユニットスケジューリングユニットスケジューリング

add(+) sub(-) mul(*) div(/)

・・・

並列データ型並列データ型並列データ型並列データ型

ユニットユニットユニットユニットパイプライン型ユニット

パイプライン型ユニットパイプライン型ユニットパイプライン型ユニット

ユニットユニットユニットユニットデータ書き込みデータ書き込みデータ書き込みデータ書き込み

制御部制御部制御部制御部

パイプライン型ユニットパイプライン型ユニットパイプライン型ユニットパイプライン型ユニット

並列データ型ユニット並列データ型ユニット並列データ型ユニット並列データ型ユニット

図1.4 DRAコンパイラフロー

FlexSword^TM でのコンパイラ問題分割は，データ依存解析 , クラスタリング , 配

置・配線 , ユニットスケジューリングの4 つのフェーズから成る．以下で，各フェーズについての説明を行う.

• ^{データ依存解析}

データ依存解析では, 高級プログラミング言語で記述されたソースプログラムを入力としてデータ依存解析を行い, データフローグラフを生成し，出力する. データフローグラフは有向グラフであり,ノードが演算を表し,エッジが演算の入出力データの流れを表現している. データフローグラフの例は図1.4に示されている.

• ^{クラスタリング}

(22)

クラスタリングは，次に実行される配置・配線フェーズとセットで構成されており，

FlexSword^TM アーキテクチャ制約と性能を考慮し, データフローグラフを適切な演算

ユニットに割り当てるフェーズである. 演算ユニット単位のデータ依存グラフを命令・

ユニット対応情報と呼ぶ. 図1.4に命令・ユニット対応情報の例が示されている.

• ^{配置・配線}

配置・配線では，各演算ユニット単位に分割されたデータフローグラフ内の演算をアーキテクチャ制約を考慮して配置・配線するフェーズである. そして,配置・配線可否判定と,配置配線等のアーキテクチャ構成情報を生成する. アーキテクチャ構成情報は構成情報と呼ばれ，図1.4に例が示されている.

• ユニットスケジューリング

ユニットスケジューリングでは，クラスタリングフェーズで生成される演算・ユニット対応情報から得られたユニット単位でのデータフローグラフのスケジューリングを行う. 最終的には，ユニットレベルのスケジューリング結果と配置・配線によって得られた構成情報より，DRAの実行コードが生成される.

そこで，本論文では，性能や探索時間に大きく影響する配置・配線(Placement & Routing : P&R)について注目する．

(23)

1.2 関連手法

Placement & Routing (P&R) 手法における既存手法について述べる．代表的な既存手法として，全探索アルゴリズムを用いた P&R 手法と Genetic Algorithm (GA) [23] [24]， Simulated Annealing (SA) [15]，タブーサーチ [25]やメトロポリス法[26]に代表されるメタヒューリスティクスアルゴリズムを用いたP&R手法が挙げられる．

全探索アルゴリズムを用いたP&R手法は，網羅的に全ての配置は全パターンを探索する手法であり，探索解が存在する場合は必ず解を発見できるという特徴を持つ．しかし，配置配線パターンが多い場合には，探索パターンが増大し，現実時間での解発見が困難となるという欠点を持つ．

一方で，メタヒューリスティクスアルゴリズムにおけるP&R手法として最もよく用いられるSAでは，ランダムに生成した配置配線パターンから近傍解を次々に探索していく手法である．メタヒューリスティクスアルゴリズムを用いたP&R手法では，配置配線制約が少ない場合に，配置配線パターンが多い場合でも短時間で解を発見できる可能性を持つが，全探索と比較すると，必ずしも解を発見できる保障が無いという欠点を持つ．

DRAユニットにおける配置配線を考える場合，DRAユニットの構造によって最適なP&R 手法というのは異なるため，次節にて良く用いられるDRA構造の考察と，本論文で対象とするDRA構造の決定を行う．

1.3 DRA 構造

P&Rを解決するための新たなマッピング探索手法を提案するにあたり，ターゲットとする

アーキテクチャの構造を選定する．DRAが用いる構造は，主にアレイ型とパイプライン型の 2つが挙げられる [18]．アレイ型DRA（以後，アレイ型アーキテクチャとする）は，図1.5 のように演算器がアレイ状に配置され，隣接する演算器が双方向に接続されている．パイプライン型DRA（以後，パイプライン型アーキテクチャとする）は，図1.6のように演算器が 1 方向に接続されている．一般的なDRAとしてはアレイ型アーキテクチャが多く用いられており，データが全てのノードに到達可能な配線構造であるため，マッピングの自由度が高いという特徴を持つ．一方，パイプラン型アーキテクチャはデータの流れが1方向であるパイプラ

(24)

イン処理に特化させるため，データが全てのノードに到達可能でない配線構造を持っており，

PipeRench [27], KC256 [28], SANYOアーキテクチャ [29], FlexSword^TM [6]などで採用されている．ただし，データが全てのノードに到達可能でないため，マッピングの自由度が低いという特徴を持つ．以上より，アレイ型アーキテクチャはマッピング自由度が高く多様なアプリケーションに対応可能であるが配線数が多く面積が増大する傾向にあり，パイプライン型アーキテクチャはマッピング自由度はやや下がり，対応可能なアプリケーションをストリーム処理に限定する必要があるが，配線数を削減することが可能となることがわかる [28]．このようなDRA構造の特徴を踏まえた上で，既存のP&R手法が適用可能かどうかを確認する．

図1.5 アレイ型アーキテクチャ図1.6 パイプライン型アーキテクチャ

まず，アレイ型DRAにおいて全探索アルゴリズムを用いたP&R手法を適用した場合を考える．この場合，配置配線制約を考えずに全ての配置配線パターンを探索してしまい，探索時間が膨大となり現実時間内での探索終了は困難となる．そのため，アレイ型DRA において全探索アルゴリズムを用いたP&R手法の適用は困難であることが分かる．アレイ型DRAに

SAを用いたP&R手法を適用した場合，アレイ型DRAのマッピング自由度の高さを利用し，

効率的に配置配線パターンを探索することが可能となる．そのため，アレイ型DRAにSAを

用いたP&R 手法の適用は可能であり，既にADRES向けコンパイラであるDRESCで適用

されている [30]．

次に，パイプライン型 DRA における P&R 手法の適用について考える．PipeRench や

KC256などのパイプライン型DRA では，パイプライン間のフルクロスバーと呼ばれる全て

の演算器へのデータ転送が可能な配線構造を持ち，配線数を多く持つためパイプライン型アーキテクチャの中ではマッピング自由度が高いという特徴を持つ．この場合，配線制約が無い

(25)

ため，コンパイラは配置のみを考慮すれば良いので，マッピング問題は容易に解くことができる [31]．一方で，配線制約が非常に厳しいSANYOアーキテクチャ [29]では，配置配線パターンが全探索で網羅できる範囲に収まっているため，全探索手法の適用が可能となる．しか

し， FlexSword^TM [6]などのフルクロスバーよりも配線が少ないが，全探索では現実時間内

で探索が完了しないようなパイプライン型DRAでは，配置配線制約が多いため，SA を用い

たP&R手法を単純に適用しただけでは機能しない事が分かる．

本論文では小面積なターゲットアーキテクチャを目標としていることから，パイプライン間の配線がフルクロスバーでなく，配線が削減されているパイプライン型DRA が最適と考える．また，配線が削減されているパイプライン型アーキテクチャでは，配線空間が削減できるとともに，構成情報を保持するメモリ面積の削減も可能となる．しかし，上記の考察より，パイプライン型DRAに既存へのP&R手法の適用は困難であることが分かった．そこで本論文では，ユニット数が多く，パイプライン型ユニットを持つFlexSword^TMを元に，パイプライン型DRAをターゲットとするマッピング探索問題を考える．

1.4 ^{本研究のアプローチ}

パイプラン型のマッピング探索問題では，有限パイプライン段数条件のもとで，目標とする所定の演算を実現する必要から，マッピング探索を行う前にパイプラン段数に合わせて処理を分割するクラスタリングを行う必要がある．性能向上のため，演算の充填率を上げたクラスタリングを行う必要があるが，配線制約のあるパイプライン型アーキテクチャでは必ずしもマッピング可能性が上がらないという問題が生じる．そこで，マッピングに失敗した場合は，演算の充填率を下げたクラスタリング結果を生成する必要がある．そこで，クラスタリングとマッピングを再試行するフィードバックが導入される [32] [33] [34]．

これにより，クラスタリングは再度処理分割パターンを生成することができ，マッピング探索解が得られた処理分割パターンの中から最も性能の良い結果を得ることになる．また，１回のマッピング探索時間を短縮することができれば，試行できる分割処理のパターンが増えるため，分割した処理を高速にマッピング探索する手法が必要とされている．しかし，マッピング自由度の低いパイプライン型アーキテクチャにおいても，配線数が少なくマッピングが限定的になる場合には探索は短時間で完了するが [35]，配線が多く多様なマッピングが可能なパイプ

(26)

ラン型では探索が長時間となる傾向にある [36]．そこで本論文では，アレイ型アーキテクチャよりも小面積を実現し，配線を多くすることでマッピング可能性を向上させたパイプライン型アーキテクチャに対しても，より短時間で解が発見可能となるマッピング探索手法を提案する．このことにより，提案するマッピング探索手法では上記の配線数が少ないケースと多いケースの両方に対応可能となる．

この新マッピング探索手法を提案するにあたり，ターゲットとするパイプライン型アーキテクチャのモデルを定義した．モデル化では，様々なパイプライン型アーキテクチャの特徴を表現可能とするために一般化を行った．また，マッピング探索の入力となるデータフローグラフの定義も行った．様々なパイプライン型アーキテクチャモデルに対して提案マッピング探索手法を評価するため，アーキテクチャサイズを基準としたデータフローグラフの複雑度指標を導入し，コンパイラの高速化を実現するとともに，評価の正当性を示すことが可能となった．これらを定義することで，フィードバック機能を持つコンパイラ上で効率的に動作するマッピング探索手法を提案することが可能となった．

第2章ではターゲットとするパイプライン型アーキテクチャのモデル化と，マッピング探索の入力となるデータフローグラフの定義を行う．第3章では関連手法に関する分析を行う．

第4章ではデーターフローグラフの複雑度指標とマッピング探索手法の提案を行う．第5章では提案手法についてSAとの比較評価と，提案手法の有効性を評価する．さらに，提案手法がパイプライン型アーキテクチャに汎用的に適用可能かどうかの検証を行い，その上でフィードバック機構を導入した新たなコンパイラフローを提案する．最後に第6章でまとめと今後の課題を述べる．

(27)

第 2 ^章

パイプライン型アーキテクチャとデータフローグラフのモデル化

本章では，本論文でターゲットとするパイプライン型アーキテクチャのモデリングを行い，

その後，提案マッピング手法の入力となるデータフローグラフの定義を行う．

2.1 パイプライン型アーキテクチャ

パイプライン型アーキテクチャのモデル化では，様々なタイプのパイプライン型アーキテクチャが実現できるような一般化を行う．そこでは，小面積を実現しながら多様なパイプライン処理を実現可能なアーキテクチャであるFlexSword^TM をベースとして，様々なパラメータである演算器数，パイプラン段数，配線パターン数を設定可能なアーキテクチャを設計する [6]．

パイプライン型アーキテクチャにおいて，多くのデータフローグラフを配置配線するために用いられ，探索時間に影響を与える重要なパラメータとして配線パターン数が挙げられる．これは，配線パターン数を増やすことにより様々な位置の演算器にデータを転送することができるが，一方で配線数が増えることで探索数が増大することを示している．そこで，配線パターンが複数存在するようなパイプライン型アーキテクチャのモデリングを行う．

図2.1にモデル化したパイプライン型アーキテクチャの構成を示す.

(28)

PE Connection (PEC

⁰

)

PE 0

PE 1

PE 2

PE N-1

ALU

M-1

PE Connection (PEC

¹

)

PE Connection (PEC

^N-2

)

ALU

0

ALU

1

ALU

M-1

ALU

1

ALU

0

ALU

M-1

ALU

1

ALU

0

ALU

M-1

ALU

1

ALU

0

Example of PE Connection

図2.1 パイプライン型アーキテクチャモデル

(29)

Connection Pattern 0 PE Connection

Connection Pattern 1

Connection Pattern 2

Connection Pattern 3

図2.2 PE間接続の配線パターンライブラリ

(30)

提案するパイプライン型アーキテクチャモデルは, N 個のProcessing Element (PE)とPE 間をデータ転送を行うN −1個のPE Connection (PEC) から成る. P E0 からデータを入力し,最終的にP E_N₋₁ から演算結果を出力する. 各PE はM個の ALUで構成されており, P Ei を構成する各ALUは，P ECi から2つのデータを入力し，同一の演算結果をP ECi+1

に2出力する.

以下で,各PEを構成してるALUとPECの詳細について述べる.

2.1.1 ALU

主な演算は2入力が多いことから，2入力の演算器でALUを図2.3のようにモデル化する．

さらに，出力結果も 2出力とすることで，全ての出力結果を次の段のいずれかの ALUの入力とすることができる．また,各ALUは別に定義された演算集合の任意のものを実行可能である．

ALU

IN

_A

IN

_B

OUT

_A

OUT

_B

図2.3 ALU

2.1.2 PE Connection (PEC)

PE Connection (PEC)は隣接するPE間のデータ転送に用いられ, 各ALU出力データの配置変更を行う機構である．PECはハードウェア設計時にあらかじめ決められた複数個の配線パターンのセットを有し，実行時には必要に応じてどれか一つを動的に選択可能である．例えば図2.2 のようにP Ei のALUからP Ei+1 のALUへとデータを転送する様々な配線パ

ターン (Connection Pattern)として，上下段のALUがそれぞれ２入力２出力でデータ入出

(31)

力可能な４種類の配線パターン (Connection Pattern)が用意されており，各PEC は独立にこれらのパターンのうちの1つを動的に選択可能な構造をとる. なお，配線パターンの種類は任意に決定可能である．種類を少なくすれば小面積となるが配置配線の自由度は下がる．一方で，配線パターンの種類を多くした場合，面積は配線の分だけ大きくなるが，配置配線の自由度は上がることになる．ただし，配線を選択可能とすることで配線制約が厳しくなり，配線不可能となるケースも存在することに注意したい．なお，各配線パターンはALUが２入力２出力の条件を満足していなければならない．つまり，全ての配線パターンはP Ei−1 のALU出力が２出力となり，P E_iにおけるALUが２入力２出力となり，P E_i+1のALUが２入力となるような配線でなければならない．

2.2 データフローグラフ

本論文で提案する手法は,データフローグラフを入力とし，前節でモデル化したパイプライン型アーキテクチャにマッピングすることを目的としている. 最初に，提案手法で使用するデータフローグラフの定義を行う．

提案手法のターゲットであるパイプライン型アーキテクチャモデルのループを持たない構造であることから，データフローグラフはDirected Acyclic Graph (DAG : ループなし有向グラフ)を採用した．DAGは，ノードが演算を表し，エッジがデータ依存関係を表現している. さらに，ALUが2入力2出力であることから，バイナリグラフを形成する．これらの条件を満たすDAGを，提案手法の入力とする．

G はノードの集合 V とノードを接続しているエッジの集合 E の 2 つの要素で構成されるグラフを示している．ノードの集合 V は，P ath_i,_v_j で構成され，これは入力からのパス長が i の j 番目のノードを表している．そのため，i と j は，i ∈ {0,1, ..., N − 1}, j ∈ {0,1, ..., M −1}となる．また，エッジの集合Eは(P ath_k,_v_l, P ath_k+1,_v_m)で構成され，

これは P athk,vl が入力ノード，P athk+1,vm を出力ノードとしたエッジを示している．つまり，k は，k ∈ {0,1, ..., N −2}^，l, mは，l, m ∈ {0,1, ..., M −1}^{となる．さらに，}ALUは 2入力2出力であるため，バイナリツリーを形成し，同一パス長のノードは各PEのALU数であるM以下とし，クリティカルパス長はパイプライン段数であるN以下とする．これらの条件を満たすDAGを提案アルゴリズムの入力とする．図2.4はPEの数がN = 5段，ALU

(32)

の数がM = 8の場合のDAGの例である．

図2.4 DAG

以上のように定義されたDAGのノードとエッジを，それぞれパイプライン型アーキテクチャの演算器（ALU）と配線へとマッピングされる．

(33)

第 3 ^章

提案手法

本章では，DAGの複雑度指標と，パイプライン型アーキテクチャ向けのマッピング手法についての提案を行う．

まず，コンパイラにおけるフィードバック機構の可用性を向上させるための複雑度指標について説明する．

4.1 ^{複雑度指標}

複雑度指標の提案では，DAGをパイプライン型アーキテクチャにマッピングするにあたり，

マッピング探索時間が問題となることに注目する．これは，コンパイラにおいてマッピングが成功しなかった場合にクラスタリングを再実行するというフィードバック機構が含まれるため

である．FlexSword^TM におけるフィードバック機構を，図5.43に示す．クラスタリングで

は，演算・ユニット対応情報を生成することで，データフローグラフにおけるパイプライン型アーキテクチャへの割当か所をクラスタリングするが，マッピング探索を行った結果，そのクラスタリングが実現できないケースが発生する．その場合，フィードバック機構を利用して，

再度クラスタリングや配置配線を行う必要が生じる．そこで，事前に配置配線の実行時間を予測することで，探索の短いクラスタリングを優先的に実行することが可能になると考えた．これにより，短い探索時間で多くのフィードバックを実行，もしくは少ないフィードバック回数で良いマッピング解を得るという効果を得ることができる．以上を踏まえて，マッピング探索時間がDAGのノード数やエッジ数によって変化することに注目した．これはDAGの規模や

(39)

複雑さによって，マッピング探索の困難さが変化する事を示している．DAGの複雑さと実行時間の関係が明らかになった場合，マッピング時間が短いと予想されるクラスタリング結果からマッピング探索を実行する事ができ，フィードバック機構を効率的に利用したコンパイラ提案を行うことが可能となる．さらに，マッピング探索の上限時間設定を行うことでマッピング時間そのものを短縮できる可能性がある．

以上のことから，DAGの規模や複雑さを，パイプラン型のALU数，配線数とDAGのエッジ数，ノード数を用いて表すComplexityという指標を導入した．Complexityの算出方法を式(4.1)に示す．

Complexity(G) = (V_num∗E_num)/(ALU_{SU M} ∗EDGE_{SU M}) (4.1) Complexity(G)はDAGGのComplexityを表している．VnumはGのノード数，Enumは Gのエッジ数を表しており，図5.43のクラスタリング結果より算出できる．また，ALU_{SU M} はアーキテクチャ全体における ALU 数，EDGESU M はエッジ数の総数を表しており，図 5.43のクラスタリングと配置配線によって算出できる，分子はDAGの規模を表しており，分母はアーキテクチャの規模を表している．これにより，様々な規模のパイプラン型アーキテクチャのALUと配線に対して，DAG Gのノードとエッジの充填率を得ることができる．充填率が高いほどマッピング探索領域が増えることから，これを複雑度指標とした．

動的再構成可能なパイプライン型 アーキテクチャ向け配置配線手法

動的再構成可能なパイプライン型 アーキテクチャ向け配置配線手法

肥塚 真由子

電気通信大学大学院情報システム学研究科 博士（工学）の学位申請論文

2013 年 3 月

動的再構成可能なパイプライン型 アーキテクチャ向け配置配線手法

博士論文審査委員会

主査 渡辺 俊典 教授

委員 本多 弘樹 教授

委員 吉永 努 教授

委員 古賀 久志 准教授

委員 近藤 正章 准教授

著 作 権 所 有 者

肥 塚 真 由 子

2013

Mayuko Koezuka Abstract

肥塚真由子

概要

目次

図目次

表目次

第 1 章

はじめに

1.1 本研究の背景と目的

1.1.1 LSI 市場の動向

1.1.2 Dynamically Reconfigurable Architecture (DRA)

1.1.3 パイプライン処理

1.1.4 コンパイラ構成

1.1.5 DRA におけるアプリケーション実装

DRA

構成情報 構成情報 構成情報 構成情報 保存メモリ 保存メモリ 保存メモリ 保存メモリ

I/Oデータ データ データ データ 保存メモリ 保存メモリ 保存メモリ 保存メモリ

分割結果 構成情報

1.2 関連手法

1.3 DRA 構造

1.4 本研究のアプローチ

第 2 章

パイプライン型アーキテクチャと データフローグラフのモデル化

2.1 パイプライン型アーキテクチャ

PE Connection (PEC

)

PE 0

PE 1

PE 2

PE N-1

ALU

PE Connection (PEC

)

PE Connection (PEC

)

ALU

ALU

ALU

ALU

ALU

ALU

ALU

ALU

ALU

ALU

ALU

Example of PE Connection

Connection Pattern 0 PE Connection

Connection Pattern 1

Connection Pattern 2

Connection Pattern 3

2.1.1 ALU

ALU

IN

IN

OUT

OUT

2.1.2 PE Connection (PEC)

2.2 データフローグラフ

第 3 章

関連手法の分析

3.1 全探索によるマッピング探索手法

3.2 SA によるマッピング探索手法

第 4 章

提案手法

動的再構成可能なパイプライン型アーキテクチャ向け配置配線手法

動的再構成可能なパイプライン型アーキテクチャ向け配置配線手法

肥塚真由子

電気通信大学大学院情報システム学研究科博士（工学）の学位申請論文

2013 ^年 3 ^月

動的再構成可能なパイプライン型アーキテクチャ向け配置配線手法

主査渡辺俊典教授

委員本多弘樹教授

委員吉永努教授

委員古賀久志准教授

委員近藤正章准教授

著作権所有者

肥塚真由子

第 1 ^章

1.1.4 ^{コンパイラ構成}

構成情報構成情報構成情報構成情報保存メモリ保存メモリ保存メモリ保存メモリ

I/Oデータデータデータデータ保存メモリ保存メモリ保存メモリ保存メモリ

分割結果構成情報

1.4 ^{本研究のアプローチ}

第 2 ^章

パイプライン型アーキテクチャとデータフローグラフのモデル化

第 3 ^章

第 4 ^章

4.1 ^{複雑度指標}