計測自動制御学会東北支部 第 229 回研究集会 (2006.6.9)
資料番号 229-7

貪欲算法に基づくロジックインメモリ VLSIのハイレベルシンセシス
High Level Synthesis of a Logic-In-Memory VLSI Based on a
Greedy algorithm○櫻田卓也 ∗ ，工藤隆男 ∗ ，亀山充隆 ∗∗○ Takuya Sakurada∗ , Takao Kudoh∗ , Michitaka Kameyama∗∗*八戸工業高等専門学校, **東北大学大学院情報科学研究科*Hachinohe National college of Technology, **Graduate School of Information Sciences,Tohoku University
キーワード : VLSI プロセッサ（VLSI Processor），ハイレベルシンセシス (High-Level-Synthesis)，ロジックイン
メモリ構造 (Logic-in-Memory Architecture)，アロケーション・スケジューリング (Allocation / Scheduling)，貪欲算法 (Greedy Algorithm)

連絡先 : 〒 039–1192 青森県八戸市田面木字上野平 16–1 八戸工業高等専門学校 電気情報工学科
工藤隆男，Tel.: (0178)27-7279，Fax.: (0178)27-7279，E-mail: tkudoh-e@hachinohe-ct.ac.jp

1.

はじめにリェ変換や絶対差分演算，行列演算，相関演算な
ど知能集積システム実現のために必須の演算が挙知能アルゴリズムと集積回路技術を融合したリげられる．

アルワールド応用知能集積システムの実現には，動的に変化する環境への高速応答性が重要になる．
1, 2, 3)しかしながら，外界からの信号に応じ処理を瞬時に切り替えながらの高速応答性を必要とする演算のように，処理アルゴリズムが条件分岐を有す

また，VLSI 製造技術の進展に伴う高集積化のため，ハイレベルシンセシスの重要性が高まっている 4) ．

る DFG で表される場合，最適なアロケーションとスケジューリングは条件により異なることから，あらかじめ決定することは困難である．よって，条件

処 理 す べきアルゴリズムがデータ依存グラフ(DFG) で与えられるとき，DFG に条件分岐がない処理を最高性能で実現するVLSIの設計においては，分岐後の処理に必要なアロケーションとスケジューリングをその都度高速に行うリアルタイムハイレ
ベルシンセシスが重要になる．

演算ノードの開始ステップの決定（スケジューリング）と演算ノードを実行する演算器の決定（アロケーション）を，可能な組合せの中からあらかじめ探索しておくことが可能である．条件分岐の

また，ディープサブミクロン VLSI プロセッサにおいては，シグナルインテグリティや配線遅延などの配線に起因する性能劣化が深刻になっている
5) ．特に，メモリ部と演算部との間に複雑な相互結ない DFG で表されるアルゴリズムには，高速フー–1–合回路網を備えるアーキテクチャにおいては，相互結合回路網が大規模になればなるほど配線問題

RRRPEPEPELMLMLMが深刻になりがちである．このことから，シンプルな相互結合回路網を有する並列構造 VLSIアーキテクチャが重要になる．
本稿では，そのようなハードウェアモデルとして，演算器に専用のローカルメモリを備えるモジューLogic-in-Memory module

ルを，シンプルな相互結合回路網で結合するロジッ
クインメモリアーキテクチャを対象とし 6, 7, 8, 9) ，演算器数制約下で処理時間最小化を達成するリア

Fig. 1

ハードウェアモデル

ルタイムハイレベルシンセシスの手法を提案する．
対象とするハードウェアモデルの場合，アロケー

2.

ハードウェアモデル

ションとスケジューリングは互いに依存することか
データ転送における配線遅延を小さくするため
ら，最適解の探索問題は組み合わせ問題になる．厳には，短い配線によるデータ転送を可能とする規密な意味での最適解を探索するためには，総当り則的な構造のハードウェアモデルが望まれる．こ的探索を行えばよい．しかしながら大規模な DFGのようなハードウェアモデルとして Fig. 1 のようの場合，組合せが爆発することから，高速応答性に 1 個の処理要素 (PE) と 1 ワードのレジスタ (R) とは期待できない．
ローカルメモリ (LM) を一体化したロジックインメ
このような問題を解決する方法として，演算ノーモリモジュールからなる空間並列構造のハードウェ
ドのスケジューリングの自由度（モビリティ）をアモデルをとりあげる．
用い，クリティカルパス上の演算を特定の演算器モジュール間のデータ転送をレジスタを介してにアロケーションする．次に，モビリティが小さ隣接するモジュールに限定することにより，デーいノードから，順に，局所的な転送時間が最小にタ転送用の配線を短くできる．各 PE は DFG の処なるアロケーションとスケジューリングを行う方
理に必要な演算器，たとえば加算器や乗算器など法を提案する．の演算器を備えており，アロケーションを行う演
この方法は，クリティカルパス上の演算を特定算ノードの種類に応じて演算を切り替えて実行での演算器にアロケーションすることにより，演算器きるものとする．
間のデータ転送時間を不要とし，さらには，クリこのハードウェアモデルの利点は，負荷分散タ
ティカルパス以外のノードについては，局所的なイプやデータ再利用タイプなどのように演算ノーデータ転送時間が最小になるようにアロケーショドの転送が少ないか，規則性のある転送のクラスンとスケジューリングを行うことにより，最適解に適する．の探索を行おうとする方法である．
以下の例については，隣接するモジュール間の最後に，提案の方法は，与えられる処理アルゴデータ転送に要する時間は1クロックステップとし，リズムに対し，処理時間を最小化するアロケーショ
演算に要する時間は 1 クロックステップとする．
ンとスケジューリングを高速で行えることを，実例を通して明らかにしている．

–2–

R

RR

N1

C.S.1

N1
1 clock
step

C.S.2

PEPEPE

N2

C.S.3

N2

C.S.4

N1

N2(b) Allocation 1(a) DFG

R(c) Case(b)

RPE

RPE

PE

C.S.1
C.S.2

(d) Allocation 2

Fig. 3N2

2 clock
steps

C.S.3
C.S.4

N1

N1

N2(e) Case(d)アロケーションとスケジューリングの依存性
印はデータの依存関係を表す．矢印の根本のノードは親ノード，矢印の先のノードは子ノードと呼N1N2

ぶ．子ノードの演算は親ノードの演算結果を必要とする．

N4N3

Fig. 3 に示すように DFG のノードを PE にアロケーションする場合，PE 間のデータ転送に必要なN5クロックステップ数は，転送のために通過するモジュール数に依存するため，スケジューリングはアロケーションが確定しないと決定できない．(a)の DFG に対して (b) のようにアロケーションする

Fig. 23.

データ依存グラフ (DFG)

場合，P E1 と P E2 は隣接しているので，通信時間アロケーションとスケジューリは 1 クロックステップ必要である．一方，(d) のよングの統合の必要性

うにアロケーションする場合，通信時間は 2 クロックステップ必要である．

PE 数を限定する本ハードウェアモデルに基づく

このようにアロケーションとスケジューリングはプロセッサ上で，DFG で与えられる処理アルゴリ不可分の関係にあることから，アロケーションとズムを最小処理時間で実行する場合，データ転送スケジューリングを統合する設計法が必要になる．

時間と演算時間とを合わせた処理時間全体の最小アロケーションとスケジューリングを同時に行化が重要になる．Fig. 2のDFGは，演算の依存関係

うため，Fig. 4 のように横方向に PE 番号，縦方向を表す．ノードは加算や乗算等の演算を表す．矢にクロックステップをとった表を用いる．この表–3–

Cell

++
****

++
-++--

-**

アロケーションとスケジューリングの探索空間

アロケーションとスケジューリングを同時に行う．

++

以降は，この表中の一つの升目をセルと呼ぶこと++にする．

提案法を用いた探索

4.1

問題の枠組み**Section C--にノード番号を書き込み配置していくことにより

4.

-**

++

++
Fig. 4--++

Section B

Section A

C.S. 1
C.S. 2
C.S. 3C.S. 4

PE 1 PE 2= Condisional branch= JoinFig. 5のように条件分岐を有するDFGの場合，セFig. 5

条件分岐を有する DFG

クションCの最適なアロケーションとスケジューリ
ングは，2 通り存在する．もし，N 通りの経路が存

4.2在する場合，N 通りの最適解が存在することから，後ろのセクションになるほど，N が膨大になり，N通りの最適解をあらかじめ記憶しておくためのメモリ容量が大きすぎるという問題がある．このような問題に対して，条件に応じて，セクションごとの最適解をリアルタイムで探索することが重要

貪欲算法は，優先度に基づき，局所的な最適解を成長させることにより，最終的に近似解を導き出す方法である．局所解に陥りやすいという欠点はあるものの，高速探索を可能とするという特徴に着目し，リアルタイムハイレベルシンセシスへの適用を考える．になる．

貪欲算法を用いると，Fig. 4 のセルに全くノー最適解の探索問題は Fig. 4 のセルへのノード配置問題となる．全ての可能な組み合わせを探索すれば，最適解を探索できる．しかし，総当たり的探索では，ノード数が多い場合，組み合わせ数が爆発することから解の高速探索は困難になる．そこで，近似解の探索が重要になる．

貪欲算法

ドが配置されていない状態から始まり，優先度に従って逐次的にノードを配置することにより解を構成できる．セルへの配置は，処理時間を可能な限り最小化するため，親ノードから子ノードへの局所的な転送時間を最小にするセルへの配置を行う．すなわち，クロックステップ差が小さいセルに配置する．配置するセルの候補が複数個ある場
合には PE 番号の小さいセルに配置する．

–4–N1N2N4N3N5C.S.1

N1C.S.2
C.S.3(a) DFG

N3N1

N2

N4N4N3N5N5(b) ASAP(c) ALAP

ステップ１Fig. 64.3

N2

モビリティ

配置可能なセルが少ないノードから配置するた

N1N2め，優先度には，モビリティを用いる．モビリティ
はASAPスケジューリングと ALAPスケジューリン

N4N3グから求める．２種類のスケジューリングのクロッ

CriticalPath

クステップの差が，各ノードのモビリティとなる．

4.4N5解の探索

解の探索手順について述べる．以下の説明では，

Fig. 7

ステップ２モビリティが0のノードを連ねた一つの経路をクリティカルパスと呼ぶ．親ノードから子ノードへの4.4.1

ステップ１：モビリティの算出

Fig. 6 に示すように，モビリティは ASAP スケジ

データ転送に要する時間を局所転送時間と呼ぶこューリングと ALAP スケジューリングから求める．とにする．
解の探索について述べる．まず，局所転送時間

例として，(a)のDFGのモビリティを求める．(b)はを最小化するため，クリティカルパスのノードをASAPスケジューリングで，(c)はALAPスケジュー同一のPEで連続したクロックステップに配置する．

リングである．ASAP スケジューリングは，PE のこれにより，局所転送時間を 0 にできる．

数を無制限とし，また，転送時間を考慮しない場

次に，モビリティの小さいノード（但し，同じモ合に，それぞれのノードを可能な限り早いクロッ

ビリティのノードが複数あるならノード番号の大クステップにスケジューリングしたものであり，同きいノード）から順にセルへ配置していく．この様に，ALAP は最も遅いクロックステップにスケときの配置するセルを選択する．その基準は局所ジューリングしたものである．この 2 種類のスケ転送時間を最小にするセルに配置するものとする．

ジューリングでのクロックステップの差が，それこれにより局所的な転送時間を最小化しつつ，スぞれのノードのモビリティとなる．N3 のモビリティ

ケジューリングとアロケーションを同時に行える．

は 1，その他のノードのモビリティは 0 である．

–5–PE 1

PE 1

PE 2

C.S.1

N2

C.S.2

N1

C.S.2

N1

C.S.3

N4

C.S.3

N4

C.S.4

N5

C.S.4

N5

Fig. 8
4.4.2

C.S.1

PE 2

Feasible Cells
(a)

ステップ３

ステップ２：クリティカルパスの選択

PE 1

クリティカルパスを求めるために，モビリティ

C.S.1

N2が0のノードを連ねた一つの経路を選び出す．複数

C.S.2

N1の候補がある場合，経路の先頭のノード番号が小C.S.3

N4

さいものを選び出す．Fig. 7 では，クリティカルパC.S.4N5スの候補として，N1 ・N4 ・N5 の経路と N2 ・N4 ・PE 2
N3(b)N5 の経路があるが，N1・N4・N5 の経路をクリティカルパスとしている．

Fig. 94.4.3

ステップ３：クリティカルパスのノードの配置

ステップ４へ配置する．その後に N3 を配置する．Fig. 9(b) の網掛けのセルに配置可能である．配置可能なセル

クリティカルパス上のノードの局所転送時間を 0のうちクロックステップが最大のセル，すなわちにするため，Fig. 8 のように，クリティカルパス上局所転送時間が最小となるセルへ配置する．解をのノードを同じ PE 番号の連続したクロックステッ

Fig. 9(b) に示す．

プへ配置する．

4.4.4

5.

ステップ４：それ以外のノードの配置

提案手法の探索時間と解の精度を調べるためにクリティカルパス上に存在しないノードは，モビリティの小さい順に配置する．モビリティが同じノードが複数ある場合は，ノード番号が大きい

典型的な DFG のテンプレートである FIR と EW を用い，PE 数が 4 個の場合について評価を行う．

ノードから配置することとする．
配置するセルの選択は，子ノードとの依存関係

評価

5.1

探索時間を満たすセルのうち一番大きなクロックステップ

提案手法は，2 種類の DFG において 10−3 秒以下のセル，すなわち，局所的転送時間が最小になるの探索時間となった．総当たり法ではノード数がセルを選択する．この例ではN2 の配置となる．N210 個の DFG で 103 秒程度の探索時間が必要であっを配置可能なセルは Fig. 9(a) の網掛けのセルであた．提案手法は総当たり法と比較した場合に高速る．網掛けのセルのうち，PE 番号の小さいセルであると言える．

–6–

PE1 PE2 PE3 PE4
C.S.1(a) FIR

C.S.2
C.S.3
C.S.4
C.S.5

2311171841210913

C.S.6
C.S.7
C.S.8
C.S.9
C.S.101920212223141615

15687(b) Feasible Solution

Fig. 10

評価１PE1 PE2 PE3 PE4
C.S.1
C.S.2
C.S.3
C.S.4
C.S.5
C.S.6
C.S.7
C.S.8
C.S.9
C.S.10C.S.11
C.S.12
C.S.13
C.S.14(a) EW

1235681013161923273132

47912
15172024283334

18222630(b) Solution

Fig. 11

評価２–7–1114212529

ルである．
一方，N1 とN3 との依存関係を満たすセルはFig. 12(c)N1PE 1 PE 2N2の斜線のセルである．ここで，(a) より N3 は N1 とN4 との依存関係を同時に満たす必要がある．このN3N1N4(a) DFG



N3ためには，(b)の斜線のセルと(c)の網掛けのセルのN2交わりのセルが必要である．しかしながら，(d) にN4示すように交わりのセルは存在しない．よって N3を配置できない．従って，提案手法では，クリティ(b)Dependencein N3 and N4

カルパスの一部に複数のパスを有する場合，可能解を探索できていない．

PE 1 PE 2

PE 1 PE 26.

まとめN1

N1

N2

N2

ムハイレベルシンセシスについて，局所転送時間N4を最小にすることで処理時間全体を最小にする方

N4N3(c)Dependencein N3 and N1

条件分岐を有する DFG を対象とするリアルタイ(d)Unsatisfied
dependencies in N 3法を提案した．しかしながら，クリティカルパスの一部に複数のパスを有する場合，可能解を探索できていない．このような場合を除き，提案手法

Fig. 125.2

可能解を得られない例

は，最適解を高速探索できるなどの有効性を実験的に明らかにした．この方法は，条件分岐のない解の精度DFG に対しても有効である．
FIR の DFG と結果を Fig. 10 に示す．FIR の場合，知能集積システム用 VLSI の実現には，リアルタ最適解を探索できた．表中の数字はノード番号をイムハイレベルシンセシスは重要であることから，表している．

提案手法の改良としてクリティカルパスの一部にEW の DFG と結果を Fig. 11 に示す．EW では可含まれる 2 個以上のパスの一方に冗長ノードを入能解を探索できていない．Fig. 11 の表中，下線付れる，あるいは分岐している部分のパス上にあるきのノードが DFG の依存関係を満たしていないたノードを特定の1個のPEにアロケーションするなどめである．

し，適用限界を拡大することが今後の課題である．

可能解を探索できない原因について考察する．
ここで，Fig. 12(a) の DFG について，モジュール数

本研究は，科学研究費補助金の交付を受けて行った研究の成果である．

を 2 個とし，アロケーションとスケジューリングを考える．モビリティは全てのノードで０になる．そこで，N1・N2・N4 をクリティカルパスとする．ク

参考文献

リティカルパスをセルに配置した結果が Fig. 12(b)1) 今井正治：ASIC技術の基礎と応用 亀山充隆，である．最後に，残った N3 を配置する．N4 と N3

第 8 章：ロボットエレクトロニクス，118/140，との依存関係を満たすセルはFig. 12(b)網掛けのセ

電気情報通信学会 (1994)–8–2) 亀山充隆，藤岡与周：ロボット用VLSIプロセッ
サシステム，日本ロボット学会誌，14-1, 22/25(1996-1)
3) 工藤隆男，亀山充隆：ロジックインメモリ構
造に基づく知能集積システム用 VLSI プロセッ
サのハイレベルシンセシス，電気学会論文誌

C, 123-8, 1374/1381 (2003)
4) Gajski, D., Dutt, N., Wu, A. and Lin, S.:
HIGH-LEVEL SYNTHESIS Introduction toChip and Sustem Design, 359, Kluwer Academic Publichers (1992).
5) 桜井貴康：総論−システム LSI のアプリケー
ションとシステムLSIの課題, 信学会誌, 81-11,1082/1086 (1998).
6) Kauts, W.H.:Cellular Logic-in-Memory Array, IEEE Trans. Computers, 18-8, 719/727(1969).
7) Hanyu, T. and Kameyama, M.:MultipleValued
ture

Logic-in-Memory

Basedon

VLSI

Architec-

Floating-Gate-MOS-Pass-Transistor Logic, IEICE Trans. Electron,28-9, 1662/1668 (1999).
8) 工藤隆男，羽生貴弘，亀山充隆：ロジックインメモリアーキテクチャに基づく道路抽出 VLSI
プロセッサの構成, 計測自動制御学会論文集,

36-11, 1009/1018 (2000).
9) 張山昌論，工藤隆男，亀山充隆：最適アロケーションに基づく道路抽出 VLSI プロセッサとその高安全知能自動車への応用, 計測自動制御
学会論文集, J84-D-1-6, 531/539 (2001).

–9–