Parallel-computer-architecture-quick-guide

並列コンピューターアーキテクチャ-はじめに

過去50年間で、コンピューターシステムのパフォーマンスと機能は大きく発展しました。 これは、VLSI（Very Large Scale Integration）テクノロジーのおかげで可能になりました。 VLSIテクノロジーにより、多数のコンポーネントを1つのチップに収容し、クロックレートを上げることができます。 したがって、一度により多くの操作を並行して実行できます。

並列処理は、データの局所性とデータ通信にも関連付けられています。 Parallel Computer Architecture は、すべてのリソースを整理して、テクノロジーとコストによって与えられる制限内でパフォーマンスとプログラマビリティを最大化する方法です。

なぜ並列アーキテクチャなのか？

並列コンピューターアーキテクチャは、より多くのプロセッサを使用することにより、コンピューターシステムの開発に新しい次元を追加します。 原則として、多数のプロセッサを使用することで達成されるパフォーマンスは、特定の時点での単一のプロセッサのパフォーマンスよりも高くなります。

アプリケーショントレンド

ハードウェア容量の進歩に伴い、パフォーマンスの高いアプリケーションの需要も増加し、コンピューターアーキテクチャの開発が要求されました。

マイクロプロセッサ時代以前は、エキゾチックな回路技術と機械構成により高性能なコンピューターシステムが得られ、高価になりました。 現在、複数のプロセッサを使用することで高性能のコンピューターシステムが得られ、最も重要で要求の厳しいアプリケーションは並列プログラムとして記述されています。 したがって、パフォーマンスを向上させるには、並列アーキテクチャと並列アプリケーションの両方を開発する必要があります。

アプリケーションのパフォーマンスを向上させるには、スピードアップが考慮される重要な要素です。 pプロセッサの*スピードアップ*は次のように定義されます-

単一の修正された問題の場合、

科学技術計算

並列アーキテクチャは、科学計算（物理学、化学、生物学、天文学など）およびエンジニアリングアプリケーション（リザーバーモデリング、気流解析、燃焼効率など）に不可欠になっています。 ほとんどすべてのアプリケーションで、計算出力の視覚化に対する大きな需要があり、その結果、計算速度を向上させるための並列計算の開発が求められています。

商用コンピューティング

商用コンピューティング（ビデオ、グラフィック、データベース、OLTPなど）では、指定された時間内に大量のデータを処理するために高速コンピューターも必要です。 デスクトップは、並列プログラムとほぼ同じマルチスレッドプログラムを使用します。 これは、並列アーキテクチャの開発を要求します。

技術動向

テクノロジーとアーキテクチャの開発に伴い、高性能アプリケーションの開発に対する強い需要があります。 実験により、並列コンピューターは、開発された最大限の単一プロセッサーよりもはるかに高速に動作できることが示されています。 さらに、並列コンピューターは、技術とコストの制限内で開発できます。

ここで使用される主な技術はVLSI技術です。 したがって、現在では、同じエリアにトランジスタ、ゲート、および回路をより多く取り付けることができます。 基本的なVLSIフィーチャサイズの縮小により、それに比例してクロックレートも向上しますが、トランジスタの数は正方形として増加します。 一度に多くのトランジスタを使用すると（並列性）、クロックレートを上げるよりもはるかに優れたパフォーマンスが期待できます。

技術動向は、基本的なシングルチップビルディングブロックがますます大きな容量を提供することを示唆しています。 したがって、単一のチップに複数のプロセッサを配置する可能性が高まります。

建築トレンド

テクノロジーの開発により、何が実現可能かが決まります。アーキテクチャは、テクノロジーの可能性をパフォーマンスと機能に変換します。 *平行度*と*局所性*は、より多くのリソースとより多くのトランジスタがパフォーマンスを向上させる2つの方法です。 ただし、これら2つの方法は同じリソースを求めて競合します。 複数の操作が並行して実行されると、プログラムの実行に必要なサイクル数が削減されます。

ただし、各同時アクティビティをサポートするにはリソースが必要です。 ローカルストレージを割り当てるにはリソースも必要です。 最高のパフォーマンスは、リソースを使用してある程度の並列性とある程度の局所性を利用する中間アクションプランによって達成されます。

一般的に、コンピュータアーキテクチャの歴史は、次の基本的な技術を持つ4つの世代に分けられています-

• 真空管
• トランジスター
• 集積回路
• VLSI

1985年までは、ビットレベルの並列処理の増加がその期間の大半を占めていました。 4ビットのマイクロプロセッサと、それに続く8ビット、16ビットなど。 完全な32ビット操作の実行に必要なサイクル数を減らすために、データパスの幅が2倍になりました。 後に、64ビット操作が導入されました。

• 命令レベルの並列処理*の成長は、80年代半ばから90年代半ばを支配しました。 RISCアプローチは、命令処理のステップをパイプライン処理するのが簡単で、平均してほぼすべてのサイクルで命令が実行されることを示しました。 コンパイラ技術の成長により、命令パイプラインの生産性が向上しました。

80年代半ば、マイクロプロセッサベースのコンピューターは

• 整数処理ユニット
• 浮動小数点ユニット
• キャッシュコントローラー
• キャッシュデータ用のSRAM
• タグストレージ

チップの容量が増加すると、これらのコンポーネントはすべて単一のチップに統合されました。 したがって、単一のチップは、整数演算、浮動小数点演算、メモリ演算、および分岐演算用の個別のハードウェアで構成されていました。 個々の命令をパイプライン処理する以外に、一度に複数の命令をフェッチし、可能な場合は常に異なる機能ユニットに並列に送信します。 このタイプの命令レベルの並列処理は、*スーパースカラー実行*と呼ばれます。

並列アーキテクチャの収束

並列マシンは、いくつかの異なるアーキテクチャで開発されています。 このセクションでは、異なる並列コンピュータアーキテクチャとそれらの収束の性質について説明します。

通信アーキテクチャ

並列アーキテクチャは、通信アーキテクチャを使用して、コンピュータアーキテクチャの従来の概念を強化します。 コンピュータアーキテクチャは、重要な抽象化（ユーザーシステムの境界やハードウェアとソフトウェアの境界など）および組織構造を定義し、通信アーキテクチャは基本的な通信および同期操作を定義します。 また、組織構造にも対応しています。

抽象化の層

プログラミングモデルは最上層です。 アプリケーションはプログラミングモデルで記述されています。 並列プログラミングモデルには以下が含まれます-

• 共有アドレス空間
• メッセージパッシング
• データ並列プログラミング

• 共有アドレス*プログラミングは、掲示板を使用するようなもので、特定の場所に情報を投稿することにより、1人または複数の個人と通信できます。 個々のアクティビティは、誰がどのタスクを実行しているかを記録することで調整されます。

• メッセージの受け渡し*は、特定の受信者が特定の送信者から情報を受信する電話や手紙のようなものです。

• データ並列*プログラミングは、組織化された形の協力です。 ここでは、複数の個人がデータセットの個別の要素に対して同時にアクションを実行し、情報をグローバルに共有しています。

共有メモリ

共有メモリマルチプロセッサは、並列マシンの最も重要なクラスの1つです。 マルチプログラミングワークロードのスループットが向上し、並列プログラムがサポートされます。

共有メモリマルチプロセッサ

この場合、すべてのコンピューターシステムでは、プロセッサと一連のI/Oコントローラーがハードウェアの相互接続によってメモリモジュールのコレクションにアクセスできます。 メモリモジュールを追加するとメモリ容量が増加し、I/Oコントローラにデバイスを追加するか、I/Oコントローラを追加するとI/O容量が増加します。 より高速なプロセッサーが使用可能になるのを待つか、プロセッサーを追加することにより、処理能力を増やすことができます。

すべてのリソースは、中央のメモリバスを中心に編成されています。 バスアクセスメカニズムにより、すべてのプロセッサがシステム内の物理アドレスにアクセスできます。 すべてのプロセッサはすべてのメモリロケーションから等距離にあるため、すべてのプロセッサのアクセス時間またはレイテンシはメモリロケーションで同じです。 これは*対称型マルチプロセッサ*と呼ばれます。

メッセージ受け渡しアーキテクチャ

メッセージパッシングアーキテクチャは、並列マシンの重要なクラスでもあります。 明示的なI/O操作としてプロセッサ間の通信を提供します。 この場合、通信はメモリシステムではなく、I/Oレベルで結合されます。

メッセージパッシングアーキテクチャでは、実際の通信操作を含む、多くの低レベルのアクションを実行するオペレーティングシステムまたはライブラリ呼び出しを使用して実行されるユーザー通信。 その結果、物理ハードウェアレベルでのプログラミングモデルと通信操作の間には距離があります。

送信*および*受信*は、メッセージパッシングシステムで最も一般的なユーザーレベルの通信操作です。 送信は、ローカルデータバッファ（送信される）と受信リモートプロセッサを指定します。 Receiveは、送信プロセスと、送信データが配置されるローカルデータバッファーを指定します。 送信操作では、 *identifier または tag がメッセージに添付され、受信操作は特定のプロセッサからの特定のタグまたは任意のプロセッサからのタグなどの一致ルールを指定します。

送信と一致する受信の組み合わせにより、メモリ間のコピーが完了します。 各エンドは、ローカルデータアドレスとペアごとの同期イベントを指定します。

収束

ハードウェアとソフトウェアの開発により、共有メモリとメッセージパッシングキャンプの明確な境界が薄れています。 メッセージパッシングと共有アドレススペースは、2つの異なるプログラミングモデルを表します。それぞれが、共有、同期、通信のための透過的なパラダイムを提供します。 ただし、基本的なマシン構造は、共通の組織に収束しています。

データ並列処理

並列マシンのもう1つの重要なクラスは、プロセッサアレイ、データ並列アーキテクチャ、および単一命令複数データマシンと呼ばれています。 プログラミングモデルの主な特徴は、大規模な通常のデータ構造（配列や行列など）の各要素で操作を並列に実行できることです。

データ並列プログラミング言語は通常、プロセッサごとに1つのプロセスグループのローカルアドレス空間を表示して、明示的なグローバル空間を形成することにより実施されます。 すべてのプロセッサが相互に通信し、すべての操作のグローバルビューがあるため、共有アドレススペースまたはメッセージパッシングを使用できます。

基本的な設計の問題

プログラミングモデルの開発では、コンピューターの効率を高めることはできず、ハードウェアの開発だけでそれを行うこともできません。 ただし、コンピューターアーキテクチャの開発により、コンピューターのパフォーマンスに違いが生じる可能性があります。 プログラムがマシンをどのように使用し、どの基本技術が提供されるかに焦点を当てることで、設計上の問題を理解できます。

このセクションでは、通信の抽象化とプログラミングモデルの基本要件について説明します。

コミュニケーションの抽象化

通信の抽象化は、プログラミングモデルとシステム実装の間の主要なインターフェイスです。 これは、多くの実装で同じプログラムを正しく実行できるプラットフォームを提供する命令セットのようなものです。 このレベルでの操作は単純でなければなりません。

通信の抽象化は、ハードウェアとソフトウェアの間の契約のようなもので、作業に影響を与えることなく柔軟性を向上させることができます。

プログラミングモデルの要件

並列プログラムには、データで動作する1つ以上のスレッドがあります。 並列プログラミングモデルは、スレッドが name できるデータ、名前付きデータに対して実行できる operations 、および操作が続く順序を定義します。

プログラム間の依存関係が適用されていることを確認するには、並列プログラムがそのスレッドのアクティビティを調整する必要があります。

並列コンピューターアーキテクチャ-モデル

並列処理は、実際のアプリケーションでの高性能、低コスト、および正確な結果の要求を満たすために、現代のコンピューターの効果的なテクノロジーとして開発されました。 同時イベントは、マルチプログラミング、マルチプロセッシング、またはマルチコンピューティングの実践により、今日のコンピューターでは一般的です。

最新のコンピューターには、強力で広範なソフトウェアパッケージがあります。 コンピューターのパフォーマンスの開発を分析するには、最初にハードウェアとソフトウェアの基本的な開発を理解する必要があります。

• コンピューター開発のマイルストーン-コンピューターの開発には、*機械*または*電気機械*の2つの主要な段階があります。 現代のコンピューターは、電子部品の導入後に進化しました。 電子計算機の高移動度電子は、機械計算機の動作部品に取って代わりました。 情報伝送では、ほぼ光の速度で進む電気信号が機械式ギアまたはレバーに取って代わりました。
• 現代のコンピューターの要素-現代のコンピューターシステムは、コンピューターハードウェア、命令セット、アプリケーションプログラム、システムソフトウェア、ユーザーインターフェイスで構成されています。

現代のコンピューターシステムの要素

計算の問題は、数値計算、論理的推論、およびトランザクション処理に分類されます。 一部の複雑な問題では、3つの処理モードすべての組み合わせが必要になる場合があります。

• コンピュータアーキテクチャの進化-過去40年間で、コンピュータアーキテクチャは革命的な変化を遂げました。 Von Neumannアーキテクチャから始めて、今ではマルチコンピューターとマルチプロセッサーを持っています。
• コンピューターシステムのパフォーマンス-コンピューターシステムのパフォーマンスは、マシンの機能とプログラムの動作の両方に依存します。 優れたハードウェア技術、高度なアーキテクチャ機能、効率的なリソース管理により、マシンの機能を改善できます。 プログラムの動作は、アプリケーションや実行時の条件に依存するため予測不可能です

マルチプロセッサとマルチコンピューター

このセクションでは、2種類の並列コンピューターについて説明します-

• マルチプロセッサ
• マルチコンピューター

共有メモリマルチコンピューター

3つの最も一般的な共有メモリマルチプロセッサモデルは次のとおりです-

Uniform Memory Access（UMA）

このモデルでは、すべてのプロセッサが物理メモリを均一に共有します。 すべてのプロセッサは、すべてのメモリワードへのアクセス時間が等しくなっています。 各プロセッサにはプライベートキャッシュメモリがあります。 周辺機器についても同じルールに従います。

すべてのプロセッサがすべての周辺機器に同等にアクセスできる場合、システムは*対称型マルチプロセッサ*と呼ばれます。 周辺機器にアクセスできるプロセッサが1つまたは少数の場合、システムは「非対称マルチプロセッサ」と呼ばれます。

UMAマルチプロセッサ

不均一メモリアクセス（NUMA）

NUMAマルチプロセッサモデルでは、アクセス時間はメモリワードの場所によって異なります。 ここでは、共有メモリはローカルメモリと呼ばれるすべてのプロセッサに物理的に分散されています。 すべてのローカルメモリのコレクションは、すべてのプロセッサがアクセスできるグローバルアドレス空間を形成します。

マルチプロセッサシステムのNUMAモデル

キャッシュオンリーメモリアーキテクチャ（COMA）

COMAモデルは、NUMAモデルの特殊なケースです。 ここでは、すべての分散メインメモリがキャッシュメモリに変換されます。

マルチプロセッサのCOMAモデル

• 分散-メモリマルチコンピューター-分散メモリマルチコンピューターシステムは、メッセージパッシングネットワークによって相互接続されたノードと呼ばれる複数のコンピューターで構成されます。 各ノードは、プロセッサ、ローカルメモリ、および場合によってはI/Oデバイスを備えた自律型コンピュータとして機能します。 この場合、すべてのローカルメモリはプライベートであり、ローカルプロセッサのみがアクセスできます。 これが、従来のマシンが* no-remote-memory-access（NORMA）*マシンと呼ばれる理由です。

メッセージパッシングマルチプロセッサの一般的なモデル

マルチベクターおよびSIMDコンピューター

このセクションでは、ベクトル処理とデータ並列処理のためのスーパーコンピューターと並列プロセッサーについて説明します。

ベクトルスーパーコンピューター

ベクトルコンピューターでは、オプション機能としてベクトルプロセッサがスカラープロセッサに接続されます。 ホストコンピューターは、最初にプログラムとデータをメインメモリに読み込みます。 次に、スカラー制御ユニットがすべての命令をデコードします。 デコードされた命令がスカラー操作またはプログラム操作である場合、スカラープロセッサはスカラー機能パイプラインを使用してこれらの操作を実行します。

一方、デコードされた命令がベクトル演算である場合、命令はベクトル制御ユニットに送信されます。

ベクタースーパーコンピューターのアーキテクチャ

SIMDスーパーコンピューター

SIMDコンピューターでは、「N」個のプロセッサーが制御ユニットに接続され、すべてのプロセッサーに個別のメモリーユニットがあります。 すべてのプロセッサは相互接続ネットワークで接続されています。

SIMDコンピューターの運用モデル

PRAMおよびVLSIモデル

理想的なモデルは、物理的な制約や実装の詳細を考慮せずに並列アルゴリズムを開発するための適切なフレームワークを提供します。

モデルを実行して、並列コンピューターで理論的なパフォーマンスの限界を取得したり、チップを製造する前にチップ面積と動作時間でVLSIの複雑さを評価したりできます。

並列ランダムアクセスマシン

Sheperdson and Sturgis（1963）は、従来のユニプロセッサコンピューターをランダムアクセスマシン（RAM）としてモデル化しました。 Fortune and Wyllie（1978）は、メモリアクセスのオーバーヘッドと同期がゼロの理想的な並列コンピュータをモデル化するための並列ランダムアクセスマシン（PRAM）モデルを開発しました。

PRAMモデル

NプロセッサPRAMには共有メモリユニットがあります。 この共有メモリは、プロセッサ間で集中化または分散できます。 これらのプロセッサは、同期された読み取りメモリ、書き込みメモリ、および計算サイクルで動作します。 したがって、これらのモデルは、読み取りおよび書き込みの同時操作の処理方法を指定します。

可能なメモリ更新操作は次のとおりです-

• 排他的読み取り（ER）-この方法では、各サイクルで1つのプロセッサのみが任意のメモリ位置から読み取ることができます。
• 排他的書き込み（EW）-この方法では、少なくとも1つのプロセッサが一度にメモリ位置に書き込むことができます。
• 同時読み取り（CR）-複数のプロセッサが同じサイクルで同じメモリ位置から同じ情報を読み取ることができます。
• 同時書き込み（CW）-同じメモリ位置への同時書き込み操作が可能です。 書き込みの競合を避けるために、いくつかのポリシーが設定されています。

VLSI複雑度モデル

並列コンピュータはVLSIチップを使用して、プロセッサアレイ、メモリアレイ、および大規模なスイッチングネットワークを製造します。

現在、VLSIテクノロジーは2次元です。 VLSIチップのサイズは、そのチップで使用可能なストレージ（メモリ）スペースの量に比例します。

アルゴリズムのVLSIチップ実装のチップ面積（A）により、アルゴリズムの空間複雑度を計算できます。 Tがアルゴリズムの実行に必要な時間（レイテンシ）である場合、A.Tはチップ（またはI/O）で処理されるビットの総数の上限を示します。 特定のコンピューティングでは、下限f（s）が存在します。

A.T ^ 2 ^> = O（f（s））

ここで、A =チップ面積およびT =時間

建築開発トラック

私は次のトラックに沿って広がる並列コンピュータの進化-

• 複数のプロセッサトラック
• マルチプロセッサトラック
• マルチコンピュータートラック
• 複数のデータトラック
• ベクトルトラック
• SIMDトラック
• 複数のスレッドの追跡
• マルチスレッドトラック
• データフロートラック

• マルチプロセッサトラック*では、異なるスレッドが異なるプロセッサで同時に実行され、共有メモリ（マルチプロセッサトラック）またはメッセージパッシング（マルチコンピュータトラック）システムを介して通信することが想定されています。

• 複数のデータトラック*では、大量のデータに対して同じコードが実行されると想定されています。 これは、一連のデータ要素で同じ命令を実行する（ベクトルトラック）か、同様のデータセットで同じ命令を実行する（SIMDトラック）ことによって行われます。

• 複数スレッドトラック*では、異なるプロセッサで実行されるスレッド間の同期遅延を隠すために、同じプロセッサでさまざまなスレッドのインターリーブされた実行が想定されています。 スレッドインターリーブは、粗い（マルチスレッドトラック）または細かい（データフロートラック）にできます。

並列システムのプロセッサ

80年代には、 Transputer と呼ばれるマルチコンピューターを作成するために特別な目的のプロセッサーが普及しました。 トランスピュータは、1つのコアプロセッサ、小さなSRAMメモリ、DRAMメインメモリインターフェイス、および4つの通信チャネルで構成され、すべて1つのチップ上にありました。 並列コンピュータ通信を行うために、チャネルが接続されてトランスピュータのネットワークが形成されました。 しかし、計算能力が不足しているため、並列アプリケーションの増加する需要に応えることができませんでした。 この問題はRISCプロセッサの開発によって解決され、安価でもありました。

最新の並列コンピューターは、命令レベルの並列処理やデータレベルの並列処理など、いくつかのレベルで並列処理を使用するマイクロプロセッサーを使用しています。

高性能プロセッサー

RISCおよびRISCyプロセッサは、今日の並列コンピューター市場を支配しています。

従来のRISCの特徴は次のとおりです-

• アドレッシングモードがほとんどありません。
• 命令の形式は固定で、通常は32ビットまたは64ビットです。
• メモリからデータをロードして登録し、レジスタからメモリにデータを保存する専用のロード/ストア命令があります。
• 算術演算は常にレジスタに対して実行されます。
• パイプラインを使用します。

最近のマイクロプロセッサのほとんどはスーパースカラーです。 並列コンピューターでは、複数の命令パイプラインが使用されます。 したがって、スーパースカラープロセッサは、同時に複数の命令を実行できます。 スーパースカラープロセッサの有効性は、アプリケーションで使用可能な命令レベルの並列処理（ILP）の量に依存します。 パイプラインを埋めるために、ハードウェアレベルの命令はプログラムの順序とは異なる順序で実行されます。

最新のマイクロプロセッサの多くは、_super pipelining_アプローチを使用しています。 _super pipelining_では、クロック周波数を上げるために、パイプラインステージ内で行われる作業が削減され、パイプラインステージの数が増えます。

超大型命令語（VLIW）プロセッサー

これらは、水平マイクロプログラミングとスーパースカラー処理から派生しています。 VLIWプロセッサの命令は非常に大きいです。 単一の命令内の操作は並行して実行され、実行のために適切な機能ユニットに転送されます。 したがって、VLIW命令をフェッチした後、その操作はデコードされます。 次に、操作は、それらが並列に実行される機能ユニットにディスパッチされます。

ベクトルプロセッサ

ベクトルプロセッサは、汎用マイクロプロセッサに対するコプロセッサです。 ベクトルプロセッサは通常、レジスタ間またはメモリ間です。 ベクトル命令がフェッチおよびデコードされた後、オペランドベクトルの各要素に対して特定の操作が実行されますが、通常のプロセッサでは、ベクトル操作にはコード内のループ構造が必要です。 より効率的にするために、ベクトルプロセッサは複数のベクトル演算をチェーンします。つまり、1つのベクトル演算の結果がオペランドとして別のベクトル演算に転送されます。

キャッシング

キャッシュは、高性能マイクロプロセッサーの重要な要素です。 18か月ごとに、マイクロプロセッサの速度は2倍になりますが、メインメモリ用のDRAMチップはこの速度に対抗できません。 そのため、プロセッサとメモリ間の速度のギャップを埋めるためにキャッシュが導入されています。 キャッシュは、高速で小型のSRAMメモリです。 Translation Look-aside Buffers（TLB）キャッシュ、命令キャッシュ、データキャッシュなど、より多くのキャッシュが最新のプロセッサに適用されます。

直接マップされたキャッシュ

直接マップされたキャッシュでは、「モジュロ」関数を使用して、メインメモリ内のアドレスをキャッシュの場所に1対1でマッピングします。 同じキャッシュエントリに複数のメインメモリブロックをマップできるため、プロセッサは、キャッシュ内のデータブロックが実際に必要なデータブロックであるかどうかを判断できる必要があります。 この識別は、キャッシュブロックとともにタグを格納することによって行われます。

完全連想キャッシュ

完全連想マッピングにより、キャッシュ内の任意の場所にキャッシュブロックを配置できます。 いくつかの置換ポリシーを使用することにより、キャッシュはキャッシュブロックを格納するキャッシュエントリを決定します。 完全連想キャッシュには柔軟なマッピングがあり、キャッシュエントリの競合の数を最小限に抑えます。 完全連想の実装は高価なので、大規模に使用されることはありません。

セットアソシアティブキャッシュ

セット連想マッピングは、直接マッピングと完全連想マッピングの組み合わせです。 この場合、キャッシュエントリはキャッシュセットに分割されます。 直接マッピングと同様に、キャッシュ内のセットへのメモリブロックの固定マッピングがあります。 ただし、キャッシュセット内では、メモリブロックは完全に連想的にマッピングされます。

キャッシュ戦略

マッピングメカニズム以外に、キャッシュには、特定のイベントの場合に何をすべきかを指定する一連の戦略も必要です。 （セット）連想キャッシュの場合、キャッシュは、キャッシュに入る新しいブロックによって置き換えられるキャッシュブロックを決定する必要があります。

いくつかのよく知られている交換戦略は-

• 先入れ先出し（FIFO）
• 最長時間未使用（LRU）

マルチプロセッサとマルチコンピューター

この章では、マルチプロセッサとマルチコンピュータについて説明します。

マルチプロセッサシステムの相互接続

並列処理では、入出力および周辺機器、マルチプロセッサ、共有メモリ間の高速通信のために効率的なシステム相互接続を使用する必要があります。

階層バスシステム

階層バスシステムは、コンピューターのさまざまなシステムとサブシステム/コンポーネントを接続するバスの階層で構成されます。 各バスは、多数の信号線、制御線、および電力線で構成されています。 ローカルバス、バックプレーンバス、I/Oバスなどの異なるバスを使用して、異なる相互接続機能を実行します。

ローカルバスは、プリント基板に実装されているバスです。 バックプレーンバスは、機能的なボードを差し込むために多くのコネクタが使用されるプリント回路です。 入出力デバイスをコンピューターシステムに接続するバスは、I/Oバスと呼ばれます。

クロスバースイッチとマルチポートメモリ

スイッチドネットワークは、入力と出力の間の動的な相互接続を提供します。 小規模または中規模のシステムは、主にクロスバーネットワークを使用します。 遅延の問題を解決できれば、多段ネットワークをより大きなシステムに拡張できます。

クロスバースイッチとマルチポートメモリの両方の組織は、単一ステージのネットワークです。 単一ステージのネットワークを構築する方が安価ですが、特定の接続を確立するには複数のパスが必要になる場合があります。 多段ネットワークには、複数のスイッチボックスがあります。 これらのネットワークは、入力を出力に接続できる必要があります。

マルチステージおよび結合ネットワーク

多段ネットワークまたは多段相互接続ネットワークは、主にネットワークの一端にある処理要素と、他端にあるスイッチング要素によって接続されたメモリ要素で構成される高速コンピュータネットワークのクラスです。

これらのネットワークは、より大きなマルチプロセッサシステムを構築するために適用されます。 これには、Omega Network、Butterfly Networkなどが含まれます。

マルチコンピューター

マルチコンピューターは、分散メモリーMIMDアーキテクチャーです。 次の図は、マルチコンピューターの概念モデルを示しています-

マルチコンピューターの概念モデル

マルチコンピューターは、パケット交換方式を適用してデータを交換するメッセージパッシングマシンです。 ここでは、各プロセッサにはプライベートメモリがありますが、プロセッサは自身のローカルメモリにしかアクセスできないため、グローバルアドレス空間はありません。 そのため、通信は透過的ではありません。ここでは、プログラマはコードに通信プリミティブを明示的に配置する必要があります。

グローバルにアクセス可能なメモリがないことは、マルチコンピューターの欠点です。 これは、次の2つのスキームを使用して解決することができます-

• 仮想共有メモリ（VSM）
• 共有仮想メモリ（SVM）

これらのスキームでは、アプリケーションプログラマは、グローバルにアドレス可能な大きな共有メモリを想定しています。 必要に応じて、アプリケーションによって作成されたメモリ参照はメッセージパッシングパラダイムに変換されます。

仮想共有メモリ（VSM）

VSMはハードウェア実装です。 そのため、オペレーティングシステムの仮想メモリシステムは、VSMの上に透過的に実装されます。 そのため、オペレーティングシステムは、共有メモリを備えたマシンで実行されていると見なします。

共有仮想メモリ（SVM）

SVMは、プロセッサのメモリ管理ユニット（MMU）からのハードウェアサポートを備えたオペレーティングシステムレベルのソフトウェア実装です。 ここでは、共有の単位はオペレーティングシステムのメモリページです。

プロセッサが特定のメモリ位置をアドレス指定する場合、MMUはメモリアクセスに関連付けられたメモリページがローカルメモリにあるかどうかを判断します。 ページがメモリにない場合、通常のコンピューターシステムでは、オペレーティングシステムによってディスクからスワップインされます。 ただし、SVMでは、オペレーティングシステムはその特定のページを所有するリモートノードからページをフェッチします。

3世代のマルチコンピューター

このセクションでは、3世代のマルチコンピューターについて説明します。

過去のデザインの選択肢

プロセッサテクノロジを選択する際、マルチコンピュータの設計者は、ビルディングブロックとして低コストの中粒度プロセッサを選択します。 大部分の並列コンピューターは、標準の市販のマイクロプロセッサーで構築されています。 分散メモリは、スケーラビリティを制限する共有メモリを使用するのではなく、マルチコンピューター用に選択されました。 各プロセッサには独自のローカルメモリユニットがあります。

相互接続スキームの場合、マルチコンピューターには、アドレス交換ネットワークではなく、メッセージパッシング、ポイントツーポイントダイレクトネットワークがあります。 制御戦略として、マルチコンピューターの設計者は、非同期MIMD、MPMD、およびSMPD操作を選択します。 CaltechのCosmic Cube（1983年、Seitz）は、第一世代のマルチコンピューターの最初のものです。

現在および将来の開発

次世代コンピューターは、グローバルに共有された仮想メモリを使用して、中規模から細粒度のマルチコンピューターに進化しました。 第二世代のマルチコンピューターは現在も使用されています。 ただし、i386、i860などのより優れたプロセッサを使用する 第二世代のコンピューターはたくさん開発されました。

第3世代コンピューターは、VLSI実装ノードが使用される次世代コンピューターです。 各ノードには、14 MIPSプロセッサ、20 Mバイト/秒のルーティングチャネル、および16 KバイトのRAMが1つのチップに統合されています。

Intel Paragonシステム

以前は、すべての機能がホストに与えられていたため、同種のノードを使用してハイパーキューブマルチコンピューターを作成していました。 そのため、これによりI/O帯域幅が制限されました。 したがって、大規模な問題を効率的にまたは高いスループットで解決するために、これらのコンピューターは使用できませんでした。IntelParagon Systemは、この困難を克服するように設計されました。 ネットワーク環境でのマルチユーザーアクセスを備えたマルチサーバーをアプリケーションサーバーに変えました。

メッセージパッシングメカニズム

マルチコンピューターネットワークのメッセージパッシングメカニズムには、特別なハードウェアとソフトウェアのサポートが必要です。 このセクションでは、いくつかのスキームについて説明します。

メッセージルーティングスキーム

ストアアンドフォワードルーティングスキームを備えたマルチコンピューターでは、パケットは情報伝送の最小単位です。 ワームホールでルーティングされたネットワークでは、パケットはさらにフリットに分割されます。 パケット長はルーティングスキームとネットワーク実装によって決まりますが、フリットの長さはネットワークサイズの影響を受けます。

• ストアアンドフォワードルーティング*では、パケットは情報伝送の基本単位です。 この場合、各ノードはパケットバッファーを使用します。 パケットは、一連の中間ノードを介して送信元ノードから宛先ノードに送信されます。 遅延は、送信元と宛先の間の距離に直接比例します。

• ワームホールルーティング*では、送信元ノードから宛先ノードへの送信は一連のルーターを介して行われます。 同じパケットのすべてのフリットは、パイプライン方式で分離不可能なシーケンスで送信されます。 この場合、ヘッダーフリットのみがパケットの送信先を認識します。

デッドロックと仮想チャネル

仮想チャネルは、2つのノード間の論理リンクです。 ソースノードとレシーバノードのフリットバッファ、およびそれらの間の物理チャネルによって形成されます。 物理チャネルがペアに割り当てられると、1つのソースバッファが1つのレシーババッファとペアになり、仮想チャネルが形成されます。

すべてのチャネルがメッセージで占有されており、サイクル内のどのチャネルも解放されていない場合、デッドロック状態が発生します。 これを回避するには、デッドロック回避スキームに従う必要があります。

キャッシュの一貫性と同期

この章では、マルチキャッシュの不整合の問題に対処するためのキャッシュ一貫性プロトコルについて説明します。

キャッシュの一貫性の問題

マルチプロセッサシステムでは、隣接するレベル間またはメモリ階層の同じレベル内でデータの不整合が発生する場合があります。 たとえば、キャッシュとメインメモリに同じオブジェクトの一貫性のないコピーがある場合があります。

複数のプロセッサが並列に動作し、独立して複数のキャッシュが同じメモリブロックの異なるコピーを所有する可能性があるため、これにより*キャッシュの一貫性の問題*が発生します。 *キャッシュコヒーレンススキーム*は、キャッシュされたデータブロックごとに均一な状態を維持することにより、この問題を回避するのに役立ちます。

書き込み可能なデータの共有の不一致

Xを、2つのプロセッサP1とP2によって参照されている共有データの要素とします。 最初は、Xの3つのコピーに一貫性があります。 プロセッサP1が write-through policy を使用して新しいデータX1をキャッシュに書き込むと、同じコピーが共有メモリにすぐに書き込まれます。 この場合、キャッシュメモリとメインメモリ間で矛盾が発生します。 *ライトバックポリシー*が使用されている場合、キャッシュ内の変更されたデータが置換または無効化されると、メインメモリが更新されます。

一般的に、不整合の問題には3つの原因があります-

• 書き込み可能なデータの共有
• プロセス移行 *I/Oアクティビティ

スヌーピーバスプロトコル

スヌーピープロトコルは、バスベースのメモリシステムを通じて、キャッシュメモリと共有メモリ間のデータの一貫性を実現します。* Write-invalidate および *write-update ポリシーは、キャッシュの一貫性を維持するために使用されます。

ブロックXの一貫性のあるコピー

書き込み無効化操作

この場合、ローカルキャッシュメモリと共有メモリにデータ要素「X」の一貫したコピーを持つ3つのプロセッサP1、P2、およびP3があります（図-a）。 プロセッサP1は、 write-invalidate protocol を使用して、キャッシュメモリにX1を書き込みます。 したがって、他のすべてのコピーはバスを介して無効になります。 これは「I」で示されます（図-b）。 無効化されたブロックは dirty とも呼ばれます。 使用しないでください。 write-update protocol は、バスを介してすべてのキャッシュコピーを更新します。 *ライトバックキャッシュ*を使用すると、メモリコピーも更新されます（図-c）。

更新操作の書き込み

キャッシュイベントとアクション

次のイベントとアクションは、メモリアクセスおよび無効化コマンドの実行時に発生します-

• 読み取りミス-プロセッサがブロックを読み取りたいが、それがキャッシュにない場合、読み取りミスが発生します。 これにより、 bus-read 操作が開始されます。 ダーティコピーが存在しない場合、一貫性のあるコピーを持つメインメモリは、要求元のキャッシュメモリにコピーを提供します。 ダーティコピーがリモートキャッシュメモリに存在する場合、そのキャッシュはメインメモリを制限し、要求元のキャッシュメモリにコピーを送信します。 どちらの場合も、キャッシュコピーは読み取りミスの後に有効な状態になります。
• Write-hit -コピーがダーティまたは*予約済み*状態の場合、書き込みはローカルで行われ、新しい状態はダーティです。 新しい状態が有効な場合、write-invalidateコマンドがすべてのキャッシュにブロードキャストされ、それらのコピーが無効になります。 共有メモリへの書き込みが完了すると、最初の書き込み後に結果の状態が予約されます。
• Write-miss -プロセッサがローカルキャッシュメモリへの書き込みに失敗した場合、コピーはメインメモリまたはダーティブロックを備えたリモートキャッシュメモリから取得する必要があります。 これは、すべてのキャッシュコピーを無効にする read-invalidate コマンドを送信することで実行されます。 次に、ローカルコピーがダーティ状態で更新されます。
• Read-hit -状態の遷移を引き起こしたり、無効化にスヌーピーバスを使用したりすることなく、常にローカルキャッシュメモリで読み取りヒットが実行されます。
• ブロック置換-コピーが汚れている場合、ブロック置換方法によってメインメモリに書き戻されます。 ただし、コピーが有効または予約済みまたは無効な状態の場合、置換は行われません。

ディレクトリベースのプロトコル

マルチステージネットワークを使用して数百のプロセッサを備えた大規模なマルチプロセッサを構築するには、ネットワーク機能に合わせてスヌーピーキャッシュプロトコルを変更する必要があります。 ブロードキャストは多段ネットワークで実行するのに非常にコストがかかるため、整合性コマンドはブロックのコピーを保持するキャッシュにのみ送信されます。 これが、ネットワークに接続されたマルチプロセッサ用のディレクトリベースのプロトコルの開発の理由です。

ディレクトリベースのプロトコルシステムでは、共有されるデータはキャッシュ間の一貫性を維持する共通ディレクトリに配置されます。 ここで、ディレクトリはフィルターとして機能し、プロセッサはプライマリメモリからキャッシュメモリにエントリをロードする許可を求めます。 エントリが変更された場合、ディレクトリはそれを更新するか、そのエントリを持つ他のキャッシュを無効にします。

ハードウェア同期メカニズム

同期は、データ制御の代わりに、同じまたは異なるプロセッサに存在する通信プロセス間で情報が交換される特別な形式の通信です。

マルチプロセッサシステムは、ハードウェアメカニズムを使用して低レベルの同期操作を実装します。 ほとんどのマルチプロセッサには、メモリの読み取り、書き込み、読み取り-変更-書き込みなどのアトミック操作を課して同期プリミティブを実装するハードウェアメカニズムがあります。 アトミックメモリ操作以外に、プロセッサ間割り込みの一部は同期目的でも使用されます。

共有メモリマシンのキャッシュコヒーレンシ

プロセッサにローカルキャッシュメモリが含まれる場合、マルチプロセッサシステムではキャッシュの一貫性を維持することが問題になります。 このシステムでは、異なるキャッシュ間でデータの不整合が簡単に発生します。

主な関心分野は-

• 書き込み可能なデータの共有
• プロセス移行
• I/Oアクティビティ

書き込み可能なデータの共有

2つのプロセッサ（P1およびP2）のローカルキャッシュに同じデータ要素（X）があり、1つのプロセス（P1）がデータ要素（X）に書き込む場合、キャッシュはP1のライトスルーローカルキャッシュであるため、メインメモリは更新されました。 P2がデータ要素（X）を読み取ろうとすると、P2のキャッシュ内のデータ要素が古くなっているため、Xが見つかりません。

書き込み可能なデータの共有

プロセス移行

最初の段階では、P1のキャッシュにはデータ要素Xがありますが、P2には何もありません。 P2のプロセスは最初にXに書き込み、次にP1に移行します。 ここで、プロセスはデータ要素Xの読み取りを開始しますが、プロセッサP1に古いデータがあるため、プロセスはそれを読み取ることができません。 したがって、P1のプロセスはデータ要素Xに書き込み、その後P2に移行します。 移行後、P2のプロセスはデータ要素Xの読み取りを開始しますが、メインメモリで古いバージョンのXを検出します。

プロセスの移行

I/Oアクティビティ

図に示すように、2プロセッサマルチプロセッサアーキテクチャでは、I/Oデバイスがバスに追加されます。 最初は、両方のキャッシュにデータ要素Xが含まれています。 I/Oデバイスは新しい要素Xを受け取ると、新しい要素をメインメモリに直接保存します。 現在、P1またはP2（P1を想定）が要素Xを読み取ろうとすると、古いコピーが取得されます。 したがって、P1は要素Xに書き込みます。 現在、I/OデバイスがXを送信しようとすると、古いコピーが取得されます。

入力出力アクティビティ

Uniform Memory Access（UMA）

Uniform Memory Access（UMA）アーキテクチャは、共有メモリがシステム内のすべてのプロセッサで同じであることを意味します。 一般的に（ファイル）サーバーに使用されるUMAマシンのクラスは、いわゆる対称型マルチプロセッサ（SMP）です。 SMPでは、メモリ、ディスク、その他のI/Oデバイスなどのすべてのシステムリソース。 プロセッサは均一な方法でアクセスできます。

不均一メモリアクセス（NUMA）

NUMAアーキテクチャには、内部間接/共有ネットワークを持つ複数のSMPクラスターがあり、それらはスケーラブルなメッセージパッシングネットワークで接続されています。 したがって、NUMAアーキテクチャは、論理的に共有される物理的に分散されたメモリアーキテクチャです。

NUMAマシンでは、プロセッサのキャッシュコントローラーが、メモリ参照がSMPのメモリに対してローカルかリモートかを判断します。 リモートメモリアクセスの数を減らすために、NUMAアーキテクチャは通常、リモートデータをキャッシュできるキャッシュプロセッサを適用します。 ただし、キャッシュが関係する場合、キャッシュの一貫性を維持する必要があります。 したがって、これらのシステムはCC-NUMA（キャッシュコヒーレントNUMA）とも呼ばれます。

キャッシュオンリーメモリアーキテクチャ（COMA）

COMAマシンはNUMAマシンに似ていますが、COMAマシンのメインメモリがダイレクトマップまたはセットアソシエイティブキャッシュとして機能するという唯一の違いがあります。 データブロックは、アドレスに従ってDRAMキャッシュ内の場所にハッシュされます。 リモートでフェッチされたデータは、実際にはローカルのメインメモリに保存されます。 さらに、データブロックにはホームロケーションが固定されておらず、システム全体を自由に移動できます。

COMAアーキテクチャには、ほとんどの場合、階層的なメッセージパッシングネットワークがあります。 そのようなツリーのスイッチには、サブツリーとしてデータ要素を持つディレクトリが含まれます。 データにはホームロケーションがないため、明示的に検索する必要があります。 つまり、リモートアクセスでは、必要なデータをディレクトリで検索するために、ツリー内のスイッチに沿ってトラバースする必要があります。 そのため、ネットワーク内のスイッチが同じデータに対するサブツリーから複数の要求を受信した場合、それらをスイッチの親に送信される単一の要求に結合します。 要求されたデータが返されると、スイッチはそのサブツリーに複数のコピーを送信します。

COMA対CC-NUMA

COMAとCC-NUMAの違いは次のとおりです。

• COMAは、OSを必要とせずにデータの移行と複製を透過的にサポートするため、CC-NUMAよりも柔軟性が高い傾向があります。
• COMAマシンは、非標準のメモリ管理ハードウェアを必要とし、コヒーレンシプロトコルを実装するのが難しいため、構築が高価で複雑です。
• COMAのリモートアクセスは、データを見つけるためにツリーネットワークを走査する必要があるため、CC-NUMAのリモートアクセスよりも遅いことがよくあります。

ハードウェアソフトウェアのトレードオフ

ハードウェアコストを削減する方法は多数あります。 1つの方法は、通信アシストとネットワークを処理ノードにあまり緊密に統合せず、通信の待ち時間と占有率を増やすことです。

別の方法は、ハードウェアではなくソフトウェアで自動複製と一貫性を提供することです。 後者の方法は、メインメモリでレプリケーションと一貫性を提供し、さまざまな粒度で実行できます。 これにより、ノードおよび相互接続に既製の汎用部品を使用できるため、ハードウェアコストが最小限に抑えられます。 これは、プログラマーに良いパフォーマンスを達成するよう圧力をかけます。

緩和されたメモリ整合性モデル

共有アドレス空間のメモリ一貫性モデルは、同じ場所または異なる場所のメモリ操作が相互に実行しているように見える順序で制約を定義します。 実際、共有アドレス空間の命名モデルをサポートするシステム層には、プログラマーのインターフェース、ユーザーシステムのインターフェース、ハードウェアとソフトウェアのインターフェースを含むメモリ一貫性モデルが必要です。 その層と対話するソフトウェアは、独自のメモリ一貫性モデルを認識している必要があります。

システム仕様

アーキテクチャのシステム仕様は、メモリ操作の順序付けと並べ替え、およびそこから実際に得られるパフォーマンスの量を指定します。

以下は、プログラムの順序で緩和を使用するいくつかの仕様モデルです-

• * Write-to-Readプログラム順序の緩和*-このクラスのモデルにより、ハードウェアは、第1レベルのキャッシュメモリで見逃された書き込み操作のレイテンシを抑制することができます。 書き込みミスが書き込みバッファにあり、他のプロセッサから見えない場合、プロセッサはキャッシュメモリでヒットする読み取り、またはキャッシュメモリでミスする単一の読み取りを完了することができます。
• * Write-to-ReadおよびWrite-to-Writeプログラムの順序を緩和*-さまざまな場所への以前の未処理の書き込みをバイパスして書き込みできるようにすることで、メインメモリを更新する前に複数の書き込みを書き込みバッファにマージできます。 したがって、重複する複数の書き込みミスが発生し、順不同で表示されます。 動機は、プロセッサブレークタイムに対する書き込みレイテンシの影響をさらに最小限に抑え、新しいデータ値を他のプロセッサから見えるようにすることで、プロセッサ間の通信効率を高めることです。
• すべてのプログラム注文の緩和-プロセス内のデータと制御の依存関係を除き、デフォルトではプログラム注文は保証されません。 したがって、利点は、複数の読み取り要求を同時に未処理にすることができ、プログラムの順序で後の書き込みでバイパスでき、順序が狂って完了するため、読み取りの待ち時間を隠すことができることです。 このタイプのモデルは、他のメモリ参照への過去の読み取りミスを継続できる動的にスケジュールされたプロセッサに特に役立ちます。 これらは、コンパイラーの最適化によって行われるアクセスの排除さえも含め、多くの並べ替えを可能にします。

プログラミングインターフェース

プログラミングインターフェイスは、同期操作の間、プログラムの順序をまったく維持する必要がないことを前提としています。 すべての同期操作が明示的にラベル付けまたは識別されていることが保証されます。 ランタイムライブラリまたはコンパイラは、これらの同期操作を、システム仕様で要求される適切な順序保存操作に変換します。

システムは、プロセス内の場所への依存を混乱させることなく、同期操作間で操作を任意の方法で並べ替えることができますが、連続した一貫した実行を保証します。 これにより、コンパイラは、必要な並べ替えに対して同期ポイント間の十分な柔軟性を実現し、メモリモデルで許可されている数だけ並べ替えを実行することもできます。 プログラマのインターフェイスでは、一貫性モデルは少なくともハードウェアインターフェイスの一貫性モデルと同じくらい弱い必要がありますが、同じである必要はありません。

翻訳メカニズム

ほとんどのマイクロプロセッサでは、ラベルを翻訳してメカニズムを維持することは、同期としてラベル付けされた各操作の前後に適切なメモリバリア命令を挿入することになります。 命令を保存し、個々のロード/ストアにどの順序を適用するかを示し、余分な命令を回避します。 ただし、通常は操作が頻繁ではないため、ほとんどのマイクロプロセッサがこれまで行ってきた方法ではありません。

容量制限の克服

プロセッサキャッシュメモリ内のハードウェアのみで自動複製と一貫性を提供するシステムについて検討しました。 プロセッサキャッシュは、ローカルのメインメモリに最初に複製されることなく、参照時にリモートで割り当てられたデータを直接複製します。

これらのシステムの問題は、ローカルレプリケーションの範囲がハードウェアキャッシュに制限されることです。 キャッシュメモリからブロックを置き換える場合、再度必要になったときにリモートメモリからブロックをフェッチする必要があります。 このセクションで説明するシステムの主な目的は、レプリケーションキャパシティの問題を解決することですが、ハードウェアの一貫性とキャッシュブロックのきめ細かい粒度を提供して効率を高めることです。

三次キャッシュ

複製能力の問題を解決するための1つの方法は、大きくても低速のリモートアクセスキャッシュを使用することです。 これは機能のために必要です。マシンのノード自体が小規模なマルチプロセッサであり、パフォーマンスのために単純に大きくすることができる場合です。 また、ローカルプロセッサのキャッシュメモリから置き換えられた複製されたリモートブロックも保持します。

キャッシュオンリーメモリアーキテクチャ（COMA）

COMAマシンでは、メインメモリ全体のすべてのメモリブロックにハードウェアタグがリンクされています。 メモリブロックに割り当てられたスペースが常に保証される固定ノードはありません。 データは、それらにアクセス/引き付けるノードのメインメモリに動的に移行または複製されます。 リモートブロックにアクセスすると、アトラクションメモリに複製されてキャッシュに取り込まれ、ハードウェアによって両方の場所で一貫性が保たれます。 データブロックは、任意のアトラクションメモリに常駐でき、一方から他方へ簡単に移動できます。

ハードウェアコストの削減

コスト削減とは、専用ハードウェアの一部の機能を既存のハードウェアで実行されるソフトウェアに移行することを意味します。 ソフトウェアは、ハードウェアキャッシュ内よりもメインメモリ内で複製と一貫性を管理する方がはるかに簡単です。 低コストの方法は、メインメモリで複製と一貫性を提供する傾向があります。 コヒーレンスを効率的に制御するために、アシストの他の各機能コンポーネントは、ハードウェアの専門化と統合の恩恵を受けることができます。

研究努力は、専用のハードウェアでアクセス制御を実行するなど、さまざまなアプローチでコストを削減することを目的としていますが、他のアクティビティをソフトウェアおよびコモディティハードウェアに割り当てます。 別のアプローチは、ソフトウェアでアクセス制御を実行することであり、特殊なハードウェアサポートなしで、コモディティノードおよびネットワーク上でコヒーレントな共有アドレス空間抽象化を割り当てるように設計されています。

並列ソフトウェアへの影響

緩和されたメモリ一貫性モデルでは、並列プログラムが必要な競合するアクセスを同期ポイントとしてラベル付けする必要があります。 プログラミング言語は、一部の変数を同期としてラベル付けするサポートを提供します。このラベルは、コンパイラーによって適切な順序保存命令に変換されます。 コンパイラが共有メモリへのアクセスの再配列を制限するために、コンパイラはそれ自体でラベルを使用できます。

相互接続ネットワーク設計

並列マシンの*相互接続ネットワーク*は、任意のソースノードから任意の目的のノードに情報を転送します。 このタスクは、可能な限り短い遅延で完了する必要があります。 多数のこのような転送を同時に実行できるようにする必要があります。 さらに、それは機械の残りの部分のコストと比較して安価でなければなりません。

ネットワークはリンクとスイッチで構成され、情報を送信元ノードから宛先ノードに送信するのに役立ちます。 ネットワークは、トポロジ、ルーティングアルゴリズム、スイッチング戦略、およびフロー制御メカニズムによって指定されます。

組織構造

相互接続ネットワークは、次の3つの基本コンポーネントで構成されます-

• リンク-リンクは、スイッチまたはネットワークインターフェイスポートに接続された各端にコネクタが付いた1つ以上の光ファイバーまたは電線のケーブルです。 これにより、アナログ信号が一方の端から送信され、もう一方の端で受信されて元のデジタル情報ストリームが取得されます。
• スイッチ-スイッチは、入力および出力ポートのセット、すべての入力をすべての出力に接続する内部「クロスバー」、内部バッファリング、および各時点で入出力接続を実現する制御ロジックで構成されます。 一般に、入力ポートの数は出力ポートの数と同じです。
• ネットワークインターフェース-ネットワークインターフェースはスイッチノードとはまったく異なる動作をし、特別なリンクを介して接続される場合があります。 ネットワークインターフェイスはパケットをフォーマットし、ルーティングおよび制御情報を構築します。 スイッチと比較して、入力および出力のバッファリングがある場合があります。 エンドツーエンドのエラーチェックとフロー制御を実行できます。 したがって、そのコストは、処理の複雑さ、ストレージ容量、ポート数に影響されます。

相互接続ネットワーク

相互接続ネットワークは、スイッチング要素で構成されています。 トポロジは、個々のスイッチをプロセッサ、メモリ、その他のスイッチなどの他の要素に接続するパターンです。 ネットワークにより、並列システムのプロセッサ間でデータを交換できます。

• 直接接続ネットワーク-直接ネットワークには、隣接ノード間のポイントツーポイント接続があります。 これらのネットワークは静的です。つまり、ポイントツーポイント接続は固定されています。 直接ネットワークの例には、リング、メッシュ、キューブがあります。
• 間接接続ネットワーク-間接ネットワークには固定ネイバーがありません。 通信トポロジーは、アプリケーションの要求に基づいて動的に変更できます。 間接ネットワークは、バスネットワーク、マルチステージネットワーク、クロスバースイッチの3つの部分に分割できます。
• バスネットワーク-バスネットワークは、いくつかのリソースが接続されているいくつかのビット線で構成されています。 バスがデータとアドレスに同じ物理ラインを使用する場合、データとアドレスラインは時間多重化されます。 バスに複数のバスマスターが接続されている場合、アービターが必要です。
• マルチステージネットワーク-マルチステージネットワークは、スイッチの複数のステージで構成されます。 これは、特定のインターステージ接続パターン（ISC）を使用して接続された「axb」スイッチで構成されています。 小型の2x2スイッチエレメントは、多くの多段ネットワークで一般的な選択肢です。 ステージの数がネットワークの遅延を決定します。 異なるステージ間接続パターンを選択することにより、さまざまなタイプのマルチステージネットワークを作成できます。
• クロスバースイッチ-クロスバースイッチには、接続を作成または切断するためにオン/オフを切り替えることができる単純なスイッチ要素のマトリックスが含まれています。 マトリックス内のスイッチエレメントをオンにすると、プロセッサとメモリを接続できます。 クロスバースイッチは非ブロッキングです。つまり、すべての通信順列はブロッキングなしで実行できます。

ネットワークトポロジでの設計のトレードオフの評価

主な関心事がルーティング距離である場合、寸法を最大化し、ハイパーキューブを作成する必要があります。 ストアアンドフォワードルーティングでは、スイッチの程度とリンクの数が重要なコスト要因ではなく、リンクの数またはスイッチの程度が主なコストであると仮定すると、次元を最小化し、メッシュ作りました。

各ネットワークの最悪の場合のトラフィックパターンでは、すべてのパスが短い高次元ネットワークを使用することをお勧めします。 各ノードが1つまたは2つの近隣のノードとのみ通信するパターンでは、実際に使用されるディメンションはごく少数であるため、低次元のネットワークを使用することをお勧めします。

ルーティング

ネットワークのルーティングアルゴリズムは、ソースから宛先への可能なパスのどれがルートとして使用されるか、および特定の各パケットがたどるルートがどのように決定されるかを決定します。 次元順序ルーティングは、各ソースから各宛先へのルートが1つだけになるように、有効なパスのセットを制限します。 最初に高次元で正しい距離を移動し、次に次の次元に移動するなどして得られたもの。

ルーティングメカニズム

算術、ソースベースのポート選択、およびテーブル検索は、高速スイッチがパケットヘッダーの情報から出力チャネルを決定するために使用する3つのメカニズムです。 これらのメカニズムはすべて、従来のLANおよびWANルーターに実装されている種類の一般的なルーティング計算よりも単純です。 並列コンピューターネットワークでは、スイッチはすべてのサイクルですべての入力のルーティングを決定する必要があるため、メカニズムはシンプルかつ高速である必要があります。

確定的ルーティング

ルーティングアルゴリズムは、メッセージがたどるルートがネットワーク内の他のトラフィックではなく、送信元と宛先によってのみ決定される場合に決定的です。 ルーティングアルゴリズムが宛先への最短パスのみを選択する場合、それは最小であり、そうでない場合は非最小です。

デッドロックの自由

デッドロックはさまざまな状況で発生する可能性があります。 2つのノードが互いにデータを送信しようとし、それぞれが受信する前に送信を開始すると、「ヘッドオン」デッドロックが発生する場合があります。 ネットワーク内のリソースを奪い合う複数のメッセージがある場合、デッドロックの別のケースが発生します。

ネットワークを証明するための基本的な手法は、デッドロックがなく、ネットワーク内を移動するメッセージの結果としてチャネル間で発生する可能性のある依存関係をクリアし、チャネル依存関係グラフ全体にサイクルがないことを示すことです。したがって、デッドロックを引き起こす可能性のあるトラフィックパターンはありません。 これを行う一般的な方法は、依存関係サイクルが発生しないように、すべてのルートが特定の増加または減少シーケンスに従うようにチャネルリソースに番号を付けることです。

スイッチ設計

ネットワークの設計は、スイッチの設計とスイッチの相互接続方法に依存します。 スイッチの程度、内部ルーティングメカニズム、および内部バッファリングによって、サポートできるトポロジと実装可能なルーティングアルゴリズムが決まります。 コンピューターシステムの他のハードウェアコンポーネントと同様に、ネットワークスイッチにはデータパス、制御、およびストレージが含まれます。

ポート

ピンの総数は、実際には入力ポートと出力ポートの総数にチャネル幅を掛けたものです。 チップの周囲が面積と比較してゆっくりと成長するにつれて、スイッチはピン制限される傾向があります。

内部データパス

データパスは、入力ポートの各セットとすべての出力ポート間の接続です。 通常、内部クロスバーと呼ばれます。 ノンブロッキングクロスバーは、各入力ポートを任意の順列で個別の出力に同時に接続できるクロスバーです。

チャンネルバッファー

スイッチ内のバッファストレージの構成は、スイッチのパフォーマンスに重要な影響を及ぼします。 従来のルーターとスイッチは、スイッチファブリックの外部に大きなSRAMまたはDRAMバッファーを持っている傾向がありますが、VLSIスイッチでは、バッファリングはスイッチの内部にあり、データパスおよび制御セクションと同じシリコンバジェットから発生します。 チップのサイズと密度が増加するにつれて、より多くのバッファリングが利用可能になり、ネットワーク設計者はより多くのオプションを使用できるようになりますが、それでもバッファの不動産は最優先の選択肢であり、その構成は重要です。

フロー制御

ネットワーク内の複数のデータフローが同じ共有ネットワークリソースを同時に使用しようとする場合、これらのフローを制御するために何らかのアクションを実行する必要があります。 データを失いたくない場合は、一部のフローをブロックし、他のフローを続行する必要があります。

フロー制御の問題は、すべてのネットワークおよび多くのレベルで発生します。 ただし、並列コンピュータネットワークでは、ローカルネットワークやワイドエリアネットワークとは質的に異なります。 並列コンピューターでは、ネットワークトラフィックをバスを通過するトラフィックとほぼ同じくらい正確に配信する必要があり、非常に短い時間スケールで非常に多数の並列フローがあります。

レイテンシートレランス

マイクロプロセッサの速度は10年ごとに10倍以上に増加しましたが、コモディティメモリ（DRAM）の速度は2倍になりました。つまり、アクセス時間が半分になりました。 したがって、プロセッサクロックサイクルに関するメモリアクセスのレイテンシは、10年で6倍に増加します。 マルチプロセッサが問題を強化しました。

バスベースのシステムでは、プロセッサとメモリの間に高帯域幅バスを確立すると、メモリからデータを取得するレイテンシが増加する傾向があります。 メモリが物理的に分散されると、ネットワークおよびネットワークインターフェイスのレイテンシが、ノード上のローカルメモリにアクセスするレイテンシに追加されます。

通常、ノードの数が多いほど計算に関連する通信が多くなり、一般的な通信のためのネットワーク内のジャンプが多くなり、競合が増えるため、マシンのサイズに応じて遅延が増加します。 ハードウェア設計の主な目標は、高いスケーラブルな帯域幅を維持しながら、データアクセスの遅延を削減することです。

レイテンシートレランスの概要

遅延許容値の処理方法は、マシンのリソースとその使用方法を確認することで最もよく理解できます。 プロセッサの観点から見ると、あるノードから別のノードへの通信アーキテクチャはパイプラインと見なすことができます。 パイプラインのステージには、送信元と宛先のネットワークインターフェイス、および途中のネットワークリンクとスイッチが含まれます。 アーキテクチャが通信を管理する方法に応じて、通信アシスト、ローカルメモリ/キャッシュシステム、およびメインプロセッサにも段階があります。

ベースライン通信構造の使用率の問題は、プロセッサまたは通信アーキテクチャが特定の時間でビジーであり、通信パイプラインでは、送信される単一ワードが送信元から宛先に移動するため、一度に1つのステージのみがビジーです。 レイテンシトレランスの目的は、これらのリソースの使用を可能な限り重複させることです。

明示的なメッセージパッシングでのレイテンシートレランス

メッセージ受け渡しにおけるデータの実際の転送は、通常、送信操作を使用して送信者が開始します。 受信操作自体は、データを通信するように動機付けるのではなく、着信バッファからアプリケーションのアドレス空間にデータをコピーします。 受信者が開始した通信は、データのソースであるプロセスに要求メッセージを発行することにより行われます。 その後、プロセスは別の送信を介してデータを送り返します。

同期送信操作の通信遅延は、メッセージ内のすべてのデータを宛先に通信するのにかかる時間、受信処理の時間、および確認応答が返される時間に等しくなります。 同期受信操作の遅延は、処理のオーバーヘッドです。これには、データをアプリケーションにコピーすること、およびデータがまだ到着していない場合の追加の待ち時間が含まれます。 可能であればオーバーヘッドを含め、これらのレイテンシを両端で非表示にしたいと思います。

共有アドレススペースでのレイテンシトレランス

ベースライン通信は、共有アドレス空間での読み取りと書き込みを介して行われます。 便宜上、これは読み取り/書き込み通信と呼ばれます。 受信者が開始した通信は、読み取り操作で行われ、その結果、別のプロセッサのメモリまたはキャッシュからのデータがアクセスされます。 共有データのキャッシュがない場合、送信者が開始した通信は、リモートメモリに割り当てられたデータへの書き込みによって行われます。

キャッシュコヒーレンスを使用すると、書き込みの効果はより複雑になります。書き込みが送信者につながるか、受信者が開始する通信はキャッシュコヒーレンスプロトコルに依存します。 受信者が開始するか送信者が開始するかのどちらかで、ハードウェアでサポートされる読み取り書き込み共有アドレス空間での通信は、当然のことながらきめ細かく、これにより許容遅延が非常に重要になります。

共有アドレススペースでのデータ転送のブロック

共有アドレス空間では、ハードウェアまたはソフトウェアのいずれかによって、データの結合とブロック転送の開始をユーザープログラムで明示的に、またはシステムによって透過的に実行できます。 明示的なブロック転送は、ユーザープログラムでの送信と同様のコマンドを実行することにより開始されます。 送信コマンドは通信アシストによって説明されます。通信アシストは、ソースノードから宛先にパイプライン方式でデータを転送します。 宛先で、通信アシストはネットワークインターフェイスからデータワードを取得し、指定された場所に保存します。

送受信メッセージの受け渡しには2つの主な違いがあります。これらの場所は共有アドレス空間にあるため、送信プロセスがデータを宛先に配置するプログラムデータ構造を直接指定できるという事実から生じます。 。

共有アドレススペースでの過去の長時間のイベントの進行

メモリ操作が非ブロック化されると、プロセッサはメモリ操作を通過して他の命令に進むことができます。 書き込みの場合、これは通常、書き込みが書き込みバッファーに入れられ、バッファーがメモリシステムに書き込みを発行し、必要に応じてその完了を追跡する間、プロセッサーが動作する場合に実装するのが非常に簡単です。 違いは、書き込みとは異なり、読み取りの後に返される値を必要とする命令が通常すぐに読み取られることです。

共有アドレス空間での事前通信

事前通信は、市販のマイクロプロセッサで既に広く採用されている技術であり、その重要性は将来増加する可能性があります。 プリフェッチ命令は、データ項目の実際の読み取りに置き換わるものではありません。オーバーラップによりレイテンシを隠すという目標を達成するためには、プリフェッチ命令自体が非ブロッキングでなければなりません。

この場合、共有データはキャッシュされないため、プリフェッチされたデータはプリフェッチバッファと呼ばれる特別なハードウェア構造に取り込まれます。 次の反復でワードが実際にレジスタに読み込まれるとき、メモリからではなくプリフェッチバッファの先頭から読み込まれます。 非表示のレイテンシが単一ループの反復を計算する時間よりもはるかに大きい場合、先にいくつかの反復をプリフェッチし、一度にプリフェッチバッファに複数のワードが存在する可能性があります。

共有アドレス空間でのマルチスレッド

さまざまなタイプのレイテンシを非表示にするという点では、ハードウェアでサポートされているマルチスレッドはおそらく多目的なテクニックです。 他のアプローチよりも次の概念的な利点があります-

• 特別なソフトウェア分析やサポートは必要ありません。
• 動的に呼び出されるため、キャッシュの競合などの予測不可能な状況を処理できます。 同様に予測可能なもの。
• プリフェッチのように、スレッド内のアクセスを並べ替えないため、メモリ一貫性モデルは変更されません。
• 以前の手法はメモリアクセスの遅延を隠すことを目的としていましたが、マルチスレッドは、実行時にイベントを検出できる限り、潜在的に長い遅延イベントの遅延を簡単に隠すことができます。 これには、同期と命令レイテンシも含まれます。

プロセッサの速度と比較してレイテンシがますます長くなっているため、この傾向は将来変化する可能性があります。 また、マルチスレッド用に拡張できるメソッドを既に提供しているより洗練されたマイクロプロセッサ、およびマルチスレッドと命令レベルの並列性を組み合わせるために開発されている新しいマルチスレッド技術により、この傾向は確かに将来変化しているようです。