中京大学磯研究室研究紹介 ◆ 目次 ◆ 1. sequence-pairを用いた一般構造フロアプランに関する研究 2. トランク方式クロック分配回路のスキュー改善に関する研究 3.分枝限定法によるリソースバインディング手法に関する研究 4. Cooperアルゴリズムを用いた制約論理式の真偽判定手法 5. 遺伝的アルゴリズムを用いたルーティング手法 6. 痕跡と正規手続きデータベースを利用した侵入検知システム 7.バッファオーバーフローの視覚化とプログラム作成支援 8.俯瞰可能迷路における半環によるモデル化と最短経路導出手法 9. 標準電波を用いた時刻同期システムの開発中京大学磯研究室の研究テーマ ＶＬＳＩ設計 ＣＡＤアルゴリズム ネットワーク技術研究紹介1 sequence-pairを用いた一般構造フロアプランに関する研究(1) LSIの開発・・・面積をなるべく小さくしたい ⇒配置配線処理の前にフロアプランを行うフロアプランとは ⇒ 矩形領域をある機能を実現する幾つかの小領域に分割すること a フロアプラン b c d b a c d どんなフロアプランでも定式化できるsequence-pairに注目研究紹介1 sequence-pairを用いた一般構造フロアプランに関する研究(2) sequence-pair：モジュールの相対位置関係を 2つの順列によって表したもの本研究室ではsequence-pairを用い、フロアプラン問題における最適解を高速に見つけるためのアルゴリズムについて研究している。研究紹介2 トランク方式クロック分配回路のスキュー改善に関する研究(1) LSIの微細化、大規模化クロックスキューが問題スキュー：各ノードへの信号伝播時間の差トランク方式クロック分配回路：メッシュ状の配線から、短い配線を介しFFを駆動する方式の回路特徴・スキューが小さい・消費電力が大きいトランク方式クロック分配回路の回路の例研究紹介2 トランク方式クロック分配回路のスキュー改善に関する研究(2) ：ダミーセルトランクバッファ回路をダミーセルに置換駆動力を調整し、スキュー改善置換処理ダミーセル：バッファから出力を取り除いたものダミーセル研究紹介3 分枝限定法によるリソースバインディング手法に関する研究(1) リソースバインディング・ディジタル信号処理ハードウェアのデータパス設計・ RTL(Register Transfer Revel) のデータパスを合成するためのリソースバインディング *2 in 数、レジスタ数) ＜出力＞・アーキテクチャモデル(RTLのデータパス) in ＭＵＸ *1 *3 out ＜入力＞・スケジューリングされた DFG(Data-Flow Graph) ・リソース(演算器の種類やその＜枝＞変数を表す。レジスタに割り当てる。Ｒ１ *2 ＜マルチプレクサ＞ひとつの入力端子に二つ以上の入力があったときに使用。Ｒ２Ｒ３ out in *1 *3 out M1 M２＜節点＞演算を表す。演算器に割り当てる。スケジューリングされたDFG アーキテクチャモデル研究紹介3 分枝限定法によるリソースバインディング手法に関する研究(2) 特徴・リソースバインディングは NP困難問題分枝限定法により、解空間を早く削減でき最適解を現実時間で算出可能。分枝限定法を適用＜入力＞ *2 ＜出力＞ in 演算器割当て *1 *3 out in *2 in *1 初期割当て *3 out コストが悪くなる演算or 変数を選択するＭＵＸレジスタ割当てＲ１Ｒ２Ｒ３ out 未割当て演算、データ転送路変数選択割当てすべて割り当てるまで繰り返すコスト算出リソースバインディング手法のアルゴリズム M1 悪いコストなら削除する M２研究紹介4 Cooperアルゴリズムを用いた制約論理式の真偽判定手法（１）回路条件を論理式で表し、回路の正当性を検証 Cooperのアルゴリズム＝論理式の論理和を求める <回路例> A 1. 0<=A<=9である B 2. 0<=B<=9である加算器 C <条件> 回路の持つ条件 S 3. A+B=10C+Sとなる C,Sを出力する研究紹介4 Cooperアルゴリズムを用いた制約論理式の真偽判定手法（２） <条件> 1. 0<=A<=9である 2. 0<=B<=9である 3. A+B=10C+Sとなる <論理式> ∀A ∀ B ∃ C ∃ S [(0<=A and A <=9 and 0<=B and B <=9) ⊃(A+B=10C+S and 0<=S and S <=9)] C,Sを出力する真偽判定本研究室では、論理式をより高速に真偽判定するためのデータ構造の設計を行っている。検証可能研究紹介5 遺伝的アルゴリズムを用いたルーティング手法(１) 近年のインターネットの普及ネットワークにかかる負荷が増大遺伝的アルゴリズムを利用して高品質なルーティングを行う（代替経路を探索する）障害、アクセス過多等により、ネットワークが混雑研究紹介5 遺伝的アルゴリズムを用いたルーティング手法(２) D B 遺伝的アルゴリズム A E F 生物の進化まねたアルゴリズム C ネットワークモデル問題を遺伝子として表現ネットワークモデルを木構造で表現その節点を遺伝子として扱う B A E 高速ルーティングのための木構造の簡単化 C D E D E F D F F F F ツリー構造 F F 研究紹介6 痕跡と正規手続きデータベースを利用した侵入検知システム(１) 特徴    『正規の行為』を記述したデータベースを利用 →未知の攻撃でも検出可能侵入に伴う特徴的なイベント(痕跡)のみ監視する →解析に伴う負荷を最小限にとどめられる統計的手法ではない →誤検出、不検出を最小限にとどめられる問題点『正規の行為』を登録する作業が煩雑改良前のフロー図ログやシステムコールトレース “痕跡”データベースと照合一致正規手続きデータベースと照合不一致発報研究紹介6 痕跡と正規手続きデータベースを利用した侵入検知システム(２) 煩雑な正規手続きデータベースの作成・更新の効率化改良点 ① システムコールの呼び出しを判断し、ある行為に伴う一連の挙動を自動的に体系化して抜き出す ② データベースへ登録できる形に整形し、自動登録改良後のフロー図ログやシステムコールトレース “痕跡”データベースと照合一致正規手続きデータベースと照合不一致データベース更新システム管理者発報研究紹介7 バッファオーバーフローの視覚化とプログラム作成支援（１）ネットワーク環境が整備課題：セキュリティの確保調査 Exploitにバッファオーバフローが用いられる例：スタックスマッシング攻撃文字配列を利用したバッファオーバフロー攻撃セキュリティホール発見侵入セキュリティホール利用 Root権限奪取破壊スタックスマッシング攻撃研究紹介7 バッファオーバーフローの視覚化とプログラム作成支援（２）  本研究室では、バッファオーバフローの状態を視覚的に訴えメモリ構造のシミュレーションを行うことでC言語学習者を対象とした脆弱性のないプログラミングの作成支援を目指している。イメージ図研究紹介8 俯瞰可能迷路における半環によるモデル化と最短経路導出手法(１) 俯瞰 = 全体を見渡すこと俯瞰可能な迷路＝定式化可能俯瞰不可能な迷路俯瞰可能迷路の構造を行列式で表現俯瞰可能迷路 1 2 3 定式化行列式 E 1 d 0  E   l 1 r  0 u 1  研究紹介8 俯瞰可能迷路における半環によるモデル化と最短経路導出手法(２) 半環という代数系の特徴を用いた行列式の積 d dr  1 d 0  1 d 0  1  dl       E2   l 1 r    l 1 r    l ld  1  ru r  0 u 1  0 u 1   ul u ur  1 En1,M (≠0) が最短経路を示す d dr  1  dl   E2   l ld  1  ru r   ul u ur  1 r 1 d 2 3 • 深さ優先探索と比較して、次の特徴がある 1. 迷路の探索回数・・・深さ優先探索: O(M2)、本手法: O(M) 2. 各分岐点で選択すべき進行方向も得られる研究紹介9 標準電波を用いた時刻同期システムの開発 (１) 複数の計算機がネットワークを介して協調動作互いに正確な時刻情報を保持し同期していることが必要．時刻を高精度で保持するため，NTP等いくつかの時刻同期手法が考案,正確な時刻をもつ「時刻サーバ」と接続する必要がある. ネットワークのゆらぎで同期困難研究紹介9 標準電波を用いた時刻同期システムの開発 (２) 通信総合研究所が発射する標準電波の利用し、日本中どこでも手軽に正確な時刻を取得可能。本研究室では，“標準電波”を用いたネットワーク時刻同期システムを開発，精度測定を行っている．