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

[MetaQuotes]

MIT 6.172 ソフトウェア システムのパフォーマンス エンジニアリング、2018 年秋 - 1. 導入と行列乗算

1. 導入と行列乗算

「1. Introduction and Matrix Multiplication」というタイトルのこの YouTube ビデオでは、講師がパフォーマンス エンジニアリングの重要性と、それがどのように進化してきたかについて説明しています。行列乗算の例を使用して、講演者は、コーディング手法とマシン仕様がパフォーマンスにどのように大きく影響するかを示します。ディスカッションでは、ループの順序、キャッシュの使用、並列プログラミングなどのトピックが取り上げられています。講演者は、さまざまなプロセッサや算術計算用にコードを最適化する方法についても説明します。全体として、このビデオは、パフォーマンス エンジニアリングの世界と、現代のコンピューティング システムにおけるその実用的なアプリケーションに関する貴重な洞察を提供します。

• 00:00:00 このセクションでは、講師がパフォーマンス エンジニアリングの重要性と、それが研究される理由について説明します。ソフトウェア開発に関しては、パフォーマンスが常に最優先事項であるとは限りません。ただし、これはコンピューティングの通貨であり、プログラミングの容易さ、セキュリティ、正確性など、他の望ましい特性を購入するために使用されます。パフォーマンスが低下するとソフトウェアが使用できなくなる可能性があり、コンピューティング システムに対する人々の主な不満は、システムが遅すぎるというものです。したがって、パフォーマンスには本質的な価値はないかもしれませんが、開発者が気にかけていることに貢献します。
  
  
• 00:05:00 このセクションでは、スピーカーはコンピューティングにおけるパフォーマンス エンジニアリングの歴史と、限られたマシン リソースによる集中的なパフォーマンス エンジニアリングの初期から、チップ密度が 2 年ごとに 2 倍になり、待っているムーアの法則の時代への移行について説明します。ハードウェアが追いつくことは、ソフトウェアを最適化することよりも有益でした。ただし、スピーカーは、電力を削減することでクロック速度を大きくすることを可能にするデナード スケーリングが 2004 年に終了したため、パフォーマンス エンジニアリングの必要性がこれまで以上に重要になっていると述べています。講演者には、コンピューター科学者のドナルド・クヌース、ビル・ウルフ、マイケル・ジャクソンの引用が含まれており、読みやすいコードの重要性と時期尚早の最適化に対する警告が含まれています。
  
  
• 00:10:00 このセクションでは、スピーカーは、2000 年代初頭に電力密度のために達したクロック速度の限界について説明し、その結果、パフォーマンスをスケーリングするためにマルチコア プロセッサが開発されました。しかし、これは、パフォーマンスが無料ではなくなり、並列プログラミングが必要になることを意味していました。これは、業界がこれまで行ったことのないことでした。その時点から、ソフトウェアは新しいハードウェア構成に適応して効果を発揮する必要があり、その結果、ソフトウェア開発ジョブのパフォーマンスがますます重視されるようになりました。
  
  
• 00:15:00 このセクションでは、スピーカーは、最新のハードウェアを効率的に使用するソフトウェアの作成方法を学習することの実践的および理論的な重要性を説明することから始めます。次に、十分に研究されている行列乗算の問題を使用したパフォーマンス エンジニアリングの例を示し、使用するマシンについて、並列処理、キャッシュ サイズ、メモリ容量などの仕様と機能を含めて説明し、最後に次の説明で締めくくります。行列乗算のための Python の基本コード。スピーカーは、マシンのパワーと、その機能を活用した楽しいプロジェクトの可能性を強調しています。
  
  
• 00:20:00 このセクションでは、講師が行列乗算のコンテキストにおける Python、Java、および C++ のパフォーマンスについて説明します。講義では、Python は実行時間が約 21,000 秒と大規模な行列乗算には遅すぎることを示しています。Java はより高速で、Python の約 9 倍のスピードアップを実現し、C++ は約 1,100 秒の実行時間で最速です。これは、Java の 2 倍、Python の 18 倍高速です。
  
  
• 00:25:00 このセクションでは、講演者は、Python のようなインタープリター型言語、C のようなコンパイル済み言語、およびバイトコードにコンパイルされてからインタープリターされる Java のような言語の間のパフォーマンスの違いについて説明します。 Python のようなインタープリターは汎用性がありますが低速ですが、C のようなコンパイラーはハードウェアとマシン命令を利用してパフォーマンスを最適化します。 JIT コンパイラーは、Java で使用されているものと同様に、最も頻繁に実行されるコード部分のみをコンパイルすることで、ある程度のパフォーマンスを回復します。講演者は、Python のパフォーマンス モデルは理解しにくいと述べています。そのため、コースではパフォーマンスの比較に C を使用します。ただし、Python などのマネージ言語でのパフォーマンス エンジニアリングについて説明するゲスト レクチャーがあります。
  
  
• 00:30:00 このセクションでは、行列乗算のパフォーマンスに対するループ順序の重要性について説明します。ループの順序は、実行時間に影響を与えるキャッシュの局所性に影響します。行列は、C では行優先の順序で、Fortran では列優先の順序でメモリに配置されます。次数 ijk のアクセス パターンは、C の空間的局所性は良好ですが、B の空間的局所性は不十分です。ツール「cachegrind」はコードのミス率を判断するのに役立ち、コンパイラ フラグの調整などの単純な変更でもパフォーマンスを向上させることができます。
  
  
• 00:35:00 このセクションでは、スピーカーはコードを最適化してマシンのパフォーマンスを向上させる方法について説明します。 -O2 や -O3 などの適切な最適化フラグを選択することが重要ですが、コードによっては、最適化フラグを低くすると、実際により適切に最適化される場合があります。さらに、マルチコア プロセッサは、シルク インフラストラクチャを使用した並列ループで利用できるため、18 コアでほぼ 18 倍のスピードアップが実現します。スピーカーは、外側のループを並列化することは、実際にプログラムの速度を低下させる可能性がある内側のループを並列化するよりも効果的であることを強調しています。ただし、キャッシュミスやベクトル化された命令を効果的に使用していないなど、最適化の機会が依然として存在します。
  
  
• 00:40:00 このセクションでは、スピーカーは、計算を再構築してキャッシュ内のデータを可能な限り再利用することにより、キャッシュ ミスをより適切に管理する方法について説明します。タイル スキーマを使用することで、行列は小さなサブ行列に分割され、ブロックで乗算されて、必要なメモリ アクセスの数が削減されます。スピーカーは、部分行列のサイズを決定するには調整パラメータが必要であると説明し、実験が最適な値を見つける最良の方法であることを示唆しています。このアプローチにより、スピーカーは、同じサイズのフットプリントを計算するために必要なメモリアクセスの数を大幅に削減し、計算をより効率的にできることを示しています。
  
  
• 00:45:00 このセクションでは、スピーカーは、キャッシュ使用の改善や実行時間の短縮など、行列乗算を実行するときにブロッキングまたはタイリングを使用する利点について説明します。チップが持つさまざまなレベルのキャッシュと、プログラマーがチューニング パラメーターを使用して各キャッシュ レベルのコードを最適化する方法について説明します。ただし、チューニングのプロセスはキャッシュの各レベルでより複雑になり、コードが読みにくく、理解しにくくなる可能性があります。講演者は、並列プログラミングを使用して小さなサブ問題を再帰的に解決する分割統治アプローチを提案しています。この方法はキャッシュの使用を改善しますが、関数呼び出しのオーバーヘッドにより計算が遅くなり、巧妙なパフォーマンス エンジニアリングの必要性が強調されます。
  
  
• 00:50:00 このセクションでは、スピーカーは、分割統治法を使用した行列乗算の最適化と、アルゴリズムを使用するためのしきい値の調整について説明します。しきい値が特定の数値を下回った場合の基本ケースが設定され、アルゴリズムは通常の行列乗算を使用します。基本ケースの最適値は 32 であることがわかり、実行時間は 1.3 秒、ピーク パフォーマンスは 12% になりました。さらに、スピーカーは、ベクトル ハードウェアを使用したベクトル化の概念を紹介します。これは、単一の命令、複数のデータ形式でデータを処理します。講演者は、ベクトル化レポート、特定のアーキテクチャー用のフラグ、およびコンパイラーが関連付けを並べ替えることができる高速演算フラグの使用など、ベクトル化を最適化するさまざまな方法について概説します。アーキテクチャ ネイティブで高速な演算を使用すると、任意のコンパイラ ベクトライザーを使用した場合にパフォーマンスが 2 倍になります。
  
  
• 00:55:00 ビデオのこのセクションでは、スピーカーは算術計算に使用されるさまざまなビット サイズについて説明します。線形代数計算では 64 ビットが最も一般的です。彼らはまた、パフォーマンスを向上させるために AI アプリケーションに低精度演算を使用できるとも述べています。スピーカーは、ベクトル命令と AVX 組み込み関数の使用について説明します。これにより、最大 41% のピーク パフォーマンスと約 50,000 のスピードアップが実現します。彼らは、行列の乗算で達成されたのと同様のパフォーマンスの向上は他の分野では見られない可能性があると警告していますが、このコースでは学生が自分で大幅なパフォーマンスの向上を達成する方法を教えます.さらに、このコースでは、GPU やその他の分野ではなく、マルチコア コンピューティングに焦点を当てます。

[MetaQuotes]

講義 2. 仕事を最適化するための Bentley ルール

2. 仕事を最適化するための Bentley ルール

この YouTube ビデオでは、コンピューター プログラムのさまざまな最適化手法について説明しています。作業を最適化するための Bentley ルールが導入され、最適化はデータ構造、ループ、ロジック、および関数にグループ化されます。値のエンコード、データ構造の拡張、事前計算、キャッシング、スパース行列の利用など、さまざまな手法について説明します。講演者は、グラフィックス プログラムでグラフ、ロジックの最適化、衝突検出の最適化に疎行列表現を使用する利点についても触れています。これらの最適化手法を実装すると、プログラムの実行時間が短縮され、プログラムがより効率的になります。

ビデオの 2 番目の部分では、ループの巻き上げ、ループでのセンチネルの使用、ループの展開と融合、関数のインライン化など、いくつかのカテゴリの最適化手法について説明します。講演者は、時期尚早の最適化を避けるようアドバイスし、正確さを維持し、回帰テストを使用することの重要性を強調します。このビデオでは、生産性を向上させ、効率的な方法で目標を達成するための 6 ステップのガイドである、仕事を最適化するための Bentley ルールについても概説しています。これらのルールには、明確な目標の設定、タスクの分割、計画と整理、タスクの優先順位付け、気を散らすものを最小限に抑える、定期的なアプローチの見直しと調整が含まれます。

• 00:00:00 このセクションでは、講師がコンピューター プログラムの作業を最適化するという概念を紹介し、プログラムの作業を減らすことでパフォーマンスを向上させる方法について説明します。彼はまた、効率的なプログラムの作成に関する本を書いた John Lewis Bentley にちなんで名付けられた、作業を最適化するための Bentley ルールについても語っています。最適化は、データ構造、ループ、ロジック、および関数の 4 つのカテゴリにグループ化されます。講師は、コース全体の一連のミニ講義で 22 のルールすべてをカバーする予定です。プログラムの作業を減らすことは、実行時間を改善するための優れたヒューリスティックですが、コンピューター ハードウェアの複雑な性質は、常に実行時間の短縮につながるとは限らないことを意味します。コース。
  
  
• 00:05:00 ビデオのこのセクションでは、スピーカーはデータ構造をパッキングおよびエンコードして複数のデータ値をマシン ワードに格納し、データ値をより少ないビット数で表現できるように変換するという概念について説明します。メモリ内で移動するものの数を減らすことで、プログラムの実行時間を短縮するための優れたヒューリスティックになります。スピーカーは、特定の日付の月、年、または日を取得しやすくするために、より少ないビットを使用して日付をエンコードして格納する例を示しています。講演者は、C のビット フィールド機能を使用して構造化データを格納し、アクセスしやすくすることを提案しています。この表現は、わずかに多くのビットを必要としますが、構造内の特定のデータ値にアクセスする際にはるかに効率的です。
  
  
• 00:10:00 このセクションでは、ビデオで 3 つの最適化手法について説明します。最初の手法は、値を連続した整数としてエンコードするか、より高速なアクセスのためにアンパックするかを決定することです。 2 番目の手法は、データ構造の拡張です。データ構造に情報を追加することで、一般的な操作を最適化できます。例として、2 つのリストをより効率的に追加するために、1 つずつリンクされたリストにテール ポインターを追加します。 3 番目の手法は事前計算です。これは、事前に計算を実行して、ミッション クリティカルな時間に計算を実行しないようにすることです。例として、パスカルの三角形を使用して二項係数を事前に計算し、それらを使用するプログラムを高速化します。
  
  
• 00:15:00 このセクションでは、スピーカーは、再帰式と C コードを使用してパスカルの三角形を事前計算する方法について説明します。彼らは、再帰式には choose 関数の呼び出しが含まれていること、および実行時にループを使用してテーブルを事前計算する方法を説明しています。さらに、テーブルの値をソース コードに入れることで、コンパイル時にテーブルを初期化する方法についても説明します。これにより、プログラムの実行時間を節約できます。最後に、プログラムの実行中にアクセスできる最大 10 の二項係数のテーブルの例を示します。
  
  
• 00:20:00 このセクションでは、講演者は、プログラムに定数値の大きなテーブルを手動で入力することを避ける方法として、メタ プログラミングの概念を紹介します。必要なコードを生成するプログラムを作成することで、面倒な作業を自動的に行うことができます。スピーカーは、例として Python コード スニペットを提供します。最近アクセスした結果をキャッシュに保存することで、コストのかかる計算の繰り返しを回避する手法として、キャッシングのトピックも紹介されています。与えられた例は、平方根演算子を使用して直角三角形の斜辺を計算するもので、キャッシュは以前の斜辺を a と b の値とともに事前に保存します。斜辺関数は、最初に入力値がキャッシュ内の値と一致するかどうかをチェックし、一致する場合は、平方根を再計算することなくキャッシュされた値を返します。
  
  
• 00:25:00 このセクションでは、スピーカーは、プログラム内の作業を最適化するためのキャッシングの概念について説明します。よく計算される値をキャッシュに格納することにより、プログラムは同じ値を繰り返し計算する必要がなくなり、時間を節約できます。ハードウェアもキャッシングを行いますが、ソフトウェアもキャッシングを行うことができます。たとえば、最近計算された 1,000 個の値を格納するサイズ 1,000 のキャッシュを使用します。同じ値が繰り返し計算される場合、最適化によりプログラムが約 30% 高速化されます。次に、スピーカーは、入力のスパース性を利用して、その入力のゼロ要素での計算を回避し、計算時間を節約するというアイデアを紹介します。彼らはこれを行列ベクトル乗算の例で示し、行列の乗算を高速化できる圧縮スパース行 (CSR) データ構造を紹介します。
  
  
• 00:30:00 このセクションでは、講演者は Compressed Sparse Row (CSR) 形式を使用してスパース行列のストレージと計算効率を最適化する方法について説明します。 CSR 形式は、行列のゼロ以外の要素を 3 つの配列 (values 配列、columns 配列、rows 配列) に格納します。スピーカーは、行の長さを計算する方法と、CSR 形式を使用して行列とベクトルの乗算を実行する方法を説明します。非ゼロ要素の数が N^2 より大幅に少ない場合、CSR 形式は密行列表現よりもスペース効率が高くなる可能性があります。ただし、比較的密度の高い行列の場合、密度の高い行列表現の方が必要なスペースが少なくなる場合があります。スピーカーは、CSR 形式を使用して行列ベクトル乗算を実行するためのコード例を提供します。
  
  
• 00:35:00 このセクションでは、スパース マトリックスを使用してグラフを表す利点と、幅優先検索や PageRank などの従来のグラフ アルゴリズムをより効率的に実行するためにスパース マトリックスを使用する方法について説明します。スパース グラフ表現は、オフセットとエッジの 2 つの配列で構成されます。各頂点の次数は、連続するオフセット間の差を取ることによって取得できます。エッジの重みは、別の配列に格納するか、エッジとインターリーブしてキャッシュの局所性を向上させることもできます。このセクションの最後に、ロジックの最適化、特に定数の折りたたみと伝播について簡単に紹介します。これは、コンパイル中に定数式を評価してランタイムを短縮します。
  
  
• 00:40:00 ビデオのこのセクションでは、スピーカーは、定数の折り畳みと伝播、一般的な部分式の削除、代数的恒等式の活用など、コードのさまざまな最適化手法について説明します。コンパイル時に定数を定義することにより、コンパイラは定数を評価して実行時の時間を節約できます。共通部分式の削除により、将来の使用のために結果を保存することで、同じ式を複数回計算することを回避できます。代数恒等式を利用するには、より高価な式を安価な代替物に置き換える必要があります。講演者は、通常、コンパイラーはこれらの最適化を適切に実装していますが、コンパイラーが自動的に最適化を実行しない場合でも、それらを知ることが重要であることを強調しています。
  
  
• 00:45:00 ビデオのこのセクションでは、スピーカーが 2 つの最適化手法について説明します。 1 つ目は、代数恒等式を使用して平方根を回避することにより、計算コストの高い平方根演算子の使用を減らすことです。 2 番目の最適化手法はショートサーキットです。これは、配列に負でない整数が含まれていて、配列内の値の合計を特定の値に対してチェックする必要がある場合に、結果が判明したらすぐに一連のテストを停止することを含みます。限界。最適化により、配列内のすべての要素を調べる必要がなくなり、プログラムの実行が高速化されますが、テストが短絡する可能性がある頻度に基づいて慎重に使用する必要があります。
  
  
• 00:50:00 このセクションのビデオでは、論理演算子のショートサーキットの概念と、コードの最適化におけるそれらの有用性について説明しています。 2 つのアンパサンドと 2 つの垂直バーは短絡論理演算子であり、引数の片側のみを評価することで時間とリソースを節約できます。さらに、このビデオでは、成功の頻度と実行コストに基づいてテストを注文することを提案しています。このアプローチでは、短絡を利用して、安価なテストがすでに失敗している場合に高価なテストをスキップできます。最後に、ビデオでは、結果が既にわかっている場合にチェックを使用してプログラムを早期に終了することにより、高速パスを作成するというアイデアを紹介しています。この例として、他の衝突条件をチェックする前に、2 つのボールのバウンディング ボックスが交差するかどうかをチェックします。
  
  
• 00:55:00 このセクションでは、Bentley がグラフィックス プログラムでの衝突検出のテストを最適化する方法について説明します。彼は、よりコストのかかる衝突テストを実行する前に、バウンディング ボックスが交差するかどうかを判断する高速パス テストを提案しています。このテストでは、各座標の差の絶対値をチェックし、それが 2 つの半径の合計より大きいかどうかをチェックします。 Bentley はまた、単一の switch ステートメントまたはテーブル ルックアップを使用してテストを組み合わせると、パフォーマンスが大幅に向上する可能性があることにも言及しています。全体として、これらの最適化は、多くのアプリケーションやグラフィックス プログラムにとって有益です。
  
  
• 01:00:00 このセクションのビデオでは、ループに関連する 3 番目のカテゴリの最適化について説明します。最初に取り上げるループの最適化は巻き上げです。これには、ループの本体を通るたびにループの不変コードを再計算することを回避することが含まれます。繰り返しごとに式を再計算するのではなく、式を一度計算して変数に格納することで、実行時間を節約できます。 2 番目のループの最適化は、境界条件の処理とループ終了テストの処理ロジックを簡素化するためにデータ構造に配置された特別なダミー値であるセンチネルの使用です。配列に 2 つの追加エントリを使用するようにプログラムを変更することにより、センチネルを使用して、ループの反復ごとに 1 つのチェックのみを実行する必要があります。
  
  
• 01:05:00 このセクションでは、スピーカーはコードを最適化するための 2 つの手法、境界条件とループ展開について説明します。境界条件については、ループを変更して、入力配列のすべての要素がゼロの特殊なケースを効率的に処理する方法を示しています。配列の末尾にダミー要素を追加し、オーバーフローをチェックすることで、コードはいつ停止すべきかを検出できます。ループの展開について、フルとパーシャルの 2 種類について説明しています。ループ サイズが大きいため、完全なループ展開はまれですが、部分的なループ展開では、複数のループを 1 つに結合することでループの反復回数を減らします。これにより、実行される制御フロー命令の数が減り、パフォーマンスが向上します。
  
  
• 01:10:00 このセクションでは、インストラクターがループ展開とループ融合の最適化について説明します。ループの展開では、ループの複数の反復を 1 つの反復に結合する必要があります。これにより、ループ制御のオーバーヘッドが削減され、コンパイラの最適化がさらに可能になります。ただし、展開しすぎると、命令キャッシュが汚染されてパフォーマンスに悪影響を及ぼす可能性があります。一方、ループ融合は、同じインデックス範囲の複数のループを 1 つのループに結合し、ループ制御のオーバーヘッドを減らし、キャッシュの局所性を改善します。インストラクターはまた、ループ境界を変更して、空のループ本体でループ反復を実行しないようにすることで、無駄な反復を排除することについても説明します。
  
  
• 01:15:00 このセクションでは、Bentley が関数の最適化、特に関数呼び出しのオーバーヘッドを回避するためのインライン化の概念について説明します。関数を静的インラインとして宣言することにより、コンパイラは関数への呼び出しを関数自体の本体に置き換えようとします。これにより、別の関数呼び出しが不要になります。マクロでもこれを行うことができますが、インライン関数はより構造化されており、すべての引数を評価するため、マクロが高価な式をコードに何度も貼り付けるリスクを回避できます。 Bentley は時期尚早の最適化に注意し、開発者がまずプログラムが正しいことを確認し、回帰テストを使用して正確性を維持することを奨励しています。最後に、彼は、多くのレベルの最適化がコンパイラによって自動化される可能性があり、アセンブリ コードをチェックすることで、そのような最適化を明らかにできることを指摘しています。
  
  
• 01:20:00 このセクションでは、作業を最適化するための Bentley ルールを一連の 6 つのステップで概説します。これらのルールは、明確な目標を設定すること、タスクを小さな部分に分割すること、時間をかけて計画と整理を行うこと、タスクの優先順位を決めること、気を散らすものを最小限に抑えること、アプローチを定期的に見直して調整することで構成されます。これらのガイドラインに従うことで、生産性を向上させ、より効率的な方法で目標を達成できます。さらに、これらの戦略を日常生活に取り入れることで、強い労働倫理を維持し、目標に集中し続けることができます。

[MetaQuotes]

講義3.ビットハック

3.ビットハック

この YouTube ビデオでは、バイナリ表現、2 の補数、ビットごとの演算子、一時変数を使用しない変数の交換、コードの最適化など、さまざまなビット操作のトピックを取り上げています。このビデオでは、if-else ステートメントを使用せずに 2 つの整数の最小値を見つける方法や、一時変数を使用せずに 2 つの整数を交換する方法など、さまざまなちょっとしたトリックを紹介しています。講演者は、予測不可能な分岐について説明し、予測可能な分岐が利用できない場合に備えて分岐なしの最小ビット トリックを紹介し、除算などのコストのかかる演算を単純なビット単位の演算に置き換えることで、ビット ハックがコードを最適化する方法を示します。このビデオでは、de Bruijn 列と、N クイーン問題などの問題を解く際のその応用についても説明しています。

第 2 部では、ビット ベクトルを使用して N クイーン問題を解き、バイナリ ワード内の 1 ビットの数を効率的にカウントする方法について説明します。バックトラッキングを使用して N クイーン問題を実装し、ビット ベクトルを使用してボードを効率的に表現します。 N クィーン問題でクィーンを安全に配置するための 3 つのチェックについて説明し、最下位の 1 ビットを再帰的に削除して、単語内の 1 ビットの数をカウントする方法を示します。さらに、1 のビット数をカウントするためのテーブル ルックアップとレジスタ操作の使用についても説明します。ビデオは、語長の底 2 の対数に比例する性能を持つ 1 ビットをカウントするための分割統治アプローチのデモンストレーションで終了します。さらに学習するためのリソースも提供されています。

• 00:00:00 このセクションでは、単語のバイナリ表現と、単語から整数値を計算する方法について学びます。また、符号付き整数の 2 の補数表現と、すべてゼロとすべて 1 の単語の特殊なケースについても学びます。さらに、X の 1 の補数の重要な同一性と、2 の補数表現における X の負数との関係が見られます。
  
  
• 00:05:00 このセクションでは、発表者が 1 の補数と、1 の補数に 1 を加えて負の数を得る方法について説明します。彼はまた、大きな 2 進数定数を表すための 16 進数の使用についても説明し、16 進数と 2 進数を変換するための表を提供します。次にビデオでは、C++ のビット演算子について説明し、論理 and、論理 or、排他的 or、および左シフトと右シフトの演算にそれらを使用する方法の例を示します。
  
  
• 00:10:00 このセクションのビデオでは、C でビット単位の演算子を使用して実装できるさまざまな一般的なイディオムについて説明します。1 つの例として、シフトの後に OR または NOT とそして、それぞれ。もう 1 つの例は、ワード X からビット フィールドを抽出することです。これは、目的のビットの位置に 1 を、その他の場所に 0 を使用してマスクを生成し、マスクと X の AND を取り、抽出されたビットを右シフトします。このビデオでは、これらのトリックを使用すると、圧縮またはエンコードされたデータを操作するときに特に役立つことにも言及しています。
  
  
• 00:15:00 このセクションでは、いくつかのビット トリックを使用して、一時変数を使用せずに 2 つの整数を交換する方法について説明します。このコードでは、X を X XOR Y に設定し、次に Y を X XOR Y に設定し、最後に X を X XOR Y に設定します。これは、XOR が独自の逆数であり、最初の行で X のビットが 1 のマスクを生成するためです。と Y が異なります。これは、X とは異なる Y のビットを反転するために使用されます。これにより、一時変数を使用せずにスワップが可能になります。このビデオでは、これらのトリックを使用する際の安全を確保するためのマスキングの重要性も強調しています。
  
  
• 00:20:00 このセクションでは、スピーカーは 2 つのビット ハックについて説明します。最初のハックは、一時変数を使用せずに 2 つの変数を交換する方法です。ハックには、XOR とマスクを使用して、2 つの変数間で異なるビットを反転させることが含まれます。このハックはクールですが、命令レベルの並列性が低いため、変数をスワップする最も効率的な方法ではありません。 2 番目のハックは、if-else ステートメントを使用せずに 2 つの整数の最小値を見つける方法です。これは、分岐の予測ミスによるパフォーマンスの問題を引き起こす可能性があります。代わりに、スピーカーは、ビット演算を使用して整数を比較し、分岐せずに最小値を計算する方法を示します。
  
  
• 00:25:00 このセクションでは、スピーカーは、コードの最適化と、2 つの並べ替えられた配列をマージするサブルーチンでの「restrict」キーワードの使用について説明します。このプロセスは、2 つの緑色のアレイが青色のアレイにマージされる例を通して説明されます。コード内の各分岐の予測可能性についても説明します。最初の分岐は予測可能ですが、2 番目の分岐は予測不可能です。
  
  
• 00:30:00 このセクションのビデオでは、プログラミングにおける予測可能および予測不可能な分岐について説明し、予測不可能な分岐の問題に対する解決策として、分岐なしの最小ビット トリックを紹介します。トリックは、「comp」という変数を使用して、a と b の最初の要素の比較結果を格納し、ビット トリックを使用して a と b の最小値を取得することです。次に、最小値を C に置き、「comp」の値に基づいて A または B の値を増減します。このビデオでは、場合によってはこのトリックが機能しない可能性がありますが、コンパイラが何を行っているかを理解することは有益であり、単語のビットハックの多くはベクトルのビットハックとワードハックに拡張できるため、これらのトリックについて知っておくと役立ちます。
  
  
• 00:35:00 このセクションでは、ビデオでビット ハックとプログラミングにおけるその有用性について説明します。与えられた例は、除算を使用せずにより迅速な操作を可能にする剰余加算のちょっとしたトリックです。 Z を X と Y の合計に設定し、それが N より小さいか大きいかをチェックすることにより、プログラムは範囲内にある場合は Z を返すか、Z から N を差し引いた結果を範囲内に戻すことができます。このプログラムは、minimum と同様のロジックを使用しており、分岐の予測ミスを引き起こす可能性のある予測不可能な分岐があります。与えられた別の例は、ビット操作を使用して値を最も近い 2 の累乗に丸める方法です。N をデクリメントし、N を異なる値だけ右にシフトしてビット単位の OR 演算を実行し、最後にインクリメントします。
  
  
• 00:40:00 ビデオのこのセクションでは、スピーカーが 2 つのビット操作の問題について説明します。最初の問題は、与えられた値 n より大きい最小の 2 のべき乗を見つけることです。講演者は、ビット操作を使用してこれを達成する方法を説明し、n が既に 2 のべき乗になっている場合は n をデクリメントして、n の対数から 1 ビットを引いた値が確実に設定されるようにします。 2 番目の問題は、単語 X の最下位のマスクを計算することです。話者は、結果を X に設定し、負の X でビットごとの演算を使用して、これを達成する方法を説明します。話者は、インデックスを見つけるコードも示します。 X を定数で乗算し、結果をテーブルで検索することにより、ビットの値を計算します。セクションは、話者がビット操作を含む数学の手品を実行することで終了します。
  
  
• 00:45:00 このセクションでは、グループがカードとベルを使って手品を行っている YouTube ビデオをご覧ください。パフォーマーは聴衆の心を読むと主張し、カードを配る前にデックをカットするように依頼します。出演者は、各人のカードのスートと数字を予想し、一見成功したように見えます。彼らは、「素晴らしい着ぐるみ」と魔法の帽子を身に着けていること、そしてベルで空気をきれいにすることが自分たちの能力だと考えています。
  
  
• 00:50:00 このセクションでは、de Bruyne シーケンスと、2 のべき乗の 2 を底とする対数の計算との相関関係について学習します。de Bruyne シーケンスは、長さ K のすべての可能なビット文字列が正確に発生する巡回ビット シーケンスです。シーケンス内の部分文字列として 1 回。変換テーブルを使用すると、de Bruyne シーケンス定数に 2 の累乗を掛けて、シーケンスの先頭に現れる部分文字列を抽出し、2 のべき乗の底 2 の対数を計算できます。シーケンスを左にシフトしてから、変換テーブルの部分文字列の開始位置を上に移動すると、開始時の整数の基数 2 の対数を決定できます。これにより、前に示したカード トリックが解決されます。
  
  
• 00:55:00 このセクションでは、スピーカーは de Bruijn シーケンスについて説明します。これは、考えられる各 n ビット文字列を 1 回だけ含むバイナリ アルファベットの循環シーケンスです。シーケンスは、N クイーン問題などの問題を解決するために使用でき、手品を使用して生成できます。講演者は、左シフト後の de Bruijn シーケンスの部分文字列の位置を決定するためにビット トリックがどのように機能するかについても説明します。このビット トリックのパフォーマンスは、乗算とテーブル ルックアップのパフォーマンスによって制限されますが、それを計算するためのハードウェア命令が用意されています。
  
  
• 01:00:00 このセクションでは、スピーカーは N クイーンの問題について説明します。これは、2 つのクイーンが互いに脅威にならないように NxN のチェス盤に N 個のチェス クイーンを配置することを含みます。この問題は、多くの場合、クイーンが行ごとに配置され、有効な位置が見つからない場合にプログラムがバックトラックするバックトラックを使用して実装されます。ボードのさまざまな表現についても説明しますが、最もコンパクトなものは 3 つのビット ベクトルのセットです。ダウン ベクトルは各列のクイーンの存在を格納し、左の対角ベクトルは各左の対角のクイーンの存在を格納し、右の対角ベクトルは各右の対角のクイーンの存在を格納します。ビット ベクトルを使用すると、アルゴリズムをより効率的に実装できます。
  
  
• 01:05:00 このセクションでは、ビット ベクトルを使用して、n クイーン問題でクイーンを安全に配置できるかどうかを確認するプロセスについて説明します。 3 つのチェックでは、位置と同じ行、同じ列、同じ対角線に既にクイーンがあるかどうかをチェックします。この方法は効率的で、3 つのチェックすべてに合格した場合にクイーンを安全に配置できることが保証されます。議論されるもう 1 つの問題は、単語 X の 1 ビットの数をカウントすることを含む人口カウントです。提示された方法は、ゼロになるまで X の最下位 1 ビットを繰り返し削除します。必要な反復回数は、 X の 1 ビット。
  
  
• 01:10:00 このセクションでは、スピーカーはテーブル ルックアップを使用してバイナリ ワード内の 1 ビットの数を効率的にカウントする方法について説明します。テーブル ルックアップ方法では、各 8 ビット ワードに 1 の数を格納するサイズ 256 のテーブルを作成し、バイナリ ワード内の各 8 ビット サブストリングのカウントをルックアップします。講演者は、このメソッドのパフォーマンスは、テーブルへのアクセスに必要なメモリ操作によってボトルネックになっていることに注意しています。講演者は、レジスタを使用して 1 のビット数をカウントする 3 つ目の方法を紹介します。この方法では、マスクを作成し、特定の命令を実行して、メモリにアクセスせずにバイナリ ワード内の 1 の数をカウントできるようにします。プレゼンターは、この方法がどのように機能するかを例を挙げて説明します。
  
  
• 01:15:00 このセクションでは、話者は並列分割統治法を使用して入力単語の 1 の数をカウントする方法を示します。パフォーマンスは、単語の長さ W の基数 2 の対数に比例します。ほとんどの最新のマシンには、コンパイラ組み込み関数を介してアクセスできる、コード化できるものよりも高速な組み込み pop カウント命令があることを指摘しました。ただし、これにより、異なるマシン間でのコードの移植性が低下する可能性があります。講演者は、ウェブサイト、教科書、チェス プログラミングのウェブサイト、Hacker's Delight という書籍など、ビット トリックについてさらに学習するためのリソースをいくつか提供しています。

[MetaQuotes]

講義 4. アセンブリ言語とコンピュータ アーキテクチャ

講義 4. アセンブリ言語とコンピュータ アーキテクチャ

このビデオでは、アセンブリ言語とコンピューター アーキテクチャの包括的な概要を説明します。アセンブリ言語は、コードのパフォーマンスを最適化するための重要なインターフェイスであり、アセンブリ言語を習得するにはコンピューター アーキテクチャを理解することが不可欠です。講演者は、x86 64 アーキテクチャとその開発の歴史、主要なレジスタ、データ型、メモリ アドレッシング モード、命令セット アーキテクチャ (スタック、整数論理とバイナリ論理、ブール論理、サブルーチンを含む) について説明します。また、ゼロ拡張や符号拡張などの拡張機能や、アセンブリ言語のさまざまなアドレッシング モードについても説明しています。さらに、このビデオでは、浮動小数点型、ベクトル、ベクトル ユニット、従来の命令と SSE 命令、およびスーパースカラー処理、アウト オブ オーダー実行、分岐予測などのコンピューター アーキテクチャ設計機能について説明します。

このビデオでは、アセンブリ言語とコンピューター アーキテクチャに関連するいくつかのトピックも取り上げています。中心的なテーマの 1 つは、命令レベルの並列処理 (ILP) とパイプラインのストールです。これらは、データの依存関係などの危険によって引き起こされます。講演者は、真、逆、および出力データの依存関係と、スーパースカラー プロセッサがハードウェアでより多くの並列処理を利用して一度に複数の命令を実行する方法について説明します。ただし、危険を回避するために、アーキテクトは、分岐の結果を推測して事前に実行する投機的実行だけでなく、名前の変更や並べ替えなどの戦略を実装しています。スピーカーは、ソフトウェアの最適化をよりよく理解するために、聴衆にこれらの方法を理解するよう促します。

• 00:00:00 このセクションでは、最近のソフトウェア コースでは取り上げられていないことが多いアセンブリ言語とコンピューター アーキテクチャについてインストラクターが説明します。これらの概念を理解することは、コードのパフォーマンスを最適化するために必要であり、アセンブリ言語はそのための最適なインターフェイスです。コードをコンパイルするプロセスには、前処理、コンパイル、アセンブル、リンクなど、いくつかの段階が含まれます。アセンブリ言語は、人間が読みやすいようにする機械コードのニーモニック構造であり、最終的な実行可能ファイルは、LD コマンドを使用したリンク段階を通じて生成されます。
  
  
• 00:05:00 このセクションでは、スピーカーは、アセンブリとマシン コードの構造が非常に似ており、アセンブリの OP コードがマシン コードの特定のビット パターンに対応していることを説明します。スピーカーは、プログラム ABS を紹介します。このプログラムは、マシン コードの逆アセンブリを生成し、ニーモニックで人間が読めるアセンブリ コードを明らかにします。次に講演者は、コンパイラが実行したことと実行しなかったことを明らかにすること、コンパイラ エラーをデバッグすること、ソースにアクセスせずにプログラムをリバース エンジニアリングすることなど、誰かがアセンブリ コードを見たいと思ういくつかの理由について説明します。
  
  
• 00:10:00 このセクションでは、講演者は、コンパイラが x86 命令を使用して言語構造を実装する方法を理解すること、x86 アセンブリ言語を読み取ることができること、一般的なアセンブリ パターンのパフォーマンスへの影響を理解することなど、クラスに求められることを説明します。また、学生は必要に応じてゼロからコードを記述し、それが可能なレベルまで習熟できる必要があります。次にスピーカーは、x86 64 命令セット アーキテクチャ (レジスタ、命令、データ型、メモリ アドレッシング モードなど) について詳しく説明します。キー レジスタには、汎用レジスタと、算術演算とキャリーを追跡するフラグ レジスタが含まれます。命令ポインタは、アセンブリ言語プログラムの一連の命令を通じてハードウェアをガイドします。
  
  
• 00:15:00 このセクションでは、講演者は x86 64 アーキテクチャの歴史と、メモリが限られている 16 ビット ワード マシンから、より多くのメモリが利用できるようになったときのインデックス作成用のより広いワードへの発展について説明します。また、スピーカーは、ベクトル化のための xmm レジスターや AVX レジスターなどのベクトル レジスターの追加と、それらの使用方法についても説明します。また、汎用レジスターのトピックと、その機能目的が時間の経過とともにどのように大幅に変化したかについても触れていますが、歴史的な理由によりそれらの名前は固定されています。さらに、短い単語、32 ビット、または 64 ビットの単語の下半分と上半分について、特定のレジスタがどのように同じものにエイリアスされるかについて説明します。
  
  
• 00:20:00 このセクションでは、スピーカーが x86 64 アセンブリ言語の基本とその仕組みについて説明します。レジスタは、レジスタのどの部分にアクセスするかによって名前が異なり、スタック ポインタとして使用される RSP などの特定の目的を持つレジスタもあります。 x86 64 命令コードの形式は、オペコードとオペランド リストを持ち、通常はソースまたは宛先となる 0 ～ 3 個のオペランドを持ちます。講演者は、操作を参照するための AT&T 構文と Intel 構文の違いを説明し、「移動」や「条件付き移動」などの一般的な操作コードのリストを提供します。さらに、講演者は、32 ビット値レジスタから 64 ビット レジスタに移動するときに符号を拡張することの重要性を説明します。
  
  
• 00:25:00 このセクションでは、スピーカーは、スタック、整数演算、バイナリ論理、ブール論理、ジャンプ、およびサブルーチンの命令を含む、アセンブリ言語のさまざまなタイプの命令について説明します。オペコードは、操作のデータ型または条件コードを記述する接尾辞で拡張できます。たとえば、「キュー」を伴う移動は、移動されるデータが 8 バイトまたは 64 ビットで構成されるクワッド ワードであることを示します。 x86 64 データ型とそのアセンブリ サフィックスについても説明し、符号拡張がどのように機能するかを示す例を示します。アセンブリ言語に特定のオペコードとニーモニックが存在するかどうかは混乱を招く可能性がありますが、コンパイラはプログラムを正しく実行するためにこれらの命令を理解する必要があります。
  
  
• 00:30:00 このセクションでは、スピーカーは、32 ビット操作を 64 ビット操作に移行するときに発生するゼロ拡張や符号拡張などの拡張について説明します。彼らはまた、インテルの命令セットが新しい命令の追加によってどのように複雑になる可能性があるかについても言及しています。スピーカーは、条件付きジャンプと条件付き移動で使用されるさまざまな条件コードと、ゼロ フラグやオーバーフロー フラグなど、それらで使用されるフラグについて説明します。特定の条件コードがゼロ フラグをチェックする理由についても説明します。
  
  
• 00:35:00 このセクションでは、スピーカーはアセンブリ言語でのさまざまな直接および間接アドレッシング モードについて説明します。ダイレクト アドレッシング モードには、イミディエート、ダイレクト メモリ、およびレジスタの使用が含まれます。レジスター間接およびレジスター・インデックス・アドレッシング・モードでは、レジスターにアドレスを提供するかアドレスをオフセットすることにより、メモリーにアクセスできます。講演者は、メモリへのアクセスは遅くてコストがかかる可能性があるため、プロセスを高速化するために可能な限りレジスタに値を格納することが重要であると述べています。また、メモリ アクセスの最適化におけるキャッシングの重要性についても言及しています。
  
  
• 00:40:00 このセクションのビデオでは、ポインター相対インデックスの使用について説明しています。この場合、命令ポインターは、汎用レジスターではなく、データのインデックス付けに使用されます。ベース インデックス スケール ディスプレースメント アドレッシング メソッドも導入されています。これは、ベース ポインターからの穏やかなインデックス作成をサポートする複雑な命令です。このビデオでは、レジスタをゼロにするために使用される XOR オペコードや、2 つの値のビット単位の AND を計算し、レジスタ フラグを保持するテスト オペコードなど、いくつかのアセンブリ言語イディオムの概要を説明します。最後に、ビデオは、コード内の制御フローを可能にするジャンプ命令とラベルに触れています。
  
  
• 00:45:00 このセクションでは、さまざまな命令セットや浮動小数点の歴史など、アセンブリ言語とコンピューター アーキテクチャについて説明します。 x87 および SSE を含む x86 命令セットは、単精度および倍精度のスカラー浮動小数点演算、およびベクトル命令をサポートします。 SSE 命令は、コンパイルと最適化が簡単なため、一般に x87 よりもコンパイラに好まれます。アラインメントの最適化など、アセンブリでノーオペレーション (nop) 命令を使用する目的についても説明します。
  
  
• 00:50:00 このセクションでは、スピーカーは、コンピューター アーキテクチャで使用される浮動小数点型、ベクトル、およびベクトル ユニットについて説明します。講演者は、ベクトル ユニットの仕組みは、プロセッサがすべてのベクトル ユニットに命令を発行することであり、それぞれがレーンと呼ばれていることを説明しています。レーンには整数演算または浮動小数点演算が含まれており、すべてロックステップで動作します。つまり、すべて同じことを行います。一度に複数の操作を実行でき、これらすべてを 1 つの命令で実行できます。講演者は、一部のアーキテクチャではベクトル オペランドを揃える必要がある一方で、他のアーキテクチャではメモリ内のベクトルをシフトできるため、2 つのパフォーマンスに違いが生じると説明しています。さらに、並べ替え、シャッフル、スキャッター ギャザーなど、クロスレーン操作をサポートするアーキテクチャもあります。
  
  
• 00:55:00 このセクションでは、スピーカーは従来の命令と SSE 命令の違いと、それらの使用方法について説明します。また、ymm が xmm レジスタのエイリアスを登録し、avx-512 で 512 ビットに拡張するエイリアシングのトリックについても言及しています。次に、コンピュータ アーキテクチャ、特に 5 ステージのパイプラインと 14 ～ 19 のパイプライン ステージを備えた最新のプロセッサの違いについての議論に移ります。彼らが議論する設計機能には、ベクトルまたはハードウェア I、スーパースカラー処理、順不同実行、および分岐予測が含まれますが、時間の制約により、順不同実行については深く掘り下げないと述べています。
  
  
• 01:00:00 ビデオのこのセクションでは、インストラクターが命令レベルの並列処理 (ILP) とパイプラインのストールについて説明します。 ILP では、スループットを向上させるために、複数の命令を同時に実行する機会を見つける必要があります。ただし、パイプライン ストールは、構造ハザード、データ ハザード、または制御ハザードなどのハザードが原因で命令を実行できない場合に発生する可能性があり、データ ハザードが最も一般的です。真の依存は、命令が書き込み依存の後に読み取る場合に発生しますが、逆依存は、命令が場所に書き込みたいが、前の命令が値を読み取るまで待機する必要がある場合に発生します。コンパイラは、コードを最適化してハザードを回避することにより、パイプラインのストールを削減しようとします。
  
  
• 01:05:00 このセクションでは、アセンブリ言語におけるデータの依存関係の概念について説明します。データの依存関係には、true、anti、および output の 3 つのタイプがあります。算術演算、特に浮動小数点演算などの複雑な演算では、待ち時間が長くなり、プロセッサ内に別個の機能ユニットが必要になり、場合によっては別個のレジスタが必要になります。命令レベルの並列性を高めるために、アーキテクトはサイクルごとに複数の命令を発行してハードウェアでより多くの並列性を活用するなどの手法を実装しました。
  
  
• 01:10:00 このセクションでは、スーパースカラー プロセッサが一度に複数の命令を実行する方法をビデオで説明します。Haswell の例を使用して、命令をマイクロ演算と呼ばれるより単純な操作に分割し、サイクルごとに最大 4 つのマイクロ演算を発行します。次にビデオでは、プロセッサが命令を順番に実行することを回避するための戦略について詳しく説明します。これには、バイパスやレジスタの名前変更が含まれます。これにより、依存しない命令を順不同で実行できるようになり、結果として処理時間が短縮されます。これらの戦略では、依存関係を追跡し、データの依存関係などの危険を回避する方法でコードを実行する必要があります。
  
  
• 01:15:00 このセクションでは、スピーカーは名前の変更と並べ替えについて説明します。これらは、最新のプロセッサでデータの危険を回避するために使用される 2 つの重要な方法です。スピーカーはまた、分岐予測で使用され、分岐の結果を推測して事前に実行し、ストールを回避する投機的実行についても話します。ただし、推測が間違っていると、計算を元に戻すのに約 15 ～ 20 サイクルかかります。スピーカーは、分岐予測子がどのように機能するかについて簡単に説明しますが、それは複雑であり、さらなる研究が必要であることを指摘します。急ぎの終了にもかかわらず、講演者は聴衆にさまざまな方法を理解するよう促し、特定のソフトウェアの最適化が機能する理由と機能しない理由を理解するのに役立ちます。

[MetaQuotes]

講義 5. C からアセンブリへ

講義 5. C からアセンブリへ

ビデオのこの部分では、アセンブリ言語に対する C の理解の重要性と、コンパイラを使用してアセンブリ言語で C コードを実装する方法について説明します。特に、LLVM IR が Linux x86 64 呼び出し規約でアセンブリに変換される方法に焦点を当てています。プレゼンターは、LLVM IR の基本コンポーネントと、C プログラミング言語の構造が LLVM IR に変換される方法について説明します。このビデオでは、仮想メモリのレイアウト、複数の関数間での関数呼び出しの調整の問題、Linux x86 64 呼び出し規約での 2 つのポインター (BP と SP) の使用によるすべてのスタック フレームの管理についても取り上げています。

このビデオでは、C to Assembly プログラミングでレジスタの状態を維持するための戦略 (caller-save または callee-save としてレジスタを保存するなど) や、x86 呼び出し規約が無駄な作業を回避する方法についても説明しています。 C およびアセンブリで関数呼び出しがどのように機能するかについて説明し、引数とローカル変数をスタックに保存するプロセス、およびベース ポインターの代わりにスタック ポインターを使用する一般的な最適化について説明します。このビデオでは、LV miR をアセンブリ コードにコンパイルするプロセス、関数のプロローグについて説明するプロセス、レジスタを保存するプロセス、条件を処理するプロセス、および制御フロー グラフを使用して C コードをアセンブリ コードに変換するプロセスも示しています。最後に、結果を返す前にレジスタを復元するために使用される関数エピローグについて説明します。

• 00:00:00 ビデオのこのセクションでは、TB Shuttle が C をアセンブリ言語に理解することの重要性について説明しています。彼は、アセンブリ言語は C コードよりも精度が高く、C コードからは明らかでないプログラムの詳細を明らかにできることに注目しています。開発者は、アセンブリを確認することで、プログラムの最適化時にコンパイラが何を実行し、何を実行しなかったかを判断できます。さらに、特定のレベルでコードを最適化するときにのみ予期しない動作を引き起こすバグが発生する可能性があり、これらのバグを見つけるのが難しくなります。最後に、アセンブリを理解すると、開発者はアセンブリ コードを手動で変更したり、コードをリバース エンジニアリングしたりできるようになります。
  
  
• 00:05:00 このセクションでは、どのアセンブリ命令を使用するかについて複雑な決定を行う必要があるコンパイラを使用して、アセンブリ言語で C コードを実装する方法、C 条件文とループを実装する方法、および C コードを実装する方法について説明します。関数呼び出しを調整します。変換プロセスを理解するために、ビデオでは LVM IR を紹介しています。これは、コンパイラーがプログラムについて推論するために使用する単純化されたアセンブリーです。ビデオでは、関数、条件、ループなどの C プログラミング言語の構成要素が LVM IR に変換される方法について説明します。このセクションは、LVM IR 属性の簡単な説明で終わります。
  
  
• 00:10:00 このセクションでは、特に Linux x86 64 呼び出し規約で、LLVM ir がアセンブリに変換されるプロセスに焦点を当てています。発表者は、LLVM ir の簡単な入門書を提供し、機能、命令、およびレジスターの基本コンポーネントを説明します。これらは、より単純なバージョンのアセンブリーに似ています。 LLVM ir レジスタは c 変数に似ており、名前で区別され、各関数には独自のローカル レジスタ名があります。プレゼンターは、コード スニペットの例でレジスターを強調し、LLVM のさまざまな基本ブロックを参照するときにレジスターの構文がハイジャックされていることを指摘します。この講演は、フィボナッチ数を計算する単純なコードでこのプロセスがどのように機能するかについてのケース スタディで締めくくられます。
  
  
• 00:15:00 このセクションでは、スピーカーは LV Mir 命令の構文を説明します。これには、レジスタ名、等号、オペコード、およびオペランド リストが含まれます。一部の命令は、ローカル レジスタに格納される値を返しますが、そうでない命令もあります。 LV Mir の命令セットは、x86 の命令セットよりも小さく、データ移動、算術演算、論理演算、および制御フロー用の命令しか含まれていません。 LV Mir では、整数 (ビット数が定義されている)、浮動小数点型、ポインター型、ベクトル型、基本ブロックのラベル型など、すべてが型として公開されます。講演者はまた、LV Mir のベクトル演算は SSE や AVX のようには見えず、ベクトル型で機能する通常の演算に似ているとも述べています。
  
  
• 00:20:00 このセクションのビデオでは、C コードの一連の操作が LLVM IR に変換される方法と、IR でコードを解釈するための経験則について説明します。この抜粋では、LLVM IR が配列や構造体などのプリミティブ型と集約型を処理する方法についても説明し、配列内の要素へのアクセスにメモリ内のアドレスの計算がどのように含まれるかの例を示します。さらに、このビデオでは、C 関数が LLVM IR に変換される方法と、対応する return ステートメントを両方の言語で説明しています。
  
  
• 00:25:00 このセクションでは、C の関数とパラメーターがどのように LV Mir に変換されるかをビデオで説明します。 LV Mir の関数は C の関数に似ていますが、C パラメーターは LV Mir のパラメーターのリストになります。ただし、LV Mir の読み取りは、レジスターの名前が適切でなく、解読が困難であるため、困難な場合があります。このビデオでは、LV Mir の基本ブロックについても説明しています。これは、制御フロー命令に基づいて分割されたコードのチャンクです。基本ブロック間の接続は、分岐命令によって誘導されるエッジに基づいています。最後に、ビデオは LV Mir の条件に触れます。この場合、if-then-else ステートメントは、基本ブロックを誘導し、フロー エッジを制御する条件付き分岐命令になります。
  
  
• 00:30:00 このセクションでは、条件付き操作と分岐が LLVM IR でどのように機能するかをビデオで説明します。このプロセスは、リテラル値とレジスタに格納された値との比較から始まり、1 ビットの整数またはブール値の結果が作成されます。この結果は、述語が true または false の場合に移動先を示す基本ブロックの 2 つのラベルと共に、条件付き分岐アクションに渡されます。オペランドが 1 つの無条件分岐がある場合、結果は特定の基本ブロックへの直接ジャンプになります。このビデオでは、条件ステートメントがある場合に制御フロー グラフでひし形を作成する方法も示し、C コードで記述されたループの例を示します。
  
  
• 00:35:00 このセクションのビデオでは、ループ本体とループ コントロールを含む C ループのコンポーネントについて説明します。ループ本体は反復ごとに実行され、ループ コントロールはループのすべての反復を管理します。 AC ループは、制御フロー グラフにループ パターンを生成し、LLVM ir にループ構造を作成します。次に、ビデオは、ループ制御の LLVM ir コードを分析します。ここには、ループを処理するときに一般的に発生する奇妙な fie 命令があります。 fie 命令は、コードの LLVM 表現に関する問題を解決しようとします。ここで、私はさまざまなレジスタ全体で表され、実際にどこに行ったのかが不明確になります。
  
  
• 00:40:00 このセクションでは、ループ内の誘導変数の LLVM 内のさまざまな場所へのマッピングについて説明します。これは、ループの繰り返しで変数の値が変化するために行われます。これは、各命令がレジスタの値を 1 回だけ定義する LLVM の「静的単一代入」不変条件につながり、誘導変数に問題を引き起こします。 「phi」命令は、制御フローがループのエントリ ポイントでどのようにマージされるかに依存するレジスタ値を定義することで、この問題を解決します。このビデオでは、LLVM の属性と、「add」命令に付加された NSW 属性など、LLVM 構造に追加情報を提供する方法についても説明しています。
  
  
• 00:45:00 ビデオのこのセクションでは、LLVM IR に焦点を当てています。LLVM IR はアセンブリに似ていますが、すべての計算値が通常の C 変数のようなレジスタに格納されるため、多くの点でより単純です。 LLVM IR は、各変数が最大 1 つの命令によって書き込まれる静的単一代入パラダイムを使用します。このビデオでは、C コードを LLVM IR に変換してからアセンブリに変換する方法について説明していますが、その過程でいくつかの追加の複雑さが伴います。コンパイラは、LLVM IR 操作に必要な実際のアセンブリ命令を選択し、使用する汎用レジスタを決定し、異なるソース ファイルとバイナリ ライブラリ間の関数呼び出しを調整します。次に、Linux x86 64 の呼び出し規約について説明します。
  
  
• 00:50:00 このセクションでは、プログラムの仮想メモリのレイアウトについて説明します。仮想メモリは、スタック セグメントやヒープ セグメントなどのセグメントに分割されます。これらのセグメントは、アセンブリ コードでアセンブラー ディレクティブを使用して編成されます。さらに、スペース ディレクティブやロング セグメントなど、メモリを割り当てて値を格納するさまざまなタイプのストレージ ディレクティブについても説明します。次に、関数の呼び出しと戻りを管理するためにデータが格納されるスタック セグメントに注意が向けられます。これには、ローカル変数、関数の引数、戻りアドレス、および場合によっては中間結果の格納が含まれます。
  
  
• 00:55:00 ビデオのこのセクションでは、プレゼンターが複数の関数間で関数呼び出しを調整する問題について説明します。そのいくつかは、異なるファイルまたはライブラリから発生する可能性があります。すべての関数がうまく連携するようにするために、すべての関数が従わなければならない呼び出し規約が確立されています。 Linux x86 64 呼び出し規約では、2 つのポインター (BP と SP) を使用して、関数のインスタンス化ごとにすべてのスタック フレームを管理します。呼び出し命令が実行されると、IP の現在の値が戻りアドレスとしてスタックにプッシュされ、呼び出し命令はプログラム メモリ内の関数のアドレスにジャンプします。 return 命令は、call 命令の操作を元に戻し、リターン アドレスをスタックからポップして、呼び出し元の実行に戻ります。複数の機能が同じものを使いたいという問題に対処するには
  レジスタ、呼び出し規約では、各関数が使用できるレジスタのルールと、関数呼び出しを通じてそれらのレジスタを保持する方法について詳しく説明しています。
  
  
• 01:00:00 このセクションのビデオでは、C からアセンブリへのプログラミングでさまざまな関数を操作するときに、レジスタの状態を維持する方法について説明します。使用できる 2 つの方法について説明します。1 つは呼び出し元が呼び出しを呼び出す前にレジスタの状態を保存する方法で、もう 1 つは呼び出し先がすべてのレジスタの状態を保存する方法です。 x86 呼び出し規約には両方が含まれており、無駄な作業を避けるために、一部のレジスタを callee-save として指定し、他のレジスタを caller-save として指定します。このビデオでは、スタック メモリがどのように編成され、スタックが成長するかについても説明します。最後に、関数がスタック メモリの重複部分をどのように使用するかを調整する方法について説明します。
  
  
• 01:05:00 このセクションのビデオでは、C とアセンブリで関数呼び出しがどのように機能するかについて説明します。関数 C を呼び出す前に、関数 B は関数 C の非レジスタ引数を、ローカル変数の下にある独自のスタック メモリ内の予約済みリンケージ ブロックに配置します。負のオフセットでこれらの引数にアクセスします。関数 C が開始されると、関数プロローグが実行されます。関数プロローグは、B のスタック フレームのベース ポインターを保存し、新しいフレームに入るために BP を SP に等しく設定します。次に、独自のローカル変数用にスタック上のスペースを割り当てます。また、B が呼び出し元または呼び出すもののために作成するリンケージ ブロックに使用するスペースも割り当てます。このビデオでは、コンパイラが BP を取り除き、スタック ポインター RSP に基づいてすべてのインデックス付けを実行して、もう 1 つの汎用レジスターを取得する一般的な最適化についても言及しています。
  
  
• 01:10:00 このセクションでは、講師が聴衆に LV miR をアセンブリ コードにコンパイルするプロセスを説明します。最初のステップでは、グローバル fib ディレクティブやアラインメントなどのアセンブラー ディレクティブを使用して、関数 'fib' をグローバルにアクセス可能な関数として定義します。次に、関数プロローグは、var BP のプッシュ キューと RSP rbp のモブ キューで保存されます。アセンブリ コードはまた、引数を関数 RTI に移動する前に、Kali 保存レジスタであるいくつかのレジスタをスタックにプッシュし、それを RBX レジスタに移動します。最後に、N の値が 2 未満かどうかをチェックする比較命令が評価され、2 未満の場合は入力値が返されます。それ以外の場合は、いくつかの直線コードを使用して、n から 1 を引いた値の fib と n から 2 を引いた値の fib を計算し、それらを加算してその結果を返します。
  
  
• 01:15:00 このセクションでは、条件付きジャンプと、比較結果に応じてコード内で次に発生するさまざまな動作について説明します。 JGE 命令は、n が 2 以上の場合、LLVM 分岐操作の false 側のラベルにジャンプします。一方、n が 2 未満の場合、操作は操作の true 側に対応します。 LEA 命令は、次の目的で使用されます。移動操作では、関数呼び出しの結果が R14 に保存されます。次の一連の命令は、n-2 の値を計算し、それを RDI に格納してから、n-2 で fib を呼び出し、結果を AX に返します。最後に、R14 を AX に追加します。
  
  
• 01:20:00 このセクションでは、ビデオで C コードからアセンブリ コードへの変換について説明します。講演者は、このプロセスでは、制御フロー エッジで接続された基本ブロックで構成される制御フロー グラフを使用してコードを表現していると説明しています。また、アセンブリ コードで呼び出し規則を処理する複雑さについても言及しています。関数エピローグは、結果を返す前に、スタック フレーム内の何よりも前にレジスタを復元するために使用されます。このビデオは、セクション全体で取り上げた主なトピックを要約して締めくくります。

[MetaQuotes]

講義 6. マルチコアプログラミング

講義 6. マルチコアプログラミング

このビデオ講義では、マルチコア プログラミングと、ムーアの法則によるマルチコア プロセッサの出現とクロック周波数のスケーリングの終焉について説明します。講演者は、プロセッサが直面する電力密度の問題と、それがムーアの法則に追いつくためにチップに複数のコアを追加することにつながった方法について説明します。この講義では、共有メモリ ハードウェアのキャッシュ コヒーレンス プロトコルの基本と、並列プログラミングの抽象化を提供する Pthreads、TBB、OpenMP、Silk などの同時実行プラットフォームについても説明します。各プラットフォームの長所と短所について説明し、フィボナッチ プログラムの実装例を示します。このビデオでは、マルチコア プログラミングの包括的な概要と、プログラマーが直面する課題と解決策について説明します。

このビデオでは、並列処理を処理するための抽象化ツールである Silk のさまざまな側面についても説明します。講演者は、ネストされたシルク for ループ、アセンブリ コードの生成、レデューサーを使用したリダクション、スケジューラー、パフォーマンスの最適化などのトピックについて説明します。また、Silk エコシステムの概要と、それぞれデバッグとスケーラビリティの分析のための Silk Sanitizer や Silk Scale などの関連ツールも提供します。主なポイントは、マルチコア プロセッサ用の並列プログラムを作成するのは困難な場合があるということですが、Silk は複雑なタスクを効率的に処理することでプロセスを簡素化し、プログラマーがコードの実行をより細かく制御できるようにします。

• 00:00:00 このセクションでは、インストラクターがマルチコア プログラミングと、マルチコア プロセッサが出現した理由について説明します。チップに搭載できるトランジスタの数は 2 年ごとに 2 倍になるというムーアの法則の出現と、2004 年から 2005 年頃のクロック周波数のスケーリングの終了により、半導体ベンダーは複数のプロセッサ コアを搭載したチップの製造を開始しました。これは、チップ上のシングルコアの周波数を上げることができなくなり、並列処理を可能にする設計モデルに切り替える必要が生じたためです。インストラクターは、チップ上のトランジスタの数とプロセッサの最大周波数との関係も明らかにします。
  
  
• 00:05:00 このセクションでは、プロセッサが直面する電力密度の問題についてスピーカーが説明します。クロック周波数が高くなると、電力密度が指数関数的に増加します。これにより、ムーアの法則に対応し、電力密度の制限を超えないようにするために、複数のコアがチップに追加されました。次にスピーカーは、チップ マルチプロセッサとして知られる抽象的なマルチコア アーキテクチャを紹介し、P スレッド、winAPI スレッド、Intel スレッドなどのさまざまな同時実行プラットフォームを使用して、マルチコア マシンで並列プログラムをプログラムするためのハードウェアの課題とソフトウェア ソリューションに関する講義の概要を説明します。ビルディング ブロック、openmp などに加えて。
  
  
• 00:10:00 このセクションでは、スピーカーがマルチコア プログラミングでキャッシュがどのように機能するかを説明します。 1 つのプロセッサが値をメイン メモリからキャッシュにロードすると、将来再びアクセスする必要がある場合に備えて、その値をキャッシュに保持します。別のプロセッサが同じ値をロードしたい場合、メイン メモリにアクセスする代わりに、最初のプロセッサのキャッシュを介してそれを取得することもできます。ただし、あるプロセッサが自身のキャッシュの値を更新すると、別のプロセッサのキャッシュの値が古くなってしまうという問題が発生します。 MSI プロトコルは、この問題に対する基本的な解決策であり、キャッシュ ラインに 3 つの可能な状態 (M、S、および I) をラベル付けして、キャッシュ間の一貫性を確保します。
  
  
• 00:15:00 このセクションでは、共有メモリ ハードウェアにおけるキャッシュ コヒーレンス プロトコルの基本について説明します。特に、あるプロセッサのキャッシュ内のキャッシュ ラインを変更すると、同じラインの他のキャッシュのコピーが無効になる可能性があります。この講義では、簡単なプロトコルを紹介し、他のより複雑なプロトコルが実際にどのように存在するかを説明します。複数のプロセッサが同じキャッシュ ラインを変更する場合、ハードウェアは競合を管理しますが、これにより「無効化の嵐」が発生し、パフォーマンスが低下する可能性があります。この講義では、同時実行プラットフォームがこれらの複雑さを抽象化し、並列プログラミングでの同期と通信を支援できることにも言及しています。
  
  
• 00:20:00 このセクションでは、スピーカーはフィボナッチ数の例を使用して、さまざまな同時実行プラットフォームについて説明します。フィボナッチ プログラムは、フィボナッチ数を複数回計算する再帰アルゴリズムを使用して実装されているため、アルゴリズムとしては不十分です。 2 つの再帰呼び出しは、完全に独立した計算であるため、並列化できます。スレッド化の標準 API である Pthreads を使用して、この並列化を実装できます。
  
  
• 00:25:00 このセクションでは、スピーカーは、プログラミングの同時実行を可能にする関数のライブラリである Pthreads について説明します。 Pthreads は、特殊なセマンティクスを持つ関数のライブラリを使用してコード内で同時実行を指定できるようにするため、自作の同時実行プラットフォームを提供します。 Pthreads の各スレッドは、プロセッサの抽象化を実装し、実際のマシン リソースに多重化されます。 Pthreads は、内部スレッドの調整に関係するプロトコルを単純化するマスクも提供します。 Pthreads ライブラリには、pthread が作成する新しいスレッドを格納して識別する pthread_create や、スレッドが終了するまで待ってからコードを続行する pthread_join などの主要な関数があります。講演者は、Pthreads を使用してフィボナッチ数列を実装する方法を実演します。
  
  
• 00:30:00 このセクションでは、プレゼンターは、フィボナッチ数列を並列で実行するための Pthreads コードの実装について説明します。彼らは、入力サイズが十分に小さい場合は、並列にスレッドを作成するコストがかかるため、プログラムを順次実行する方がよいと説明しています。このコードは、入力引数をスレッドにマーシャリングし、arguments 構造体に格納します。プレゼンターは、Pthread の作成、Pthread の結合、およびコードが再帰的にスレッドを作成する必要がある場合にコードがはるかに複雑になるなど、いくつかの欠点について説明します。また、このコードは 1 つのスレッドしか作成しないため、4 つのプロセッサで実行した場合、可能な最大速度は 2 であると述べています。
  
  
• 00:35:00 ビデオのこのセクションでは、Pthreads の問題とフィボナッチ数列のコードについて説明します。スレッドを作成するための高いオーバーヘッドにより、粗粒度の同時実行が発生し、スケーラビリティの問題は、2 つのコアが同じ量の作業を行っていないことです。フィボナッチ ロジックが 1 つの関数内にうまくカプセル化されておらず、保守と変更が困難なため、コードにはモジュール性も欠けています。引数のマーシャリングによってコードも複雑になります。これは、アセンブリでコードを記述しなければならないのと似ています。次にビデオでは、これらの問題の解決策を提供するために Intel が開発したライブラリである Threading Building Blocks (TBB) を紹介します。
  
  
• 00:40:00 このセクションのビデオでは、インテル スレッド ビルディング ブロック (TBB) ライブラリの使用について説明しています。このライブラリは、プログラマがネイティブ スレッドを使用できるように設計された C++ ライブラリであり、スレッドを直接処理することなくワークスティーリング アルゴリズムを使用できます。タスクを指定することにより、TBB はスレッド間でそれらの負荷を分散し、POSIX スレッドを使用するよりもコードの記述が簡単になり、パフォーマンスが向上します。このビデオは、TBB を使用してフィボナッチ プログラムを実装する例を示し、子タスクを再帰的に作成する方法を示し、複数のプロセッサ間でより多くの並列処理とスケーラビリティを可能にします。また、TBB は、ループの並列処理、データ集約、およびソフトウェア パイプライン処理のためのテンプレートと、共有データへの安全な同時アクセスのための同時コンテナー クラスも提供します。
  
  
• 00:45:00 このセクションでは、講演者は同時実行性の問題に対する 2 つの言語的ソリューション、OpenMP と Silk を紹介します。 OpenMP は、C と C++、および Fortran に言語拡張を提供する仕様であり、コンパイラ プラグマを使用してどのコードを並列実行するかを指定します。ループの並列処理、タスクの並列処理、およびパイプラインの並列処理をサポートし、多くのスケジューリングおよびデータ共有ディレクティブと同期構造を備えています。スピーカーは、OpenMP でフィボナッチを実装する例を提供します。これは、Pthreads や TBB を使用するよりも簡単でパフォーマンスが優れています。 OpenMP は、多くの機能を提供し、コードを簡素化するため、並列プログラムを作成するための一般的なソリューションです。
  
  
• 00:50:00 このセクションでは、講演者はシルク プログラミング プラットフォームについて説明します。シルク プログラミング プラットフォームは、ジョイントとベクトルの並列処理をサポートし、効率が証明されているワークスティーリング スケジューラを備えています。このプログラムには、グローバル変数を使用してコードを並列化するためのハイパー オブジェクト ライブラリもあり、シルク スクリーン レース検出器やシルク ビューと呼ばれるスケーラビリティ アナライザーなどのプログラミング ツールが付属しています。講演者はまた、授業では Silk Plus を使用しないが、taper LLVM として知られるより優れたコンパイラを使用する予定であることに注意します。このコンパイラは、他のすべての Silk 実装よりも優れたコードを生成します。
  
  
• 00:55:00 このセクションでは、並列実行を有効にするための Silk spawn ステートメントと Silk sync ステートメントの使用について、例を通して説明します。最初の例は、フィボナッチのソルト コートです。これには、n-2 の fib が実行されている間に、n-1 の fib がそれを呼び出す関数と並行して実行できることを示唆する Silk spawn ステートメントと Silk sync ステートメントが含まれています。ただし、ランタイム システムは、これらのタスクを並行して実行するかどうかを決定します。議論されているもう 1 つの例は、ループの並列処理です。ここでは、シルクの for ステートメントを使用して for ループを並列に実行し、コンパイラーは繰り返しスペースを半分に再帰的に分割し、範囲が小さくなりすぎて並列実行できないまで、シルクの spawn ステートメントと Silk sync ステートメントを使用します。正しい結果を得るには反復が独立していることを保証することが重要であり、シルクを使用するとオーバーヘッドが追加されます。
  
  
• 01:00:00 このセクションのビデオでは、ネストされた Silk for ループの使用と、clang コンパイラでフラグを使用してアセンブリ コードを生成する方法の詳細について説明します。シルクの for ループを使用した値の合計のサンプル コードでは、複数のプロセッサが同じメモリ位置に書き込むときに決定性競合の問題が発生します。 Silk は、レデューサー マクロを登録および登録解除する際に、特定の変数の加算関数を処理するハイパー オブジェクトであるレデューサーを使用することで、この問題に対処します。これは、マルチコア プログラミングで発生するリダクションの問題に対処する方法であり、他の多くのリダクション演算子も使用できます。
  
  
• 01:05:00 このセクションでは、スピーカーは Silk のレデューサーについて説明します。これは連想二項演算と恒等要素を持つ代数構造です。 Silk には、加算、乗算、最小値、最大値、XOR など、いくつかの事前定義されたレデューサーがあり、独自のレデューサーを定義できます。 Silk の利点の 1 つは、プログラムの有効な逐次解釈が常に存在するため、デバッグが容易になることです。また、ワークスティーリング スケジューリング アルゴリズムを使用してタスクのバランスを取ることで、プログラムを監視し、使用可能なプロセッサ コアにマップするランタイム スケジューラを備えていることです。均等に。他の同時実行プラットフォームとは異なり、Silk のスケジューラは理論的に効率的です。
  
  
• 01:10:00 このセクションでは、スピーカーはマルチコア プログラミングのための Silk エコシステムの概要を説明します。これには、Silk ソース コードのコンパイル方法、並列およびシリアル パフォーマンスのベンチマーク、Silk Sanitizer や Silk などのツールを使用した問題のデバッグ方法が含まれます。規模。また、シリアル プログラムのパフォーマンスを最適化することの重要性と、Silk のスケジューラがプログラムの実行中にさまざまなタスクを処理する方法についても強調しています。さらに、講演者は、シルク スケールがコードが利用できるプロセッサの最大数をどのように決定できるかを説明し、スケーラビリティを分析するための便利なツールにします。
  
  
• 01:15:00 このセクションでは、講演者がマルチコア プログラミングに関する講義の重要なポイントをまとめます。最新のプロセッサのほとんどは複数のコアを備えているため、高性能を実現するには並列プログラムを作成する必要があると彼らは説明しています。ただし、そのようなプログラムを作成するのは難しい場合があります。そこで Silk の出番です。このツールは、プロセッサ コアをプログラマから抽象化し、同期、通信プロトコル、および負荷分散を処理します。講演者は、学生が Silk を使用して独自の並列スクリーンセーバーを実装する将来のプロジェクトについても言及しています。

[MetaQuotes]

講義 7. レースと並列処理

講義 7. レースと並列処理

このビデオでは、Silk プログラミングのレース、並列処理、および計算タスクに関連するさまざまなトピックを取り上げます。カバーされるいくつかの重要な概念には、同時実行のための spawn ステートメントと sync ステートメント、競合状態を回避することの重要性、それらを識別するための Silk の競合検出器の使用が含まれます。このビデオでは、プログラム内の並列処理の量を定量化する方法として、アムダールの法則、仕事の法則、スパンの法則、および計算の作業とスパンを分析する方法についても説明します。貪欲なスケジューラの定理に焦点を当てて、並列ソート アルゴリズムの潜在的な高速化と並列性、およびスケジューリング理論の概念についても説明します。全体として、このビデオは、Silk プログラミングでのプログラム パフォーマンスの理解と最適化に関する貴重な洞察を提供します。

このビデオでは、貪欲なスケジューラ バウンドの結果が説明されています。これは、基本的に、T1/Tinfinity が P^2 以上である限り、貪欲なスケジューラがほぼ完全な線形スピードアップを達成することを示しています。ワーク スティーリング スケジューラを使用するシルク スケジューラは、プロセッサの数が T1/Tinfinity よりもはるかに少ない限り、ほぼ完全な線形速度向上を実現できます。シルク ランタイム システムは、準備が整ったストランドのワーク デックを維持することで機能し、デックの下部をスタックのように操作します。ビデオでは、Cactus Stack についても説明しています。これにより、スタックの複数のビューを並行して使用でき、並行関数呼び出しが可能になります。 P プロセッサの実行に必要なスタック領域の上限は、多くの場合、実際に必要な量よりもはるかに緩いです。これは、各プロセッサが作業を盗むたびに計算グラフをずっと下る必要がない場合があるためです。

• 00:00:00 このセクションでは、講師が Silk のレースと並列処理のトピックを紹介します。これは、今後の宿題やプロジェクトで重要になります。親関数と子関数の同時実行を可能にする、Silk の spawn および sync ステートメントの基本が確認されます。講師はまた、MIT のポリシー メンバーと会うことの重要性と、過去の例で見られるように悲惨な結果につながる可能性のあるコードの競合状態を回避することの重要性を強調しています。見つけるのが最も難しい人種バグは、壊滅的な出来事を引き起こしたものであり、従来のテストはしばしば効果的ではありません. Silk は、コード内の潜在的な競合バグを特定するのに役立つツールを提供しています。
  
  
• 00:05:00 このセクションでは、論理的に並列なコードが同じメモリ位置にアクセスし、少なくとも 1 つが書き込みを登録するというまれなイベントでのみ発生する可能性があるため、競合が開発者にとって発見するのが最も困難なバグの 1 つであることをビデオで説明します。それに。例として、このビデオでは、依存関係グラフを利用して、2 つの並列パス間で共有される競合バグが常に発生するとは限らないことを示す簡単なコードを示しています。競合は、両方のストアが同じメモリ位置に書き込むときに発生し、どちらの実行パスが最初に完全に実行されるかによって異なる出力になる可能性があります。
  
  
• 00:10:00 このセクションでは、スピーカーは、2 つの命令が同じメモリ位置にアクセスし、少なくとも 1 つの命令が書き込み操作である場合に発生する決定性競合の概念を説明し、プログラムで非決定論的な動作を引き起こします。講演者は、Silk の for ループの反復が独立していることを確認したり、Silk spawn ステートメントと対応する Silk sync ステートメントの間のコードも独立していることを確認したりするなど、競合を回避する方法に関するヒントを提供します。講演者はまた、機械語のサイズが重要であり、非標準型を使用するパックされたデータ構造を読み書きするときは注意が必要であることに注意します。
  
  
• 00:15:00 このセクションのビデオでは、Silk プラットフォームの「レース検出器」について説明しています。これは、プログラム内の潜在的な競合状態を特定するのに役立ちます。 「-f sanitized equal to silk」フラグを使用してインストルメント化されたプログラムを生成することにより、Silk は問題のある競合を報告およびローカライズできるため、コードのデバッグに役立ちます。このビデオでは、並列処理の概念と、Silk 実行モデルが計算グラフを使用して実行中の計算の展開を示す方法についても説明しています。これらの概念は、プログラムのパフォーマンスを最適化および改善しようとするときに理解することが重要です。
  
  
• 00:20:00 計算データの頂点の種類: 初期ストランド、継続ストランド、関数呼び出しストランド、および最終ストランド。最初のストランドには実行される最初の命令が含まれ、最後のストランドにはプログラムで実行される最後の命令が含まれます。継続ストランドはスポーン操作の継続を表し、関数呼び出しストランドは関数呼び出しの実行を表します。計算データは実行中に動的に展開され、プロセッサに依存しないことに注意することが重要です。つまり、ランタイム システムは実行時にタスクをプロセッサにマップする方法を見つけ出します。要約すると、計算データは、プログラムの並列性と並行性を理解するための強力なツールです。
  
  
• 00:25:00 このセクションでは、計算 DAG と、それらを使用してプログラムの並列処理を分析する方法について学習します。計算 DAG は、プログラムのさまざまな部分間の依存関係を表し、スポーン エッジ、呼び出しエッジ、リターン エッジ、継続エッジなど、さまざまな種類のエッジを持ちます。計算データを使用してプログラムの並列度を分析することができ、アムダールの法則を使用して並列度を定量化します。提供されている例では、順次実行する必要があるノードが 7 つ未満であり、計算にある程度の並列性があることを示しています。
  
  
• 00:30:00 このセクションでは、並列処理で可能な最大スピードアップを決定する方法として、アムダールの法則の概念を紹介します。プログラムのシリアル部分は 3/18 であり、最大 6 倍のスピードアップが得られると判断されます。アムダールの法則は並列処理の上限を提供しますが、実際には緩すぎることがよくあります。ワーク法則とスパン法則は、並列処理の別の定義として導入されます。ワーク法則は、P 個のプロセッサでの実行時間が、プログラムの作業を P で割った値以上であることを示し、スパン法則は、実行時間がP 個のプロセッサでの実行時間は、少なくとも無数のプロセッサでの実行時間です。これらの法則は、多くの場合、アムダールの法則よりも優れた最大速度の上限を提供します。
  
  
• 00:35:00 このセクションでは、スピーカーは、さまざまな計算の作業量とスパン量を構成する方法について説明します。彼らは、2 つの並列計算を実行する場合でも、作業は個々の計算の作業の合計であり、スパンは個々の計算のスパンの最大値であると説明しています。講演者は、P プロセッサの高速化についても定義し、サブリニア、リニア、スーパーリニアの高速化について説明します。彼らは、可能な最大のスピードアップは、計算の並列処理に等しいことに注目しています。これは、計算に沿ったステップごとの平均作業量に等しいです。全体として、このセクションでは、計算の構成とその並列処理の測定方法についての洞察を提供します。
  
  
• 00:40:00 このセクションでは、スピーカーは、計算 DAG や並列クイックソート アルゴリズムなどの例を使用して、最大の並列処理を計算するために計算の作業と範囲を分析する方法について説明します。スピーカーは、コンパイラ インストルメンテーションを使用してプログラムのシリアル実行を分析し、プログラムの並列スピードアップの上限を導き出す Silk Scale スケーラビリティ アナライザーを紹介します。講演者はまた、大規模な計算の並列処理を手動で分析するのは面倒ですが、Silk Scale はこれを支援できると述べています。
  
  
• 00:45:00 このセクションのビデオでは、並列計算を実行し、観測されたスピードアップを示すプロットを生成した結果と、スパンと仕事の法則からの境界について説明します。プロットは、最大速度向上が約 5 であることを示しており、プログラムの並列処理が低いことを示しています。分析の結果、並列処理のボトルネックはパーティション関数の順次実行であり、クイックソートの並列バージョンの期待される作業とスパンは n log n のオーダーであることが明らかになりました。達成できる最大の並列処理は log log n のオーダーであり、それほど高くはありません。並列処理を増やすには、パーティション関数を並列化する必要があります。
  
  
• 00:50:00 このセクションでは、大幅なスピードアップを実現するために、パーティションおよびマージ ソート アルゴリズムに並列処理を実装することの重要性について講演者が説明します。これらのアルゴリズムの並列バージョンは、全体の範囲が log 二乗 n で制限されており、log n に対する n の高い並列性があります。さらに、高い並列性と、対応する逐次アルゴリズムの作業バウンドと漸近的に等しい作業バウンドを備えた実用的な並列アルゴリズムが他にも多数あります。講演者はまた、スケジューリング理論の概念を紹介し、分散スケジューラが Silk プログラミングで使用される一方で、集中型スケジューラが実行時に計算 DAG を使用可能なプロセッサにマップできることを説明します。例として、計算のすべてのステップで可能な限り多くのことを行う貪欲なスケジューラーを使用します。
  
  
• 00:55:00 このセクションでは、未来を考えずに現在の時間ステップで可能な限り多くの作業を実行する貪欲なスケジューラの概念が紹介されています。少なくとも P 本のストランドが準備できている完全なステップと、P 本未満のストランドが準備できている不完全なステップが定義されます。 1968 年に Ron Graham によって最初に示された有名な定理は、貪欲なスケジューラによって達成される時間境界は、T1/P + T 無限大以下であると述べています。T1 は作業であり、T 無限大はスパンです。この定理の証明が提供され、任意の貪欲なスケジューラーが最適な実行時間の 2 倍以内で達成されることが示されています。
  
  
• 01:00:00 このセクションでは、最適スケジューラの 2 分の 1 以内で達成する貪欲なスケジューラ バウンドの帰結をビデオで説明します。 T1/Tinfinity が P^2 以上の場合、欲張ったスケジューラーはほぼ完全な線形スピードアップを達成するという結果が得られます。ここで、T1/P に T infinity を掛けると、プロセッサの数と比較した計算の並列処理の量が測定されます。利用可能。シルク スケジューラはワーク スチール スケジューラを使用します。これは、T1/P に次数 T 無限大を加えたものに等しい TP の予想実行時間を持ち、スケジューリングのオーバーヘッドを考慮して T 無限大の前に Big O を置き、ほぼプロセッサの数が T1/Tinfinity よりもはるかに少ない限り、完全な線形速度アップです。シルク ランタイム システムは、準備が整ったストランドのワーク デックを維持することで機能し、デックの下部をスタックのように操作します。 Silk Scale の計測機能により、作業とスパンの項を測定して、プログラムの並列性を判断できます。
  
  
• 01:05:00 このセクションでは、スピーカーはプロセッサのスポーンと並列処理の概念について説明します。彼らは、プロセッサが関数を呼び出すと、その関数のフレームをスタックの一番下に配置し、スタックの一番下にフレームを生成できると説明しています。複数のプロセスが並行して発生する可能性があり、スポーンと呼び出しからリターンを行うことができます。労働者がやるべき仕事がなくなると、彼らは別のプロセッサのデッキの一番上から盗みます。有名な定理によると、ワーカーが盗む頻度は非常に低く、線形に近いスピードアップが得られます。また、スピーカーは、Silk がポインタに関する C の規則をサポートしていることにも注意します。この規則では、スタック スペースへのポインタを親から子に渡すことができますが、子から親には渡すことができません。
  
  
• 01:10:00 ビデオのこのセクションでは、スピーカーは Cactus スタックについて説明します。これは、Silk プログラムの祖先計算グラフ内のタスクによって表示されるスタックです。このスタックを使用すると、スタックの複数のビューを並列に表示できるため、並列関数呼び出しが可能になります。講演者は、Silk プログラムに必要なスタック スペースは、プログラムのシリアル実行に必要なスタック スペース (S sub 1) に、使用されるプロセッサの数 (P) を掛けることで求めることができると説明しています (Sサブ P ≤ P x S サブ 1)。スピーカーは、この概念の高レベルの証明を提供し、P プロセッサの実行に必要なスタック スペースの上限は、多くの場合、実際に必要な量よりもはるかに緩いことに注意します。仕事を盗む時間。

[MetaQuotes]

講義 8. マルチスレッドアルゴリズムの分析

講義 8. マルチスレッドアルゴリズムの分析

このビデオでは、分割統治の繰り返しを分析するためのマスター メソッドについて説明し、n の対数基数 B と A の対数基数 B を比較して、n の成長と必要な作業を決定することにより、マルチスレッド アルゴリズムに適用します。このビデオでは、基本的なマルチスレッド アルゴリズムのソリューションを含むチート シートを紹介し、作業とスパンの分析、作業効率、粒度最適化による間接費の克服などのトピックを取り上げます。技術的な話題を伝える際の共感の重要性が強調され、DAG の概念が作業とスパンのバランスをとって並列処理を増やし、実行時間を短縮する手段として導入されます。

このビデオでは、ワークとスパンに焦点を当てたマルチスレッド アルゴリズムの分析、およびスパンを最小化しながら並列処理を最大化して、ほぼ完全な線形スピードアップを達成する方法についても説明します。講演者は、スレッドに与えられるタスクの数が十分に大きいマルチスレッド アルゴリズムへの分割統治アプローチを提案し、スケジューリング オーバーヘッドが原因で多数の小さなタスクを生成しないように警告します。提示されたコード例には、効率的なものと粗末なものが含まれています。スピーカーは、2 次元コーディングとインデックス付けで部分行列を表現する方法についても説明し、パフォーマンスを向上させるために分割統治型行列乗算コードで「restrict」を使用することを強調します。

• 00:00:00 このセクションでは、インストラクターは、生徒に分割統治の繰り返しと、それらを解決するためのマスター メソッドと呼ばれる一般的な方法について思い出させることから始めます。このメソッドは、繰り返しとその形式 T(n) = a*T(n/B) + F(n) を扱います。ここで、a は定数、B は分割係数、F(n) は総作業量です。問題をサイズ n/B の部分問題に分割します。生徒は、再帰ツリーと、各レベルがサイズ n/B のサブ問題にどのように分割されるかを思い出します。行全体の実行時間を加算し、ツリーの高さを計算して、各レベルのサブ問題の数を掛けます (a ^k)。最後に、学生は A の n^log ベース B がアルゴリズムの合計実行時間であることを計算します。
  
  
• 00:05:00 このセクションでは、マルチスレッド アルゴリズムを評価する際に n の増加と必要な作業を決定する方法についてスピーカーが説明します。重要なのは、n の対数底 B と、N の F を持つ A の対数底 B を比較することです。話者は 3 つの考えられるケースを取り上げます。最初の例は、対数底 B n が n の F よりもはるかに大きい場合です。この場合、重みの定数部分は葉にあり、A の対数底 B に対する答えは n になります。2 番目のケースは、対数底 B n が n の F にほぼ等しい場合です。このために、追加の対数を追加すると、答えは対数底 B に対する n から k に n の 1 を加えたものになります。最後に、3 番目のケースは、対数ベース B が N の F よりもはるかに小さい場合です。これは、F が規則性条件を満たす必要があることを意味します。これは、多項式や対数など、対象となるすべての関数によって満たされます。
  
  
• 00:10:00 このセクションでは、スピーカーは、コンピューター サイエンスで一般的に使用される基本的なマルチスレッド アルゴリズム ソリューションを含むチート シートを提示します。最初のアルゴリズム T(n) = T(n/2) + n は、ケース 1 に該当するため、Θ(n^2) の解になります。 2 番目のアルゴリズム T(n) = T(n/2) + n^2logn は、k = 0 のケース 2 に該当するため、Θ(n^2logn) の解になります。3 番目のアルゴリズムでは、T(n) = T(n/2) + n^2、ケース 1 に該当するため、解は Θ(n^2) です。 4 番目のアルゴリズム T(n) = 2T(n/2) - n は、マスター メソッドのどのケースにも当てはまらず、Θ(n^2loglogn) の解を持つため、注意が必要です。
  
  
• 00:15:00 このセクションでは、スピーカーは Aqua Bazi メソッドと、ほとんどのプログラムを分析するのに十分なマスター メソッドよりも複雑である方法について説明します。次に、外側のループが並列化されているインプレース行列転置コードを使用した並列ループの例を示します。講演者は、効率的な並列処理のために反復空間と負荷分散を正しく定義することの重要性を強調しています。また、オープン シルク コンパイラとランタイム システムによってループがどのように実装されるかについても説明します。
  
  
• 00:20:00 このセクションでは、スピーカーは、分割統治法を利用してループを 2 つの部分に分割し、1 要素の反復に達するまでそれぞれの側で再帰的に自分自身を呼び出すループの再帰プログラムについて説明します。この計算の作業は作業とスパンの観点から分析されます。葉の作業は次数 n の 2 乗であり、上部はシータ n です。これは、葉から根までのすべてのレベルに n 個のノードしかないためです。オープン シルク ランタイム システムにはループ プリミティブがないため、ループは効果的にこの分割統治アプローチに並列に変換されます。
  
  
• 00:25:00 このセクションでは、スピーカーはマルチスレッド アルゴリズムの作業とスパン分析について説明します。彼は、完全なバイナリ ツリーの n 個の葉のそれぞれに対して一定の作業が行われるため、作業の合計は Θ(n²) であると説明しています。ループ制御の範囲は log(n) です。これは、無数のプロセッサが対数時間でタスクを完了できることを意味します。ただし、計算には線形成分 (n) があるため、合計スパンは Θ(n) です。したがって、並列度は Θ(n) であり、これはほとんどの実用的なシステムにとって適切な量です。次にスピーカーは、内側のループも並列化するシナリオを検討し、結果として生じる作業量について説明します。
  
  
• 00:30:00 ビデオのこのセクションでは、教授が並列アルゴリズムにおける作業効率の概念について説明しています。アルゴリズムを並列化しても作業は変わりませんが、大きな並列処理を実現するために計算のスパンを減らすことが期待されます。ただし、並列化によって作業が増える場合があり、元のアルゴリズムと比較してプログラムの速度が低下するため、問題になる可能性があります。作業効率の高い並列アルゴリズムは、教授が教えたいと考えているものです。これは、作業を追加することなく、スパンを縮小して大きな並列処理を実現できるためです。教授は、同じ質問をするかもしれないが質問することを恐れている他の人を助けることができるので、質問をして学習プロセスで間違いを犯すことの重要性を強調しています.彼は、学生が上位 10% に含まれていなくても、学習プロセスに参加して参加することを奨励しています。
  
  
• 00:35:00 このセクションでは、技術的なトピックに関するコミュニケーションにおける共感の重要性が強調されています。教授は、授業の内容に慣れていない可能性のあるクラスの他の生徒に対しても、忍耐強くあるよう学生に勧めます。マルチスレッド アルゴリズムの分析に移ると、ベクトル加算の分割統治アルゴリズムが提示され、並列処理は log n に対して n であることがわかります。並列処理とプロセッサ数の関係が議論されており、教授は、並列処理が多いほど良く見えるかもしれませんが、それは特定のしきい値までしか有益ではないことを強調しています。
  
  
• 00:40:00 このセクションでは、スピーカーは、マルチスレッド アルゴリズムのオーバーヘッドの一部、特にサブルーチン呼び出しのオーバーヘッドを最適化する方法について説明します。それらは「粒度」の概念を導入し、分割統治プロセスのリーフでチャンクあたり最大 G 個の要素があることをコンパイラーに示唆します。これにより、サブルーチンのオーバーヘッドを 1 回だけではなく G 回の反復で償却できるため、パフォーマンスが向上します。粒度が指定されていない場合、システムはオーバーヘッドを最小限に抑えるために最善の推測を行います。スピーカーは、変数 I、G、および s を分解して、このコンテキストでの作業を分析し、並列制御要素のない元のコードでの作業と比較します。
  
  
• 00:45:00 このセクションでは、スピーカーは、マルチスレッド アルゴリズムの分析と、最新のアウト オブ オーダー プロセッサでループ制御がどのように安価であるかについて話します。彼らは、無限の数のプロセッサでアルゴリズムを実行するのにかかる時間であるスパンを調べ、反復のコストとオーバーヘッドのコストについて議論します。スピーカーは、リーフの数と、それぞれに対して実行する必要がある「s」と呼ばれるカラフルな操作の観点からスパンを分類します。また、完全なバイナリ ツリー内の内部ノードの数と、スパンを計算するためにたどるパスに関する質問にも答えます。
  
  
• 00:50:00 このセクションでは、スピーカーはマルチスレッド アルゴリズムの分析、特に DAG (有向非巡回グラフ) の概念と、それがアルゴリズムのパスに与える影響について説明します。それらは、並列処理を可能にするために、DAG の異なるサブツリー間の独立性の必要性を強調しています。目標は、アルゴリズムの作業と範囲のバランスを取ることです。これら 2 つの要因は反対方向に作用するからです。重要なのは、G (並列処理の量) を I (アルゴリズムの順次部分) よりもはるかに大きくすることです。これにより、オーバーヘッドが小さくなり、処理が高速になります。講演者は、この概念の実装についても言及していますが、これについては講義シリーズで後述することに注意してください。
  
  
• 00:55:00 このセクションでは、スピーカーは for ループを使用して 2 つのベクトルを追加するマルチスレッド アルゴリズムの実装を提示します。ループは V add と呼ばれる演算子を使用してシリアル ベクトル加算を実行し、ループはサイズ G のベクトルを使用して G のグループで加算を生成します。G が 1 に等しいと仮定すると、ループの作業は次数 n であり、スパンも注文n。並列処理は、作業とスパンの比率をとることによって測定されます。これは、n を n で割ると 1 に単純化されます。スピーカーは、マルチスレッド アルゴリズムを分析する目的は、並列処理を増やし、スパンを減らしてランタイムを最小限に抑えることであることを強調し、手法を強調します。これはストリップ マイニングと呼ばれ、マルチスレッド アルゴリズムを改善する 1 つの方法として、長さ N のループを二重のネストされたループに置き換えて計算を並列化します。
  
  
• 01:00:00 このセクションでは、マルチスレッド アルゴリズムのパフォーマンスをワークとスパンの観点から分析します。スパンは分母にあるため、並列処理を最大化するためにスパンを最小化する方法について説明します。ほぼ完全な線形スピードアップが必要な場合、重要なのはプロセッサの 10 倍の並列処理を生成することです。講演者は、必要に応じて並列処理をトレードオフして、作業のオーバーヘッドを削減することも提案しています。十分な並列処理が保持されている限り、粒度を調整することをお勧めします。
  
  
• 01:05:00 このセクションでは、スピーカーはマルチスレッド アルゴリズムでの分割統治戦略の使用について説明し、いくつかのタスクにチャンクされていない限り、多数の小さなタスクを次々に生成しないようアドバイスします。結構です。一般に、スレッドに与えられるタスクの数が十分に多い場合、分割統治アプローチが必要です。講演者は、スケジューリングのオーバーヘッドに注意するよう警告し、より多くのオーバーヘッドがある内側のループではなく、外側のループを並列化することを提案しています。ここに示すコード例は、スケジューリングが 1 回だけ発生する効率的なコードと、オーバーヘッドが n 回発生する厄介なコードを示しています。行列の乗算は、分割統治法を使用するマルチスレッド アルゴリズムの例として使用され、n を n 行列で乗算するために、n を 2 行列で n を 2 行列で 8 回乗算し、次に 2 つの n x n 行列を加算します。
  
  
• 01:10:00 このセクションでは、スピーカーは、2 次元コーディングとインデックス付けで部分行列を表す方法について説明します。特に、C や Fortran などの言語の行優先順と列優先順で説明します。アイデアは、すべての 2 次元行列を 1 次元行列としてインデックス付けできるということです。サブ行列を扱う場合、行数と長い行列の長さを追加して、IJ 要素がどこにあるかを知る必要があります。さらに、分割統治を実装する場合、4 つのサブマトリックスのそれぞれの開始コーナーを知ることが重要です。最終的に、講演者は、分割統治型の行列乗算コードで「restrict」を使用して、どの要素をエイリアス化できるか、またはエイリアス化できないかをコンパイラに伝えることを強調しています。
  
  
• 01:15:00 このセクションでは、スピーカーは行列乗算のマルチスレッド アルゴリズムについて説明します。このアルゴリズムは、行列をより小さな部分行列に再帰的に細分割し、各部分行列を再帰的に乗算して最終結果を得ることに基づいています。スピーカーは、n が 2 のべき乗であるかどうかをすばやく判断するためのちょっとしたトリックを強調し、マクロを使用して行列のインデックス付けを簡素化します。このアルゴリズムは高い並列性を示しますが、これを減らしてパフォーマンスを向上させることができます。他の同様のアルゴリズムについても言及されています。

[MetaQuotes]

講義 9. コンパイラにできることとできないこと

講義 9. コンパイラにできることとできないこと

このビデオでは、さまざまな例を使用して、コンパイラがコードを最適化する方法について説明します。コンパイラが不要なストレージとメモリの参照を削除する方法と、ループを最適化してパフォーマンスを向上させる方法について説明します。

このビデオでは、コンパイラー最適化パスの概念と、それらを使用してコードのパフォーマンスを向上させる方法についても説明しています。また、特にベクトル化に関して、コンパイラーの制限についても説明します。コンパイラーは、コード内のポインターが別名にならないと判断できる場合にのみ、コードをベクトル化できます。ポインターが別名である場合、コンパイラーはコードをベクトル化できません。プログラマーは、ポインターに注釈を付けてその使用法に関する詳細情報を提供することで、コンパイラーを支援できます。

• 00:00:00 このレクチャーでは、Tao Schardl がコンパイラでできることとできないことについて説明します。彼は、コンパイラーの最適化を研究することは、開発者が最適化を利用するコードを作成する方法と、コンパイラーが既に最適化できるコードを手動で最適化することを避ける方法を理解するのに役立つと説明しています。
  
  
• 00:05:00 コンパイラは大きなソフトウェアであり、コンパイラ自体にバグがある場合のデバッグに非常に役立ちます。コンパイラが間違いを犯した可能性がある場所や、コンパイラができるはずだと思っていたことが単に実行されなかった場所を理解するのに役立ちます。
  
  
• 00:10:00 コンパイラは多くの最適化を実行できますが、実行できないこともあります。たとえば、常に高速パスを作成したり、ループを最適化したりできるとは限りません。
  
  
• 00:15:00 コンパイラはコードを最適化するために多くのことを行うことができますが、うまくできないこともあります。 1 つの例はデータ構造です。コンパイラは、関数と同じようにデータ構造については賢くありません。もう 1 つはループです。コンパイラはループに対していくつかの最適化を行うことができますが、制限があります。
  
  
• 00:20:00 この YouTube ビデオでは、コンパイラが単純な操作を使用してより複雑な操作を置き換える方法について説明しています。たとえば、除算演算を置き換えるために、コンパイラはマジック ナンバーを乗算し、結果をシフトできます。このビデオでは、住所計算機の仕組みについても説明しています。
  
  
• 00:25:00 ビデオでは、単純な「vex スケール」関数を例として使用して、コンパイラがコードを最適化する方法について説明しています。コードは最初は最適化なしで示され、次にさまざまな最適化が適用されています。示されている最適化には、命令数の削減、ベクトル命令の使用、およびマジック ナンバーの使用が含まれます。
  
  
• 00:30:00 このビデオでは、コンパイラが不要なメモリ操作を排除してコードを最適化する方法について説明しています。特に、値をメモリに格納する必要をなくすことで、コンパイラが 2 つのスカラー値を乗算する関数を最適化する方法を示します。最後に、構造体をメモリに格納する必要をなくすことで、構造体を操作する関数をコンパイラが最適化する方法を示します。
  
  
• 00:35:00 この YouTube ビデオでは、不要なストレージとメモリの参照を削除することで、コンパイラがコードを最適化する方法について講演者が説明しています。彼は、複数のフィールドを持つ構造体の例を使用して、アドレス計算に含まれる数学を注意深く分析することにより、コンパイラーがコードを最適化する方法を示しています。各命令の動作を理解することで、コンパイラはコードを最適化し、不要な操作を削除できます。
  
  
• 00:40:00 コンパイラは、データ構造とスカラー値を変換して、可能な限り純粋にレジスタ内に格納し、可能であればローカル ストレージの使用を避けるように懸命に取り組んでいます。関数呼び出しの場合、コンパイラは呼び出し命令と呼び出される関数のコードを確認します。次に、上記のコードの関数をさらに高速化しようとします。
  
  
• 00:45:00 コンパイラは、コードをインライン化して関数呼び出しのオーバーヘッドを回避できます。また、不要な操作を削除してコードを最適化することもできます。
  
  
• 00:50:00 この YouTube ビデオでは、スピーカーは、コンパイラが関数をインライン展開しない主な理由が 3 つあることを説明しています。関数が再帰的である場合、関数が別のコンパイル単位にある場合、または関数が増加する可能性がある場合です。コードサイズとパフォーマンスの低下。また、スピーカーは、独自のプログラムで関数のインライン展開を制御するためのヒントも提供します。
  
  
• 00:55:00 このビデオでは、コンパイラがループを最適化してプログラムをより高速に実行する方法について説明しています。コード巻き上げ、またはループ不変コード モーションは、パフォーマンスを向上させるために使用できる最適化の 1 つです。
  
  
• 01:00:00 コンパイラは一連の変換パスを実行することでコードを最適化できます。これらのパスは、同一の住所計算などのプロパティを見つけて、より効率的なコードに置き換えるように設計されています。
  
  
• 01:05:00 コンパイラーは、'x' と 'y' のアドレスが重複しているかどうかを認識していないにもかかわらず、このループをベクトル化できます。これは、コンパイルされたコードの構造が、入力として与えられた 2 行の関数よりも複雑であるためです。
  
  
• 01:10:00 この YouTube ビデオでは、コンパイラでできることとできないことを説明しています。コードにループが含まれていない場合、コンパイラーはコードをベクトル化できます。ただし、コードにループが含まれている場合、コンパイラーはループがベクトル演算でいっぱいである場合にのみコードをベクトル化できます。ループがベクトル演算でいっぱいでない場合、コンパイラーはコードをベクトル化できません。
  
  
• 01:15:00 コンパイラがコードをベクトル化できるかどうかという問題は、多くの要因に依存するため、難しい問題です。特に、コンパイラは、2 つのポインターがエイリアスになるかどうかを判断できる必要がありますが、これは難しい作業になる可能性があります。プログラマーは、ポインターに注釈を付けてその使用法に関する詳細情報を提供することで、コンパイラーを支援できます。

[MetaQuotes]

講義 10. 測定とタイミング

講義 10. 測定とタイミング

このビデオでは、スピーカーは、精度に影響を与える可能性のある外部要因を含め、コンピューティングにおける測定とタイミングのさまざまな側面について説明します。モデルの必要性とデータの明確な理解を強調し、差異を減らして誤差を補正し、適切なタイミング コールを使用して信頼性を確保します。また、パフォーマンス モデリング、タイミング コール、ハードウェア カウンター、シミュレーターなどのツールを強調しながら、べき乗則や非決定論的要因など、ソフトウェア パフォーマンスを正確に測定する際の課題についても説明します。最後に、彼らは単一のツールに依存しないように警告し、正確な結果を保証するための手法として三角測量と適応を推奨しています。

講演者は、パフォーマンス ソフトウェア エンジニアリングにおける信頼性の高いパフォーマンス測定の重要性について説明します。彼は、パフォーマンスを正確に測定するために統計を使用することを推奨し、さまざまなコンテキストでパフォーマンスの有用な尺度を提供できる、平均などのさまざまな種類の要約統計について説明しています。彼は、比率の算術平均を取ることは有効なアプローチではないと指摘し、代わりに幾何平均を使用することを提案しています。スピーカーは、プログラムを比較するときにデータを集計する正しい方法を選択することの重要性を強調し、パフォーマンスをより正確に比較するために、複数の実行から最小または 10% などの低次の統計を取得することを提案します。スピーカーは、直接比較や統計を導出するためのモデルのフィッティングなど、パフォーマンスの測定と比較のためのさまざまな方法論についても説明しますが、モデリングにおけるオーバーフィッティングの問題について警告します。全体として、このビデオは、プログラムのパフォーマンスを改善するための信頼できるパフォーマンス測定の重要性を強調しています。

• 00:00:00 このセクションでは、スピーカーは、以前の学生の 1 人が行ったコードの並べ替えに関する研究について説明します。このコードは、time.h ヘッダー ファイルを使用して、タイミング測定用のクロック取得時刻ルーチンにアクセスします。ソート ルーチンの時間が計測され、経過時間が計算されて出力されます。測定された実行時間のグラフは、並べ替えルーチンがほとんど N log N の増加に従うことを示していますが、測定された時間は、最大の配列の場合でも遅いです。
  
  
• 00:05:00 このセクションでは、観察されるデータのモデルを持つことの重要性について教授が説明します。彼は、測定データが予想されたものから大幅に逸脱している例を提示し、学生にこの逸脱について考えられる仮説を提案するよう求めています。キャッシュやタイミングの精度に問題があるのではないかと考える人もいましたが、教授は、マシン上で実行されている無関係なプロセスが偏差を引き起こしている可能性があると指摘しています。この場合、問題はマルチテナンシーにあり、マシンが複数のプロセスによって同時に使用されています。教授は、品質測定の必要性と、データが何を意味するかを明確に理解する必要性を強調しています。
  
  
• 00:10:00 このセクションでは、スピーカーはコンピューティングにおける測定とタイミング、および外部要因が測定の精度にどのように影響するかについて説明します。特に、システムの温度と省電力技術によってクロック周波数がどのように変化するかに焦点を当てています。これは、測定結果に大きな影響を与える可能性があります。スピーカーは、トランジスタへのクロック周波数と電圧を調整することによって電力を削減する技術である動的周波数および電圧スケーリングの概念を導入しています。彼らは、不正確な結果を避けるために、測定を行う際に外的要因を考慮することが重要であることを強調しています。
  
  
• 00:15:00 このセクションでは、スピーカーは、電気エンジニアが使用するべき法則によるソフトウェア パフォーマンスの測定の課題について説明します。べき法則は、電力が CV の 2 乗 F に等しいと述べています。ここで、C は動的容量、V は電源電圧、F はクロック周波数です。電力と熱を減らすには、周波数と電圧を下げると、電力が 3 倍減少します。これは、ソフトウェアのパフォーマンスを確実に測定するための課題であり、講演者は、正確な測定を行うために、ノイズの一部を取り除くことでシステムを休止することを提案しています。また、パフォーマンス モデリングなど、ソフトウェア パフォーマンスを測定するためのツールについても説明します。
  
  
• 00:20:00 このセクションでは、スピーカーは、特にパフォーマンス エンジニアリングのコンテキストにおいて、測定とタイミングに関して分散を減らすことの重要性について説明します。変動性を減らすことにより、系統的およびランダムな測定誤差を補正し、プログラムを比較するための試行回数を減らすことができます。講演者はまた、バックグラウンド ジョブ、割り込み、スレッド配置など、コンピューター システムの変動性のさまざまな原因についても指摘しています。最後に、彼は、システムに変更を加える前にまず分散を減らすことに集中することの重要性を強調しています。分散が大きいときに測定すると、信頼できない結果が生じる可能性があるからです。
  
  
• 00:25:00 このセクションでは、スピーカーはプロセッサのハイパースレッディングの概念と、それがクラウド システムでの不正確な測定にどのようにつながるかについて話します。ハイパースレッディングは、1 つの機能ユニットを介して 2 つの命令ストリームを実行し、2 つのプロセッサのように見えますが、実際には 2 つの別個のプロセッサではなく 20% の速度向上しか提供しません。講演者は、ターボ ブーストやシステムの休止など、測定結果に大きな影響を与える可能性がある他の手法についても説明します。ハイパー スレッディングとターボ ブーストをオフにし、すべての悪魔を静止させることで、スピーカーと彼のグループは、最小実行時間よりも 1% も遅くない、非常に信頼性の高い測定値を達成することができました。
  
  
• 00:30:00 このセクションでは、スピーカーは、最新のハードウェアで実行されるプログラムの決定論に影響を与える可能性のあるさまざまな要因について話します。プログラムをより決定論的にするために実行できる特定の手段はありますが、非決定論的な要因を完全に排除することは不可能です。キャッシング、割り込み、スレッド化、分岐予測など、プログラムの実行中に発生する可能性がある非決定論的要因のほとんどは、決定論的プロセスです。ただし、ハードウェアのランダム性はユーザーが制御できないため、メモリ エラーが発生する可能性があります。スピーカーは、コードのアライメントがプログラムの決定性に違いをもたらす可能性があり、コードに加えられた変更がキャッシュのアライメントにシフトを引き起こし、プログラムの決定性に影響を与える可能性があることを示唆しています。
  
  
• 00:35:00 このセクションでは、小さな変更がプログラムのパフォーマンスに大きな影響を与える可能性があることについてスピーカーが説明します。たとえば、1 バイトを挿入すると、それ以降のすべてが直線的に影響を受ける可能性があり、リンカー コマンド ラインでドット o ファイルが表示される順序を変更すると、-OH- と -O3 の間を移動するよりも大きな効果が得られます。これらの問題に対処するために、コンパイラは問題を認識し、より多くのアライメントを行っています。 LLVM には、関数内のすべての関数とブロックを整列できるスイッチがありますが、整列するとプログラムの速度が低下する可能性があります。さらに、プログラムの名前は、実行可能ファイルの名前がコール スタックで終わる環境変数で終わるため、その速度に影響を与える可能性があります。
  
  
• 00:40:00 このセクションでは、スピーカーはソフトウェア パフォーマンスを測定するためのさまざまなツールと方法について説明します。これには、time コマンドを使用して外部からプログラムを測定すること、clock get time またはその他の方法を使用してタイミング呼び出しをプログラムに入れること、gdb を使用してプログラムを中断することが含まれます。 perf ツールセットで使用されるようなハードウェアと OS のサポートを活用するか、プログラムをシミュレートして、より遅い速度でより深い理解を得るために、どのルーチンが最も時間がかかっているかを特定します。講演者は、time コマンドを使用した場合の経過時間、ユーザー時間、およびシステム時間の違いと、プロセッサの割り当てにより合計時間がどのように加算されないかについて説明します。
  
  
• 00:45:00 このセクションでは、スピーカーは、ウォール クロック時間、ユーザー モードで費やされたプロセッサ時間、カーネルで費やされた時間など、さまざまな種類のタイミングと測定について説明します。使用が推奨されるタイミング コールは、決して逆方向に実行されないことを保証する clock monotonic オプションを使用した clock get time です。実行には非決定的な時間がかかる場合がありますが、異なるコアで異なる応答を返し、逆方向に実行される可能性がある RTIDTSC などの他のタイマーよりも信頼性が高くなります。スピーカーは、get time of day を使用しないように警告します。
  
  
• 00:50:00 このセクションでは、スピーカーは、clock_gettime の使用や time コマンドでの測定など、プログラミングでイベントを測定および時間計測するさまざまな方法について説明します。彼らは、時間の経過とともに技術が変化する可能性があり、エンジニアが適応する必要があるかもしれないと警告しています.講演者はまた、単純なプロファイリング手法としてランダムな瞬間にコードを中断することを提案し、Facebook などの大企業がこの方法を使用していると述べています。さらに、スピーカーは、ハードウェア カウンターとライブラリ livepFM4 のアイデアを紹介します。これにより、プロセスごとにこれらのカウンターにアクセスできます。彼らは、技術者が常に外科的に正確なツールを必要とするわけではなく、単純なツールで十分な場合があることを強調しています.
  
  
• 00:55:00 このセクションでは、スピーカーは、ハードウェア カウンターやシミュレーターなど、測定値を収集するさまざまな方法について説明します。彼らは、多くのハードウェア カウンターが十分に文書化されておらず、一部のツールでは、4 つまたは 5 つを超えるカウンターが使用されている場合に帯域幅を時分割で共有していることに注意しています。シミュレーターは再現性が高く評価されていますが、キャッシュ内のすべてをモデル化できるわけではありません。講演者は、三角測量と、精度を確保するために少なくとも 2 つの測定値を使用することを推奨しています。彼らはまた、データ解釈の指針となるパフォーマンス モデルを持つことの重要性を強調しています。
  
  
• 01:00:00 このセクションでは、スピーカーはパフォーマンス ソフトウェア エンジニアリングのプロセスを説明します。これには、プログラムを取得して変更を加え、そのパフォーマンスを測定してより高速なプログラムを作成することが含まれます。ただし、小さな変更を加えて結果を正確に導き出すには、信頼できるパフォーマンス測定が不可欠です。したがって、講演者は、何が起こっているかを正確に把握するために統計を使用することを推奨しています。彼はまた、決定論的プログラムの生のパフォーマンスを測定するパズルを提示し、最小値を使用することがノイズを排除し、プログラムの基礎となるハードウェア パフォーマンスを決定する最良の方法であると結論付けています。
  
  
• 01:05:00 このセクションでは、平均を含むさまざまなタイプの要約統計について説明します。これは、さまざまなコンテキストでのパフォーマンスの有用な尺度を提供できます。 Web サーバーを評価する場合、CPU 使用率と合計タスク完了時間は算術平均を使用して測定できますが、実時間とパーセンタイル動作は、要求の満足度を最適化するためにより関連する場合があります。ただし、プログラム A と B のパフォーマンスを比較するなど、比率を要約する場合、算術平均を取ることは有効な方法ではありません。これは、ビデオに示されている例に示されているように、比率の平均が比率自体と同じではないためです。
  
  
• 01:10:00 このセクションでは、スピーカーは、パフォーマンスを測定する際の比率と平均の比較に関する問題について説明します。彼らは、比率の算術平均を取ると疑わしい結果が生じる可能性があることを示しており、幾何平均を使用する方が適切です。さらに、レートを比較する場合、調和平均が役立つことが多いと指摘しています。プログラムを比較するときにデータを集計する正しい方法を選択することの重要性が強調され、講演者はパフォーマンスをより正確に比較するために、複数の実行から最小または 10% などの低次の統計を取得することを提案します。
  
  
• 01:15:00 このセクションでは、スピーカーはパフォーマンスを測定および比較するためのさまざまな方法について説明します。決定的な証拠にはならないかもしれませんが、1 つのアプローチは、10% の最も安いオプションを比較し、平均を比較するためにノイズ削減を行うことです。または、A と B の間で直接比較を行って、どちらがより頻繁に勝つかを確認することもできます。これにより、帰無仮説を検定し、p 値を計算して偏差が有意かどうかを判断できます。この方法は社会科学で一般的に使用されており、騒がしい環境で役立ちます。最後に、スピーカーはモデルをフィッティングして統計を導出するという考え方に簡単に触れ、最小二乗近似の使用について説明します。
  
  
• 01:20:00 このセクションでは、モデリングにおける過適合の問題と、基底関数を追加するとデータの適合性が向上するだけでなく、過適合につながることについても説明します。解決策は、基底関数を削除し、それがモデルの品質に影響するかどうかを確認することです。講演者はまた、測定のグルとして知られるケルビン卿についても言及しています。彼は、測定することは知ることであり、測定できなければ改善することはできないと述べました。ビデオは、スピーカーが火曜日のクイズで幸運を祈ることで締めくくられます。