著者

上土井 陽子 若林 真一 吉田 典可

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.48, pp.17-22, 1995-11-17

参考文献数

5

---

グラフの最小コストk分割問題は枝に正の重みを持つ無向グラフG=(V,E)の節点集合Vを互いに非連結なk個の節点集合に分割する最小コスト分割を求める問題である.この問題は巡回セールスマン問題やVLSI設計で用いられるクラスタリング問題等の組合せ問題の定式化において用いられる重要な組合せ問題の一つである.Goldschmidtらはグラフの最小コストk分割問題に対し,n=|V|とするとき,O(n^<k^2>の計算時間のアルゴリズムを提案している.本稿では最小コストk分割問題に対する多項式計算時間のアルゴリズムを提案する.提案アルゴリズムでは最大流-最小コストカットアルゴリズムをO(n^<k-1>)回適用する.

著者

川中 洋祐 若林 真一 永山 忍

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CPSY, コンピュータシステム (ISSN:09135685)

巻号頁・発行日

vol.108, no.413, pp.189-194, 2009-01-22

---

本稿では,ネットワーク侵入検知システム(NIDS)におけるパケット検査に対するパターンマッチングのための専用ハードウェアの構成を提案する.提案する専用マッチングマシンは,NIDSソフトウェアSnortで採用されている正規表現に基づくウィルスパターン記述を入力とし,高速にマッチングを実現する.提案専用マッチングマシンは,ウィルスパターンの更新に瞬時に対応するため,回路構成がパターンに依存する従来方式のマッチングマシンと,我々が提案しているパターンを実行時に設定できるマッチングマシンで構成されている.

著者

宇丹 裕一朗 稲木 雅人 永山 忍 若林 真一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)

巻号頁・発行日

vol.111, no.450, pp.115-120, 2012-02-28

参考文献数

7

---

バイオインフォマティクスやデータベース検索で使用されている近似文字列マッチングにおいて,より高度なマッチングを行うため,正規表現を扱うシストリックアルゴリズムとそのFPGA実装法が提案されている.しかし,このFPGA実装では,DNAの配列検索などに必要な長いパターンを扱うことができない.そこで本研究では,スケーラブルな処理が可能なGPU上での近似正規表現マッチングの高速解法を提案する.また,FPGA実装と比較することで近似正規表現マッチングをGPU上で実装することの有用性を検証する.実験の結果,CPUと比較してFPGA実装が8.3倍,GPU実装が2.9倍高速に実行できることが分かった.特に,パターン長が3200以上の場合,CPUと比較してGPU実装では18倍以上の高速化ができた.また,FPGA実装ではパターンの文字数がFPGAの規模に制限されるのに対し,GPU実装ではFPGA実装よりも長いパターンを容易に扱えることを確認した.

著者

中村 朋健 上土井 陽子 若林 真一 吉田 典可

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.468, pp.31-37, 2003-11-18

---

近年,巨大なデータベースが世界中の至るところで作成され,そこから役立つ情報を抽出するデータマイニング技術が実用に供されるようになった.規則性の見え難いデータベースからデータベースの性質を見つけ出す場合に,類似したデータ要素を集めるクラスタリングは有効である.特に,大規模な高次元データベースからの知識抽出において,実時間性や即時応答性が要求される分野ではメモリ使用量が少なく高速なクラスタリングが要求される.本稿では,実社会データを想定した高次元かつ疎なデータ空間を対象に,処理時間とデータ要素数が線形関係であるクラスタリング手法を提案する.また,数次元の入力データに対して提案手法を適用し,与えた評価基準により提案手法を評価する.提案手法では入力のデータ空間を階層的に不均一なサイズのセルに区切り,パラメータにより密と判断された隣接したセルを結合させることで,類似したデータ要素を集めるアルゴリズムである.

著者

小出 哲士 北川 章夫 若林 真一

出版者

広島大学

雑誌

基盤研究(B)

巻号頁・発行日

2000

---

本研究では,ディープサブミクロンVLSIチップのレイアウト自動設計に注目し,ディープサブミクロンVLSIチップの実用化と共に顕著になってきた回路のパフォーマンスの考慮,ハード・ソフトマクロブロックの考慮,及び設計時間の短縮,等の問題を解決するための以下の新しいレイアウト設計手法を開発した.1.パフォーマンスを考慮した回路分割手法の開発回路のパフォーマンスを最適化するために,論理合成後に行われる回路分割において,回路のパス遅延を陽に考慮した回路分割手法を開発した.2.パフォーマンスを考慮したフロアプランニング手法の開発ハード・ソフトマクロを取り扱うフロアプランニングにおいて,バッファ挿入と配線幅調整を考慮した概略配線とフロアプランニングを実用的な計算時間で同時に求める手法を開発した.3.パフォーマンスを考慮した配置手法の開発タイミングを考慮したクラスタリングと新しい配置モデル(アメーバモデル)に基づくタイミングドリブン配置手法を開発した.4.パフォーマンスを考慮した配線手法の開発6層以上の配線層に対して,配線幅とバッファ挿入を考慮したスタイナ木生成アルゴリズムを用いて,与えられたタイミング制約を満たす概略配線経路を階層的に求める手法を提案した.5.パフォーマンスを考慮した階層的バッファブロックプランニング手法の開発チップ領域をグローバルビンに分割し,タイミングを考慮したバッファブロックプランニングを階層的に行う手法を提案した.6.パフォーマンスドリブンレイアトに対する適応的遺伝的アルゴリズムの適用エリート度に基づく適応的遺伝的アルゴリズムを提案し,レイアウト設計手法に適用した.また,高速化のためのLSI化を行い,パフォーマンスドリブンレイアウト手法の数10倍の高速実行の見通しを得た.

著者

細谷 好志 若林 真一 小出 哲士 吉田 典可

雑誌

全国大会講演論文集

巻号頁・発行日

vol.47, pp.89-90, 1993-09-27

---

ネットワーク管理における重要な問題の1つに最短経路木更新問題がある.特に各通信リンクの負荷晴報をコストと考えた場合に最短経路木更新問題を解くことは,メッセージを送る経路を決定する際に混雑した経路を避けるという意味で有用である.オンラインシステムではネットワークのトポロジが頻繁に変化するため,その都度最短経跨を更新する必要がある.動的ネットワークにおける最短経路木更新問題はこれまでにも多くの研究がなされてきた.特に,アルゴリズムの実行中でもトポロジの変化を許す場合,いつかはネットワークのトポロジ変化が安定するという仮定のもとでいくつかのアルゴリズムが提案されている.一般にメッセージ複雑度と空間計算量はトレードオフの関係にあり,さらにメッセージに持たせる情報を少なくすれば,一時的に経路木中にサイクルが生じるなどして各プロセスが正しい情報を保持するまでに時間がかかったり,ネットワークが非連結になった場合に正しい更新が保証されない.文献では,静的ネットワークのアルゴリズムを動的ネットワークに適用する手法として,トポロジの変化ごとにアルゴリズムをリセットして再起動させているが,その手法だとそれまでに集められた情報が無駄になってしまう.本稿では,少ない局所情報及びメッセージ情報によって,分散最短経路木更新問題を効率良く解くイベントドリプンアルゴリズムを提案する.

著者

若林 真一 小泉 慎哉 小出 哲士 井村 紀道 藤原 一成

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.44, no.2, pp.340-343, 2003-02-15

---

本論文では,遺伝的アルゴリズム(GA)の実行における計算時間の短縮を目的として,任意のGAを高速に実行可能なRISCプロセッサDLX-GAを提案する.提案プロセッサDLX-GAはDLXアーキテクチャをベースとしたRISCプロセッサであり,GAの実行において多用されるビット演算命令や乱数発生命令,SIMD型命令等をサポートし,これらを6段のパイプラインで処理することによりGA実行の高速化を実現する.提案RISCプロセッサをHDL設計し,CMOS 0.35umスタンダードセルテクノロジを用いて4.93mm角のLSIチップとして実現し,評価ボード上で性能評価を行った.その結果,開発したプロセッサチップが仕様どおりに動作することを確認した.This paper proposes a new RISC processor for high speed execution of genetic algorithms (GAs).The proposed RISC processor was designed based on the DLX architecture,and a new instruction set,which was effective for high-speed execution of GAs, was implemented.The proposed RISC processor was designed with the hardware description language,and it was fabricated as an LSI chip with the CMOS 0.35um standard cell technology.From the evaluation of the fabricated LSI chip using the evaluation board,we have shown that all the functions specified by the specifications of the chip were correctly realized.