パイプライン化による平衡2分探索木に対する並列操作
スポンサーリンク
概要
- 論文の詳細を見る
今までパイプライン化が難しいとされてきた平衡2分探索木の要素の削除アルゴリズム,および2分探索木の平衡化アルゴリズムを提案する.削除アルゴリズムでは,各頂点にデータが有効であるかどうかを示すフラグを設け,そのフラグを操作する.このフラグで有効なデータのみの通りがけ順の値を計算し,この値を用いて平衡化を行ない.この削除と平衡化の手法を用いて,頂点数nの平衡2分探索木に対する挿入,検索,および削除からなる長さO(logn)の任意の操作系列をパイプライン化して並列実行し,その後に2分探索木の平衡化を行ない平衡2分探索木を得るまでを,EREW PRAMにおいい時間O(logn),命令数O(n)で実行できる.
- 一般社団法人電子情報通信学会の論文
- 1994-11-18
著者
関連論文
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(夏のデータベースワークショップ2007(データ工学,一般))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(検索エンジン応用,夏のデータベースワークショップ2007(データ工学,一般))
- Webを対象としたロボット型住所関連情報検索システムの開発(Web検索,データ工学論文)
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- R3Qによる進化型計算の中粒度Gridスケジューリング(グリッド)
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 術中における対話的な医用画像処理のための遠隔並列計算環境の構築 : 手術支援グリッドの実現に向けて
- 拡張されたヒープ領域管理機能をもつPASCAL処理系ELPH
- PASCALシンボリック・デバッガの作成
- 分枝限定法の並列化と並列計算機での実行
- 分枝限定法の並列化と並列計算機での実行
- 進化計算のためのグリッドコンピューティング
- 並列再帰の実行方式をプログラマが指定可能なコンパイラの評価
- 分割統治法アルゴリズムの効率的な並列化手法とそのコンパイラの実装
- 分割統治法プログラムを並列実行するコンパイル手法の提案と評価
- λコンピューティング環境におけるOpenMPアプリケーションによる共有メモリシステムの評価
- λコンピューティング環境におけるOpenMPライブラリの設計と実装(フォトニックネットワークシステム,光ルーチング,ブロードバンドアプリケーション,一般)
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- デスクトップグリッド環境でのマルチジョブスケジューリングにおけるジョブの追い越しを防ぐジョブ優先度制御
- 余剰計算力を用いるグリッドのジョブスケジューリングにおける優先度制御の一手法(セッション2)
- A_002 企業イントラグリッドでのジョブ割当てアルゴリズムの比較評価(A分野:モデル・アルゴリズム・プログラミング)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップDBWS2005)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップ2005)
- グリッド上でのパラメータ・スウィープ計算を対象として消費余剰計算力の最小化をねらった動的タスクスケジューリングのための近似アルゴリズム(シンポジウム)
- タスクスケジューリングを用いた並列プログラム生成におけるタスク粒度の調整とその評価
- タスク複製率とプロセッサ***率に着目したBSPスケジュール生成手法の提案
- 検索可能な樹状ヒストリ機能を備えたホワイトボードシステム"S.W.ボード"の提案と実装
- 会合における備忘録をもとに一次記録を検索参照する会合情報記録検索システムReSPoM(:知識と情報の共有)
- 検索可能な樹状ヒストリ機能を備えたホワイトボ-ドシステム"S.W.ボ-ド"の提案と実装
- 会合記録の関連性に着目した会合記録検索支援システムの実装
- 会合における情報の関連性を記録するためのインタフェースの検討と評価
- 会合における情報の関連性を記録するためのインタフェースの検討と評価
- MI-Cluster : 術中医用画像処理を実現するPCクラスタシステム
- ミニコンによるある連想記憶システムの作成について
- 共有メモリ式SIMD型並列アルゴリズム解析ツール
- プロセッサグループの動的分割による並列再帰プログラムの実現手法
- アニメーションを用いた並列アルゴリズム学習支援環境の構築
- 階層情報の3次元視覚化に関する評価
- スケーラビリティのあるWWW並列全文検索システム構築法の提案と評価
- 並列型全文検索システム構築のための手法の提案とその評価
- スケーラビリティを考慮した並列再帰の実行方式の提案と評価
- 計算グリッド上でのパラメータ・スウィープ計算を対象とした性能保証のある動的タスクスケジューリング
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信の一括化に適したタスクスケジューリングアルゴリズム
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリングアルゴリズム
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- 分散メモリ型並列計算機の通信特性を考慮したスケジューリングアルゴリズムの開発とその評価
- JPEGアルゴリズムにブロック比較法を適用した画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- 音声メニュー同時提示方法の提案と評価
- 動的なパラメータ指定機能をもつあるデバッグシステム
- 進化戦略のためのグリッド計算に関する一考察(進化・学習とロボティクス3)
- 分散メモリ型並列計算機による高解像度ボリュームレンダリング(バイオメトリクスシステムおよび一般)
- グリッド環境における独立粗粒度タスク集合の動的スケジューリングアルゴリズムの性能評価
- タスクグラフ分割を用いた並列処理によるスケジューリングアルゴリズムBCSHの大規模細粒度グラフへの適用
- ビデオアーカイブを利用した学習を支援するシステムの提案
- ビデオアーカイブを利用した学習を支援するシステムの提案
- SPMD プログラムを生成する Work-Time C 処理系の実現
- 並列プログラムの性能改善支援機能を持つ性能解析システム : Gordini(並列処理)
- 並列プログラムの改善支援機能を持つ性能解析システムの開発
- 1対1プロセッサ間通信の一括化を考慮したタスクスケジューリングアルゴリズム
- 一対一プロセッサ間通信の一括化を考慮したタスクスケジューリングアルゴリズム
- 最小値関数を用いて適合度を算出するNRA検索アルゴリズムの改善
- 最小値関数により適合度を算出するNRA検索アルゴリズムの改善
- グリッド環境における計算ノードの故障を考慮した独立タスクのスケジューリングアルゴリズム
- MPI-PreDebugger : 通信依存解析に基づくメッセージ通信並列プログラム向けデバッグ支援ツール
- LogGPS : メッセージ通信プロトコルの切替えを考慮した高水準通信ライブラリ向けの並列計算モデル
- 平衡2分探索木に対する並列オンライン操作
- 3. ハードウェアアルゴリズムの設計法 3.2 ハードウェアアルゴリズムの記述と検証 (VLSI向きハードウェアアルゴリズム)
- 2. ハードウェアアルゴリズムの基礎理論 2.3 VLSIモデルと面積複雑度 (VLSI向きハードウェアアルゴリズム)
- パイプライン化による平衡2分探索木に対する並列操作
- システム記述用言語Cのポータブルコンパイラの作成