並列部分問題探索法による組合せ最適化問題の並列処理
スポンサーリンク
概要
- 論文の詳細を見る
本稿では, 最良優先探索を用いた分枝限定法の並列化手法として並列部分問題探索法(PSS:Parallel Subproblem Search)を新たに提案する. また, 静的に負荷分散を行う手法を提案する. PSSにこの負荷分散手法を組み合わせることでさらに処理時間を短縮することか可能となる. 実際にナップザック問題を複数のインスタンスを与えて解いた結果, 1プロセッサに比べて負荷分散を行った64プロセッサで約10〜80倍の速度向上が実測された.
- 一般社団法人情報処理学会の論文
- 1996-03-04
著者
-
安浦 寛人
九州大学大学院システム情報科学研究科情報工学専攻
-
吉松 敬仁郎
九州大学大学院総合理工学研究科
-
吉松 敬仁郎
九州大学大学院総合理工学研究科情報システム学専攻
-
安浦 寛人
九州大学大学院 システム情報科学研究院
関連論文
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- 12.社会システムを支えるディペンダブルコンピューティング(時代をひらく電子情報通信技術-技術がもたらした変革,そして更なる飛躍-)
- 入力依存の遅延ばらつきを利用するDVSシステムにおける性能およびエリアオーバーヘッドの改善検討(低消費電力,集積回路とアーキテクチャの協創〜どう繋ぐ?どう使う?マルチコア〜)
- 緊密な産学連携に基づく自律的なICT人材育成の実践(情報システム教育コンテスト(3))
- Non-uniform Selective Way Cacheの動的制御による組込みプロセッサの省エネルギー化(消費電力,組込技術とネットワークに関するワークショップETNET2009)
- Non-uniform Selective Way Cacheの動的制御による組込みプロセッサの省エネルギー化(省エネ,組込技術とネットワークに関するワークショップETNET2009)
- 6U-6 ウェーブレットに基づく音声認証システムの精度向上にむけて(ネットワーク応用,学生セッション,ネットワーク)
- C-12-9 ゲーテッドフリップフロップの多ビット結合によるレジスタの低電力化(C-12.集積回路,一般セッション)
- RFIDタグを用いた安全で効率の良いデジタルネーミング社会について
- 1A1-K06 ラジコンカーを用いた計算機の動作原理教育
- 製造後にタイミング補正可能なオンチップバスアーキテクチャ(回路方式,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 90nm CMOS回路における遅延・電力ばらつきのゲート段数およびゲート幅依存性に関する考察(耐ノイズ・ばらつき設計(1),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 90nmCMOS回路における遅延および電力ばらつきの実測と解析(演算回路・ばらつきの測定,システム設計及び一般)
- シングルサイクルアクセス可能な二階層キャッシュアーキテクチャ(消費電力,組込技術とネットワークに関するワークショップETNET2009)
- シングルサイクルアクセス可能な二階層キャッシュアーキテクチャ(省エネ,組込技術とネットワークに関するワークショップETNET2009)
- Analysis of effects of input arrival time variations on on-chip bus power consumption (VLSI設計技術)
- Analysis of effects of input arrival time variations on on-chip bus power consumption (システムLSI設計技術)
- AI-1-6 ディペンダブルVLSI設計技術への挑戦(AI-1.デイベンダブルVLSIに向けて,依頼シンポジウム,ソサイエティ企画)
- ハッシュを用いたID照合における計算時間についての考察(セッション2)
- パネル討論 : システムオンシリコン時代に向けてどんなCADを作るべきか?
- パネル討論 : システムオンシリコン時代に向けてどんなCADを作るべきか?
- VLSI 設計教育の現状と将来
- タイミングエラーの予報を目的とするカナリアFFの挿入位置限定(ディペンダブル設計,デザインガイア2008-VLSI設計の新しい大地)
- タイミングエラーの予報を目的とするカナリアFFの挿入位置限定(ディペンダブル設計,デザインガイア2008-VLSI設計の新しい大地)
- コデザイン環境におけるメタ記述からハードウェア/ソフトウェアコジェネレーション
- パフォーマンスを考慮したデータパス幅の最適化手法
- コデザイン環境におけるメタ記述からハードウェア/ソフトウェアコジェネレーション
- パフォーマンスを考慮したデータパス幅の最適化手法
- コデザイン環境におけるメタ記述からハードウェア/ソフトウェアコジェネレーション
- パフォーマンスを考慮したデータパス幅の最適化手法
- 出力品質を考慮した変数ビット幅最適化手法
- MPEG-2 AACデコーダ専用の組み込みシステムLSIの開発
- MPEG-2 AACデコーダ専用の組み込みシステムLSIの開発
- VDEC向けスタンダードセルライブラリの評価
- VDEC向けスタンダードセルライブラリの評価
- VDEC向けスタンダードセルライブラリの評価
- RijndaelのLSI実装における低消費電力化手法の提案
- RijndaelのLSI実験における低消費電力化手法の提案
- A-7-20 パストランジスタを用いたDES S-boxの実装評価
- 実行不能パスを考慮したHDL記述のプログラムスライシング・アルゴリズム
- 低消費電力化を目的とした Gated-Clock によるビット幅可変方式
- 教育用マイクロプロセッサ QP-DLX の開発 : LSIテスタを用いたテスト及び評価
- プログラムスライシングと部分評価を用いたVHDL記述の機能部品作成
- 識別可能な多値レベルを考慮したニューロンMOS論理素子設計手法
- 識別可能な多値レベルを考慮したニューロンM0S論理素子設計手法
- 新機能デバイスを利用した高集積システム設計技術
- VHDLおけるプログラムスライシングとプロセッサ記述への適用
- ニューロンMOSトランジスタを用いた基本論理素子の設計手法
- デルタ遅延に基づくVHDL記述のスライシングアルゴリズム
- デルタ遅延に基づくVHDL記述のスライシングアルゴリズム
- UDL/IによるVLSI設計
- グループ化された仕様記述に基づくパイプライン・プロセッサの設計検証
- NeuMOSを用いたパラレルカウンタ型乗算器
- ニュｰロンMOSトランジスタを用いたパラレルカウンタ型乗算器の設計
- On the Computational Power of Binary Decision Diagram with Redundant Variables
- 教育用32ビットマイクロプロセッサQP-DLXの設計における設計検証
- 情報社会に生きる小中学生のための計算機の動作原理の教育
- フラッシュ・メモリを主記憶とするシステムのためのメモリ・アーキテクチャの検討
- フラッシュ・メモリを主記憶とするシステムのためのメモリ・アーキテクチャの検討
- フラッシュ・メモリを主記憶とするシステムのためのメモリ・アーキテクチャの検討
- マイクロプロセッサにおけるアーキテクチャレベルの低消費電力化手法
- ハードウェア/ソフトウェア・コデザインのためのソフトコア・プロセッサの検討
- VHDLによるソフトコア・プロセッサの設計
- 特定用途向け集積システム最適化手法
- システム・オン・シリコン時代の特定用途向けシステム設計手法
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- 90nm CMOS回路における遅延・電力ばらつきのゲート段数およびゲート幅依存性に関する考察(耐ノイズ・ばらつき設計(1),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 90nmCMOS回路における遅延および電力ばらつきの実測と解析(演算回路・ばらつきの測定,システム設計及び一般)
- システムLSI設計人材養成実践プログラムQUBEにおけるETSSの活用
- 通信品質を考慮したディジタル無線通信システムの低消費エネルギー化の検討(デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 通信品質を考慮したディジタル無線通信システムの低消費エネルギー化の検討
- CMOSプロセスにおけるゲート遅延ばらつき測定回路の提案(VLSI回路, デバイス技術(高速・低電圧・低消費電力))
- CMOSプロセスにおけるゲート遅延ばらつき測定回路の提案(VLSI回路, デバイス技術(高速・低電圧・低消費電力))
- アクティブビットを考慮した低電力データパス設計手法
- アクティブビットを考慮したバスの低電力化手法
- アクティブビットを考慮したバスの低電力化手法
- マルチタスク組込みアプリケーションの低消費エネルギー化のためのメモリ管理技術(消費電力1,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 製造後にタイミング補正可能なオンチップバスアーキテクチャ(回路方式,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- マルチタスク組込みアプリケーションの低消費エネルギー化のためのメモリ管理技術(消費電力1,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 製造後にタイミング補正可能なオンチップバスアーキテクチャ(回路方式,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- マルチタスク組込みアプリケーションの低消費エネルギー化のためのメモリ管理技術(消費電力1,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- CMOS回路におけるタイミング歩留り最大化のためのゲートサイジング手法の提案(耐ノイズ・ばらつき設計(1),システムオンシリコン設計技術並びにこれを活用したVLSI)
- CMOS回路におけるタイミング歩留り最大化のためのゲートサイジング手法の提案(耐ノイズ・ばらつき設計(1),システムオンシリコン設計技術並びにこれを活用したVLSI)
- Non-uniform Selective Way Cacheの動的制御による組込みプロセッサの省エネルギー化(消費電力,組込技術とネットワークに関するワークショップETNET2009)
- Non-uniform Selective Way Cacheの動的制御による組込みプロセッサの省エネルギー化(省エネ,組込技術とネットワークに関するワークショップETNET2009)
- スキャンべース攻撃とその防御法に対する定量的なセキュリティ評価(ディペンダブル設計,デザインガイア2009-VLSI設計の新しい大地)
- スキャンベース攻撃とその防御法に対する定量的なセキュリティ評価(ディペンダブル設計,デザインガイア2009-VLSI設計の新しい大地-)
- 算術演算器を含む回路に対する高速なソフトエラー率評価手法(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- 算術演算器を含む回路に対する高速なソフトエラー率評価手法(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- シングルサイクルアクセス可能な二階層キャッシュアーキテクチャ(消費電力,組込技術とネットワークに関するワークショップETNET2009)
- シングルサイクルアクセス可能な二階層キャッシュアーキテクチャ(省エネ,組込技術とネットワークに関するワークショップETNET2009)
- スキャンパス攻撃を考慮した暗号LSIのテスタビリティ評価(フォールトセキュア・セキュリティ・2線2相回路のテスト,VLSI設計とテスト及び一般)
- 2.応用プログラム (重点領域研究 : 超並列原理に基づく情報処理基本体系)
- 大規模な産学連携による高度ICT人材育成に向けての取り組み
- RC-011 仮想キューによる高性能ハードウエアRTOSの実現(C分野:ハードウェア・アーキテクチャ,査読付き論文)
- LSIテスタを用いたLSIの信号遅延の測定
- 機能情報抽出を用いた CPU の動作検証
- 同期式順序回路からの動作記述の抽出
- 端子位置を考慮した論理多段化の一手法およびその評価
- VDEC用スタンダードセルライブラリの開発