109

合計で約2.8GBのオブジェクトコードを含む膨大な数の関数があります(残念ながら、科学計算を回避する方法はありません...)

それらをリンクしようとすると、(予期される)relocation truncated to fit: R_X86_64_32Sエラーが発生します。これは、コンパイラフラグを指定することで回避したいと考えていました-mcmodel=medium。私が制御できることに加えてリンクされているすべてのライブラリは、-fpicフラグを使用してコンパイルされます。

それでもエラーは解決せず、リンク先の一部のライブラリはPICでコンパイルされていないと思います。

エラーは次のとおりです。

/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/crt1.o: In function `_start':
(.text+0x12): relocation truncated to fit: R_X86_64_32S against symbol `__libc_csu_fini'     defined in .text section in /usr/lib64/libc_nonshared.a(elf-init.oS)
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/crt1.o: In function `_start':
(.text+0x19): relocation truncated to fit: R_X86_64_32S against symbol `__libc_csu_init'    defined in .text section in /usr/lib64/libc_nonshared.a(elf-init.oS)
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/crt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/crti.o: In function    `call_gmon_start':
(.text+0x7): relocation truncated to fit: R_X86_64_GOTPCREL against undefined symbol      `__gmon_start__'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/crtbegin.o: In function `__do_global_dtors_aux':
crtstuff.c:(.text+0xb): relocation truncated to fit: R_X86_64_PC32 against `.bss' 
crtstuff.c:(.text+0x13): relocation truncated to fit: R_X86_64_32 against symbol `__DTOR_END__' defined in .dtors section in /usr/lib/gcc/x86_64-redhat-linux/4.1.2/crtend.o
crtstuff.c:(.text+0x19): relocation truncated to fit: R_X86_64_32S against `.dtors'
crtstuff.c:(.text+0x28): relocation truncated to fit: R_X86_64_PC32 against `.bss'
crtstuff.c:(.text+0x38): relocation truncated to fit: R_X86_64_PC32 against `.bss'
crtstuff.c:(.text+0x3f): relocation truncated to fit: R_X86_64_32S against `.dtors'
crtstuff.c:(.text+0x46): relocation truncated to fit: R_X86_64_PC32 against `.bss'
crtstuff.c:(.text+0x51): additional relocation overflows omitted from the output
collect2: ld returned 1 exit status
make: *** [testsme] Error 1

そして、私がリンクしているシステムライブラリ:

-lgfortran -lm -lrt -lpthread

問題を探す手がかりはありますか?

編集:

まず第一に、議論をありがとう...

少し明確にするために、私は次のような何百もの関数(それぞれが別々のオブジェクトファイルでサイズが約1 MB)を持っています:

double func1(std::tr1::unordered_map<int, double> & csc, 
             std::vector<EvaluationNode::Ptr> & ti, 
             ProcessVars & s)
{
    double sum, prefactor, expr;

    prefactor = +s.ds8*s.ds10*ti[0]->value();
    expr =       ( - 5/243.*(s.x14*s.x15*csc[49300] + 9/10.*s.x14*s.x15*csc[49301] +
           1/10.*s.x14*s.x15*csc[49302] - 3/5.*s.x14*s.x15*csc[49303] -
           27/10.*s.x14*s.x15*csc[49304] + 12/5.*s.x14*s.x15*csc[49305] -
           3/10.*s.x14*s.x15*csc[49306] - 4/5.*s.x14*s.x15*csc[49307] +
           21/10.*s.x14*s.x15*csc[49308] + 1/10.*s.x14*s.x15*csc[49309] -
           s.x14*s.x15*csc[51370] - 9/10.*s.x14*s.x15*csc[51371] -
           1/10.*s.x14*s.x15*csc[51372] + 3/5.*s.x14*s.x15*csc[51373] +
           27/10.*s.x14*s.x15*csc[51374] - 12/5.*s.x14*s.x15*csc[51375] +
           3/10.*s.x14*s.x15*csc[51376] + 4/5.*s.x14*s.x15*csc[51377] -
           21/10.*s.x14*s.x15*csc[51378] - 1/10.*s.x14*s.x15*csc[51379] -
           2*s.x14*s.x15*csc[55100] - 9/5.*s.x14*s.x15*csc[55101] -
           1/5.*s.x14*s.x15*csc[55102] + 6/5.*s.x14*s.x15*csc[55103] +
           27/5.*s.x14*s.x15*csc[55104] - 24/5.*s.x14*s.x15*csc[55105] +
           3/5.*s.x14*s.x15*csc[55106] + 8/5.*s.x14*s.x15*csc[55107] -
           21/5.*s.x14*s.x15*csc[55108] - 1/5.*s.x14*s.x15*csc[55109] -
           2*s.x14*s.x15*csc[55170] - 9/5.*s.x14*s.x15*csc[55171] -
           1/5.*s.x14*s.x15*csc[55172] + 6/5.*s.x14*s.x15*csc[55173] +
           27/5.*s.x14*s.x15*csc[55174] - 24/5.*s.x14*s.x15*csc[55175] +
           // ...
           ;

        sum += prefactor*expr;
    // ...
    return sum;
}

オブジェクトsは比較的小さく、必要な定数x14、x15、...、ds0、...などを保持tiしますが、外部ライブラリからdoubleを返すだけです。ご覧のとおり、csc[]は事前に計算された値のマップであり、次の形式の個別のオブジェクトファイル(それぞれ約1 MBのサイズで数百)でも評価されます。

void cscs132(std::tr1::unordered_map<int,double> & csc, ProcessVars & s)
{
    {
    double csc19295 =       + s.ds0*s.ds1*s.ds2 * ( -
           32*s.x12pow2*s.x15*s.x34*s.mbpow2*s.mWpowinv2 -
           32*s.x12pow2*s.x15*s.x35*s.mbpow2*s.mWpowinv2 -
           32*s.x12pow2*s.x15*s.x35*s.x45*s.mWpowinv2 -
           32*s.x12pow2*s.x25*s.x34*s.mbpow2*s.mWpowinv2 -
           32*s.x12pow2*s.x25*s.x35*s.mbpow2*s.mWpowinv2 -
           32*s.x12pow2*s.x25*s.x35*s.x45*s.mWpowinv2 +
           32*s.x12pow2*s.x34*s.mbpow4*s.mWpowinv2 +
           32*s.x12pow2*s.x34*s.x35*s.mbpow2*s.mWpowinv2 +
           32*s.x12pow2*s.x34*s.x45*s.mbpow2*s.mWpowinv2 +
           32*s.x12pow2*s.x35*s.mbpow4*s.mWpowinv2 +
           32*s.x12pow2*s.x35pow2*s.mbpow2*s.mWpowinv2 +
           32*s.x12pow2*s.x35pow2*s.x45*s.mWpowinv2 +
           64*s.x12pow2*s.x35*s.x45*s.mbpow2*s.mWpowinv2 +
           32*s.x12pow2*s.x35*s.x45pow2*s.mWpowinv2 -
           64*s.x12*s.p1p3*s.x15*s.mbpow4*s.mWpowinv2 +
           64*s.x12*s.p1p3*s.x15pow2*s.mbpow2*s.mWpowinv2 +
           96*s.x12*s.p1p3*s.x15*s.x25*s.mbpow2*s.mWpowinv2 -
           64*s.x12*s.p1p3*s.x15*s.x35*s.mbpow2*s.mWpowinv2 -
           64*s.x12*s.p1p3*s.x15*s.x45*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.p1p3*s.x25*s.mbpow4*s.mWpowinv2 +
           32*s.x12*s.p1p3*s.x25pow2*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.p1p3*s.x25*s.x35*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.p1p3*s.x25*s.x45*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.p1p3*s.x45*s.mbpow2 +
           64*s.x12*s.x14*s.x15pow2*s.x35*s.mWpowinv2 +
           96*s.x12*s.x14*s.x15*s.x25*s.x35*s.mWpowinv2 +
           32*s.x12*s.x14*s.x15*s.x34*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.x14*s.x15*s.x35*s.mbpow2*s.mWpowinv2 -
           64*s.x12*s.x14*s.x15*s.x35pow2*s.mWpowinv2 -
           32*s.x12*s.x14*s.x15*s.x35*s.x45*s.mWpowinv2 +
           32*s.x12*s.x14*s.x25pow2*s.x35*s.mWpowinv2 +
           32*s.x12*s.x14*s.x25*s.x34*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.x14*s.x25*s.x35pow2*s.mWpowinv2 -
           // ...
    
       csc.insert(cscMap::value_type(192953, csc19295));
    }

    {
       double csc19296 =      // ... ;

       csc.insert(cscMap::value_type(192956, csc19296));
    }

    // ...
}

それについてです。最後のステップは、それらすべてを呼び出しfunc[i]て結果を合計することです。

これがかなり特殊で珍しいケースであるという事実に関して:はい、そうです。これは、素粒子物理学のために高精度の計算を行おうとするときに人々が対処しなければならないことです。

EDIT2:

また、x12、x13などは実際には定数ではないことも付け加えておきます。それらは特定の値に設定され、それらすべての関数が実行されて結果が返され、次にx12、x13などの新しいセットが選択されて次の値が生成されます。そして、これは105から106回行わなければなりませ...

EDIT3:

これまでの提案と議論に感謝します...正直なところ、これを正確に行う方法がわからないので、コード生成時にループをロールアップしようとしますが、これが最善の策です。

ところで、私は「これは科学計算であり、最適化する方法はありません」の背後に隠れようとはしませんでした。
このコードの基礎は、私が実際にアクセスできない「ブラックボックス」から出てきたものであり、さらに、単純な例ですべてがうまく機能し、主に実際に起こっていることに圧倒されていると感じていますワールドアプリケーション...

EDIT4:

cscそこで、数式処理システム(Mathematica )で式を簡略化することで、定義のコードサイズを約4分の1に減らすことができました。コードを生成する前に他のトリックを適用することで(この部分を約100 MBに減らす)、もう1桁程度減らす方法もわかりました。このアイデアが機能することを願っています。

今あなたの答えに関連しています:

funcCASがあまり役に立たないsでループを再びロールバックしようとしていますが、すでにいくつかのアイデアがあります。たとえば、のような変数で式を並べ替え、 Pythonでsをx12, x13,...解析し、cscそれらを相互に関連付けるテーブルを生成します。そうすれば、少なくともこれらの部分をループとして生成できます。これがこれまでのところ最良の解決策であるように思われるので、私はこれを最良の答えとしてマークします。

ただし、VJoの功績も認めたいと思います。GCC 4.6は確かにはるかにうまく機能し、より小さなコードを生成し、より高速です。大きなモデルを使用すると、コードをそのまま使用できます。したがって、技術的にはこれが正解ですが、概念全体を変更する方がはるかに優れたアプローチです。

あなたの提案と助けをありがとうございました。興味のある方は、準備ができ次第最終結果を掲載します。

備考:

他のいくつかの答えに対するいくつかの注意:私が実行しようとしているコードは、単純な関数/アルゴリズムの拡張と愚かな不必要な展開に由来するものではありません。実際に起こることは、私たちが始めたものはかなり複雑な数学的オブジェクトであり、それらを数値的に計算可能な形式にすることでこれらの式が生成されるということです。問題は、実際には基礎となる物理理論にあります。中間式の複雑さは階乗的にスケーリングしますが、これはよく知られていますが、これらすべてを物理的に測定可能なもの(観察可能なもの)に組み合わせると、式の基礎を形成する非常に小さな関数のほんの一握りに要約されます。(この点に関しては、一般的で唯一利用可能な仮説に関しては間違いなく「間違った」ものがありますこれは「摂動論」と呼ばれます)私たちは、この仮説を別のレベルに引き上げようとします。これは、もはや分析的に実行可能ではなく、必要な関数の基礎がわからない場合です。ですから、このようにブルートフォースを試みます。最善の方法ではありませんが、うまくいけば、最終的に手元にある物理学の理解に役立つ方法です...

最終編集:

すべての提案のおかげで、Mathematicaを使用しfunc、トップアンサーの線に沿ってsのコードジェネレーターを変更することで、コードサイズを大幅に削減することができました:)

Mathematicaで関数を単純化し、csc92MBに減らしました。これは既約部分です。最初の試みは永遠にかかりましたが、いくつかの最適化の後、これは現在、単一のCPUで約10分で実行されます。

sへの影響funcは劇的でした。それらのコード全体のサイズは約9MBに減少したため、コードの合計は100MBの範囲になりました。これで、最適化をオンにするのが理にかなっており、実行は非常に高速です。

繰り返しになりますが、皆さんの提案に感謝します。私はたくさんのことを学びました。

4

11 に答える 11

53

したがって、このテキストを生成するプログラムがすでにあります。

prefactor = +s.ds8*s.ds10*ti[0]->value();
expr = ( - 5/243.*(s.x14*s.x15*csc[49300] + 9/10.*s.x14*s.x15*csc[49301] +
       1/10.*s.x14*s.x15*csc[49302] - 3/5.*s.x14*s.x15*csc[49303] -...

double csc19295 =       + s.ds0*s.ds1*s.ds2 * ( -
       32*s.x12pow2*s.x15*s.x34*s.mbpow2*s.mWpowinv2 -
       32*s.x12pow2*s.x15*s.x35*s.mbpow2*s.mWpowinv2 -
       32*s.x12pow2*s.x15*s.x35*s.x45*s.mWpowinv2 -...

右?

すべての関数が同様の「形式」を持っている場合(n個の数値をm回乗算し、結果を追加するなど)、これを実行できると思います。

  • 文字列の代わりに(つまり、文字列「s.ds0」の代わりに生成されるオフセットを出力するようにジェネレータプログラムを変更しますoffsetof(ProcessVars, ds0)
  • そのようなオフセットの配列を作成します
  • 上記の配列と構造体ポインタのベースアドレスを受け入れて結果を生成するエバリュエータを記述します

配列+エバリュエーターは、関数の1つと同じロジックを表しますが、エバリュエーターのみがコードになります。配列は「データ」であり、実行時に生成するか、ディスクに保存してiチャンクを読み取るか、メモリマップトファイルを使用して読み取ることができます。

func1の特定の例では、のベースアドレスにアクセスできる場合に、エバリュエーターを介して関数を書き直す方法を想像してください。また、に到達するためにベースアドレスに追加する必要のある定数とオフセットの表現のようなベクトルもありsます。とcscx14ds8csc[51370]

膨大な数の関数に渡す実際のデータを処理する方法を説明する新しい形式の「データ」を作成する必要があります。

于 2011-06-09T22:16:15.353 に答える
46

Linuxで使用されるx86-64ABIは、GOTおよびPLTの64ビット再配置タイプを含むこのようなサイズ制限を回避するために特に「ラージモデル」を定義します。(セクション4.4.2の表、およびそれらの使用方法を示す3.5.5の命令シーケンスを参照してください。)

関数が2.8GBを占有しているため、gccは大規模なモデルをサポートしていないため、運が悪いことになります。できることは、動的にリンクする共有ライブラリにコードを分割できるようにコードを再編成することです。

それが不可能な場合は、誰かが提案したように、データをコードに入れる(コンパイルしてリンクする)代わりに、データが巨大であるため、実行時にロードできます(通常のファイルとして、またはmmapすることができます)。

編集

ラージモデルはgcc4.6でサポートされているようです(このページを参照)。それを試すことはできますが、コードの再編成については上記が引き続き当てはまります。

于 2011-06-09T18:47:07.340 に答える
37

その側のプログラムでは、コードのキャッシュミスは、実行時のループのコストを超える可能性が非常に高くなります。コードジェネレーターに戻って、評価したいもの(つまり、Dキャッシュに収まる可能性が高いもの)のコンパクトな表現を生成してから、プログラムのインタープリターを使用して実行することをお勧めします。また、まだかなりの数の操作がある小さなカーネルを除外して、解釈されたコードの「命令」としてそれらを使用できるかどうかを確認することもできます。

于 2011-06-09T22:06:46.277 に答える
21

データではなくコードが多すぎるため、エラーが発生します。これは、たとえば__libc_csu_fini(関数である)が参照されていることによって示され_start、再配置はそれに合わせて切り捨てられます。これは、_start(プログラムの真のエントリポイント)が、範囲が2GBしかないSIGNED32ビットオフセットを介してその関数を呼び出そうとしていることを意味します。オブジェクトコードの合計量は約2.8GBなので、事実を確認してください。

データ構造を再設計できれば、巨大な式を単純なループとして書き直すことで、コードの多くを「圧縮」できます。

また、別のプログラムで計算csc[]し、結果をファイルに保存して、必要に応じてロードすることもできます。

于 2011-06-09T19:33:47.457 に答える
15

私は、あなたがやりたいことをするための別の方法があるべきだということに誰もが同意していると思います。数百メガバイト(ギガバイト?)のコードをコンパイルし、それを数ギガバイトサイズの実行可能ファイルにリンクして実行すると、非常に非効率に聞こえます。

私があなたの問題を正しく理解しているなら、あなたはある種のコードジェネレーターGを使用してfunc1...N、一連のマップcsc1...Mを入力として受け取る一連の関数を生成します。あなたがしたいのは、計算しcsc1...M、さまざまな入力に対して1,000,000回のループを実行し、毎回を見つけることs = func1 + func2 + ... + funcNです。fucn1...Nただし、どのように関連しているかは指定していませんcsc1...M

それがすべて当てはまる場合は、問題を別の方法で解決できるはずです。これにより、管理がはるかに容易になり、場合によってはさらに高速になる可能性があります(つまり、マシンのキャッシュを実際に機能させることができます)。

オブジェクトファイルサイズの実際的な問題に加えて、現在のプログラムは、データへのアクセスをローカライズせず(巨大なマップが多すぎる)、ローカライズされたコード実行がない(非常に長い関数が多すぎる)ため、効率的ではありません。

プログラムを3つのフェーズに分割するのはどうですか:フェーズ1のビルドcsc1...Mと保存。フェーズ2は、一度に1つずつビルドfuncし、入力ごとに1,000,000回実行して、結果を保存します。func1...Nフェーズ3は、1,000,000回の実行ごとに保存された結果の結果の合計を見つけます。このソリューションの良いところは、複数の独立したマシン間で簡単に並列化できることです。

編集:@bbtrb、1つのfuncと1つのcscをどこかで利用できるようにできますか?それらは非常に規則的で圧縮可能であるように見えます。たとえば、func1は、それぞれが1つの係数、sの変数への2つのインデックス、およびcscへの1つのインデックスで構成される式の単なる合計のようです。したがって、それは素晴らしいループに減らすことができます。完全な例を利用できるようにすれば、それらを長い式ではなくループに圧縮する方法が見つかると確信しています。

于 2011-06-10T02:04:07.033 に答える
5

私があなたのエラーを正しく読んだ場合、制限を引き継ぐのは初期化されたデータセクションです(それがコードだった場合、私見でははるかに多くのエラーが発生します)。グローバルデータの大きな配列がありますか?その場合は、動的に割り当てられるようにプログラムを再構築します。データが初期化されている場合は、構成ファイルから読み取ります。

ところでこれを見て:

(.text + 0x20):`main'への未定義の参照

別の問題があると思います。

于 2011-06-09T18:47:51.670 に答える
3

いくつかの提案:-サイズを最適化する(-Os)。インライン関数呼び出し、通常の関数呼び出しを行います。文字列プーリングを有効にします。

物事を異なるDLL(共有オブジェクト、Linuxの場合は.so、Mac OS Xの場合は.dylib)に分割してみてください。それらがアンロードできることを確認してください。次に、オンデマンドで物事をロードするために何かを実装し、不要なときにそれらを解放します。

そうでない場合は、コードをさまざまな実行可能ファイルに分割し、それらの間で通信するために何かを使用します(パイプ、ソケット、さらにはファイルへの書き込み/読み取り)。不器用ですが、どのようなオプションがありますか?

完全に代替:-JITで動的言語を使用します。私の頭の真上で-LuaJITを使用して-そしてLua、またはコードをガベージコレクションできる他のそのような言語やランタイムでこれらの式の多くを書き直します(再生成しますか?) 。

LuaJITは非常に効率的で、特定の点でC / C ++を上回っている場合もありますが、非常に近い場合があります(ガベージコレクションが不十分なため、低速になる場合があります)。自分で確認してください:

http://luajit.org/performance_x86.html

そこからファイルをダウンロードscimark2.luaし、「C」バージョン(google it)と比較します。多くの場合、結果は非常に近くなります。

于 2011-06-10T00:12:47.917 に答える
3

コードが何らかの適応深度法を使用して数値積分を行っているように見えます。残念ながら、コードジェネレーター(またはコードジェネレーターの作成者)は、パッチの種類ごとに1つではなく、パッチごとに1つの関数を生成するほど愚かです。そのため、コンパイルするには大量のコードが生成され、コンパイルできたとしても、どこにも共有されていないため、実行に苦労します。(何も共有されていないため、オブジェクトコードの各ページをディスクからロードしなければならないことによる苦痛を想像できますか?したがって、常にOSが削除する候補になります。無駄になる命令キャッシュは言うまでもありません。)

修正は、すべての展開を停止することです。この種のコードでは、より複雑なパターンでデータにアクセスするための追加の命令のオーバーヘッドが、とにかく(おそらく)大きな基になるデータセットを処理するコストによって吸収されるため、共有を最大化する必要があります。コードジェネレーターがデフォルトでこれを行う可能性もあり、科学者は展開するためのいくつかのオプションを見て(これらは時々速度を向上させることに注意してください)、それらを一度にすべてオンにし、この結果として生じる混乱を受け入れるように主張していますマシンの実際の制限を受け入れて、デフォルトで生成される数値的に正しいバージョンを使用するのではなく、コンピューターによって。しかし、コードジェネレーターがそれを行わない場合は、それを行う(または既存のコードをハックする)ものを入手してください。

結論: 2.8GBのコードのコンパイルとリンクは機能せず、強制的に機能させるべきではありません。別の方法を見つけてください。

于 2011-06-11T07:28:55.410 に答える
2

それらの表現は、私には交代級数によく似ています。コードの残りの部分がどのように見えるかはわかりませんが、生成する式を導出するのはそれほど難しいことではないようです。特に、2.8GBの2KBのアンロールされたコードがある場合は、実行時にも価値があるでしょう。

于 2011-06-10T01:52:18.023 に答える
2

リンカは、これらの制限を何らかの形で超えたバイナリ内に32ビットの再配置オフセットを生成しようとしています。メインプログラムのアドレス空間要件を減らしてみてください。

オブジェクトコードの一部/大部分を1つ以上のライブラリに分割できますか(これも-fpic / -fPICでコンパイルされます)?次に、これらのライブラリに対してリンクする非静的バイナリを生成します。ライブラリは個別のメモリブロックに存在し、再配置オフセットは相対(32ビット)ではなく動的/絶対(64ビット)になります。

于 2011-06-10T11:56:36.627 に答える
1

これは、おそらく記号代数や手動での展開によって、コード生成がうまくいかなかった結果のように見えます。シンボリック操作は、式ツリーまたは計算グラフの深さで指数関数的に成長することがよく知られています。ここでは自動微分を使用できる可能性があります。これにより、コードサイズが非常に小さくなり、実行が大幅に高速化されます。

于 2011-06-10T10:10:51.157 に答える