1、1並列処理 並列処理：一仕事分割複数同時処理 並列処理目的 処理時間短縮(処理速度向上)一仕事処理(向上)複数仕事処理(向上)耐故障性向上 処理速度向上 最速使最高速目指 安価使高価格性能比目指2並列処理簡単例 19総和計算 1人普通計算1+2=3,3+3=6,6+4=10,45 加算1回=1秒 計算時間8秒 3人仕事分計算(長男)1+2=3,3+3=6(次男)4+5=9,9+6=15 同時計算：2秒(三男)7+8=15,15+9=24次男三男自分結果(部分和)長男伝.(長男)6+1521，21+2445!2秒計算時間合計4秒 8/4=2倍速度向上 並列処理効果3並列処理簡単例 1900総和計
2、算 1人普通計算計算時間899秒 3人仕事分計算各自計算時間 299秒長男合計計算時間 2秒 計算時間合計301秒 1人計算時間1/3短縮理想的並列処理効果 一見幾4並列処理効果阻害要因 逐次処理必要無処理発生並列処理並列処理効果低減 総和計算例：行?弟長男結果伝時間 通信 伝合必要 同期 各自計算時間均等限(計算能力違，計算難違)分割 並列処理効果向上上記問題解決必要5 並列処理（SMT)複数備単一/CPU 高速LAN結合群 Grid接続群 並列構成 構成並列6講義内容並列処理身近重要本講義並列処理関視点現状今後可能性課題探並列(分散)並列並列実行方式並列/並列化7並列分散概要8並列分散化
3、並列分散化 並列分散形態 9集中並列分散 並列分散形態 機能並列分散 業務並列分散 地理的並列分散 例)計算機計算専用専用研究用事務用研究室10集中並列分散 並列分散化動機 処理性能専用化高性能化並列処理高性能化処理局所性高性能化 拡張性()信頼性可用性 etc.11並列分散 並列分散分散多数()相互通信(結合)網用互密通信，協調並列動作 並列分散特徴 並行並列性 開放性 性 資源共有 透過性12並列分散 並行並列性 異仕事同時処理 単一仕事分割同時処理13並列分散 並行並列性 異仕事同時処理 単一仕事分割同時処理14並列分散 規模拡大容易性 作15並列分散 開放性 既存機能利用機能追加容易性
4、 公開標準化 高拡張性，16並列分散 性/冗長性 回復性17並列分散 性/冗長性 回復性18並列分散 資源共有 資源管理()資源利用()明確化/19並列分散 透過性提供 透過性近対象遠隔対象同操作可能 位置透過性対象物存在意識%cp/home/user1/file myfile%rcp remotehost:/home/user1/file myfile透過性20並列分散 透過性 並行透過性操作同時並行行問題起 複製透過性情報複製問題起21並列分散 透過性 故障透過性故障生稼動続 移動透過性情報移動影響受22並列分散 透過性 故障透過性故障生稼動続 移動透過性情報移動影響受23並列分散 透過性
5、 性能透過性性能向上再構築可能 規模透過性規模簡単拡張24並列分散 並列分散構築際代表的課題 高性能高信頼通信同期 負荷適切分割配置(負荷分散)資源位置透過名前付大域的名前通信必要識別子変換 構造開放性 一貫性維持資源分散処理並行性矛盾生25並列分散構成26(SMP)複数備(単体)計算機 高速結合網 単一OS(分散)LAN(Gbps)結合計算機群 個別OS Grid WAN()接続(地理的離)計算機群 環境並列分散種類27並列分散分類 主記憶形態()=結合形態3分類 共有型 分散型 分散共有型28共有型 複数/経由等単一主記憶(共有)接続形態 SMP(Symmetrical Multi-Pro
6、cessor)(Shared Memory Multi-Processor)密結合 UMA(Uniform Memory Access)遅延一定 Pentium CPUCPUCPUCPU 相互結合相互結合 主記憶主記憶29 通信時間低 簡単：(物理)単一空間 通信書込読出v.s.陽通信 主記憶相互結合混雑 低数数十程度 実際CPU分散CPUCPUCPUCPU 相互結合相互結合 主記憶主記憶共有型storeload30CPU0: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+s
7、um2;CPUCPUCPUCPU 相互結合相互結合 主記憶主記憶a(),sum0,sum1,sum2,suma(),sum0,sum1,sum2,sum発生実際同期必要共有型31分散型 主記憶各分散他直接 入出力通信介 通信必相手介在必要 利用上手分散主記憶競合 高大規模構築可能 Grid，PCCPUCPUCPUCPU 相互結合相互結合 主記憶主記憶主記憶主記憶主記憶主記憶主記憶主記憶sendreceive32 通信OS経由 複雑 共有(仮想単一空間)提供 分散共有CPUCPUCPUCPU 相互結合相互結合 主記憶主記憶主記憶主記憶主記憶主記憶主記憶主記憶分散型33CPU0:sum0=a(0)
8、+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 相互結合相互結合 主記憶主記憶主記憶主記憶主記憶主記憶主記憶主記憶分散型34分散共有型 主記憶各分散他可能 NUMA(Nonuniform Memory Access)ccNUMA(cache-coherent NUMA)主記憶時間不均一 分散型境不明確CPUCPUCPUC
9、PU 相互結合相互結合 主記憶主記憶主記憶主記憶主記憶主記憶主記憶主記憶write35 大規模構築可能 変換単一空間提供 SGI OriginCPUCPUCPUCPU 相互結合相互結合 主記憶主記憶主記憶主記憶主記憶主記憶主記憶主記憶分散共有型36CPU0: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 相互結合相互結合 主記憶主記憶主記憶主記憶主記憶主
10、記憶主記憶主記憶実際同期必要分散共有型37通信機構38通信機構 共有通信機構 同一同時排他制御 同一読出/書込順序実行39通信機構 通信機構 send/receive send:送信格納場所受信者指定 receive 送信者受信格納場所指定40send/receive通信機構 send/receive機構 同期通信 sendreceivesend先行sendreceive送信側受信側41send/receive通信機構 send/receive機構 同期通信 sendreceive receive先行sendreceive送信側受信側42send/receive通信機構 send/receiv
11、e機構送信側有 同期通信 sendreceivesend先行sendreceive送信側受信側43send/receive通信機構 send/receive機構送信側有 同期通信 sendreceivereceive先行sendreceive送信側受信側44send/receive通信機構 send/receive機構送信側有 非同期通信 sendreceivesend先行sendreceive送信側受信側45send/receive通信機構 send/receive機構送信側有 非同期通信 sendreceivereceive先行sendreceive送信側受信側46send/receive
12、通信機構 send/receive機構受信側有 非同期通信 sendreceivereceive先行sendreceive送信側受信側47send/receive通信機構 send:送信(他場所)，送手待状態 send:状況送信指示後次処理 同期非同期別解釈 同期send:受信待状態 非同期send:受信待48集団通信 集団通信：v.s.49集団通信 保障問題：全員届全員届 到着順一貫性保障問題50Remote Procedure Call 遠隔手続呼出(RPC)要求応答手続呼出形実装 抽象化向上/間通信要求応答：要求送信，応答待：要求操作実行後，応答返送上手続遠隔呼出，戻値待手続実行戻値返送
13、51RPC機構 手続 手続呼出対遠隔手続呼出変換引数詰()応答 手続 遠隔呼出対応手続呼出引数 戻値52RPC機構 RPC例n=sum(2,5)sum 2 5sum7=2+5sum 2 577n=7753RPC機構 生成 定義言語(IDL)手続(手続名，入力引数，戻値)記述 手続生成 手続通信識別子()対応付54同期機構55 複数()互密通信，協調動作正結果得間実行順序調整必要 同期 条件同期(point-to-point event)同期(global event)相互排除 同期実現基本要素 許可獲得 許可譲渡 許可獲得待(busy waiting vs.blocking)同期56 条件同期
14、 他条件満待制御条件同期wait(p0)p1p0post(p1)wait(p0)p1p0post(p1)wait(p0)wait(p0)57条件同期 単純実現(共有変数型)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;58 同期 地点()全到達次処理進制御同期barrierp1p0barrierbarrierp3p2barrierb
15、arrierbarrierbarrierbarrier59同期 単純実現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);実際繰返際再初期化必要60同期 効率同期実現 単純方法変数集中 変数分散化 方式 方式 方式61 相互排除(mutual exclusion)複数共有資源(変数/)際，同時可能数制御 相互排除必要処理呼相互排除同期62 相互排除(mutua
16、l exclusion)相互排除同期Enterp1p0p2ExitEnterExitEnterCSCSCS63CPU0: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更新変更64相互排
17、除基本要件 安全性：入 活動性：入要求権利得 順序性入順序要求発行順序65lock/unlock相互排除実現 入前lock，出後unlock lock命令：lock状態lock状態次命令移lock状態解除待機 複数同時lock命令発行場合lock成功他 lock状態解除待機 unlock命令：lock状態解除 変数(同期変数)共lock(v)/unlock(v)複数lock/unlock区別，66lock/unlock相互排除実現CPU0:sum0=a(0)+a(1)+a(2);lock(v);sum=sum+sum0;unlock(v);CPU1:sum1=a(3)+a(4)+a(5);lo
18、ck(v);sum=sum+sum1;unlock(v);CPU2:sum2=a(6)+a(7)+a(8);lock(v);sum=sum+sum2;unlock(v);67同期機構相互排除実現 共有変数flag変数lock実現 flag0初期化 lock-loop:ld$r1,flag bne$r1,$zero,lock-loop st$one,flag unlock:st$zero,flag 動作?68同期機構 lock-loop:ld$r1,flag bne$r1,$zero,lock-loop st$one,flag ld実行後st完了他ld実行可能性ld$r1,flagbne$r1,
19、$zero,.st$one,flag$r1 ld$r1,flagbne$r1,$zero,.st$one,flag$r1 flag 0 0 0 1 69同期機構 ldst不可分実行 read-modify-write命令必要性 lock-loop:ld$r1,flag 不可分命令 st$one,flag bne$r1,$zero,lock-loopld$r1,flagbne$r1,$zero,.st$one,flag$r1 ld$r1,flagbne$r1,$zero,.st$one,flag$r1 flag 0 0 1 1 ld$r1,flagst$one,flag70同期機構 Test&S
20、et Test&Set命令lock-loop:ts$r1,flag$r1flag;flag1 bne$r1,$zero,lock-loop busy waiting busy waiting実現：spin lock spin lock 間実行時間浪費 相互結合網共有増加 特上記ts命令毎回書込！対策 back off：ts頻度下 test and Test&Set 71同期機構 Test&Set(suspend lock),獲得失敗 unlock実行中断()待機 Test&Set派生命令 swap fetch&op fetch&increment fetch&decrement fetch&a
21、dd compare&swap Load-Locked,Sotre-Conditional etc.7210 同期機構Compare&Swap Compare&Swap命令cs$r1,$r2,flag tempflag;if temp=$r1 then flag$r2;$cc1else$r1temp;$cc0cs$r1,$r2,flag$r1 10 flag20$r2 20$cc 1 temp 10=7310 同期機構Compare&Swap Compare&Swap命令cs$r1,$r2,flag tempflag;if temp=$r1 then flag$r2;$cc1else$r1te
22、mp;$cc0cs$r1,$r2,flag$r1 30 flag10$r2 20$cc 0 temp 10 74同期機構Compare&Swap 更新例変数sum複数更新 Test&Set実現lock-loop:ts$r1,flag bne$r1,$zero,lock-loop ld$r1,sum add$r2,$r1,$sum0 st$r2,sumst$zero,flag75同期機構Compare&Swap 更新例 Compare&Swap実現 ld$r1,sumloop:add$r2,$r1,$sum0 cs$r1,$r2,sum be$cc,$zero,loop Compare&Swap
23、命令cs$r1,$r2,sum tempsum;if temp=$r1 then sum$r2;$cc1else$r1temp;$cc0ld時sum値?$r2，変更$r1sum76add$r2,$r1,$sum0be$cc,$zero,loop同期機構Compare&Swap 更新例 Compare&Swap実現 ld$r1,sumloop:add$r2,$r1,$sum0 cs$r1,$r2,sum be$cc,$zero,loopld時sum値?$r2、変更$r1sum10 cs$r1,$r2,sum$r1 10 sum 15$r2$cc 1 temp 10=5$sum015 ld$r1,
24、sum77add$r2,$r1,$sum0be$cc,$zero,loop同期機構Compare&Swap 更新例 Compare&Swap実現 ld$r1,sumloop:add$r2,$r1,$sum0 cs$r1,$r2,sum be$cc,$zero,loopld時sum値?$r2、変更$r1sum10 cs$r1,$r2,sum$r1 10 sum$r2$cc 0 temp 30 5$sum015 ld$r1,sum30 30 35 78Load-Locked,Sotre-Conditional 更新例 LL&SC実現loop:ll$r1,sum add$r1,$sum0sc$r1,
25、sumbez$cc,loopsumll以降書込?$r1、sum($cc=1)($cc=0)lock-loop:ll$r1,flag bnez$r1,lock-loop sc$one,flag beq$cc,lock-loopunlock:st$zero,flag79相互排除 lock/unlock相当二操作 P(s)操作/V(s)操作：s変数 T.H.E.by 提案間同期機構 semaphore：腕木信号 P:語passeren()proberen(試)verlagen(減)造語prolagen V:verhogen(増加)vrygeven(開放)言1E.W.Dijkstra,Solution
26、 of a Problem in Concurrent Programming Control,Communications of the ACM,Vol.8,Sep.pp.569-578,1965.80 P(s)操作loop:if s0 then s=s-1CS入;else goto loop;V(s)操作s=s+1CS出;s同時CS入数初期化 s対操作自体当然相互排除必要相互排除81 場合 P(s)操作if s0 then s=s-1;else 休止状態,s対応入；V(s)操作if(s対応)then 実行可能状態;else s=s+1;相互排除82 P(s)操作/V(s)操作 P(s)p1
27、p0p2V(s)P(s)V(s)P(s)queues 1 p0 p2 V(s)0 p2 相互排除83 P(s)操作/V(s)操作条件同期 P(s)p1 消費者消費者p0 生産者生産者V(s)sp1 0 V(s)P(s)1 0 queue相互排除84同期 共有無共有時計無 異上AB生起時刻生起順序関係知容易 時計同期(時刻)：一定精度内 時計時刻時刻進 外部同期：外部時計(例：UTC)同期 内部同期：内互同期 物理時計論理時計85時計合 物理時計同期方式(外部内部同期)（内部同期)NTP(Network Time Protocol)(Cristian)AB時刻要求時刻要求Ts時刻回答時刻回答 t
28、Trt時計t+(Tr-Ts)/2設定86時計合（内部同期)特定()他()時刻問合(方法)時刻平均値通達 NTP(Network Time Protocol)広域時刻情報配布 木構造間互時刻合，手続呼出，対称87論理時計 論理時計 物理時計完全同期不可能 正確順序関係重要 関連生起順序可能 先行生起(happened-before)概念 同一内生起二(a,b)順序付可能(ab)間通信送信(a)受信(b)先生起(ab)abbcac88論理時計 Lamport論理時計方式 先行生起順序簡単数値表現 各論理時計(増加C)持 各生起C=C+1C付与 送信：送信(Tt)付加送信 受信：C=max(C,Tt
29、)+1C受信 全半順序関係与89論理時計 Lamport論理時計方式31343536444546501011123347495051P0P2P1X/33X/49X/52timeX+X+X+32524853自分X最終更新(32)後更新X：共有変数 排他90相互排除 集中方式 合意分散方式 方式 相互排除基本的動作(CS)入要求発行 CS入許可与 CS入 CS出 CS出通知91相互排除：集中方式 CS入権利要求受付CS入許可発行一括管理 性能single point of failure危険143243要求2492相互排除：合意分散方式 間合意形成順次CS入 CS入Pi動作：Ti付加要求(Pi,T
30、i)他全送信 他全OK返送待，返送CS入 CS出際全要求対OK返送93相互排除：合意分散方式 Pj要求受信際動作：CS外入要求：OK返送 CS中：返事受信要求入 CS外入要求：TjTiOK返送，返事受信要求入 多，関与理由一括管理同程度性能得94相互排除：合意分散方式 間合意形成順次CS入動作例1020/80/80/8OKOK02/92/92OK0OK2/995相互排除：合意分散方式 間合意形成順次CS入動作例 21020/80/80/82/122/1202OKOKOK0OK2/1296相互排除：分散方式 間巡回 CS入次 CS入要求回保持CS入 CS出次97選出 特定役割障害起際，残新選出仕
31、組 前提：各一意ID持 稼動障害起知 問題：稼動中大ID持選出98選出：各他ID知 障害検知選出動作行：選出動作 自分高ID選出送付応答待 誰応答自分調整者送付 応答調整者待99選出：選出受信 応答送付 選出動作行 調整者受信 送信元新40736512選出選出応答応答選出選出応答応答6調整者調整者100選出：各他ID知 全巡回順番知 障害検知 選出自ID付加下流(無反応）送付 戻選出ID最大物選出，選出済再度巡回 選出受信 選出自ID付加下流送付 選出済受信 選出知101選出：4101731591113選出選出15選出済選出済 4 413 41311 15102 空場合低獲得望 busy wait際増望 解除待獲得望 獲得公平必要 小相互排除
