1

少なくともタイトル検索からは、これに関する既存の質問はないようです。外部マージに最適なパス数を見つけようとしています。したがって、1000チャンクのデータがある場合、1回のパスは1000ウェイのマージになります。2つのパスは、200チャンクの5つのグループであり、5つのチャンクの1つのグループの最終的なマージです。等々。2つのパスが1つのパスに勝るものはないように見えるので、私はいくつかの計算を行いましたが、これには欠陥があるはずです。ただし、データの読み取り方法については誤解である可能性があります。

まず、数値例：

データ：100 GB RAM
：1 GB

1GBのメモリがあるため、一度に1GBをロードして、クイックソートまたはマージソートを使用して並べ替えることができます。これで、100個のチャンクを並べ替えることができます。100ウェイマージを実行できます。これは、RAM/(chunks+1)サイズバケット==1024MB/101を作成することによって行われ10.14MBます。10.14MB100個のチャンクごとに100個のバケットがあり、サイズも1つの出力バケットがあります10.14MB。マージするときに、入力バケットが空の場合、ディスクシークを実行してそのバケットを補充します。同様に、出力バケットがいっぱいになると、ディスクに書き込んで空にします。「ディスクが読み取る必要がある回数」は(data/ram)*(chunks+1)です。これは、入力バケットのサイズを設定しているという事実から得ram/(chunks+1)られます。特定のパスのデータ全体を読み込む必要があるため、次のように読みます。(data/bucket_size)回数。つまり、入力バケットが空になるたびに、それを補充する必要があります。ここでは100を超えるチャンクを実行するため、numChunks*(chunk_size/bucket_size)=datasize/bucket_sizeまたは100*(1024MB/10.14MB)。BucketSize = ram/(chunks+1)so 100*(1024/10.14)= (data/ram) * (chunks+1)== 1024*100MB/1024MB * 10110100読み取り。

2パスシステムの場合、B #chunksのAグループを実行し、次にA#chunksの1グループの最終マージを実行します。前のロジックを使用すると、numReads=になりA*( (data/ram)*(B+1)) + 1*( (data/ram)*(A+1))ます。A*B=もありますData/Ram。たとえば、10個のチャンクからなる10個のグループで、各チャンクはGBです。ここで、A = 10 B = 10. 10 * 10 = 100/1 = 100、つまりData/Ram。これはData/Ram、元のチャンクの数であったためです。2パスの場合、Data/RamB＃チャンクのAグループに分割します。

ここで式を分解してみます。D=データ、A =＃グループ、B =＃チャンク/グループ、R=RAMとします。

A*(D/R)*(B+1) + 1*(D/R)*(A+1)-これは、B#chunksでの外部マージの読み取り数とA#chunksでの最終マージのA倍です。

A = D/(R*B) => D^2/(B*R^2) * (B+1) + D/R * (D/(R*B)+1)

(D^2/R^2)*[1 + 2/B] + D/R2パス外部マージの読み取り数です。1パスの場合、1パスの(data/ram)*(chunks+1)チャンク=データ/RAMです。したがって、1つのパスに対してD^2/R^2 + D/R。チャンクサイズBが無限大になると、2パスがそれに達するだけであり、それでも追加の最終マージによってが得られD^2/R^2 + D/Rます。ですから、私が見逃している読み取りについて何かがあるに違いありません。さもないと、私の数学に欠陥があります。私を助けるために時間を割いてくれた人に感謝します！

4

2 に答える 2

3

ディスクからデータのブロックを読み取るのにかかる合計時間が合計であるという事実を無視します

  • ハードディスクドライブを回転させるためのアクセス時間はほぼ一定で、数ミリ秒のオーダーです。
  • データブロックのサイズと転送速度に依存する転送時間。

チャンクの数が増えると、入力バッファー（バケットと呼びます）のサイズが小さくなります。入力バッファが小さいほど、バッファを埋めるのにかかる合計時間に対する一定のアクセス時間の影響がより顕著になります。ある時点で、バッファをいっぱいにする時間は、アクセス時間によってほぼ完全に支配されます。したがって、マージパスの合計時間は、読み取られたデータの量ではなく、バッファーの数に比例し始めます。

ここで、追加のマージパスによってプロセスを高速化できます。これにより、使用する入力バッファーの数を減らしたり増やしたりして、アクセス時間の影響を軽減できます。

編集：これは、損益分岐点がどこにあるかについてのアイデアを与えるための封筒裏の簡単な計算です。

総転送時間は簡単に計算できます。すべてのデータは、パスごとに1回読み書きする必要があります。

total_transfer_time = num_passes * 2 * data / transfer_rate

バッファ読み取りの合計アクセス時間は次のとおりです。

total_access_time = num_passes * num_buffer_reads * access_time

出力バッファは1つしかないため、メモリを無駄にすることなく入力バッファよりも大きくすることができます。したがって、書き込みのアクセス時間は無視します。バッファ読み取りの数はdata / buffer_size、バッファサイズは約ram / num_chunksワンパスアプローチであり、チャンクの数はですdata / ram。だから私たちは持っています：

total_access_time1 = num_chunks^2 * access_time

sqrt(num_chunks)2パスソリューションの場合、アクセス時間を最小限に抑えるためにバッファを使用することは理にかなっています。したがって、バッファサイズはram / sqrt(num_chunks)次のようになります。

total_access_time2 = 2 * (data / (ram / sqrt(num_chunks))) * acccess_time
                   = 2 * num_chunks^1.5 * access_time

したがって、、、、を使用するとtransfer_rate = 100 MB/s、access_time = 10 ms合計時間は次のようになります。data = 100 GBram = 1 GB

total_time1 = (2 * 100 GB / 100 MB/s) + 100^2 * 10 ms
            = 2000 s + 100 s = 2100 s
total_time2 = (2 * 2 * 100 GB / 100 MB/s) + 2 * 100^1.5 * 10 ms
            = 4000 s + 20 s = 4020 s

アクセス時間の影響はまだ非常に小さいです。それでは、データを1000GBに変更しましょう。

total_time1 = (2 * 1000 GB / 100 MB/s) + 1000^2 * 10 ms
            = 20000 s + 10000 s = 30000 s
total_time2 = (2 * 2 * 1000 GB / 100 MB/s) + 2 * 1000^1.5 * 10 ms
            = 40000 s + 632 s = 40632 s

現在、ワンパスバージョンの半分の時間はディスクシークに費やされています。5000GBで試してみましょう。

total_time1 = (2 * 5000 GB / 100 MB/s) + 5000^2 * 10 ms
            = 100000 s + 250000 s = 350000 s
total_time2 = (2 * 2 * 5000 GB / 100 MB/s) + 2 * 5000^1.5 * 10 ms
            = 200000 s + 7071 s = 207071 s

これで、2パスバージョンが高速になりました。

于 2013-03-23T13:10:20.310 に答える
2

最適なものを得るには、ディスクのより洗練されたモデルが必要です。サイズのブロックを埋める時間Sは、シーク時間と読み取り速度です。rS + kkr

MサイズのRAMをサイズのC+1バッファに分割するとM/(C+1)、RAMを1回ロードする時間は(C+1) (r M/(C+1) + k)=rM + k(C+1)です。したがって、ご想像のとおり、Cシークを排除することで、読み取り時間を短縮できます。1つのシーケンシャルブロックですべてのメモリを読み取るのが最速ですが、マージでは許可されません。トレードオフを行う必要があります。そこで、最適なものを探す必要があります。

合計データサイズにcRAMサイズをc掛けると、マージされるチャンクがあります。

ワンパススキームでは、、、C=cおよび合計読み取り時間は、RAM時間をいっぱいにする時間である必要がありcますc (rM + k(c+1)) = c(rM + kc + k)。

最初のパスのデータの-way除算を使用する2パス方式ではN、そのパスにはがC=c/Nあり、2番目のパスではC=N。したがって、総コストは

c ( rM + k(c/N+1) ) + c ( rM + k(N+1) ) = c ( 2rM + k(c/N + N) + 2k )

このモデルでは書き込み時間が省略されていることに注意してください。別のデバイスでI/Oが重複していると想定しているため、無視できる場合を除いて、最終的にはこれを入力する必要があります。

ここで、cとkが適切に大きい場合、2パスモデルのc/N+N項は1パスの項に比べて非常に小さいためc、2パスモデルの方が高速になることを理解するのは難しいことではありません。

ここで停止しますが、このロジックを続行して、（おそらく）任意のパス数の閉じた近似式を取得できます。これには、無限級数を解く必要があります。次に、導関数をゼロに設定し、最適なパス数の推定値を求めて解くことができます。寿命が良ければN、パス番号の2次元関数の勾配Nをゼロに設定することでの最適値も学習します。私の直感は言うN ~ sqrt(c)。

数学が手に負えなくなった場合でも、最初に上記のような単純な代数を使用して、妥当な範囲のパス数をシミュレートし、その方法で最適なものを選択することができます。

これは興味深い問題であり、申し訳ありませんが、現時点でこれに取り組む時間がありません。分析フレームワークが、素晴らしい結果に到達するのに十分であることを願っています。

于 2013-03-24T01:23:16.593 に答える