分枝限定法の並列化と並列計算機での実行
スポンサーリンク
概要
- 論文の詳細を見る
分枝限定法はNP困難な組み合わせ最適化問題を解く有効な手段として知られている.ナップサック問題を題材として,分枝限定法の並列アルゴリズムを提案する.部分問題の分割や問題送信順序を工夫した.MIMD型の並列計算機iPSC/860(8PE)及びKSR1(32PE)上にそのアルゴリズムを適用して実行した.iPSC/860(8PE)上のプログラムで平均倍率(100問題)は7.25倍となった.KSR1上のプログラムの平均倍率(100問題)は2PEで2.04倍,32PEで15.48倍となった.その結果並列化アルゴリズムの有効性が確かめられた.
- 社団法人電子情報通信学会の論文
- 1995-04-28
著者
関連論文
- 拡張されたヒープ領域管理機能をもつPASCAL処理系ELPH
- PASCALシンボリック・デバッガの作成
- 論理合成された回路に対するLFSRのテスト長
- 1MビットSRAMの故障解析
- 分枝限定法の並列化と並列計算機での実行
- 分枝限定法の並列化と並列計算機での実行
- 1MビットSRAMの故障解析
- 検出困難故障用パターンを生成するLFSRのテスト長について
- ナップサック問題における分枝限定法の並列化
- 多重MISRの構成とそのエイリアス確率に関する二,三の考察
- ビット毎に誤り率が異なるMISRのエイリアス確率と完全重み分布
- 多重MISRの構成とそのエイリアス確率に関する二、三の考察
- ビット毎に誤り率が異なるMISRのエイリアス確率と完全重み分布
- 3. 符合理論の計算機システム、ディジタル信号処理への応用 ( 情報理論の計算機システムへの応用)
- 特集「情報理論の計算機システムへの応用」の編集にあたって
- 並列計算機に適した格子らせんネットワークの提案
- 64PE並列計算機"発葉"における故障発生実験とその対策
- 超並列計算機MP-1を用いたVLSI組込み自己テストのエイリアス確率の計算
- マスクROMの故障解析とそのシグネチャ回路設計への応用
- H8/330並列システムにおけるフォールトトレランスの実験
- 放送+挙手アーキテクチャとH8/330並列システムでの実験
- 超並列計算機MP-1を用いたナップサック問題解法の試み
- キャンパスネットワークにおける障害 : 落雷
- 千葉大学計算機ネットワークにおける障害 : ネットワーク層
- ミニコンによるある連想記憶システムの作成について
- マスクROMのBISTにおけるエイリアス誤りの一実験
- アーキテクチャ・シミュレータN.2を用いた並列マシンのシミュレーションの試み(マイクロ・プロセッサ,ニューラルネットワーク)
- アーキテクチャ・シミュレータN.2を用いた並列マシンのシミュレーションの試み
- 単一誤り訂正リードソロモン符号を用いた自己修復可能なマスクROM構成法
- MasParを用いたエイリアス確率の計算-改良
- 16PE並列計算機「樹葉」における最大値問題のサイクル数による評価
- 階層情報の3次元視覚化に関する評価
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリングアルゴリズム
- 音声メニュー同時提示方法の提案と評価
- 動的なパラメータ指定機能をもつあるデバッグシステム
- 平衡2分探索木に対する並列オンライン操作
- 3. ハードウェアアルゴリズムの設計法 3.2 ハードウェアアルゴリズムの記述と検証 (VLSI向きハードウェアアルゴリズム)
- 2. ハードウェアアルゴリズムの基礎理論 2.3 VLSIモデルと面積複雑度 (VLSI向きハードウェアアルゴリズム)
- パイプライン化による平衡2分探索木に対する並列操作
- システム記述用言語Cのポータブルコンパイラの作成