并列諸理論2第二回課件

並列処理とは並列処理：

一つの仕事を分割して複數(shù)プロセッサで同時(shí)に処理並列処理の目的処理時(shí)間の短縮(処理速度の向上)

一つの仕事の処理(レスポンスタイム向上)

複數(shù)の仕事の処理(スループット向上)耐故障性の向上処理速度の向上最速のプロセッサを使って最高速を目指す安価なプロセッサを使って高い価格性能比を目指す並列処理とは並列処理：

一つの仕事を分割して複數(shù)プロセッ並列処理の簡単な例1から9までの総和計(jì)算1人で普通に計(jì)算すると

1+2=3,3+3=6,6+4=10,…,45

加算1回=1秒とすると計(jì)算時(shí)間は8秒3人で仕事を分けて計(jì)算すると

(長男)1+2=3,3+3=6

(次男)4+5=9,9+6=15同時(shí)に計(jì)算：2秒

(三男)7+8=15,15+9=24

次男と三男は自分の結(jié)果(部分和)を長男に伝え...

(長男)6+15は21，21+24は45!2秒

計(jì)算時(shí)間は合計(jì)4秒8/4=2倍の速度向上並列処理効果並列処理の簡単な例1から9までの総和計(jì)算並列処理の簡単な例1から900までの総和計(jì)算1人で普通に計(jì)算すると

計(jì)算時(shí)間は899秒3人で仕事を分けて計(jì)算すると

各自の計(jì)算時(shí)間はそれぞれ299秒

長男での合計(jì)計(jì)算の時(shí)間は2秒計(jì)算時(shí)間は合計(jì)301秒1人での計(jì)算時(shí)間のほぼ1/3に短縮

理想的な並列処理効果一見すると幾らでもスピードアップできそうだが???並列処理の簡単な例1から900までの総和計(jì)算並列処理効果を阻害する要因逐次処理では必要無かった処理が発生してしまう

並列処理オーバーヘッド

?並列処理効果の低減総和計(jì)算の例：いつもこんなにうまく行くのか?弟が長男に結(jié)果を伝えるのにも時(shí)間がかかるはず

?通信伝えるタイミングを合わせる必要もあるはず

?同期各自の計(jì)算時(shí)間が均等になるとは限らない

(計(jì)算能力の違い，計(jì)算の難しさの違い)

?タスク分割?スケジューリング並列処理効果の向上には上記問題の解決が必要並列処理効果を阻害する要因逐次処理では必要無かった処理が発生並列処理のためのコンピュータマルチプロセッサ（SMT)

プロセッサを複數(shù)備えた単一のコンピュータ/CPUクラスタ

高速LANで結(jié)合されたコンピュータ群Grid

インターネットで接続されたコンピュータ群

ほとんどのハイエンドコンピュータは並列構(gòu)成パソコンレベルでもマルチプロセッサ構(gòu)成並列コンピュータシームレスコンピューティング並列処理のためのコンピュータ並列コンピュータシームレスコンピ講義內(nèi)容並列処理はいっそう身近にまた重要なものとなってきている本講義では並列処理に関しておもにソフトウエアの視點(diǎn)から現(xiàn)狀と今後の可能性と課題を探る並列(分散)システム並列コンピュータモデル並列実行方式並列プログラム/プログラミング並列化コンパイラ講義內(nèi)容並列処理はいっそう身近にまた重要なものとなってきてい並列?分散システムの概要并列諸理論2第二回課件システムの並列?分散化システムの並列?分散化並列?分散システムの形態(tài)ハードウェアソフトウェアシステムの並列?分散化システムの並列?分散化集中と並列?分散並列?分散の形態(tài)機(jī)能並列?分散業(yè)務(wù)並列?分散地理的並列?分散例)計(jì)算機(jī)センター計(jì)算専用マシンとグラフィックス専用マシン研究用と事務(wù)用センターと研究室集中と並列?分散並列?分散の形態(tài)集中と並列?分散並列?分散化の動(dòng)機(jī)処理性能

専用化による高性能化

並列処理による高性能化

処理の局所性による高性能化拡張性(スケーラビリティ)信頼性?可用性etc.集中と並列?分散並列?分散化の動(dòng)機(jī)並列?分散システム並列?分散システム

「分散された多數(shù)のコンピュータ(プロセッサ)が相互通信(結(jié)合)網(wǎng)を用いて互いに密に通信し，協(xié)調(diào)しながら並列に動(dòng)作する」並列?分散システムの特徴並行?並列性スケーラビリティ開放性フォールトトレラント性資源共有透過性並列?分散システム並列?分散システム

「分散された多數(shù)のコン並列?分散システム並行?並列性異なる仕事の同時(shí)処理単一の仕事の分割同時(shí)処理並列?分散システム並行?並列性並列?分散システム並行?並列性異なる仕事の同時(shí)処理単一の仕事の分割同時(shí)処理並列?分散システム並行?並列性並列?分散システムスケーラビリティシステム規(guī)模拡大の容易性ボトルネックやホットスポットを作らない並列?分散システムスケーラビリティ並列?分散システム開放性既存機(jī)能の利用や機(jī)能追加の容易性インターフェースの公開?標(biāo)準(zhǔn)化高い拡張性，マルチベンダ，インターオペラビリティ並列?分散システム開放性並列?分散システムフォールトトレラント性/アベイラビリティハードウェア冗長性ソフトウェア回復(fù)性並列?分散システムフォールトトレラント性/アベイラビリティ並列?分散システムフォールトトレラント性/アベイラビリティハードウェア冗長性ソフトウェア回復(fù)性並列?分散システムフォールトトレラント性/アベイラビリティ並列?分散システム資源共有資源管理プロセス(サーバ)と資源利用プロセス(クライアント)の明確化

→クライアント/サーバモデルサーバサーバクライアントクライアント並列?分散システム資源共有サーバサーバクライアントクライア並列?分散システム透過性

シングルシステムイメージの提供アクセス透過性

近くの対象と遠(yuǎn)隔の対象を同じ操作でアクセス可能位置透過性

対象物がどこに存在しているかを意識(shí)しなくてよい

%cp/home/user1/filemyfile

%rcp

remotehost:/home/user1/filemyfileネットワーク透過性並列?分散システム透過性

シングルシステムイメージの提供ネッ並列?分散システム透過性並行透過性

操作を同時(shí)並行に行っても問題が起きない複製透過性

情報(bào)などを複製しても問題が起きない並列?分散システム透過性並列?分散システム透過性故障透過性

故障が生じてもシステムが稼動(dòng)し続ける移動(dòng)透過性

情報(bào)を移動(dòng)させても影響を受けない並列?分散システム透過性並列?分散システム透過性故障透過性

故障が生じてもシステムが稼動(dòng)し続ける移動(dòng)透過性

情報(bào)を移動(dòng)させても影響を受けない並列?分散システム透過性並列?分散システム透過性性能透過性

性能向上のためにシステムの再構(gòu)築が可能規(guī)模透過性

システムの規(guī)模を簡単に拡張できる並列?分散システム透過性並列?分散システム並列?分散システム構(gòu)築の際の代表的な課題高性能?高信頼な通信?同期負(fù)荷の適切な分割?配置(負(fù)荷分散)資源の位置透過な名前付け

大域的な名前から通信に必要な識(shí)別子への変換ソフトウェア構(gòu)造の開放性一貫性の維持

資源の分散と処理の並行性により矛盾が生じないようにする並列?分散システム並列?分散システム構(gòu)築の際の代表的な課題並列?分散システムの構(gòu)成并列諸理論2第二回課件マルチプロセッサ(SMP)プロセッサを複數(shù)備えた(単體の)計(jì)算機(jī)バスやスイッチなど高速の結(jié)合網(wǎng)単一のOSクラスタシステム(分散メモリマルチプロセッサ)LAN(Gbps)で結(jié)合された計(jì)算機(jī)群個(gè)別のOSGridWAN(インターネット)に接続された(地理的に離れた)計(jì)算機(jī)群ヘテロジニアスな環(huán)境並列?分散システムの種類マルチプロセッサ(SMP)並列?分散システムの種類並列?分散システムの分類主記憶の形態(tài)(メモリモデル)=プロセッサの結(jié)合形態(tài)から3つに分類共有メモリ型分散メモリ型分散共有メモリ型並列?分散システムの分類主記憶の形態(tài)(メモリモデル)=プロセ共有メモリ型複數(shù)のプロセッサがバス/スイッチ経由等で単一の主記憶(共有メモリ)に接続される形態(tài)SMP(SymmetricalMulti-Processor)

(SharedMemoryMulti-Processor)密結(jié)合マルチプロセッサUMA(UniformMemoryAccess)メモリアクセス遅延が一定Pentiumマルチプロ

セッサなどCPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶共有メモリ型複數(shù)のプロセッサがバス/スイッチ経由等で単一の主通信時(shí)間が低いメモリモデルが簡単：(物理)単一アドレス空間

→プログラムしやすい通信はメモリ書込み?読出し

v.s.「陽」な通信主記憶や相互結(jié)合ネットワークの混雑

→スケーラビリティが低い

プロセッサ數(shù)は數(shù)十程度実際にはメモリがCPU

ボードに分散している

ものもあるCPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶共有メモリ型storeload通信時(shí)間が低いCPUCPUCPUCPU相互結(jié)合ネットワCPU0:sum0=a(0)+a(1)+a(2);CPU1:sum1=a(3)+a(4)+a(5);CPU2:sum2=a(6)+a(7)+a(8); sum=sum0+sum1+sum2;CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶a(),sum0,sum1,sum2,sumレーシングが発生するため実際には同期が必要共有メモリ型CPU0:sum0=a(0)+a(1)+a(2);CPUC分散メモリ型主記憶がローカルメモリとして各プロセッサに分散

他のプロセッサからは直接アクセスできない入出力チャネルや通信ポートを介してアクセスデータ通信には必ず相手プロセッサの介在が必要ローカリティを利用してデータを上手に分散すれば主記憶のアクセス競合もない高いスケーラビリテ?！笠?guī)模システム構(gòu)築可能Grid，PCクラスタ

など

CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶sendreceive分散メモリ型主記憶がローカルメモリとして各プロセッサに分散

通信はOSやライブラリ経由メッセージパッシングモデル

→プログラミングが複雑ソフトウェアで共有メモリ(仮想?yún)g一アドレス空間)を提供するアプローチもあるソフトウェア分散共有メモリCPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶分散メモリ型通信はOSやライブラリ経由CPUCPUCPUCPUCPU0:sum0=a(0)+a(1)+a(2); send(CPU2,sum0);CPU1:sum1=a(3)+a(4)+a(5); send(CPU2,sum1);CPU2:sum2=a(6)+a(7)+a(8); receive(CPU0,tmp0); receive(CPU1,tmp1); sum=tmp0+tmp1+sum2;CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶分散メモリ型CPU0:sum0=a(0)+a(1)+a(2);CPUC分散共有メモリ型主記憶は各プロセッサに分散

他のプロセッサからもアクセス可能NUMA(NonuniformMemoryAccess)ccNUMA(cache-coherentNUMA)主記憶アクセス時(shí)間は不均一分散メモリ型との境は不明確

CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶write分散共有メモリ型主記憶は各プロセッサに分散

他のプロセッサか大規(guī)模システム構(gòu)築可能ハードウェアによるリモートアドレス変換で単一アドレス空間を提供するものもあるSGIOriginなどCPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶分散共有メモリ型大規(guī)模システム構(gòu)築可能CPUCPUCPUCPUCPU0:sum0=a(0)+a(1)+a(2); write(CPU2:tmp0,sum0);CPU1:sum1=a(3)+a(4)+a(5); write(CPU2:tmp1,sum1);CPU2:sum2=a(6)+a(7)+a(8); sum=tmp0+tmp1+sum2;CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶実際には同期が必要分散共有メモリ型CPU0:sum0=a(0)+a(1)+a(2);CPUC通信機(jī)構(gòu)并列諸理論2第二回課件通信機(jī)構(gòu)共有メモリによる通信機(jī)構(gòu)同一メモリロケーションへの同時(shí)アクセスはハードウェアで排他制御される同一プロセッサでの読出し/書込みはプログラムの順序で実行されるものとする

メモリコンシステンシモデル通信機(jī)構(gòu)共有メモリによる通信機(jī)構(gòu)通信機(jī)構(gòu)メッセージパッシングによる通信機(jī)構(gòu)send/receivesend:送信データの格納場所と受信者の指定receive送信者と受信データの格納場所の指定通信機(jī)構(gòu)メッセージパッシングによる通信機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)同期通信ブロッキングsend

ブロッキングreceivesend先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)同期通信ブロッキングsend

ブロッキングreceivereceive先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)送信側(cè)システムバッファ有同期通信ブロッキングsend

ブロッキングreceivesend先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)送信側(cè)システムバッファ有同期通信ブロッキングsend

ブロッキングreceivereceive先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)送信側(cè)システムバッファ有非同期通信ノン?ブロッキングsend

ブロッキングreceivesend先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)送信側(cè)システムバッファ有非同期通信ノン?ブロッキングsend

ブロッキングreceivereceive先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)受信側(cè)システムバッファ有非同期通信ノン?ブロッキングsend

ノン?ブロッキングreceivereceive先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)ブロッキング?ノンブロッキングブロッキングsend:

バッファデータが送信(もしくは他の場所にコピー)されるまで，送り手が待ち狀態(tài)ノンブロッキングsend:

バッファデータの狀況にかかわらず送信指示の後すぐに次の処理へ同期?非同期の別の解釈同期send:

受信されるまで待ち狀態(tài)になる非同期send:

受信を待たないsend/receive通信機(jī)構(gòu)ブロッキング?ノンブロッキン集団通信集団通信：マルチキャスト

ブロードキャスト

v.s.ユニキャスト集団通信集団通信：集団通信ブロードキャストのアトミシティ保障の問題アトミシティ：全員にメッセージが屆くか全員にメッセージが屆かないかのいずれかメッセージ到著順の一貫性の保障の問題集団通信ブロードキャストのアトミシティ保障の問題RemoteProcedureCall遠(yuǎn)隔手続き呼出(RPC)要求応答プロトコルを手続き呼出の形で実裝データ抽象化とソフトのモジュラリティが向上クライアント/サーバ間通信の要求応答プロトコルクライアント：サーバに要求メッセージ送信，応答メッセージを待つ

サーバ：要求された操作を?qū)g行後，応答メッセージを返送サーバ上の手続きを遠(yuǎn)隔呼出，戻り値を待つ手続きを?qū)g行し戻り値を返送RemoteProcedureCall遠(yuǎn)隔手続き呼出(RRPCの機(jī)構(gòu)クライアントスタブ手続きクライアントでの手続き呼出をサーバに対する遠(yuǎn)隔手続き呼び出しに変換

引數(shù)をメッセージに詰める(マーシャリング)応答メッセージのアンマーシャリングサーバスタブ手続きクライアントからの遠(yuǎn)隔呼出に対応する手続きを呼び出す

引數(shù)のアンマーシャリング戻り値のマーシャリングRPCの機(jī)構(gòu)クライアントスタブ手続きRPCの機(jī)構(gòu)RPCの例クライアントマシンサーバマシンクライアントクライアントスタブクライアントプロセスn=sum(2,5)sum25サーバスタブsumサーバプロセス7=2+5sum2577n=77カーネルカーネルRPCの機(jī)構(gòu)RPCの例クライアントマシンサーバマシンクライアRPCの機(jī)構(gòu)スタブの生成インターフェース定義言語(IDL)

サーバの手続きのインターフェース(手続き名，入力引數(shù)，戻り値)を記述インタフェースコンパイラ

クライアントスとサーバのスタブ手続きを生成バインディング手続きから通信識(shí)別子(ソケットアドレス)への対応付けRPCの機(jī)構(gòu)スタブの生成同期機(jī)構(gòu)并列諸理論2第二回課件複數(shù)プログラム(プロセス)が「互いに密に通信し，協(xié)調(diào)しながら」動(dòng)作し正しい結(jié)果を得る

→プロセス間での実行順序の調(diào)整が必要同期條件同期(point-to-pointevent)バリア同期(globalevent)相互排除同期を?qū)g現(xiàn)する基本要素許可の獲得許可の譲渡許可の獲得待ち(busywaitingvs.blocking)同期複數(shù)プログラム(プロセス)が「互いに密に通信し，協(xié)調(diào)しながら條件同期あるプロセスが他のプロセスによってある條件が満たされるまで待つように制御すること條件同期wait(p0)p1p0post(p1)wait(p0)p1p0post(p1)wait(p0)wait(p0)條件同期條件同期wait(p0)p1p0post(p1)wa條件同期フラグのセットとテストでの単純な実現(xiàn)

(共有変數(shù)型)

flag0=0;flag1=0;CPU0:sum0=a(0)+a(1)+a(2);

flag0=1;CPU1:sum1=a(3)+a(4)+a(5);

flag1=1;CPU2:sum2=a(6)+a(7)+a(8);

while(flag0==0);

while(flag1==0);

sum=sum0+sum1+sum2;條件同期フラグのセットとテストでの単純な実現(xiàn)

(共有変バリア同期ある地點(diǎn)(バリアポイント)に全プロセッサが到達(dá)するまで次の処理に進(jìn)めないように制御バリア同期barrierp1p0barrierbarrierp3p2barrierbarrierbarrierbarrierbarrierバリア同期バリア同期barrierp1p0barrierbaバリア同期フラグのセットとテストによる?yún)g純な実現(xiàn)

flag0=0;flag1=0;flag2=0;CPU0:…

flag0=1;

while(flag0*flag1*flag2==0);CPU1:…

flag1=1;

while(flag0*flag1*flag2==0);CPU2:…

flag2=1;

while(flag0*flag1*flag2==0);実際にはバリアを繰返す際の再初期化が必要バリア同期フラグのセットとテストによる?yún)g純な実現(xiàn)バリア同期効率よいバリア同期の実現(xiàn)フラグやカウンタによる?yún)g純な方法では変數(shù)アクセスが集中しボトルネックとなってしまう変數(shù)へのアクセスの分散化コンバイニング?ツリー方式トーナメント方式ツリー方式バリア同期効率よいバリア同期の実現(xiàn)相互排除(mutualexclusion)複數(shù)プロセスが共有資源(変數(shù)/ハードウェア)にアクセスする際，同時(shí)アクセス可能なプロセス數(shù)を制御すること相互排除が必要となる処理を「クリティカルセクション」と呼ぶ相互排除同期相互排除(mutualexclusion)相互排除同期相互排除(mutualexclusion)相互排除同期Enterp1p0p2ExitEnterExitEnterCSCSCS相互排除(mutualexclusion)相互排除同期EnCPU0:sum0=a(0)+a(1)+a(2);CPU1:sum1=a(3)+a(4)+a(5);CPU2:sum2=a(6)+a(7)+a(8);

sum=sum0+sum1+sum2;

CPU0:sum0=a(0)+a(1)+a(2);

sum=sum+sum0;CPU1:sum1=a(3)+a(4)+a(5);

sum=sum+sum1;CPU2:sum2=a(6)+a(7)+a(8);

sum=sum+sum2;相互排除同期の必要性sumの更新は

相互排除して

行う必要がある(なぜか?)各プロセッサがsumを更新するよう変更CPU0:sum0=a(0)+a(1)+a(2);相互排除相互排除の基本要件安全性：

クリティカルセクションに入れるプロセスはひとつだけ活動(dòng)性：

クリティカルセクションに入ることを要求するプロセスはいずれその権利を得る順序性

クリティカルセクションに入る順序は要求発行順序でなくてはならない相互排除の基本要件安全性：

クリティカルセクションに入れるプlock/unlockによる相互排除の実現(xiàn)クリティカルセクションに入る前にlock，出た後にunlocklock命令：lockの狀態(tài)でなければl(wèi)ock狀態(tài)とし次命令に移る

さもなければl(wèi)ock狀態(tài)解除まで待機(jī)複數(shù)のプロセスが同時(shí)にlock命令発行場合

ひとつのプロセスのみlockに成功

他プロセスはlock狀態(tài)解除まで待機(jī)unlock命令：lock狀態(tài)を解除するロック変數(shù)(同期変數(shù))と共にlock(v)/unlock(v)とする

→複數(shù)のlock/unlockを區(qū)別するため，lock/unlockによる相互排除の実現(xiàn)クリティカルセクシlock/unlockによる相互排除の実現(xiàn)CPU0:sum0=a(0)+a(1)+a(2);

lock(v);

sum=sum+sum0;

unlock(v);CPU1:sum1=a(3)+a(4)+a(5);

lock(v);

sum=sum+sum1;

unlock(v);CPU2:sum2=a(6)+a(7)+a(8);

lock(v); sum=sum+sum2;

unlock(v);lock/unlockによる相互排除の実現(xiàn)CPU0:sumハードウェア同期機(jī)構(gòu)による相互排除の実現(xiàn)共有変數(shù)flagをロック変數(shù)としてlockを?qū)g現(xiàn)してみる

flagを0に初期化

lock-loop:ld$r1,flag

bne$r1,$zero,lock-loop

st$one,flag

クリティカルセクション

unlock:st$zero,flagこれでちゃんと動(dòng)作する?ハードウェア同期機(jī)構(gòu)による相互排除の実現(xiàn)共有変數(shù)flagをロハードウェア同期機(jī)構(gòu)lock-loop:ld$r1,flag

bne$r1,$zero,lock-loop

st$one,flagldの実行後stの完了までに他プロセスがldを?qū)g行してしまう可能性ld$r1,flagbne$r1,$zero,...st$one,flag$r1

ld$r1,flagbne$r1,$zero,...st$one,flag$r1

flag0001ハードウェア同期機(jī)構(gòu)lock-loop:ld$r1,fハードウェア同期機(jī)構(gòu)ldとstが不可分に実行されなければならないread-modify-write命令の必要性lock-loop:ld$r1,flag不可分命令

st$one,flag

bne$r1,$zero,lock-loop

ld$r1,flagbne$r1,$zero,...st$one,flag$r1

ld$r1,flagbne$r1,$zero,...st$one,flag$r1

flag0011ld$r1,flagst$one,flagハードウェア同期機(jī)構(gòu)ldとstが不可分に実行されなければならハードウェア同期機(jī)構(gòu)Test&SetTest&Set命令

lock-loop:ts$r1,flag{$r1←flag;flag←1}

bne$r1,$zero,lock-loopbusywaitingbusywaitingによるロックの実現(xiàn)：spinlockspinlockではスピンしている間プロセッサは実行時(shí)間を浪費(fèi)相互結(jié)合網(wǎng)や共有メモリへのアクセスが増加特に上記のts命令では毎回書き込みもある！対策backoff：tsの頻度を下げるtestandTest&Setハードウェア同期機(jī)構(gòu)Test&SetTest&Seハードウェア同期機(jī)構(gòu)Test&Setサスペンドロック(suspendlock),ブロック

ロック獲得に失敗

→unlockされるまで実行を中斷(スリープ)して待機(jī)Test&Setから派生した命令swapfetch&opfetch&incrementfetch&decrementfetch&addcompare&swapLoad-Locked,Sotre-Conditionaletc.ハードウェア同期機(jī)構(gòu)Test&Setサスペンドロック(10ハードウェア同期機(jī)構(gòu)Compare&SwapCompare&Swap命令

cs$r1,$r2,flag{temp←flag;

iftemp==$r1then

{flag←$r2;$cc←1}

else

{$r1←temp;$cc←0}

}cs$r1,$r2,flag$r1

10flag20

$r2

20$cc

1

temp

10

==10ハードウェア同期機(jī)構(gòu)Compare&SwapCom10ハードウェア同期機(jī)構(gòu)Compare&SwapCompare&Swap命令

cs$r1,$r2,flag{temp←flag;

iftemp==$r1then

{flag←$r2;$cc←1}

else

{$r1←temp;$cc←0}

}cs$r1,$r2,flag$r1

30flag10

$r2

20$cc

0

temp

10

<>10ハードウェア同期機(jī)構(gòu)Compare&SwapComハードウェア同期機(jī)構(gòu)Compare&Swapカウンタ更新の例

変數(shù)sumを複數(shù)のプロセスが更新Test&Setで実現(xiàn)すると

lock-loop:ts$r1,flag

bne$r1,$zero,lock-loop

ld$r1,sum

add$r2,$r1,$sum0

st$r2,sum

st$zero,flagハードウェア同期機(jī)構(gòu)Compare&Swapカウンタ更新ハードウェア同期機(jī)構(gòu)Compare&Swapカウンタ更新の例Compare&Swapで実現(xiàn)

ld$r1,sum

loop:add$r2,$r1,$sum0

cs$r1,$r2,sum

be$cc,$zero,loopCompare&Swap命令

cs$r1,$r2,sum{temp←sum;

iftemp==$r1then

{sum←$r2;$cc←1}

else

{$r1←temp;$cc←0}

}ldの時(shí)のsumの値は

そのままかな?

そのままなら$r2を，

変更されてたら$r1を

sumにストアハードウェア同期機(jī)構(gòu)Compare&Swapカウンタ更新add$r2,$r1,$sum0be$cc,$zero,loopハードウェア同期機(jī)構(gòu)Compare&Swapカウンタ更新の例Compare&Swapで実現(xiàn)

ld$r1,sum

loop:add$r2,$r1,$sum0

cs$r1,$r2,sum

be$cc,$zero,loopldの時(shí)のsumの値は

そのままかな?

そのままなら$r2を、

変更されてたら$r1を

sumにストア10cs$r1,$r2,sum$r1

10

sum15$r2

$cc

1

temp

10

==5

$sum015ld$r1,sumadd$r2,$r1,$sum0be$cc,$zeadd$r2,$r1,$sum0be$cc,$zero,loopハードウェア同期機(jī)構(gòu)Compare&Swapカウンタ更新の例Compare&Swapで実現(xiàn)

ld$r1,sum

loop:add$r2,$r1,$sum0

cs$r1,$r2,sum

be$cc,$zero,loopldの時(shí)のsumの値は

そのままかな?

そのままなら$r2を、

変更されてたら$r1を

sumにストア10cs$r1,$r2,sum$r1

10

sum$r2

$cc

0

temp

30

<>5

$sum015ld$r1,sum30

30

35add$r2,$r1,$sum0be$cc,$zeLoad-Locked,Sotre-Conditionalカウンタ更新の例LL&SCで実現(xiàn)

loop:ll$r1,sum

add$r1,$sum0

sc$r1,sum

bez$cc,loopsumにll以降書き込みはされてないかな?

されてなければ$r1を、

sumにストア($cc=1)さされてたら($cc=0)lock-loop:ll$r1,flag

bnez$r1,lock-loop

sc$one,flagbeq$cc,lock-loopunlock:st$zero,flagLoad-Locked,Sotre-Conditionalセマフォによる相互排除lock/unlockに相當(dāng)する二つの操作P(s)操作/V(s)操作：sはセマフォ変數(shù)T.H.E.オペレーティングシステムbyダイクストラで提案されたプロセス間同期機(jī)構(gòu)semaphore：のろしや腕木信號(hào)P:オランダ語のpasseren(パスする)またはproberen(試す)とverlagen(減らす)の造語prolagenからV:verhogen(増加させる)あるいはvrygeven(開放する)から

と言われている．

[1]E.W.Dijkstra,SolutionofaProbleminConcurrentProgrammingControl,CommunicationsoftheACM,Vol.8,Sep.pp.569-578,1965.セマフォによる相互排除lock/unlockに相當(dāng)する二つのP(s)操作

loop:ifs>0thens=s-1としてCSに入る;

elsegotoloop;V(s)操作

s=s+1としCSから出る;sは同時(shí)にCSに入れるプロセス數(shù)に初期化sに対する操作自體も當(dāng)然相互排除が必要セマフォによる相互排除P(s)操作

loop:ifs>0thens=s-サスペンドロックとする場合P(s)操作

ifs>0thens=s-1;

elseこのプロセスを休止?fàn)顟B(tài)にし,

sに対応するキューに入れる；V(s)操作

if(sに対応するキューにプロセスがある)

thenプロセスのひとつを?qū)g行可能狀態(tài)にする;

elses=s+1;セマフォによる相互排除サスペンドロックとする場合セマフォによる相互排除P(s)操作/V(s)操作

P(s)p1p0p2V(s)P(s)V(s)P(s)queues

1p0p2V(s)0p2セマフォによる相互排除P(s)操作/V(s)操作

P(s)p1p0p2V(sP(s)操作/V(s)操作による條件同期

P(s)p1消費(fèi)者p0生産者V(s)sp10V(s)P(s)10queueセマフォによる相互排除P(s)操作/V(s)操作による條件同期

P(s)p1同期共有メモリ無し＋共有時(shí)計(jì)無し異なるマシン上でのイベントAとBの生起の時(shí)刻や生起の順序関係を知ることも容易ではない時(shí)計(jì)の「同期」(時(shí)刻あわせ)：一定精の度內(nèi)でそれぞれの時(shí)計(jì)は時(shí)刻がずれている

時(shí)刻の進(jìn)むペースもずれている外部同期：システム外部の時(shí)計(jì)(例：UTC)との同期內(nèi)部同期：システム內(nèi)のマシンがお互いに同期物理時(shí)計(jì)と論理時(shí)計(jì)同期共有メモリ無し＋共有時(shí)計(jì)無し時(shí)計(jì)合わせ物理時(shí)計(jì)を同期させる方式クリスチャンのアルゴリズム(外部?內(nèi)部同期)バークレイアルゴリズム（內(nèi)部同期)NTP(NetworkTimeProtocol)クリスチャン(Cristian)のアルゴリズム

マシンAマシンB時(shí)刻要求Ts時(shí)刻回答tTrt時(shí)計(jì)をt+(Tr-Ts)/2に設(shè)定時(shí)計(jì)合わせ物理時(shí)計(jì)を同期させる方式マシンAマシンB時(shí)刻要求T時(shí)計(jì)合わせバークレイアルゴリズム（內(nèi)部同期)特定のマシン(マスタ)が他のマシン(スレーブ)の時(shí)刻を問い合わせ(クリスチャンの方法)すべてのマシンの時(shí)刻の平均値をスレーブに通達(dá)NTP(NetworkTimeProtocol)広域ネットワークに時(shí)刻情報(bào)を配布する木構(gòu)造のサーバ間で互いに時(shí)刻合わせ

マルチキャストモード，手続き呼出モード，対稱モード時(shí)計(jì)合わせバークレイアルゴリズム（內(nèi)部同期)論理時(shí)計(jì)論理時(shí)計(jì)物理時(shí)計(jì)を完全に同期させるのは不可能イベントの正確な順序関係はきわめて重要関連するイベントの生起の順序づけを可能とする先行生起(happened-before)の概念同一プロセス內(nèi)で生起した二つのイベント(a,b)

順序付け可能(a→b)プロセス間でのメッセージ通信イベント

送信イベント(a)は受信イベント(b)より先に生起(a→b)a→bかつb→cならばa→c論理時(shí)計(jì)論理時(shí)計(jì)論理時(shí)計(jì)Lamportの論理時(shí)計(jì)方式先行生起順序を簡単な數(shù)値で表現(xiàn)各プロセスは論理時(shí)計(jì)(増加カウンタC)を持つ各プロセスはイベント生起ごとにC=C+1としCをタイムスタンプとしてイベントに付與するメッセージ送信プロセス：送信イベントのタイプスタンプ(Tt)を付加して送信メッセージ受信マシン：C=max(C,Tt)+1としCを受信イベントのタイムスタンプとする全イベントはタイムスタンプにより半順序関係を與えることができる論理時(shí)計(jì)Lamportの論理時(shí)計(jì)方式論理時(shí)計(jì)Lamportの論理時(shí)計(jì)方式31343536444546501011123347495051P0P2P1X/33X/49X/52timeX++X++X++32524853自分でのXの最終更新(32)より後に更新されたものであることがわかるX：共有変數(shù)

排他????論理時(shí)計(jì)Lamportの論理時(shí)計(jì)方式313435364445相互排除サーバによる集中方式合意による分散方式トークンリング方式相互排除での基本的な動(dòng)作クリティカルセクション(CS)に入りたいという要求発行CSに入る許可を與えるCSに入るCSから出るCSから出たことを通知する相互排除サーバによる集中方式相互排除：サーバによる集中方式CSへ入る権利の要求の受付とCSへ入る許可の発行をサーバが一括管理サーバが性能ボトルネックやsinglepointoffailureになる危険143243サーバ要求キュー24相互排除：サーバによる集中方式CSへ入る権利の要求の受付とC相互排除：合意による分散方式プロセス間で合意を形成しながら順次CSに入るCSへ入ろうとするプロセスPiの動(dòng)作：タイムスタンプTiを付加した要求メッセージ(Pi,Ti)を他の全プロセスに送信他の全プロセスからOKが返送されるまで待ち，返送されたらCSに入るCSから出る際キューの全要求に対してOKを返送相互排除：合意による分散方式プロセス間で合意を形成しながら順相互排除：合意による分散方式プロセスPjが要求メッセージを受信したした際の動(dòng)作：CSの外であり入る要求もしていない：

OKを返送CSの中にいる：

返事せず受信要求をキューに入れるCSの外で入る要求をしている：

Tj>TiならOKを返送，そうでないなら返事せず受信要求をキューに入れるメッセージが多い，すべてのプロセスが関與しなくてはならないなどの理由からサーバによる一括管理と同程度の性能しか得られない相互排除：合意による分散方式プロセスPjが要求メッセージを受相互排除：合意による分散方式プロセス間で合意を形成しながら順次CSに入る

動(dòng)作例１1020/80/80/8OKOK02/92/92OK0OK2/9相互排除：合意による分散方式プロセス間で合意を形成しながら順相互排除：合意による分散方式プロセス間で合意を形成しながら順次CSに入る

動(dòng)作例21020/80/80/82/122/1202OKOKOK0OK2/12相互排除：合意による分散方式プロセス間で合意を形成しながら順相互排除：トークンリングによる分散方式プロセス間にひとつのトークンを巡回させるCSに入るつもりがなければ次のプロセスにトークンをまわすCSに入る要求があるプロセスはトークンが回ってきたときのみにトークンを保持したままCSに入るCSから出たらトークンを次のプロセスにまわす相互排除：トークンリングによる分散方式プロセス間にひとつのト選出サーバなど特定の役割のプロセスが障害を起こした際，殘ったプロセスから新たにサーバを選出する仕組み前提：各プロセスは一意のIDを持っているどのプロセスが稼動(dòng)していてどのプロセスが障害を起こしているかは知らない問題：稼動(dòng)しているプロセスの中でもっとも大きなIDを持つものを選出する選出サーバなど特定の役割のプロセスが障害を起こした際，殘った選出：ブリーアルゴリズム各プロセスは他のプロセスのIDを知っているとするサーバ障害を検知したプロセスは選出動(dòng)作を行う：

[選出動(dòng)作]自分より高いIDのプロセスに選出メッセージを送付し応答メッセージを待つもし誰も応答しないならば自分がサーバとなり調(diào)整者メッセージをすべてのプロセスに送付するひとつでも応答があれば調(diào)整者メッセージを待つ選出：ブリーアルゴリズム各プロセスは他のプロセスのIDを知っ選出：ブリーアルゴリズム選出メッセージを受信したプロセス 応答メッセージを送付する選出動(dòng)作を行う調(diào)整者メッセージを受信したプロセス送信元を新たなサーバとする40736512選出メッセージ応答メッセージ選出メッセージ応答メッセージ6調(diào)整者メッセージ選出：ブリーアルゴリズム選出メッセージを受信したプロセス 4選出：リングアルゴリズム各プロセスは他のプロセスのIDを知らない全プロセスはメッセージを巡回させる順番を知っているサーバ障害を検知したプロセス選出メッセージに自IDを付加し下流のプロセス(無反応のプロセスはスキップ）に送付戻ってきた選出メッセージよりID最大の物をサーバに選出し，選出済みメッセージとして再度巡回させる選出メッセージを受信したプロセス選出メッセージに自IDを付加し下流プロセスに送付選出済みメッセージを受信したプロセス選出されたサーバを知る選出：リングアルゴリズム各プロセスは他のプロセスのIDを知ら選出：リングアルゴリズムリングアルゴリズム4101731591113選出メッセージ15選出済みメッセージ44134131115選出：リングアルゴリズムリングアルゴリズム410173159ロックが空いている場合に低レイテンシでロックが獲得できるほうが望ましいbusywaitしている際にトラフィックを増やさないほうが望ましいロックが解除されたらすぐに待っていたプロセスがロックを獲得できるほうが望ましいロック獲得が公平であることが必要クリティカルセクションはできるだけ小さく相互排除のオーバーヘッドロックが空いている場合に低レイテンシでロックが獲得できるほう並列処理とは並列処理：

一つの仕事を分割して複數(shù)プロセッサで同時(shí)に処理並列処理の目的処理時(shí)間の短縮(処理速度の向上)

一つの仕事の処理(レスポンスタイム向上)

複數(shù)の仕事の処理(スループット向上)耐故障性の向上処理速度の向上最速のプロセッサを使って最高速を目指す安価なプロセッサを使って高い価格性能比を目指す並列処理とは並列処理：

一つの仕事を分割して複數(shù)プロセッ並列処理の簡単な例1から9までの総和計(jì)算1人で普通に計(jì)算すると

1+2=3,3+3=6,6+4=10,…,45

加算1回=1秒とすると計(jì)算時(shí)間は8秒3人で仕事を分けて計(jì)算すると

(長男)1+2=3,3+3=6

(次男)4+5=9,9+6=15同時(shí)に計(jì)算：2秒

(三男)7+8=15,15+9=24

次男と三男は自分の結(jié)果(部分和)を長男に伝え...

(長男)6+15は21，21+24は45!2秒

計(jì)算時(shí)間は合計(jì)4秒8/4=2倍の速度向上並列処理効果並列処理の簡単な例1から9までの総和計(jì)算並列処理の簡単な例1から900までの総和計(jì)算1人で普通に計(jì)算すると

計(jì)算時(shí)間は899秒3人で仕事を分けて計(jì)算すると

各自の計(jì)算時(shí)間はそれぞれ299秒

長男での合計(jì)計(jì)算の時(shí)間は2秒計(jì)算時(shí)間は合計(jì)301秒1人での計(jì)算時(shí)間のほぼ1/3に短縮

理想的な並列処理効果一見すると幾らでもスピードアップできそうだが???並列処理の簡単な例1から900までの総和計(jì)算並列処理効果を阻害する要因逐次処理では必要無かった処理が発生してしまう

並列処理オーバーヘッド

?並列処理効果の低減総和計(jì)算の例：いつもこんなにうまく行くのか?弟が長男に結(jié)果を伝えるのにも時(shí)間がかかるはず

?通信伝えるタイミングを合わせる必要もあるはず

?同期各自の計(jì)算時(shí)間が均等になるとは限らない

(計(jì)算能力の違い，計(jì)算の難しさの違い)

?タスク分割?スケジューリング並列処理効果の向上には上記問題の解決が必要並列処理効果を阻害する要因逐次処理では必要無かった処理が発生並列処理のためのコンピュータマルチプロセッサ（SMT)

プロセッサを複數(shù)備えた単一のコンピュータ/CPUクラスタ

高速LANで結(jié)合されたコンピュータ群Grid

インターネットで接続されたコンピュータ群

ほとんどのハイエンドコンピュータは並列構(gòu)成パソコンレベルでもマルチプロセッサ構(gòu)成並列コンピュータシームレスコンピューティング並列処理のためのコンピュータ並列コンピュータシームレスコンピ講義內(nèi)容並列処理はいっそう身近にまた重要なものとなってきている本講義では並列処理に関しておもにソフトウエアの視點(diǎn)から現(xiàn)狀と今後の可能性と課題を探る並列(分散)システム並列コンピュータモデル並列実行方式並列プログラム/プログラミング並列化コンパイラ講義內(nèi)容並列処理はいっそう身近にまた重要なものとなってきてい並列?分散システムの概要并列諸理論2第二回課件システムの並列?分散化システムの並列?分散化並列?分散システムの形態(tài)ハードウェアソフトウェアシステムの並列?分散化システムの並列?分散化集中と並列?分散並列?分散の形態(tài)機(jī)能並列?分散業(yè)務(wù)並列?分散地理的並列?分散例)計(jì)算機(jī)センター計(jì)算専用マシンとグラフィックス専用マシン研究用と事務(wù)用センターと研究室集中と並列?分散並列?分散の形態(tài)集中と並列?分散並列?分散化の動(dòng)機(jī)処理性能

専用化による高性能化

並列処理による高性能化

処理の局所性による高性能化拡張性(スケーラビリティ)信頼性?可用性etc.集中と並列?分散並列?分散化の動(dòng)機(jī)並列?分散システム並列?分散システム

「分散された多數(shù)のコンピュータ(プロセッサ)が相互通信(結(jié)合)網(wǎng)を用いて互いに密に通信し，協(xié)調(diào)しながら並列に動(dòng)作する」並列?分散システムの特徴並行?並列性スケーラビリティ開放性フォールトトレラント性資源共有透過性並列?分散システム並列?分散システム

「分散された多數(shù)のコン並列?分散システム並行?並列性異なる仕事の同時(shí)処理単一の仕事の分割同時(shí)処理並列?分散システム並行?並列性並列?分散システム並行?並列性異なる仕事の同時(shí)処理単一の仕事の分割同時(shí)処理並列?分散システム並行?並列性並列?分散システムスケーラビリティシステム規(guī)模拡大の容易性ボトルネックやホットスポットを作らない並列?分散システムスケーラビリティ並列?分散システム開放性既存機(jī)能の利用や機(jī)能追加の容易性インターフェースの公開?標(biāo)準(zhǔn)化高い拡張性，マルチベンダ，インターオペラビリティ並列?分散システム開放性並列?分散システムフォールトトレラント性/アベイラビリティハードウェア冗長性ソフトウェア回復(fù)性並列?分散システムフォールトトレラント性/アベイラビリティ並列?分散システムフォールトトレラント性/アベイラビリティハードウェア冗長性ソフトウェア回復(fù)性並列?分散システムフォールトトレラント性/アベイラビリティ並列?分散システム資源共有資源管理プロセス(サーバ)と資源利用プロセス(クライアント)の明確化

→クライアント/サーバモデルサーバサーバクライアントクライアント並列?分散システム資源共有サーバサーバクライアントクライア並列?分散システム透過性

シングルシステムイメージの提供アクセス透過性

近くの対象と遠(yuǎn)隔の対象を同じ操作でアクセス可能位置透過性

対象物がどこに存在しているかを意識(shí)しなくてよい

%cp/home/user1/filemyfile

%rcp

remotehost:/home/user1/filemyfileネットワーク透過性並列?分散システム透過性

シングルシステムイメージの提供ネッ並列?分散システム透過性並行透過性

操作を同時(shí)並行に行っても問題が起きない複製透過性

情報(bào)などを複製しても問題が起きない並列?分散システム透過性並列?分散システム透過性故障透過性

故障が生じてもシステムが稼動(dòng)し続ける移動(dòng)透過性

情報(bào)を移動(dòng)させても影響を受けない並列?分散システム透過性並列?分散システム透過性故障透過性

故障が生じてもシステムが稼動(dòng)し続ける移動(dòng)透過性

情報(bào)を移動(dòng)させても影響を受けない並列?分散システム透過性並列?分散システム透過性性能透過性

性能向上のためにシステムの再構(gòu)築が可能規(guī)模透過性

システムの規(guī)模を簡単に拡張できる並列?分散システム透過性並列?分散システム並列?分散システム構(gòu)築の際の代表的な課題高性能?高信頼な通信?同期負(fù)荷の適切な分割?配置(負(fù)荷分散)資源の位置透過な名前付け

大域的な名前から通信に必要な識(shí)別子への変換ソフトウェア構(gòu)造の開放性一貫性の維持

資源の分散と処理の並行性により矛盾が生じないようにする並列?分散システム並列?分散システム構(gòu)築の際の代表的な課題並列?分散システムの構(gòu)成并列諸理論2第二回課件マルチプロセッサ(SMP)プロセッサを複數(shù)備えた(単體の)計(jì)算機(jī)バスやスイッチなど高速の結(jié)合網(wǎng)単一のOSクラスタシステム(分散メモリマルチプロセッサ)LAN(Gbps)で結(jié)合された計(jì)算機(jī)群個(gè)別のOSGridWAN(インターネット)に接続された(地理的に離れた)計(jì)算機(jī)群ヘテロジニアスな環(huán)境並列?分散システムの種類マルチプロセッサ(SMP)並列?分散システムの種類並列?分散システムの分類主記憶の形態(tài)(メモリモデル)=プロセッサの結(jié)合形態(tài)から3つに分類共有メモリ型分散メモリ型分散共有メモリ型並列?分散システムの分類主記憶の形態(tài)(メモリモデル)=プロセ共有メモリ型複數(shù)のプロセッサがバス/スイッチ経由等で単一の主記憶(共有メモリ)に接続される形態(tài)SMP(SymmetricalMulti-Processor)

(SharedMemoryMulti-Processor)密結(jié)合マルチプロセッサUMA(UniformMemoryAccess)メモリアクセス遅延が一定Pentiumマルチプロ

セッサなどCPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶共有メモリ型複數(shù)のプロセッサがバス/スイッチ経由等で単一の主通信時(shí)間が低いメモリモデルが簡単：(物理)単一アドレス空間

→プログラムしやすい通信はメモリ書込み?読出し

v.s.「陽」な通信主記憶や相互結(jié)合ネットワークの混雑

→スケーラビリティが低い

プロセッサ數(shù)は數(shù)十程度実際にはメモリがCPU

ボードに分散している

ものもあるCPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶共有メモリ型storeload通信時(shí)間が低いCPUCPUCPUCPU相互結(jié)合ネットワCPU0:sum0=a(0)+a(1)+a(2);CPU1:sum1=a(3)+a(4)+a(5);CPU2:sum2=a(6)+a(7)+a(8); sum=sum0+sum1+sum2;CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶a(),sum0,sum1,sum2,sumレーシングが発生するため実際には同期が必要共有メモリ型CPU0:sum0=a(0)+a(1)+a(2);CPUC分散メモリ型主記憶がローカルメモリとして各プロセッサに分散

他のプロセッサからは直接アクセスできない入出力チャネルや通信ポートを介してアクセスデータ通信には必ず相手プロセッサの介在が必要ローカリティを利用してデータを上手に分散すれば主記憶のアクセス競合もない高いスケーラビリテ?！笠?guī)模システム構(gòu)築可能Grid，PCクラスタ

など

CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶sendreceive分散メモリ型主記憶がローカルメモリとして各プロセッサに分散

通信はOSやライブラリ経由メッセージパッシングモデル

→プログラミングが複雑ソフトウェアで共有メモリ(仮想?yún)g一アドレス空間)を提供するアプローチもあるソフトウェア分散共有メモリCPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶分散メモリ型通信はOSやライブラリ経由CPUCPUCPUCPUCPU0:sum0=a(0)+a(1)+a(2); send(CPU2,sum0);CPU1:sum1=a(3)+a(4)+a(5); send(CPU2,sum1);CPU2:sum2=a(6)+a(7)+a(8); receive(CPU0,tmp0); receive(CPU1,tmp1); sum=tmp0+tmp1+sum2;CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶分散メモリ型CPU0:sum0=a(0)+a(1)+a(2);CPUC分散共有メモリ型主記憶は各プロセッサに分散

他のプロセッサからもアクセス可能NUMA(NonuniformMemoryAccess)ccNUMA(cache-coherentNUMA)主記憶アクセス時(shí)間は不均一分散メモリ型との境は不明確

CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶write分散共有メモリ型主記憶は各プロセッサに分散

他のプロセッサか大規(guī)模システム構(gòu)築可能ハードウェアによるリモートアドレス変換で単一アドレス空間を提供するものもあるSGIOriginなどCPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶分散共有メモリ型大規(guī)模システム構(gòu)築可能CPUCPUCPUCPUCPU0:sum0=a(0)+a(1)+a(2); write(CPU2:tmp0,sum0);CPU1:sum1=a(3)+a(4)+a(5); write(CPU2:tmp1,sum1);CPU2:sum2=a(6)+a(7)+a(8); sum=tmp0+tmp1+sum2;CPUCPUCPUCPU

相互結(jié)合ネットワーク主記憶主記憶主記憶主記憶実際には同期が必要分散共有メモリ型CPU0:sum0=a(0)+a(1)+a(2);CPUC通信機(jī)構(gòu)并列諸理論2第二回課件通信機(jī)構(gòu)共有メモリによる通信機(jī)構(gòu)同一メモリロケーションへの同時(shí)アクセスはハードウェアで排他制御される同一プロセッサでの読出し/書込みはプログラムの順序で実行されるものとする

メモリコンシステンシモデル通信機(jī)構(gòu)共有メモリによる通信機(jī)構(gòu)通信機(jī)構(gòu)メッセージパッシングによる通信機(jī)構(gòu)send/receivesend:送信データの格納場所と受信者の指定receive送信者と受信データの格納場所の指定通信機(jī)構(gòu)メッセージパッシングによる通信機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)同期通信ブロッキングsend

ブロッキングreceivesend先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)同期通信ブロッキングsend

ブロッキングreceivereceive先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)送信側(cè)システムバッファ有同期通信ブロッキングsend

ブロッキングreceivesend先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)送信側(cè)システムバッファ有同期通信ブロッキングsend

ブロッキングreceivereceive先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)送信側(cè)システムバッファ有非同期通信ノン?ブロッキングsend

ブロッキングreceivesend先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)送信側(cè)システムバッファ有非同期通信ノン?ブロッキングsend

ブロッキングreceivereceive先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)受信側(cè)システムバッファ有非同期通信ノン?ブロッキングsend

ノン?ブロッキングreceivereceive先行sendreceive送信側(cè)受信側(cè)send/receive通信機(jī)構(gòu)send/receive機(jī)構(gòu)send/receive通信機(jī)構(gòu)ブロッキング?ノンブロッキングブロッキングsend:

バッファデータが送信(もしくは他の場所にコピー)されるまで，送り手が待ち狀態(tài)ノンブロッキングsend:

バッファデータの狀況にかかわらず送信指示の後すぐに次の処理へ同期?非同期の別の解釈同期send:

受信されるまで待ち狀態(tài)になる非同期send:

受信を待たないsend/receive通信機(jī)構(gòu)ブロッキング?ノンブロッキン集団通信集団通信：マルチキャスト

ブロードキャスト

v.s.ユニキャスト集団通信集団通信：集団通信ブロードキャストのアトミシティ保障の問題アトミシティ：全員にメッセージが屆くか全員にメッセージが屆かないかのいずれかメッセージ到著順の一貫性の保障の問題集団通信ブロードキャストのアトミシティ保障の問題RemoteProcedureCall遠(yuǎn)隔手続き呼出(RPC)要求応答プロトコルを手続き呼出の形で実裝データ抽象化とソフトのモジュラリティが向上クライアント/サーバ間通信の要求応答プロトコルクライアント：サーバに要求メッセージ送信，応答メッセージを待つ

サーバ：要求された操作を?qū)g行後