共有変数へのアクセス競合の回避を目的とする同時実行可能で拡張可能なハッシュアルゴリズムの改良
スポンサーリンク
概要
- 論文の詳細を見る
本研究では非同期共有メモリシステムにおいて,ShalevとNirが提案した複数の命令を同時に処理でき,かつ,テーブルサイズを拡張できるSplit-ordered listハッシュテーブルの構築アルゴリズム(SOLアルゴリズム)を改良することを目的とする.従来のハッシュテーブルの構築アルゴリズムでは,挿入されるデータ数がテーブルサイズより非常に大きくなるとリストの長さが大きくなりデータ検索の時間が大きくなってしまう問題点があった.SOLアルゴリズムでは,テーブルサイズを拡張することにより,検索すべきリストの長さを一定に保つことができ,データ検索を高速に行える.しかしSOLアルゴリズムは複数の命令を同時に実行した際に,検索のみの命令だと速いが,挿入,または,削除の命令を同時に実行した場合に処理速度が著しく落ちる傾向がある.この処理速度の低下の要因はハッシュテーブルのサイズの拡張に必要であるハッシュテーブルに挿入されているデータ数を格納する共有変数へのアクセス競合にあると考えられる.そこで,複数の命令がデータ数を保持している共有変数ヘアクセスする際に競合が発生することに着目し,このアクセス競合を回避する新しいアルゴリズムを開発することにより,高速なデータ検索を行うことを目指す.
- 2007-12-07
著者
-
若林 真一
広島市立大学大学院情報科学研究科
-
上土井 陽子
広島市立大学 情報科学部 情報工学科
-
上土井 陽子
広島市立大学大学院情報科学研究科
-
末田 直也
広島市立大学大学院情報科学研究科
-
若林 真一
広島市立大学大学院 情報科学研究科
関連論文
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア (リコンフィギャラブルシステム)
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア (VLSI設計技術)
- パターン非依存型正規表現ストリングマッチングマシンとそのFPGA実装(応用技術,リコンフィギャラブルシステムとその応用論文)
- 3L-1 マルチスレッディングに基づく並列フロアプランニング手法の開発と評価(論理・物理設計技術,学生セッション,アーキテクチャ)
- 2L-5 FPGA実装に適した離散データの多項式近似法(上流設計技術,学生セッション,アーキテクチャ)
- 4K-6 Snortルールを入力とするネットワーク侵入検知ハードウェアの開発(HPCと高速化,学生セッション,アーキテクチャ)
- AP-1-2 並列メタヒューリスティクスとLSI CADへの応用(AP-1.回路とシステム領域におけるメニコア計算機の活用,パネルセッション,ソサイエティ企画)
- NIDS専用正規表現マッチングマシンの構成とそのFPGA実装(アプリケーション2,FPGA応用及び一般)
- パターンを実行時に設定可能な正規表現ストリングマッチングマシンとFPGAによる実現(FPGAの応用)
- 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用)
- 配線長を考慮したクラスタリングに基づくスタンダードセル階層配置手法(VLSIの設計/検証/テスト及び一般配置配線)
- 配線長を考慮したクラスタリングに基づくスタンダードセル階層配置手法(VLSIの設計/検証/テスト及び一般 配置配線)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 配線長を考慮したクラスタリングに基づくスタンダードセル階層配置手法
- 匿名データ収集におけるプロトコルからの逸脱防止法の効率化 (データ工学)
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア(アプリケーション2,FPGA応用及び一般)
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア(アプリケーション2,FPGA応用及び一般)
- 信号経路に対するタイミング制約を考慮した回路分割手法
- タイミング制約を考慮した分割手法
- RC-003 高速なテキスト検索のための近似正規表現マッチングアルゴリズムとそのFPGA実装(C分野:ハードウェア・アーキテクチャ,査読付き論文)
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア(アプリケーション2,FPGA応用及び一般)
- 非公開データベース間における機密性の高い情報共有の検討
- NIDS専用正規表現マッチングマシンの構成とそのFPGA実装(アプリケーション2,FPGA応用及び一般)
- NIDS専用正規表現マッチングマシンの構成とそのFPGA実装(アプリケーション2,FPGA応用及び一般)
- NIDS専用正規表現マッチングマシンの構成とそのFPGA実装(アプリケーション2,FPGA応用及び一般)
- パターンを実行時に設定可能な正規表現ストリングマッチングマシンとFPGAによる実現(FPGAの応用)
- 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用)
- パターンを実行時に設定可能な正規表現ストリングマッチングマシンとFPGAによる実現(FPGAの応用)
- 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用)
- コールアドミッションアルゴリズムに適した経路探索法の提案
- A-1-30 コールアドミッションに適した効率的な経路探索法の提案(A-1.回路とシステム,一般講演)
- クラスタリング結果の特徴抽出を用いる高次元データの対話的クラスタリング
- FlexDice: 高次元な大規模データセットに対する高速クラスタリング手法
- 多次元データ空間に対する高速クラスタリングと実験的評価
- 大規模論理回路分割に関する一手法
- 大規模論理回路分割に関する一手法
- システムオンシリコン時代を支えるCAD技術(新しい知能化へ向けたLSIシステム技術)
- パターンを実行時に設定可能な正規表現ストリングマッチングマシンとFPGAによる実現(FPGAの応用)
- 最小支配集合問題に対する分枝限定アルゴリズムとFPGA上でのハードウェアによる実現(グラフ, ペトリ, ニューラルネット及び一般)
- 最小支配集合問題に対する分枝限定アルゴリズムとFPGA上でのハードウェアによる実現(グラフ, ペトリ, ニューラルネット及び一般)
- 共有変数へのアクセス競合の回避を目的とする同時実行可能で拡張可能なハッシュアルゴリズムの改良
- タイミングを考慮したフロアプランニングと動作合成の統合化の一手法
- タイミングを考慮したフロアプランニングと動作合成の統合化の一手法
- 交差手法の適応的選択機能を組み込んだ遺伝的アルゴリズムのLSIチップによる実現
- 遺伝的アルゴリズムにおける個体のエリート度に基づく遺伝オペレータとGAパラメータの適応的調整
- 遺伝的アルゴリズムにおける交差手法の適応的選択の一手法
- 適応的交差選択手法を組み込んだ遺伝的アルゴリズムのLSIチップによる実現とその評価
- 個体の優劣度に基づいて適応的にパラメータを調整する遺伝的アルゴリズム
- 遺伝的アルゴリズムにおける個体の優劣度に基づく適応的パラメータ値設定手法
- パラメータの適応的調整を伴う遺伝的アルゴリズムのハードウェア化
- スタイナ木生成問題に対する遺伝的アルゴリズムを統合的に開発するフレームワーク
- スタイナ木生成問題に対する遺伝的アルゴリズムを統合的に開発するフレームワーク
- 近似正規表現マッチングのためのシストリックアルゴリズムとそのFPGA実装
- 2次割当問題に対するシストリックアルゴリズムに基づくハードウェア解法(FPGAの応用)
- 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現(FPGAとその応用及び一般)
- 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現(FPGAとその応用及び一般)
- 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現(FPGAとその応用及び一般)
- 2次割当問題に対するタブー探索法に基づくFPGAを用いたハードウェア解法(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現(FPGAとその応用及び一般)
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現
- LSIフロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとそのPCクラスタ上での実現
- C_006 2次割当問題に対するタブー探索法に基づくハードウェア解法(C分野:ハードウェア)
- タイミング制約を伴う概略配線問題に対するバッファ挿入と配線幅の選択を許したスタイナ木構成手法
- タイミング制約を考慮した概略配線手法
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア
- LC-002 最小支配集合問題を解くインスタンス依存ハードウェア解法(C分野:アーキテクチャ・ハードウェア)
- グラフ最小節点被覆問題に対するFPGAを用いたインスタンス依存ハードウェア解法(応用1, FRGAとその応用及び一般)
- グラフ最小節点被覆問題に対するFPGAを用いたインスタンス依存ハードウェア解法(応用1, FRGAとその応用及び一般)
- グラフ最小節点被覆問題に対するFPGAを用いたインスタンス依存ハードウェア解法(応用1, FRGAとその応用及び一般)
- 最大クリークを求めるデータ依存ハードウェアアルゴリズムの実装と評価(FPGAとその応用及び一般)
- 最大クリークを求めるデータ依存ハードウェアアルゴリズムの実装と評価(FPGAとその応用及び一般)
- 最大クリークを求めるデータ依存ハードウェアアルゴリズムの実装と評価(FPGAとその応用及び一般)
- 量指定子による文字列の繰り返しに対応した正規表現マッチング専用ハードウェア
- 近似正規表現マッチングのためのシストリックアルゴリズムとそのFPGA実装(FIT推薦論文)(計算機システム)
- スタンダードセルレイアウト設計におけるセル配置改良をともなうタイミングドリブン端子割当てアルゴリズム (電子システムの設計技術と設計自動化)
- 匿名データ収集におけるプロトコルからの逸脱防止法の効率化(一般(ストリーム・匿名性・省電力),e-ScienceとData Intensive Science及び一般)
- データを極小歪曲しk-匿名性を保持したデータに変換するプライバシー保護アルゴリズム
- 共有情報を用いた同時実行可能なゼロ知識識認証について(セッション1)
- 適応的遺伝的アルゴリズムに基づくVLSIフロアプランニングの手法(システムLSIの設計技術と設計自動化)
- バッファ挿入を考慮した概略配線とフロアプランを同時に求めるフロアプランニング手法
- バッファ挿入を考慮した概略配線とフロアプランを同時に求めるフロアプランニング手法
- 適応的遺伝的アルゴリズムとシーケンスペアに基づくフロアプランニング手法
- 適応的遺伝的アルゴリズムとシーケンスペアに基づくフロアプランニング手法
- 遺伝的アルゴリズムの高速実行に適した命令セットを持つ専用RISCプロセッサDLX-GA(計算機アーキテクチャ)(コラボレーションアートとネットワークエンターテイメント)
- 遺伝パラメータの適応的調整機能をもつ並列遺伝的アルゴリズム
- 遺伝パラメータの適応的調整機能をもつ並列遺伝的アルゴリズム
- VLSIレイアウト設計における配線幅調整とバッファ挿入を考慮した直交スタイナ木を生成する遺伝的アルゴリズム
- 配線長を考慮したクラスタリングに基づくスタンダードセル階層配置手法(VLSIの設計/検証/テスト及び一般 配置配線)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 配線長を考慮したクラスタリングに基づくスタンダードセル階層配置手法(VLSIの設計/検証/テスト及び一般 配置配線)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 遺伝的アルゴリズムの高速実行に適した命令セットを持つRISCプロセッサDLX-GA
- ULSIフロアプランニングにおける階層的バッファブロックプランニング手法
- ULSIフロアプランニングにおける階層的バッファブロックプランニング手法
- ULSI多層配線に対するバッファ挿入と配線幅を考慮したタイミングドリブン階層概略配線手法
- ULSI多層配線に対するバッファ挿入と配線幅を考慮したタイミングドリブン階層概略配線手法
- 大規模回路に対するタイミングドリブン多層概略配線の一手法
- 遺伝的プログラミングのための専用ハードウェアと専用コンピュータシステムの開発
- 遺伝的プログラミングのための専用ハードウェアと専用コンピュータシステムの開発