平成年度

学士学位論文

による自己タイミング型パイプライン演算機構の実現

古家 俊之
指導教員

岩田 誠 助教授年月日

高知工科大学 情報システム工学科

要 旨による自己タイミング型パイプライン演算機構の実現
古家 俊之

超高性能、極省電力を達成可能な自己タイミング型パイプライン機構によるデータ駆動型プロセッサが開発され、現在、商品化の途についたばかりである。

このような状況で、さらに応用分野を拡大するためには、各応用分野にある程度特化したＤＤＭＰを迅速に設計、開発することが要請されている。
従来はシミュレーションによって設計検証をおこなっていたが、ＶＬＳＩシステムが大規模化する傾向にある昨今、検証時間が膨大になる問題がある。
本研究では、実用的規模の回路を作り込める最近のＦＰＧＡを活用して新規開発ＤＤＭＰの設計内容を短期間で検証する手法の確立を目的としている。よって、本論文では、ＦＰＧＡ上での自己タイミング型パイプライン処理機構の最適設計指針を示し、その結果をもとに最適パイプラインステージ数を導き出し算術、論理演算機構に適用し目標性能を達成できる見通しを得た。

キーワード

ＦＰＧＡ、ＤＤＭＰ、自己タイミング型パイプライン処理機構

ＦＰＧＡ、ＤＤＭＰ、

目次
第章

序論

第章

データ駆動プロセッサの構造
データ駆動プロセッサの動作
各ブロックの説明
Ｍ（ＭＭ（）部）部

ＦＰ（）部

ＣＰＳ （）部

Ｄ（
第章

論理的な最適設計指針の検証
ゲート数とゲート段数
ゲート数とゲート段数の性質
共有化によるゲート数の減少
共有化の不可能な例
パイプラインステージ
パイプラインステージ化のスループットの上昇
ゲート段数の違いにより生じるスループットの変化
パイプラインステージ数とスループットの関係
パイプラインステージ数とハードウェア領域の関係
パイプラインステージ数の論理的最善数第章部の設計と構造
設計指針

目次（）部の構造）
部
論理演算
シフト（）

算術演算
比較
条件分岐
世代操作
その他
部
部
設計
設計指針１－共有化
設計指針２－パイプライン化
再利用への対応
第章

結論

謝辞
参考文献
付録

部の各命令のアルゴリズム
論理演算
シフト
算術演算
比較

目次

条件分岐
世代操作
その他

図目次
プログラム

パケットフォーマット
シンボル内の段数の決定
共有化の例
共有化の不可能な例
パイプラインステージ
ステージ数パイプラインステージ２段
パイプラインステージ数ｎ個のグラフのグラフ
スループット性能の上限
部の構造図
入力パケット 上 、出力パケット 下部の構造共有化をおこなった命令
最適パイプラインの構造図の構造図

表目次
表
表
独自アルゴリズム
出力

第章

序論

革命といわれる近年、インターネットの普及に伴いコンピューターのソフトウェア、ハードウェアをはじめ関連分野の研究、発展は目まぐるしいものとなり、従来使用していたものも数多く新しいものへと変化している。その数多くの変化の１つに非ノイマン型プロセッサの開発が挙げられる。
従来使用されていたノイマン型コンピュータは、１９４５年、フォアノイマンによって提案された。これはコンピュータの主記憶装置（現在のＲＡＭに相当している部分）の中にデータだけではなくて、プログラムも一緒に入れられる方法である。この方法を擁したプログラム内蔵型コンピュータでは内臓されたプログラムに従って、命令を１つずつ順番にＣＰＵ（中央演算処理装置）に、プログラムカウンタという一種の制御装置を用いて呼び出して実行する。しかし、この制御装置は各プロセッサに１つしかないために命令は１度に１つづつしか読み出せないという弱点を持つ。このような方法を使用しているプロセッサををノイマン型プロセッサといい、ノイマン型プロセッサを擁すコンピュータをノイマン型コンピュータという。またこれらは今日までコンピュータの基本となっており現在使われているコンピュータのほとんどがノイマン型である。
一方、非ノイマン型では、プログラムはデータが入力されることによって読み出され、データが複数入力されれば複数のプログラムが読み出されるため、並列にデータ処理が行える、このため高速処理が可能になり画像認識など高度な処理もリアルタイムで実行することができる。。また、データに制御機能をもたせて、演算部にデータが揃った時だけ作動するクロックレス構造により、低消費電力でプロセッサを動作させることができる。以上のことより、非ノイマン型並列処理方式であるデータ駆動プロセッサに焦点をあてる。

ここでデータ駆動プロセッサの簡単な歴史について触れる。非ノイマン型の並列処理プロセッサは、当初超高速コンピュータを実現するために開発された。シャープでは１９８３
年、民生機器の高機能化、小型化、および低価格化を目指し、開発に着手した。その後、世界で初めての非ノイマン型データ駆動方式により、映像、画像、音声などの膨大なマルチメディア情報を、超低消費電力で高速・並列処理する、次世代のデータ駆動メディアプロセッ
サ＜ＤＤＭＰ＞を開発した。
では、そのデータ駆動プロセッサを作成するとき、実際のカスタムＬＳＩ上で作成をおこなうには、時間的にも経済的にも無理であるうえリスクが伴うという問題がある。そこで登場するのがＦＰＧＡである。
（）とは、ハードウェアを設計データによって、動的に（使用時に）作り変えることができるゲート・アレイである。
タイプがあるが、ここではると、外部からにはいろいろな（スタティック・ラム）型を例にとって概念的な説明をすに書かれた情報によって、多数の論理ブロックを一時的に結線し動作させるものである。まず、普通のコンピュータを使って回路をハードウェア記述言語により記述し、コンパイルし、構成データを作る。動作のシミュレーションが成データはとなれば、構へダウンロードされる（構成データは普通のへ書き込むようにへ書き込まれる）。構成データにしたがって、あらかじめ内部に用意されている種々の論理ゲート、論理関数、マクロなレジスタや論理ブロックが結線される。実行段
階に入ると、中に構成されたものは、入力ピンからの信号を受けて論理動作を行ない出力ピンに結果を出力する。カスタムチップや成されるのではなく、のように永続的なハードウェアが構に書かれた構成データに応じて一時的に回路ができているだけである。したがって、電源を切れば、回路はリセットされる。
このように中に構成された回路は、ハードウェアかソフトウェアかは一概に言えない。もしコンピュータのメモリ中の情報をソフトウェアであると定義すれば、これはソフトウェアだし、回路が普通のハードウェアと同じように演算を実行するという意味ではハードウェアとも言える。最近は、内部の論理ブロックはますますマクロ化し、また実行時に部分的な再構成も可能なものが市場に現れている。
また、従来のハードウェアは高価なので、どうしても応用問題毎に（専用的に）作るわけにはいかない。しかしを使えば専用マシンを安価で作り込めるのである。

これまでに、自己タイミング型パイプライン機構によるデータ駆動型プロセッサが開発され、現在、商用化の途についたばかりである。このような状況で、さらに応用分野を拡大するためには、各応用分野にある程度特化した（－）を迅速に設計・開発することが重要になってくる。従来は、シミュレーションによって、設計内容を検証したがシステムが大規模化する傾向にある現状では、時間がかかりすぎる。したがって本研究では、前述したように実用的規模の回路を作り込める最近のを活用して新規開発ＤＤＭＰの設計内容を短期間で検証する手法の確立を目的としている。
本論文ではＦＰＧＡ上での自己タイミング型パイプライン処理機構の最適設計指針を示し、算術論理演算機構に適用した。
以下２章ではデータ駆動プロセッサの構造について記述し、３章ではハードウェア、スループットを中心に論理的に最善策を検証する。また４章ではＦＰ（）についての構造について述べ、３章での論理的最善策に従って設計をおこなう。

第章

データ駆動プロセッサの構造

データ駆動プロセッサの動作
データ駆動プロセッサでは、図２．１で示すようなデータ駆動プログラムの演算を行なうことが可能である。これらはあるノードからその後続ノードへの有向枝（アーク）のリストから構成されており、パケットデータのヘッダ部分に連結される。

図

プログラム

図２．２は基本的なデータ駆動プロセッサの構造を示している。まず外部よりデータパケット 図２．３参照 が入力され、その後適切な合流モジュールを通過して、パケットは待ち合わせ記憶部：：に至る。ここでは、世代照合を行ない対になるパケットが到着するまで保持される。もし、ここで対になるパケットが到着すれば２つのパケットは行き先ノード

世データ駆動プロセッサの動作

オペレーションコード

代番号を生成し関数的処理ユニット（とデータ同士を結合し１つのパケット：）に送られる。ここではで指定された演算の結果とそれに伴うデータを適切に書き換える。その後ＣＰＳに送られる。

図

図

パケットフォーマット

ＣＰＳでは図２．１のようなプログラムからなどが、、定数フラグメモリ内に保持されており、送られてきたパケットの次の行き先を書き換える。

このときのパケットの形式は入力パケットと同様の形式である。最後に分流モジュール（ ：）に送られ行き先に適した場所へと送られる。

各ブロックの説明

各ブロックの説明
では、次に各ブロックについて構造を簡単に説明する。

Ｍ（）部

合流要素Ｍでは２つの独立な自己同期パイプラインから単一な自己同期パイプラインを通るパケットの流れへ、２つのパケット流を結合する。合流要素Ｍに到達するパケットの流れは、最初に来たものから処理される。もしほぼ同時に２つのパケットが到着したら、２つの衝突発進信号が、調停操作回路での飽和反応型ＳＲフリップフロップの１連の動作によって調停される。このブロックでは、２つのゲート信号のうち１つを、ラッチパルスとＳｅｎｄ－Ｏｕｔ信号を作動させるようにするので、最初のパケットは、調停信号によって２つのデータパスを多重通信式にしてインプットパスからアウトプットパスに移される。その時、ラッチパルスは調停操作回路にフィードバックされて、他のパケットはアウトプットパスに伝えられる。

ＭＭ（）部

ここでは、前述の合流要素Ｍより送られてきたパケットの断基準として２つのパケットを１つにする。

世代番号 を判

世代番号 が同一のパケット同士を１つにし、あらかじめプログラムを読み込み記憶しているメモリにアドレス、データ、読み込み信号を送り、（行き先ノード）（オペレーションコード）を読み取り、それらを付け加えて次のブロックへと送られる。

ＦＰ（）部

設計や構造については、４章で詳細を示すが簡単に説明をおこなう。ＦＰ部ではプログラム上でいう演算処理を行なう。本研究では演算処理の基本命令は、、、、、、、、、、、、、、、、

各ブロックの説明、、、、、、、、、の全２５種を実現した。（詳細は４章、付録Ａを参照）。パケットの流れとしては、ＦＰ部への入力パケット（オペレーションコード）で指定された演算の結果を出力しＣＰＳへと送る。

より

ＣＰＳ （Ｆ Ｐ 部 よ り 流 れ て き た パ ケット よ り（）部
行 き 先 ノ ー ド を 読 み 取 り、Ｍ Ｍ）と同様にメモリにアドレス、読み取り信号を送り古い新しいはに置きかえられる。したがって、出力パケットはデータ駆動プロセッサへの入力パケットと同一形式で生成される。

Ｄ （分流要素は、２つの自己同期パイプラインにパイプラインを分ける。２つのアウトプットパイプライン間の切り替えは、インプットパケットに含まれている１つ以上の特定のフラグによりコントロールされる。もしすべてのフラグがアクティブなら、分流要素Ｄは２つのパイプラインにパケットの流れを複写する。

第章

論理的な最適設計指針の検証

ゲート数とゲート段数
ここでは、主にＦＰ部内部の基本命令の設計に関わるゲート数とゲート段数について検証する。また、共有化の説明をおこない、基本命令の１つであるＧＥのアルゴリズムの決定について最善策を模索する。

ゲート数とゲート段数の性質
ゲート数が増加すればするほど、ハード量は増加する。このときゲート段数が増加しなければ（既存のゲートとの並列処理ならば）スループット（時間効率）に変化は無い。
ゲート段数とは並列になっているゲートの段数であり、ゲート段数が増加するとスループットは低下する。また、１つのシンボル（モジュール）内で２つの並列な処理が行なわれる場合（図３．１参照。）、Ａのゲート段数とＢのゲート段数を比べたときにゲート段数が多い方に依存されるので、この場合はＢに依存されこのシンボルのゲート段数は４と最後のＡＮＤゲートを加えた値となるので５となる。

図

シンボル内の段数の決定

ゲート数とゲート段数

共有化によるゲート数の減少
並列処理の共有化を行ない無駄なハード領域（ゲート数）を減少させる。
げて説明する。図３．２で示すように共有化前のなうが、での結果を命令ではを例に挙後残りの演算をおこの入力とすれば今まで使用していたのハード領域の無駄が省ける。これによって、ゲート数の減少をはかる。ただし、このことによって図中のはの出力結果がないと出力することができなくなる。よって、の出力結果を出すのに必要なゲート段数は、アルゴリズムに違いが無ければ共有化する前と後とでの変化は見られないということである。

図

共有化の例

共有化の不可能な例
共有化ができないときの例を挙げる。図３．３に示すようにある演算を行いその演算結果同士をの（加算）する命令があるとする。このとき、ある命令内で必要な値は演算後、 の値（図中の、）であり、のの値は不必要である。であるから、このような状況のときには共有化は行なえないのである。以上のことより一般的に共有化が行なえるのは、入力データの演算結果が使用できる部分であるといえる。

パイプラインステージ

図

共有化の不可能な例

パイプラインステージ
一般的にパイプラインステージ数を増加させれば、スループットとハードウェア領域が増加する。（詳細は３．３．１パイプラインステージ化のスループット上昇を参照）では、スループットが最も良く更にハードウェア領域が少なくてもすむ最善のパイプラインステージ数は幾つなのか、具体的数字として論理的に検証する。
パイプラインステージの構造について簡単に説明する。パイプラインステージとは、ＦＰ内部でいえばＣエレメントと同士の区間のことである。 図３．４参照

図

パイプラインステージ

パイプラインステージ

パイプラインのステージ間のデータ転送は自己同期転送制御装置（でコントロールされる（図３．４中）。一般的に信号の両方がアクティブな時にエレメントは信号とにクロック信号を生成する。すなわち、信号は先行ステージの処理されているパケットが意ができていることを示し、エレメント）の連鎖のインプットに入れられる用信号は次ステージは空であることを示している。

パイプラインステージ化のスループットの上昇
パイプラインステージの論理的最善数を検証する前に、スループットの上昇の説明を記す。パイプラインステージ化することでスループットは上昇すると記してきたが、それは何故なのかを説明し、証明をおこなう。尚、分割の際すべてのパイプラインステージ内の通過ゲート段数は同じであり演算時間も等しいとする。
単純に考えるとが１つ増えているわけだからゲート段数が増加してスループットも低下すると思う。しかしパイプラインステージが２つの時、前項で説明したエレメントのコントロールによって、２つ目のステージにパケットデータが到着し、出発したとき、１つ目のステージへ新しいパケットデータが送られる。このことによってゲート段数は増加するが、スループットは上昇する。

図

ステージ数

パイプラインステージ

では、次に本当にスループットは上昇しているのか論理的に検証してみる。図３．５で表す
ように、パイプラインステージが１個のときは１つのデータの演算にかかる時間はＴ 秒であり、 つのでのかかる時間は秒 であり１秒間に処理できる回数は１ステージが２個のときはＴ＋秒 である。結果、かかる時間はＴ＋（回 秒）となる。次に、パイプラインで（Ｔ ２）（秒）かかるので、結果かかる時間はＴ＋（秒）であり１秒間に処理できる回数は２Ｔ＋に処理できる回数を比べると、１個のときが１（回 秒）となる。上記２つの１秒間であり２個のときが２である。 個のときはとなるので、となり、結果パイプラインステージ２個のほうが時間効率は良くなる。
一般式や更に詳しい内容は後述とする。

ゲート段数の違いにより生じるスループットの変化
前項では、パイプラインステージ内部の演算ゲート段数は同じとして検証をおこなった。
では、パイプラインステージ内部のゲート段数が異なるとスループットはどのように変化するのかを検証する。

図

パイプラインステージ２段

パイプラインステージ

図３．６で表すようなステージ数２つのときを例に考える。１つ目のパイプラインステー
ジ内の演算時間を、２つ目のパイプラインステージ内の演算時間を）内でかかる時間をとする。またこのとき Ｔ１としＤＬ（Ｔ２ とする。このときのスループットを計算すると、ｎ番目のデータが１つ目のパイプラインステージの処理が終わったとき、ｎ－１番目のデータは２つ目のパイプラインステージの処理中であるため、ｎ番目のデータは（Ｔ２－Ｔ１）だけ待ち合わせが発生する。次にｎ番目のデータが２つ目のパイプラインステージの処理の途中のときｎ＋１番目のデータは同様に（Ｔ２－Ｔ１）の待ち合わせが発生する。よってｎ番目のデータを処理するのにかかる時間は、となり、スループットは、となる。では、パイプラインステージ内の演算時間が同じのときと、比べてみる。前項より、パイプラインステージ内の演算時間が同じときのスループットは、であり、であるからとなり、パイプラインステージ内の演算時間が同じときよりもスループットは低下している。では、パイプラインステージ数が１つのとき（パイプライン化をおこなって無いとき）と比べるとどうであろうか。パイプラインステージ数が１つのときのスループットは、であるから、分子は同じであるので分母どうしを比較する。

であるから、

パイプラインステージとなり、パイプライン化しないよりはスループットは上昇している。
以上のことよりパイプラインステージ数２つのときに限っては、パイプライン化しないよ
りはスループットは上昇するが、パイプラインステージ内の演算時間を等しくしたときよりは、スループットは低下していることがわかった。
では、パイプラインステージが多くなってきたときは、どのような変化がおこるのかを検証する。

図

パイプラインステージ数ｎ個

パイプラインステージ数がｎ個のとき、各パイプラインステージ内演算時間を、Ｔ１、Ｔ２、、、Ｔｎとし、パイプラインステージの順序は変えることが可能なのでＴ１ ＜ Ｔ２ ＜、、、＜ Ｔｎとする。また各での待ち合わせ時間をＭｎとする。（図３．７参照）。では、このときの１回の処理時間を検証する。まず待ち合わせ１（図中、Ｍ１）を計算すると、同様にＭ２を計算する。

更に、Ｍｎを計算する。

パイプラインステージ

Ｍの総和は、となるので、１回の処理時間は、である。このときであり、Ｍは（ｎ－１）個存在するので、となる。これは、１回の処理時間はパイプライン内で最も時間がかかるステージの演算時間に依存されることをあらわしている。
では、次に同様にパイプラインステージ内の演算時間が等しいものと比較する。パイプラ
インステージ内の演算時間が等しいものの１回処理するのにかかる時間は、で表せるので、となり１回処理するのにかかる時間は演算時間が等しい方が短くなり、スループットも高いといえる。
次にパイプライン化していないものは、なので、比較すると、となり、より数式（３．３）は正であるといえる。これはパイプライン化していない方が、１回の処理時間は長くスループットも低いことをあらわす。

パイプラインステージ以上のことより、パイプラインステージ内の各ステージの演算時間が異なると、演算時間が等しいときよりスループットは低下するものの、パイプライン化しないときよりは、スループットが上昇することがわかった。

パイプラインステージ数とスループットの関係
ここではパイプラインステージ数とスループットの関係を検証する。まず、演算にかかる時間をＴ（秒）、でかかる時間をａ（秒）、パイプラインステージ数をｎ（個）（ただしｎは正の整数）とすると、内はフリップフロップなのでが成り立つ。また１回処理するのにかかる時間は以下のように成る。
秒
更に１秒間に処理できる回数は以下のように成る。

回 秒
ここで、パイプラインステージの数を限りなく増加させると以下のように成る。となり、に収束する。これはパイプラインステージ数を限りなく増加させても１秒間で処理できる回数は１（回 秒）以上にはならないことを示す。では、以上のことより検証をおこなう。まず数式３．５の１秒間に処理できる回数をｙとおく。

パイプラインステージとなるのでとなる。更に ｎのときとなる。また一般的な１秒間に処理できる回数は以下のようにも書ける。

よってこのグラフは直角双曲線したものであり、漸近線は２直線

図をｘ軸方向に、ｙ軸方向にである。図３．８参照のグラフ

だけ平行移動パイプラインステージ

パイプラインステージ数とハードウェア領域の関係
では、次にパイプラインステージ数とハードウェア領域の関係を検証する。
まず演算に必要なハードウェア量（ゲート数）をＨ 個 、パイプラインステージ数をｎ（個）のハードウェア量（ゲート数）をｂとすると、が成り立つ。また、１回の処理の総ハードウェア量は以下のようになる。
個
これは、総ハードウェア量はパイプラインステージ数が増加すればするほど、比例して増加することを示す。ここで、ハードウェア量は少ないほうが好ましいので逆数をとる。ハードウェア量を、ｙ２とおくととなる。このときを軸方向にのとき分母は０となるので、この式のグラフは、直角双曲線だけ平行移動したものであり、漸近線は２直線である。図３．９参照。

図のグラフ

、

パイプラインステージ

パイプラインステージ数の論理的最善数
前述したとおり、スループット性能はパイプラインステージ数の増加に伴い上昇する。しかし、そこにはエレメントの性能という上限が存在する。

自己タイミング型演算機構はエレメントでコントロールされていることは前述してあるが、そのコントロールしているもの自体のスループット性能を越える性能が、演算機構にあったとしても、エレメントの性能以上の性能をだすことはできない。

図

要するに、スループット性能の上限

エレメントのスループット性能（図中点線）と数式３．７の曲線（図中実線）のスループット性能が低い方が演算機構全体のスループットの性能となる（図３．１０参照）。よって２つの線の交点が最適設計ポイントであり、それ以下の最大のｎがパイプラインステージ数の論理的最善数といえる。

第章部の設計と構造設計指針
ここでは、前章での最適設計指針にしたがって、データ駆動プロセッサの主要部分の１つでありゲート段数、ゲート数が最も多く存在し、演算部のアルゴリズムに改善の余地があるであろうＦＰ部の設計をおこなう。このときの主な設計指針はハードウェア領域の減少のための共有化を行なうことと、スループット上昇のためのパイプライン化において最善パイプ
ラインステージ数を導出し、適用をおこなうことである。

（まず始めに、）部の構造部の構造を記す。（図４．１参照 ）。尚、図４．１は構造を便宜的に記したものであるため、実際の構造とはパイプラインステージ数が異なる。
入 力 デ ー タ は 、デ ー タ を 記 憶 す る モ ジュー ル で あ る
オペレーションコード はは部での 結果の値をを 通 る 。そ し て 、部へ、その他のデータ部へとそれぞれ流れる。その後、部へ送りを通り部、部の最終的な出力となる。
次に部における入出力パケットについて説明する（図４．２参照）。入力パケットは（）部の構造図、と部の構造図

×２、は左入力、右入力のフラグ。×２は、数字は２の補数表現とする。）、

データＡ、Ｂ。最上位
×２ の全６８、図を符号、となる。出力パケットは、の４９となる。

入力パケット 上 、出力パケット 下）
同士を結ぶ自己同期転送制御装置。
送られ現のは、前のに入れられる用意が出来ていること、次のであることの２つを信号によってやりとりし、現を出す。これによって、時間短縮を計る。

よりパケットがは空にパケットを送れという信号

（）部の構造部
部では、することは、を演算する。ここで注意
での指定に関わらず全ての演算を行なうということである。よってこ

こでの論理展開は重要であり、ゲート数に直接関係をもたらす部分である。
命令は、論理演算、シフト、算術演算、比較、条件比較、世代操作、その他の７項目から成り、全２６種類作成した。入力パケット、出力パケットを 見てもらえば解るが、命令は全て入力は２入力で、出力は１出力である。１入力の命 令については、各命令と命令の対応の全てを表にした（表４ １、４ ２参照）。また、上で詳細を記す。
位３と下位３で分けて判り易くしてある。

命令

命令

表

表表

表

（）部の構造

各命令について記す。尚、アルゴリズムについては付録を参照。

論理演算
命令の６種類から成る。

入出力数 ２入力。１出力。
変化データ
最大通過ゲート段数

１段シフト（）命令のデータをのデータ分シフトする。 の１種類から成る。

入出力数 ２入力。１出力。
変化データ
最大通過ゲート段数

２段

算術演算
加算

命令

減算の大きい方を出力
入出力数の絶対値の数の小さい方を出力の絶対値の数

掛け算 の７種類から成る。

２入力。１出力。

変化データ
最大通過ゲート段数

１４段

比較
命令のとき、出力１。のとき出力０。

＞のとき出力０。のとき出力１。のとき出力１。のとき出力０＜の（）部の構造で一致してなければ出力１、一致していれば出力０ の４種類から成る 。
入出力数 ２入力。１出力。
変化データ
最大通過ゲート段数、１７段のとき

より条件分岐
命令出力。のときを出力＞出力０のを出力。
よりのときのときを出力。

より出力１。

で一致してなければ＜よりをのときよりのときよりより出力１、一致していればより出力 ０ の４種類から成る。
入出力数 ２入力。１出力。
変化データ

行き先ノード最大通過ゲート段数、。

１７段

世代操作
世代番号 の下位１２

命令

世代番号 の下位１２をにのデータに書く。 の２種類から成 る。
入出力数 ２入力。 １出力。
変化データ
最大通過ゲート段数

世代番号 。
０段のデータを格納する。

（）部の構造その他
命令

出力は右入力に依らず、左入力入力データをそのまま出力。 の２種類から成る。
入出力数
入出力数

２入力。１出力。
１入力。１出力。

変化データ。

変化データ

変化無し。

最大通過ゲート段数

０段

部
基本的命令２６種のオペレーションコードを判別し指定された命令を割り出す部分。入力
はオペレーションコードを出力“ ０ ”とする。

。出力は指定されたものを出力“ １ ”とし、その他

オペレーションコード は、上位、下位ずつ判別し、そのまま出力する形をとった。これは、再利用への対応とともにＳＥＬＥＣＴ部での使い易さを考えたものである。（図４．３参照）

図部の構造

設計

部部よりの出力と部よりの演算結果を照合し、指定されたの演算結果を出力する。アルゴリズムとしては、２つの出力のＯＲ（論理和）をとる。

設計
前述の設計指針にしたがってＦＰ部の設計をおこなう。前述の設計指針をまとめると以下のようになる。
設計指針１ ハードウェア領域の減少のため共有化、アルゴリズムの工夫をおこなう。
設計指針２ スループット上昇のため、最適パイプライン化をおこなう。

設計指針１－共有化
最適設計指針に従って実際に共有化をおこなった基本命令を記す（図４．４参照）。
（）出力を使用して、出力を使用して使用して、（を求める。
を求める。

、）を求める。

出力を使用して出力を使用して出力を使用して図出力を求め、を求める。

出力を求める。

共有化をおこなった命令を求め、出力を出力を使用して、設計

基本命令ＧＥのアルゴリズムの決定
では、ここで共有化を行なわなかったものについて触れる。前述のとおり、共有化をおこなうことによってハードウェア領域は減少する。しかしアルゴリズムによっては、ゲート段数が増加しスループットが低下することがある。そのとき、どちらを優先すべきかが問題となる。ここでは、本研究で設計、構築をおこなうＦＰ内部の基本命令ＧＥ（力１。

＜のとき出のとき出力０）を例にどちらを優先すれば良いのかを検証する。

ＳＵＢ出力を使用する共有化とＧＥ独自のアルゴリズム アルゴリズムの詳細は付録Ａを参照。 を使用する場合について検討する。まず表３．１、３．２でのＴＯＴＡＬ部分のゲート段数の説明をしておく。ＴＯＴＡＬ部分のゲート段数は単純な加算ではなく、桁上げ（もしくは、桁下げ）信号を出すのに必要なゲート段数を加算していき最終的なでの出力のゲート段数を加えて総ゲート段数としている。では検討をおこなう。ＳＵＢ出力を使用した場合共有化により、ＳＵＢの結果を出力するのにハード量（ゲート数）は使用しないが、ゲート段数が１９段かかるためスループットは独自アルゴリズムを使用する場合と比べると低下する（表参照。）。その上、ＳＵＢ出力のままではＧＥの結果にはならないので更に１，２段は要する。では、独自アルゴリズムを使うとどうであろうか。同様に表をみれば判る通りゲート数は６０個増加するもののゲート段数は１４段で済ますことができる。後々のパイプライン化を考えると他の基本命令と比較してゲート段数が多い基本命令のゲート段数は少しでも減らしておきたい（詳細は次の項目で触れる。）ので、ここでは独自アルゴリズムによって基本命令ＧＥを構築するものとする。
尚、本研究においては、このような結論となったが他の基本命令のゲート段数や、スループットとハードウェア量の優先順位によってはこの限りではない。

設計

ゲート数

段数

０～３２０６４～７２０８～１１

桁下げ信号は

表

ゲート数

段数

０～３８６９６４～７８６９２０５８～１１８８

１１６０１４

無１９段

桁上げ信号は独自アルゴリズム段

表出力

設計指針２－パイプライン化
前述の最適設計指針に従って、パイプライン化をおこなう。
まずエレメントのスループット性能は回となる。また、前述の数式３．５におけるＴ＝３１、 ＝２となり、回となる。以上のことより最適設計ポイントはとなり、ｎの最大値は４となる。この結果に従ってパイプライン化を行なう。その際各パイプラインステージ内の演算回路ゲート段数を、できる限り等しくする必要がある。前述したが、パイプラインステージ内のゲート段数の最も多い部分にパイプラインステージ全体の処理時間は依存される。よって、ゲート段数が最も多いものを基本に考える。すると最も設計（

ゲート段数が多いものは（）は（（）の７段、８段である。しかも、）の出力結果が必要であるため、後述するが４（収まらない。まため、次）、）、ずつでは４段には桁上げ先見加算機を基本に設計しているたの出力結果を得るには桁上げ信号が必要である。更に４段のパイプライン化において、最後の４つめの段にはより、、部が必要であり全演算結果を要する。以上のことにを６演算にする必要がある。その結果、各パイプラインステージ内の段数は、７段、８段、８段、８段となる。（図４ ５参照）

図

最適パイプライン

再利用への対応
ここでは、再利用への対応として拡張されやすいよう構築した部分の説明をおこなう。
演算が１２であるため１２用のものを作成していたが、再利用、拡張を考慮し４用のものを作成しそれを３つ並べて１２用とした。しかし、命令については全場合のシフトを想定し場合分けのアルゴリズムを使っているためこの限りではない。また
前述のとおり、も６演算とした。

設計

共有化との関係でを決定してあるので、再利用の際、命令を増やすときに共有化する命令の部分に追加しやすくしてある。

第章

結論

本研究では、２章ではデータ駆動プロセッサの構造について記述した。また３章ではハードウェア、スループットを中心に論理的に最善策を検証した。また４章ではＦＰについての構造について述べ、３章での論理的最善策に従って設計をおこい目標性能を達成できる見通しを得た。
今後の課題として挙げられるのは、論理的最善策の決定におけるパラメータを増加させ一般化にすることである。本研究の結果では、例外の無い非同期回路の最善パイプラインス
テージ数しか検索は出来ない。また並列処理のパイプライン化は並べ方によっては、全体の演算時間が大きく変動する。最善のパイプラインステージ数は一般化の式より導きだすことができるが、どの部分を並列処理にして各パイプラインステージ内のゲート段数は幾つが最善なのかは導くことはできない。よって、更なる研究で、並列処理のパイプライン化における各パイプラインステージ内の最善ゲート段数の検証を必要とする。
将来展望として、今後の課題で挙げた事柄が解決できれば、最善のパイプラインステージ数が導きだすことができ、パイプラインステージ内の最善ゲート段数をも導くことができる。そうなれば、これから更に巨大になるであろうＬＳＩの設計、構築においてパイプライン化が円滑、かつ正確におこなうことができるようになる。これによって、大幅な時間短縮と有益なハードウェア領域を取得することができる。

謝辞
本研究において、懇切なる御指導、御鞭撻を賜わった高知工科大学の岩田 誠助教授に心より感謝の意を表します。
本研究を進めるにあたり、適切な御助言、御指導を賜った大森 洋一助手に深く感謝の意を表します。
日頃から御支援、適切な御指導を頂いた細美 俊彦氏に感謝の意を表します。
日頃からご支援頂いた情報システム工学科 岩田研究室の方々、別役 宣奉氏、前田 庸亮氏、森川 大智氏、橋本 正和氏、仮屋 文彦氏に感謝の意を表します。

参考文献

工学博士 田丸啓吉 論理回路の基礎 ，工学図書株式会社
井川 満、井関兼四郎、伊東清三、大島利雄、加藤順二、塩田徹治、渡辺信三
Ⅲ

数研出版株式会社

西本敏彦 微分積分学講義

培風館

数学

付録

部の各命令のアルゴリズム

論理演算
各ビットの論理演算をとる。

シフト
は、のデータ分するが、データの最上位が０（正数）なら左シフト、１（負数）なら右シフトを行なう。データのビット数より１１ので全ての場合の回路を作成し、け回路との論理積（のシフトまでなよりシフト数を判別し、信号として出力し場合分）をとり出力としてある。

算術演算
参考文献

より４桁上げ先見加算回路をベースにした。ここでは、４ブロックとし３ブロック使用しに対応させてある。更にブロックごとに上位ブロックへの桁上げ信号を発生させているため入力データの数が増加しても拡張しやすく一般的であり、どのレベルのブロックにも対応できる。
加も１３目 を複製し１３を１目を符号対策としては、最上位に追として扱った 表Ａ １ 参照。また、の信号より入力データを変化させ、と同じ回路を使用した。これによって、ハードウェア量の減少をおこなった。
後に記すのとき出力１。

＜のとき出力０。 を使用する。

比較

符号
正正負
負表

を例に説明すると、
定とのとよりの出力とをとる。２つの出力ののをとり、をとり、最終出力とする。

よりの出力の否はを逆転させるの出力を使用し作成。

力とよりの出力はにより出出力とに変化する。よってその出力を絶対値表現に変換させる。尚、出力データの最上位は常に０とする。

を例に説明すると、を通過した結果を正数の時はそのままで、負数の時は演算回路に通し、２つのデータの各をとり最終結果とする。図最上位は除く の参照。正数のときは絶対値はそのままで良いが、負数のときは２の補数表現に変化させる必要がある。

比較
各にを通し、その結果を各にを通し、結果を否定し出力。

方法は２つ考えられる。１つはで判定する。

を使用する方法である。もう１つは最上位より段階的に判定していく方法である。最大通過ゲート数を考え後者で作成する。
を例に説明する。第１に最上位に注意しながら、最上位でのから調べる。最上位、、は符号として扱っていることの３つの場合を調べる。（

条件分岐

図の出力はの構造図の時１でその他は出力０。の他は出力１。の結果のの出力はをとる。の出力はの時出力１でその他は０。）その後のときは、１つ下のす（これをイコール信号と仮に呼ぶ）。次に１１、とのて更に下位
調べ上位
力ののとき出力０で、そこの場合は１１の結果と上位

この場合は１２をとり、の結果と上位からのイコール信号とのをとる。最終的に目だけの目 からのイコール信号まで続ける。最下位

からのイコール信号との目 に信号を出を調べる。ここでは１１を調べでも同様に繰り返し最下位、をとる。そしでは、だけををとる。そして最終的にそれぞれの（論理積）をとるので各での出力（の出の時のみ出力０がでるように作成）が１のときは他での分別が可能であるが、０ならばその出力に依存される。図３．４参照。

条件分岐

し、を使用する。

よりの出力が１のときよりの出力が０のときのを使用する。

よりの出力が１のときをのをとをととする。の世代操作

図

し、し、とし、の構造図よりの出力が０のときのをとする。

を使用する。

よりの出力が１のときよりの出力が０のときのをよりの出力が１のときよりの出力が０のときのを世代操作の下位１２をのデータに書く。の下位１２にのデータを格納する。

左入力をそのまま出力。
データをそのまま出力。

をととする。

を使用する。

その他ののとする。

を