恥ずかしいほど似ている

並列コンピューティングにおいて、並列処理が容易なワークロードまたは問題（並列化が容易、完全並列、並列処理が容易、並列処理が容易とも呼ばれる）とは、問題を複数の並列タスクに分割するのにほとんど、あるいは全く労力を必要としないワークロードまたは問題のことである。^{[ 1 ]}これは、並列タスク間、あるいはタスク間の結果の通信への依存が最小限、あるいは全くないためである。^{[ 2 ]}

これらは、タスク間の通信、特に中間結果の通信を必要とする分散コンピューティングの問題とは異なります。真のスーパーコンピュータクラスタで使用される特別なインフラストラクチャを持たないサーバーファームで実行しやすく、 BOINCのような大規模なインターネットベースのボランティアコンピューティングプラットフォームに適しており、並列処理による速度低下も少ないです。並列処理が容易な問題の反対は、そもそも並列化できない本質的に逐次的な問題です。

並列処理が容易な問題の一般的な例としては、グラフィックス処理ユニットで処理される 3D ビデオのレンダリングがあり、各フレーム (順伝播法) またはピクセル (レイトレーシング法) は相互依存なく処理できます。^{[ 3 ]}パスワードクラッキングのいくつかの形式は、中央処理装置、CPU コア、またはクラスタに簡単に分散できる、並列処理が容易なタスクです。

語源

ここで「恥ずかしいほど」は、「恥ずかしいほど簡単な」並列化問題を指すために使われています。^{[ 4 ]}この用語は、開発者やコンパイラー側の恥ずかしさを暗示している可能性があります。「多くの重要な問題が主にその本質的な計算の複雑さのために未解決のままになっているため、多項式ホモトピー継続法の並列実装を開発しないのは恥ずかしいことです。」^{[ 5 ]}この用語は、 MATLABの開発者であるCleve Molerによる 1986 年のマルチプロセッサに関する書籍で初めて文献に登場し、彼はこの用語を発明したと主張しています。^[⁶^]^{[ 7 ]}

代替用語として「心地よく並列」という表現が使われるようになってきており、おそらく恥ずかしさという否定的な意味合いを避け、問題の並列化可能性について肯定的に捉えるためだろう。「もちろん、これらのプログラムには恥ずかしいところなど全くない。」^{[ 8 ]}

例

簡単な例として、静的データの配信が挙げられます。多数の処理ユニットに同じビット列を生成させるのは、ほとんど手間がかかりません。実際、有名な「Hello World」問題は、プログラミング上の考慮事項や計算コストをほとんど必要とせずに、容易に並列化できます。

恥ずかしいほど類似した問題の例としては、以下のようなものがあります。

モンテカルロ法^{[ 9 ]}
分散セット処理を使用した分散リレーショナルデータベースクエリ。
数値積分^{[ 10 ]}
一般的に、写真ギャラリーのサイズ変更や変換など、性質が類似した無関係なファイルを一括処理すること。
マンデルブロ集合、パーリンノイズ、および類似の画像では、各点が独立して計算されます。
コンピュータグラフィックスのレンダリング。コンピュータアニメーションでは、各フレームまたはピクセルは独立してレンダリングされることがあります。
暗号化における総当たり検索の例。^[¹¹^]実際の注目すべき例としては、仮想通貨で使用されるdistributed.netやプルーフ・オブ・ワークシステムなどがある。
分割データベースを用いたバイオインフォマティクスにおける BLAST検索。^{[ 12 ]}
数千の任意に取得した顔（例えば、閉回路テレビによるセキュリティまたは監視ビデオ）を、同様に多数の以前に保存された顔（例えば、犯罪者リストや同様の監視リスト）と比較する大規模な顔認識システム。^{[ 13 ]}
多数の独立したシナリオを比較するコンピュータシミュレーション。
遺伝的アルゴリズム。^{[ 14 ]}
数値天気予報のアンサンブル計算。
素粒子物理学における事象のシミュレーションと再構成。
マーチングスクエアアルゴリズム。
二次ふるいと数体ふるいのふるい分けステップ。
ランダムフォレスト機械学習手法における、ツリー成長のステップ。
各高調波が独立して計算される離散フーリエ変換。
GPU上で動作する畳み込みニューラルネットワーク。
制約プログラミングにおける並列探索^{[ 15 ]}

実装

R（プログラミング言語）では、Simple Network of Workstations（SNOW）パッケージが、ワークステーションのセットまたはBeowulfクラスタを使用して並列計算を行うためのシンプルなメカニズムを実装しています。^{[ 16 ]}同様のRパッケージには、「future」、「parallel」などがあります。

参考文献

↑ハーリヒー、モーリス；シャビット、ニール（2012）。マルチプロセッサプログラミングの技法、改訂版。エルゼビア。p. 14。ISBN 97801239779532016年2月28日取得。計算上の問題の中には「並列処理が容易」なものがあり、簡単に並列実行可能なコンポーネントに分割できます。
↑セクション 1.4.4: Foster, Ian (1995). Designing and Building Parallel Programs . Addison–Wesley. ISBN 97802015759412011年3月1日にオリジナルからアーカイブされました。
↑アラン・チャルマーズ、エリック・ラインハルト、ティム・デイビス（2011年3月21日）。『実践的並列レンダリング』CRC Press。ISBN 978-1-4398-6380-0。
↑マトロフ、ノーマン（2011）。『Rプログラミングの芸術：統計ソフトウェア設計の旅』、 p.347。No Starch。ISBN 9781593274108。
↑ Leykin, Anton; Verschelde, Jan; Zhuang, Yan (2006). "Parallel Homotopy Algorithms to Solve Polynomial Systems". Mathematical Software - ICMS 2006. Lecture Notes in Computer Science. Vol. 4151. pp. 225–234 . doi : 10.1007/11832225_22 . ISBN 978-3-540-38084-9。
↑ Moler, Cleve (1986). 「分散メモリマルチプロセッサにおける行列計算」。Heath, Michael T. (編) 『ハイパーキューブマルチプロセッサ』所収。Society for Industrial and Applied Mathematics、フィラデルフィア。ISBN 978-0898712094。
↑ Intelハイパーキューブパート2は、MathWorksウェブサイトのCleve's Cornerブログに再掲載されました。
↑ケプナー、ジェレミー (2009).マルチコアおよびマルチノードコンピュータ向け並列MATLAB、p.12. SIAM. ISBN 9780898716733。
↑エリコス・ジョン・コントギオルゲス (2005年12月21日).並列コンピューティングと統計のハンドブック. CRC Press. ISBN 978-1-4200-2868-3。
↑ Yuefan Deng (2013).応用並列コンピューティング. World Scientific. ISBN 978-981-4307-60-4。
↑ Josefsson, Simon; Percival, Colin (2016年8月). "The scrypt Password-Based Key Derivation Function" . tools.ietf.org . doi : 10.17487/RFC7914 . 2016年12月12日取得.
↑ Mathog, DR (2003年9月22日). "分割データベースでの並列BLAST" . Bioinformatics . 19 (14): 1865–6 . doi : 10.1093/bioinformatics/btg250 . PMID 14512366 .
↑顔認識機能を25倍高速化する方法（開発者ブログ記事）
↑筒井重義、ピエール・コレット（2013年12月5日）。GPGPU上での大規模並列進化計算。Springer Science & Business Media。ISBN 978-3-642-37959-8。
↑ Youssef Hamadi; Lakhdar Sais (2018年4月5日). Handbook of Parallel Constraint Reasoning . Springer. ISBN 978-3-319-63516-3。
↑シンプルネットワークオブワークステーション（SNOW）パッケージ

外部リンク

恥ずかしいほど並列な計算、ベオウルフ風の計算クラスタの設計
「Star-P：高生産性並列コンピューティング」

[1] ハーリヒー、モーリス；シャビット、ニール（2012）。マルチプロセッサプログラミングの技法、改訂版。エルゼビア。p. 14。ISBN 97801239779532016年2月28日取得。計算上の問題の中には「並列処理が容易」なものがあり、簡単に並列実行可能なコンポーネントに分割できます。

[dbpp-2] セクション 1.4.4: Foster, Ian (1995). Designing and Building Parallel Programs . Addison–Wesley. ISBN 97802015759412011年3月1日にオリジナルからアーカイブされました。

[ChalmersReinhard2011-3] アラン・チャルマーズ、エリック・ラインハルト、ティム・デイビス（2011年3月21日）。『実践的並列レンダリング』CRC Press。ISBN 978-1-4398-6380-0。

[4] マトロフ、ノーマン（2011）。『Rプログラミングの芸術：統計ソフトウェア設計の旅』、 p.347。No Starch。ISBN 9781593274108。

[5] Leykin, Anton; Verschelde, Jan; Zhuang, Yan (2006). "Parallel Homotopy Algorithms to Solve Polynomial Systems". Mathematical Software - ICMS 2006. Lecture Notes in Computer Science. Vol. 4151. pp. 225–234 . doi : 10.1007/11832225_22 . ISBN 978-3-540-38084-9。

[hcmp-6] Moler, Cleve (1986). 「分散メモリマルチプロセッサにおける行列計算」。Heath, Michael T. (編) 『ハイパーキューブマルチプロセッサ』所収。Society for Industrial and Applied Mathematics、フィラデルフィア。ISBN 978-0898712094。

[7] Intelハイパーキューブパート2は、MathWorksウェブサイトのCleve's Cornerブログに再掲載されました。

[8] ケプナー、ジェレミー (2009).マルチコアおよびマルチノードコンピュータ向け並列MATLAB、p.12. SIAM. ISBN 9780898716733。

[Kontoghiorghes2005-9] エリコス・ジョン・コントギオルゲス (2005年12月21日).並列コンピューティングと統計のハンドブック. CRC Press. ISBN 978-1-4200-2868-3。

[Deng2013-10] Yuefan Deng (2013).応用並列コンピューティング. World Scientific. ISBN 978-981-4307-60-4。

[11] Josefsson, Simon; Percival, Colin (2016年8月). "The scrypt Password-Based Key Derivation Function" . tools.ietf.org . doi : 10.17487/RFC7914 . 2016年12月12日取得.

[12] Mathog, DR (2003年9月22日). "分割データベースでの並列BLAST" . Bioinformatics . 19 (14): 1865–6 . doi : 10.1093/bioinformatics/btg250 . PMID 14512366 .

[13] 顔認識機能を25倍高速化する方法（開発者ブログ記事）

[TsutsuiCollet2013-14] 筒井重義、ピエール・コレット（2013年12月5日）。GPGPU上での大規模並列進化計算。Springer Science & Business Media。ISBN 978-3-642-37959-8。

[HamadiSais2018-15] Youssef Hamadi; Lakhdar Sais (2018年4月5日). Handbook of Parallel Constraint Reasoning . Springer. ISBN 978-3-319-63516-3。

[16] シンプルネットワークオブワークステーション（SNOW）パッケージ

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

語源

例

実装

関連項目

参考文献

外部リンク