Japan Advanced Institute of Science and Technology

(1)

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

FPGAを用いたCKYパージングの高速化

Author(s)

伊藤, 靖朗

Citation

Issue Date

2003‑03

Type

Thesis or Dissertation

Text version

author

URL

http://hdl.handle.net/10119/1710

Rights

Description

Supervisor:中野浩嗣, 情報科学研究科, 修士

(2)

修士論文

を用いた

パージングの高速化

北陸先端科学技術大学院大学情報科学研究科情報処理学専攻

伊藤靖朗

年月

(3)

修士論文

を用いた

パージングの高速化

指導教官

中野浩嗣助教授

審査委員主査

中野浩嗣助教授

審査委員

浅野哲夫教授

審査委員

金子峰雄教授

北陸先端科学技術大学院大学情報科学研究科情報処理学専攻

伊藤靖朗

提出年月年月

(4)

概要

本論文ではを用いた文脈自由文法に対するパージングを高速に実行するハードウェアの実装法を提案する

とはユーザによって設計されたハードウェア設計を即座に埋め込むことができるプログラム可能なであるユーザのハードウェア論理設計はベンダの設計ツールを用いることによってに埋め込むことが可能であるとりわけ既存のソフトウェアアプローチより高速で効果的なベースの手法を開発することが目標である

パージングとは文脈自由文法と文字列が与えられたときにがを導出するかどうか判定するものであるこのパージングはの長さがのときに

時間で導出するかを判定するできることが知られている任意の文脈自由文法が与えられたときにその文法に対するパージングを行うハードウェアの^! 記述を生成するハードウェアジェネレータを示す生成された記述はに実装され任意の文字列に対してがを導出するかを判定する ^"#$社のを用いて実際に動作させ性能評価を行った結果としてソフトウェアによるパージングより最大で約倍の高速化に成功した

(5)

第

章はじめに

背景

文脈自由文法によって記述された形式言語はパターン認識やプログラミング言語及び自然言語処理などの多くのアプリケーションで使用されるそのような形式言語に対する解析速度はアプリケーションの実装において重要な問題となる例えば自然言語処理アプリケーションの特別なケースでは実時間の制約を考慮する必要があり効率的な解析法を提案する必要があるそのようなアプリケーションの典型的な例を以下に示す

データ処理情報検索や文章抽出を行う際に光学文字認識^./0 ¹⁰

20##をすると同時にスペルチェックを行うような技術では言語に関する構文情報の統合により構文解析の一層の処理速度向上を要求する可能性があるこのような巨大な量のデータを処理する必要がある場合効率的かつ単純構造の解析プロセッサが要求される

ヒューマンマシン・インターフェース音声認識インターフェースではリアルタイムに解析を行う必要があり構文解析の性能向上が必須である

とはユーザによって設計されたハードウェア設計を即座に埋め込むことができるプログラム可能なである典型的な

は書き換え可能なロジックセルの配列分散したメモリブロックそしてそれらを結合するプログラム可能な配線から成るロジックセルは通常入力論理関数もしくは^&入力^%出力のマルチプレクサ幾つかのフリップフロップを持つメモリブロックは別々のアドレスに対して同時にデータの読み込みと書き込みが可能なデュアルポート^{2 3}であるユーザのハードウェア論理設計はベンダの設計ツールを用いることによって

に埋め込むことが可能である本研究では有用な計算を高速化するために

を使用するとりわけ既存のソフトウェアアプローチより高速で効果的なベースの手法を開発することが目標である

(8)

部分計算

本研究では部分計算^4%5の概念に基づきを用いた計算の高速化を行う与えられた問題を解くために評価する関数をとするただしその関数はを固定して繰り返し評価されることが多いとするその場合 ⁶ のようなインスタンスに特化した関数を評価することによっての計算の簡単化が可能である本研究のアイディアは固定したと変数に対してを計算するために最適化したハードウェアを作成することであるつまり次のつの性質を満たすが必要となる問題に対し問題のインスタンスに特化した手法をを用いて示していく

% 固定したの値が問題のインスタンスに依存する

問題を解くために様々な値をとる変数に対しての値が繰り返し評価される

パージングアルゴリズム

本論文では先に示したベースのアプローチを用いて文脈自由文法のパージング^4%5を文法を固定することにより高速化するハードウェアを示す入力文字列の長さをとしたときパージングは時間で計算することはよく知られている^4%5 文脈自由言語のパージングは自然言語処理^4' ^%'5 コンパイラ^4%5 バイオインフォマティックス^4%&5など様々な分野において多くのアプリケーションが存在する幾つかの研究において文脈自由言語のパージングの高速化が行われてきた^4&⁷^%%^%'5 長さの文字列に対するパージングが^{2 3}上で台のプロセッサを用いて時間で行われることが示された⁴⁷⁵ またメッシュ結合のプロセッサ列を用いることによってパージングが台のプロセッサを用いて時間台のプロセッサを用いて時間で実行可能である^4%%5 これらの並列アルゴリズムは少なくとも台のプロセッサが必要なので大きなに対しては非現実的である ^88#ら

4()5は文脈自由文法の制限したクラスに対してパージングを行うハードウェアを示しを用いてテストを行ったしかしながらハードウェア設計と制御アルゴリズムはメッシュ結合したプロセッサ上で行うもの^4%%5と本質的に同じでありインスタンスに特化してはいなかった

全体の流れ

文脈自由文法のパージングを行うインスタンスに特化した手法のために任意の文脈自由文法に対するパージングを行う ^!ソースを生成するハードウェアジェネレータを提案するを文脈自由文法を文字列をブール変数を返す関数とするただしはがを導出しかつそのときに限り^,29:を返すものとする生成された^!ソースは^"#$社の^:ロジックデザインツール^4%)5を用いて

(9)

!

"

!

"

!

"

図 ^%% ^.; ^1< ^/8# ⁸⁸

コンパイルを行うそして得られたオブジェクトファイルを ^"#$^$=シリーズの

4%(5にダウンロードするとは文法を固定したを計算する回路となるつまり入力文字列に対してがを導出するかどうかを調べる回路になる図^%%

にパージングのシステムを示すホストによって文字列が与えられはこれらの文字列がで導出可能かどうかすなわちの結果を返す

どれだけがパージングを高速化しているかを明らかにするためにソフトウェアと比較するこのソフトウェアのアルゴリズムは個の生成規則全てを時間で調べることによって計算を行うこのアルゴリズムを用いたパージングは時間で計算可能である一方を用いた手法はパージングを時間で計算可能であるただし文脈自由文法の非終端期号数をとする常により理論的には本研究の提案手法はソフトウェアアプローチよりも高速である

そこで実際に^$=シリーズのを用いて性能評価をしソフトウェアと比較したその結果ソフトウェアに対して提案手法は最大で約倍の高速化に成功した

本論文の構成

本論文は次のように構成される第章ではパージングについて述べる第章ではパージングの評価について説明する第^&章ではパージングを行うハードウェア実装を紹介しを用いて実際に動作を確認した第^'章では実用的なサイズのパージングのハードウェア実装を示し実際にを用いて動作させた第⁽章では本研究の成果と今後の課題について述べる

(10)

第

章

パージング

本章ではパージングについて説明をする

文脈自由文法

文脈自由文法^#$= とは^&つ組

6>

によって定義される文法で各成分は次のものとする

非終端記号の集合

> 終端記号の集合

生成規則の集合

開始記号ただし

チョムスキー標準形

にある各生成規則が

>

のどちらかの形式であるような文脈自由文法をチョムスキー標準形 ^18? ^*

*と呼ぶ

パージング問題

今回扱ったパージング問題とは与えられたチョムスキー標準形の文脈自由文法と

>上の入力文字列に対して開始記号がを導出するかどうか決定する問題である例えば ⁶^>が次のような文法であるとする

(11)

>6

6

このときが次のようにを導出するので文脈自由文法はを導出する

パージング

チョムスキー標準形の文脈自由文法と文字列に対してがを導出するかどうか決定するパージング法について説明する文字列を長さの文字列 ⁶

とするただし各 ^% は ^> の要素であるまたの部分集合を

45% で表し ⁴⁵の各要素は部分文字列を導出するものとするパージングのアイディアは次の関係を用いて各 ⁴⁵を計算することである

45 6

45 #

4@%5

次元配列はテーブルと呼ばれる文法が文字列を生成しかつそのときに限り ^4%⁵ にが含まれるの部分集合間のバイナリ演算を

6 # と定義するこのを用いてパージングの詳細を次に示す

パージング

% 45

A + %

45 A + # %

A

& A %<# %

' A %

( 4545

45

4@%5

最初の行はテーブルを初期化し次の^&行はテーブルの計算を行う図^% はと文字列に対するテーブルを図示したものである ^4%^'5 よりが文字列を導出することがわかる

(12)

# $ % & '

#

$

&

'

%

図 ^% ^,1 ^A ^#

最後の^&行がパージングの計算の大半を占めることは明らかである ⁽行目を計算するのに必要な時間をとすると ^B(行目の計算時間は

6

%

(

@

となる

(13)

第

章

パージングの評価

本章では生成規則の各規則に対してかつであるかどうか調べるつまりを計算するアルゴリズムに焦点を当てて説明する

ソフトウェアアルゴリズム

この節では章で述べた任意の非終端記号の集合とに対しての計算を行う逐次ソフトウェアアルゴリズムをつ示す

アルゴリズム

最初のアルゴリズムは生成規則の各規則に対してかつであるかどうか調べるアルゴリズムである適当なデータ構造を用いることによって ^% 時間でこれを行うことが可能なことは明らかであるよってにある形式の生成規則数をとするとは時間で評価可能である以上よりこのアルゴリズムを用いるとパージングの計算時間は時間である今後このアルゴリズムをアルゴリズムと呼ぶ

アルゴリズム

番目のアルゴリズムはの計算にルックアップテーブルを用いるアルゴリズムで今後アルゴリズムと呼ぶこのアルゴリズムは各のすべての組合せに対しての値をあらかじめ計算しテーブルに記録しておきを計算するときにはそのテーブルを参照する非終端記号の集合が個の非終端記号を持つとし

6

であるとする与えられたをビットベクトルであらわし各 ^% について ⁶^%でありかつそのときに限りであるとする同様にもビットベクトルであらわすを計算するためにはメモリ上にビットのテーブルが必要であるつまりアドレスがビットでデータがビットのメモリそのテーブルの番目のエントリーはを記録されるこのときは ⁶ を表すビットのベクトルであるそのようなテーブルが利用できればが ^% 時間で計算

(14)

ができることは明らかであるしかしながらがそれほど大きくないときでもそのテーブルは巨大になってしまうに ⁶^(& 個の非終端記号があるときテーブルのサイズは ^(&⁶ ^%ビットになり極めて巨大になる

そこでテーブルのサイズを減らすために^,アルゴリズムを変更するを ⁶

%

であらわされる同じサイズの部分集合に分割するつまり集合を各部分集合が個の非終端記号を含むように個の部分集合に分割するはより大きな整数値をとるが実際には ^%(より大きくなることはないを求めるために次の個のバイナリ操作

%

を用いる

8

#

6

#

よって次のように表すことができる

6

このようにとのすべての組合せに対してを評価することによってを計算できる前述のとおりはサイズのテーブルを参照することによって計算可能であるよっては個のテーブルを参照することによって時間で求めることが可能であるテーブル全体のサイズはビットである ⁶ ^(& ⁶^- のときテーブルは ⁶^'( ³ビットとなり実現可能であるしかしながら ⁶^(&回テーブルを参照する必要があるテーブルのサイズとその参照回数は生成規則の数に依存しないことに注意するこのように ^,アルゴリズムはの値が大きい場合でも効果的である

ハードウェアアルゴリズム

を用いてを計算する回路を構築することによっての評価を高速化することについて説明するを計算する回路を今後回路と呼ぶことにする各

をそれぞれビットのビット列とで表すことにする

回路は ⁶ を求める回路つまりとからを計算する回路とする次にを求める方法を示すが生成規則の中で非終端記号を左側にもつ生成規則であるとするは次式

6

で計算される

そこで生成規則から上記の式に対応するハードウェア記述言語を生成するプログラムの作成を行ったこのプログラムはテキストファイルに書かれた生成規則から各を

(15)

!

"

#

$

図 ^% ^!によるサブモジュールの記述例

計算する回路記述を出力する今回はや⁸⁰のようなハードウェア記述言語である

= !を用いて回路記述を行ったこの回路はメモリアクセスの制御部やと間のインターフェイスを含むメインモジュールに対するサブモジュールに相当する生成されたサブモジュールの記述例を図^%に示す

%行目はモジュールの名前とそのモジュールの入力と出力と名前の定義であるその入力と出力の詳細が行目と行目に定義されている ^'行目から⁷行目では生成規則に従って出力ベクトルの各エントリーの計算を行うこのサブモジュールの回路図を図

に示す先に示したとおり入力の個の^*!ゲートと ^% 個の^.2ゲートで構成される組合せ回路によってを計算することが可能であるこの回路の深さ組合せ回路の入力から出力までのゲート数は ^%^@^% である生成規則の中で

の形式が個あるとき個の^*!ゲートと個の^.2ゲートで構成される組合せ回路でを計算することが可能である常にだから回路の深さは ^%^@^% ^@^% より深くなることはない以上よりパージングはこの回路を用いることによって時間で行うことができる図は

の回路を図示したものであるは^'個の生成規則と個の非終端記号があるから回路は^'個の^*!ゲートと ^'⁶ 個の^.2ゲートから構成される

%%節で示した^*+アルゴリズムはを計算するのに時間 ^%節で示した^,アルゴリズムは時間必要であることを示した一方に対する回路ではに比例した遅延時間である常にが成立するのでに対する回路は理論上逐次アルゴリズムよりも高速である

(16)

図 ^,1 ^00;^A ^0/;#

性能評価

を計算するハードウェアとソフトウェアを実装し性能評価を行ったこのときタイミング解析には社⁴⁵の^C;;8 ⁴⁵ 回路のテストには社の^:"

シリーズの^Dの内部メモリと^%(のロジックエレメントを持つ^&万ゲート相当の:&:D('=%"を用いた性能を評価するために次に示す環境で実行し性能を計測した

#"# %) E

メモリ ^{2!2 3} ^D

#;$ #&7

関数を計算するハードウェアとソフトウェアの実行時間のグラフを図に示す図より ^(&ビットのベクトルを用いた実装よりビットのベクトルを用いた実装の方が実行時間が短いことがわかる実験に用いたはビット⁹なので ^%ワードでビットのベクトルを表現することが可能である今回の実装では非終端記号の集合をビットのベクトルであらわし非終端記号の数がのときはビットのベクトル非終端記号の数が^(&のときは^(&ビットのベクトルを用いたこのため^(&ビットの実装ではワードで計算を行う必要があるのでビットの実装と比べて余分なオーバーヘッドが存在するよって^(&ビットのベクトルを用いた実装よりビットのベクトルを用いた実装の方が実行時間が短い

*+アルゴリズムはすべての生成規則についてかつであるかどうか調べるアルゴリズムなので^*+アルゴリズムの計算時間は生成規則数に比例

(17)

10 ^-3 10 ^-2 10 ^-1 10 ⁰ 10 ¹ 10 ² 10 ³

32 64 128 256 512 1024 2048 4096 8192 16384

Time [ u s]

Number of Rules

Circuit(32bit) Naive(32bit) Table(32bit) Circuit(64bit) Naive(64bit) Table(64bit)

図 ^/;# ^+;

している

一方^,アルゴリズムの実行時間は生成規則数に依存せずテーブルのアクセス回数に依存するよって^,アルゴリズムの実行時間は生成規則数が変わってもだいたい一定であるまた^,アルゴリズムはを求めるために非終端記号数がのとき回テーブルを参照する必要があるこのためが大きくなるに従って実行時間も長くなっている生成規則数が少ないとき^*+アルゴリズムの方が^,アルゴリズムより実行時間が短いがの数が多くなるにつれて^,アルゴリズムの方が^*+アルゴリズムよりかなり高速に実行される

を計算するのに本研究で用いたハードウェアの手法では^(&ビットのベクトルを用いた場合^,アルゴリズムと比べほぼ^%倍の高速化を達成したまたビットのベクトルを用いた場合は^%倍近くの高速化が得られた ^*+アルゴリズムと比較すると ⁶^%(-&のとき最も差があらわれ ^(&ビットのベクトルのとき約倍ビットベクトルのとき約⁾倍ハードウェアが^*+アルゴリズムより高速である本研究で用いたハードウェアの実装では非終端記号数をあらわすビットのベクトルのサイズに実行時間は依存しないよって ^(&ビットのベクトルを用いたときとビットのベクトルを用いたときのハードウェアの実行時間はほとんど同じである

(18)

まとめ

節より本研究で提案したハードウェア手法がソフトウェア手法と比べて有効であることがわかったこのハードウェア手法を用いたパージングの実装を次章で説明する

(19)

第

章プロトタイプの作成

本章では前章で説明した回路を用いてパージングを行うハードウェア実装の説明を行う

パージング回路

ここではパージングを計算する回路の説明を行うこの回路の基本的な構成要素を次に示す

B ビットワードデュアルポートメモリ

B

を計算する回路

B 個の^.2ゲート列

B ビットレジスタ

図^&%にパージング回路のブロック図を示すビットワードメモリはテーブルの内容が記憶される入力 ^4%^%5 ⁴⁵ ⁴⁵がビットワードメモリに入力されるビットワードメモリには処理をしているテーブルの^%行分が記憶されるつまりテーブルの行目 ^4%⁵⁴⁵が記憶されるこのときはパージングの行目に現れる変数であるビットレジスタはパージングの⁽行目で計算される ⁴⁵ が格納される個の^.2ゲート列は ⁽行目の

F

G を計算するために用いられるビットワードメモリは回路に ⁴⁵ を表しているビットのベクトルを入力として与える同様にビットワードメモリは ⁴^@^%⁵に対するビットのベクトルを出力する回路はそれらを受け取り

45

4@%5に対するビットベクトルを計算するこのハードウェア実装を用いることでパージングの⁽行目は^%クロックサイクルで計算されるこれよりパージングはクロックサイクルで行うことが可能であるさらに実装において ^%クロックサイクルはに比例するよって計算時間はである

(20)

( ) ( )

( ) * +

(

図 ^&% ^1< ^/##^A ¹ ^/8#

!,"

!#"

!$"

!%"

図 ^& ^##¹

回路の並列化

ここでは複数の回路を用いたパージングの並列化について説明するこのとき並列にテーブルにアクセスする必要があるのでテーブルを個のサブテーブル ^% ^%に分割するこのとき^!は ⁶^!を満たすように ⁴⁵を格納する図^&にテーブルを^&分割したときの図を示す図を見るとわかるようにテーブルの各列にある連続した個の要素 ⁴⁵⁴^@

%54@ %5は別々のサブテーブルに格納されているこのとき各サブテーブルが異なるメモリバンクに格納されていれば連続した個の要素に同時にアクセスすることが可能であるこのテーブルの分割により個の回路を用いてパージングの並列化を可能にする上記の並列化の性能を評価するために複数の回路を用いてパージングを行う回路の実装を行った

並列化したパージング回路で用いた基本的な構成要素を次に示す

B ビット

ワードメモリバンクデュアルポート個

(21)

¾

図 ^& ^/## ^A ¹ ^/8# ^A ⁶^&

B ビット

ワードメモリバンクデュアルポート個

B

を計算する回路個

B 個の^.2ゲート列個

図^&に並列化したパージング回路の実装を示す個のビット

ワードメモリバンクには個のサブテーブルが格納され各サブテーブルにつき^%つのバンクが用いられるまた個のビット

ワードメモリバンクには処理をしているテーブルの^%行分が記憶されるつまり ⁴⁵ の計算を行っているときテーブルの行目 ^4%⁵⁴⁵⁴⁵が記憶されるこのとき ^! 番目のバンク ^! に

4!@%54!@ @%54!@ @%5が格納される ^4%^%5⁴⁵^4%⁵⁴⁵

4% 5 4 @%5が異なるメモリバンクに格納されているからの個の評価 ^4%^%5 ⁴⁵^4%⁵ ⁴⁵ ^4%⁵ ⁴^@^%⁵が^%クロックサイクルで評価可能である以上のことよりパージングを倍高速化することが可能になるよってパージングの計算時間はのとき

である

(22)

性能評価

パージングを行うハードウェアのプロトタイプの作成を行い性能評価を行ったこのとき節と同様にタイミング解析には^C;;8 回路のテストには^:"シリーズの^Dの内部メモリと^%(のロジックエレメントを持つ^&万ゲート相当の:&:D('=%"を用いた性能を評価するために次に示す環境で実行し性能を計測した

#"# %) E

メモリ ^{2!2 3} ^D

#;$ #&7

非終端記号と入力文字列長が ⁶ ⁶ のときのパージングの計算時間を図^&&に示すハードウェアは回路を^%個もつ回路^#=00;個もつ回路^!;=00; ^&個もつ回路^C;=00;を用意しソフトウェアと実行時間の比較を行ったソフトウェアは ^*+と^,アルゴリズム共に図に見られるパターンと同じであるこれはで費やされる時間が計算時間の大部分を占めるからである

#=00;も図に見られるパターンとだいたい同じであるまた^&節で示したとおり^!;=00;もしくは^C;=00;は実際に高速化されていることがわかる

Naive Table Single-circuit Double-circuit Quad-circuit

10 ¹ 10 ² 10 ³ 10 ⁴ 10 ⁵ 10 ⁶

32 64 128 256 512 1024 2048 4096 8192

Time [ u s]

Number of Rules

図 ^&& ^/;# ^A ¹ ¹^<1 ⁶ ^# ⁶

(23)

10 ¹ 10 ² 10 ³ 10 ⁴ 10 ⁵ 10 ⁶ 10 ⁷

64 128 256 512 1024 2048 4096 8192

Time [ u s]

Number of Rules

Naive Table Single-circuit Double-circuit Quad-circuit

図 ^&' ^/;# ^A ¹ ¹^<1 ⁶^(&^# ^! ⁶

次に⁶^(& ⁶のときのパージングの計算時間を図^&'に示す ⁶⁶ のときパージングの実行時間のグラフとだいたい同じパターンであることがわかる前に述べたようにソフトウェアで^(&ビットベクトルを用いる方法では余分なオーバーヘッドが加わるしかしハードウェア実装ではこの余分なオーバーヘッドは発生しないその結果ソフトウェアの実行時間は長くなっていることがわかる ⁶^&-の^C;=00;

を構築するのに約⁷⁽個のロジックブロックが必要である ⁶^&7( の^C;=00;

を構築するのに必要なロジックブロックは今回使用したの持つロジックブロック数を超えてしまうよって^C;=00;は ⁶^&- までである

,アルゴリズムソフトウェア手法に対するハードウェア手法のスピードアップ率を示した表を表^&%に示す ⁶⁶のとき本研究で実装したハードウェア手法は

#=00;で約^&倍 ^!;=00;で約^'倍 ^C;=00;で約⁾倍の高速化を達成したさらに ⁶^(& ⁶ のとき ^#=00;で約^&(倍 ^!;=00;で約^'- 倍 ^C;B00;で約^)'倍の高速化を達成した以上の結果より本研究のパージングを行うハードウェアの手法は実際に有効な手法であることが言える

6 のときの^#=00; ^!;=00; ^C;=00;を構成するのに必要なロジックブロックの数を図^&(に示し ⁶^(& のときのを図^&)に示す生成規則が増えるに従ってロジックブロックの数が増加していることがわかる先に述べた通り ⁶^(&のときの^C;=00;は ⁶^&7( のとき使用したの持つロジックブロック数を超えてしまうので ⁶^&- までである

(24)

表 ^&% ^/=;/ ^A ¹ ^1< ^//01⁺ ¹ ¹

66 6(&6

# !; C; # !; C;

' && B B B

(& ' ' ' & &%7 (%%

%- 7 & '% 7' '%7 )%

'( ' ' &&% ')) )

'% ) &( (& &'& '' )(

%& - &- (( &% '% )&

&- ( &' ( ( &)' (

&7( ( & &% ( &%- B

-%7( %- ) %& &- B

次に ⁶ のときの^#=00; ^!;=00; ^C;=00;の最大動作周波数を図^&-に示し ⁶^(&のときのを図^&7に示す生成規則が増えるに従って最大動作周波数が減少していることがわかるこれは生成規則が多くなると回路の深さが深くなり回路遅延が増大するからであるこのことはアルゴリズムの計算時間に大きく影響する

まとめ

本章ではパージングを高速化に実行するハードウェア手法を提案したまた実際に^:"シリーズのを用いて動作を確認し性能評価を行ったハードウェアの性能を評価するためにソフトウェアの手法を実装し性能を計測したその結果よりソフトウェアの手法と比べて最大で約^)'倍の高速化に成功したしかし実際の例として英語のパージングを行うときには入力文字列長は約^% 非終端記号数は約生成規則数は約^%)で本章で扱ったものよりもかなり大規模なものである^4%5 よって^'章では実用的なハードウェア実装について述べる

(25)

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

32 64 128 256 512 1024 2048 4096 8192

Single-circuit Double-circuit Quad-circuit

Number of Production Rules

Number of Logic Blocks

図 ^&( ^*; ^A ⁰ ^0?8 ^;8 ^0/; ¹ ¹^<1 ⁶

0 2000 4000 6000 8000 10000 12000

64 128 256 512 1024 2048 4096 8192

Single-circuit Double-circuit Quad-circuit

Number of Production Rules

Number of Logic Blocks

図 ^&) ^*; ^A ⁰ ^0?8 ^;8 ^0/; ¹ ¹^<1 ⁶^(&

(26)

Number of Production Rules 20

25 30 35 40 45 50 55 60 65

32 64 128 256 512 1024 2048 4096 8192

Single-circuit Double-circuit Quad-circuit

Frequency MHz

図 ^&- ^H;#0 ^A ^8#=⁼ ^H;=00; ^<1 ⁶

Number of Production Rules 20

25 30 35 40 45 50 55 60

64 128 256 512 1024 2048 4096 8192

Single-circuit Double-circuit Quad-circuit

Frequency MHz

図 ^&7 ^H;#0 ^A ^8#=⁼ ^H;=00; ^<1 ⁶^(&

(27)

第

章実用的な

パージングの実装

&&節で述べたように前章で実装したハードウェアは入力文字列長や非終端記号数や生成規則数が現実的なサイズではなかったそこで本章では実用的なサイズでパージングを行うために大規模なを用いたり新たなハードウェア実装法の提案を行う

ソフトウェアアプローチ

実用的なサイズでパージングを行う際^%節で示した^,アルゴリズムを用いるとテーブルのサイズが巨大になりこのアルゴリズムは使えないことがわかるこのことより本章ではソフトウェアアプローチに^%%節で説明した^*+アルゴリズムを用いることにする

ハードウェアアプローチ

ハードウェア実装

&章で説明した実装では比較的規模の小さいを用いたので入力文字列が長く非終端記号の数が多い文法では回路規模が大きくなり実装困難であったそこで^&章で用いたよりも大規模な^"#$社の^$=シリーズのを用いてパージングを行う回路を実装した回路自体は^&%節で説明したハードウェアと同じであるこれにより入力文字列数⁷ 非終端記号数^'( 生成規則数^%'のパージングを行う回路を実現した今後このハードウェアをハードウェア実装と呼ぶさらに大規模な

パージングを行うハードウェア実装法を次節で説明する

ハードウェア実装

'%節で説明した実装法はテーブルを内部に持つしかし入力文字列が長い場合や非終端記号の数が多い文法の場合にテーブルのサイズが巨大になるので現在あるでは実装困難であるそこでテーブルをホストのメモリ上に持つことによって入力文字列が長い場合や非終端記号の数が多い文法の場合でも実装可能なパージング回路を作成したこの実装はと間のデータのやり取り

(28)

にバスを用い回路はバスの動作周波数である^{3 E}に同期して動作する今後本節で説明するテーブルをのメモリ上にもつ回路をハードウェア実装と呼ぶことにするこのハードウェア実装の基本的な構成要素を次に示す

B ビットワードデュアルポートメモリ

B

を計算する回路

B 個の^.2ゲート列

B 間のインターフェイス回路

ビットワードメモリにはテーブルの^%行分が記憶されるつまりテーブルの行目 ^4%⁵⁴⁵が記憶されるビットレジスタはパージングの

(行目で計算される ⁴⁵が格納される個の^.2ゲート列は ⁽行目の ^F^G を計算するために用いられる間のインターフェイス回路はとのデータを

を通じてやり取りする際のインターフェイス回路であるこのハードウェア実装の回路は基本的にはテーブル^%行分を計算する回路であるこの回路を用いてテーブルの行目を計算する手順を次に示す

% テーブル行目つまり^4%⁵⁴⁵⁴⁵を計算するために必要なテーブルの^%行目から ^% 行目までの内容を適切な順番にからバスを通じてに送信する

は送信されたデータ順に計算を行い行目のテーブルの内容をビットワードメモリに格納する

側からすべてのデータの送信が終ったらビットワードメモリの内容をに送信しのメモリ上にあるテーブルの行目の内容を更新する

この手順をテーブルの^%行目から行目まですることによってパージングを行うハードウェア実装の計算時間はハードウェア実装^%と同じでであるしかしながらハードウェア実装はハードウェア実装^%と比べてテーブルの各行を計算する度にバスを通じてと間の通信を行う必要があるので余分なオーバーヘッドが存在するよって実行時間はこのオーバーヘッドの分ハードウェア実装

の方が長くなるしかしの内部にテーブルを持たないことによって回路規模が小さくなり入力文字列が長く非終端記号数が多いパージング回路を実現することが可能となる

(29)

¾

¡! "#

$

図 ^'% ^< ^/## ^A ¹ ^/8# ^<1 ¹ ⁸ ⁸ ^#

1 18

性能評価

本節では^&節で用いたより大規模な^$=シリーズの^"()(

%)3ビットの組込みメモリとのロジックセルがある³ゲート相当のを用いてハードウェア実装^%・の性能を評価した性能評価のためにハードウェア実装^% とソフトウェアの実行時間の比較を行ったハードウェア実装では次に示す環境で実行し実行時間を計測した

#"# & E

メモリ ^{2!2 3} ^D

308A I#<8 +

コンパイラ ^308A ^8;^@@ ⁽

またソフトウェア実装では次に示す環境で実行し実行を計測した

#"# - E D'3 E

メモリ ^%デュアルチャンネル^!!2メモリ ^D

#;$ #%-=%&8/

コンパイラ ^# ^@@ ^/^A^#;$⁾

Japan Advanced Institute of Science and Technology