並列処理マシン

Author

gentam

Date
2017-11-13
Category

booknote

Tag

parallel, architecture

最近,FPGAでErlang向きの超並列処理のプロセッサみたいなものを作りたいと思ってい たので,図書館で見つけてタイトル的に借りてみた.出版は1989年のやや古い本なので 成功しなかったアイディアや時代遅れの内容もあるが,それが逆に学びになったような 気もする.

どこかで読んだ話によると,自動車の黎明期には電気で動くものや蒸気機関で動くものな どが,ガソリン車と並んで開発され競い合っていたらしい.ところが偶然のきっかけから ガソリン車がビジネス的に成功を収めて今に至っている. (電球にも似たような話があったような)

電気自動車は当時の環境において一度は消えたが,今になって成功を収めているわけなの で,初期の市場によって淘汰されたものが必ずしも本質的に劣ったデザインであるとは限 らないとえる.みたいなことを念頭に置きながら,昔の様々な試みを知るのは宝探し的な 楽しさを感じることができる.もちろんそこには蒸気自動車みたいなアイディアも含まれ ているのだろうけど.


Title

並列処理マシン

Authors

富田眞治; 末吉敏則

Published

1989-05-25

ISBN

4-274-07501-X

Read

2017-11-13

Contents

並列処理マシンの構成

並列処理マシンを構成する方法は主に以下に分類できる:

マルチプロセッサ方式とデータフロー方式に特に興味があったので,このノートはその 2つを中心にとってある.

演算パイプライン方式

演算パイプライン方式では,演算装置が多数のステージからなる流れ作業の原理で構成 されており,ベクトルや配列などに対する定型的処理に適している.

SIMD方式

SIMD (Single Instruction Stream Multiple Data Stream)方式では,演算装置が多数 設置されており,それらが一つの制御部から発せられた演算命令を同時に実行する.

以下の2つの方式が代表的:

  • ILLIAC Ⅳ型のSIMD方式は,1つの制御部から各演算装置へ命令をブロードキャストし, それぞれの演算装置はローカルメモリを持っていて,それらが結合網に接続されている

  • BSP型のSIMD方式は,それぞれの演算装置が結合網を通じてメモリへアクセスする.

超長形式命令(VLIW)型計算機

比較的長い命令を多数のフィールドに分割して,それぞれのフィールドで多数の演算器 やレジスタ,相互結合網,メモリなどが独立に制御される.

  • コンパイル時に並列性を検出するため,ハードウェアの構成は簡潔化できる

  • 並列演算の度合いは,コンパイラの能力と問題自体の並列化できる割合に依存している.

  • 並列度が低い場合には演算器制御フィールドに遊びができて命令ビットの使用効率が 低下してしまう

  • 例: 京大のQA-2というマシンは256ビットの命令形式で,4つのALU制御と 主記憶アドレス制御,1つの順序制御を同時に指定できた.

マルチプロセッサ方式

(p.118) マルチプロセッサ方式はMIMD(Multiple Instruction Stream Multiple Data Stream) 方式の一つであり,自律的に動作する多数のプロセッサが互いに密に通信しあって協調 しながら並列に動作する.並列処理の観点からは,一つの仕事をn台のプロセッサで分担 して処理すれば,1台のプロセッサを用いた場合よりも,理想的にはn倍高速に処理でき るはずである.

マルチプロセッサ方式の目的として以下があげられる.

  1. 負荷分散

  2. 機能分散

  3. フォールトトレランス

  4. ニーズに応じたスケーラビリティ

マルチプロセッサの分類

プロセッサ間結合方式による分類

各プロセッサは,プログラムが通信と同期を行えるように相互に接続されている.この 物理的な結合方法の観点からは以下の二つに分けられる.

密結合(tightly coupled)マルチプロセッサ

全プロセッサが共通にアクセスできる共有メモリ(shared memory)を通じた情報共有 で通信を行う.したがって,通信速度はメモリのバンド幅オーダであり,大量の情報 を素早く交換することができる.一方,最大の制約要因は,複数のプロセッサが同一 メモリにアクセスしようとする際に発生する競合問題である.プロセッサ数が多く なると競合によってアクセスが逐次的になってしまう.このため,密結合マルチプロ セッサは比較的プロセッサ数が少ない場合に有効な方式である.

疎結合(loosely coupled)マルチプロセッサ

各プロセッサが自分だけがアクセスできるローカルメモリを持ち,共有メモリは存在 しない.プロセッサ間の情報交換は,入出力操作と同様にチャネルやポートを介して 行われるため,メモリのバンド幅に比べてかなり低下する.疎結合マルチプロセッサ では,メモリでの競合が起きない反面,直接的な通信路がないプロセッサ間では中継 オーバーヘッドが問題となる.一般にプロセッサ数は密結合よりも多くとることがで きる.

プロセス間通信による分類

プロセッサではなく,プログラムの並列実行の単位である プロセス 間でのソフトウ ェア的な通信モデルの観点からは以下に分けられる.

共有変数型マルチプロセッサ

プロセス間に共有変数(shared variable)を用いて通信を行う.これは掲示板による 通信に例えられる.一般的には物理的な共有メモリを用いて情報を共有する密結合 マルチプロセッサに対応して用いられることが多いが,密結合マルチプロセッサでも OSが仮想的に統一のメモリスペースを提供するならば(一般的にはかなりの性能低下 とともに)実現できる.

メッセージ転送型マルチプロセッサ

メッセージ転送(message passing)をただ一つの通信手段とするモデルである.基本 的には1対1(point-to-point)通信であるため,郵便や電話に例えられる.メッセージ 転送型マルチプロセッサは,疎結合マルチプロセッサに対応して用いられることが 多いが,密結合でも共有メモリ上のバッファ領域で通信チャネルを実現できる. この場合は必ずしも性能低下が起きるとは限らない.

またこれ以外にトポロジーによっても分類できる (相互結合網)

マルチプロセッサの有用性と限界

n倍のプロセッサを用いたらn倍高速に処理できる,線形速度向上が望ましい.しかし, 実際には,ある台数を超えると速度向上曲線は緩やかになり飽和するが,場合によって は減少することさえある.これは,1プロセッサ当たりの通信/同期オーバーヘッドに 起因する.

ベクトル演算を含むプログラムの性能評価は有名なアムダールの法則(Amdahl's law)で 表すことができる:

Sp = 1/{(1-p)+p/N} where
    p     プログラム内におけるベクトル化率
    (1-p) プログラム内におけるスカラ演算の比率
    N     スカラ演算に対するベクトル演算の性能比

この法則は,pをプログラムにおける並列化率,Nをプロセッサ数と解釈することで マルチプロセッサにも適応することができる.

ここから分かるのは,プロセッサを無数に用いたとしても速度向上は逐次処理部分で 抑えられることになり,問題をうまく分割して並列度をあげる必要があるということだ. しかし,これは通信オーバーヘッドを無視しているため,タスクの粒度(granularity)を 適切に設定しなければ速度向上には繋がらない.

マルチプロセッサにおける並列処理では,通信や同期のオーバーヘッドをいかに減らす かが鍵となる.タスク粒度の決定には,通信単位時間や通信量,同期一回にかかる時間, 同期回数などに依存するため,これらの値に密接に関係する通信/同期機構,メモリ構成 プログラミング言語が重要となる.また スケジューリングと負荷分散 も重要である.

プロセス間通信と同期

マルチプロセッサでは正しい結果を得るために,プロセスの実行順序を調整しなければ いけない.同期はデータが制御情報である特別な通信であるともいえるため,通信と 同期の機能を区別するのは難しい.

条件同期 (condition synchronization)

あるプロセスが他のプロセスによってある条件を満たされるまで待つこと

相互排除 (mutual exclusion)

あるプロセスが共有データに対して操作している最中に他のプロセスがその共有 データに対して同時に操作しないように制御すること. クリティカルセクションが不可分に実行されることを保証する.

際どい区間 (critical section)

不可分に実行されなければいけないプログラムの部分

共有変数型マルチプロセッサでは,条件同期と相互排除をともに解決するための機能が 必要になるが,メッセージ転送型マルチプロセッサでは共有変数が存在しないため, 相互排除の問題は生じない.

ハードウェアレベルの同期機構

相互排除では,共有データへのアクセスを直列化(serialization)する必要がある. 複数プロセッサが存在する場合にソフトウェアだけで相互排除を解決する方法は 非常に複雑で非効率になる.そのため,同期のための特別な機能をハードウェアで 用意して,同期操作に伴うオーバーヘッドをできるだけ小さくする. これらが,ソフトウェアレベルの同期機構を実現するプリミティブを提供する.

Test-and-Set (TS命令)

不可分な1bitのフラグ操作

Compare-and-Swap (CS命令)

不可分なワード単位での更新操作.ENQUEUE操作を実現できる

Full/Empty bit

メモリやレジスタにこのビットを付けることで書き込み前に読み出しを行うことを防 げる.(生産者-消費者問題)

Fetch-and-Add (F&A)

共有変数Vをフェッチして,それを(V)+eで置き換える不可分操作.並列アクセス時の 順番は保障されないが,返す値の一意性は保障されるため,配列のインデックス毎に 別のプロセッサを割り割てる際などに使える.

ソフトウェアレベルの同期機構

それぞれの説明は省略.

  1. セマフォ (semaphore)

  2. バリア (barrier)

  3. モニタ (monitor)

  4. 通信プリミティブ send/receive

  5. 遠隔手続き呼び出し (RPC)

プロセス間通信

  • 共有変数による通信機構: 効率的に優れているが,同期やロックが必要になる

  • メッセージ転送による通信機構: 全てのデータ移動を send, receive プリミティブで行う

    1. 通信チャネルの指定法:

      直接指定法

      プロセス名そのものを送受信側の指定に使う.1対1通信に適している.

      大域名指定法

      portやmailboxと呼ばれるチャネルを利用し,1対多/多対多通信に対応できる. ポートの実現は共有メモリを利用した方が容易に実現できる.

    2. 通信プリミティブにおける同期:

      send/receive プリミティブは,相手からの確認応答を待つブロッキングと, 常にループして調べるノンブロッキングがある.

スケジューリングと負荷分散

プロセッサが複数存在する効果を生かして,スループットの最大化,あるいはレイテンシ の最小化などの目的を達成するためには,目的に応じてプロセスの実行を制御しなければ ならない.

プロセススケジューリング

プロセス制御ブロック (Process Control Block: PCB)

複数のプロセスを1つのプロセッサで動かすためには,OSがプロセスを中断したり再開 したりして制御する必要がある.これを可能にするために,PCBがプログラムカウンタ や,内部レジスタファイル,スタック制御情報,記憶管理情報などを保存している.

プロセスの状態

プロセスはrunning, ready, waitという三つの状態を持つ.同時にrunningにあるプロセス 数が物理的なプロセッサ数を超えることはできない.readyはプロセッサの割り当て を待っている状態である.

プロセススケジューリング方式

プロセスは実行可能待ち行列(ready queue)や,待機待ち行列(wait queue)を用いて管理 される.wait queueは待っている事象ごとに用意される.これらのリストはPCBのポインタ 記述欄を利用した連結リストになっている.このリストをスケジューリングする代表的な 方法として以下がある:

到着順処理(First Come First Served)方式

単純に,実行可能になった順にプロセスを実行可能待ち行列につなぐ(FIFO). 欠点として,あるプロセスがプロセッサを長時間占有すると他のプロセスが待たされ てしまう,優先処理ができないなど.

巡回(round robin)方式

プロセッサを占有できる一定の時間(time slice)を与えて,時間を超えると ready queue の最後に繋がれる.これで単一プロセスによる占有を防ぐことができる.

優先度(priority)方式

プロセスの性質に基づいて優先度が生成時に与えられる.同じ優先度のプロセスは FIFIOやround robinでスケジューリングされる.

多重フィードバック(multilevel feedback)方式

各プロセスに最初は高い優先度と短いタイムスライスを与え,それだけで完了しないと 優先度を下げるとともに,ライムスライスを長くしていく.平均レイテンシーを短く することができる.

時限(dead line)方式

目標値としての応答時間や処理時間をプロセスの性質に応じて与えておき,目標値に 近くに従って処理優先度を上げていく.

プロセススイッチの高速化
ディスパッチ(dispatch)

プロセススイッチに際して,次に実行すべきプロセスにプロセッサを割り当てること. この操作を行う機能モジュールをディスパッチャと呼ぶ.

ディスパッチャは,コンテクストスイッチ(実行中のプロセスのPCBを退避して,次に実行 すべきプロセスのPCBから新しいコンテクストを回復する)操作を行うため,システム内で もっとも頻繁に起動されるモジュールであり,高速に実行できることが望ましい.

  1. 軽量プロセス (light-weight process)

    多重仮想記憶をサポートしているOSではレジスタ集合だけでなくページテーブル などの処理も必要となり,コンテクストスイッチのオーバーヘッドが大きくなって しまう.この問題を解決するために,CMUのMachではスレッド(thread)という概念 を導入している.スレッドは同じアドレス空間で動くため,レジスタ類の退避と 回復だけで良い.

  2. 多重レジスタセット

    汎用レジスタの数が増えるに従って,それら全ての退避と回復にも時間がかかる ようになったため,プロセスごとに物理的に異なるレジスタセットを割り当てる という方法.(例: 日立のH16ではレジスタバンクを利用して,スイッチングに かかる時間が約1/9に短縮)

マルチプロセッサスケジューリング

マルチプロセッサにおけるスケジューリングとは,複数のタスクをどのプロセッサに割り 当て,どのような順序で実行するのかを決定することである.ここで,タスク間の依存 関係を考慮して,全タスクの実行時間を最小にしなければいけない.

(この文脈においては,プロセスよりもタスクという言葉が計算活動の不可分な単位として 用いられる)

そのようなスケジューリング問題は以下の3つに分けられる:

  1. 決定性の問題 -- プログラム実行前にタスク集合が完全に与えられる

  2. 確率的な問題 -- 処理時間の確率分布関数などの統計的性質が与えられる

  3. 非決定性の問題 -- プログラム実行前にはタスク集合が全く予想できない

タスクの集合は,データ依存関係に基づいた有向非巡回グラフ(DAG)によって表すことが できる.

決定性のスケジューリング問題

以下のようなアルゴリズムを用いて多項式時間で最適なスケジューリングを見つけられる がプロセッサ台数や,タスク実行時間,タスクグラフの形状のいずれかに強い制約が課せ られている.

  • Muntz–Coffman

  • Coffman-Graham

  • Hu

  1. リストスケジューリング は最も一般的な問題に適応でき,多くのスケジューリン グアルゴリズムの基礎となっている.

    • 手順:

      1. 各タスクに異なる優先順位を与え,順位の高い順に並べたリスト(優先順位リスト) を作る

      2. プロセッサが空いたら,優先順位リストの先頭からタスクを選んで割り当てる

    • 優先順位リストの作成手順:

      1. タスクグラフの終端ノードにあるタスクに最低優先順位をつける

      2. 優先順位をつけられたタスクの直前の先行タスク全てに対して,昇順の優先順位 をつけていく

      3. 全てのタスクに優先順位がつけられるまで上を繰り返す

      4. 各タスクを付加された優先順位の高い順にリストにつなぐ

この先行制約だけに基づくリストスケジューリングでは最適なスケジューリングにはならな い場合がある.ここで精度の高い近似解を得るために様々なスケジューリングアルゴリ ズムが研究されていて,例えばCP法がある.

CP (Critical Path)法

各タスクの処理時間を考慮に入れて,終端ノードから各タスクに対応するノードま での最長パスの長さを求めて優先順位リストを作成する

CP/MISF (Critical Path/Most Immediate Successors First)

CP法の欠点を改善したもの.Coffman-Grahamの最適アルゴリズムを考慮に入れて 同一レベルのタスクが複数存在する場合に直接の後続者の多い順に優先順位をつけ ている

DF/IHS (Depth First/Implicit Heuristic Search)

ヒューリスティックを用いた深さ優先探査を行うアルゴリズム.CP/MISFより常に 優れた近似解を得ることができる

負荷分散

負荷分散(load balancing)とは,マルチプロセッサを構成する各プロセッサの能力に応じ て,負荷が均衡化するようにプロセスを割つける,スケジューリングの一種.

静的負荷分散

実行前に推定実行時間に基づいて,各プロセスの割り当てを決定すること.実際には 実行してみないと分からないことが多いため難しい.

動的負荷分散

新たなプロセスが生成された時点でプロセッサを割り当てる.各プロセッサが専用の 実行可能待ち行列を持つ方法と,大域的に共通の待ち行列を持つ方法がある.

  • 共通の実行可能待ち行列を持つ場合
    プロセッサの利用率を高められるが,実行時オーバーヘッドが問題となる.代表的な 方式に,self-scheduling と呼ばれる,プロセッサがアイドル状態になった時点で 共通の待ち行列を調べて自分で選択する分散制御方式がある.排他制御を解消する方法 として集中制御方式(マスター/スレーブ)もあるが,プロセッサ数が増えると性能の ボトルネックとなるおそれがある.
  • 専用の実行可能待ち行列を持つ場合
    排他制御のオーバーヘッドはなくなるが,プロセッサの利用率が偏るおそれがある. この偏りを回避するためには以下のような方法がある:
    • 乱数方式

      新たに生成されたプロセスをランダムに割り当てる

    • 巡回方式

      定まった順(例えばプロセスを生成したプロセッサの番号に一定値を加えた番号 のプロセッサ)に割り当てる

    • 拡散方式

      負荷の思いプロセッサのプロセスを,他のプロセッサへ実行時に移動していく

    • 閾値方式

      各プロセッサが負荷分散の閾値をもち,自分の負荷が閾値以下の場合は,新たな プロセスを自分自身に割り当て,閾値を超える場合は,閾値に達していない他の プロセッサに割り当てる

    • 最小負荷方式

      最小負荷を持つプロセッサを検出して,新たなプロセスを割り当てる

  • 上記方式のうち,大域的な情報に基づく閾値及び最小負荷方式は効率的な負荷分散が 期待できるが,全プロセッサの負荷情報を常に収集することがオーバーヘッドになる

  • また,実行時に負荷分散を行うためには,プロセスをコンテクストごと移動する (process migration) に伴うデータ転送も問題となる

  • → 負荷状況の把握と,負荷分散に伴う通信のオーバーヘッドの削減が重要となる.

  • 負荷情報管理の制御方式の観点からは,集中制御ではプロセッサ数に限界があるため, 制御を分散化が必要となる.その方法として,相互接続網に負荷分散の機構を負荷す る方式がいくつか提案されている.(負荷分散網)

メモリ構成

任意の更新パターンを前提とするマルチプロセッサではメモリや相互結合網の構成が システムの性能や拡張性を左右する.

メモリ構成方法

プロセッサの性能を最大限に引き出すには,プロセッサがアイドル状態にならないように メモリのバンド幅を高めて,必要とする命令やデータを供給できなければいけない.

多重化方式に基づくメモリ構成:

高バンド幅を実現するメモリ構成方の一つに,メモリを独立に動作可能なモジュール(バンク) に多重化した構成にすることである.代表的な多重化に基づく構成は以下:

  1. 集中共有メモリ構成

    共有のグローバルメモリを多重モジュール構成にしたもの. メモリアクセスは近接したアドレスにまとめて行われる確率が高いため,下位 ビットで多重化するとアクセスが各モジュールに分散される確率が高まる.

  2. 分散共有メモリ構成

    プロセッサと物理的に密接したローカルメモリへ分散させることで,レイテンシ や,相互結合網に要求されるバンド幅や競合も減らすことができる. しかし,他プロセッサのローカルメモリへのアクセスは遅くなるため,プログラム やデータに局所性がある場合に有利となる.

  3. 部分共有メモリ構成

    ローカルメモリとグローバルメモリの構成を組み合わせたもの.プログラムや 共有データはローカルメモリに持たせることでグローバルメモリへのアクセス を減らす.メモリの利用効率が悪いこと,ロードを明示的に行わなければいけな いことが欠点.

  4. キャッシュ方式に基づくメモリ構成

    プロセッサ毎にプライベートなキャッシュを装備する方法.グローバルメモリへ のアクセスを減らしつつ,高速SRAMを用いることでローカルメモリより高いバン ド幅を実現できる.ソフトウェア側で意識する必要がないため,単一プロセッサ システムからのソフトウェアの移植性に優れている.このため,マルチキャッシュ 方式は現在の商用密結合マルチプロセッサの主流となっている.

キャッシュコヒーレンンス問題と解決策

キャッシュコヒーレンス問題

キャッシュ間でデータに一貫性がない状態.マルチプロセッサ構成では,メモリ ブロックのコピーが複数のキャッシュに同時に存在する可能性があるため,それ らが常に最新の更新結果を反映するように制御する必要がある.

解決策:

  1. 主記憶更新方式

    プロセッサの書き込み要求に対応するブロックがキャッシュ内に存在するなら このブロックに対して書き込みを行う必要があるが,主記憶にはいつ書き込むか という問題が生ずる.この主記憶更新における制御をストア方式と呼び,以下 二つがある:

    1. store-through (write-through) 方式

      キャッシュへの書き込み時に,主記憶へは必ず書き込み,キャッシュにはヒット 時飲み書き込む方式.書き込みが多いと不利になるが,最新データが常に主記憶 にあるので,キャッシュ障害発生時の信頼確保やマルチプロセッサ構成には 都合がいい.書き込みバッファによって,主記憶への書き込み完了を待たずに 次の動作へ移れるようにしているシステムが多い.

    2. store-in (swap/write-back/copy-back) 方式

      書き込み操作の際に,キャッシュにのみデータを書き込み,ブロックが置き換 え対象になった時点でまとめて書き戻す方式.

  2. 静的コヒーレンスチェックに基づく解決策

    実行時にキャッシュコヒーレンスをチェックしないで済むようにあらかじめ解決 しておく方法.

    1. 共有キャッシュ

      あらかじめキャッシュコヒーレンス問題が生じないシステム構造をとる解決策. 複数のプロセッサが一つの共有キャッシュを利用する構造にすれば,メモリ ブロックのコピーが1つしかないため問題は生じない.しかし,大規模になると アクセス集中による競合から性能的に問題となる.

    2. ソフトウェア制御

      明らかに更新する可能性のあるデータをキャッシュに入れないという解決策. これは,任意のブロックを無効化する命令を利用したり,コンパイラが, cashable/non-cashable というタグ付けをコンパイル時に行うなどして実現する. しかし,これらは言語の記述能力やコンパイラの能力に依存する.

  3. 動的コヒーレンスチェックに基づく解決策

    キャッシュコヒーレンスを実行時にチェックして保証する方式.通常,読み出し では同一ブロックが複数のキャッシュに存在することを許すが,書き込みじには 許さない,多重読み出し/排他書き込み戦略がとられている.このため,書き込み のたびに他のキャッシュにコピーが存在するか調べる必要があり,実行時オーバ ーヘッドが問題となるため比較的小規模なマルチプロセッサ向き.

    1. ブロードキャスト方式

      書き込みがあるたびに,書き込み情報を他のキャッシュにも知らせることで 解決する.ブロードキャストは共有バスを用いて行わないと同一ブロックを 相互に更新するraceを引き起こす可能性があるため,一般的にはブロードキ ャスト無効化がとられている.この方式はプロセッサ数に比例して無効化 要求が増大することであり,せいぜい2台程度の構成しか許容できない.

    2. グローバルディレクトリ法

      キャッシュブロックと主記憶ブロックとの対応を示すディレクトリ(アドレス アレイ)を集中管理して,目的ブロックがどのキャッシュにどんな状態で存在 するかという大域的な状態を把握できるようにする.これによって,コピー が存在する場合飲み無効化要求を出すことができる.ここで,store-in 方式 を用いた場合にミスヒットすると,最新データが主記憶にあるとは限らない ので,他のキャッシュにあるか調べる必要が出てくる.この制御はブロックの 所有権(ownership)という概念に基づいた,cache coherence protocolが一般 に用いられる.所有権プロトコルでは,Read-only, Exclusive, Invalid の 3つの状態を遷移する.

    3. 共有バス法

      相互結合網として,時分割共有バスを前提とした解決策.共有バスのブロード キャスト機能を利用したバス監視機構を仮定すれば,グローバルディレクトリ にある情報を個々のキャッシュに分散させても効率的な解決が図れる. バス監視機構に基づく完全分散制御のマルチキャッシュ方式を snooping cache と呼ぶ.これを採用したシステムは拡張性に優れているため,現在密結合 マルチプロセッサの主流となっている.バス監視機構はバス上を流れる他プロ セッサのトランザクションを監視して,自キャッシュに影響を及ぼす場合に ディレクトリ情報に基づいてコヒーレンスを維持する.write-once 方式と呼 ばれるプロトコルが比較的効率の良い初期のプロトコルである.

仮想アドレスキャッシュと物理アドレスキャッシュ

キャッシュと仮想記憶機構の両方をサポートしているシステムでは,物理アドレスキャッシュ (仮想アドレスを物理アドレスに変換してキャッシュする)と,仮想アドレスキャッシュ (アドレス変換を行わずに直接キャッシュする)の2通りがある.

物理アドレスキャッシュでは,アドレス変換がオーバーヘッドとなるため,変換索引バッファ (Translation Lookaside Buffer)や,ページ内オフセットでキャッシュを引く過程と, アドレス変換とをオーバーラップさせる高速化技法が採用されている.

仮想アドレスキャッシュでは変換が不要なので,高速アクセスが可能になる利点があるが, 以下の2つの問題が生じる:

  • 多義語問題

    多重仮想記憶システムでは,同じ仮想アドレスが異なる物理アドレスを指している 可能性がある.このため,コンテクストスイッチ時に前の仮想記憶空間に属する コピーがキャッシュに残っていると,ヒットして間違ったブロックのデータをフェ ッチしてしまう可能性がある.プロセススイッチ毎にキャッシュをクリアするのが 簡単な解決策ではあるが,ヒット率低下を招くので,アドレスタグに仮想記憶空間 の識別子を含める方法などが取られることがある.

  • 同義語問題

    異なる仮想アドレスが同一の物理アドレスを指してしまうという問題が生ずる可能 性がある.この問題は単一の仮想記憶空間においても,複数ページの同一物理空間 へのマッピングを許可するシステムで生ずる.解決策には次のような方法がある:

    1. 共有を禁止/制限することで解決

    2. プロセス間の共有はキャッシュをフラッシュする

    3. 物理→仮想アドレス変換する逆変換バッファ(Reverse Translation Buffer)を用意 して,キャッシュへブロックをロードする前にTLBあるいはアドレス変換テーブル から得られた物理アドレスを用いてRTBを引き,該当ブロックがすでにキャッシュ に存在していれば,無効化する.

    • RTBは複雑な回路となるが,マルチプロセッサにおけるキャッシュコヒーレンス問題 の解決に役立つ.

並列処理言語と自動並列化コンパイラ

並列処理言語

計算モデル

  • 命令型

    • 手続き型指向モデル: Concurrent Pascal, Modula, Mesa, Concurrent Euclid, Edison, Linda

    • メッセージ指向モデル: CSP, Occam, Gypsy, PLITS

    • 操作指向モデル: Distributed Process, StarMod, Ada, SR

  • 宣言型

    • 関数(データフロー)モデル: VAL, Id, Lucid, Valid

    • 述語論理モデル: Concurrent Prolog, PARLOG, GHC

Note

Erlang載ってないのか...と思ったけど,調べたら登場が1986年でオープンソース として公開されたのは1998だったからこの本に書いてなくても仕方ない

自動並列化コンパイラ

従来の逐次処理から並列処理への橋渡しとして重要な役割を担っている.

  • 可能な限りの並列実行を行うためには,制約となるデータと制御の依存性を明らかにし て正しい順序で実行する必要がある.入力依存は並列化でき,本質的なデータ依存では ない逆依存や出力依存はrenaming技法(データ名の変更)で除去できる.

  • ループ処理では各反復を別プロセッサに分担して割り当てることでループ並列化が 行えることがある.ここでは,並列ループの認識,ループ再構成,参照パターン変換 という3つの側面がある.

データフロー方式

データ駆動方式

(p.60)

データ駆動方式にはプログラムカウンタがなく,各機械命令はそのオペランドデータ (トークン)がそろうと実行(発火. firing)される.したがって,原理的にはプログラム に内在する全ての並列性を実行時に同時に引き出すことができる.また,副作用がない ため関数型言語に適しており,プログラムの検証も容易であるとされている. プログラムはデータの依存関係を示すデータフローグラフで表現される. ...

現状のデータ駆動方式では,演算の機能レベルに比べて通信のオーバーヘッドが大きいこと, 必要なメモリバンド幅が大きいこと,プログラムやデータの参照の局所性や線形メモリ の性質を利用しにくいこと,マッチング記憶が複雑であること,構造体メモリの高速化 や並列アクセスが困難なこと,デバッグが困難なことなどの問題点があり,実用化には 至っていない.

動的データ駆動方式

同一プログラムが複数地点で呼ばれたり,再帰的に呼ばれたりすることができる. できないものを静的データ駆動方式という.

動的データ駆動方式では,異なる環境でのトークン間のミスマッチを防ぐ手段として以下 が提案されている:

  • タグ(ラベル,色)付きトークン法: 各トークンに環境を示すタグを付随して,同一タグ を持つトークン間でのマッチングが行われる

  • コピー法: 新しい環境に入るたびにプログラムのコピーがなされ実行される.

動的データ駆動型計算機の基本的な方式は循環パプライン構造が利用される:

[循環パイプライン型データ駆動計算機]

                         +-----------+                  IN
      instruction packet |           | token packet
      +------------------+   ALU     +-----------+      +
      |                  |           |           |      |
+-----+-----+            +-----------+           |      |
|instruction|                                    |      v
| memory    |                                  +-+------+-+
+-----+-----+                     interface    |          |
      |                           to I/O and   |  switch  |
      +------------+              other layers |          |
      |            |                           +-+------+-+
+-----+-----+      |                             |      |
| matching  |      | 1 op                        |      |
| memory    |      |                             |      |
+-----+-----+      |   +---------------+         |      |
      |            |   |               |         |      |
      +------------+---+   result que  +---------+      v
         2 op          |               |
                       +---------------+               OUT

             +-----+------+------+------+----------+----------+
instruction  | tag | inst | dst1 | dst2 | op1      | op1      |
packet       +-----+------+------+------+----------+----------+

             +-----+-----+------------+
token packet | tag | dst | result     |
             +-----+-----+------------+
  • オペランドデータがそろった命令は命令パケットに組み立てられ,演算器に送られる

  • 演算結果はトークンパケット(環境を示すタグ,宛先,結果からなる)に組み立てられる

  • マッチング記憶で,同一環境にある二つのオペランドデータが待ち合わせる

  • マッチング記憶へのアクセスはタグと宛先を連結したハッシングで行われる

  • マッチングが成功すると,宛先で示される次の命令が発火されて命令パケットが送出される

  • マッチングが成功しないときはもう一方のオペランドの待ち状態になる

  • 命令が1オペランドであれば,マッチング記憶は飛ばして次の命令パケットが送出される

Note

これはつまり,クロック周期のイベントループで,計算のいろんなステージにあるデータをごちゃまぜに計算していくという感じなのか. だとすると,せっかくステージ毎に並列処理できるのに,物理的には逐次処理で行わせるということなのか?

要求駆動方式とリダクション方式

(p.63)

要求駆動方式では,機械命令はその結果が要求されるとき駆動される.... 要求駆動方式では,実行過程が処理してみないとわからない動的なもので,... したがって,データ駆動方式がコンパイラ向きなのに対して,要求駆動方式は インタプリタ向きなものとなっている.要求駆動方式は関数型言語の項書換えモデル (リダクション)や論理型言語Prologの実行制御過程との相性が良い.

リダクション計算モデル

等式の左辺を右辺で順次書換え(置き換え),簡約化(reduction)し,簡約化がこれ以上 進めない段階で,計算が完了する.

リダクション戦略

書換え可能な式(リデックス)をどの順番で簡約化するか決める規則. f(g(x), h(x)) で内側の関数g, hから並列にリダクションを開始する方式を 内側並列リダクションと呼び,fのような外側の関数からリダクションを開始する方式を 外側並列リダクションと呼ぶ.

先のデータ駆動方式は,内側並列リダクションと親和性が良いが以下の欠点がある.

  • g, h が無限列を発生するような場合,fを起動できない

  • If p(x) Then f(x) Else g(x) のような条件式でxが到着した段階で,p, f, g全て の関数が起動されてしまうが,実際に必要なのはfまたはgなので不必要な評価が行われる

一方 要求駆動方式 では:

  • 必要とされるとき式の評価がなされ,不必要な評価を省ける

  • 遅延評価を容易に実現できる

  • 種々のリダクション戦略を容易に実現できる.要求駆動の特色は外側リダクションの場合に 生かされる

リダクション計算機を実現する上で,ストリングリダクション方式と, グラフリダクション方式がある.

ストリングリダクション方式

  • 評価される式を文字列としてシフトレジスタなどに保存

  • 多数のプロセッサがリデックスがあるかどうかシフトレジスタの担当領域を監視

  • 実装にはノースキャロライナ大学のMagoのFFPマシンなどがある

  • 定義式がそのままコピーされてリダクションが進むため,式の中にaが二つあると, 同一の評価を二度繰り返してしまう

  • リダクションに従ってストリングの伸縮が起こり,制御は複雑

グラフリダクション方式

  • 評価される式を,ポインタを利用したグラフの形で表現

  • 評価のために必要な値が要求されると,ポインタをたどって定義式が起動される

  • ポインタを利用しているため,他の箇所でaが評価されていれば,再度aが要求されたと きには再計算せずに結果を共有できる

  • 実装には,Imperial CollegeのALICE,東大のPIE,京大のKPRなど

相互結合網

相互結合網 (interconnection network)は,多数の演算器やプロセッサ,メモリを高速に 相互接続する網であり,並列処理マシンの性能に重大な影響を及ぼす.

相互結合網の分類:

静的網

直接結合(direct connection)網とも呼ばれ,あるターミナルから直接通信できるタ ーミナルが固定されている.静的網は完全結合網(全てのターミナルが他の全てと接続) を規則的に簡略化して構成したものと見ることができる.

動的網

間接結合(indirect connection)網とも呼ばれ,間に置かれたスイッチ群の制御によって 任意の入出力ターミナルの間での通信ができる.動的網はクロスバースイッチ網を規則 的に簡略化し,機能縮小したものと見ることができる.

負荷分散網

多段結合網上に負荷情報を流し,網のスイッチ制御を行う方法が考えられている. データとは逆方向にプロセッサの負荷状態を流して,負荷が小さい方へスイッチで きるとすると,新しいプロセスを生成した入力側プロセッサから,もっとも負荷の 軽い出力側のプロセッサへ到達することができる.通常のトラフィックの場合では ランダム方式と比較して,数倍のスループットを期待できることがシミュレーショ ンで示されている.(背景については 動的負荷分散の分散制御 を参照)