CPU CPU CPU CPU CPU 5-1 PRAM logp π c /(17)

Size: px

Start display at page:

Download "CPU CPU CPU CPU CPU 5-1 PRAM logp π c /(17)"

さやうみのなか
5 years ago
Views:

1 CPU CPU CPU CPU CPU 5-1 PRAM logp π c /(17)

2 CPU sequetial computatio Fly 2) SISD sigle istructio, sigle data SIMD sigle istructio, multiple data MIMD multiple istructio, multiple Data SIMD SIMD SIMD CPU CPU CPU Itel CPU MMX CPU SPMD sigle program, multiple data GPU SIMT sigle istructio, multiple thread SIMD SPMD SIMT PRAM PRAM RAM MIMD PRAM SIMD PRAM MIMD CPU c /(17)

3 CPU CPU CPU PRAM RAM radom access machi PRAM pararell radom access machie 5 1 PRAM 1 P P P 1 2 p Shared Memory 5 1 PRAM PRAM PRAM EREW exclusive read, exclusive write PRAM CREW cocurret read, exclusive write PRAM CRCW cocurret read, cocurret write PRAM commo CRCW PRAM c /(17)

4 arbitrary CRCW PRAM priority CRCW PRAM ID EREW CREW LogP PRAM Culler 1) LogP LogP 1 LogP L o g P L Latecy 1 o overhead 1 o g gap 1 g P Processors + LogP P=8 o=2 g=4 L=6 P LogP P=8 o=2 g=4 L=6 1) c /(17)

5 π LogP λ process calculus process algebra π π calculus 3)4) λ π 4) BNF P ::= M P P νzp!p M ::= 0 π.p M + M π ::= xy x(z) τ [x = y]π π.p π P xy y x output x(z) x z iput τ uovservable [x = y] x y match 0 iactio P + P sum P P P P compositio P P νzp restrictio z P!P replicaito P P P P νx(xz.0 x(y).yx.x(y).0) z(v).vv.0 x ( ) z z 0 z y zx.x(z).0 z x z v xv.0 x(z).0 0 π c /(17)

6 π structural cogruece [x = x]π.p π.p M 1 + M 2 M 2 + M 1, M 1 + (M 2 + M 3 ) (M 1 + M 2 ) + M 3, M + 0 M P 1 P 2 P 2 P 1, P 1 (P 2 P 3 ) (P 1 P 2 ) P 3, P 0 P νzνtp νtνzp, νz0 0, νz(p 1 P 2 ) P 1 νzp P 2 1 z!p P!P reductio (xy.p 1 + M 1 ) (x(z).p 2 + M 2 ) P 1 P 2 {y/z} { y/z} z y τ.p + M P P P, P Q P Q, νzp νzp P P, Q Q, P Q, P Q νx(xz.0 x(y).yx.x(y).0) z(v).vv.0 (0 zx.x(y).0) z(v).vv.0 zx.x(y).0 z(v).vv.0 x.x(y).0 xv π bisimulatio!p π process lik 5 3 c /(17)

7 P1 P2 : process P6 P3 : uidirectioal - li k : bidirectioalli k P5 P4 5 3 asychroous distributed system id poit-to-poit 1 o-blockig sed FIFO PRAM LogP fair local clock sed, receive, iitiator 1) David Culler, Richard Karp, David Patterso, Abhijit Sahay, Klaus Erik Schauser, Euice Satos, Ramesh Subramoia, Thorste Vo Eicke, LogP: Towards a realistic model of parallel computatio, ACM SIGPLAN Notices, vol.28, issue 7, pp.1-12, c /(17)

8 2) Michael J. Fly, Kevi W. Rudd, Parallel Architectures, ACM Computig Surveys, vol.28, o.1, pp.67-70, ) Robi Miler, David Walker, A Calculus of Mobile Processes, I, Iformatio ad Computatio, vol.100, issue 1, pp.1-40, ) Davide Sagiorgi, David Walker, The π-calculus: A Theory of Mibile Processes, Cambridge Uiversity Press, c /(17)

9 PRAM 2) 1) PRAM PRAM for i S ET pardo S T AT S ET i S T AT S T AT 1 1 S ET PRAM : P() : T() : C() = T() P() : Work() = cost T() work A[1..] EREW PRAM for i {1.. log }do for j {1.. 2 i } pardo A[ j] := A[2 j 1] + A[2 j] 1 A[1] + A[2] A[1] A[3] + A[4] A[2] A[1.. 2 ] A[1.. 4 ] log A[1] = O() c /(17)

10 P() = 2 T() = log C() = T() P() = log 2 O( log ) P() P() P() T() T() = 2P() + 4P() + + P() O( P() + log ) P() = log T() O(log + log ) = O(log ) log ) = O() C() = T() P() O(log 5 4 PRAM? T () Work() O(T ()) work optimal C() O(T ()) cost optimal P() = log : c /(17)

11 1 1: 2 EREW PRAM P() O(/log) T() O(log) C() O() Work() O() 2 2: 2 A[i], A[ j] 2 B[1.., 1..] M[1..] i M[i] 1 for i, j {1..} pardo if A[i] A[ j] the B[i, j] := 1 else B[i, j] := 0 for i {1..} pardo M[i] := 1 for i, j {1..} pardo if B[i, j] = 0 the M[i] := 0 M[i] 0 B[i, ] = 1 j A[i] A[ j] A[i] pardo B[i, ] = 0 M[i] 0 commo CRCW PRAM P() O( 2 ) T () O(1) C() O( 2 ) Work () O( 2 ) 3 3: 2 2 T() O(1) 2 2 ( ) 2 = O(1)? ( ) 2 = 2 O(1) 2 1 O(1) d ( 1 2 )d = 2 ( 1 2 )d log = 1 log = 2 d d = log log 2 doubly logarithmic-depth tree DLT DLT P() O() T() O(d) = O(log log ) C() O( log log ) 2 commo CRCW PRAM 4 4: Accelerated Cascadig 1 3 m c /(17)

12 m 1 m 3 m = log log 1 m m / 1 P() O(m /m log /m ) = O( log log log log log log log ) = O( log log log ) T() O(log log log ) 3 m P() O(m) = O( log log ) T () O(log log m) = O(log(log log log log )) = O(log log ) P() O( log log ) T () O(log log ) C() O() 1 accelerated cascadig 1), II, kouoe/lecture/compii/ ),,, c /(17)

13 ) Byzatie agreemet commuicatio complexity time complexity message complexity bit complexity 2 m 1 m CPU CPU c /(17)

14 : leader electio problem id i ID I i I i Max IN OUT 1 1: iitiator if if iitiator the Max := I i ; sed(i i, OUT) else receive(m, IN); Max := max(i i, M); sed(i i, OUT); sed(m, OUT) edif loop receive(m, IN) if M = I i the S TOP edif Max := max(max, M); sed(m, OUT) edloop ID ID ID ID ID Max ID 1 ID ID 5 6 C ID 1 O( 2 ) 2 2: Chag-Roberts Chag Roberts 1) 2) ID ID ID 1 c /(17)

15 5 6 : 1 if iitiator the Max := I i ; sed(i i, OUT) else receive(m, IN); Max := max(i i, M); sed(max, OUT) edif loop receive(m, IN) if M = I i M = FINIS H the sed( FINIS H ); S TOP edif if M > Max the Max := M; sed(max, OUT) edif edloop ID O() 2 O( 2 ) O( log ) 3 3: Peterso ID Peterso 3) 2) 5 7 if iitiator the T1 := I i ; sed(t1, OUT); receive(t2, IN) else receive(t2, IN); T1 := I i ; sed(t1, OUT) edif; while T1 T2 do c /(17)

16 sed(t2, OUT); receive(t3, IN); if T2 < max(t1, T3) the loop receive(m, IN); sed(m, OUT); if M = FINIS H the S TOP edif edloop edif if T2 > max(t1, T3) the T1 := T2 edif; sed(t1, OUT); receive(t2, IN) edwhile; Max := T1; sed( FINIS H, OUT); S TOP 5 7 : Peterso 2) ID ID T1 T3 T2 ID T1 T3 T2 T2 T2 T1 T3 T1 T2 T3 T1 T2 IDT2 T1 T3 T1 T2 FINIS H T1 = T2 while 1 O(log ) 1 2 O() O( log ) c /(17)

17 1) Erest Chag, Rosemary Roberts, A improved algorithm for decetralized extrema-fidig i circular cofiguratios of processes, Commuicatios of the ACM, vol.22, o.5, pp , ),,,, ) G.L. Peterso, A O(log) uidirectioal algorithm for the circular extrema problem, ACM Trasactios o Programmig Laguages ad Systems, vol.4, o.4, pp , c /(17)