Document

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