1?,. 1,.,,. n-way (n ). 1, 4-way, n-way n (way).,., 1., ( set x ) (x), n., 2, 2 s, 2 l (, s, l )., s + l s., s,., n s. n. s + l way, (set,way)., way,. way, LRU(Least Recently Used, ). way. way, (,...). 1,. スーパーコンピューティングニュース - 111 -
&A : A = k j 1: 4-way., A set x, way y, way y LRU y, way., A (x,y).,,, L1( 1) L2, L3 3. L1., L2,L3., TLB(Translation Lookaside Buffer). OS,. TLB, ( ),., TLB. 2. fortran fortran. C スーパーコンピューティングニュース - 112 -
, fortran.,.,,? 3. 1. (compulsory miss). 2. (capacity miss). 3. (conflict miss). 2.1 (compulsory miss) 1.. (malloc ),.,. 1, (prefetch),.,. 2.2 (capacity miss) 2.,., ( ).,,., ( ).,., スーパーコンピューティングニュース - 113 -
,. 2.3 (conflict miss) 2. ( ),., 3.,.,. (,, ). 1 A, B, C, D.,,., A(1) (0,*) 2. 4way 1 2, 2. (0,*) (1,*) (2,*) (*,0) A(1) A(2) A(3) A(4) A(5) A(6) (*,1) B(1) B(2) B(3) B(4) B(5) B(6) (*,2) C(1) C(2) C(3) C(4) C(5) C(6) (*,3) D(1) D(2) D(3) D(4) D(5) D(6) 2:, A,B,C,D., A,B,C,D, A,B,C,D.,,., E( ),?., (0,*). (0,*) 2 L1, 1way.,. スーパーコンピューティングニュース - 114 -
{A(1),A(2)},{B(1),B(2)},{C(1),C(2)},{D(1),D(2)},{E(1),E(2)}.,. A(1) B(1) C(1) D(1) E(1) A(2), (0,*) 4way D(1), E(1) A(1) (0,0), E(1)( {E(1),E(2)} )., A(2) {A(1),A(2)},., B(1) (0,1), A(2) (0,1).,,. (Cache thrashing). (way ),.,., E E(1) (1,*)., A(1) B(1) C(1) D(1) E(1) A(2),. A(1), B(1), C(1), D(1), E(1) ( 3). (0,*) (1,*) (2,*) (*,0) A(1) A(2) E(1) E(2) (*,1) B(1) B(2) (*,2) C(1) C(2) (*,3) D(1) D(2) 3:, E(1) A(1),.,, E., A,B,C,D., A E B,C,D. 1., A,E, スーパーコンピューティングニュース - 115 -
.,, E(1) (1,*), A E,., E(1)., 1 (1way ).,. 2.4. 1,.,.,,.,., fortran -. integer :: LDA, N real :: A(LDA,N), X(N), Y(N) Y(1:N)=0.0 do J=1,N do I=1,N Y(I)=Y(I)+A(I,J)*X(J),. N 2,. integer :: LDA, N real :: A(LDA,N), X(N), Y(N) Y(1:N)=0.0 do J=1,N,2 do I=1,N Y(I)=Y(I)+A(I,J)*X(J)+A(I,J+1)*X(J+1) スーパーコンピューティングニュース - 116 -
, A(I,J)*X(J) Y(I),. ( ), Y. [1], A.. integer :: LDA, N real :: A(LDA,N), X(N), Y(N) do J=1,N do I=1,N Y(J)=Y(J)+A(I,J)*X(J) Y(I)=Y(I)+A(I,J)*X(J) Y(J)=Y(J)+A(J,J)*X(J). (, 0 ) integer :: LDA, N real :: A(LDA,N), X(N), Y(N), D(N) do J=1,N D(J)=A(J,J); A(J,J)=0.0 do J=1,N,2 do I=1,J Y(J+0)=Y(J+0)+A(I,J+0)*X(J+0) Y(J+1)=Y(J+1)+A(I,J+1)*X(J+1) Y(I)=Y(I)+A(I,J+0)*X(J+0)+A(I,J+1)*X(J+1) do J=1,N Y(J)=Y(J)+D(J)*X(J); A(J,J)=D(J). 2,. スーパーコンピューティングニュース - 117 -
,, NG. [1], 4032 4160 1 (4096 ±64 ). SR8000F1 1PE, Power3., L1 128KB 4way. 15, 4 ( M-, ). [MFLOPS] 1200 1000 800 600 Effect of the dimension in Matrix-Vector multiplications δ=32 M-3 M-4 M-5 M-6 M-7 M-8 M-9 M-10 M-12 M-13 M-14 M-15 400 200 0 4020 4040 4060 4080 4100 4120 4140 4160 4180 dimension of the array 4: SR8000F1 4 ( ), (MFLOPS, FLOPS 1, M 10 9 ).,. 4080 4120 (4096 32 ),.,?, 4096 4096?,. LDA, N.. fortran, スーパーコンピューティングニュース - 118 -
( leading dimension ), 1., A(1,1) A(2,1) ( ), A(1,1) A(1,2). A(I,J),A(I,J+1), A(I,J+1) A(I,J) ( ) % ( /way / ( 8 )) ( ). SR8000F1, ( /way / ) 4096 (=128K/4/8)., N=LDA=4096 A(I,J) A(I,J+1)., way 4, 4 A, 5. 2 (X Y), 3., N 4096? N=4097 A. SR8000F1 128 ( 16 ),. 5. (0,*) (*,0) (1,1) (2,1) (15,1) (16,1) (*,1) (1,2) (14,2) (15,2) (*,2) (13,3) (14,3) (*,3) (12,4) (13,4) 5: 4 J=1., A (0,*),., LDA=4096+6=4102, 4 A(1,4) A(1,1) 6*3=18(> 16), (0,3) (1,3) ( 6)., 4 4130., SR8000., 2., ad hoc 4096+ *C (C 1 ) スーパーコンピューティングニュース - 119 -
(0,*) (1,*) (*,0) (1,1) (2,1) (15,1) (16,1) (17,1) (18,1) (*,1) (9,2) (10,2) (11,2) (12,2) (*,2) (3,3) (4,3) (5,3) (6,3) (*,3) (1,4) 6:., *C,., (, 4096 ). 2.5?, k, A N A?.,,.,, ( ),. [2],. : n-way 1way 2 L (, n 2 L )., N A., k, i,., δ. 0 < i < k/n, mod(i N A + 2 L, 2 L 1 ) 2 L 1 < δ (1), N A,. スーパーコンピューティングニュース - 120 -
2.6, A.,.,.. 2 A, B, way., B(1,1) A(1,1) (2 L 1,*).,.,.. 3,.,.,.,,.. [1], :, SACSIS2003, pp.145-152, 2003. [2], :,, No. SIG 6 (ACS 6), Vol. 45, pp. 113-121, 2004. スーパーコンピューティングニュース - 121 -