PCクラスタを用いたN-queens問題の求解
スポンサーリンク
概要
- 論文の詳細を見る
N-queensは,互いに攻撃を行わないようなIV個のクイーンをN×Nのボードに配置する解の冊数を求める問題である.我々は,既存のプログラムと比較して,逐次プログラムとして11%から18%の高速化を達成するプログラムを作成した.また,MPIを用いて並列化を行い,PCクラスタを用いて計算することで,世界で初めて,24-queensの解を得た.この経験の主な知見は以下のとおり,(1)メモリ参照,制御構造等の最適化により,Semorsのプログラムと比較して11〜18%の高速化を達成する.2)並列化には,マスタ・ワーカ方式が有効となる.(3) Pentium4のもつHyper-Threadingを利用することで,利用しない場合と比較して,30%の高速化を達成する.(4)実問題の求解には,システム全体として高速に動作するように配慮する必要がある.
- 2004-12-01
著者
-
本多 弘樹
電気通信大学大学院情報システム学研究科
-
片桐 孝洋
電気通信大学 大学院情報システム学研究科
-
吉瀬 謙二
電気通信大学大学院情報システム学研究科
-
弓場 敏嗣
電気通信大学
-
弓場敏嗣
電気通信大学
-
本多 弘樹
電気通信大学 大学院情報システム学研究科
関連論文
- OMPCUDA : GPU向けOpenMPの実装(高性能計算)
- POSIXスレッドを用いたCellプロセッサ向けAPIの提案(マルチプロセッサ)
- コードの性能可搬性を提供するSIMD向け共通記述方式(コンパイラ)
- F-Omega : サーバ稼動状況に適応するGridRPCアプリケーションの開発・実行フレームワーク(シミュレーション・エミュレーション,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 高性能GridRPCアプリケーションの開発環境(グリッド)
- 高性能 GridRPC アプリケーションの開発環境
- コードの性能可搬性を提供するSIMD向け共通記述方式(ARC-7:性能予測,2006年並列/分散/強調処理に関する『高知』サマー・ワークショップ(SWoPP 高知2006))
- GridRPCアプリケーションポータルの構築・運用を支援するポートレット(並列処理システム)
- 高性能GridRPCアプリケーションの開発環境(グリッドRPC)
- Relis-G : 計算グリッドのための遠隔ライブラリインストール機構(グリッド)
- GridRPCシステムにおけるリモートプログラムシッピング機構(グリッド)
- GridRPCシステムにおけるリモートプログラムシッピング機構
- 相乗り通信を利用したソフトウェアDSMの通信回数削減手法(ARC-9:メモリ管理,2006年並列/分散/強調処理に関する『高知』サマー・ワークショップ(SWoPP 高知2006))
- ネットワークサービス提供に向けた汎用システムにおけるソフトウェア修正方式(交換)
- SMPクラスタ上でのMPIとOpenMPを用いたマクロデータフロー処理(HPC-3 : クラスタソフトウェア)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- iPat/OMPでのソースコードレベル最適化における試行錯誤支援ツール(コンパイラ及びツール,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- ソフトウェア自動チューニングにおける標本点逐次追加型性能パラメータ推定法の疎行列計算への適用(数値計算)
- Alphaアーキテクチャ用COINSマシン記述の実装とGCCとの比較
- ソフトウェア自動チューニングにおける標本点逐次追加型性能パラメータ推定法(数値計算,数理計画法)
- S-DSMシステムにおけるページ要求時の受信通知を削減する方式(ソフトウェア分散共有メモリ)
- タイムワープ法並列離散事象シミュレーションにおけるロールバックの雪崩現象
- 並列離散事象シミュレーションにおける適応的同期プロトコルの評価
- メッセージ通信型GPGPUプログラミング(プログラミング環境,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 非均一分散環境における並列性の仮想化(Inventive and Creative Architecture特別セッションII)
- 既存の並列化手法を用いたGPGPUプログラミングの提案(Inventive and Creative Architecture特別セッションI)
- コンパイラ研究の明日 : アーキテクチャの進歩とともに(パネル討論会, SHINING 2006 「アーキテクチャとコンパイラの協調および一般」)
- SMPクラスタ上でのタスク粒度を考慮した階層型粗粒度並列処理(並列処理手法, SHINING 2006 「アーキテクチャとコンパイラの協調および一般」)
- 分散インプリサイス計算における負荷の状態近似に基づく適応的なタスク移送方式
- F-Omega : サーバ稼動状況に適応するGridRPCアプリケーションの開発・実行フレームワーク(シミュレーション・エミュレーション,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- GPUコンピューティング向け中間言語の研究
- マルチクラスタ向けソフトウェア分散共有メモリの提案
- ホームベースソフトウェア分散共有メモリ上でMigratory Accessを効率良く処理する権限委譲プロトコル(ソフトウェア分散共有メモリとその応用)
- プログラマの意図により複数のキャッシュコヒーレンスプロトコルの利用を可能とするソフトウェア分散共有メモリ
- キャリアグレードOSのためのディスクWrite処理方式
- GPU向けソフトウェアキャッシュ機構の実装と評価
- GPU向けソフトウェアキャッシュ機構の実装と評価
- 細粒度通信機構を持つ並列計算機EM-Xにおける共有メモリプログラムの効率的実行
- 2000-ARC-139-15 EM-XとMD Oneを統合化した粒子シミュレーション用並列計算機プロトタイプの構築
- 並列計算機EM-Xの細粒度通信機構を用いた共有メモリベンチマークの実行
- 並列計算機EM-Xの細粒度通信機構を用いた共有メモリベンチマークの実行
- 並列計算機用要素プロセッサの細粒度同期機構におけるキャッシュ方式の検討
- 細粒度並列計算機EM-Xにおけるキャシュメモリアーキテクチャ
- GridRPCにおける計算ノードの動的な追加・切替を可能とする枠組
- F-Omega:グリッドアプリケーションの自動サーバ切替えの枠組み
- メッセージ通信型GPGPUプログラミング(プログラミング環境,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- iPat/OMPでのソースコードレベル最適化における試行錯誤支援ツール(コンパイラ及びツール,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- Bimode-Plus分岐予測器の提案(プロセッサアーキテクチャ)
- 対話型OpenMPプログラム作成支援ツールの開発(ARC-9:ハイパフォーマンスコンピューティング)(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- ユーザ知識を活用するソフトウエア自動チューニングについて(EVA-2 : 性能改善)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- GridRPC における計算ノードの動的な追加・切替を可能とする枠組
- GPU向けソフトウェアキャッシュ機構の実装と評価
- GPU向けソフトウェアキャッシュ機構の実装と評価
- IPネットワークにおける待時式帯域予約通信方式の評価 (インターネットの新しいサービスとその基盤技術, 及び一般)
- 帯域予約開始までの待ち時間を考慮したRSVPの提案(インターネットアーキテクチャ技術論文特集)
- RAO-SS : Autopilotを用いた疎行列ソルバにおける実行時自動チューニング機構(数値計算アルゴリズム(1), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- RAO-SS : Autopilot を用いた疎行列ソルバにおける実行時自動チューニング機構
- D-3-9 Autopilotを用いた疎行列ソルバにおける実行時自動チューニング機構の設計(D-3. ソフトウェアサイエンス)
- 階層並列構造と演算チェインニング機構を持つ : 粒子シミュレーション用並列計算機の提案
- タイムワープ法並列離散事象シミュレーションにおけるロールバックの雪崩現象
- タイムワープ法並列離散事象シミュレーションにおけるロールバックの雪崩現象
- 並列離散事象シミュレーションにおける適応的同期プロトコルの評価
- SimCore/Alpha Functional Simulatorの設計と実装(VLSI設計支援システム, システム開発論文)
- Doacrossループのsandglass型並列化方法とその評価 (並列処理)
- データの分割配置を考慮したsandglass型並列化手法の有効性について
- データの分割配置を考慮したsandglass型並列化手法の有効性について
- データの分割配置を考慮したsandglass型並列化手法の有効性について
- Doacrossループのsandglass型並列化手法の有効性について
- Doacrossループにおける並列粒度調整方法の検討
- 分散メモリシステム上でのマクロデータフロー処理のためのデータ到達条件
- 分散メモリシステム上でのマクロデータフロー処理の実現
- D-6-6 分散メモリシステム上での粗粒度並列処理のためのデータ到達条件
- 分散メモリシステム上でのマクロデータフロー処理の実現
- 機械学習により抽出されたアプリケーションの特徴を利用したタスク配置の検討
- ヘテロジニアス計算機クラスタにおける省エネルギー化タスクスケジューリング手法
- S-DSMシステムの受信通知オーバヘッドを削減する方式(システムII)(リコンフィギャラブルシステムにおける設計技術及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- HxABCLibScript:非均質計算機向け自動チューニング記述言語拡張
- PCクラスタを用いたN-queens問題の求解
- O-011 qn24b: N-queensの解を計算するベンチマークプログラム(O.情報システム)
- 走行時パワーゲーティングにおけるスラック解析を用いた動的命令スケジューリングの検討
- 2000-DSM-18-1 ワールドワイドなインターラクティブシステムのためのHTTPコネクション型RPCの検討
- 可換/結合法則が成立する操作を対象としたログベース更新型分散共有メモリ
- データ再分散を行う並列Gram-Schmidt再直交化(数値計算)
- Peer-to-Peerシステムにおける共有ファイルの最適配置手法の提案
- ソフトウェア分散共有メモリを用いたマクロデータフロー処理(並列処理)
- PCクラスタ上でのマクロデータフロー処理の評価(スケジューリング)
- D-6-9 分散メモリ型並列計算機上での粗粒度並列処理におけるデータローカライゼーション手法(D-6. コンピュータシステム)
- D-6-7 0MJ : JIAJIA向けのOpenMPコンパイラ(D-6. コンピュータシステム)
- D-3-10 SMPマシン上でのBLASライブラリ用自動チューニング機構の設計と実装(D-3. ソフトウェアサイエンス)
- 粗粒度並列化コンパイラCoCoの開発(並列処理のためのシステム)
- キャッシュラインの時間情報を利用するTime Based Filterの提案
- RAO-SS : Autopilotを用いた疎行列ソルバにおける実行時自動チューニング機構(数値計算アルゴリズム(1), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- MPI埋め込み可能GPUプログラミングフレームワーク適用可能性の評価(並列処理支援,2011年並列/分散/協調処理に関する『鹿児島』サマー・ワークショップ(SWoPP鹿児島2011))
- マルチコア・プロセッサ向けのヘルパースレッドによるキャッシュ制御支援手法の検討
- 複数GPU向けのCUDAコードを生成するOpenMP処理系の提案
- ログ情報に基づくGrid上でのMPIアプリケーションにおけるタスク割り当て手法の提案とその評価
- Alfred V. Aho and Jeffrey D. Ullman : Principles of Compiler Design, Addison Wesley (1977)(20世紀の名著名論)
- SimCore/Alpha Functional Simulatorの設計と評価(プロセッサアーキテクチャ)
- Bimode-Plus分岐予測器の提案(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(CPSY-3予想とスケジューリング)
- FIBER : 汎用的な自動チューニング機能の付加を支援するソフトウエア構成方式(プロセッサシステムとプログラミング環境)
- FLAT:MPIを埋め込み可能なGPUプログラミングフレームワーク