MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Julian ShunView the complete course: https://ocw.mit.edu/6-172F18YouTube Playlist...
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Julian ShunView the complete course: https://ocw.mit.edu/6-172F18YouTube Playlist...
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Tao B. SchardlView the complete course: https://ocw.mit.edu/6-172F18YouTube Playl...
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 乗になります。
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Julian ShunView the complete course: https://ocw.mit.edu/6-172F18YouTube Playlist...
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:45:00 このセクションでは、キャッシングと並列処理の相互作用について説明します。彼らは、シリアル実行でキャッシュミスを最小限に抑えると、低スパンアルゴリズムを想定して、並列実行でキャッシュミスを本質的に最小限に抑えることができるという定理を説明しています。次に、台形アルゴリズムが V カットを使用して並列に動作する方法を示します。この場合、2 つの独立した台形が並列に実行され、その後灰色の台形が実行されます。彼らはまた、逆台形に使用される逆 V カットについても言及しています。
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Julian ShunView the complete course: https://ocw.mit.edu/6-172F18YouTube Playlist...
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Charles LeisersonView the complete course: https://ocw.mit.edu/6-172F18YouTube Pl...
ビデオの 2 番目の部分では、並列プログラムでのエラーを防止するためのメモリ フェンスと同期命令の使用について説明します。講演者は、メモリ フェンスを暗黙的または明示的に実装するさまざまな方法と、プロセッサのさまざまな側面に取り組んでいるさまざまなチーム間の慎重なエンジニアリングと調整の重要性について説明します。さらに、講師は、C11 言語標準のロックフリー アルゴリズムの一部として CAS 命令を使用して、定数スペースのみを使用して n スレッド デッドロックのない相互排除アルゴリズムのミューテックスを実装する方法について説明します。 Charles Leiserson は、マルチスレッド システムでロックを使用する際の問題と、代わりに CAS を使用する解決策について説明しています。スレッドが長時間ロックを保持すると、同じリソースへのアクセスを待機している他のスレッドを潜在的にブロックする可能性があるからです。さらに、このビデオでは、コンペア アンド スワップに関する ABA 問題の潜在的な問題が強調されており、このトピックに関心のある人は、ロックフリー アルゴリズムについて詳しく学ぶことができます。
00:25:00 このセクションでは、スピーカーはロックなしで同期するプロセスを説明します。これらは、命令チェーンを確立し、それらが正しい順序で発生することを保証して、同期エラーを回避します。デモンストレーションとして、Bob と Alice が共有リソースにアクセスしたいという例を使用します。彼らは、同期するとき、エンジニアは注意して「物事の前に起こる」ことを確認して、それらが正しい順序で発生していることを確認する必要があると説明しています.
01:15:00 このセクションでは、Charles Leiserson が、マルチスレッド システムでロックを使用する際の問題と、代わりに CAS を使用する解決策について説明します。ロックを使用すると、スレッドが長時間ロックを保持し、同じリソースへのアクセスを待機している他のスレッドをブロックする可能性があります。ただし、CAS を使用すると、x のロードの後に一時を計算した後、x のストアが続きます。また、変数 old と new を使用して古い結果を格納し、一時的な結果をその古い値に追加して、新しい値を生成することができます。古い値が変更されていない場合はスワップインされます。また、Charles はコンペア アンド スワップに関する ABA の問題についても言及しており、このトピックに関心のある人には、ロックフリー アルゴリズムについてさらに学ぶよう勧めています。
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Charles LeisersonView the complete course: https://ocw.mit.edu/6-172F18YouTube Pl...
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Saman AmarasingheView the complete course: https://ocw.mit.edu/6-172F18YouTube Pl...
00:55:00 このセクションでは、講演者が Leiserchess プロジェクトの eval.c ファイルについて説明し、そのサイズと複雑さのために一見圧倒されるように見えることについて説明します。ただし、ユーザーがそれに慣れるにつれて、適切なサイズのコードを処理することに自信が持てるようになります。 eval.c ファイルには、ピースのタイプとその色に基づいてボード上の各正方形を評価する、p between、p central、k face、k agressive などのヒューリスティックが含まれています。 p between ヒューリスティックはポーンが両方のキングの間にあるかどうかを決定し、p central はポーンがボードの中心にどれだけ近いかに基づいてボーナスを与えます。 k 面と k アグレッシブ ヒューリスティックは、キングの向きと、対戦相手やボードの端からの距離に基づいてボーナスを与えます。
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Helen XuView the complete course: https://ocw.mit.edu/6-172F18YouTube Playlist: h...
00:25:00 このセクションでは、スピーカーは 1999 年の世界コンピューター チェス選手権でほぼ優勝したプログラムについて話します。彼らはサンディア国立研究所の 1824 ノードのスーパーコンピューターで実行されていましたが、唯一の損失は Deep Blue にありました。彼らは、プログラムの速度が低下するため、テーブルにアクセスするためのロックを含めずに、プログラムの転置テーブルで競合が発生するようにすることにしました。彼らは、選択する値に影響を与え、最終的にトーナメントの結果に影響を与えるレースのオッズは低いと計算しました.
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Charles LeisersonView the complete course: https://ocw.mit.edu/6-172F18YouTube Pl...
講義 11. ストレージの割り当て
講義 11. ストレージの割り当て
このビデオでは、講師がストレージの割り当てについて説明し、メモリの割り当てと解放の両方をカバーしています。スタックやヒープ、固定および可変サイズの割り当てスキームなど、さまざまなタイプのストレージが扱われています。ディスクページごとのフリーリストやビットマップなどのソリューションを使用して、メモリブロックが分散することによって引き起こされる外部フラグメンテーションについても説明します。参照カウントやこのアルゴリズムの制限など、ガベージ コレクションの概念も紹介されています。 「マーク アンド スイープ」および「ストップ アンド コピー」ガベージ コレクション手順についても説明し、後者がフラグメンテーションにどのように対処するか、およびポインターの更新によって生じる可能性のある正確性の問題に焦点を当てています。このビデオは、ストップ アンド コピー アルゴリズムの時間と空間の複雑さと、外部フラグメンテーションの排除に関するメモで締めくくられています。
このビデオでは、バディ システム、マークとスイープの手順、最適化、世代別およびリアルタイムのガベージ コレクション、マルチスレッド ストレージ割り当て、並列ガベージ コレクションなど、動的ストレージ割り当てに関連するさまざまなトピックについて説明します。講師は、世代別ガベージ コレクションは、若いオブジェクトがより頻繁にスキャンされるという考えに基づいていると説明しています。一方、リアルタイム ガベージ コレクションは、プログラムの実行中にバックグラウンドで実行されますが、オブジェクトとポインター グラフが変化し続けると、正確性の問題が発生する可能性があります。最後に、スタックやヒープなどのさまざまな種類のストレージ割り当てと、参照カウント、マーク アンド スイープ、ストップ アンド コピーなどのガベージ コレクションのさまざまな方法についてまとめます。講師は、学生は今後の宿題でこれらの方法のいくつかを試すことができると述べています.
講義 12. 並列ストレージ割り当て
講義 12. 並列ストレージ割り当て
このビデオでは、さまざまなメモリ割り当て戦略とそのトレードオフについて説明しています。 malloc とアラインされた割り当ての使用、および free による適切なメモリ割り当て解除の重要性が説明されています。外部の断片化とパフォーマンスの低下の問題とともに、仮想メモリの割り当てに Mmap を使用する方法についても説明します。 C および C++ プログラミングにおけるスタックの概念が調査され、スタック フレームを割り当てるためのヒープベースのサボテン スタック アプローチに重点が置かれています。断片化を最小限に抑えるために小さなブロックを最適化することの重要性とともに、線形スタックのプールの使用についても説明します。このビデオは、グローバルおよびローカル ヒープ アプローチとそれらの潜在的な問題、およびこれらの問題に対処するためのビン フリー リストや定期的なメモリ リバランスなどのアプローチについての議論で締めくくられています。
このビデオでは、並列ストレージ割り当てのソリューションについても説明し、ソリューションとして Hoard アロケーターを紹介しています。 Hoard アロケーターは、ローカル ヒープとグローバル ヒープ、およびヒープ間で移動できる大きなスーパー ブロックの組み合わせを使用して、偽共有を減らし、スケーラビリティを向上させ、外部の断片化を減らします。グローバル ヒープに割り当てられる最大ストレージは、最大でローカル ヒープに割り当てられる最大ストレージであり、フットプリントの上限は、ユーザー フットプリントとローカル ヒープ内の割り当て済みで未使用のストレージです。このビデオでは、Je malloc や Super malloc などの他のアロケーターについても簡単に説明しています。ベンチマークの結果は、Super malloc が Je malloc や Hoard よりもパフォーマンスが優れていることを示しています。ディスカッションは、ガベージ コレクションの詳細についてオンライン スライドを参照して締めくくります。
講義 13. Cilk ランタイム システム
講義 13. Cilk ランタイム システム
Cilk ランタイム システムは、ランダム化されたワーク スティーリング スケジューラを使用して実行時にプロセッサに計算をマッピングし、並列プロセッサでの計算のスケジューリングと負荷分散を担当します。このシステムは、盗むための追加コストを犠牲にしても、プログラムのシリアル実行を最適化するように設計されています。ワーカーは、スタック フレームへのポインターを含み、ヘッド ポインターとテール ポインターを使用する別のデッキ データ構造を維持します。盗むことができるフレームには、デックが呼び出しスタックの外部にある間に盗むために必要な情報を含む追加のローカル構造があります。このセクションでは、システムが実行中の関数の途中からプロセッサが実行を開始できるようにする方法と、特定のプロセッサがまだ計算の終了を待っているためにそのポイントを超えて実行できない sync ステートメントに到達すると、プロセッサ間の同期がどのように複雑になるかについて説明します。さらに、スピーカーは、システムのパフォーマンス、設計上の考慮事項とデータ構造、およびシステムが THC プロトコルを使用して実行を最適化する方法について説明します。これには、作業を実行するワーカー用と泥棒用の 2 つのプロトコル セットが含まれます。
Cilk ランタイム システムは、セット ジャンプおよびロング ジャンプ プロトコルを使用して、犠牲プロセスの実行デックからの計算の盗難を処理します。 Cactus スタックの抽象化により、泥棒プロセスは独自の呼び出しスタックを持つことができ、被害者のスタックの破損を防ぐことができます。システムの同期プロトコルは、計算ツリーと Cactus スタックを使用して、関数内のネストされた計算間でのみ同期が行われるようにします。フル フレーム ツリーは、同期プロセスを簡素化するために、未処理のサブ計算を含む計算間の親子関係を維持します。さらに、ランタイム システムは、現在の関数に未処理の子計算がなく、すべてのワーカーがビジーであるという一般的なケースを最適化します。サポートされているその他の機能には、C++ 例外、リデューサー ハイパー オブジェクト、血統などがあります。
講義 14. キャッシングとキャッシュ効率の良いアルゴリズム
講義 14. キャッシングとキャッシュ効率の良いアルゴリズム
キャッシングとキャッシュ効率の高いアルゴリズムに関するビデオで、講師は最新のマシンのキャッシュ階層、完全連想キャッシュとダイレクト マップ キャッシュの違い、セット アソシエイティブ キャッシュの長所と短所について説明します。このビデオでは、理想的なキャッシュ モデルとキャッシュ効率の高いアルゴリズムの概念についても紹介しています。スピーカーは、キャッシュ ミスの補題、tall キャッシュの仮定、およびサブマトリックス キャッシングの補題について説明します。また、サブマトリックスの読み取り時およびマトリックスの乗算中に発生したキャッシュ ミスも分析します。このビデオは、タイル化された行列乗算の概念と、それがパフォーマンスを大幅に向上させる方法を紹介することで締めくくられていますが、移植性がなく、複数レベルのキャッシュを最適化するにはコストがかかる可能性があることにも注意してください。
この講義では、例として再帰的な行列の乗算を使用して、キャッシングとキャッシュ効率の高いアルゴリズムについて説明します。講演者は、ワーク ミスとキャッシュ ミスの両方を個別に分析することの重要性を強調し、キャッシュ サイズが異なるため、キャッシュ対応アルゴリズムがすべてのマシンに最適ではない可能性があることに注意します。講演者は、任意のキャッシュ サイズに合わせて自動調整するキャッシュ無視アルゴリズムについても説明し、並列キャッシュ無視コードの開発について言及します。最後に、目標は、キャッシュ認識またはキャッシュ無視のアルゴリズムを設計することです。キャッシュ無視アルゴリズムの設計に関する議論は、次の講義で続けます。
講義 15. キャッシュを無視するアルゴリズム
講義 15. キャッシュを無視するアルゴリズム
このビデオでは、マシンのキャッシュ サイズを自動的に調整し、優れたキャッシュ効率を実現し、マシンのキャッシュ パラメータの知識を必要としない、キャッシュ無視アルゴリズムについて説明します。このビデオでは、2D マトリックスでステンシル法を使用して、微分方程式を通じて熱拡散をシミュレートするためのコードを記述する方法を示します。コードにはループ バージョンと台形バージョンの両方があり、後者の方がキャッシュ効率が高くなりますが、ループ コードのアクセス パターンが予測可能であるため、2D シミュレーションではそれほど高速ではありません。このビデオでは、キャッシングと並列処理の相互作用、および潜在的な並列速度向上のボトルネックの診断についても説明しています。最後に、講演者は、ステンシルの計算と、ステンシルと呼ばれる固定パターンを使用して配列内の各ポイントを更新する方法について説明します。ステンシルは、キャッシュ ミスが発生する可能性があり、時間的および空間的な局所性を利用する効率的なアルゴリズムを使用して削減できるストレージ要件があります。
ビデオの 2 番目の部分では、並べ替えとマージのためのキャッシュ無視アルゴリズムについて説明します。具体的には、ビデオはマージソートのキャッシュの複雑さをカバーし、マルチウェイマージの概念を紹介し、マルチウェイマージアルゴリズムのキャッシュの複雑さを説明します.このビデオでは、ファネル ソート アルゴリズムについても説明します。これは、K 乗要素と K ソート リストをマージできる、キャッシュ無視のソート アルゴリズムです。ファンネルソートアルゴリズムは最適であり、K ファンネルの平方根で再帰的に構築されます。このビデオでは、b ツリー、順序付きファイル メンテナンス、優先キューなど、他にも多くのキャッシュ無視アルゴリズムとデータ構造があることを説明しています。全体として、このビデオは、このトピックについて詳しく知りたい人向けに、キャッシュを無視するアルゴリズムの概要を提供します。
講義 16. 非決定論的並列プログラミング
講義 16. 非決定論的並列プログラミング
このビデオでは、決定論的および非決定論的な並列プログラミングに関連するさまざまな概念について説明します。スピーカーは、異常な動作や困難なデバッグにつながる可能性があるため、非決定論を回避することの重要性を強調しています。非決定性を管理するための戦略には、固定値、レコードの再生、分析ツール、カプセル化、単体テストの使用が含まれます。ミューテックスの使用については、回転と譲歩、再入可能と非再入可能、公平と不公平など、詳細に検討されています。講演者はまた、並列プログラミングのコンテキストにおけるコンテキスト切り替えの概念と「スキーのレンタル問題」についても触れています。最後に、マルチコア プロセッサにおけるパフォーマンス エンジニアリングの基本原則について説明します。
ビデオの 2 番目の部分では、並列プログラミングにおけるデッドロックの問題を取り上げ、待機サイクルがないことを保証するミューテックスの線形順序付けなど、デッドロックを回避するためのソリューションを提供します。さらに、スピーカーは、すべての更新を一度にコミットするトランザクションとして重要な領域を表すことによって原子性を保証するトランザクション メモリの概念を紹介します。次にビデオでは、グローバル ロックを必要とせずにデッドロックとスタベーションを防ぐために、有限所有権配列とリリース ソートを必要とするメソッドを使用したロックベースのアプローチを使用するアルゴリズムを紹介します。最後に、リリースソートと再取得のアルゴリズムについて説明します。これにより、複数のロックが同時にロックを取得しようとするのを防ぎ、パフォーマンスの問題を回避できます。
講義 17. ロックなしの同期
講義 17. ロックなしの同期
Charles Leiserson は、YouTube ビデオでロックなしの同期の概念を探っています。彼は、シーケンシャルな実行を確実にするために命令のグローバルな線形順序の必要性を示す例を提供し、シーケンシャルの一貫性によって相互排除を達成し、ロックを使用することの困難と潜在的な問題を回避する方法について説明します。 Leiserson は、Peterson のアルゴリズムを、ロード操作とストア操作のみを使用して、並行プロセスからの干渉なしにクリティカル セクションにアクセスするソリューションとして提示しています。このビデオでは、ハードウェアの並べ替えによるメモリを介した同期の課題と、他の命令との相対的な順序を維持するためのメモリ フェンスの概念についても取り上げています。 Leiserson は、並列マシンの順次一貫性をサポートすることは有益ですが、ハードウェア設計者にとっては実現が難しいと主張しています。
ビデオの 2 番目の部分では、並列プログラムでのエラーを防止するためのメモリ フェンスと同期命令の使用について説明します。講演者は、メモリ フェンスを暗黙的または明示的に実装するさまざまな方法と、プロセッサのさまざまな側面に取り組んでいるさまざまなチーム間の慎重なエンジニアリングと調整の重要性について説明します。さらに、講師は、C11 言語標準のロックフリー アルゴリズムの一部として CAS 命令を使用して、定数スペースのみを使用して n スレッド デッドロックのない相互排除アルゴリズムのミューテックスを実装する方法について説明します。 Charles Leiserson は、マルチスレッド システムでロックを使用する際の問題と、代わりに CAS を使用する解決策について説明しています。スレッドが長時間ロックを保持すると、同じリソースへのアクセスを待機している他のスレッドを潜在的にブロックする可能性があるからです。さらに、このビデオでは、コンペア アンド スワップに関する ABA 問題の潜在的な問題が強調されており、このトピックに関心のある人は、ロックフリー アルゴリズムについて詳しく学ぶことができます。
講義 18. ドメイン固有言語と自動チューニング
講義 18. ドメイン固有言語と自動チューニング
このビデオでは、MIT の EECS 部門の Saman Amarasignhe 教授が、パフォーマンス エンジニアリングにおけるドメイン固有言語 (DSL) と自動チューニングを使用する利点について説明しています。彼は、DSL の重要性を強調しています。DSL は、汎用言語では記述が困難な領域固有のドメインをキャプチャし、プログラマーがドメインの専門家の知識を利用してパフォーマンスを向上できるようにします。 Singh は、グラフの分割や計算におけるグラフの形状の重要性など、DSL を使用したグラフ プロセスの最適化について説明しています。彼は、画像処理用の DSL Halide を紹介します。これにより、高速なコードの最適化とマシン間での移植性が可能になります。彼は、Google や Adobe などのさまざまな業界での Halide の使用について説明しています。最後に、並列性、局所性、および冗長作業に焦点を当てながら、コードを最適化するさまざまなアプローチを試すことの重要性を強調しています。
このビデオでは、パフォーマンス エンジニアリングの課題と、プログラムを効率的に実行するための最適なパラメーターを見つけることについても説明しています。講演者は、オートチューニングが大きなパラメータ空間を自動的に検索して最適な値を見つけることにより、この問題に対処できることを示唆しています。彼は、徹底的な検索は非現実的である可能性があり、ヒューリスティック ベースのソリューションは最適ではない可能性があると指摘しています。許容値のスペースを定義し、パフォーマンス結果に基づいて反復する自動調整により、最適なソリューションを見つけるプロセスを高速化できます。講演者は、Try のスケジュール生成における自動調整の適用についても説明します。Try は、網羅的な検索よりも効率的かつ効果的にスケジュールを生成することができました。
講義 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 インターフェイスによって提供される優れた柔軟性についても説明します。これにより、ユーザーはテーブルやコマンドを好みに合わせて編集できるようになり、デッド コードがクリーンアップされ、その他のバグが修正されるように報告する必要があることを視聴者に安心させます。
講義 20. 投機的並列処理と Leiserchess
20. 投機的並列処理と Leiserchess
「20. 投機的並列処理と Leiserchess」というタイトルのこの YouTube ビデオでは、インストラクタが投機的並列処理の概念を紹介しています。これは、特定のタスクを並列で実行できることを先制的に推測し、コードを高速化することができます。ただし、スピーカーは、このコードは非決定論的であり、必要な場合にのみ使用する必要があることを警告すると同時に、より優れたシリアル コードを使用できる場合には使用しないように警告します。ビデオの大部分は、ゲーム ツリーをプルーニングして検索時間を最適化することを含む、並列アルファ ベータ検索についての議論を中心に展開しています。また、検索アルゴリズムの評価プロセスで使用されるさまざまなデータ構造とヒューリスティックについても、特に循環と静止を回避する際に使用されます。検索。このビデオでは、反復的な深化の利点と、それが検索のより良い移動順序付けにどのようにつながるかについても触れており、Zobrist ハッシングについても説明しています。これは、チェス盤の各位置の一意のハッシュ値を同じ駒で使用する検索アルゴリズムで使用される最適化手法です。
このビデオでは、転置テーブル、遅い手数の削減、手数生成のためのビットボードの使用など、チェス エンジンのさまざまな最適化手法についても説明します。講演者はまた、「投機的並列処理と Leiserchess」のトピックについても話し、ある動きがレーザーの経路に影響を与えるかどうかを評価し、「レーザー カバレッジ」を追求するようプログラマーにアドバイスしています。講演者は、古い表現をコードに残し、プログラムを使用して変更をテストすることを提案しています。彼らはまた、レーザーチェスのキングにレーザーがどれだけ近いかを測定するためのヒューリスティックを開発しました。より多くの最適化の提案には、プレイヤーのレーザーへの対戦相手の近さを評価するためのより良い方法の発見と、動きの並べ替えの最適化が含まれます。最後に、コードを適切にリファクタリングしてテストすることの重要性について説明します。