質問があいまいに見えるかもしれませんが、私に説明してください。特定の値で関数を並列に評価する
関数f（x、y、z ....）があり、その値を点（x1、y1、z1 .....）で見つける必要があるとします。
最も単純なアプローチは、（x、y、z ...）を（x1、y1、z1 .....）に置き換えることです。
ここで、関数の評価に時間がかかり、アルゴリズムを並列化して評価したいとします。明らかにそれは機能の性質にも依存します。
私の質問は、f（x、y、z ...）を並列化するために「考えている」ときに探す必要がある制約は何ですか？
可能であれば、勉強するリンクを教えてください。
このような一般的な方法で質問すると、非常に具体的な助言を与えることはできません。
私は、密接に関係する変数のグループを使用して関数を評価したり書き換えたりする方法を探して、最終的な評価に使用できる中間式を作成して分析を開始します。変数自体から最終関数に至る部分式の階層を含む方法を見つけることができます。
一般に、このような評価ツリーが短くて幅が広いほど、並列度が高くなります。 「より多くの並列性が優れている」ということを念頭に置いておくと、2つの注意点があります。
非常に並列的なアプローチは、実際には、元の「シリアル」アプローチよりも多くの計算を必要とします。実際には、直列アプローチが以前のすべての部分式評価を利用してその再利用を最大化することができるので、この点で効率のいくらかの損失が予想される。
別の点として、並列評価では、良好または最適な誤差の見積もりを得るために選択された連続評価よりも丸め/精度の動作が悪いことがよくあります。
行列を含む評価では、関数値が引数にどのように依存するかについて、多くの対称性がありますが、多くの作業が行われています。したがって、そこで開発された数値線形代数と並列アルゴリズムに精通していることが役立ちます。
ロットが分かっている別の領域は、多変量多項式関数と有理関数です。
関数が超越的である場合、依存性をより扱いやすくする（代数的）変換やリファクタリングが望まれるかもしれません。
あなたの質問には直接関係しませんが、多くの引数にわたって計算値の計算コストを償却するアルゴリズムがあります。たとえば、常微分方程式の解を計算する場合、中間点での導関数を評価するコストを共有する「複数ステップ」の方法があります。これらの値は、それらの値を複数回再利用することによって得られます。
私は、機能の評価をスピードアップするという懸念から、複数の評価を実行する予定があることを示唆しています。したがって、事前評価を活用する方法や、関連する議論で評価を実行して、並列性の検索に貢献する方法について考えるかもしれません。
を追加しました：いくつかのリンクや検索戦略の議論は
ほとんどの著者は、複数の引数のポイントで同じ機能を評価する意味 に句「並列機能の評価」を使用します。 [ - ルーロンとユーセフ粗視化パラレル機能評価]
http://cdsweb.cern.ch/record/401028/files/p837.pdf
材料のGaurav Kalraの種類を見つけるための検索戦略を約それらを回避しようとしてください を尋ね
：例えば
を参照してください。 。たとえば、検索用語に「fine-grained」と入力すると、 と表示されます。
特定の種類の機能に焦点を当てることも効果的です。 「関数評価」ではなく「多項式評価」です。例えばここで
私たちは「速い」の評価のためのいくつかのよく知られた技術 の治療を持っているが、GPUベースの計算のための設計に適用：
[効率的なGPUカーネルを入手する方法 - クルス、レイトン、およびバルバ]
http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.3457v1.pdf
（その要旨から）「ここで、我々は アルゴリズム（高速多重極法と高速ガウス変換）、 高速の合計に取り組みと GPU上でのパフォーマンスを達成するためのアルゴリズムの再設計が適用されている。performanの進行達成された改善は はGPUの 超並列アーキテクチャのための公式化アルゴリズムの演習を示しています。
排除する価値のある別の検索語句は「パイプライン」です。 この用語は、複数の関数評価が行われるときに が使用される並行処理の種類について常に議論します。初期の ステージの計算は、後の ステージと並列に行うことができますが、異なる入力に実行できます。
これは除外したい検索用語です。か否か。ここで
は、有限体GF（p）を超えるのn変量 多項式評価のためのn倍の高速化について説明した紙です。これは、暗号アプリケーションのための直接の利害関係の かもしれませんが、変更ホーナー法を介した アプローチは、一般化のために その可能性について興味深いことがあります
[有限リング上 非構造化機能を評価するためのビットの比較と単語レベルアルゴリズム - - SunarとCyganski]
http://www.iacr.org/archive/ches2005/018.pdf
「我々は、有限リングとフィールド上で定義された 任意のn変量機能を評価するためのホーナーのアルゴリズムに変更を提示 ...ドメインは、有限体GF（p）である場合。コンプO（p^n） からO（（p^n）/（2n））まで多変量ホーナー多項式評価が改善されました。提示されたアルゴリズムの最適性を証明する。「
多変量有理関数は、単に二つのそのような多項式関数の 比と考えることができる。初等超越関数 等を近似する際に特に 有効であることができる単変量有理関数の特別な場合 について、評価することができます有限（それぞれ切り捨て）を介してそのconvergents（部分分母 と分母）再帰的に定義することができる 連分数、。
連分数評価のトピックは、いくつかとそのトピックを接続する最終的なリンクに をセグエために私たちを可能にしますファムIAR数値線形代数の 平行：
[LU分解と連分数 の並列評価 - オメルEgecioglu]
http://www.cs.ucsb.edu/~omer/DOWNLOADABLE/lu-cf98.pdf
「一般的な連分数 （CF）の最初のn convergentsとすることができます
1つの関数に対する1回の呼び出しの評価を高速化する方法を尋ねました。これは、対数的に最適な対数並列で計算されたものです（O（n/log（n）評価時間が時間単位で測定されない限り、スピードアップにはなぜそれが価値があるのかは不明です。関数の実行自体を高速化することを主張する場合、その内容を調べて、そのいくつかの側面が並列化可能かどうかを確認する必要があります。あなたはそれが何を計算するか、それがどういうものなのかについて何の情報も提供していないので、この点についてさらに助言するのは難しいです。ハードマスの答えは、関数の実際の内部構造に応じて、使用できるアイデアを示唆しています。
しかし、通常、あなたの質問をしている人は実際にx、y、zの異なる値（例えば、x1、y1、... x2、y2、...）に対して関数を何度もxN、yN、...あなたのボキャブラリーを使用して）。 はい、機能の実行をスピードアップすると、コールの集合をスピードアップし、それは人々が望む傾向があることです。これが当てはまる場合、全体の実行をスピードアップするのは「技術的に簡単」です。関数をN回コールすることは並行して行います。そして、ポイントワイズ評価はすべて同時に行われます。これを実現するには、処理したい値からベクトルを作りだしています（この種のトリックは「データ並列」プログラミングと呼ばれます）。あなたが本当に望むのは次のようなものです：
PARALLEL DO I=1,N
RESULT(I)=F(X[J],Y[J], ...)
END PARALLEL DO
どのようにPARALLEL DOを実装するかは、ご使用のプログラミング言語とライブラリによって異なります。 これは一般にNがかなり大きい数値である場合にのみ有効ですが、実行するのが高価なfほど有効Nが小さくなります。
また、関数の構造を利用してこれをさらに効率化することもできます。 fが一般的な場合と同じように内部的な値を計算する場合は、 を使用して特殊なケースを除外し、それらを事前に計算し、その結果を使用して個々の呼び出しごとに "残りのf"を計算することができます。
すべての関数の結果（e..g、すべての結果を合計）を組み合わせる（「減らす」）場合は、の外側にあるのPARALELL DOループを実行できます。ループ内で結果を結合しようとすると、 "ループに依存する依存関係"が発生し、誤った答えが得られるか、コンパイラや並列ライブラリによっては期待通りの結果が得られません。がの場合、組み合わせが "sum"のような連想/可換演算の場合は効率的に結合し、バイナリツリーの量を構築しての評価を並列に実行することで、効率的に結合を行います。これは、データ並列計算でも頻繁に発生する別の問題ですが、ここではさらに進めません。
多くの場合、並列forループのオーバーヘッドはかなり高くなります（フォークスレッドは高価です）。だから、通常、人々はいくつかの反復でオーバーヘッドを分割する：
PARALLEL DO I=1,N,M
DO J=I,I+M
RESULT(J)=F(X[J],Y[J], ...)
END DO
END PARALLEL DO
定数Mは効率のための較正を必要とする。あなたはそれを "調整"しなければなりません。また、NはMの倍数ではないかもしれないという事実に注意を払わなければならない。エッジ条件を処理するために余分なクリーンループが必要な場合：
PARALLEL DO I=1,int(N/M)*M,M
DO J=I,I+M
RESULT(J)=F(X[J],Y[J], ...)
END DO
END PARALLEL DO
DO J=int(N/M)*M,N,1
RESULT(J)=F(X[J],Y[J], ...)
END DO
どのタイプの機能を並列化したいかについての詳細を記入してください。例は素晴らしいでしょう。 – marcog