機械学習とニューラルネットワーク - ページ 30

[MetaQuotes]

講義 11. ストレージの割り当て

講義 11. ストレージの割り当て

このビデオでは、講師がストレージの割り当てについて説明し、メモリの割り当てと解放の両方をカバーしています。スタックやヒープ、固定および可変サイズの割り当てスキームなど、さまざまなタイプのストレージが扱われています。ディスクページごとのフリーリストやビットマップなどのソリューションを使用して、メモリブロックが分散することによって引き起こされる外部フラグメンテーションについても説明します。参照カウントやこのアルゴリズムの制限など、ガベージ コレクションの概念も紹介されています。 「マーク アンド スイープ」および「ストップ アンド コピー」ガベージ コレクション手順についても説明し、後者がフラグメンテーションにどのように対処するか、およびポインターの更新によって生じる可能性のある正確性の問題に焦点を当てています。このビデオは、ストップ アンド コピー アルゴリズムの時間と空間の複雑さと、外部フラグメンテーションの排除に関するメモで締めくくられています。

このビデオでは、バディ システム、マークとスイープの手順、最適化、世代別およびリアルタイムのガベージ コレクション、マルチスレッド ストレージ割り当て、並列ガベージ コレクションなど、動的ストレージ割り当てに関連するさまざまなトピックについて説明します。講師は、世代別ガベージ コレクションは、若いオブジェクトがより頻繁にスキャンされるという考えに基づいていると説明しています。一方、リアルタイム ガベージ コレクションは、プログラムの実行中にバックグラウンドで実行されますが、オブジェクトとポインター グラフが変化し続けると、正確性の問題が発生する可能性があります。最後に、スタックやヒープなどのさまざまな種類のストレージ割り当てと、参照カウント、マーク アンド スイープ、ストップ アンド コピーなどのガベージ コレクションのさまざまな方法についてまとめます。講師は、学生は今後の宿題でこれらの方法のいくつかを試すことができると述べています.

• 00:00:00 このセクションでは、講師がストレージの割り当てについて説明します。これには、メモリの割り当てと解放の両方が含まれます。ストレージの最も単純な形式はスタックです。この場合、メモリはスタック ポインターをインクリメントすることによって割り当てられ、スタック ポインターをデクリメントすることによって解放されます。ただし、最後に割り当てられたものしか解放できず、使用済み領域の途中にあるものは解放できないため、スタックの適用範囲は限られています。講師はまた、効率上の理由から、通常、スタック オーバーフローはコンパイラによってチェックされないことに注意しています。
  
  
• 00:05:00 このセクションでは、講師はスタックとヒープの 2 種類のストレージについて説明します。スタックは固定サイズのストレージであり、効率的ですが、すべてに使用できるわけではありません。一方、ヒープはより一般的ですが、整理して効率的に使用するのは困難です。ヒープ割り当てには、malloc および free C 関数を使用できますが、C および C++ はガベージ コレクターを提供しないため、プログラマーは自分でメモリを管理する必要があり、メモリ リーク、ダングリング ポインター、および二重解放につながる可能性があります。講師は、アドレス サニタイザーや Valgrind などのメモリ チェッカーを使用して、プログラム内のメモリ バグの数を減らすことを提案しています。
  
  
• 00:10:00 このセクションでは、スピーカーはストレージを割り当てるさまざまな方法について説明します。固定サイズの割り当てから始めます。固定サイズの割り当てでは、ストレージの各部分が同じサイズで、一部のブロックが使用され、他のブロックは使用されていません。未使用のブロックは、フリー リストと呼ばれるリストに保持されます。フリー リスト内の各ブロックには、リスト内の次のブロックへのポインタがあります。フリー リストから 1 つのオブジェクトを割り当てるために、プログラムはポインターをフリーに設定し、次にフリー リスト内の次のものを指すようにフリー ポインターを設定し、フリー リスト内の最初のオブジェクトへのポインターを返します。割り当てを解除するには、オブジェクトの次のポインターを解放するように設定し、解放するオブジェクトと同じように解放を設定します。フリーリストを使用すると、割り当てと解放に一定の時間がかかり、時間的局所性も良好になります。
   
  
• 00:15:00 このセクションでは、外部フラグメンテーションの概念が導入されています。これは、使用済みメモリのブロックがすべてのメモリの空間全体に広がっているときに発生します。これにより、ページ テーブルが大きくなり、ディスクのスラッシングが発生し、翻訳の検索効率が低下する可能性があります。外部の断片化を軽減するために、ディスク ページごとの空きリストまたはビットマップを使用できます。また、最もいっぱいのページから割り当て、ストーリーのブロックを解放し、空のページをページアウトすることができます。固定サイズのヒープ割り当ては、外部の断片化を減らすのにも役立ちます。最後に、可変サイズのヒープ割り当てをビンの空きリストで使用できます。これは、割り当てられたメモリのさまざまなサイズの空きリストの効率を活用します。
  
  
• 00:20:00 このセクションでは、メモリ割り当てシステムでさまざまなサイズのメモリ ブロックを格納するためのスキームを示します。このスキームでは、ブロックをサイズに基づいてビンに分割し、各ビンには 2 のべき乗である指定されたサイズのブロックを保持します。メモリを割り当てるとき、要求されたサイズに基づいて適切なビンが選択され、それが空の場合は、より大きな空でないビンがより小さなチャンクに分割されて、目的のサイズが取得されます。ただし、この方式ではメモリの内部断片化が発生する可能性があり、無駄が生じるため、使用されるビンの数が制限され、小さなブロックがページにグループ化されてオーバーヘッドが削減されます。必要に応じて、オペレーティング システムを使用してより多くのメモリを提供できます。また、この目的で使用できるシステム コールがあります。
  
  
• 00:25:00 このセクションでは、ビデオでメモリ割り当てのしくみについて説明し、「malloc」の標準実装がオペレーティング システムからメモリを取得するために「break」などのコマンドに依存していることに注意します。 OS は大量のメモリを提供し、それを小さなブロックに分割するのはストレージ割り当てシステム次第です。このセクションでは、ブロック サイズを格納するためのさまざまなスキームや、プログラム内での仮想メモリ アドレス空間の配置方法など、メモリ アロケータのバリエーションについても説明します。スタックとヒープは互いに向かって成長しますが、交差することはありません。最後に、プログラム内の定数の大きなテーブルを事前に計算すると、データ セグメントからの読み取りが必要になるため、読み込み時間が長くなる可能性があることが言及されています。
  
  
• 00:30:00 このセクションでは、仮想メモリの断片化の問題について説明します。これは、外部の断片化、ページ テーブルのパフォーマンスの低下、ディスクのスラッシング、およびメモリが分散している場合の TLB ヒット率の低下につながる可能性があります。ストレージ割り当ての目標は、メモリの使用部分をコンパクトに保ちながら、できるだけ少ない仮想メモリを使用することです。ヒープ ストレージによって消費される仮想メモリの量の上限は M log M であるという定理を使用して、ビン フリー リスト割り当てスキームが分析されます。小さなブロックを大きなブロックに結合すると、ビン フリー リスト スキームを改善できますが、 Charles Leiserson の論文によると、この方法は標準のビン フリー リスト アルゴリズムと比較して高くなる可能性があります。
  
  
• 00:35:00 このセクションでは、スピーカーはストレージ割り当ての概念と、ヒープ ストレージを処理する際の断片化をどのように減らすことができるかについて説明します。彼はまた、ガベージ コレクションのアイデアについても説明しています。これにより、プログラマはオブジェクトを手動で解放する必要がなくなります。講演者は、3 種類のメモリ オブジェクト (ルート、ライブ オブジェクト、デッド オブジェクト) と、ガベージ コレクションが後者をリサイクルする方法について説明します。最後に、オブジェクトを参照するポインターの数をカウントして、オブジェクトを解放できるかどうかを判断する単純な形式のガベージ コレクションである参照カウントについて説明します。
  
  
• 00:40:00 このセクションでは、スピーカーはガベージ コレクション スキームとしての参照カウントの概念を紹介し、参照カウント アルゴリズムがどのように機能するかを説明します。ただし、参照グラフのサイクルを収集できないというアルゴリズムの制限が指摘されています。次にスピーカーは、この制限を回避するために、一部のプログラミング言語でのストロング ポインターとウィーク ポインターの使用について説明します。最後に、講演者は、参照グラフでサイクルを処理する際の参照カウントの制限を回避する、「マーク アンド スイープ」と「ストップ アンド コピー」という 2 つのガベージ コレクション スキームをプレビューします。
  
  
• 00:45:00 このセクションでは、スピーカーは幅優先探索アルゴリズムを使用してメモリ内のすべてのライブ オブジェクトを検索する方法について説明します。検索用の FIFO キューを表すために 2 つのポインターを含む配列が使用され、アルゴリズムはルートから到達可能な各ライブ オブジェクトをマークします。検索が完了すると、マークされていないオブジェクトはガベージ コレクションに使用できるようになります。マークアンドスイープ手順には、幅優先探索アルゴリズムを含むマーク段階と、メモリをスキャンしてマークされていないオブジェクトを解放するスイープ段階の 2 つの段階があります。ただし、このスキームには制限があります。たとえば、すべてのメモリをスキャンする必要があることや、参照されていないオブジェクトを参照することに関連するオーバーヘッドがあります。
  
  
• 00:50:00 このセクションのビデオでは、断片化を処理する「ストップ アンド コピー」ガベージ コレクション手順を紹介しています。この手順は、マーク アンド スイープ アルゴリズムに似ていますが、ライブ オブジェクトがメモリ内で連続していることを確認するために異なるアプローチをとります。この手順では、from 空間と to 空間の 2 つの別個のメモリ空間を使用し、from 空間がいっぱいになるまで、そこからオブジェクトを割り当てて解放します。次に、ガベージ コレクション アルゴリズムが実行され、2 つの領域が幅優先検索のキューとして使用され、2 つの領域のメモリ内に連続して配置されるライブ オブジェクトが識別されます。ただし、このアルゴリズムを使用すると、from 空間内のオブジェクトを指すポインターが正しくなくなる可能性があるという、正確性の問題が発生する可能性があります。これに対処するために、プロシージャは、from 空間の対応するオブジェクトに転送ポインターを格納し、幅優先検索でキューからオブジェクトを削除するときに、これらの転送ポインターをたどってすべてのポインターを更新します。
  
  
• 00:55:00 このセクションでは、スピーカーは、ストップ アンド コピー ガベージ コレクション アルゴリズム、その時間の複雑さ、および外部フラグメンテーションの処理方法について説明します。停止およびコピー アルゴリズムでは、オブジェクトを from 空間から to 空間にコピーし、to 空間でこれらのオブジェクトのポインターを更新します。このアルゴリズムは時間と空間の線形であるため、より効率的で効果的なガベージ コレクションの方法になります。 from スペースがいっぱいになると、ユーザーは新しいヒープ スペースを要求して、from スペースのサイズを 2 倍にすることができます。このスキームが必要とする仮想メモリ空間は最適な一定倍であり、このアルゴリズムは外部の断片化を排除します。
  
  
• 01:00:00 このセクションでは、スピーカーは、合体を行うためのバディ システム、マーク アンド スイープ手順のバリエーション、パフォーマンスを向上させるための最適化、世代別ガベージ コレクション、リアルタイム ガベージ コレクションなど、動的ストレージ割り当てに関連するトピックについて説明します。 、マルチスレッド ストレージ割り当て、並列ガベージ コレクション。世代別ガベージ コレクションは、多くのオブジェクトは存続期間が短いため、ほとんどの場合、若いオブジェクトのみがスキャンされるという考えに基づいています。リアルタイム ガベージ コレクションは、プログラムの実行中にバックグラウンドで動作しますが、オブジェクトとポインターのグラフが変化すると、正確性の問題が発生する可能性があります。マルチスレッドのストレージ割り当てと並列ガベージ コレクションでは、複数のスレッドが実行されているため、競合やその他の正確性の問題にアルゴリズムが対処しにくくなっています。また、スピーカーは、スタックとヒープを含むさまざまな種類のストレージ割り当てと、参照カウント、マーク アンド スイープ、ストップ アンド コピーなどのガベージ コレクションのさまざまな方法についても要約します。
  
  
• 01:05:00 このセクションで、インストラクターは、ストレージ割り当てスキームをさらに掘り下げ、学生が今後の宿題でそれらのいくつかを試す機会があると述べました.その後、インストラクターは講義を終了し、さらなる質問のためにフロアを開きました。

[MetaQuotes]

講義 12. 並列ストレージ割り当て

講義 12. 並列ストレージ割り当て

このビデオでは、さまざまなメモリ割り当て戦略とそのトレードオフについて説明しています。 malloc とアラインされた割り当ての使用、および free による適切なメモリ割り当て解除の重要性が説明されています。外部の断片化とパフォーマンスの低下の問題とともに、仮想メモリの割り当てに Mmap を使用する方法についても説明します。 C および C++ プログラミングにおけるスタックの概念が調査され、スタック フレームを割り当てるためのヒープベースのサボテン スタック アプローチに重点が置かれています。断片化を最小限に抑えるために小さなブロックを最適化することの重要性とともに、線形スタックのプールの使用についても説明します。このビデオは、グローバルおよびローカル ヒープ アプローチとそれらの潜在的な問題、およびこれらの問題に対処するためのビン フリー リストや定期的なメモリ リバランスなどのアプローチについての議論で締めくくられています。

このビデオでは、並列ストレージ割り当てのソリューションについても説明し、ソリューションとして Hoard アロケーターを紹介しています。 Hoard アロケーターは、ローカル ヒープとグローバル ヒープ、およびヒープ間で移動できる大きなスーパー ブロックの組み合わせを使用して、偽共有を減らし、スケーラビリティを向上させ、外部の断片化を減らします。グローバル ヒープに割り当てられる最大ストレージは、最大でローカル ヒープに割り当てられる最大ストレージであり、フットプリントの上限は、ユーザー フットプリントとローカル ヒープ内の割り当て済みで未使用のストレージです。このビデオでは、Je malloc や Super malloc などの他のアロケーターについても簡単に説明しています。ベンチマークの結果は、Super malloc が Je malloc や Hoard よりもパフォーマンスが優れていることを示しています。ディスカッションは、ガベージ コレクションの詳細についてオンライン スライドを参照して締めくくります。

• 00:00:00 このセクションでは、講師が malloc やアライン割り当てなどのメモリ割り当てプリミティブを確認します。アラインされた割り当てを使用してメモリをキャッシュ ラインにアラインし、キャッシュ ライン内のオブジェクトへのアクセスが 1 回のキャッシュ アクセスのみで済むようにして、キャッシュ ミスの数を減らすことができます。また講師は、free 関数を使用してメモリを適切に解放し、メモリ リークや二重解放を回避することの重要性についても説明します。最後に、講師は、バッキング ファイルなしで仮想メモリを割り当てるために使用できるシステム コール Mmap を紹介します。
  
  
• 00:05:00 このセクションでは、スピーカーは M マップを使用してメモリを割り当てるプロセスを説明します。これは、要求されたメモリ サイズを保持するのに十分な大きさのアプリケーションのアドレス空間で連続した未使用領域を見つけて更新するシステム コールです。割り当てられたページのエントリを含むページ テーブル。ライブラリ呼び出しであり、C ライブラリのヒープ管理コードの一部である malloc とは異なり、M マップは、要求されたメモリに物理メモリをすぐに割り当てませんが、ページ テーブルに、変更された特別なゼロ ページを指すエントリを設定します。ユーザーが最初に書き込むときにのみ、物理メモリに変換されます。さらに、M map はオペレーティング システムからメモリを取得する役割を担い、malloc は以前に割り当てられたメモリを再利用して断片化を減らし、一時的な局所性を向上させる役割を果たします。
  
  
• 00:10:00 このセクションのビデオでは、ストレージ割り当てに MMAP と MALLOC を使用する場合の違いについて説明し、MMAP は比較的重量が大きく、小さな割り当てでもページ全体を割り当てるため、外部の断片化とパフォーマンスの低下につながることを強調しています。このビデオでは、仮想アドレスを使用してメモリにアクセスし、ハードウェアがページ テーブルで適切な物理アドレスを検索するアドレス変換のプロセスについても説明します。このビデオでは、最近のページ テーブル ルックアップをキャッシュすることで TLB がどのように機能するかを説明し、空間的または時間的な局所性を持つプログラムでは、TLB に多くの最近のアクセスが格納されるため、パフォーマンスが向上することに注意してください。
  
  
• 00:15:00 このセクションでは、講演者は最新のマシンでアドレス変換がどのように機能するかについて説明し、C および C++ プログラミングにおけるスタックの概念についても掘り下げます。スタックは、関数呼び出しとローカル変数を追跡し、線形の順序に従うために使用されます。スピーカーは、従来の線形スタックにおけるポインターの 1 つの規則を強調しています。変数の上書きを避けるために、親はスタック変数へのポインターを子に渡すことができますが、その逆はできません。スピーカーは、ヒープまたは親のスタックにメモリを割り当てるなど、子関数から親にメモリを渡すためのオプションも提案します。
  
  
• 00:20:00 並列ヒープの割り当ては正しいです。ヒープベースのサボテン スタックを使用する際の潜在的な問題は、メモリの断片化です。将来の割り当てのために十分な連続したメモリが残っていない可能性があり、スペースが無駄になり、場合によっては不足する可能性がありますメモリまたはプログラムのクラッシュ。並列プログラミングの初期のシステムではこの戦略が使用されていましたが、コードを最適化してパフォーマンスへの影響を最小限に抑え、メモリの断片化の結果を考慮することが重要です。
  
  
• 00:25:00 このセクションのビデオでは、最大深度に上限を設けずにスタック フレームを割り当てるためのヒープベースのサボテン スタック アプローチの使用について説明しています。ただし、このヒープベースのサボテン スタックで従来の線形スタック コードを使用しようとすると、相互運用性が問題になります。これは、スレッド ローカル メモリ マッピングと呼ばれるアプローチを使用して修正できますが、このアプローチではオペレーティング システムを変更する必要があります。それにもかかわらず、ヒープベースのサボテン スタック アプローチは実際には依然として優れており、それを使用する Silk プログラムのスペース バウンドを証明するために使用できます。このスペース バウンドは、ヒープ ベースのサボテン スタックを使用する P ワーカー実行のスタック スペースの上限が P × s1 であることを示しています。ここで、s1 は、Silk プログラムのシリアル実行に必要なスタック スペースです。これは、ヒープ ベースのサボテン スタック アプローチの優れた機能です。
  
  
• 00:30:00 このセクションでは、分割統治行列乗算コードを分析して、時空トレードオフ定理に適用する方法を理解します。このコードは、それぞれのサイズが N/2 の 8 回の再帰呼び出しを行い、各呼び出しの前に malloc を実行して、サイズが N の 2 乗のオーダーの一時スペースを取得します。この一時スペースは、関数が戻る直前に解放されます。割り当てはスタック規則に従うため、ヒープから割り当てを行う場合でも、前のスライドで制限されたスペースを使用して、P ワーカー スペースの上限を設定できます。仕事は N の 3 乗であり、スパンは N の 2 乗の対数です。したがって、ビジー リーフのプロパティとスペース バウンドの定理は、P 個のプロセッサでは、スペースは P × N の 2 乗で区切られることを示しています。
  
  
• 00:35:00 このセクションでは、スピーカーは、前のセクションで説明したアルゴリズムに限定されたより強いスペースを証明する方法を聴衆に説明します。アルゴリズムの構造を分析し、再帰ツリーの上部近くで可能な限り分岐することに焦点を当てることで、話者は、以前の上限よりも優れた、N の 2 乗の 3 分の 1 までの P の空間境界を示すことができます。 .講演者は、アルゴリズムの構造を分析すると、一般的な定理を単純に適用するよりも、空間に縛られたより強力な証明につながる可能性があると述べています。このセクションの最後に、並列関数がレガシーおよびサードパーティのシリアル バイナリと相互運用できない理由について説明します。
  
  
• 00:40:00 このセクションでは、スピーカーはストレージ割り当てにおける線形スタックのプールの使用について説明します。これは、レガシー コードのスタックのプールを維持するために使用できます。プール内のスタックの数は、プロセッサの数の定数倍にして、スペースの制限を維持する必要があります。ただし、この戦略はワーク スチール アルゴリズムの制限時間に影響を与える可能性があります。これは、使用可能なスタックがなくなるとワーカーがスチールできない可能性があるためです。次にスピーカーは、アロケーターの速度やユーザー フットプリントなど、ヒープ ストレージ アロケーターの基本的な特性について説明し、断片化や割り当てのオーバーヘッドの可能性があるため、小さなブロックを最適化することの重要性を強調します。断片化は、アロケーターのフットプリントをユーザーのフットプリントで割ったものとして定義されます。
  
  
• 00:45:00 ビデオのこのセクションでは、スピーカーは、2 つの比率を最小限に抑えるために、割り当てられたフットプリントをユーザーのフットプリントにできるだけ近づける方法について説明します。解決策の 1 つは、M アドバイスと呼ばれるものを使用することです。これは、オペレーティング システムに、メモリの特定のページが不要になったが、仮想メモリに保持する必要があることを伝えます。講演者は、ビン フリー リストのフラグメンテーションは、割り当てられたメモリの総量である U の次数ログ ベース 2 であるという前の講義の定理にも言及し、スペース オーバーヘッド、内部フラグメンテーション、および外部フラグメンテーションの違いを説明します。最後に、講演者は、最新の 64 ビット プロセッサが約 2 ～ 48 バイトの仮想アドレス空間を提供することを指摘しました。これは、ほとんどのプログラムにとって十分ですが、一般的なマシンの物理メモリよりも多くの容量があります。
  
  
• 00:50:00 このセクションのビデオでは、mutex 保護を備えたグローバル ヒープを使用した並列ヒープ割り当て戦略について説明します。これは、デフォルトの C++ アロケーターがどのように機能するかです。この戦略の欠点は、シリアル アロケーターと比較して追加のスペースを必要としないことです。ただし、このアプローチの潜在的な問題は、パフォーマンスへの影響です。割り当てと解放のたびにロックを取得するのは遅く、プロセッサが増えると悪化するからです。ロックの競合は、スケーラビリティが低い主な理由です。リクエスト レートが高いため、小さな割り当てではより問題になり、大きなブロックの割り当てではより多くの作業が必要になります。
  
  
• 00:55:00 このセクションのビデオでは、ローカル ヒープ アプローチを使用する場合の潜在的な問題について説明します。これは、メモリ ドリフトと無制限のブローアップにつながる可能性があるということです。基本的に、すべてのメモリを 1 つのスレッドに割り当てて別のスレッドで解放すると、アロケータが再利用できるほど賢くなく、システム内に未使用のメモリが存在する可能性があります。その結果、複数のプロセッサで実行されているプログラムは最終的にメモリ不足になる可能性がありますが、単一のコアでのみ実行されている場合は発生しません。このビデオでは、ビン フリー リスト アプローチを使用してこの問題に対処することを提案しています。これには、解放されたブロックがリンクされたリストの 1 つに表示されるように、ビン フリー リストのデータ構造にポインターを設定することが含まれます。もう 1 つの戦略は、メモリを定期的に再調整することですが、より簡単な方法についても説明します。
  
  
• 01:00:00 このセクションのビデオでは、メモリ アロケータを変更して、グローバル ヒープを必要とせずに各スレッドが独自のヒープにアクセスするという目的の動作を実現する方法について説明します。 1 つの方法は、各オブジェクトに所有者のラベルを付け、解放されたときに所有者のヒープに返すことです。このようにして、ローカル オブジェクトは高速に割り当てと解放を行いますが、リモート オブジェクトはある程度の同期を必要としますが、グローバル ヒープほどではありません。割り当てることができるメモリの最大量は、シーケンシャル プログラムによって使用される量である X によって制限され、ブローアップ率は、ヒープの数である P によって制限されます。このアプローチには、複数のプロセッサが同じキャッシュ ライン上の異なるメモリ位置にアクセスする場合に発生する偽共有に対する回復力もあります。
  
  
• 01:05:00 このセクションでは、スピーカーは、並列ヒープ割り当てがどのように偽共有につながるかについて説明し、ソリューションとしてホード アロケーターを紹介します。ホード アロケータは、ローカル ヒープとグローバル ヒープを組み合わせて使用し、メモリをヒープ間で移動できる大きなスーパー ブロックに編成します。このアプローチは、高速でスケーラブルで、偽の共有に対して回復力があります。割り当てが行われると、アロケーターはローカル ヒープ内の空きオブジェクトをチェックし、存在する場合はそれを取得します。そうでない場合は、より多くのメモリを取得するためにグローバル ヒープに移動します。
  
  
• 01:10:00 このセクションでは、Horde アロケーターが、フルではないスーパー ブロックからフリー オブジェクトを割り当てて、スーパー ブロックの動きを高密度化することにより、外部フラグメンテーションを削減する方法について説明します。オブジェクトがローカル ヒープに見つからない場合は、グローバル ヒープをチェックし、グローバル ヒープが空の場合は、OS から新しいスーパー ブロックを呼び出します。 Horde アロケーターは、ヒープの使用率が最大で半分になる不変条件を維持し、ヒープの使用率が低いことを検出すると、半分空のスーパーブロックをグローバル ヒープに移動します。次に、スピーカーは、グローバル ヒープに割り当てられた最大ストレージが、ローカル ヒープに割り当てられた最大ストレージであるという補題を提示します。最後に、スピーカーは、Horde アロケーターのフットプリントが u に SP を加えた順序で上限が決まるという定理を証明します。ここで、u はプログラムのユーザー フットプリントであり、SP はローカル ヒープ内の割り当てられた未使用のストレージです。次に、ブローアップは、u で割った 1 プラス次数 SP として計算されます。
   
  
• 01:15:00 このセクションでは、講演者は Je malloc や Super malloc などのさまざまなアロケーターについて説明します。 Je malloc は、さまざまな割り当てサイズに対して個別のグローバル ロックを持ち、em アドバイスを使用して空のページを解放します。これにより、さまざまな割り当てトレースに対して堅牢になります。一方、Super malloc はコード行数が非常に少なく、非常に高速に開発されています。スピーカーは、Super malloc が Horde よりも優れたパフォーマンスを発揮した J malloc よりも優れたパフォーマンスを発揮したベンチマーク結果を共有していますが、デフォルトのアロケーターはパフォーマンスが低かったです。議論はガベージ コレクションにも及びますが、スピーカーはこれの詳細をオンライン スライドに委ねます。

[MetaQuotes]

講義 13. Cilk ランタイム システム

講義 13. Cilk ランタイム システム

Cilk ランタイム システムは、ランダム化されたワーク スティーリング スケジューラを使用して実行時にプロセッサに計算をマッピングし、並列プロセッサでの計算のスケジューリングと負荷分散を担当します。このシステムは、盗むための追加コストを犠牲にしても、プログラムのシリアル実行を最適化するように設計されています。ワーカーは、スタック フレームへのポインターを含み、ヘッド ポインターとテール ポインターを使用する別のデッキ データ構造を維持します。盗むことができるフレームには、デックが呼び出しスタックの外部にある間に盗むために必要な情報を含む追加のローカル構造があります。このセクションでは、システムが実行中の関数の途中からプロセッサが実行を開始できるようにする方法と、特定のプロセッサがまだ計算の終了を待っているためにそのポイントを超えて実行できない sync ステートメントに到達すると、プロセッサ間の同期がどのように複雑になるかについて説明します。さらに、スピーカーは、システムのパフォーマンス、設計上の考慮事項とデータ構造、およびシステムが THC プロトコルを使用して実行を最適化する方法について説明します。これには、作業を実行するワーカー用と泥棒用の 2 つのプロトコル セットが含まれます。

Cilk ランタイム システムは、セット ジャンプおよびロング ジャンプ プロトコルを使用して、犠牲プロセスの実行デックからの計算の盗難を処理します。 Cactus スタックの抽象化により、泥棒プロセスは独自の呼び出しスタックを持つことができ、被害者のスタックの破損を防ぐことができます。システムの同期プロトコルは、計算ツリーと Cactus スタックを使用して、関数内のネストされた計算間でのみ同期が行われるようにします。フル フレーム ツリーは、同期プロセスを簡素化するために、未処理のサブ計算を含む計算間の親子関係を維持します。さらに、ランタイム システムは、現在の関数に未処理の子計算がなく、すべてのワーカーがビジーであるという一般的なケースを最適化します。サポートされているその他の機能には、C++ 例外、リデューサー ハイパー オブジェクト、血統などがあります。

• 00:00:00 このセクションでは、並列プロセッサでの計算のスケジューリングと負荷分散を担当する Cilk ランタイム システムについて Tibi が説明します。ランタイム システムは、ランダム化されたワーク スティーリング スケジューラを使用して、実行時に計算をプロセッサにマップし、効率的な実行を保証します。 Tibi は、Cilk ランタイム システムは複雑なソフトウェアですが、その基礎となる魔法は、Cilk コンパイラとランタイム ライブラリのコラボレーションによって実装されると述べています。さらに、コンパイル後の単純な Cilk プログラムの疑似コードを示し、Cilk のランタイム システムの基礎となる複雑なプロセスを強調しています。
  
  
• 00:05:00 このセクションでは、講演者が Cilk ランタイム システムに必要な機能と、パフォーマンスに関する考慮事項について説明します。彼は、並列化されたフィボナッチ ルーチンの例を使用して、Cilk プログラムが計算データを実行する方法を説明します。これは、プログラムが 1 つのプロセッサで実行されると動的に展開されます。ただし、silk spawn ステートメントが検出されると、3 の fib に対して新しいフレームが作成され、別のストランドが並列実行に使用可能になります。次にプロセッサは、通常の関数呼び出しであるかのように fib of 3 の実行を開始します。命令ポインターが fib ルーチンの先頭に戻ると、このプロセスが繰り返されます。
  
  
• 00:10:00 このセクションでは、Cilk ランタイム システムの助けを借りて、複数のプロセッサがどのように fib ルーチンを並行して実行するかを確認します。各プロセッサは、独立したレジスタを持っているにもかかわらず、実行中の関数の途中に飛び込んで実行を開始します。これは、Silk システムがどのようにしてプロセッサが実行中の関数の途中から実行を開始できるようにするかという問題を引き起こします。さらに、特定のプロセッサが計算の終了を待機しているため、ポイントを超えて実行できない sync ステートメントに到達すると、プロセッサ間の同期が複雑になります。これには、ネストされたパターン内でのきめ細かい同期が必要です。
  
  
• 00:15:00 このセクションでは、講演者は Cilk ランタイム システムの実装に関する考慮事項について説明します。彼らは、1 つのワーカーがプログラムを実行できること、関数の実行中にジャンプして他のプロセッサが中断したところから再開できること、同期という 3 つの主要な考慮事項について言及しています。さらに、Silk にはサボテン スタックの概念があり、スタックのすべてのビューを利用可能で一貫性のあるものにするために正しく実装する必要があります。最後に、システムは、プロセッサが相互にフレームを盗むことができるようにすることで、ワークスティーリングを許可する必要があります。
  
  
• 00:20:00 このセクションでは、講演者は Cilk ランタイム システムに必要な機能について説明します。これには、シリアル実行、実行中の関数の途中に侵入する泥棒、ネストされた細かい方法で同期するための同期、すべてのワーカーを表示し、スポーン フレームと呼び出されたフレームの混合物を処理します。次に、このセクションでは、システムのパフォーマンスについて説明します。ここでは、十分な並列処理が必要であり、T 無限大に対する T1 は P よりもはるかに大きくする必要があり、プログラムを実行するプロセッサの数を増やすと、線形の速度向上が必要になります。このセクションでは、P 個のプロセッサでの TCP の予想実行時間についても説明します。これは、計算の作業をプロセッサの数で割った値に計算のスパンのオーダーを加えたものに比例します。
  
  
• 00:25:00 このセクションでは、Cilk ランタイム システムと、十分な並列性を備えたプログラムで高い作業効率を維持するというその目的について学びます。 Silk Runtime System は、スチールの追加コストを犠牲にしても、プログラムのシリアル実行を最適化することにより、作業優先の原則に従います。ランタイム システム ライブラリは、並列実行の問題を処理し、スティールが発生したときに実行の遅いパスを処理します。ワーカーは、スタック フレームへのポインターを含み、ヘッド ポインターとテール ポインターを使用する別のデッキ データ構造を維持します。盗むことができるフレームには、デックが呼び出しスタックの外部にある間に盗むために必要な情報を含む追加のローカル構造があります。
  
  
• 00:30:00 このセクションでは、Cilk ランタイム システムの設計とその基本的なデータ構造について学びます。システムは計算ごとにスポーン ヘルパー関数を生成します。この関数は、スポーン関数とスポーン ヘルパーのインスタンス化ごとにワーカー構造と Silk スタック フレーム構造をそれぞれ維持します。 Silk RTS スタック フレームには、Silk スタック フレームの状態を要約するバッファやフラグ整数、コール スタック内の親 Silk スタック フレームへのポインタなどのフィールドが含まれています。ワーカー構造は、デックと現在の Silk RTS スタック フレームへのポインターを維持します。これらのデータ構造は、インテル® so+ ランタイム・システムが精緻化する Cilk ランタイム・システムの本質です。
  
  
• 00:35:00 このセクションのビデオでは、スポーン関数「foo」とスポーン ヘルパー関数のコードについて説明します。 「foo」のコードには、スタック フレームを初期化するための呼び出し、set jump ルーチンによるスポーンのセットアップ、スポーン ヘルパー関数「spawn bar」への呼び出し、Silk RTS のシンクの条件付きコード ブロックが含まれます。そして、クリーンアップのためにフレームをポップおよびリーフするように呼び出します。スポーン ヘルパーのコードには、スタック フレームを初期化するための呼び出しと、スタック構造の追加のクリーンアップ関数を使用して Silk RTS をデタッチするための呼び出しが含まれています。セットアップ ルーチンは、関数の場所を再開するために必要な情報を格納するためのバッファを引数として取り、泥棒が関数の継続を盗むことを可能にする関数として記述されています。
  
  
• 00:40:00 このセクションでは、スピーカーは、レジスターのセットを制限し、それらを関数呼び出し用の所定のセットに保存する方法について説明します。レジスタを保存する責任は関数にありますが、命令ポインタとスタック ポインタはバッファに保存されます。このセクションでは、スポーン ヘルパー関数と、それがワーカー構造と現在のスタック フレームを更新する方法について説明します。最後に、このセクションでは、enter frame fast ルーチンがコール スタックに親ポインターを確立し、ワーカーの現在のスタック フレームを更新して一番下を指すようにする方法について説明します。
  
  
• 00:45:00 このセクションでは、"The Cilk Runtime System" というタイトルの YouTube ビデオのトランスクリプトで、Silk RTS デタッチ関数がどのようにして計算を盗むことができるかを説明しています。シルクスポーンの続き。ポップ フレームは、スタック フレーム構造をクリーンアップし、現在のスタック フレームを更新して親を指すようにします。この関数呼び出しは返される場合と返されない場合があり、実行時システムが最適化するためにこれら 2 つのケースのどちらがより重要であるかが、最初の原則で動作する 2 つのケースに基づいて成功ケースとなります。
  
  
• 00:50:00 このセクションでは、ワーカーが通常のシリアル実行を行うと想定されるケース 1 のワーカー実行における Cilk ランタイム システムの最適化についてスピーカーが説明します。また、泥棒が被害者のデッキの一番上をターゲットにし、アイテムをデキューし、デッキの先頭と現在のスタック フレーム ポインターを更新することで、ワーカーの盗みがどのように機能するかについても説明します。生成された関数の結果は、元の SIL コードの親スタック フレームに返されます。
  
  
• 00:55:00 このセクションでは、スピーカーは、THC プロトコルと呼ばれるプロトコルを使用して、複数のプロセッサが関与する同時アクセスを処理する Cilk ランタイム システムのアプローチについて説明します。プロトコルには、作業を実行するワーカー用と泥棒用の 2 つのプロトコル セットが含まれます。労働者のプロトコルは、デッキの底から何かをポップしようとすることによって最適化され、失敗した場合にのみデッキのロックを取得しますが、泥棒はデッキ操作を実行する前に常にロックを取得します。次に、泥棒はロング ジャンプ関数を呼び出し、セット ジャンプ関数から取得したスタック フレーム バッファーを渡し、そのレジスター状態を盗まれた継続のレジスター状態に設定することによって、魔法のように盗まれた継続を再開します。
  
  
• 01:00:00 このセクションでは、Cilk ランタイム システム内でのセット ジャンプとロング ジャンプの呼び出しの相互作用について説明します。彼らは、ロング ジャンプ ルーチンが呼び出されたときに、設定されたジャンプから 2 回目に効果的に戻る方法を説明しています。今回は、2 番目の引数に別の値が指定されています。適切なバッファと 2 番目の引数を使用して、泥棒はロング ジャンプを実行し、被害者のコード内の特定の計算をスキップできます。講演者は、通話を飛び越えるために必要な距離を静的に計算し、別のアプローチを使用することは可能であると述べていますが、セット ジャンプおよびロング ジャンプ プロトコルは、Cilk ランタイム システムのより柔軟な方法として機能します。全体として、スピーカーは、泥棒が Cilk を使用して被害者のデッキから計算を盗むために利用できるさまざまな手法を強調しています。
  
  
• 01:05:00 このセクションでは、Cilk ランタイム システムのサボテン スタック抽象化の必要性について説明します。被害者のスタックを使用すると、被害者のスタックが破損し、すべてのワーカー間で一貫性を維持する上で問題が発生する可能性があると説明されています。したがって、シーフ用の別のコール スタックが必要です。サボテン スタックの実装には、泥棒が継続を盗み、スタック ポインターを自分のスタックに設定する一方で、RB p からのオフセットを介して被害者のスタック上の関数の状態にアクセスできることが含まれます。
  
  
• 01:10:00 このセクションでは、スピーカーは、SIL ランタイム システムが異なるプロセッサでの計算の同期をどのように処理するかを説明します。システムは、サボテン スタックと計算ツリーを使用して、一般的なプログラムではなく、関数の下にネストされたサブ計算間でのみ同期が行われるようにします。すべてのサブ計算が戻る前にワーカーがシルク同期ステートメントに到達すると、ワーカーは泥棒になり、盗まれた計算のスタック フレームで作業を続けます。これにより、システムはワーカーの浪費を回避し、ネストされた計算が適切に同期されるようにすることができます。システムは、このアプローチと競合する可能性のある最適化を使用しないようにコンパイラに明確に指示します。
  
  
• 01:15:00 このセクションでは、Cilk ランタイム システムは、フル フレームと呼ばれる状態のツリーを維持するものとして説明されています。これは、どの計算が他のどの計算の完了を待っているかを追跡します。このシステムは、完全なフレーム ツリーを使用して、並列実行のための情報の負荷を追跡します。これには、親フレームへのポインター、場合によっては子フレームへのポインター、および未処理のサブ計算が互いにどのように関連しているかが含まれます。ワーカーが同期に遭遇したとき、未処理の子計算がある場合、ワーカーは同期できず、より多くの作業を盗む泥棒になるまでフレーム全体を一時停止する必要があります。このシステムにより、プログラムは十分な並列性を持つことができ、同期プロトコルが簡素化されます。
  
  
• 01:20:00 このセクションでは、実行中の関数に未処理の子がなく、システム上のすべてのワーカーがそれぞれのタスクで忙しいという一般的なケースを、Cilk ランタイム システムがどのように最適化するかについて説明します。ランタイム システムは、関連するスタック フレームのフラグ フィールドのビットを使用して、シルク同期に同期が必要かどうかを評価します。講演者は、C++ 例外、リデューサー ハイパー オブジェクト、血統など、ランタイム システムでサポートされているその他の機能についても言及しています。

[MetaQuotes]

講義 14. キャッシングとキャッシュ効率の良いアルゴリズム

講義 14. キャッシングとキャッシュ効率の良いアルゴリズム

キャッシングとキャッシュ効率の高いアルゴリズムに関するビデオで、講師は最新のマシンのキャッシュ階層、完全連想キャッシュとダイレクト マップ キャッシュの違い、セット アソシエイティブ キャッシュの長所と短所について説明します。このビデオでは、理想的なキャッシュ モデルとキャッシュ効率の高いアルゴリズムの概念についても紹介しています。スピーカーは、キャッシュ ミスの補題、tall キャッシュの仮定、およびサブマトリックス キャッシングの補題について説明します。また、サブマトリックスの読み取り時およびマトリックスの乗算中に発生したキャッシュ ミスも分析します。このビデオは、タイル化された行列乗算の概念と、それがパフォーマンスを大幅に向上させる方法を紹介することで締めくくられていますが、移植性がなく、複数レベルのキャッシュを最適化するにはコストがかかる可能性があることにも注意してください。

この講義では、例として再帰的な行列の乗算を使用して、キャッシングとキャッシュ効率の高いアルゴリズムについて説明します。講演者は、ワーク ミスとキャッシュ ミスの両方を個別に分析することの重要性を強調し、キャッシュ サイズが異なるため、キャッシュ対応アルゴリズムがすべてのマシンに最適ではない可能性があることに注意します。講演者は、任意のキャッシュ サイズに合わせて自動調整するキャッシュ無視アルゴリズムについても説明し、並列キャッシュ無視コードの開発について言及します。最後に、目標は、キャッシュ認識またはキャッシュ無視のアルゴリズムを設計することです。キャッシュ無視アルゴリズムの設計に関する議論は、次の講義で続けます。

• 00:00:00 キャッシングとキャッシュ効率の高いアルゴリズムに関するこのセクションでは、インストラクターが最新のマシンのキャッシュ階層について説明します。これには、各プロセッサのプライベート L1 データと命令キャッシュ、プライベート L2 キャッシュ、および最終レベルのキャッシュが含まれます。すべてのプロセッサ間で共有されます。これらのキャッシュのサイズは、メモリ階層が上がるにつれて大きくなり、DRAM が最も低速で最大になります。キャッシュとレイテンシーの連想性も、メモリ階層が上に移動するにつれて増加し、L1 キャッシュが最も高速で最も連想的です。インストラクターは、並列処理のためのメモリ アドレス アクセスの一貫性を確保するためのキャッシュ コヒーレンス プロトコルの重要性についても言及しています。プログラムで局所性を利用する方法を理解すると、より高速なメモリ キャッシュを効率的に使用するのに役立ちます。
  
  
• 00:05:00 このセクションでは、完全連想キャッシュとダイレクト マップ キャッシュの違いについて説明します。完全連想キャッシュでは、ブロックを見つけるためにキャッシュ全体を検索する必要がありますが、ブロックを見つけるには複数の行にアクセスする必要があるため、遅くて非効率的です。一方、ダイレクト マップ キャッシュでは、ブロックごとに可能な場所が 1 つしかないため、ブロックへのアクセスがはるかに高速になり、競合が少なくなります。アドレス空間の 3 つの要素であるオフセット、セット、およびタグについても、仮想メモリ アドレスを分割してキャッシュ ブロックの位置を決定する際に説明します。タグは、キャッシュ ブロックがどのメモリ ブロックに対応するかを識別し、セットは、W ビットの合計アドレス空間で、キャッシュ内のどの位置にブロックが入るかを決定します。
  
  
• 00:10:00 このセクションのビデオでは、ダイレクト マップ キャッシュの長所と短所について説明します。ダイレクト マップ キャッシュはキャッシュ内の 1 つの場所のみを検索する必要があるため高速ですが、キャッシュ ブロックが互いに排除し続ける競合ミスが発生しやすく、パフォーマンスを低下させます。次にビデオでは、各セットに複数のラインが含まれるハイブリッド ソリューションであるセット連想キャッシュを紹介し、キャッシュ ブロックごとにキャッシュ内の複数の場所を許可します。このビデオでは、キャッシュ ブロックに初めてアクセスしたときに発生し、回避できないコールド ミスを含む、さまざまなタイプのキャッシュ ミスの分類についても言及しています。
  
  
• 00:15:00 このセクションのビデオでは、キャパシティ ミス、競合ミス、共有ミスなど、さまざまな種類のキャッシュ ミスについて説明します。キャパシティ ミスは、キャッシュがいっぱいで、アクセスする必要のあるすべてのキャッシュ ブロックに収まらない場合に発生します。一方、セット連想キャッシュでは、同じセット マップからキャッシュにマップされるブロックが多すぎる場合に競合ミスが発生します。最後に、複数のプロセッサが同じキャッシュ ラインにアクセスし、そのうちの少なくとも 1 つがそれに書き込みを行っている場合、並列コンテキストで共有ミスが発生します。このビデオは、行優先順で格納された大きな行列内のサブ行列にアクセスするときに競合ミスが発生するという悪い例も示しています。
  
  
• 00:20:00 このセクションでは、スピーカーはキャッシングとキャッシュ効率の高いアルゴリズムについて説明します。彼らは、より大きなマトリックス内のサブマトリックスにアクセスする例と、キャッシュが 4 ウェイ アソシアティブのみの場合に競合ミスがどのように発生するかを使用しています。スピーカーは、行列の各行の末尾に一定量のスペースを追加することを提案しています。これにより、各行が 2^15 バイトよりも長くなり、競合ミスを減らすのに役立ちます。
  
  
• 00:25:00 このセクションでは、スピーカーは、アルゴリズムのキャッシュ パフォーマンスを分析するために使用されるモデルである理想的なキャッシュ モデルについて説明します。このモデルは、2 レベルのキャッシュ階層、完全な連想キャッシュ、および最適な Nishant 置換ポリシーを想定しています。講演者は、重要な 2 つのパフォーマンス測定値は、N の次数とキャッシュ ミスの数であると説明しています。理想的なシナリオは、従来の標準アルゴリズムから作業を増やすことなく、キャッシュ ミスの数を減らすことです。 1985 年に証明された LRU レンマも言及されており、サイズ M の理想的なキャッシュで Q キャッシュ ミスが発生するアルゴリズムは、LRU ポリシーを使用するサイズ 2M の完全連想キャッシュで 2Q キャッシュ ミスが発生することを示しています。
  
  
• 00:30:00 このセクションでは、講演者はキャッシュ効率の高いアルゴリズムの概念と、キャッシュ ミスの数を最小限に抑えることでプログラムのパフォーマンスを向上させる方法を紹介します。彼は、LRU を使用した理想的なキャッシュの 2 倍のサイズの完全連想キャッシュは、キャッシュ ミスの数が 2 倍を超えないことを示す、LRU (Least Recent Used) 置換ポリシーについて説明しています。これにより、漸近分析を実行する際のキャッシュ ミスの分析が容易になります。講演者は、キャッシュ ミスの補題も提示します。プログラムが、サイズがキャッシュ サイズの 3 分の 1 未満で、平均サイズが少なくともキャッシュ ラインのサイズであるデータ セグメントのセットを読み取る場合、それらをすべて読み取るためのキャッシュ ミスは、キャッシュ ラインのサイズで割ったセグメントの合計サイズの最大 3 倍です。
  
  
• 00:35:00 このセクションのビデオでは、キャッシングに関連する 2 つの仮定、つまりキャッシュ ミス レンマとトール キャッシュの仮定について説明します。キャッシュ ミス レンマは、データ セグメントの平均長がキャッシュ ブロック サイズよりも大きい場合、キャッシュ ミスの数が一定の係数だけ増加することを示しています。背の高いキャッシュの仮定は、キャッシュが幅よりも高いことを前提としており、通常は実際に満たされます。このビデオでは、サブマトリックス キャッシング レンマについても説明しています。この補題では、サブマトリックスをキャッシュ ラインに適合させる際のショート キャッシュの問題と、この問題の解決にトール キャッシュの仮定が役立つ理由について説明しています。
  
  
• 00:40:00 このセクションでは、スピーカーはキャッシングとキャッシュ効率の高いアルゴリズムについて説明します。彼らは、正方部分行列をキャッシュに読み込むときに発生したキャッシュ ミスの数を分析し、キャッシュ ミス補題を使用して、行列のすべての要素をキャッシュに読み込むのに必要なキャッシュ ミスの数が最大で 3n^2/B であることを示します。 .次に、標準の 3 次作業行列乗算アルゴリズムで発生したキャッシュ ミスの数を分析し、行列が行優先順であり、tall キャッシュの仮定を満たしていると仮定します。彼らは 3 つのケースを検討し、2 番目と 3 番目のケースでは LRU を想定しており、アルゴリズム設計におけるキャッシュ最適化の重要性を最終的に示しています。
  
  
• 00:45:00 このセクションでは、スピーカーはキャッシングとキャッシュ効率の高いアルゴリズムについて説明します。彼らは行列乗算の 2 つのケースを分析します。ここで、n は B に対する M より大きい場合と、n が B に対する M の C 倍より小さい場合です。彼らは LRU 置換ポリシーを使用し、行列 B にアクセスするときに発生するキャッシュ ミスの数を計算します。その場合、彼らは n キューブのキャッシュ ミスのシータが必要であることを発見し、その結果、アルゴリズムに局所性を持たせることによる利益は得られません。 2 番目のケースでは、空間的局所性を利用して、キャッシュ ミスの数を B 倍に減らすことができます。その結果、B キャッシュ ミスに対して n の 3 乗のシータが得られ、より効率的になります。
  
  
• 00:50:00 ビデオのこのセクションでは、スピーカーはキャッシングとキャッシュ効率の高いアルゴリズムについて説明します。彼らは最初に、行列全体がキャッシュに収まるケースを分析し、B の n の 2 乗のシータの合計数のキャッシュ ミスが発生するようにします。キャッシュ ミスの合計数を B の n の 3 乗のシータに減らすことができます。ただし、タイルをループするために 6 つの for ループが使用され、サブごとに計算が行われるタイリングと呼ばれる最適化を使用することで、より良い結果が得られる可能性があることに注目しています。 -matrix を実行してから、次に進みます。サイズが s × s の部分行列の作業は s の 3 乗になります。
  
  
• 00:55:00 このセクションでは、タイル行列乗算の概念を紹介し、詳細に説明します。このアルゴリズムの目標は、部分行列をキャッシュに適合させて、すべての計算をキャッシュ内で実行でき、キャッシュ ミスが発生しないようにすることです。キャッシュ ミスの数を分析すると、キャッシュ ミスの数は n/s^3 × s^2 /B、合計 n^3/B * sqrt(M) のキャッシュ ミスであることがわかります。この数値は、行列乗算コードのパフォーマンスを向上させる上で非常に重要です。ただし、このアルゴリズムには問題があります。アルゴリズムが実行されるマシンのキャッシュ サイズに大きく依存するため、移植性がありません。さらに、複数レベルのキャッシュを最適化する場合、多次元チューニングの最適化ははるかにコストがかかり、コードはより複雑になります。
  
  
• 01:00:00 このセクションでは、キャッシングとキャッシュ効率の高いアルゴリズムについて説明します。スピーカーは、キャッシュ効率の高いアルゴリズムのパラメーターを調整し、特定のマシン用に最適化するという課題について説明します。それらは、入力行列が 4 つのサブ行列または象限に分割される再帰行列乗算アルゴリズムを導入します。出力行列の象限ごとに、2 つの行列乗算の合計が再帰的に発生します。最後に、講演者はこのアルゴリズムの作業を分析し、優れたキャッシュ パフォーマンスを維持するより単純な設計であると結論付けました。
  
  
• 01:05:00 このセクションでは、スピーカーはキャッシングとキャッシュ効率の高いアルゴリズムについて説明し、行列乗算の例を使用して、作業とキャッシュ ミスの分析の違いを説明します。スピーカーは、再帰ツリーを描画して、サイズの問題と分岐部分問題を視覚化し、葉までのレベル数が n の対数底 2 であることを指摘します。葉の数は、n の 2 を底とする対数の 8 として計算されます。これは、n の 3 乗と同じです。作業量は単純にシータ n の 3 乗です。キャッシュ ミスは、サブマトリックスがキャッシュに収まる別の基本ケースで分析され、N 2 乗のキャッシュ ミスのシータが使用されます。話者は、レベルの数が n の 2 を底とする対数だけでなく、キャッシュのサイズにも依存することを強調しています。その結果、葉の数が異なり、n のシータが m の 3 乗に 3 乗されます。
  
  
• 01:10:00 このセクションでは、スピーカーは、再帰的な行列乗算コードの例を使用して、キャッシュ効率の高いアルゴリズムでキャッシュ ミスの数を分析する方法を説明します。コードはキャッシュを無視します。つまり、キャッシュに関する明示的な知識がなく、実行中のマシンの特定のキャッシュ サイズに合わせて受動的に自動調整します。講演者はまた、今日の最良のキャッシュ無視コードは、任意の長方形行列で機能し、8 分割ではなく 2 分割を実行することにも言及しています。講演者は、並列コンテキストについて説明し、プライベート キャッシュを備えた複数のプロセッサで実行される決定論的セル計算でキャッシュ ミスの数を分析する方法を説明します。
  
  
• 01:15:00 このセクションでは、スピーカーはキャッシングとキャッシュ効率の高いアルゴリズムについて説明します。シリアル イリュージョンでキャッシュ ミスを最小限に抑えることで、低スパン アルゴリズムの並列実行でキャッシュ ミスを本質的に最小限に抑えることができます。スピーカーは、シリアル実行と同じ、並列再帰行列乗算アルゴリズムにバインドされたキャッシュ ミスを提供します。目標は、キャッシュの明示的な知識を持つ、またはキャッシュを無視するアルゴリズムを設計することです。講演者は両方の例を示し、次の講義でキャッシュ無視アルゴリズムの設計についてさらに議論する予定であると述べています。

[MetaQuotes]

講義 15. キャッシュを無視するアルゴリズム

講義 15. キャッシュを無視するアルゴリズム

このビデオでは、マシンのキャッシュ サイズを自動的に調整し、優れたキャッシュ効率を実現し、マシンのキャッシュ パラメータの知識を必要としない、キャッシュ無視アルゴリズムについて説明します。このビデオでは、2D マトリックスでステンシル法を使用して、微分方程式を通じて熱拡散をシミュレートするためのコードを記述する方法を示します。コードにはループ バージョンと台形バージョンの両方があり、後者の方がキャッシュ効率が高くなりますが、ループ コードのアクセス パターンが予測可能であるため、2D シミュレーションではそれほど高速ではありません。このビデオでは、キャッシングと並列処理の相互作用、および潜在的な並列速度向上のボトルネックの診断についても説明しています。最後に、講演者は、ステンシルの計算と、ステンシルと呼ばれる固定パターンを使用して配列内の各ポイントを更新する方法について説明します。ステンシルは、キャッシュ ミスが発生する可能性があり、時間的および空間的な局所性を利用する効率的なアルゴリズムを使用して削減できるストレージ要件があります。

ビデオの 2 番目の部分では、並べ替えとマージのためのキャッシュ無視アルゴリズムについて説明します。具体的には、ビデオはマージソートのキャッシュの複雑さをカバーし、マルチウェイマージの概念を紹介し、マルチウェイマージアルゴリズムのキャッシュの複雑さを説明します.このビデオでは、ファネル ソート アルゴリズムについても説明します。これは、K 乗要素と K ソート リストをマージできる、キャッシュ無視のソート アルゴリズムです。ファンネルソートアルゴリズムは最適であり、K ファンネルの平方根で再帰的に構築されます。このビデオでは、b ツリー、順序付きファイル メンテナンス、優先キューなど、他にも多くのキャッシュ無視アルゴリズムとデータ構造があることを説明しています。全体として、このビデオは、このトピックについて詳しく知りたい人向けに、キャッシュを無視するアルゴリズムの概要を提供します。

• 00:00:00 このセクションのビデオでは、キャッシュを無視するアルゴリズムについて説明します。これは、マシンのキャッシュ サイズを自動的に調整し、優れたキャッシュ効率を実現するアルゴリズムであり、コードがキャッシュ パラメータを認識している必要はありません。この機械。このビデオでは、微分方程式による熱拡散のシミュレーションの例を使用して、科学計算がしばしば微分方程式に依存して物理プロセスを記述し、そのプロセスをシミュレートするために効率的なコードを記述する必要があることを示しています。ビデオは、1D 熱方程式をシミュレートするための有限差分近似法に基づくコードの記述方法を示しています。
  
  
• 00:05:00 このセクションでは、スピーカーは、ステンシル法を使用して有限差分近似を可能にするシミュレーション方程式のコードを記述する方法について説明します。この方程式は、T と X に関する U の偏微分を使用し、話者は近似法を使用してこれらの偏微分を取得する方法を示します。 2D 空間は、X 値と T 値をそれぞれ水平方向と垂直方向に持つマトリックスを使用して表されます。スピーカーは行列の境界を説明し、方程式を使用して U を計算します。
  
  
• 00:10:00 このセクションでは、科学計算でさまざまな目的に広く使用されている方法であるステンシル計算について、発表者が説明します。この方法では、ステンシルと呼ばれる固定パターンを使用して、配列内の各ポイントが更新されます。計算は他の 3 つの値に依存し、これはスリーポイント スタンスとして知られています。ステンシル計算は大きな X 値に使用できますが、キャッシュに関してパフォーマンスが低下し、キャッシュ ミスが発生する可能性があります。さらに、ポイント値を更新するために、現在の行と前の行の 2 つの行を格納するだけで、データを格納するために必要なストレージを削減できます。
  
  
• 00:15:00 の動作: 各時間ステップで、前の行の値を使用して特定の行の X の値のみを更新しています。そのため、更新している行と前の行として使用している行を交互に使用でき、余分な値の行を約 1 行保持するだけで済みます。ただし、このコードはキャッシュ効率があまり高くないため、タイリングまたはキャッシュ無視アルゴリズムを使用して効率を高めることができます。理想的なキャッシュ モデルは、最適または LRU 置換ポリシーを備えた完全連想キャッシュを想定しており、シリアル実行で容量ミスをキャプチャしますが、競合ミスはキャプチャしません。それにもかかわらず、時間的および空間的な局所性を利用する効率的なアルゴリズムの設計には依然として有用です。
  
  
• 00:20:00 このセクションでは、キャッシュを無視するアルゴリズムを使用して、2D 行列の台形空間内の点を外側を見ずに計算する方法についてスピーカーが説明します。この計算には、UT mod to X へのポインターを取り、0 の W にアルファを掛けた W に負の 1 を足したものを 2 倍したものに 0 の W を足したものと 1 の W を足したものを返すカーネル関数が含まれます。キャッシングの動作は、LRU 置換ポリシーを想定して分析されます。キャッシュ ミスの数は、すべての行の B に対する NT のシータです。ただし、講演者は、タイリングを使用するとパフォーマンスを向上できると述べていますが、キャッシュを無視するバージョンについての議論を続けています。台形は、T1 に上底があり、T0 に下底があります。このアルゴリズムは、T、t0、t1、X、x0、x1、DX0、DX1 を含む不等式条件を使用して、台形内のすべての点を計算します。DX0 と DX1 は、勾配を表す -1、0、または 1 です。
  
  
• 00:25:00 このセクションでは、話者は台形ルール アルゴリズムの分割統治アプローチについて説明します。このアプローチには、台形の高さが 1 である基本ケースがあり、ループは計算順序に基づいてすべての値を計算します。このアルゴリズムには、台形の幅と高さにそれぞれ依存するスペース カットとタイム カットという 2 つの再帰的なケースがあります。台形の幅が広すぎる場合は、台形の中心を通る傾き 1 マイナス 1 の線で台形を垂直にカットするスペース カットが適用されます。逆に台形が高すぎる場合はタイムカットをかけ、中央を通る横線でカット。再帰アルゴリズムは、台形の左右と下と上をそれぞれ特定の順序でトラバースする 2 つの呼び出しを行い、ポイント間の相互依存を防ぎます。
  
  
• 00:30:00 このセクションでは、スピーカーはキャッシュ無視アルゴリズムのキャッシュの複雑さについて説明します。彼らは再帰ツリー アプローチを分析し、アルゴリズムが、H が W のシータである HW ポイントのシータを表す基本ケースに到達するまで、各レベルで 2 つのサブ問題に分割されることを発見しました。葉ごとのキャッシュ ミスの数は、シータ W です。葉の数は HW 上の NT のシータです。内部ノードは、キャッシュの複雑さに大きく影響しません。キャッシュの複雑さは複数の次元に一般化され、d が 1 の場合、MB よりも NT になります。
  
  
• 00:35:00 このセクションでは、スピーカーは、ループ コードと台形コードの違いを説明します。台形コードは、係数 M を節約することでキャッシュの複雑さが大幅に改善されます (M はキャッシュ ラインの数です)。シミュレーションは、ループ コードと比較して台形コードが発生するキャッシュ ミスが少ないことを示しているため、計算がはるかに高速に終了します。ただし、スピーカーは、このシミュレーションは 1 次元のみのものであり、2 次元で何が起こるかのデモを続けて示していることに注意してください。
  
  
• 00:40:00 このセクションでは、プレゼンターが、画面上の色が温度に対応する 2D 空間での熱拡散のリアルタイム シミュレーションを実演します。プレゼンターは、ループ コードと台形コードのパフォーマンスを比較し、台形コードはキャッシュ ミスがはるかに少ないものの、ループ コードよりわずかに高速であることを明らかにしました。これは、ハードウェアのプリフェッチがコードのループを助長していることが原因である可能性が示唆されています。これは、そのアクセス パターンが規則的で予測しやすいためです。
  
  
• 00:45:00 このセクションでは、キャッシングと並列処理の相互作用について説明します。彼らは、シリアル実行でキャッシュミスを最小限に抑えると、低スパンアルゴリズムを想定して、並列実行でキャッシュミスを本質的に最小限に抑えることができるという定理を説明しています。次に、台形アルゴリズムが V カットを使用して並列に動作する方法を示します。この場合、2 つの独立した台形が並列に実行され、その後灰色の台形が実行されます。彼らはまた、逆台形に使用される逆 V カットについても言及しています。
  
  
• 00:50:00 このセクションでは、スピーカーは並列ループ コードと並列台形コードのパフォーマンスを、シリアル コードと比較して説明します。並列ループ コードは、台形コードよりも潜在的な並列性を備えているにもかかわらず、潜在的なスピードアップの半分未満しか達成できません。これは、十分なメモリ帯域幅があるシリアルの場合と比較して、並列の場合にはメモリ帯域幅のボトルネックがあり、プリフェッチが並列ループ コードを支援できないためです。対照的に、台形コードはほぼ線形の高速化を達成します。これは、入力サイズと比較して、キャッシュが非常に小さい入力サイズが大きいほど、キャッシュ効率がはるかに大きな役割を果たすという事実と一致しています。
  
  
• 00:55:00 このセクションでは、スピーカーは、並列処理の高速化のボトルネックを診断する方法について説明し、不十分な並列処理、スケジューリング オーバーヘッド、メモリ帯域幅の不足、競合など、その原因となるいくつかの要因を特定します。彼らは、Silk Scale を使用してコードの並列処理を測定したり、ハードウェア カウンターを実行してメモリ帯域幅を測定したりするなど、これらの問題を診断するいくつかの方法を提案しています。ただし、競合を診断することは特に困難であり、スピーカーは、競合が問題であるかどうかを評価する前に、最初の 3 つの潜在的な原因を調べることをお勧めします。最後に、スピーカーはステンシル計算について議論します。
  
  
• 01:00:00 このセクションでは、スピーカーは、最初に 2 つの並べ替えられた入力配列をマージする複雑さを分析することによって、マージ ソートのキャッシュの複雑さを分析することについて説明します。これを行う時間は、入力配列のサイズの合計に比例します。 n 個の要素をマージする際に発生するキャッシュ ミスの数は、B を超えるシータンです。ここで、B はキャッシュ ラインのバイト数です。マージソートは、半分のサイズの入力に対して 2 つの再帰呼び出しを持ち、その再帰呼び出しのソート済み出力をマージします。マージソートの全体的な作業は、n log n の theta であり、再帰ツリー法を使用して分析されます。マージ ソートのキャッシュの複雑さも説明されており、キャッシュ ミスの数はデータを格納するために必要なキャッシュ ブロックの数に比例することが示されています。サブブロックを持つことができます。
  
  
• 01:05:00 このセクションでは、スピーカーはマージソートのキャッシュの複雑さの再発について説明します。基本的なケースは、問題のサイズがキャッシュに収まる場合に発生し、Θ(n/B) キャッシュ ミスが発生します。それ以外の場合、アルゴリズムにはサイズ n/2 の 2 つの再帰呼び出しと Θ(n/B) キャッシュ ミスがあり、結果をマージします。分析には、n/CM の対数底 2 である再帰ツリーのレベル数が含まれます。ここで、CM は定数です。リーフあたりのキャッシュ ミスの数は Θ(M/B * n/CM) であり、全体のキャッシュ ミス数は Θ(n/B * log (n/CM)) となり、最初の項で B の係数を節約できます。 .ただし、問題のサイズが大きい場合は、作業と比較して B の係数しか節約できませんが、問題のサイズが小さい場合は B log n の係数が保存されます。スピーカーは、より良い解決策があるかどうかを尋ねますが、答えは常にイエスです。
  
  
• 01:10:00 このセクションでは、スピーカーは、並べ替えられたサブ配列をマージするために多方向マージを使用する方法を説明し、サブ配列の最小要素を決定するためのトーナメント ツリーのアイデアを紹介します。彼らはまた、このアプローチの作業とキャッシュの複雑さについても説明しています。これは、並べ替えのためのキャッシュ無視アルゴリズムで使用されます。マルチウェイ マージの作業の複雑さは、バイナリ マージ ソートと同じですが、キャッシュの複雑さは、トーナメント ツリーを埋めて入力配列にアクセスするために必要なキャッシュ ミスの数によって決まります。小さな定数 C の C*M/B。
  
  
• 01:15:00 このセクションでは、講演者はマルチウェイ マージ ソート アルゴリズムのキャッシュの複雑さについて説明し、それをバイナリ マージ ソート アルゴリズムと比較します。多方向マージ ソート アルゴリズムでは、問題をサイズ n/R のサブ問題に分割し、それらをマージするために n/B キャッシュ ミスを支払う必要があります。再帰木の段数はｎ／ｃｍの対数底Ｒ、葉の大きさはｃｍである。話者は、R を M/B のシータに等しく設定して、可能な限り大きくし、キャッシュの複雑さを分析します。これは、B log M で割った theta n log n であることがわかります。バイナリ マージ ソート アルゴリズムと比較すると、マルチ-way マージ ソート アルゴリズムは、ログ M の係数をキャッシュ ミスで節約します。ただし、このアルゴリズムはキャッシュを無視するものではなく、特定のマシンに合わせて R の値を調整する必要があります。これは、キャッシュを競合する他のジョブが実行されている場合に問題になる可能性があります。
   
  
• 01:20:00 このセクションでは、スピーカーはファネル ソート アルゴリズムについて説明します。これは、K 個の二乗要素と K 個のソート済みリストをマージできる、キャッシュ無視のソート アルゴリズムです。このマージのコストは、マルチウェイ マージ ソート アルゴリズムと同じであることが示されていますが、ファンネル ソート アルゴリズムはキャッシュを意識せず、その境界は最適です。講演者は、K 漏斗がどのように見えるかの図を提示し、アルゴリズムが K 漏斗の平方根を使用して再帰的に構築され、バッファーに要素を供給し、バッファーが要素を K 漏斗の最終出力平方根に供給し、生成されることを説明します。 K漏斗の出力。講演者は、b ツリー、順序付きファイル メンテナンス、優先キューなど、他にも多くのキャッシュを無視するアルゴリズムやデータ構造があることに言及し、オンラインでそれらについて詳しく学ぶよう視聴者に呼びかけています。

[MetaQuotes]

講義 16. 非決定論的並列プログラミング

講義 16. 非決定論的並列プログラミング

このビデオでは、決定論的および非決定論的な並列プログラミングに関連するさまざまな概念について説明します。スピーカーは、異常な動作や困難なデバッグにつながる可能性があるため、非決定論を回避することの重要性を強調しています。非決定性を管理するための戦略には、固定値、レコードの再生、分析ツール、カプセル化、単体テストの使用が含まれます。ミューテックスの使用については、回転と譲歩、再入可能と非再入可能、公平と不公平など、詳細に検討されています。講演者はまた、並列プログラミングのコンテキストにおけるコンテキスト切り替えの概念と「スキーのレンタル問題」についても触れています。最後に、マルチコア プロセッサにおけるパフォーマンス エンジニアリングの基本原則について説明します。

ビデオの 2 番目の部分では、並列プログラミングにおけるデッドロックの問題を取り上げ、待機サイクルがないことを保証するミューテックスの線形順序付けなど、デッドロックを回避するためのソリューションを提供します。さらに、スピーカーは、すべての更新を一度にコミットするトランザクションとして重要な領域を表すことによって原子性を保証するトランザクション メモリの概念を紹介します。次にビデオでは、グローバル ロックを必要とせずにデッドロックとスタベーションを防ぐために、有限所有権配列とリリース ソートを必要とするメソッドを使用したロックベースのアプローチを使用するアルゴリズムを紹介します。最後に、リリースソートと再取得のアルゴリズムについて説明します。これにより、複数のロックが同時にロックを取得しようとするのを防ぎ、パフォーマンスの問題を回避できます。

• 00:00:00 このセクションでは、講師がプログラミングにおける決定論の概念と、それが並列計算にどのように関係しているかを紹介します。すべてのメモリ位置が実行ごとに同じ値のシーケンスで更新され、プログラムが常に同じように動作する場合、プログラムは決定論的です。決定論的プログラムには、反復可能であるという利点があり、デバッグが容易になります。講師は、デバッグが困難な異常な動作を示す可能性があるため、非決定論的な並列プログラムを決して作成しないことの重要性を強調しています。ただし、実際には、並列計算で非決定性を回避するのは難しい場合があります。
  
  
• 00:05:00 このセクションでは、スピーカーは非決定論的並列プログラミングと、パフォーマンスの向上につながる場合があるという事実について説明しますが、必要でない限り避けるべきです。スピーカーは、プログラムをそのように書かなければならない場合、非決定性を管理するためのテスト戦略を考案することを推奨しています。戦略の例としては、非決定性を無効にする、乱数に同じシードを使用する、ランダムに変化する可能性のあるプログラム入力に固定値を提供するなどがあります。スピーカーは、非決定論によって引き起こされるプログラムのバグを処理する方法を持つことの重要性を強調しています。
  
  
• 00:10:00 このセクションでは、スピーカーは、レコードの再生、非決定性のカプセル化、決定論的な代替手段の代用、分析ツールの使用、単体テストなど、非決定論的なプログラミングに対処するための戦略について話します。講演者は、コード内のバグを発見する可能性を高めるために、非決定性を制御することの重要性を強調しています。また、講演者は、ハッシュ テーブルで相互排除と原子性を使用する例を示し、非決定論的プログラミングの処理方法を説明します。
  
  
• 00:15:00 このセクションでは、スピーカーは、同じ場所にアクセスする並列命令が競合バグを引き起こし、システムの完全性を破壊する方法について説明します.標準的な解決策は、一部の命令をアトミックにすることです。つまり、システムの残りの部分では完全に実行されているか、まったく実行されていないと見なされます。これを実現するために、相互排他ロックまたはミューテックス ロックが使用されます。これは、lock および unlock メンバー関数を持つオブジェクトです。各スロットは、ミューテックス ロックとスロット コンテキストへのポインター ヘッドを持つ構造体に作成され、リストにアクセスする前にロックおよびロック解除関数を使用できるようにすることで、システムの正確性を保証します。
  
  
• 00:20:00 このセクションのビデオでは、ミューテックスを使用してアトミック性を実装する方法と、決定性競合との関係について説明します。ミューテックス ロックは、クリティカル セクションがアトミックであることを保証できますが、結果のコードは、場合によっては必要とされる決定性の競合により、非決定論的になります。このビデオでは、データ競合と決定性競合の違いを理解することの重要性を強調し、単純にデータ競合を排除してもコードにバグが存在しないとは限らないことを指摘しています。誤検知やコード内の競合バグの欠落を避けるために、非決定論を検出する方法を持つことが重要です。
  
  
• 00:25:00 このセクションでは、スピーカーは、データ競合がないからといって、コードにバグがないことを必ずしも意味しないと説明しています。データ競合はコードのポジティブな側面ではありませんが、原子性を提供するためのロックの例は、原子性違反につながる可能性があります。さらに、2 つの並列プロセスが同じ値にアクセスしている場合など、無害な競合が発生する可能性があります。これは同じ結果になる可能性がありますが、一部のアーキテクチャでは正しくない値になる可能性もあります。講演者は、良性の人種を無害と考える人もいますが、それでも人種を特定して避けることが不可欠であると主張しています。
  
  
• 00:30:00 このセクションでは、スピーカーは、特に複数のプロセスが同じ場所に値を設定しようとしたときに発生する可能性のある競合状態による、非決定論的プログラミングの危険性について説明します。スピーカーは、意図的なレースを可能にする「シルク」の概念を紹介しますが、正しく使用しないと危険になる可能性があります。競合の複雑さは、デバッグを困難にし、正しいコードの検出を支援するためのツールを混乱させる可能性もあります。また、ミューテックスとそのパラメーターの実装が、ミューテックスの動作にどのように影響するかについても説明します。
  
  
• 00:35:00 このセクションの動画では、並列プログラミングにおけるミューテックスの 3 つの基本的な特性 (スピンと譲歩、再入可能と非再入可能、公平と不公平) について説明します。スピンと譲歩の概念は、スレッドがアイドル状態でロックへのアクセスを継続的にチェックするのではなく、より効率的な実行のためにオペレーティング システムに制御を譲るという考え方です。再入可能ミューテックスを使用すると、既にロックを保持しているスレッドがロックを再度取得できますが、スレッドが既に保持しているミューテックスを再取得しようとすると、非再入可能ロックはデッドロックします。最後に、公平なミューテックスにより、最も長く待機しているスレッドが最初にロックを取得し、飢餓の問題が発生する可能性を回避できます。このビデオでは、アセンブリ言語での単純な回転ミューテックスの実装も提供します。
  
  
• 00:40:00 このセクションのビデオでは、並列プログラミングでミューテックスを使用する方法と、ミューテックスを取得する代わりに交換命令を使用する理由について説明します。交換操作は権利に似ていると説明されており、権利を実行するには、そのキャッシュ ラインが他のキャッシュ ラインで無効になり、変更された状態または排他的な状態で保持される必要があります。これにより、メモリ ネットワーク上にトラフィックが発生し、プロセスが遅くなります。一方、exchange 命令を使用すると、キャッシュ ラインが共有状態になり、処理が速くなり、トラフィックが少なくなります。
  
  
• 00:45:00 このセクションでは、スピニング ミューテックスとイールド ミューテックスの違いについて説明します。回転ミューテックスでは、プログラムはミューテックスのロックが解除されるかどうかをチェックし続けますが、譲歩ミューテックスでは、プログラムはオペレーティング システムに制御を譲り、他の何かをスケジュールできるようにします。講演者は、競合ミューテックスと呼ばれる別の種類のミューテックスもあり、回転するミューテックスと譲歩するミューテックスの両方の目標を達成することに注意します。スピーカーは、待機中のスレッドに通知するためにメッセージ パッシングまたは割り込みを使用することも検討しますが、より簡単な解決策は相互排除メカニズムを使用することであることに注意してください。
  
  
• 00:50:00 このセクションでは、スピーカーはコンテキスト切り替えの概念について説明します。コンテキスト切り替えとは、オペレーティング システムが使用可能なプロセッサのスレッド間で切り替える頻度です。通常、システムは 1 秒あたり約 100 回コンテキストの切り替えを行います。つまり、各切り替えには約 10 ミリ秒かかります。ただし、これは単純な命令の実行時間よりも 1 桁以上長くなります。つまり、スレッドが戻ってきてロックを取得する前に実行できる命令が多数あることを意味します。この問題は、スピニングとイールドを組み合わせることで解決できます。話者はこれを理論の文献で「スキーのレンタル問題」と呼んでいます。
  
  
• 00:55:00 このセクションでは、スポーツ用品の購入またはレンタルの例を使用して、特定のタスクのために機器を購入するかレンタルするかを決定するプロセスについて説明します。講演者は視聴者にレンタルと購入のコストを検討するよう促し、コストが購入と同じになるまでレンタルしてから購入することを提案します。このビデオでは、コンテキスト切り替え時間、ディスク アクセス時間、および複数のロックを同時に保持する場合のデッドロックの問題の概念についても説明します。全体として、このセグメントでは、マルチコア プロセッサのパフォーマンス エンジニアリングの基本原則について説明します。
  
  
• 01:00:00 このセクションでは、スピーカーはデッドロックについて説明します。デッドロックとは、2 つのスレッドが他方のスレッドが両方とも必要とするリソースを保持し、パフォーマンスが低下することです。デッドロックには 3 つの基本的な条件があります。相互排除 (リソースの排他的制御)、非プリエンプション (リソースが終了するまで保持される)、および循環待機 (スレッドが次のスレッドによって保持されるリソースを待機するサイクル) です。これらの制約のいずれかを削除すると、デッドロックの問題を解決できます。話者は、デッドロックの問題を説明するために、エドガー ダイクストラの試験問題に基づいてトニー ホーアが語った「食事の哲学者」という物語を使用します。物語は、テーブルの周りに座っている哲学者が、麺の各皿が2本の箸の間に置かれている箸で麺を食べることを含み、麺を食べるには2本の箸が必要です.哲学者たちは左右の箸をつかんで麺を食べます。しかし、全員が左の箸を左手に持ってしまうと、餓死してしまいます。
   
  
• 01:05:00 このセクションでは、スピーカーは並列プログラミングにおけるデッドロックの問題について説明し、デッドロックを回避しながらプリエンプションを回避するソリューション、つまりミューテックスの線形順序付けを提供します。各ミューテックスに番号を付け、それらの番号順に基づいて戦略的にロックすることにより、プログラマは待機サイクル (デッドロックに必要な条件) が発生しないことを保証できます。ただし、これらのロックによって追加の非決定性が導入されると問題が発生する可能性があるため、Silk のランタイム システムによるロックのカプセル化に注意するようプログラマーに警告しています。彼は、1 つのロックだけでデッドロックが発生する可能性がある例を共有し、並列プログラムを設計する際の慎重な検討の重要性を強調しています。
  
  
• 01:10:00 このセクションでは、スピーカーはトランザクション メモリのトピックを掘り下げます。これは、ロックを指定する必要なく、原子性が暗黙的に発生するデータベース トランザクションを含む最近の研究レベルの手法です。講演者は、同時グラフ計算、つまりガウス消去法でトランザクショナル メモリがどのように役立つかの例を示します。ガウス消去法では、2 つのノードを同時に消去すると原子性違反が発生します。トランザクショナル メモリの背後にある考え方は、クリティカル リージョンをトランザクションとして表し、コミット時に、クリティカル リージョン内のすべてのメモリ更新が一度に発生したかのように見せることです。
  
  
• 01:15:00 このセクションでは、スピーカーは競合の解決、競合の解決、進行状況、およびトランザクション メモリのスループットについて説明します。彼らは、グローバルロックを必要とせずにデッドロックと枯渇を防ぐために、有限所有権配列とリリースソートrequireメソッドを使用したロックベースのアプローチを使用するアルゴリズムを導入しています。このアルゴリズムは、読み取りと書き込みをログに記録して、トランザクションが中止されたときにロールバックまたはアトミック コミットを可能にします。ロック配列は、ハッシュ関数がマップする場所をロックするために使用され、ロックの公平な取得を可能にします。このアルゴリズムは、パフォーマンスを犠牲にしたり、デッドロックを引き起こしたりすることなく、同時トランザクションを可能にします。
  
  
• 01:20:00 このセクションでは、スピーカーは解放ソートと再取得と呼ばれるアルゴリズムについて説明します。このアルゴリズムは、貪欲にメモリ ロケーションのロックを取得しようとすることで機能し、競合が発生した場合、トランザクションは保持しているロックを解放せずにロールバックします。その後、アルゴリズムは、アクセスしようとしている場所のインデックスより大きいインデックスを持つすべてのロックを解放します。次に、目的のロックを取得し、最後に解放されたロックをソートされた順序で取得します。このプロセスは、トランザクションが成功するまで繰り返されます。このアルゴリズムは、複数のロックが同時にロックを取得しようとするのを防ぐように設計されており、パフォーマンスの問題を引き起こす可能性があります。

[MetaQuotes]

講義 17. ロックなしの同期

講義 17. ロックなしの同期

Charles Leiserson は、YouTube ビデオでロックなしの同期の概念を探っています。彼は、シーケンシャルな実行を確実にするために命令のグローバルな線形順序の必要性を示す例を提供し、シーケンシャルの一貫性によって相互排除を達成し、ロックを使用することの困難と潜在的な問題を回避する方法について説明します。 Leiserson は、Peterson のアルゴリズムを、ロード操作とストア操作のみを使用して、並行プロセスからの干渉なしにクリティカル セクションにアクセスするソリューションとして提示しています。このビデオでは、ハードウェアの並べ替えによるメモリを介した同期の課題と、他の命令との相対的な順序を維持するためのメモリ フェンスの概念についても取り上げています。 Leiserson は、並列マシンの順次一貫性をサポートすることは有益ですが、ハードウェア設計者にとっては実現が難しいと主張しています。

ビデオの 2 番目の部分では、並列プログラムでのエラーを防止するためのメモリ フェンスと同期命令の使用について説明します。講演者は、メモリ フェンスを暗黙的または明示的に実装するさまざまな方法と、プロセッサのさまざまな側面に取り組んでいるさまざまなチーム間の慎重なエンジニアリングと調整の重要性について説明します。さらに、講師は、C11 言語標準のロックフリー アルゴリズムの一部として CAS 命令を使用して、定数スペースのみを使用して n スレッド デッドロックのない相互排除アルゴリズムのミューテックスを実装する方法について説明します。 Charles Leiserson は、マルチスレッド システムでロックを使用する際の問題と、代わりに CAS を使用する解決策について説明しています。スレッドが長時間ロックを保持すると、同じリソースへのアクセスを待機している他のスレッドを潜在的にブロックする可能性があるからです。さらに、このビデオでは、コンペア アンド スワップに関する ABA 問題の潜在的な問題が強調されており、このトピックに関心のある人は、ロックフリー アルゴリズムについて詳しく学ぶことができます。

• 00:00:00 およびそれらの命令はインターリーブされ、すべての命令のグローバルな線形順序が生成されます。これは、理論的な観点から最も重要なメモリ モデルである順次整合性のメモリ モデルの背後にある考え方です。ロックがない場合、並列プログラムの動作はメモリ モデルに依存するため、メモリ モデルを理解することは重要です。講義で提示された 1 つの例は、使用されているメモリ モデルに応じて、コードを並列実行した後、2 つのプロセッサが両方とも 0 の値を持つことが可能かどうかを尋ねることで、この点を示しています。
  
  
• 00:05:00 このセクションでは、Charles Leiserson がロックを使用しない同期の概念について説明します。実行がシーケンシャルになるためには、ロードとストアがグローバルな線形順序に従っているように見える必要があります。彼は、さまざまな値をインターリーブする例を使用して、発生する可能性のあるさまざまな実行パスと、ハードウェアが必要なことをどのように実行できるかを示しています。彼はまた、値をインターリーブするにはさまざまな方法が考えられますが、実行の一貫性を保つには、ロードとストアが線形の順序に従っているように見える必要があると説明しています。最終的に、Leiserson は、両方の値が 0 で終了する実行は存在しないと結論付けており、興味深いことに、最新のコンピューターのいずれも順序の一貫性を提供していません。
  
  
• 00:10:00 このセクションでは、シーケンシャル一貫性の概念について説明します。これには、命令とその順序の間の発生前の関係、右矢印接続、プロセッサの順序、および命令の順序付けの間の線形関係を理解することが含まれます。また、シーケンシャルコンシステンシーを考え、ロードとストアによる共有データ構造を実現することで、負荷の高い命令やロックを使わずに相互排除を実現できます。講義ノートでは、テストと設定、比較とスワップなどの特殊な操作を使用する方法について説明していますが、提示されたソリューションは、ロックを使用するときに発生するビルドのデッドロックやその他の悪いことを回避します。
  
  
• 00:15:00 このセクションでは、Charles Leiserson が、ロード操作とストア操作のみを使用して並列プログラムで相互排除を実現するための Peterson のアルゴリズムについて説明します。このアルゴリズムでは、Alice と Bob の 2 つの同時プロセスが、一連の変数とターンテイキング メカニズムを使用して、互いに干渉することなくコードを実行できます。コードは、一度に 1 つのプロセスだけがクリティカル セクションに入り、共有リソースを変更できることを保証します。ロックとは異なり、Peterson のアルゴリズムはロックの取得または解放に依存せず、代わりにロードとストアを使用して相互排除を実現します。
  
  
• 00:20:00 このセクションでは、スピーカーは、ロックを使用せずにクリティカル セクションで相互排除を実現するピーターソンのアルゴリズムについて説明します。彼は、クリティカル セクションに入ることができるのは一度に 1 人だけであり、アルゴリズムは、クリティカル セクションに入りたいと思っている人が自分だけである場合、クリティカル セクションに入ることができることを保証すると説明しています。次にスピーカーはアルゴリズムの証明を提示します。これには、アリスとボブの両方が一緒にクリティカル セクションにいると仮定し、矛盾を導き出すことが含まれます。この証明は、「前に起こる」関係と実行される命令のプログラム順序に依存しています。
  
  
• 00:25:00 このセクションでは、スピーカーはロックなしで同期するプロセスを説明します。これらは、命令チェーンを確立し、それらが正しい順序で発生することを保証して、同期エラーを回避します。デモンストレーションとして、Bob と Alice が共有リソースにアクセスしたいという例を使用します。彼らは、同期するとき、エンジニアは注意して「物事の前に起こる」ことを確認して、それらが正しい順序で発生していることを確認する必要があると説明しています.
  
  
• 00:30:00 このセクションでは、Charles Leiserson がモデル チェックの概念と、ネットワーク、セキュリティ、およびキャッシュ プロトコルの分析におけるその使用について説明します。次にピーターソンのアルゴリズムの特性を説明します。このアルゴリズムは飢餓の自由を保証しますが、2 つ以上のプロセスでは機能しません。 Leiserson はまた、メモリを介した同期の課題と、最近のプロセッサにおけるシーケンシャルの一貫性の欠如についても調査しています。これにより、メモリの一貫性が緩和され、同期を正しく行うことが困難になります。
  
  
• 00:35:00 ロード レイテンシの問題を引き起こさずに命令を並べ替えても安全ですか? 2 つ目の制約は、命令間にデータの依存関係がない場合です。つまり、命令がデータを共有したり、メモリ内の同じ場所を使用したりしません。この場合、命令の順序を変更すると、パフォーマンスが向上し、ロード遅延をカバーできます。これは、ロードをより早く実行し、結果を待っている間に他の作業を実行できるためです。これらのハードウェア レベルの概念を理解することは、ソフトウェアについて推論し、パフォーマンスを最適化するのに役立ちます。
  
  
• 00:40:00 このセクションでは、Charles Leiserson が、ロックを使用しない同期での並べ替えの概念について説明します。彼は、特にプロセッサが動作している場合や命令ストリームにバブルがある場合は、同時実行性がない限り、並べ替えを安全に実行できることを明確にしています。これは、最新のプロセッサでは、ハードウェアがデータをバッファに格納し、メモリ システムに直接アクセスしてロードをバイパスするためです。ただし、このバイパスは、ストアの 1 つが読み込まれている場合、正確性の問題につながる可能性があります。
  
  
• 00:45:00 このセクションでは、Charles Leiserson が、ハードウェアの並べ替えがどのように発生し、なぜそれが順次整合性を満たさないのか、および x86 には総ストア順序と呼ばれるメモリ整合性モデルがあり、これは順次整合性よりも弱いことを説明しています。合計ストア順序の規則には、ロードをロードと並べ替えないこと、ロードが外部プロセッサによって同じ順序で認識されること、ストアがストアと並べ替えられないこと、ロードが別の場所への前のストアとのみ並べ替えられること、以前のロードとは並べ替えられないことが含まれます。同じ場所。ロック命令とメモリの順序は、全体の順序に従います。
  
  
• 00:50:00 このセクションでは、スピーカーは、命令の並べ替えが順序の一貫性に違反し、誤った値をもたらす可能性があることについて説明します。並べ替えはハードウェアとコンパイラの両方で発生する可能性があり、ロック命令は他の命令の前に移動されないことを知っておくことが重要です。講演者はまた、異なるアドレスへの場合、ロードがストアの前に行われる可能性があることにも注意します。並べ替えの危険性はピーターソンのアルゴリズムで実証されており、特定の並べ替えが発生すると完全に台無しになる可能性があります。したがって、メモリーを介して同期する際にこれらの問題を回避するには、確定的なコードを記述することが重要です。
  
  
• 00:55:00 このセクションでは、Charles Leiserson が、ストアの前に発生する特定のロードを回避することが重要な、並列および並行コードを記述する際の並べ替えの問題について説明します。このようなシナリオに対処するために、エンジニアは他の命令との相対的な順序を維持するメモリ フェンスを導入しますが、複雑さが増し、潜在的なバグが発生するという代償が伴います。 Leiserson はまた、並列マシンが逐次一貫性をサポートすることは有益であるが、ハードウェア設計者が達成するのは困難であると主張しています。
  
  
• 01:00:00 このセクションでは、スピーカーは、並列プログラムでエラーが発生するのを防ぐためのメモリ フェンスと同期命令の重要性について説明します。スピーカーは、命令として明示的に、またはロックや交換などの他の同期命令を介して暗黙的になど、メモリ フェンスを実装できるさまざまな方法について説明します。ただし、メモリ フェンスが実際にプログラムの速度を低下させる場合があり、慎重なエンジニアリングと、プロセッサのさまざまな側面に取り組んでいるさまざまなチーム間の調整の重要性を示しています。さらに、講演者は、揮発性変数とコンパイラ フェンスを使用して、コンパイラが変数を最適化し、並列コードでエラーが発生するのを防ぐようにアドバイスします。
  
  
• 01:05:00 このセクションでは、講師が C11 言語標準のロックなしの同期について説明します。この標準では、物事をアトミックとして宣言できる弱いメモリ モデルが定義されており、デッドロックのない相互排除アルゴリズムのためのメモリ フェンスやアトミック コンペア アンド スワップなどの高価な操作を使用する必要があります。ここでは、CAS 命令 (Compare-and-Swap) がロックフリー アルゴリズムの一部として検討されています。この命令は、メモリ内の値が古い値と同じかどうかを確認してから、新しい値にスワップします。すべてアトミックに行われます。 CAS を使用すると、定数スペースのみを使用して、n スレッドのデッドロックのない相互排除アルゴリズムのミューテックスを実装できます。値が true になるまでスピンするロック命令は、誰かがロックを保持していることを示す true にスワップするために使用されます。
  
  
• 01:10:00 このセクションでは、Charles Leiserson 教授が比較交換 (CAS) を使用して同期の問題を解決する方法を説明しています。彼は、CAS をロックとして使用する方法を示し、学生が提示したコードのバグを修正します。次に、配列内の値の合計を計算するために使用される誤ったコードを提示すると、競合状態が発生します。彼は、典型的な解決策としてミューテックスロックを紹介し、ロックを取得した後にスレッドがスワップアウトされ、他のスレッドがロックを待機し、進行を妨げるという潜在的な問題について説明しています。
  
  
• 01:15:00 このセクションでは、Charles Leiserson が、マルチスレッド システムでロックを使用する際の問題と、代わりに CAS を使用する解決策について説明します。ロックを使用すると、スレッドが長時間ロックを保持し、同じリソースへのアクセスを待機している他のスレッドをブロックする可能性があります。ただし、CAS を使用すると、x のロードの後に一時を計算した後、x のストアが続きます。また、変数 old と new を使用して古い結果を格納し、一時的な結果をその古い値に追加して、新しい値を生成することができます。古い値が変更されていない場合はスワップインされます。また、Charles はコンペア アンド スワップに関する ABA の問題についても言及しており、このトピックに関心のある人には、ロックフリー アルゴリズムについてさらに学ぶよう勧めています。

[MetaQuotes]

講義 18. ドメイン固有言語と自動チューニング

講義 18. ドメイン固有言語と自動チューニング

このビデオでは、MIT の EECS 部門の Saman Amarasignhe 教授が、パフォーマンス エンジニアリングにおけるドメイン固有言語 (DSL) と自動チューニングを使用する利点について説明しています。彼は、DSL の重要性を強調しています。DSL は、汎用言語では記述が困難な領域固有のドメインをキャプチャし、プログラマーがドメインの専門家の知識を利用してパフォーマンスを向上できるようにします。 Singh は、グラフの分割や計算におけるグラフの形状の重要性など、DSL を使用したグラフ プロセスの最適化について説明しています。彼は、画像処理用の DSL Halide を紹介します。これにより、高速なコードの最適化とマシン間での移植性が可能になります。彼は、Google や Adobe などのさまざまな業界での Halide の使用について説明しています。最後に、並列性、局所性、および冗長作業に焦点を当てながら、コードを最適化するさまざまなアプローチを試すことの重要性を強調しています。

このビデオでは、パフォーマンス エンジニアリングの課題と、プログラムを効率的に実行するための最適なパラメーターを見つけることについても説明しています。講演者は、オートチューニングが大きなパラメータ空間を自動的に検索して最適な値を見つけることにより、この問題に対処できることを示唆しています。彼は、徹底的な検索は非現実的である可能性があり、ヒューリスティック ベースのソリューションは最適ではない可能性があると指摘しています。許容値のスペースを定義し、パフォーマンス結果に基づいて反復する自動調整により、最適なソリューションを見つけるプロセスを高速化できます。講演者は、Try のスケジュール生成における自動調整の適用についても説明します。Try は、網羅的な検索よりも効率的かつ効果的にスケジュールを生成することができました。

• 00:00:00 このセクションでは、MIT の EECS 部門の教授である Saman Amarasignhe 教授が、ドメイン固有言語と自動チューニングについて話します。これらの言語は、汎用言語では記述しにくい特定の領域固有のドメインをキャプチャするため、エンジニアリング上の利点があると彼は説明します。ドメイン固有言語は、理解と保守がはるかに簡単であり、プログラマーはドメインの専門家の知識を利用して、非常に優れたパフォーマンスを得ることができます。さらに、正しく構築された場合、ドメイン固有言語は、低レベルの決定をコンパイラに任せることができるため、最適化プロセスがはるかに簡単になります。
   
  
• 00:05:00 このセクションでは、スピーカーはパフォーマンス エンジニアリングにおけるドメイン固有言語 (DSL) の使用について説明します。彼らは可能な限りパフォーマンスをコンパイラに委ねることを奨励し、Graffiti、Halide、OpenTuner という 3 つの異なるプログラミング言語/フレームワークをグラフ処理に導入しています。彼らは、グラフは Google 検索からレコメンデーション エンジンまで至るところにあると指摘し、Google が Web ページのランク付けに使用する PageRank アルゴリズムをさらに深く掘り下げています。 PageRank アルゴリズムは、Web ページの近隣を調べ、その影響に基づいて新しいランクを計算します。これは、パフォーマンス エンジニアリングにおけるグラフ処理の重要性を示しています。
  
  
• 00:10:00 このセクションでは、スピーカーはグラフ アルゴリズムについて説明します。グラフ アルゴリズムには、大量のデータの処理と、グラフ全体の計算の反復が含まれます。コードのパフォーマンスを最適化するには、DSL を使用できます。グラフ処理に使用されるアルゴリズムのタイプには、グラフ全体が計算に参加するトポロジ駆動型アルゴリズムと、グラフの小さな領域または一部で処理が行われるデータ駆動型アルゴリズムがあります。グラフの反転を行う方法も複数あり、それぞれの方法で異なる結果が得られます。
  
  
• 00:15:00 このセクションでは、大きなグラフを小さな断片に分割するグラフ パーティショニングのトピックについて説明します。グラフを分割する利点は、並列処理が可能になることと、ローカル性が良好になることです。つまり、作業中のノードがキャッシュに収まるほど小さいということです。グラフ パーティショニングは、ソーシャル ネットワーク グラフにも影響を与えます。これは、べき乗関係があるためです。これは、特定のノードが他のノードよりも多くの接続または大きな影響を持っていることを意味し、これらのグラフを処理するとき、特定の接続とノードはその重要性を考慮してより多くの注意を払う必要があります。
  
  
• 00:20:00 このセクションでは、スピーカーは計算におけるグラフの形状の重要性、特にグラフのサイズと局所性が並列処理アルゴリズムの効率にどのように影響するかについて説明します。特定のアルゴリズムで最高のパフォーマンスを実現するには、並列処理、局所性、必要な追加作業などの要素のバランスを慎重に調整する必要があります。また、使用するグラフの種類、アルゴリズムの種類、およびハードウェアに基づいて適切な方法を選択する必要があります。これらの要因をより適切に最適化するために、定数アルゴリズムを処理メソッドから分離するドメイン固有言語が開発されました。
  
  
• 00:25:00 このセクションでは、ドメイン固有言語 (DSL) を使用してより高いレベルでコードを記述し、よりシンプルでエレガントにする方法について説明します。それらは、さまざまなアルゴリズムの例と、DSL がそれらを計算する簡単な方法をどのように提供するかを示しています。さらに、講演者は、DSL のスケジューリングを最適化して可能な限り最高の速度を実現し、並列処理を可能にする方法についても説明します。グラフまたはマシンの変更に基づいてコードを変更できますが、アルゴリズムは同じままです。講演者は、最適化されたスケジュールを生成するのに十分なほど強力でありながら、プログラミングを簡素化する DSL の重要性を強調しています。
  
  
• 00:30:00 このセクションでは、講演者は別のドメイン固有言語である Halide について説明します。Halide は、高密度の規則的な構造を持つ画像処理に焦点を当てています。 Halide は、最適化されたパフォーマンスを実現するために必要なプログラミングの量を削減し、異なるマシン間でのプログラムの移植性を向上させます。スピーカーは、ハライドがどのように機能するかを示すために、3 x 3 のぼかしの例を提供します。 Halide には、さまざまな手法をさまざまに組み合わせてパフォーマンスを最適化するという点で、前述のグラフ言語と同様のパターンがあります。
  
  
• 00:35:00 このセクションでは、スピーカーはドメイン固有言語 (DSL) の使用と、コードのパフォーマンスを最適化するための自動チューニングについて説明します。彼は、有効な C コードと比較して、Halide と呼ばれる DSL を使用して高速に実行される画像フィルターの例を示しています。 Halide を使用すると、アルゴリズムをスケジュールから切り離すことができ、実行される純粋な関数のパイプラインを簡単に最適化できます。最後に、講演者は、利用可能なコンピューティング リソースから最高のパフォーマンスを実現するために、局所性、並列処理、および冗長作業の間のトレードオフの必要性を強調しています。
  
  
• 00:40:00 このセクションでは、スピーカーは画像処理における局所性の重要性について説明します。大きな画像を処理する場合、一度に画像全体に作用するフィルターを適用するのは効率的ではありません。キャッシュに収まらないためです。代わりに、スピーカーは、画像を小さなセクションに分割し、各セクションにフィルターを適用して、局所性と並列性に焦点を当てることを提案しています。これは、スケジューリング フレームワークを使用し、計算帯域幅とストレージの粒度を最適化することで実現できます。また、局所性と並列性を向上させるために、冗長な作業が必要になる場合もあります。
  
  
• 00:45:00 このセクションでは、講演者は、Halide の使用に焦点を当てて、ドメイン固有言語と自動調整について説明します。 Halide はライブラリ関数を融合できます。局所性が高いため、ライブラリを呼び出すよりも高速です。講演者は、Halide がバイラテラル フィルター計算やセグメント化アルゴリズムなどの計算プロセスを最適化する方法を示します。一例として、手動で最適化されたライブラリを呼び出していた MATLAB で記述されたセグメント化アルゴリズムは、Halide で記述された場合に 70 倍高速になりました。 Halide は Google の重要な部分であり、Android フォンに統合され、Google Glass で使用されました。
  
  
• 00:50:00 このセクションでは、講演者はフロントエンド処理に Halide を使用することの有効性と、それがさまざまな業界でどのように広く使用されるようになったかについて説明します。 Halide は、以前のバージョンと比較して速度が 4 ～ 5% 向上しています。これは、ダウンロードされたビデオの数を考えると、Google にとって重要です。 Adobe は、Photoshop フィルタ全体が Halide で記述されていることも発表しました。 Snapdragon イメージ プロセッサと Intel も Halide を使用し始めています。講演者はまた、Halide と Graph が最適化を自動化し、パフォーマンス エンジニアの仕事を容易にするという点でどのように類似点を共有しているかについても説明します。ただし、アルゴリズムの最適化に関しては、特定のコンテキストに関する知識が必要な高レベルの変更であるため、自動化が困難です。それにもかかわらず、スケジュールされた言語などのツールを使用すると、ユーザーはさまざまなアプローチを試してパフォーマンスを向上させることができます。
  
  
• 00:55:00 このセクションでは、スピーカーが最新のコンピューター システムの複雑さと、コードを最適化する唯一の正しい方法がないことについて説明します。彼らは、さまざまなアプローチを試すことの重要性と、キャッシュ、局所性、および並列処理の重要性を強調しています。また、生物学や物理学などのさまざまな分野の人々が、コードの複雑さのためにプログラムを十分に迅速に作成できないため、研究を進めるのではなく、コードの最適化に多くの時間を費やしていることについても説明しています。講演者は、人々がほとんどの時間をハッキングと抽象化に費やしているドメインを見つけることは、研究のために探索する興味深い領域になる可能性があることを示唆しています.全体として、プログラムを最適化するために操作するスペースには、並列処理、局所性、および冗長な作業が含まれます。このスペースで遊ぶことは、パフォーマンス エンジニアにとって非常に重要です。


• 01:00:00 このセクションでは、スピーカーはパフォーマンス エンジニアリングの課題について説明します。これには、プログラムを最適に実行するための適切なパラメーターを見つけることが含まれます。彼は、メモリ割り当てやブロック サイズなど、調整できるパラメーターは数多くあるものの、プログラムごとに各パラメーターの適切な値を決定するのは難しい場合があると説明しています。ただし、講演者は、オートチューニングがこの問題に対処できることを示唆しており、大きなパラメーター空間を自動的に検索して最適な値を見つけます。彼は、特定の状況でルールをハード コーディングするヒューリスティック ベースのソリューションは、ほとんどの場合は機能しますが、常に最適であるとは限らないと説明しています。講演者はまた、モデルがすべての重要な要因を考慮していないため、システムのモデルを構築すると問題が発生する可能性があり、最適ではない結果につながる可能性があることにも言及しています。
  
  
• 01:05:00 このセクションでは、講演者は、テクノロジーの変化や要件の進化に直面して最適なソリューションを見つけるという課題について説明します。彼は、プログラマーが解決策を導くために使用するさまざまな「ヒューリスティック」があり、多くの場合、もはや適用できないガイドラインや経験則に基づいていると述べています。選択肢の 1 つは徹底的な検索ですが、考えられる順列の数が非常に多いため、これは実用的ではありません。これに対処するために、講演者は、探索空間を刈り込み、最適な解をより迅速に見つける方法として、オートチューニングの使用を推奨しています。自動調整では、許容値の範囲を定義し、テストする値をランダムに選択してから、パフォーマンス結果に基づいて反復します。 OpenTuner は、ヒル クライマーやランダム検索などの一連の手法を使用して、この反復プロセスを高速化するフレームワークの一例です。
  
  
• 01:10:00 このセクションでは、スピーカーはオートチューニングの概念と、Try のスケジュールの生成に適用する方法について説明します。関係するグラフとリズムを理解することで、オートチューニングを使用して、網羅的な検索よりも効率的かつ効果的にスケジュールを生成できます。この方法により、2 時間以内にスケジュールを作成することができ、場合によっては、当初考えられていた最善のスケジュールよりも優れたスケジュールを作成することができました。

[MetaQuotes]

講義 19. Leiserchess Codewalk

講義 19. Leiserchess Codewalk

「19. Leiserchess Codewalk」というタイトルのこの YouTube ビデオでは、Helen Xu が Lesierchess のルールを説明しています。Lesierchess は、相手チームの王を撃つか、自分の王を撃つことを目的として 2 つのチームが行うゲームです。このゲームには、基本的な動きと叩く動きの 2 種類の動きと、対戦相手の最新の動きを元に戻すと動きが違法になる Ko ルールがあります。 Xu は、Fisher 時間制御法、Forsythe-Edwards Notation、クラウド オートテスター、プロジェクト編成、Elo レーティング、ムーブ生成、静的評価、アルファ ベータなどの検索アルゴリズムを使用したボットの評価と比較など、ゲームのプレイのさまざまな側面に飛び込みます。原則のバリエーション、サブツリーの枝刈り、および転置テーブル。彼女はまた、プログラムと eval.c ファイルを最適化するためのテスト インフラストラクチャの重要性についても説明しています。このファイルには、ピースの種類とその色に基づいてボード上の各正方形を評価するヒューリスティックが含まれています。

スピーカーは、ゲームのレーザー カバレッジの側面についても掘り下げ、while-true ステートメントを使用して、プレイヤーの色に基づいて位置の可能なすべての動きを生成する複雑なシステムについて説明します。また、コードの正確性の重要性とそれをテストする方法についても説明し、パフォーマンスを最適化する前に正確性を確保するために表現を変換することを提案しています。講演者はまた、Leiserchess UCI インターフェイスによって提供される優れた柔軟性についても説明します。これにより、ユーザーはテーブルやコマンドを好みに合わせて編集できるようになり、デッド コードがクリーンアップされ、その他のバグが修正されるように報告する必要があることを視聴者に安心させます。

• 00:00:00 このセクションでは、Helen が Lesierchess ゲームのルールとその遊び方について説明します。ゲームはオレンジとラベンダーの 2 つのチームで行われ、各チームは 7 つのポーンとキングを持ちます。ゲームの目的は、相手チームのキングを撃つか、自分のキングを撃つことです。このゲームには、基本的な動きとスワットの動きの 2 種類の動きがあります。ゲームにはさらに、相手チームがいた場所に戻るだけで相手の最新の動きを元に戻す場合、動きを違法にするKoルールがあります.引き分けは、ポーンがザッピングされずに各チームが 50 回移動した場合、同じ位置が繰り返された場合、または 2 つのチームが引き分けに同意した場合に発生します。
  
  
• 00:05:00 このセクションでは、スピーカーは、レイザーチェスで使用されるフィッシャー時間制御法について説明します。各プレーヤーは、最初の時間予算と時間増分から始めます。使用されている例では、各プレイヤーは 60 秒で開始し、移動を終了すると 0.5 秒の延長を取得します。しかし、実際の制限時間はいくらでもかまいません。次にスピーカーは、反撃を避けながら F5 でポーンを攻撃するみかんの動きを聴衆に提案するように求めることで、ライサーチェスのプレイ方法を実演します。ただし、スピーカーは、対戦相手を開く可能性があるため、単純にすべてのピースを殺すなど、ゲームの機微について警告します。
  
  
• 00:10:00 このセクションでは、Helen Xu が Forsythe-Edwards Notation について、文字列を使用してチェスの位置を表すためのツールとして説明しています。これはデバッグ目的に役立ち、特定の位置に簡単に戻ることができます。彼女はまた、チェス ゲームのログの読み方を説明し、各動きとそれに対応する注釈を分析しています。さらに、彼女はスクリメージ サーバーを使用してクラス内の他のチームとボットをテストする方法、および他のチームに挑戦し、行われた試合を表示する方法を示します。
  
  
• 00:15:00 このセクションでは、Helen Xu が Lesierchess のクラウド オートテスターとプロジェクト組織について説明します。スクリメージ サーバーでは一度に 1 つのゲームしか実行できませんが、クラウド オートテスターでは、各ユーザーの好みに合わせてカスタマイズできる時間制御で複数のゲームとバイナリを実行できます。リポジトリのプロジェクト構成には、doc、auto tester、pgnstates、tests、player、および webgui ディレクトリが含まれます。自動テスターは、変更をローカルでテストするために使用される Java ローカル自動テスターであり、tests ディレクトリでは、自動テスト用の構成を指定できます。 Helen Xu は、Lesierchess が自動テスターとのインターフェースに使用する通信プロトコルであるユニバーサル チェスト インターフェース (UCI) も紹介しています。
  
  
• 00:20:00 このセクションでは、ゼロサム ゲームの相対的なスキル レベルに基づく評価システムである Elo 評価を使用してボットを測定および比較する方法について説明します。 Elo 評価は、時間だけでなく、UCI を使用して検索された 1 秒あたりのノード数にも基づいています。次にスピーカーは、ゲームのプレイについて詳しく説明します。たとえば、動きの生成、ボードの表現、位置を格納するために使用される構造体などです。さらに、移動は 28 ビットを使用して表されます。これには、駒の種類、向き、正方形、中間の正方形、および 2 つの正方形が含まれます。参照埋め込みは、ボードを反復処理し、その特定のピースからすべての動きを生成することにより、誰のターンであるかに応じてすべての動きを生成します。スピーカーは、デバッグ関数 perft を使用して、変更された手の生成が各位置から同じ動きを返すことを確認することに言及しています。
  
  
• 00:25:00 このセクションでは、スピーカーは、ヒューリスティックを使用して位置に基づいてスコアを生成する静的評価を通じて、動きが適切かどうかを判断する方法について説明します。ヒューリスティックには、キング、ポーン、および距離に焦点を当てたものが含まれており、位置が適切かどうかを判断するのに役立ちます。講演者はまた、ゲームをプレイするプログラムがどのように検索ツリーを使用してゲームをプレイし、評価に基づいて最善の手を選ぶかについても話します。ノードの数を減らすために、スピーカーは静止検索と最小最大検索について詳しく説明します。これにより、評価されるノードの量が改善され、パフォーマンスが向上します。
  
  
• 00:30:00 このセクションでは、スピーカーはアルファ ベータと呼ばれるアルゴリズムについて説明します。これは、ウィンドウ アルファ ベータを持つノードからの検索中に使用されます。検索の値がアルファを下回った場合、移動は十分ではなく、検索を続けます。ベータとは、基本的に一方が最大化を試み、一方が最小化を試みることを意味します。したがって、値がベータを超えると、ベータ カットオフが生成されます。これは、相手がその動きを許可しないためです。次に、スピーカーは、最初の手が最良のものであると仮定する原則バリエーション検索を説明し、ゼロウィンドウ検索とも呼ばれるスカウト検索を残りの手で実行して、それらがより悪いことを確認します。この検索方法は、アルファ ベータ アルゴリズムのバリエーションです。
  
  
• 00:35:00 このセクションでは、ミニマックス検索アルゴリズムにおけるサブツリーの枝刈りの概念について説明します。サブツリーの剪定の背後にある考え方は、これまでに見つかった最高のスコアよりも低いスコアを持つサブツリーを削除することです。これにより、評価されるノードの数が減り、検索プロセスが高速化されます。対戦相手も最善の手を探して、プレーヤーのスコアを最小限に抑えようとします。プレイヤーのスコアを最大化することと、対戦相手のスコアを最小化することのバランスが重要であり、目標は、プレイヤーにとって有益であり、対戦相手が許可する動きを見つけることです。
  
  
• 00:40:00 このセクションでは、Helen Xu がプリンシパル バリエーション プルーニングの概念について説明します。ここでは、左端のサブツリーが最適なパスであるという仮定が行われ、仮定が真の場合は早期に終了します。仮定が偽の場合、サブツリー全体を検索する必要があります。スカウト検索を使用して、これを下位のサブツリーに再帰的に適用し、最初のパスで仮定を検証します。この方法は枝刈りを改善し、ほとんどのゲーム ツリーをウィンドウ検索なしで処理します。
  
  
• 00:45:00 このセクションでは、Leiserchess プログラムの検索最適化について学びます。最も重要な最適化の 1 つは、転置テーブルを使用して以前に検出された位置を保存することです。これにより、不要な検索を回避して時間を節約できます。その他の最適化には、各位置に固有のハッシュを生成するための Zobrist ハッシュの使用、再計算する必要がないように適切な動きを格納するキラー ムーブ テーブル、アルファ スコアを増加させない動きの探索をスキップするための無益プルーニングが含まれます。ゲームの開始時に事前に計算された位置を保存し、検索の時間を節約するために、より優れたオープニング ブックの実装もお勧めします。
  
  
• 00:50:00 このセクションでは、スピーカーは、事前に計算できるオープン ブックやエンド ゲーム データベースなど、チェス プログラムを最適化するための便利なツールについて説明します。テストを行い、問題をデバッグすることなく革新し、進歩できるように、テストのための優れたインフラストラクチャを用意することが重要です。並列プログラミングで転置テーブルを使用する場合、テスト目的で転置テーブルをオフにできることが重要になります。また、テスト時には固定深さの検索を行うことをお勧めします。全体として、優れたテスト インフラストラクチャを持つことは、進歩を遂げ、重大なデバッグの問題を回避するために不可欠です。
  
  
• 00:55:00 このセクションでは、講演者が Leiserchess プロジェクトの eval.c ファイルについて説明し、そのサイズと複雑さのために一見圧倒されるように見えることについて説明します。ただし、ユーザーがそれに慣れるにつれて、適切なサイズのコードを処理することに自信が持てるようになります。 eval.c ファイルには、ピースのタイプとその色に基づいてボード上の各正方形を評価する、p between、p central、k face、k agressive などのヒューリスティックが含まれています。 p between ヒューリスティックはポーンが両方のキングの間にあるかどうかを決定し、p central はポーンがボードの中心にどれだけ近いかに基づいてボーナスを与えます。 k 面と k アグレッシブ ヒューリスティックは、キングの向きと、対戦相手やボードの端からの距離に基づいてボーナスを与えます。
  
  
• 01:00:00 このセクションでは、スピーカーは、ゲームの複雑な側面であるレーザー カバレッジについて説明します。レーザーカバレッジは、プレーヤーの色に応じて、特定の位置で可能なすべての動きを生成します。次に、動きのリストを提供し、話者は、このマップがその機能をどのように実行するかについて、while-true ステートメントを使用して詳しく説明します。レーザー パスは、パスを描画しているときに一部のポーンに跳ね返り、各マスの距離が長くなります。マップを生成した後、プロセスが繰り返され、距離がレーザーからの実際の距離で除算されます。この複雑なシステムは、ボード上の各ピースを見つけるための評価方法に必要な反復を最適化します。これにより、プロセスが遅くなります。話者は、ボードを異なる方法で表現し、両方の変換関数が同じ結果をもたらすと主張することを追加します。最適化の決定。
  
  
• 01:05:00 ビデオのこのセクションでは、スピーカーがコードの正確性を維持することの重要性と、それをテストする方法について説明します。彼らは、ある表現から別の表現に変換するとプロセスが遅くなる可能性があるが、パフォーマンスを最適化する前に正確性を確保するために必要であると説明しています。正確性をテストする 1 つの方法は、ノード数を追跡し、変更を加えた後も同じままであることを確認することです。また、コードを実行し、Lesierchess.c で UCI インターフェイスを表示する方法も示します。これにより、バイナリを毎回再コンパイルすることなく、さまざまな値を設定できます。最後に、ヒューリスティックの表を見て、自動テスターの値を指定する方法を説明します。
  
  
• 01:10:00 このセクションでは、スピーカーは Leiserchess ゲームが UCI インターフェイスを介してテーブルとコマンドを編集するために提供する優れた柔軟性について説明します。これにより、ユーザーは、新しいヒューリスティックを含む任意のコマンドにアクセスして実装し、解析と実装を制御できます。死んだコードがいくつか存在しますが、教授は視聴者を安心させ、それはクリーンアップされ、その他のバグは修正されるように報告する必要があります。最後に、このプロジェクトは毎分楽しいものではないかもしれませんが、全体的には十分に楽しめると彼は述べています。

[MetaQuotes]

講義 20. 投機的並列処理と Leiserchess

20. 投機的並列処理と Leiserchess

「20. 投機的並列処理と Leiserchess」というタイトルのこの YouTube ビデオでは、インストラクタが投機的並列処理の概念を紹介しています。これは、特定のタスクを並列で実行できることを先制的に推測し、コードを高速化することができます。ただし、スピーカーは、このコードは非決定論的であり、必要な場合にのみ使用する必要があることを警告すると同時に、より優れたシリアル コードを使用できる場合には使用しないように警告します。ビデオの大部分は、ゲーム ツリーをプルーニングして検索時間を最適化することを含む、並列アルファ ベータ検索についての議論を中心に展開しています。また、検索アルゴリズムの評価プロセスで使用されるさまざまなデータ構造とヒューリスティックについても、特に循環と静止を回避する際に使用されます。検索。このビデオでは、反復的な深化の利点と、それが検索のより良い移動順序付けにどのようにつながるかについても触れており、Zobrist ハッシングについても説明しています。これは、チェス盤の各位置の一意のハッシュ値を同じ駒で使用する検索アルゴリズムで使用される最適化手法です。

このビデオでは、転置テーブル、遅い手数の削減、手数生成のためのビットボードの使用など、チェス エンジンのさまざまな最適化手法についても説明します。講演者はまた、「投機的並列処理と Leiserchess」のトピックについても話し、ある動きがレーザーの経路に影響を与えるかどうかを評価し、「レーザー カバレッジ」を追求するようプログラマーにアドバイスしています。講演者は、古い表現をコードに残し、プログラムを使用して変更をテストすることを提案しています。彼らはまた、レーザーチェスのキングにレーザーがどれだけ近いかを測定するためのヒューリスティックを開発しました。より多くの最適化の提案には、プレイヤーのレーザーへの対戦相手の近さを評価するためのより良い方法の発見と、動きの並べ替えの最適化が含まれます。最後に、コードを適切にリファクタリングしてテストすることの重要性について説明します。

• 00:00:00 このセクションでは、インストラクタは、コードを最適化し、より高速に実行する方法として、投機的並列処理の概念を紹介します。これには、特定のタスクが本質的に逐次的であっても、並列で実行できると推測することが含まれます。推測が正しくないことが判明した場合、無駄な労力が発生する可能性があります。インストラクターは、合計のしきい値を設定する例を示し、部分的な合計がしきい値を超えた場合に早期に終了することによる簡単な最適化を示しますが、これにより予測可能な分岐が発生し、コードの速度が低下する可能性があります。
  
  
• 00:05:00 このセクションでは、スピーカーは、並列で動作するときに内部ループに追加しすぎる問題を軽減する方法について説明します。彼らは、ストリップマイニングを使用して、n回の反復のループを4回の反復のn回のループに置き換え、4回の反復の内側のループに置き換えると同時に、4回の反復ごとにしきい値を超えているかどうかを確認して、チェック。短絡ループを並列化するために、スピーカーは中止フラグをコードに追加し、それを再帰的に使用して、フラグを true に設定する前に、合計が制限を超えていて中止されていないかどうかを確認します。フラグを設定する前にフラグをチェックすることで、決定性競合を回避し、真の共有競合を防ぎます。
  
  
• 00:10:00 このセクションでは、ビデオで投機的並列処理について説明します。これは、並列処理を実行する必要があるとプログラムが予測し、プリエンプティブに動作するスポーンを生成する場合です。このコードは非決定論的であり、必要な場合にのみパフォーマンスの目的で使用する必要があります。アボート フラグをリセットし、並列処理の機会が他にほとんどなく、それが必要になる可能性が高い場合を除き、投機的な作業を生成しないことが不可欠です。このビデオでは、より優れたシリアル コードを使用できる場合に投機的並列処理を使用しないように警告しています。最後に、並列処理の場合、作業が不要になる可能性は、使用されるプロセッサの数よりも少なくなければならないという定理が参照されます。
  
  
• 00:15:00 このセクションでは、並列アルファ ベータ検索を中心に議論します。これには、ゲーム ツリーを剪定して検索時間を最適化することが含まれます。 Burkhardt Manin と彼の生徒たちは、最良順序のツリーでは、すべてのノードの次数が 1 または最大になることを観察しました。彼らの考えは、最初の子がベータ カットオフを生成できなかった後に、最良の動きが選択されたと推測することでした。これにより、作業を無駄にすることなく、残りの子を並行して検索できます。コード内のヒューリスティックは、若い兄弟の重み付けアルゴリズムを使用して最適な動きを選択するなど、物事が適切な順序で行われるようにするのに役立ちます。アルゴリズムは、サブ計算が不要であることが判明した場合にもサブ計算を中止します。
  
  
• 00:20:00 ビデオのこのセクションでは、スピーカーは、並列化で中止された祖先をチェックし、無駄な作業を避けるために定期的にツリーを登るメカニズムについて説明します。彼らは、ツリーを引き上げるにはコストがかかるため、チェックする頻度を決定するためにカウンターまたはブードゥーパラメーターを用意することを提案しています。スピーカーは、並列化で競合を引き起こす可能性がある転置テーブルのような検索で使用されるデータ構造についても話します。彼らは、データの競合を避けるために、ワーカーごとに複製するか、ロックすることを提案しています。最後に、スピーカーは、コードの推測やその他の非決定論的な部分をオフにして、デバッグをより簡単にする方法を用意することを推奨しています。
  
  
• 00:25:00 このセクションでは、スピーカーは 1999 年の世界コンピューター チェス選手権でほぼ優勝したプログラムについて話します。彼らはサンディア国立研究所の 1824 ノードのスーパーコンピューターで実行されていましたが、唯一の損失は Deep Blue にありました。彼らは、プログラムの速度が低下するため、テーブルにアクセスするためのロックを含めずに、プログラムの転置テーブルで競合が発生するようにすることにしました。彼らは、選択する値に影響を与え、最終的にトーナメントの結果に影響を与えるレースのオッズは低いと計算しました.
  
  
• 00:30:00 ビデオのこのセクションでは、スピーカーはチェス AI の意思決定に重要な 3 つのデータ構造について説明します。 1 つ目は「キラー」ヒューリスティックです。これは、コードの特定の深さで最良の動きを追跡し、本質的に反復する傾向があります。 2 つ目は「ベスト ムーブ」テーブルで、統計データに基づいて下位のすべてのムーブを並べ替えます。両方のデータ構造は共有されており、コードを並列化するときに適切に管理する必要があります。最終的なデータ構造はオープニング ブックで、ゲームの開始時に最適な動きを事前に計算します。しかし、講演者は、オープニング ブックよりも簡単に達成できる成果があり、統計的には、ほとんどのゲームはオープニング ブックが有益であるほど長く続かないことを示唆しています。
  
  
• 00:35:00 このセクションでは、チームが最強のチェス ボットを作成しようとするゲームである Leiserchess でオープニング ブックを構築する戦略についてスピーカーが説明します。スピーカーは、いくつかのチームが素晴らしいスタートで勝つことを可能にする強力なオープニングブックを作成することで成功したことを指摘しています.彼らはまた、両方に1つを使用するよりも、それぞれの側に別々のオープニングブックを保持する方が効果的であることを示唆しています.さらに、講演者は、予測可能性を避けるためにコードにわずかなランダム性を追加することを推奨していますが、ベータ 1 では最適化する必要はないと警告しています。最後に、彼らは、時間制御が切れるまでさまざまな深さで検索を実行することを含む、反復的な深化の戦略を提案しています。話者は、深さごとに作業量が指数関数的に増加するため、これは良い戦略であることに注意しますが、重要な情報は最初の数深さで蓄積されます。
  
  
• 00:40:00 このセクションでは、反復的な深化の利点と、それが検索の移動順序の改善にどのようにつながるかについて、ビデオで詳しく説明します。反復的な深化を経ることで、転置テーブルはすべての中間位置の最良の移動順序情報を格納できるため、より深い深さで枝刈りがより効果的になります。さらに、反復的な深化を行うことで、時間制御の優れたメカニズムも提供します。このビデオでは、ゲーム データベースと、エンドゲーム データベースを作成することが有益である理由についても触れています。また、単純なブール値ではなく交配までの距離を保存することで、エンドゲーム データベースでサイクリングを回避する方法についても説明しています。
  
  
• 00:45:00 このセクションでは、スピーカーは検索アルゴリズムの評価プロセスで使用されるさまざまなヒューリスティックについて説明します。特に循環と静止検索を回避する際に使用されます。話者は、現在の距離よりも 1 少ない距離で勝つ距離を探して、勝つまでの距離を維持し、サイクリングを避けることの重要性に言及します。使用されるもう 1 つのヒューリスティックは、ムーブ プルーニングです。これは、じっと座っていることは、通常、ムーブを実行するほど良くありません。ノームーブ プルーニングでは、ポジションが非常に優れているため、何もしなくても勝利につながる場合に、検索を簡素化するためにヌル ムーブが適用されます。 .講演者は、チェスのズーグス ワンについても説明し、強制的な手が 1 つしかない場合に、チェスのライ検索でどのように手の拡張機能が使用されるかについても説明します。
  
  
• 00:50:00 このセクションでは、スピーカーは検索アルゴリズムでの転置テーブルの使用について話します。これは、転置された移動によって同じ位置に到達できるため、実際には DAG (有向非巡回グラフ) です。転置テーブルは、同じ位置を再度検索することを避けるために移動の値を確立するために、検索された深さによって決定される品質スコアを格納します。完全な検索ができず、保存された値の精度が低下する可能性があるため、品質が低すぎる移動を使用しないことが重要です。さらに、特別なコードを使用して、深さから非常に大きな数を差し引いて計算された合致位置を格納し、合致するようにします。検索アルゴリズムで使用される最適化手法である Zobrist ハッシングについても、同じピースを持つボード上の各位置の一意のハッシュ値を含めて説明されています。
  
  
• 00:55:00 このセクションでは、Leiserson 教授が、チェス盤上のさまざまな駒の位置を表すハッシュ関数を効率的に更新するために使用される Zobrist ハッシュの概念について説明します。ハッシュ関数では、ピースの種類、行、列、方向のさまざまな組み合わせに対応する乱数のテーブルを生成します。ハッシュ関数は、XOR 演算を使用して、すべてのピースの値とその向きの XOR を取得することでハッシュを計算します。 Zobrist ハッシュは、XOR プロパティを利用して、削除されるピースの値を XOR 演算して残りのピースのハッシュを取得することにより、ハッシュ関数からピースを削除します。これにより、実行された移動に対して 2 つの XOR 操作のみで、ハッシュ関数の安価で効率的な更新が可能になります。
  
  
• 01:00:00 このセクションでは、スピーカーはチェス エンジンのさまざまな最適化手法について説明します。彼は転置テーブルについて語っています。これは、移動の Zobrist キー、スコア、品質、バインド タイプの記録を保存し、古い移動を削除します。さらに、彼は、時間を節約するために、あまり有望でない手があまり深く検索されない、遅い動きの削減の概念について言及しています。講演者はまた、ボードの表現と、ビット トリックを使用してビットのシフトやカウントなどの操作を効率的に実行することで、ビットボードを使用して移動の生成やその他のチェスの概念を高速化する方法についても話します。
  
  
• 01:05:00 このセクションでは、スピーカーは「投機的並列処理と Leiserchess」のトピックについて説明します。彼は、レーザーを扱う際に行うことができる主な最適化の 1 つは、動きがレーザーの経路に影響を与えるかどうかを評価することであると説明しています。さらに、講演者は、「レーザー照射」は非常に高価であるため、「レーザー照射」を利用することを提案しています。彼はまた、プログラマーに対して、コードに古い表現を残し、物事が同等であると主張するアサーションを入れ、Perfectiy のようなプログラムを使用して、変更を加えたかどうかを判断するようにアドバイスしています。最後に、彼は、レーザーをキングに近づけるためにプログラムがどのように機能するか、およびゲーム内での位置の重要性について説明します。
  
  
• 01:10:00 このセクションでは、スピーカーは、レーザーチェスで相手のキングにレーザーがどれだけ近づいているかを測定するために開発した新しいヒューリスティックについて説明します。彼らは、キングからのレーザーの距離を計算することによって各動きを評価し、離れた位置ごとに 1 を数え、敵に跳ね返った場合は追加の値を数えます。彼らは、各正方形に到達できる最小数を取り、乗数を使用して、キングの近くにいることがどれほど良いかを重み付けします.彼らはそれをすべて加算し、魔法の定数乗数を掛けて、値をポーンの分数として表します。結果の数は、平均で約 4 つまでの範囲です。
  
  
• 01:15:00 このセクションでは、スピーカーはチェス エンジンの効率を向上させるさまざまな方法について説明します。提案の 1 つは、現在の方法は計算コストが高いため、プレイヤーのレーザーに対する対戦相手の近さを評価するためのより良い方法を見つけることです。最適化のもう 1 つの領域は、移動の並べ替えです。これは、特にふるいにかける移動が多数ある場合は、コストがかかる可能性があります。スピーカーは、関連する動きのみがソートされ、不要なソートが回避されるように、ソートを最適化する方法を見つけることを提案しています。話者はまた、ボードの表現を変更するのは骨の折れるプロセスである可能性があると述べていますが、より効率的なビットボード表現の代替手段があります。
  
  
• 01:20:00 このセクションのビデオでは、コードをリファクタリングし、適切にテストして、コードを壊さずに変更が正しく行われたことを確認することの重要性について説明しています。講演者は、大規模なリファクタリングなしでボード表現を簡単に変更できるように、関数呼び出しを変更する前にボード アクセスをリファクタリングすることを提案しています。適切なテストは、変更が正しく、コードが壊れていないことを確認するためにも不可欠です。また、予測不可能性を回避するためにコードを決定論的にすることが重要です。講演者はまた、有名人に会ってこの分野についてさらに学ぶ貴重な機会として、John Bentley による今後の講演についても言及しています。