平成  年度
学士学位論文超高速ルーティング検索機構の  による実装

             

長野 光

指導教員

岩田 誠

 年  月  日
高知工科大学 情報システム工学科

要 旨
超高速ルーティング検索機構の  による実装
長野 光

今後の超大規模集積化システムには、高速化だけではなく、省電力化、設計容易化が求められている。そのため、集積化システムの高速化の有力な手段であるパイプライン処理機構
を、従来のクロック同期回路以外の方式によって実現する方法が求められている。

 システムは、省電力性、高速性などの優れたアーキテクチャの特性により、次世代特定用途向き  として期待されている。加えて、将そこで、注目する自己タイミング型

来的には要求の多様化、集積化技術の進展等の要因により飛躍的にシステムが大規模複雑化する事が予想される。このため、自己タイミング型

 システムを短期間で効果的に設計、検証する環境の整備が急務となっている。
本研究では、自己タイミング型システムを前提として提案された超高速ルーティング検索 用に設計し、性能評価を行うことで、自己タイミング型アーキテクチャを用いたシステム開発において、システムの事前評価に  の適用を応用することの優位性

機構を

を示した。
キーワード

自己タイミング型

 システム、、超高速ルーティング検索機構         
                                  !        " #       !                       $    !             
     "      %      %       & !              #    !    "  #   %                           #     &   
          #     "    #                               $  "      #                         !     #                                  !  !"      ##         

目次
第章

序論



第章

データ駆動型プロセッサの基本アーキテクチャ""""""""""""""""""""""""""
命令実装部 " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " ")*データ駆動原理に基づく超高速ルーティング処理



'"(
'"'
第章

+"(
+"'
+"+
第章

)"(
)"'

)"+
第章

/"(
/"'
第章

*"(
第

章

プロセッサエレメント構成""""""""""""""""""""" ,-  検索命令 " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " .
プレフィックス検査命令 " " " " " " " " " " " " " " " " " " " " " " " " " " "((超高速ルーティング機構の処理概要

ルーティング用新命令回路設計

""""""""""""""""""""""""
回路記述言語による設計 " " " " " " " " " " " " " " " " " " " " " " " " " " ")"'"(    の回路構造 " " " " " " " " " " " " " " " " " " " " " " " " ")"'"' -  &% の回路構造 " " " " " " " " " " " " " " " " " " " " " " "性能分析 " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " "各命令における論理の体系化

ルーティング用新命令回路の考察

()
()
(/
(0
(.


" " " " " " " " " " " " " " " " " " " " " ''新命令における回路コストの考察 " " " " " " " " " " " " " " " " " " " " " "'+新命令における命令実行時間の考察

性能評価
新命令回路の性能評価

" " " " " " " " " " " " " " " " " " " " " " " " " " " " '/

結論





目次

謝辞



参考文献





図目次
'"( データ駆動プロセッサの基本構成 " " " " " " " " " " " " " " " " " " " " " " "'"' 112 におけるパケットフォーマット " " " " " " " " " " " " " " " " " " " "/*+"(     概要図 " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " ((+"' -  &% 概要図 " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " (+)"(     " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " ")"' -  &% " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " ")"+     のクリティカルパス " " " " " " " " " " " " " " " " " " " " " " " ")") -  &% のクリティカルパス " " " " " " " " " " " " " " " " " " " " " " "

(*
(,
'3
'3

表目次
)"( 要求時間と到達時間 " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " '(/"( 命令実行時間（メモリアクセス時間を含まない） " " " " " " " " " " " " " "/"' 命令実行時間（メモリアクセス時間を *45 とする） " " " " " " " " " " " "/"+ 回路規模見積もり " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " "/") 67 '386 デバイス概要 9(", : " " " " " " " " " " " " " " " " " " " " "

''
'+
')
')

*"( パケット処理性能見積もり " " " " " " " " " " " " " " " " " " " " " " " " " " '/*"' データ転送処理能力 " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " '*



第章

序論
今現在プロセッサの速度は日々速くなっており、楽観的に考えるならばプロセッサの性能はこのまま上限なく向上するように思われる。しかし、現在の集積化技術では性能を倍にするために、同じ大きさの基盤に倍数の配線が配置されるように は設計されている。そのために配線は細くなり、その配線の間隔は確実に狭くなっていくと容易に想像される。当然ながら配線間隔には限界があり、間隔が限界まで短くなりすぎることで配線同士が干渉しあい、正常に動作しなくなることはすでに明らかとされている。そして、現在使われている
プロセッサ構造の配置配線ではその限界に近づきつつある。この問題を回避するために一定の配線間隔を維持すると、その反動としてチップサイズは肥大化する一方である。また、配置配線が長くなることでその距離分の電力が必要となり、消費電力が飛躍的に増大する。加
えて設計自体も困難になる。そもそもチップ自体が材質上の問題で耐えられなくなるといわれている。
これらの問題が発生している原因はノイマン型の処理方式を用いているからである。そのため、従来のシステムを維持したまま問題点を解決するのは困難を極める。これらの問題を解決するために、集積化システムの高速化に有用な手段であるパイプライン処理機構を、従来のクロック同期回路ではなく、新しい非同期回路によって実現する方法が挙げられる。そのため、非同期回路である自己タイミング型システムを用いることが提案されている。この方式では処理に対して実際に必要なモジュールのみが駆動するため、データを処理していな
い時は消費電力をゼロにできる。それにより、ノイマン型処理方式と比べて省電力化を容易に実現できる。さらに、隣接するパイプライン・ステージ間でしか配線をしないために、配線長の増大に伴う消費電力増加の問題を解決できて、同時にモジュール化が簡単にできるた

めに設計の容易化も可能となる。
この自己タイミング型システムを用いたプロセッサであるデータ駆動型プロセッサの特徴を以下に示す。

¯

自己タイミング型パイプライン機構の採用¯

マルチプロセッサ構成による設計の容易化¯

ソフトウェア処理

¯

省電力性

¯

高速性

 システムは、上記のような優れたアーキテクチャの特性により、次世代特定用途向き  として期待されている。加えて、将来的な要求の多様
このように自己タイミング型

化、集積化技術の進展等の要因により飛躍的にシステムが大規模複雑化すると予想される。

 システムを短期間で効果的に設計、検証する環境の整備が急務となっている。すでに同期型のシステム開発では、百万ゲート規模の高速  を

このため、自己タイミング型

用いて、設計、検証を行う手法が主流である。
本研究では、自己タイミング型アーキテクチャを用いたシステム開発において、システム を使って行うことの優位性を示すため、自己タイミング型システムを前提として提案された、 ルータの   部である超高速ルーティングアドレス検索機
構を  用に設計し、検証する。

の事前評価を本研究において実装した超高速ルーティング検索機構は、データ駆動型処理と親和性の強

'

112）

いアルゴリズムを採用し、 種類の新命令回路をデータ駆動型マルチプロセッサ（に組み込むことで実現される。詳しい内容については' 章でデータ駆動型プロセッサ11）の構成を述べるとともに、11 に適用することの優位性を示し、説明を行う。
また、今回実装したルーティング検索用新命令回路は -  検索命令と  &% 検査命令である。この ' 種類の新命令について、+ 章ではそのアルゴリズムと処理概要について詳しく述べ、) 章ではルーティング用新命令回路設計の内容について、検索実行時間及び回路（

規模見積もりを算出し、性能分析を行う。

/

加えて、 章ではルーティング用新命令回路の考察として、新命令における回路遅延時間

*



の考察と回路コストの考察を行い、 章では新命令回路全体の性能分析をした上で、上に実装した新命令回路が

 アドレスの   として要求を満たしているか検証し、評

価を下す。
最後に

0 章において、超高速ルーティング検索機構を  上で実装する事によって検証された結果を提示し、この提案が専用ハードウェアでは作成する意義のあるものであるという確証をより堅固なものとするとともに、自己タイミング型アーキテクチャを用いたシステム開発において、システムの事前評価を を用いて行う優位性を示し結論とする。



第章

データ駆動型プロセッサの基本アー
キテクチャ プロセッサエレメント構成
データ駆動プロセッサの基本構成である環状パイプライン構造を図'"( に示し、データ全体の流れと各部の説明を簡単に行う。

¯

22：2  2  
マッチングメモリ部ではデータ駆動型プロセッサの核と言える部分である。ここ
では入力されたデータの待ち合わせを行い、データがそろったときのみそれらのデータが次の部分へと送られる。それによって、演算すべきデータがそろった場合のみに稼動するというデータ駆動処理が可能となる。

¯

：    
 部は命令部であり、22 部より送られてきたデータの処理を用意されている命令によって行う。

¯-：-     - 部ではプログラム部であり、 部より送られてきた結果データの宛先を決める部分である。

¯

2：! 2  2 
この部分では入力データと環状パイプライン内を( 周してきたデータが合流する

'"( プロセッサエレメント構成

Input
Data

M

MM

FP
Output
Data

D

CPS

図  データ駆動プロセッサの基本構成部分である。

¯

1：! 1  2 
ここでは - 部より送られてきたデータが、このまま出力されるのか、そうではなくもう一度環状パイプライン内を廻り処理されるデータかを判定し、データ送信の制御を行う部分である。

'"( において全体の流れは、入力データパケットが入力されると、図 '"( の 2 部であるマージングモジュールに送られる。マージングモジュールを通過したパケットは、図 '"(の 22 部であるマッチングメモリに留められ、必要なもう片方のパケットが到着するまで
図格納される。ここで、両方のパケットがそろった場合、２つのパケットは操作コード、目的
ノード番号、カラー、オペランドのペアを含む操作パケットの形に格納される。この新しく

'"' 命令実装部'"( の  部へと送られるか、操作コードから指示を受けた ;が実行される。指示通りの操作が実行された後に、出力パケットが生成されて、図 '"( の- 部へと送られる。この - 部において古い目的ノード番号は新しく書き換えられ、出生成されたパケットは図

力パケットは入力パケットと同様のフォーマットに生成される。最終的に出力パケットは図'"( の 1 部へと送られ、パケットの指示している目的に従って、出力を切り替える。
パケットフォーマットを図  に示す。
本研究において実装するルーティング用新命令回路はデータ駆動プロセッサの基本構成では

 部にあたる。

Op. code Dest. node Generation id. Data type 1st data 2nd data 3rd data 4th data 5th data 6th data

16 bit10 bit25 bit21 bit72 bit (12 bit × 6)

図   におけるパケットフォーマット

 命令実装部
この超高速ルーティング検索機構の実現方法について、これまでに使われてきた既存のシステムでは問題点があり、以下のようにどちらかの性能を優先としなければならないといえる。
これらの問題を解決するために序論において述べた特徴を持つデータ駆動型プロセッサへの適応が提案される。
本研究において実装した超高速ルーティング検索機構は、データ駆動処理と親和性の高い
アルゴリズムを採用している。データ駆動型プロセッサでは、その特徴として自己同期型パイプライン機構を有しているため、パイプラインによる高速化を図ることができる。また、

'"' 命令実装部
マルチプロセッサ構成であるため、専用ハードウェアが組込み易いといえる。そのため、設計の容易化を図ることができる。加えて、この特徴により処理内容毎にプロセッサコアを用意することにより、機能分散を行え、また複数のプロセッサコアを使用することから、負荷分散も図ることができる。同様にして、検索データを分割配置することによって、メモリア
クセスの分散化もできる。

'

以上の理由により超高速ルーティング検索機構は、 種類の  専用回路をデータ駆112）に組み込む事により理想的に実現にされる。

動型マルチプロセッサ（

第章

データ駆動原理に基づく超高速ルー
ティング処理 超高速ルーティング機構の処理概要
通常、ルータの処理には

 アドレスの   処理やルーティングテーブルの更新処理などを行うものである。その中でもルーティングテーブルの処理などでは、すでに処理手法 が確立されており、これらの部分を改善する必要はないといわれている。しかし、処理は非常に処理コストがかかり、ルーティング処理のボトルネックとなっているために、高速化を図るために様々な改善案が提案されている。

  処理には、ルーティングテーブル内の複数のエントリの中から入力された宛
先アドレスを比較してその中から一致する最長のエントリの検索を複雑な    &%2 92: 検索によって行う。この一致したエントリが最長のエントリであるという確
この実性を得るために、ルーティングテーブル内の複数のエントリをすべて比較し、検索を行う必要がある。そのためにこの  にはルーティング処理の他の部分に比べて非常に処理時間がかかるといわれている。
これまでに提案された様々な2 検索手法の多くはアルゴリズムの提案である。この2 アルゴリズムには様々なものがあるが、キャッシュ方式のようにトラヒック分布への適応が困難である場合や、ツリー方式ではメモリアクセス回数が多いなどのマイナス的要因があるなどの高速化への問題として課題を残している。しかし、今回新しくハードウェアを含めた超高速実現法の提案がなされた。



+"' -  検索命令
この提案された超高速ルーティング検索機構では、メモリアクセス回数の削減、パイプラ
イン並列化による性能向上を達成するために、平均メモリアクセス回数の少ない

-9  -  :  法が使われている。-  構造はルーティングテーブル内の複数のエントリを  木構造に写実するが、この場合通常の  構造では非常に深い構造になるためにメモリアクセス回数が肥大化し、この部分がボトルネックとなる。そのため、この 構造を深さ方向に圧縮を行うことによって、( 回のメモリアクセスにおいて数ビット分を (度に比較するため、平均メモリアクセス回数を極小化することができる。
この超高速ルーティング検索機構は

-  検索と  &% 検査の ' 種類で構成されてい-  検索では -  構造によってテーブル内に格納されている複数のエントリから、探している  アドレスを見つけだす。この操作は複数回行われ、これによっていくつかの  アドレスが候補として挙げられる。この検索が終了すると  &% 検査へと移る。次に &% 検査では、-  検索によって候補として挙がった  アドレスの中から、  &% 2  によって検査を行い、正しい  アドレスと出力ポートのポインタを探しだす。これらの命令を複数回実行することによって、高速に  アドレスを検索することが
る。

できる。

  !  検索命令
-  検索命令は、宛先  アドレスが入力されると、レベル圧縮された  構造に
よってメモリ上に配置されている  アドレス群を / 段のパイプラインで検索する。これらの検索が終了すると  アドレスと検索結果は、次の命令である  &% 検査へと送られる。
 で行う。
これら一段分の検索を複合命令       では  アドレスと検索用データを入力する。
検索用データは、¯¯<  ：検索に使用する  アドレスの  からの長さ
：検索に使用する  アドレスの 2< からの位置

+"' -  検索命令  ：-  の検索レベルにおけるノードの基準ポインタ

¯

である。

 の子ノードを取得するためにメモリ参照アドレスを求める。そのために  ア
ドレスの 2< を基準として  番目から <  分のビット数分のデータに  
を加えたものをメモリ参照アドレスとし、-  構造のテーブルとなっているメモリを対まず、象としてメモリ参照を行う。
メモリ参照により得られる子ノードのデータは、¯¯¯<  ：次の検索で使用する  アドレスの部分長： アドレスの検索に使用しない部分長  ：次の検索の基準ポインタである。

<  を参照して、<  の値が 3 であるならノードが葉であるとみなして検索終了とし、 アドレスと -  &% のためのポインタを出力する。
この場合は   の出力ポートから -  % のためのポインタが出力される。
<  の値が 3 以外の場合はノードが葉でないとして、もう一度検索を行うために新しい検索用データが必要となる。新しい検索用データは、メモリから読み込んできた < を新しい <  、入力されたデータの <  と  にメモリから読み込んできた  の値を加えたものを新しい 、メモリから読み込んできた   を新しい  
として、次の検索用データとして  アドレスとともに出力される。これら一連の処理が-  検索の ( 段分の検索処理となる。
    命令の概要図を図 +"( に示す。
次に、得られた子ノードの+"+ プレフィックス検査命令

図 



  概要図

 プレフィックス検査命令
 &% 検査は  検索により得られた検索結果により    &% 2  による検査を行い、 &% が正しいかを検査する。正しければ = %>  へのポインタを出力する処理を行い、誤りならば <  によって  &% の再検査を行う処理へと移る。
これら一回分の検査は複合命令 -  &% で行われる。
-  &% では -  検索によって得られた検索結果と一致するプレフィックスを検索して、そのプレフィックスに対応した = %> が格納されている = %>  へのポ
インタを取得する。
入力するのは アドレスとプレフィックス検査データ取得用のポインタである。



+"+ プレフィックス検査命令
まず、プレフィックス検査データ取得用のポインタによりメモリを参照して、検査用デー
タを取得する。
検査用データは、¯¯¯ &%：プレフィックス，-  検索によって検索された  アドレス候補
2 長：2< から何ビット分比較するか決定する値= %>   ：= %>  参照用ポインタである。

2 長を元にして、2 長ビット分の  アドレスとプレフィックスを取得して比較する。一致すれば = %>   の出力を行う。一致し得られた検索用データのない場合は再検査のために、新しいプレフィックス検査データ取得用のポインタを作成し、この値と アドレスを出力する。これら一連の処理が  &% 検査の ( 段分の検索処理となる。

-  &% 命令の概要図を図 +"' に示す。

+"+ プレフィックス検査命令

図 



  概要図



第章

ルーティング用新命令回路設計" 各命令における論理の体系化( つである     では、  #<  ##   の各値が入力され、  ##   # フラグが出力される。検索が終了した場合には、これらのデータは次の命令である -  &% に向かわなければならない。その場合に行き先はフラグによって決められる。フラグは - 部
本研究で実装したルーティング用新命令回路のに送られると、その値によって行き先が決定する。フラグが立っている（フラグ＝１）場合-  &% に送られる。フラグが立っていな へと送い（フラグ＝０）場合は、もう一度検索を行うためにこれらのデータは   には検索終了とみなされ、これらのデータはられる。

-  &% においても、  #-   &%  の各値が入力され、  #= % >   #-   &%  # フラグが出力され、フラグによって - 部で行き先が決められる。フラグが立っている（フラグ＝１）場合には検査終了とみなされ、= % >   が出力される。フラグが立っていない（フラグ＝０）場合は、再検査を行うためにこれらのデータが -  &% へと送られることになる。
同様にして" 回路記述言語による設計
この章では超高速ルーティング検索機構を実現するために、ルーティング用新命令回路として

 と -  &% の ' 種類の新命令回路を回路記述言語で設計した構造と、

)"' 回路記述言語による設計
それぞれの処理概要について述べる。

   の回路構造

-  検索を行うための新命令回路である     の設計を回路記述言語にて行う。
 命令では宛先  アドレスと検索用データが入力される。
この    における各モジュールの動きを示す。
以下に図 )"( の   
入力されるデータは以下のとおりである。

  ：+'<  ：/
：0  ：'3

¯
¯
¯
¯

<  と  の値を加算する。
［］    の 2< から、［(］によって得られた値ビット分の長さを取得する。
［］ ［'］によって得られた値と   の値を加算する。
［］ ［+］から得られる値をメモリ参照アドレスとして、メモリから <  ##  ［］を取得する。

)<  の値が 3 であるならフラグを立てる。
［］ ［(］の値と［)］より読み込んだ  の値を加算する。
［］ ［ ］より読み込んだ

これより以下のデータが出力される。

¯
¯
¯
¯
¯

  ：+'<  ：/
：0  ：'3
フラグ：()"' 回路記述言語による設計
   は入力 され た値が その まま 出力さ れ、<  は
  の値が 出力［)］より 得られた <  の値、   も同様に［)］の  の値は実質的には次の検索で使用するための、される。尚、検索終了時の-  &% の値が格納されている。これらの値は出力後に - 部にて行き先が決められ、> の場合には   ，   （実質的に -  & ｘ  ）が、2> の場合には   ，<  ，，   が最終的に出力されるた
め、結果的にそれぞれの値が > の場合には次の命令である -  &% 命令に送られ、
2> の場合には     命令へと送られ検索が行われる。
出力 デー タに ついて 、

図  )"' 回路記述言語による設計
  の回路構造

 &% 検索を行うための新命令回路である -  &% の設計を回路記述言語にて行う。
 命令から送られた来た  アドレスと検索結果であ
この -  &% 命令では   るポインタが入力される。
以下に図)"' の -  &% における各モジュールの動きを示す。

入力されるデータは以下のとおりである。

  ：+'-  &% ：'3¯¯-  &% メ モ リ 参 照 ア ド レ ス と し て 、メ モ リ か ら  &%#2
長#= %>   を取得する。
［］    の 2 長分のビット長を取り出す。
［］  &% の 2 長分のビット長を取り出す。
［］ ［'］［+］の値を比較して一致すればフラグを立てる。
［］ -  &% の値に１を加える。
［］

これより以下のデータが出力される。

¯
¯
¯
¯

  ：+'-  &% ：'3
フラグ：(= %>   ：0 

 命令の場合と同じように、これらの値は出力後に - 部にて行き先が決められる。そのとき、2 の場合には = %>   が出力され、22 の場合は   ，-  &% が出力される。そのため、結果として 2 の場合には = %>   が出力され、正しい出力ポートにたどり着くことができ、

)"' 回路記述言語による設計
22 の場合にはそれぞれのデータが -  &% 命令へと送られ再検査される。

図   )"+ 性能分析" 性能分析
これら' 種類のルーティング用新命令回路の設計を行った結果を示す。

設計評価に使用した環境を以下に示す。

¯

 チップ67'386 6'38'336-),)£  社¯

論理合成ツール    £
6%   社¯

シミュレータ2  6?66 /")£2    社
設計 したル ーティング 用新命 令回路 である と -  &% の ' 種類は 、

2  6?66 /") を用いてシミュレーションを行うことで、データの動きを確認する
ことができる。
また、論理合成ツールで論理合成後、最適化を行うことで、どの部分が



 命令

-  &% 命令のクリティカルパスとなるかを示すことができる。それぞれのクリティ
カルパスを回路図を用いて図 )"+ 及び、図 )") に示す。

と)"+ 性能分析

図    のクリティカルパス

図    のクリティカルパス

' 種類の新命令はそれぞれ、    では入力データ  が入力され、フラグが出力されるまで。-  &% では -  &% が入力され、この図に示されるようにフラグが出力されるまでがクリティカルパスとなっていることが確認できる。
このクリティカルパスをもとにして到達時間と要求時間を測定した結果を表)"( に示す。

)"+ 性能分析
表  要求時間と到達時間 -  &%

 $      



++"++
++"++

')"'.
'("+.

."3)
((".)



第

章

ルーティング用新命令回路の考察# 新命令における命令実行時間の考察
クリティカルパスは各回路において、最も遅延があり、そのためにデータの到着時間の最もかかる経路である。そのために、クリティカルパスにおけるデータ到達時間を計ることによって、命令実行時間が算出できる。また、今回計測したデータはクリティカルパス全体のデータ到達時間ではなく、入出力にかかる部分の時間は除外してある。つまり、命令内部でのデータ到達時間を測定したものである。
クリティカルパスより算出した新命令の命令実行時間を表
表 /"( に示す。

命令実行時間（メモリアクセス時間を含まない）

命令実行時間（メモリアクセス時間を含まない）

 -  &%')",/ 45'("+. 45

ただし、この表においてメモリアクセス時間は考慮されていないため、実際の命令実行時' 種類の新命令に設計したメモリはともに、アドレス、書き込み、読み出しの非同期な @2 を想定して間を示すにはこの数値にメモリアクセス時間を加算する必要がある。これらいる。
メモリには様々な種類があり、高速な@2 を使うことでメモリアクセス時間を短縮する

ことは理論上可能となる、しかし、今回必要とされるメモリには高速性だけではなく、格納/"' 新命令における回路コストの考察できる容量も重要であるために、高速であるだけのメモリを使用することはできない。これらの条件を考慮して、本研究ではメモリはメモリアクセス時間は約@2 を使用するものとし、この @2 の*45 とする。これ以降のメモリアクセス時間にもこの数値を適用する。

@2（メモリアクセス時間を約 *45 とする）として、メモリアクセ
ス時間を考慮して算出した命令実行時間を表 /"' に示す。
使用するメモリを

表 

命令実行時間（メモリアクセス時間を  とする）

命令実行時間（メモリアクセス時間を -  &%

*45 とする）

+3",/ 45
約 '0"+. 45約# 新命令における回路コストの考察
回路規模を見積もるために' 種類の新命令回路のゲート数を計測した、加算器とセレクタにおいては以下のものを用いて見積もりを行った。

¯

加算器
高速桁上げ回路及び、全加算器¯

セレクタ（マルチプレクサ）+' 入力のマルチプレクサ
これらをもとにして全ゲート数の総和により算出した回路規模見積りを表/"+ に示す。

 チップの規模を表 /") に示す。
 命令が ')3)
本研究で実装を行った ' 種類の新命令回路の見積よりそれぞれ、  ゲート、-  &% が +),+ ゲートであることから、上記の  チップの標準ゲート数
次に、今回使用したと比較しても回路規模は小さく、回路コストは充分によいといえる。

/"' 新命令における回路コストの考察

表  回路規模見積もり

回路規模見積もり -  &%表 ')3) 4ゲート5+),+ 4ゲート5  デバイス概要 ! "#6'38'336

デバイス
標準ゲート数
最大システム・ゲート数
ロジック・エレメント（
最大

6）数

@2 ビット数

'33#333/'/#,'),#+'3(3*#).*

第

章

性能評価

$ 新命令回路の性能評価
メモリアクセス時間を考慮した命令実行時間は

 命令が約 +3",/45、-  &% 命令が約 '0"+.45 である。この値をもとにして、実装した新命令回路のパケット
 命令は ' 回、処理能力を見積もる。この新命令回路を使用すると、平均的に   -  &% 命令は ( 回行うことで、  を完了することができる。ただし、これら '種類の命令はハードウェアであるので、それぞれが独立して動作している。そのため、パケットの処理を行う場合、一連の処理の中で命令処理時間の遅い 命令がパケッ

ト処理性能に影響を与える。
これにより、算出した新命令回路のパケット処理性能の見積もりを表*"( に示す。

表  パケット処理性能見積もり

パケット処理性能
新命令回路

約+#'33 万 4 ? 5  処理のデータ転送速度を見積もる。このときの  パケット長は最小の場合には )0< 、平均では (3')<  とする。
  処理のデータ転送処理能力の見積もりを表 *"' に示す。
次に、上記で見積もったパケット処理性能より、上記にパケット処理性能やデータ転送処理能力を見積もった値を示した。それによって、少なくとも見積もりによって算出された性能を出すことは可能であるといえる。これは

*"( 新命令回路の性能評価
表  データ転送処理能力

データ転送処理能力

 パケット長 )0< 
平均  パケット長 (3')< 最小("/ 4< ? 5+' 4< ? 5 上にて実装した見積もりの値であり、実際に専用ハードウェアでつくることによって、格段に性能は上昇することが予想できる。これにより、 を利用することで処理性能を見積もれ、それにともなうハードウェアリソースやコストパフォーマンスを算出することができるといえる。



第

章

結論
'

本研究では提案された超高速ルーティング検索機構を受けて、 種類の新命令回路である

 命令と -  &% 命令の設計を行った。+ 章では超高速ルーティング検索機構の原理について述べ、) 章において設計を行い、その設計内容を示したのちに、性能分析を行いクリティカルパスによって要求時間と到達時間について述べた。/ 章での命令実行時間と回路コストの考察によって得られた結果を受けて、* 章において性能評価を行うことで、パケット処理性能とデータ転送処理能力の見積もりを行い、これにより自己タイミング型
アーキテクチャを用いたシステム開発において、システムの事前評価を を用いて行うことの優位性を示した。
本研究では自己タイミング型アーキテクチャと親和性の高いアルゴリズムで作られた超高速ルーティング検索機構を 上に設計することで、自己タイミング型アーキテクチャを用いたシステム開発の事前評価を行った。しかし、命令部のみでは当然ながら実用的とは言えず、この' 種類のルーティング用新命令回路はプロセッサに組み込まれることによって、実際に稼動する。
そのため、今後の展望では以下の事柄が考えられる。

("

本研究で実装した' 種類の新命令をプロセッサに実際に組み込み、プロセッサ全体の性能評価を行う。この場合は自己タイミング型パイプライン機構を有して動作するプロセッサを作ることになり、現状ではこれらのルーティング用新命令を組み込むべきプロ
セッサへの適応を考えることとなる。

'"

今回は

 上での実装をして性能評価を行ったが、実際にデータ駆動型プロセッサに組み込んだ場合、事前評価とくらべてどの程度の性能差が出るのか、また事前評価によって得られた値と比べ、どの程度の性能向上を見込むことができるかなどを調べる
ことが考えられる。

+"

これら' 種類のルーティング用新命令の設計をして、その評価として命令実行時間や回路規模の見積もりなどを行ったが、これらの新命令にはいくつか加算や乗算などの処理を行う部分があるが、これらはすでに

; として作成されいるものがあり、これを考慮した性能評価を行うことが考えられる。

謝辞
本研究において懇切なる御指導、御鞭撻を賜った岩田 誠 教授に心より感謝の意を表します。
本研究室の基礎としているデータ駆動型アーキテクチャを提唱され、様々な御示唆を賜った、寺田 浩詔 教授に心より感謝の意を表します。
本研究を進める上で、適切な御助言、御指導を賜った大森 洋一 助手に深く感謝の意を表します。
本研究を進めるにあたり、様々な御助言、御指導を賜った高知工科大学 情報システム工学

1   教授、科の坂本 明雄 教授、島村 和典 教授、岡田 守 教授、門田 幹夫 教授、

!  >  教授、竹田 史章 教授、菊池 豊 助教授、篠森 敬三 助教
! 助教授、 明神 千代 助教授、 福本 昌弘 助教授、 浜村 昌則 講師、

清水 明宏 教授、授、@ 

任 向実 講師、妻鳥 貴彦 助手、近藤 剛 実験講師に心より感謝の意を表します。
日頃、温かい御支援、御助言を頂いた大学院生の細美 俊彦 氏、橋本 正和 氏、別役 宣奉
氏、森川 大智 氏に感謝の意を表します。
日頃から御支援戴いた岩田研究室の小倉 通寛 氏、三宮 秀次 氏、志摩 浩 氏、中村 勲二氏、原田 香織 氏に感謝の意を表します。
日頃から御意見、御支援を頂いた岩田研究室の荒木 俊介 氏、岩井 秀樹 氏、大石 祐子 氏、
西山 直人 氏、平井 圭一郎 氏、宮崎 康徳 氏、山岡 正明 氏に心より感謝の意を表します。



参考文献
4(5 >" # "2# 2"!# A112BC                 A#  "   666# ,09':# '.''.* 9(...:"
4'5 1"2 !# 2"!# >"> #  >" # A          11   = ! A#     1    -   
 # )+()+* 9'33(:"
4+5 16- 監修# 浅田 邦博 編# Aディジタル集積回路の設計と試作A# 中央印刷# 9'333:"
4)5 喜安 善市# 清水 賢資# Aディジタル情報回路（第 ' 版）A# 森北出版株式会社# 9(.,.:"

