研究室紹介

Last Modified:2014/03/24

明治大学・理工学部・情報科学
笹尾　勤　研究室（コンピュータ・システム研究室）


情報検索やパターンマッチングを高速に行う手法を研究している．


主な研究テーマ
  1. インターネット用パターンマッチング装置．
  2. インターネット用パケット分類装置．
  3. データマイニングの応用．
  4. ビッグデータの表現法（決定グラフを用いた手法）．
  5. FPGAの設計理論．
  6. EXORを用いた論理設計．
  7. 論理回路の複雑度解析．
  8. スペクトル変換を用いた論理設計．
研究室に入ると自然に英語がうまくなる．

インターネット用パターンマッチング回路．

　以下のようなパターンマッチングを行う論理回路を研究中である. 　いずれも, 企業と共同研究中であり, 特許も保有している.
完全マッチング
　ビットパターンが, 完全に一致したものを見つける. インターネットのアクセス制御回路に使用する. 入力数は48から128で, パターン数は数万程度までである.

LPMマッチング
　Longest Prefix Matching (接頭語が, なるべく長く一致するようなパターンを見つける）. これは, 英単語帳で, 検索している英単語を見つける作業に似ている. インターネットのルータで利用する. 入力数は, 32から128で, パターン数は, 数万程度までである.

正規表現マッチング
パターンを正規表現で記述する. ウイルスや, 迷惑メイルの検出に使う. パターン数は, ５０万以上である.

インターネット用パケット分類装置．

　インターネットでは、データを、パケット（小包）という小さな単位に分割して送ります。インターネットでは、ウイルスや、不正プログラムを送ることにより、パスワードを盗んだり、迷惑行為を行う人がいるので、それを防御するための処理が必要です。また、迷惑メールが氾濫し、本来必要な情報がその中に埋もれてしまい、貴重な資源を浪費していますが、それを除去する処理も必要です。これらの処理をするために、コンピュータや専用LSI（集積回路）を使用します。ただ、通常のコンピュータでは、処理が遅くて間に合わないため、専用LSIを使うことが多いです。これらのLSIでは、データの中にあるパターンを高速に見つけます。
メモリを用いた設計
　インターネットのアドレス、ウイルス、迷惑メールなどは、頻繁に変化するので、LSIの内容も、頻繁に書き換える必要があります。これらのLSIは、一旦電源を入れれば、何年間も、電源を入れたままの状態にするため、電力消費は極力減らす必要があります。このような処理を行うLSIは、どのような構造にすればよいのでしょうか？　色々な構造があると思いますが、私は、メモリを用いた構造を提案しています。メモリは、規則的な形をしており、微細化（光学技術を用いて回路を縮小すること）により、値段を下げることができます。また、メモリを使うと、内容を簡単に書き換えることができます。つまり、書き換え可能なLSIとなります。また、消費電力も通常のコンピュータに比べると少ないです。

多値CAMを用いた方法
　 インターネットでは，様々なユーザに対して個別サービスの提供や，パケットの通過を監視するパケットフィルタリングを行っています. その際に必要な処理がパケット分類です．パケット分類はスイッチまたはルーターで行いますが，大量のデータを高速に分類する必要があります． 現在，高速にパケット分類を実行するためにTCAM (Ternary Content Addressable Memory)というメモリを用いています．TCAMは入力データに対してTCAM内に格納されたデータを1クロックで検索できるので，ソフトウェアを使った検索手法より高速です． TCAMには，IPアドレスやポート番号などを用いてパケットの分類をするための規則を記載したルールセットを格納します．その際，ポート番号は整数の区間で指定するため，1つのルールを表現するために複数のTCAMワードが必要な場合があります．しかし，ポート番号の符号化を工夫すれば，1ワード中により多くのルールを格納できます． 例えば，4値CAMを用いればTCAMより効率的にルールセットを格納できます．本研究ではこの考え方を発展させ，さらに多値化した8値CAMと16値CAMのワード数を推定します． また，ClassBennchというベンチマークデータを用いて，4値CAMと比べ，どの程度ワード数が減るのかの実験を行い，実験結果に対して考察を行います.

データマニングの応用

論理合成の技術をデータマイニング分野で応用することを考えている.

ビッグデータ表現のためのデータ構造（BDDとその拡張）．

　ｎ変数論理関数を計算機上で表現する方法は多数ある．
真理値表
　関数部のみを記憶すれば，２nビットで表現できる． ｎ＝５のとき，32ビット計算機では１ワードに納まり，高速に演算が実行できる． また，表現が一意的という特長もある． n=24程度(16MB)までは実用的であが，ｎ≧30の時はメモリが大きくなりすぎる．

論理和形(SOP)
　一つの積項は２ｎビットで表現できる．AND,OR,NOT等の処理が比較的容易であり，多数のアルゴリズムが開発されている．また，SOPはAND-OR二段回路に対応している．パリティ関数や加算器などを表現するには，SOPは２nに比例した大きさとなる．一般に，一つの関数を表現するSOPは一意的に決まらない．

BDD（二分決定グラフ）
関数とその否定を同時に表現できる．また，変数の展開順序を決めれば，BDDは 一意的に定まる．AND,OR,NOT演算や等価性判定が高速に実行できる．多くの実用回路に対しては， BDDはそれほど大きくならない．展開する変数の順序によって表現の複雑度が大きく変わる．最悪Ｏ(2n/n)個の節点が必要である．多くの実用的な関数に対して， 真理値表やSOPよりもBDDの方がメモリは少なくてよい．そのため，論理設計の種々の問題は，BDDで表現すると能率よく解決できる場合が多い． 　本研究室では，BDDの拡張として，スペクトル変換グラフ, SMTBDD（shared multi-terminal binary decision diagram), HMDD (heterogenious multivalued decision diagram)等を開発した．

FPGA（Field Programmable Gate Array)の設計理論．

FPGAでは基本モジュールとしてPLA (Programmable Logic Array)，ROM (read only memory)，および MPX (multiplexer)を考え，与えらた論理関数をモジュールを用いて能率よく実現する方法について研究する．

EXORを用いた論理設計．

　従来の論理設計法は，AND,OR,及びNOTを基本としている． しかし，算術演算回路，誤り訂正回路，通信用回路等では，ＥＸＯＲを活用するとゲート数の少ない回路が設計できる． 本研究室で開発した高性能AND-EXOR形論理式の簡単化プログラムEXMIN2は世界的に有名である． 1995年の8月に幕張で，2009年の5月には那覇で、2013年の5月には富山でReed-Muller国際ワークショップを開催した．

論理回路の複雑度解析．

　与えらた論理関数を論理回路として実現する際，必要なゲート数や接続線数の予測が重要である． ゲート数や接続線数は実現法や，実現すべき関数のクラスによって異なる． 任意のｎ変数関数を実現するために必要なゲート数は，ｎの指数関数となる． 論理回路の複雑度を調べることによって，回路実現に必要なゲート数や接続線数を予測できる．

スペクトル変換を用いた論理設計．

　論理関数のスペクトルを解析することにより，論理関数の大域的性質が明らかになり，それを用いて能率の良い回路を設計できる． これは，アナログシステムの設計や解析にスペクトラル解析が有効であるのに似ている． スペクトラル解析をデジタルシステムの設計や解析に利用する手法は従来から知られていた． しかし，ｎ変数論理関数のスペクトルを計算するために２nの行列を用いる計算法しか知られておらず，ｎ＝３０程度の問題でも，計算機の記憶容量を越えてしまい，実用上利用不可能であった． しかし，最近，MTBDD（多端子二分決定グラフ）を用いることにより，n＝100以上の論理関数のスペクトラムを短時間内に計算する方法が開発された． この方法を用いることにより，スペクトル解析を実用回路の設計に利用できる可能性が出てきた． 本研究では，論理関数のスペクトルを解析することにより，論理関数の大域的性質を解析し，それを用いて回路を能率よく設計する方法について研究を行う．
Back