158 10 10 CIP /.2002 ISBN 7-302-05978-0... - -.TP303-44 CIP (2002) 078737 100084 http://www.tup.tsinghua.edu.cn 787 1092 1/16 18.75 427 2002 10 1 2002 10 1 ISBN 7-302-05978-0/TP 3563 0001 5000 26.00
1 2 3 4 5 6 7 8 2 5 6 10 10 9 DOS Windows OS/2 Macintosh Unix Linux 10 11 PC 12 CD-ROM (E-mail thjd@thjd.com.cn) 100084 010 62791976 010 62788903 www.thjd.com.cn 15%
2002 8
1...1 1.1... 1 1.1.1... 1 1.1.2... 3 1.1.3... 4 1.1.4... 5 1.1.5... 6 1.2... 9 1.3... 20 2...31 2.1... 31 2.1.1... 31 2.1.2... 36 2.1.3... 37 2.1.4... 38 2.1.5... 38 2.2... 39 2.3... 48 3...66 3.1... 66 3.1.1... 66 3.1.2... 69 3.1.3... 75 3.2... 77 3.3... 86 4... 110 4.1... 110 4.1.1... 110
IV 4.1.2... 111 4.1.3... 112 4.1.4... 113 4.2... 115 4.3... 122 5...139 5.1... 139 5.1.1... 139 5.1.2... 140 5.1.3... 141 5.1.4... 142 5.1.5... 144 5.2... 144 5.3... 151 6...170 6.1... 170 6.1.1... 170 6.1.2... 171 6.1.3... 172 6.2... 172 6.3... 179 7...184 7.1... 184 7.1.1... 184 7.1.2... 185 7.1.3... 186 7.1.4 DMA... 188 7.1.5... 189 7.2... 190 7.3... 200 8...210 8.1... 210 8.1.1... 210 8.1.2... 213 8.1.3... 217
V 8.2... 218 8.3... 225 9...250 9.1... 250 9.1.1... 250 9.1.2... 251 9.1.3... 251 9.1.4... 253 9.1.5... 255 9.2... 257 9.3... 263 10...273 10.1... 273 10.1.1... 273 10.1.2... 273 10.1.3... 275 10.2... 276 10.3... 285...289
1 1.1 1.1.1 1 5 1 5 2
2 3 CPU CPU 5 2 1 a b 2 CPU CPU CPU 4 4 4
1 3 3 1.1.2 1 1 2 2 Word CAD
4 3 4 1.1.3 1 SQL 2
1 5 1.1.4 1 2 PC CPU 3 CPU cache
6 4 1 4 3 ALU 5 Flynn 4 SISD SIMD MISDMIMD 1.1.5 1 3 2 CPU T cpu Tcpu = I n CPI T c I n CPI T c
1 7 CPI CPI n i= 1 CPI = CPIi Ii I i i CPI i i n MIPS IN MIPS = 6 TE 10 = I N IN I N CPI Tc 10 6 Rc = CPI 10 T E =T cpu CPU MIPS CPI MFLOPS FN 6 E I MFLOPS = T 10 I FN MFLOPS MFLOPS MFLOPS 1 CPU CPU 2 3 TPS 3 1 6
8 2 SPEC SPEC95 3 A m = = + + + = = = n i n n i i i m T T T n T n R n A 1 1 2 1 ) 1 1 1 ( 1 1 1 1 Λ G m n n n n n n i i n n i i m R R R T R G 1 1 2 1 1 1 1 ) 1 ( ) ( = = = = = Λ H m n n i i n i i m T T T n T n R n H + + + = = = = = Λ 2 1 1 1 1 A m = = = = n i n i i i i i m T w w R A 1 1 G m wn n w w n i Wi i m R R R R G = = = Λ 2 2 1 1 1 H m n n n i i i n i i i m w T w T w T w T R w H + + + = = = = = Λ 2 2 1 1 1 1 1 1 1 SPEC icomp 4 S p e e e e o r f f T T S + = = 1 1 p f e 0 f e 1 r e 5
1 9 1fault error failure 1 2 3 MTTF MTBF MTTR 1.2 ALU CPU D CPU CPU ALU ALU
10 0 1 16 32 1 8 8 16 32 64 0 CPU
1 11 ROM RAM SRAM DRAM CPI MIPS MFLOPS SISD SIMD (PE) MISD MIMD CPU SPEC
12 0 stuck-at-zero 1 stuck-at-one 1 2 1MB KB 3 4 5 6 RAM 7 8 9 10 11 12 13 14 15
1 13 16 17 18 19 20 21 22 23 24 25 26 27 4 28 CPU 29 30 3 31 A 1 B 2 A B 10 6 MIPS MIPS 32 1 2 1024 1048576 3 4 5 6 SRAM DRAM 7 8 9 10 11 12 13 14 15 16 17
14 18 19 20 21 BASIC C++ Java 22 23 24 25 26 27 28 29 30 31 0.75 0.67 32 1 CPU a) b) c) d) 2 a) b) c) d) 3 a) b) c) d) 4 a) b) c) d)
1 15 5 a) b) c) d) 6 a) b) c) d) 7 a) b) c) CPU d) 8 a) b) c) 32 d) 9 a) b) c) d) 10 a) b) c) d) CAD 11 a) b) c) d) 12 a) b)
16 c) d) 13 a) b) c) d) 14 a) b) c) d) 15 a) b) c) d) 16 a) b) c) d) 17 a) b) c) d) 18 a) b) c) d) 19 a) b) PC c) d) 20 Benchmark a) b) c)
1 17 d) 21 a) b) c) d) 22 a) b) c) d) 23 a) MIPS MFLOPS b) C c) d) 24 a) b) c) d) 25 a) b) c) d) 26 a) 32 b) c) d) 27 i R i w i 1 1 n w R n n n w Wi i i i R i a) i= 1 b) i= 1 i= 1 R w R i i i i= 1 c) d) 28 a) b) MTTF c) MTBF d) MTTR 29
18 a) b) MTTF c) MTBF d) MTTR 1 c 2 b 3 a 4 a 5 b 6 c 7 b 8 c 9 d 10 a 11 b 12 c 13 a 14 d 15 c 16 d 17 c 18 a 19 b 20 a 21 a 22 c 23 c 24 d 25 a 26 a 27 b 28 b 29 c 1 CPU CPU CPU IO 2 3 4 CPU 5
1 19 6 Flynn Flynn 7 (1) (2) PC (3) (4) (5) 8 9 TPS 10
20 1.3 1 1-1 2 3 (1) X 3 (2) Y 3 1-1 X Y Z B1 20 10 40 B2 40 80 20 (1) 1-1 B1 Y X B2 Y X B1 Z X B2 Z X X 1-2 1-2 A m Y Z X 25%3 1-2 X X Y Z B1 1.00 0.50 2.00 B2 1.00 2.00 0.50 A m 1.00 1.25 1.25 G m 1.00 1.00 1.00 (2) Y 1-3 A m X Y 25% Z 3 A m 1-3 Y X Y Z B1 2.00 1.00 4.00 B2 0.50 1.00 0.25 A m 1.25 1.00 2.13 G m 1.00 1.00 1.00
1 21 2 40MHz 1-4 1-4 CPI 1 60% cache 2 18% 4 12% cache 8 10% CPI MIPS CPI CPI = 1 60% + 2 18% + 4 12% + 8 10% = 2.24 MIPS = 40/2.24=17.9 T cpu = I n CPI T c = I n CPI/R c = I n 2.24/(40 10 6 ) = 56 10 9 I n ( ) 3 40MHz 1-5 1-5 45000 1 32000 2 15000 2 8000 2 CPI MIPS 45000+32000+15000+8000=100000 4 45% 32% 15% 8% CPI=1 45% + 2 32% + 2 15% +2 8% = 1.55 MIPS = 40/1.55 = 25.8 =100000 1.55/(40 10 6 )=3875 10 6 ( ) 4 15MHz 10MIPS 1 (1) CPI (2) 30MHz
22 2 30% 1 5% 2 (1) CPI MIPS CPI = 15 10 6 /(10 10 6 )=1.5 (2) 1 CPI CPI=1.5+0.30 (2 1)+0.05 2 (2 1)=1.9 MIPS MIPS = R c /(CPI 10 6 )= 30 10 6 /(1.9 10 6 )=15.79 5 Load/Store / CPI 1-6 1-6 CPI CPI 43% 1 Load 21% 2 Store 12% 2 24% 2 (1) CPI (2) M 25% Load - CPI 2 CPI 3 CPI (1) CPI CPI = 43% 1 + 21% 2 + 12% 2 + 24% 2 = 1.57 (2) 75% 43% 75%=32.25% 25% 43% 25%=10.75% Load 21% 43% 25%=10.25% Store 12% 24% Load 1 10.75%=89.25% 32.25%/89.25%=36.13% CPI 1 10.75%/89.25%=12.04% CPI 2
1 23 Load 10.25%/89.25%=11.48% CPI 2 Store 12%/89.25%=13.45% CPI 2 24%/89.25%=26.89% CPI 3 CPI CPI = 36.13% 1 + (12.04%+11.48%+13.45%) 2 + 26.89% 3 = 1.908 CPI CPU 6 25% CPI 4.0 CPI 1.33 1% CPI 20 CPI CPI 2 CPI 3 CPI (4 25%) + (1.33 75%) = 2.0 CPI 2.0 1% (20 2 ) = 1.82 2.00/1.82 = 1.10 CPI (3 25%) + (1.33 75%) = 1.75 2.00/1.75 = 1.14 7 20 5 Amdahl 1 5 = f e 1 f + e 20 f e =16/19= 0.8421052631579 84% 8 40% 20% 2 4
24 Amdahl 1 0.40 0.40/2 0.20 0.20/4 1 0.40 0.20 1/(1 0.40 0.20+0.40/2+0.20/4) = 1/0.65 = 1.54 9 a n xmips (1) n a x MIPS (2) n=16, x=4 MIPS 40MIPS a (1) MIPS xs p S p MIPS =x/(1 a + a /n) (2) 40=4/(1 a + a /16) a =0.96 10 1-7 1-7 1 1.5 2.0 10.0 4.0 30% 40% 20% 5% 5% 100MHz (1) (2) 1 (3) (2) 1 (1) A m = (1 30% + 1/1.5 40% + 1/2.0 20% + 1/10.0 5% + 1/4.0 5%) 100 = 67.1666666667 (MIPS) 0.4 0.2 0.05 0.3 1 1 1 1 G m = 1 100 =61.555 (MIPS) 1.5 2 10 4 100 1 H m = = 100 = 50 (MIPS) (1 0.3 + 1.5 0.4 + 2 0.2 + 10 0.05 + 4 0.05) 2 MIPS n 1 1 CPI = CPIi Ii = (1 30 + 1.5 40 + 2 0.2 + 10 0.05 + 4.0 5) = 2 I 100 n i= 1 0.05
1 25 R 6 c 100 10 MIPS = = =50(MIPS) 6 6 CPI 10 2 10 (2) 1 A m = (1 30% + 2/1.5 40% + 1/2.0 20% + 1/10.0 5% + 1/4.0 5%) 100 = 95.08 (MIPS) 0.4 0.2 0.05 0.05 0.3 2 1 1 1 G m = 1 100 =81.221 (MIPS) 1.5 2 10 4 H m =100/(2 0.3) = 100/1.7 = 58.82 (MIPS) (3) (2) 1 A m = (1 30% + 2/1.5 40% + 1/2.0 20% + 1/20.0 5% + 1/4.0 5%) 100 = 94.83 (MIPS) 0.4 0.2 0.05 0.05 0.3 2 1 1 1 G m = 1 100 =78.454 (MIPS) 1.5 2 20 4 H m =1/2.2 100= 45.45 (MIPS) 11 SUN SPARC2 SPEC 1-8 1-8 SPEC (MFLOPS) (MFLOPS) GCC 10.7 Li 9.0 Espresso 8.9 Eqntott 9.7 Spice2g6 8.3 Matrix300 11.1 Doduc 5.0 FPPPP 7.8 NASA 7 8.7 Tomcatv 5.6 A m = (10.7+8.9+8.3+5.0+8.7+9.0+9.7+11.1+7.8+5.6)/10 = 8.48 G m = 10 10.7 8.9 8.3 5.0 8.7 9.0 9.7 11.1 7.8 5. 6 = 8.2470 10 H m = = 7.985 1 1 1 1 1 1 1 1 1 1 ( + + + + + + + + + ) 10.7 8.9 8.3 5.0 8.7 9.0 9.7 11.1 7.8 5.6 12 20 (1) (2) 2 (3) 20
26 (4) 70% 10% (1) f e Amdahl 1 Sp = 19 1 fe 20 f e S p 1-9 1-9 f e S p f e 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 S p 1.10 1.23 1.40 1.61 1.90 2.33 2.99 4.17 6.90 20 1-1 25 20 SP 15 10 S P Sp 5 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 f e 1-1 (2) S p =2 1 2 = 19 1 fe 20 1 20 10 f e = = = 52.69% 2 19 19 (3) S p =10 9 20 18 f e = = = 94.73% 10 19 19 (4) f e =0.7 1 S p = = 2.99 19 1 0.7 20 10% 2.99 1.1=3.29
1 27 1 3.29 = 1 0.7 + r e =177 0.7 r e f e 1 20 f e = ( 1 ) = 0.7327 3.29 19 f e ' f e = 0.0327 3.27 13 8 T T 25% (1) a (2) (3) (2) a (1) T Amdahl 0.25T 9 S p =(0.75T+9 0.25T)/T=3 Amdahl S p = 1/(1 a+a/9)=3 (2) 9 2=18 Amdahl S p = 1/(1 a+a/18)=18/(0.25 18+0.75)=3.79 (3) Amdahl 3.79 = 1/(1 a'+a'/9) a' = 0.828 14 R v 10MFLOPS R s 1MFLOPS a
28 (1) R a (2) R a 7.5MFLOPS a (1) 10MFLOPS/1MFLOPS=10 Amdahl S p = 1/(1 a +a /10) =10/(10 9a) R a = S p 1MFLOPS = 10/(10 9a) MFLOPS (2) R a =7.5MFLOPS 10/(10 9a)=7.5 a=0.963 15 icomp 4 Whestone Cint92 Cfp92 ZD Bench PC 16 70% 32 30% CPU 8 16 16 16 16 32 32 32 32 1-10 1-10 16 ZD Bench CPU 52% 16 16 Whestone 2% ZD Bench CPU 1% 16 ZD Bench CPU 10% 16 ZD Bench CPU 5% 32 Cint92 15% 32 Cfp92 5% 32 Cint92 5% 32 Cint92 5% (1) icomp 1-11 1-11 ZD Bench 68% Cint92 25% 16 Whestone 2% Cfp92 5%
1 29 ZDBench 0.68 Whetstone icomp = 100 ( ) ( ) Base ZDBench Base Whetstone Cint92 0.25 Cfp92 0.05 ( ) ( ) Base Cint92 Base Cfp92 (2) CPU Base ZD Bench = 6792.91 Base Whestone = 150.2 Base Cint92 = 14.24 Base Cfp92 = 0.45 i486dx2-66 ZD Bench=17060.22 Whestone=6752.10 Cint92=32.44 Cfp92=16.07 icomp 17060.22 0.68 6752.10 0.02 32.44 icomp = 100 ( ) ( ) ( ) 6792.91 150.2 14.24 0.25 16.07 ( ) 0.45 0.05 0.02 = 297 16 MTTF 10 6 h 10h? λ=1/mttf=10 6 R(10) = e 0.00001 = 0.99999000005 17 n (1) i R i (2) i λ i (1) n = 1 2L n = i= 1 R R R R R (2) n R = i= 1 λ e i t n 1 + λ2 + + λn = λi i= 1 λ = λ Λ i
30 1 1 MTBF = = λ λ + λ + Λ + 1 2 λ n 18 n (1) i R i (2) λ i (1) R = 1 (1 R )(1 R ) L (1 R ) n i= 1 i= 1 1 2 = 1 (1 R ) n i = 1 (1 e ) i λ t (2) λ i λi R = 1 (1 e t ) n n 19 S 1 S 2 S 1 2 S 2 3 R S 1 2 1 (1 R) 2 S 2 3 1 (1 R) 3 R S =[1 (1 R) 3 ][1 (1 R) 2 ]=6R 2 9R 3 +5R 4 R 5 20 0.005/h (1) 1 300h (2) 3 300h (3) 2 150h (1) λ=0.005 R(300)=e 0.005 300 =e 1.5 = 0.2231301601484 (2) λ=0.005 3=0.015 R(300)=e 0.015 300 =e 4.5 = 0.01110899653824 (3) λ =0.005 R(150)=1 (1 e 0.005 150 ) 2 =1 (1 e 0.75 ) 2 =1 (1 0.472366552741) 2 = 0.7216029453336
3 Cache 3.1 3.1.1 1 1 SRAM DRAM SRAM 6 DRAM SRAM DRAM 2 WE* CS* CE* OEDRAM 3 4 5 DRAM RAS* CAS* RAS* 6 DRAM SRAM DRAM 7 (FPM DRAM)
3 67 EDO DRAM EDRAM SDRAM Rambus RDRAM 2 ROM ROM 0 1 PROM EPROM ROM EEPROM ROM 3 4 1 CPU CS* CE* CS* CE CS TTL
68 2 32 4 4 3 5 CPU 1000 0 1001 1 4 4 1/4 4 1000 1005 1010 4 4 4 2 2 6 Cache Cache CPU CPU
3 69 3.1.2 1 CPU Cache Cache Cache Cache CPU Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache LRU Cache Cache Cache Cache Cache Cache Cache Cache 2 Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache Cache n Cache n n
70 Cache Cache Cache n Cache Cache n=1 3 Cache Cache Cache Cache Cache 1 Cache Cache Cache Cache Cache Cache = + + Cache = + 2 Cache Cache Cache Cache = + + + 3 Cache Cache Cache Cache Cache 4 Cache Cache Cache 1 LRU 2 FIFO Cache Cache 3 Cache 5 Cache Cache Cache Cache Cache
3 71 Cache Cache Cache Cache CPU Cache Cache Cache Cache 6 Cache 1 Cache Cache Cache 2 Cache Cache Cache Cache Cache Cache Cache 3 Cache Cache H c Cache T c T m T b Cache T a = H c T c + (1-H c )T m = T c + (1-H c )(T m -T c ) Cache T a = T c + (1-H c )T m 4 Cache T a = T c + (1-H c )T b Cache T c1 Cache T c2 Cache T m1 Cache T m2 Cache H c1 Cache H c2 Cache T a = T c1 + (1 H c1 )T m1 T m1 = T c2 + (1 H c2 )T m2 T a = T c1 + (1 H c1 )(T c2 + (1 H c2 )T m2 ) = T c1 + (1 H c1 )T c2 + (1 H c1 ) (1 H c2 )T m2 (1 H c2 ) Cache (1 H c2 ) (1 H c2 ) Cache 7 Cache Cache Cache Cache 1 3-1
72 Y? N Y? N Y? N Y? N cache cache a b 3-1 T a = T c + (1-H c )T b + W b (1-H c )T b = T c + (1-H c )(1+W b )T b Cache T c Cache Tb (1-Hc) (1-Hc)Tb Cache Tb W b (1 H c ) W b (1 H c )T b Cache 2 3-2 Y? N Y? N Y? N cache cache a b 3-2
3 73 T a = T c + (1-W)(1-H c )T b + W b (1-W)(1-H c )T b + W(1-H c )(T m -T c ) = T c + (1+W b )(1-W)(1-H c )T b + W(1-H c )(T m -T c ) 3 3-3 Y N Y N?? cache cache a b 3-3 T a = T c + (1-H c )T b + W(T m - T c ) 3 3-4 Y? N Y? N cache cache a b 3-4 T a = T c + (1-W)(1-H c )T b + W(T m - T c ) 8 Cache 1 Cache 3 Compulsory miss
74 Cache Cache Capacity miss Cache Cache Conflict miss Cache Cache Cache 2 Cache Cache Cache Cache Cache Cache Victim Cache Cache Cache Cache Cache 3 Cache Cache CPU CPU Cache Cache Cache CPU Cache Cache 4 Cache Cache Cache Cache Cache Cache Cache
3 75 3.1.3 1 LRU CPU (TLB) Cache 2 1 Cache 2
76 3 3 Cache 1 Cache Cache Cache Cache Cache 3-5 VPN MEM PPN Disp TLB Disp cache a Cache MEM VPN Disp TLB cache PPN tag Data C O M P b Cache 3-5 Cache CPU Cache Cache 2 Cache Cache 3-6 a b
3 77 VPN cache Disp a Cache VPN Disp TLB cache PPN Disp Data C O M P b Cache 3-6 Cache Cache 4 1 2 3.2 RAM ROM SRAM DRAM EDO DRAM PROM ROM EPROM ROM
78 EEPROM SDRAM EEPROM Cache Cache CPU Cache Cache Cache Cache CPU Cache Cache Cache Cache Cache Cache (miss -penalty) CPU 90% 10% 10% 90% Cache Cache Cache Cache Cache LRU Cache Cache Cache Cache Cache Cache Cache Cache -Cache Cache Cache
3 79 ROM 1 2 3 4 5 6 7 8 9 ROM ROM ROM ROM 10 PROM 11 1024 4 SRAM 000 16 12 16M 8 DRAM 000000 16 13 14 15 16 17 18 19 20 21
80 22 23 24 CPU 25 26 Cache Cache 27 Cache Cache 28 Cache 128 i 29 Cache Cache 30 n Cache M n 1 Cache n M Cache 31 Cache 3 32 C Cache M 33 34 Cache 35 Cache 64 4 4096 64 36 Cache Cache 37 -Cache Cache 38 CPU 39 40 41 42 43 44 3 3
3 81 1 RAM ROM 2 SRAM DRAM 3 4 5 6 7 T C 8 RAS* CAS* 9 ROM PROM EPROM EEPROM 10 11 10 4 3FF 16 12 12 8 FFFFFF 16 13 14 15 16 17 18 19 20 21 22 23 24 25 Cache 26 27 28 i mod 128 29 30 31 32 M 33 34 35 6 4 36 37
82 38 39 40 41 42 43 44 1 a) RAM b) CS* c) d) 2 a) b) c) d) 3 a) EPROM b) c) CPU d) 4 SRAM 1024 8 a) 20 b) 22 c) 25 d) 30 5 RAM a) b) c) d) 6 a) b) c) SRAM d) ROM 7 a) b) c) d) 8
3 83 a) b) Cache c) Cache Cache d)- 9 1K 8 a) 1024 b) 64 c) 32 d) 10 10 32 4MB 0 a) 2 20 1 b) 2 21 1 c) 2 23 1 d) 2 24 1 11 a) b) c) d) 12 a) b) c) d) 13 Cache a) b) c) d) 14 Cache Cache a) b) c) d) 15 Cache Cache a) b) c) d) 16 Cache a) b) c) d) Cache 17 Cache Cache Cache a) b) c) d) 18 Cache Cache Cache a) b) c) d) 19 a) I/O b) c)
84 d) 20 a) b) c) d) 21 a) b) c) Cache d) LRU FIFO 22 a) b) c) d) 23 a) b) c) d) 24 a) b) c) d) 25 a) b) c) d) 26 a) b) c) d) IEEE 754 27 a) b) c) d) 28 a) CPU b) RAM ROM c) d) 20 1MB
3 85 29 Cache a) b) c) Cache d) 30 a) b) c) d) 1 a 2 d 3 a 4 a 5 b 6 c 7 a 8 b 9 b 10 a 11 a 12 b 13 a 14 a 15 d 16 a 17 a 18 c 19 c 20 a 21 a 22 b 23 a 24 b 25 d 26 a 27 b 28 c 29 b 30 b 1 Cache Cache Cache Cache Cache LRU FIFO 2 ROM RAM EEPROM RAM 3 ROM ROM SRAM 4
86 5 Cache? Cache Cache 3.3 1 a b a b (1) 2K 16 (2) 64K 8 (3) 16M 32 (4) 4G 4 (1) 11 16 (2) 16 8 (3) 24 32 (4) 32 4 2 4K 8 16KB A15~A0 16KB 4 4K 8 12 A11~A0 16K=2 14 14 A13 A13 A12 CS0= A13 *A12 CS1= A13 *A12120 CS2=A13* A12 CS3=A13*A12
3 87 3 4K 8 8K 16 CPU R/W* A15~A0 CS* WE* CPU (8K/4K) (16/8)=4 ( ) CPU 3-7 A13 A13~A1 R/W* CPU A12~A1 we* A cs we* A cs 4K 8 4K 8 D D we* A cs we* A cs 4K 8 4K 8 D D D7~D0 D15~D8 D7~D0 D15~D8 D15~D0 3-7 3 CPU 4 64 1 SRAM 1024 16 16 64 16 8 512 16 1024 A9~A1 AS# WE# D15~D0 A9~A7 A6~A1 3-8 A9~A1 AS# A9-7 3:8 A6~A1 WE# CPU we* A ce 64x1x16 D we* A ce 64x1x16 D we* A ce 64x1x16 D D 15-0 D 15-0 D 15-0 D15-0 3-8 4 5 512 RAM 512 ROM RAM 128 8 ROM 512 8 RAM CS* WE* ROM CS*
88 CPU A15~A0 D7~D0 RW* CPU 4 RAM 1 ROM RAM ROM 3-1 3-1 16 RAM1 0000~007F 0 0 0 x x x x x x x RAM2 0080~00FF 0 0 1 x x x x x x x RAM3 0100~017F 0 1 0 x x x x x x x RAM4 0180~01FF 0 1 1 x x x x x x x ROM 0200~03FF 1 x x x x x x x x x 3-1 16 x 1KB 10 CPU RAM 7 2 7 =128 ROM 9 2 9 =512 CPU 3-9 6 32 32 32 4Mb DRAM 32MB (1) 4M 32 (2) DRAM (3) DRAM (4) CPU (1) 4M 32 16MB 2 (2) 4/4 32/1 = 32 (3) m n M N M N m n 64
3 89 (4) 32M = 2 25 25 32 2 23 CPU A15~10 A9 A8 A7 A6~A0 R/W# Data 2:4 3 2 1 0 RAM1 CS WE* 128 8 A D D0~D7 RAM2 CS WE* 128 8 A D RAM3 CS WE* 128 8 A D RAM4 CS WE* 128 8 A D A8,A7 CS A ROM 512 8 D 3-9 5 CPU 7 1K 8 SRAM 2K 32 CPU CPU MREQ# R/W# SRAM 1K 2K SRAM 8 32 2K/1K 32/8 = 8 SRAM 4 2 2K=2 11 11 10 2K 32=2 13 KB CPU A12 CPU MREQ# R/W# CPU 3-10 8 4K 8 2 1K 8 ROM 2 2K 4 RAM
90 CPU RAM ROM RAM CS# WE# CPU A11~A0 8 D7~D0 R/W# MREQ# ROM 10 2 ROM RAM 11 2 RAM ROM CPU RAM ROM 3-11 ROM A9~A0 RAM A10~A0 A11 A10 2:4 sel0~sel3 sel0 sel1 ROM sel2 sel3 RAM R/W# RAM WE* A 12-2 A 12 A 11-2 CPU CE A CE A CE A CE A CE A CE A CE A CE A 1Kx8 1Kx8 1Kx8 1Kx8 1Kx8 1Kx8 1Kx8 1Kx8 WE# D WE# D WE# WE# D WE# D WE# D WE# D WE# D R/W# D31 ~D 0 D 7-0 D 15-8 D 23-15 D 31-24 D 7-0 D 15-8 D 23-15 D 31-24 3-10 7 CPU MREQ# A11~A0 R/W# OE# sel0 A11~A10 ROM A OE 2:4 sel1 RAM ROM A OE WE* A CE sel2sel3 WE* A CE CPU 1K 8 D 1K 8 D 2K 4 D 2K 4 D D7~D0 D7~D0 D7~D0 D7~D4 D3~D0 3-11 CPU RAM ROM 9 64 1 SRAM 1024 16 16 1024 16 512 16 16 BE1 BE0
3 91 WE1 WE0 A9~A7 A6~A1 3-12 A9~A7 A9~A1 WE1 WE0 3:8 A6~A1 BE0 BE1 D15~D0 we A ce 64 1 8 D7~D0 we A ce 64 1 8 D15~D8 we A ce we A ce 64 1 64 1 8 8 we A ce we A ce 64 1 64 1 8 8 3-12 9 CPU BE0 BE1 WE0 WE1 CPU / B/W# A0 R/W# 10 0000 16 3FFF 16 ROM 4000 16 5FFF 16 6000 16 FFFF 16 RAM RAM CS# WE# CPU A15~A0 8 D7~D0 R/W# MREQ# RAM ROM 8K 1 CPU 2 16 =64KB ROM 2 14 =16KB 8KB RAM 64 16 8=40KB 8KB 64KB 8 8KB 3 3-13 Y0 Y1 ROM ROM 0000 16 3FFF 16 A15~A13 000~001 Y3 Y7 5 RAM RAM 3FFF 16 FFFF 16 A15~A13 011~111 romsel0 = A15 *A14*A13*MREQ# romsel1 = A15 *A14*A13* MREQ# ramsel0 = A15 *A14*A13* MREQ# ramsel1 = A15* A14 *A13*MREQ# ramsel2 = A15* A14 *A13* MREQ# ramsel3 = A15*A14* A13 *MREQ#
92 ramsel4 = A15*A14*A13* MREQ# romsel0 romsel1 ramsel0 ~ ramsel4 MREQ# Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 3:8 OE s2 s1 s0 A 15 A 14 A 13 3-13 10 8KB 8 8K 1 13 A12~A0 16 3 3-14 ROM SRAM R/W# MREQ# A 15 ~A 13 OE# romsel0 3-8 romsel1 ramsel0 ramsel4 A 15 ~A 0 A 12 ~A 0 R/W# CPU ROM A CE 8K 1 8 D ROM A CE 8K 1 8 D WE A CE 8K 1 8 D RAM WE A CE 8K 1 8 D RAM D 7 ~D 0 3-14 10 11 256 8 RAM 1024 8 ROM 2K RAM 4K ROM 4 4 8 8KB 2 00 RAM 01 10 ROM 11 (1) RAM ROM (2) (3) 16 RAM ROM (1) 2KB/256 = 8 8 RAM 4KB/1024B = 4 4 ROM (2) 3-15
3 93 0 2K 4K 6K RAM ROM ROM IO 3-15 11 2 2KB RAM 4K ROM 16 (3) RAM 0000 16 07FF 16 ROM 0800 16 17FF 16 1FF0 16 1FFF 16 12 0000 0005 00100495 (1) 4 (2) 4 (1) 100 5 4 1/4 4 (2) 4 4 5 13 8 (1) 1001 8 1002 8 1003 8 1100 8 (2) 1002 8 1004 8 1006 8 1200 8 (3) 1003 8 1006 8 1011 8 1300 8 (1) 8 8 (2) 4 4 4 (3) 3 6 1 4 7 2 5 0 8
94 8 14 A[16] 4 3-16 CPU 1/4 16 0 4 8 12 0 A[0] A[4] A[8] A[12] 1 A[1] A[5] A[9] A[13] 2 A[2] A[6] A[10] A[14] 3 A[3] A[7] A[11] A[15] 3-16 4 4 1/4 1 15 1/4 1+15 1/4 = 4.75 15 Cache 16 3 (1) 1 (2) 4 4 4 (3) 8 (1) 4 1 1 3 Cache ( ) (2) Cache 1% Cache 1.2 1.5 3 (1) 1+4+1+1=7 7 16 = 112 4 7 4 4 16/4 4 16/4 7 + 4 = 32 8 7 15 7+15=22
3 95 (2) 1.2 + 1.5 0.01 112 = 2.88 4 1.2 + 1.5 0.01 32 = 1.68 8 1.2 + 1.5 0.01 22 = 1.53 16 64K 16 Cache 1K 4 (1) Cache (2) Cache (1) 64K 16 64K = 2 16 16 1K = 2 10 Cache 10 Cache 16 10=6 4 = 2 2 2 10 2=8 (2) 2 8 =256 Cache 256 17 1MB 32 Cache 512 (1) Cache 1 (2) Cache 8 (3) Cache 1 4 1MB 20 32 2 20 2=18 Cache 512 Cache 9 3-17 20 9 2 3-17 17 (1) Cache 0 1 0 2 0 9 9 (2) Cache 0 8 3
96 2 3 6 9 (3) 4 2 1 0 2 0 2 7 9 18 Cache 4 16 4096 64K (1) Cache (2) Cache (1) 3-18 4 4 Cache 4096 Cache 12 64K 16 4 10 2 3 12 2 16 3-18 18 Cache 3-19 4 10 2 10 2 Cache 0 Cache 1023 1 3-19 Cache (2) 16K Cache 1024 19 16KB Cache 32 Cache 4 32
3 97 (1) Cache (2) ABCDE8F8 Cache (1) 3-20 Cache 16KB Cache 14 4 2 32 4 2 Intel 80486 32 18 18 10 2 2 10 2 2 Cache 0 Cache 1023 2 3-20 19 1 Cache cahce 14 10 2 2 (2) ABCDE8F8 16 =1010 1011 1100 1101 1110 1000 1111 1000 2 Cache =1010 1011 1100 1101 11 =1010001111 =1000 20 Cache- 8 Cache 4 (1) 0, 1, 2, 5, 4, 6, 4, 7, 1, 2, 4, 1, 3, 7, 2 Cache Cache (2) (3) Cache (1) Cache 3-2
98 3-2 Cache 0 1 2 5 4 6 4 7 1 2 4 1 3 7 2 Cache 0 1 2 1 0 2 0 3 1 2 0 1 3 3 2 Cache 3 3-21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 5 4 6 4 7 1 2 4 1 3 7 2 0 0 0 0 0 4 4 4 4 4 4 4 4 4 4 4 1-1 1 5 5 5 5 5 1 1 1 1 1 1 1 2 - - 2 2 2 6 6 6 6 2 2 2 2 2 2 3 - - - - - - - 7 7 7 7 7 3 7 7 h h h h 3-21 Cache 3 (2) 3-21 7 11 12 15 (3) h = 4/15 =0.267 21 1 4 8 5 20 17 19 56 9 11 4 43 5 6 9 17 Cache 4 Cache 16 Cache Cache Cache Cache 3-22 Cache 1 4 8 5 20 17 19 56 9 11 4 43 5 6 9 17 0 0 0 0 0 16 16 16 16 16 16 16 16 16 16 16 1 1 1 1 1 17 17 17 17 17 17 17 17 17 17 17 2 2 2 2 2 18 18 18 18 18 18 18 18 18 18 18 3 3 3 3 3 19 19 19 19 19 19 19 19 19 19 19 4 4 4 20 20 20 20 20 20 4 4 4 4 4 4 5 5 5 21 21 21 21 21 21 5 5 5 5 5 5 6 6 6 22 22 22 22 22 22 6 6 6 6 6 6 7 7 7 23 23 23 23 23 23 7 7 7 7 7 7 8 8 8 8 8 56 8 8 8 40 40 40 8 8 9 9 9 9 9 57 9 9 9 41 41 41 9 9 10 10 10 10 10 58 10 10 10 42 42 42 10 10 11 11 11 11 11 59 11 11 11 43 43 43 11 11 n n n y n n y n n y n n y y n y 3-22 Cache
3 99 Cache Cache 22 LRU? LRU Cache 0 1 Cache 0 1 B (B (B 1)) / 2 i i 1 i 0 0 1 23 Cache 64 4 4096 128 (1) Cache (2) (1) 4096=2 12 12 Cache 64=2 6 Cache 6 128=2 7 7 12+7=19 Cache 6+7=13 3-23 (2) 3-23 19 13=6 6 2=4 2 7 12 7 6 2 3-23
100 24 16KB 4 Cache 32 Cache 4 32 (1) Cache (2) ABCDE8F8 Cache ABCDE8F8=1010 1011 1100 1101 1110 1000 1111 1000 (1) 3-24 Cache 16KB Cache 14 Cache 4 2 4 2 32 4 2 (2) 32 18 3-24 18 8 2 2 2 8 2 2 Cache 0 1023 Cache 18 2 2 3-24 Cache Cahce 14 8 2 2 2 (2) 1010 1011 1100 1101 1110 1000 1111 1000 Cache =10100011 1000 25 Intel 80486 Cache 8KB 4 4 32 3 LRU B0 B1 B2 Cache (1) Cache 3-25 Cache 8KB Cache 13 Cache 4 2 4 2 32 4 2 Intel 80486 32 19 3-25 (2) Cache 19 2 2 Cache B0, B1 B2 Cache V Cache
3 101 19 7 2 2 2 7 2 2 Cache 0 511 Cache B0 B1 B2 V 19 2 2 3-25 Cache 26 Cache 4 16 2 4096 64K 32 Cache Cache 4096 Cache 12 2 1 4 2 128K 17 5 9 1 2 3 3-26 12 1 2 17 3-26 26 Cache 3-26 5 9 1 2 1 9 1 2 Cache 0 1023 Cache 5 1 1 3-26 Cache
102 27 Cache- 8 (0~7) Cache 4 (0~3) 2 (LRU) (1) Cache (2) Cache (3) 1 2 4 1 3 7 0 1 2 5 4 6 4 7 2 Cache Cache (4) (3) (5) (3) Cache (1) Cache 1 4 Cache 3-27 1 1 1 1 1 Cache 0 1 2 3 Cache 3-27 Cache (2) 0 1 Cache 0 1 2 3 Cache 2 3 4 5 Cache 0 1 6 7 Cache 2 3 3-28 0 1 2 3 4 5 Cache 0 1 2 3 6 7 3-28 Cache
3 103 (3) Cache 3-29 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 4 1 3 7 0 1 2 5 4 6 4 7 2 1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 - - 4 4 4 4 0 0 0 5 5 5 5 5 5-2 2 2 2 7 7 7 7 7 7 6 6 6 2 - - - - 3 3 3 3 2 2 2 2 2 7 7 h m m h m m m m h m m 3-29 Cache (4) 6, 7, 9, 10, 11, 12, 14, 15 (5) Cache 3 Cache h = 3/15 =0.2 28 Cache 5 Cache 90% Cache T a =0.10 T m +0.90 T m /5 =0.28 T m 1/0.28=3.57 2.57 1 Sp = 1 0.9 + 0.9 5 = 1 0.28 = 3.57 29 VAX-11/780 Cache 8.5 Cache 6 11% 3 Cache Cache? Cache 8.5 + 3 6 0.11 = 8.5 + 1.98 = 10.48 Cache 10.48/8.5 1 = 24% Cache 8.5 3 Cache 3 3 Cache Cache 3 30 CPU Cache 1.5 RISC?? 1.5 + 3 6 0.11 = 3.48 3.48/1.5 1 = 132%
104 CPI Cache 31 4 Cache Cache 40ns 90% 80% 400 Cache 4 (1) (1+0.8) 4=7.2 4M 4M 7.2=28.8 MB/s (2) Cache 90% 10% 2.88MB/s 32 Cache Cache Cache 1 50 Cache 0.64% Cache 6.47% 75% Cache Cache (75% 0.64%) + (25% 6.47%) = 2.10% 75% (1+0.64% 50) + 25% (1+6.47% 50) =75% 1.32 + 25% 4.325 = 2.05 33 1000 Cache 40 Cache 20 Cache Cache 40/1000=4% Cache 20/40=50% Cache 20/1000=2% 34 Cache CPI 2.0 STORE LOAD 40% 25 2% Cache Cache
3 105 Cache CPI Cache CPI S p = (2+40% 2% 25)/2=1.1 Cache 1.1 35 Cache (1) Cache1: 1 (2) Cache2: 4 (3) Cache3: 4 (1) Cache1: 4% 8% (2) Cache2: 2% 5% (3) Cache3: 2% 4% Cache 6 Cache (1) Cache1 Cache T 1 = (4% +0.5 8%) (6+1) =0.08 7 =0.56 (2) Cache2 Cache T 2 = (2 % +0.5 5%) (6+4) =0.45 (3) Cache3 Cache T 3 = (2% +0.5 4%) (6+4) =0.4 Cache1 Cache 36 10 Cache 20 (1) 0.05 (2) Cache 0.03 Cache 1.2 (3) Cache (1) T a = 1 10 +0.05 20 10 = 20 (2) T a = 1 10 1.2 +0.03 20 10 = 10 1.2 + 6 = 18 (3) T a = 1 12 +0.03 20 12 = 19.2 37 Cache 1 (32 ) 1 Cache 15% 1.2 Cache 2 Cache 8
106 (1) (2) 2 10% (3) (2) 2 (4) (2) 64 (1) 2 +1.2 0.15 8 = 3.44 (2) 2 +1.2 0.10 2 8 = 3.92 (3) 2 + 1.2 0.10 (8+1) = 3.08 (4) 2 +1.2 0.10 8 = 2.96 38 32K 16 4K Cache Cache 4 4 LRU Cache 0 1 2 4351 10 Cache Cache 10 Cache 4352 1088 1024 Cache 1024 64 Cache 0 63 64 10 4352 = 43520 Cache Cache Cache 1088 9 64 64 1088 + (10 1) 64 2 = 2240 H = 1 2240 43520 =0.9485294117647 Tm 1 1 Sp = = = HT ( 1 ) c 1 c + H T T m H + (1 H ) 0.9485294117647 + 0.0514058823529 T 10 = 6.834170854285 m (1) Cache (2) Cache Cache 10 4352 = 43520T m 1088T b + 2 64 9T b + (4352 2 64) 9 T c + 3 1088T
3 107 T b =T m =10T c = 6368T m S p = 43520/6368 = 6.834170854271 39 Cache 1 T a =T c +(1 H c )T b +(1 H c )T b T a =T c +(1 W)(1 H c )T b +(1 W)(1 H c )T b +W(1 H c )(T m T c ) 40 128 32 4K 1MW 128 = 2 7 7 32 = 2 5 5 4K = 2 12 12 7+5+12=24 1M = 2 20 20 12 20 12=8 41 32 3-3 CPU 2 3-3 41 000 01 1 001 0 010 11 1 011 00 1 100 10 1 101 0 110 0 111 0 (1) 00001101
108 (2) 10000000 (3) 00101000 32 5 8 3 2 7 (1) 000 01 01101 0101101 (2) 100 10 00000 1000000 (3) 001 42 8 1024 4 3-4 3-4 42 0 3 4 2 1 1 5 2 6 0 3 7 4098 1024 4098 4 = 4 2 4 2 2 2 1024 + 2 = 2050 1024 10 4098 10 = 1 0000 0000 0010 2 100 2 00 0000 0010 2 10 2 1000 0000 0010 2 43 8 1024 4 3-5 3-5 0 3 4 2 1 1 5 2 6 0 3 7 (1)
3 109 (2) 1) 0 2) 3728 3) 1023 4) 1024 5) 1025 6) 7800 7) 4096 (1) 2 3 5 7 (2) 1) 0110000000000 2) 3 3) 0111111111111 4) 0010000000000 5) 0010000000001 6) 7 7) 0100000000000 44 1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 0, 3, 0, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3 LRU 3-6 3-6 1 0 2 2 1 7 6 7 0 1 2 0 3 0 4 5 1 5 2 4 5 6 7 6 7 2 4 2 7 3 1 1* *1 1* 1 1 1 1 1* 1 1 1 1* 1* 4 4 4 4 4* 4 4 4 4* 4* 4* 2 2 2 2 2-0 0 0 0* 0* 6 6 6 6* 2 2 2 2 2* 5 5 5 5 5 5 5 5 5 5 5* 4 4 4 4* - - 2 2 2 2 2* 2* 0 0 0 0 0 0 0 0 0* 0* 2 2 2 2* 7 7 7 7 7 7 7 7 - - - - - 7 7 7 7 7 7* 7* 3 3 3 3* 1 1 1 1* 1* 6 6 6 6 6 6* 6* 6* 3 n n n y y n n y n y n y n y n n n y n y y n n y y n n y y n 3-6 13 =13/30=43.3%
4 4.1 4.1.1 1 2 NOP CLR INC R1 ADD R1, R2 ADD R1, R2, R3 3 4 (PC) PC CPU
4 111 4.1.2 PC 1 PC 4-1 load 4-1 load 1 2 load adr ac mem[adr] LD ADR AC M[ADR] load (adr) ac mem[mem[adr]] LD @ADR AC M[M[ADR]] load adr(pc) ac mem[pc+adr] LD $ADR AC M[PC+ADR] load #n ac n LD #NBR AC NBR load adr(rn) ac mem[adr+rn] LDADR(X) AC M[ADR+XR] load rn ac rn LD Rn AC Rn load (rn) ac mem[rn] LD (R1) AC M[R1] adr (adr) adr Rn (Rn) @ $ PC
112 # 2 3 Little Endian Big Endian 4 4.1.3 1 2 3 6 60 2 6 60=4 20 4 3 3 8
4 113 4 4 2 3 =32 20 12 6 6 4.1.4 1 CISC CPU V Z N C ALU 1 C 1 ALU 0 C 0 ALU () 1 N 1 ALU 0 N 0 ALU 0 Z 1 Z 0 0 Z=1 0 Z=0 ALU V 1 ALU V 0 (PSW) 2 LOAD STORE STORE R1,mem STORE mem,r1 3 PUSH POP
114 3 PUSH POP 3 - - - 4 CISC RISC 1 CISC 2 RISC -
4 115 4.2 RISC- CISC PC PC 1 2 3 4 5 6 7 8 9
116 10 11 12 PC 13 14 15 x=0.0101 y= 0.1001 n=5 x y Z= V= N= 16 17 18 RISC 19 20 21 22 24 23 ( ) CPU (PC+1) PC 2003H 2008H 2008H 2001H 24 25 8 43 16 1 2 3 4 5 6 7
4 117 8 9 10 11 12 13 14 15 0.1110 0 0 0 16 17 18-19 20 21 22 2 24 23 00000011 11110111 24 25 21 16 90 16 1 a) b) c) d) 2 a) b) c) d) 3 a) b) c) d) 4 12345678 16 a) 12 34 56 78 b) 78 56 34 12 c) 56 78 12 34 d) 34 12 78 56 5 a) b) c) d) 6 a)
118 b) c) d) 7 16 PC a) 1 b) 2 c) 4 d) 16 8 16 3000 PC a) 3000 b) 3001 c) 3002 d) 3016 9 a) b) c) d) 10 a) b) c) d) 11 a) b) c) d) 12 a) b) c) d) 13 Load a) b) c) d) 14 STORE a) b) c) d) 15 a) PC b) c) PC
4 119 d) PC 16 a) PC b) c) PC d) PC 17 a) PC b) c) PC d) PC 18 a) PC b) PC PC c) PC d) PC PC 19 a) PC b) c) d) 20 a) b) c) 1 d) 21 a) b) c) d) 22 LOAD a) b) c) d) 23 a) b) c) d) 24 a) b) c) d) 25 a) b) c) d) 26 a) b) c) d) 27 a) b) c) d) 28
120 a) b) c) d) DRAM 29 a) RAM b) c) d) 30 a) b) RISC c) Cache d) RAS* 31 a) RISC LOAD/STORE b) c) EPROM d) 32 4 150 PC a) 150 b) 151 c) 152 d) 154 33 a) b) c) d) 34 16 PC 1 a) b) c) d) 16 35 a) b) c) d) 36 a) b) c) I/O d) 37 LOAD R1,A LOAD R2,B ADD R3,R1,R2 STROE C,R3 a) b) - c) - d) -
4 121 1 c 2 b 3 b 4 b 5 c 6 d 7 b 8 c 9 c 10 c 11 b 12 d 13 a 14 b 15 a 16 c 17 d 18 b 19 a 20 c 21 a 22 b 23 d 24 c 25 d 26 c 27 b 28 b 29 c 30 c 31 a 32 d 33 d 34 c 35 c 36 d 37 b 1? 2 C 3 LIFO FIFO 1 1 4 RISC 0 5 NOP PC
122 CPU NOP 4.3 1 32 12 250 32 12 12=8 8 256 250 1 6 12 6 2 12 = 24K 2 9 T1 30% T2 24% T3 6% T4 7% T5 7% T6 2% T7 3% T8 20% T9 1% (1) (2) (1) 4 9 4 I1 10 I2 00 I3 1110 I4 1100 I5 1101 I6 111110 I7 11110 I8 01 I9 111111 2 (0.30+0.24+0.20) + 4 (0.06+0.07+0.07)+5 0.03+6 (0.02+0.01)=2.57 (2) 3 2 6 5 I1 00 I2 01 I8 10 I3 11000
4 123 I4 11001 I5 11010 I6 11011 I7 11100 I9 11101 2 ((0.30+0.24+0.20) +5 (1 0.30 0.24 0.20)=2.74 3 A 60 6 000000 111011 B 32 A (1) B (2) (1) 6 111100 111111 3 32 111100000 111111111 (2) (60 6 + 32 9)/(60+32) = 7.04 B A B A A 4 10 0.35, 0.20, 0.11, 0.09, 0.08, 0.07, 0.04, 0.03, 0.02, 0.01 10 00 10 010 110 0110 0111 1110 11110 111110 111111 = 0.01 6 + 0.02 6 + 0.03 5 + 0.04 4 + 0.07 4 + 0.08 4 +0.09 3 + 0.11 3 + 0.20 2 + 0.35 2 = 2.79 5 10 T 1 20% T 2 12% T 3 11% T 4 15% T 5 8% T 6 3% T 7 2% T 8 18% T 9 10% T 10 1% (1) 10 (2) 3.20 (1) 4-1
124 1.00 0.59 0.26 0.14 0.41 0.06 0.03 0.21 0.33 0.01 0.02 0.03 0.08 0.10 0.11 0.12 0.15 0.18 0.20 4-1 5 4-1 4-1 5 (1) I1 I8 I4 I2 I3 I9 I5 I6 I7 I1 11 001 011 010 101 100 0001 00001 000001 000000 =2 0.20 + 3 (0.18+0.15+0.12+0.11+0.10) + 4 0.08 + 5 0.03 + 6 (0.02+0.01) = 2 0.2 + 3 0.66 + 4 0.08 + 5 0.03 + 6 0.03 = 0.4 1.98 + 0.32 + 0.15 + 0.18 = 3.03 (2) 3 4 6 3 4 4-2 4-2 5 (2) I1 I8 I4 I2 I3 I9 I5 I6 I7 I1 000 001 010 011 100 101 1100 1101 1110 1111 =3 (0.20+0.18+0.15+0.12+0.11+0.10)+4 (0.08+0.03+0.02+0.01) = 3 0.86 + 4 0.14 = 3.14 3 5 7 3 5 4-3 4-3 5 (2) I1 I8 I4 I2 I3 I9 I5 I6 I7 I1 000 001 010 011 100 101 110 11100 11101 11110
4 125 =3 (0.20+0.18+0.15+0.12+0.11+0.10+0.08)+5 (0.03+0.02+0.01) = 3 0.94 + 5 0.06 = 3.12 6 16 6 3 M N 3 4 10 16 2 6 2 6 L N=((2 4 M) 2 6 L) 2 6 L=(2 4 M) 2 6 N 2 6 7 16 4 M N 3 4 8 12 L L=((2 4 M) 2 4 N) 2 4 8 20 40 30 50 40 60 50 70 (1) load #20 (2) load 20 (3) load (20) (4) load #30 (5) load 30 (6) load (30) (1) 20 (2) 40 (3) 60 (4) 30 (5) 50 (6) 70 9 R 1000 1000 2000 2000 3000 PC 4000
126 (1) R (2) (R) (3) 1000 (4) (1000) (5) 2000(PC) (6) #2000 (1) 1000 (2) 2000 (3) 2000 (4) 3000 (5) 3000 (6) 2000 10 W W+1 Y Z X Z (1) (2) (3) (4) 4-2 X W W+1 Z OP Y A 4-2 10 (1) Z W+1 Z Z=Y (2) Z Y Z = (Y) (3) PC PC W+2 Y Z=W+Y+2 (4) Y Z=X+Y 11 LOAD 200 201 AC PC 200 R1 400 XR 100 4-3
4 127 PC 200 200 201 load 500 M R1 400 202 XR 100 309 400 450 700 AC 500 800 600 900 702 325 800 300 4-3 AC (1) (2) (3) (4) (5) (6) (R1) (7) (R1) (1) 500 AC 800 (2) 500 AC 201 (3) 500 800 300 (4) 500+202=702 325 PC 202 (5) XR+500=100+500=600 900 (6) R1 400 AC (7) R1 400 AC 700 12 4 750 10 500 10 (1) PC (2) (3)
128 (4) (1) PC 754 10 (2) 500 754 = 254 (3) 254 < 2 8 8 (4) 9 13 300 301 400 R1 200 (1) (2) (3) (4) (R1) (5) R1 (1) 400 (2) 301 (3) PC PC 302 302+400=702 (4) R1 R1 200 (5) R1 200+400=600 14 CPU 4 3 3 3 3 OP M D R D M S R S OP 4 M S, M D 3 R S, R D 3 (1) 16 (2) CPU 16 (3) 16 (1) 4 16 16 16 16 16 (2) CPU 16 4
4 129 4 2 4 2 4 OP M D R D M S R S 2 3 4 3 4 OP M D R D M S R S (3) 16 4 3 4 3 4 OP M D R D M S R S 16 18 15 1000 16 SP 100 16 2000 16 2001 16 3000 16 PC SP (1) (2) (3) (1) PC SP PC=2000 16 SP=100 16 1000 16 (2) PC SP 1 2 2000 16 +2=2002 16 PC=3000 16 SP=FF 16 2002 16 (3) PC SP 1 PC=2002 16 SP=100 16 1000 16 16 16 16 5 3 5 8 PC Rx (1)
130 (2) (3) EA (1) 5 2 5 =32 (2) 8 2 8 =256 16 2 16 =64K 16 8 2 16 +2 8 PC 8 PC 256 (3) A EA=PC EA=A EA=(A) EA=Rx+A EA=PC+A 17 16 128 64~63 16 (1) 3 (2) 6 (3) 8 (4) 12 (5) 32 128 log 2 128=7 64~63 7 16 4 4 5 4-4 (1) 2 3 00 01 10 11 (2) 5 3 2 11 3 8 6 6 11000 11001 11010 11011 11100 11101 11110 11111 (3) 8 3 8 11110000~11110111 11111000~11111111
4 131 2 7 7 1 2 3 4 5 OP 1 2 5 4 7 OP 8 4 4 OP 9 7 OP 16 OP 4-4 (4) 9 8 16 9 12 12 111110000~111111011 4 111111100~111111111 (5) 16 7 4 4 27 32 32 32 1111111000000000~1111111000011111 18 1000 32 1267AB92 16 1000 1001 1002 1003 4 4 32 12 16 1000 67 16 1001 AB 16 1002 92 16 1003 1000 1001 1002 1003 12 16 67 16 AB 16 92 16 19 C char str[]= abcde ; int i=0x00112233; str 5 6 i 32 2 4-4 4-4 19 0 1 2 3 4 5 6 7 8 9 10 11 a b c d e \000 - - 33 22 11 00
132 20 C ( ) (1) struct { double i; // 0x1112131415161718 } S1; (2) struct { int i; // 0x11121314 int j; // 0x15161718 } S2; (3) struct { short i; // 0x1112 short j; // 0x1314 short k; // 0x1516 short l; // 0x1718 } S3; (1) 11 12 13 14 15 16 17 18 18 17 16 15 14 13 12 11 (2) 11 12 13 14 15 16 17 18 14 13 12 11 18 17 16 15 (3) 11 12 13 14 15 16 17 18 12 11 14 13 16 15 18 17 21 (1) 64 (2) 3 (3) 16 (4) / (LOAD/SRORE) (5) 64KB /
4 133 (1) 64 8 (2) 16 4 64KB 16 (3) 8 4 4 (4) / (LOAD/SRORE) 16 8 4 4 (5) PC+ 8 8 8 22 8 C5H???? E2 16 C=1 C4 16 C=1 62 16 C=0 C4 16 23 8 CPU A 11110000 B 00010100 A B C N V Z A B B 1 A A 11110000 B +1 + 11101100 A B 11011100 C=1 N=1 1 V=0 1 Z=0 0
134 24 A B A B A<B C=1 C Z A B 4-5 4-5 C Z A B A B C=0 Z=0 A B C=1 Z=1 A B C=0 A B Z=1 A B C=1 A B Z=0 (1) A B 0 C=0 Z=0 (2) A B 0 Z=1 C=0 (3) A B 0 C=1 C=1 (4) A B C=1 0 Z=1 C=1 Z=1 (5) A B 0 Z=1 Z=1 (6) A B A=B Z=0 25 A B A B S Z V A B 4-6 4-6 A B A B (S V)=0 Z=0 A B (S V)=1 Z=1 A B (S V)=0 A B Z=1 A B (S V)=1 A B Z=0 (1) A B A B (V=0) (S=0 S ) 0.010 0.001=0.010+1.111=0.001 (AB ) 1.111 1.110=1.111+0.010=0.001 (AB ) 0.010 1.100=0.010+0.100=0.110 (AB ) (V=1) (S=1) 0.100 1.010=0.100+0.110=1.010 (AB ) 0 Z=0 S V=0 Z=0 (2) A B A B (V=0) (S=1)
4 135 0.001 0.010=0.001+1.110=1.111 (AB ) 1.110 1.111=1.110+0.001=1.111 (AB ) 1.100 0.010=1.100+1.110=1.010 (AB ) (V=1) (S=0) 1.010 0.100=1.010+1.100=0.110 (AB ) S V=1 (3) A B A<B (S V)=0 (4) A B A>B (S V)=1 Z=1 (5) A B 0 Z=1 Z=1 (6) A B A B Z=0 26 N V Z C (1) (2) (3) (4) (1) C + Z 1 A B A B>0(C=0) 0(Z=0) C+Z=0 (2) C+Z 1 A B A B<=0 (C=1) 0(Z=1) C+Z=1 (3) N V A B A<B A B (V=0) (N=1) (V=1) (N=0) N V=1 0.001 0.010=0.001+1.110=1.111 (AB ) 1.110 1.111=1.110+0.001=1.111 (AB ) 1.100 0.010=1.100+1.110=1.010 (AB ) 1.010 0.100=1.010+1.100=0.110 (AB ) (4) N V N V 1 27 [a b+c+d e+f f] b+c+d a b c d e f push a push b mult push c add push d
136 push e mult add push f push f mult add push b mult push c add push d add 28M-M R-R A=B+C PUSH POP M-M 3 R-R 3 LOAD STORE 16 1 2 4 4-7 4-7 M-M R-R LOAD B PUSH B ADD A,B,C LOAD R1,B ADD C PUSH C LOAD R2,C STORE A ADD ADD R3,R1,R2 POP A STORE A,R3 4-8 29 28 4 A=B+C; B=A+C; D=A B
4 137 4-8 M-M R-R 9 10 7 15 12 12 12 12 21 22 19 27 4-9 4-9 M-M R-R LOAD B PUSH B ADD A,B,C LOAD R1,B ADD C PUSH C ADD B,A,C LOAD R2,C STORE A ADD SUB D,A,B ADD R3,R1,R2 ADD C POP A STORE A,R3 STORE B PUSH A ADD R1,R2,R3 LOAD A SUB B PUSH C ADD STORE B,R1 SUB R4,R3,R1 STORE D POP B STORE D,R4 PUSH A PUSH B SUB POP D 4-10 4-10 M-M R-R 24 30 21 29 32 36 36 20 56 66 57 49 30 29 F = (A B)/(C+D*E) A B C D E F a b c d e f 4-11
138 4-11 30 M-M R-R push a push b sub push c load d mult e add c store f mult t1,d,e add t1,t1,c sub t2,a,b div f,t2,t1 load r1,a load r2,b sub r3,r1,r2 load r1,d push d load a load r2,e push e sub b mult r2,r1,r2 mult add div pop f div f store f load r1,c add r2,r2,r1 div r1,r3,r2 store r1,f 22+24 24+32 28+48 36+24
5 CPU 5.1 5.1.1 1 CPU CPU CPU CPU CPU CPU 2 CPU CISC 1 IR 2 PC 3 DR 4 AR 5 SR RISC
140 3 CPU CPU CPU 5.1.2 1 1 PC IR 2 CPU 1 2 CPU CPU CPU add r1, r2, r3 r2 r3 CPU r2 Y r3 Y add r1, r2, r3 r1
5 141 5.1.3 1 T1 T2 T1 5 8 END 2 3 1 T1 INS1 T1 INS1 + T1 INS2 + = T1 INS1 + INS2 + C
142 C = T1 INS1 + INS2 + + T2 INS1 + INS2 + + 1 2 T1 T2 5.1.4 1 1 2 IRout IR 2 1 2 3 3
5 143 n n n 3 ROM ROM RAM sequencer 4 1 µpc 1 µpc BCF BAF 2
144 3 5.1.5 1 PLA PAL PLA D GAL PAL D 2 CAD 5.2
5 145 ROM 1 2 CPU 5 3 4 5 6 7 8 9 10 11 12 13 CPU CPU 14 3 15 3 16 17 16 18 19 20 1 2 3 4
146 5 6 7 8 9 10 11 12 13 14 15 16 17 16 16 64K 1 18 19 20 (SP) 1 CPU a) b) c) d) 2 a) b) c) d) 3 a) b) c) d) 4 a) b) c) d) PC 5 CPU a) b) c) d)
5 147 6 a) b) c) d) 7 a) PC b) PC c) d) PC 8 a) b) c) d) 9 a) b) c) d) 10 a) b) c) CPU PC d) 16 11 a) b) c) d) 12 a) b) c) d) 13 a) b) c) d) CPU 14 a) b)
148 c) d) 15 a) b) c) b) 16 a) b) c) d) 17 a) b) c) d) 18 RAM a) b) c) d) 19 a) b) c) d) 20 a) b) c) d) 21 a) b) c) d) 22 a) b) c) d)
5 149 23 a) b) c) d) 24 a) b) PC c) d) 25 a) b) PC c) d) 1 d 2 c 3 b 4 b 5 b 6 b 7 a 8 d 9 a 10 d 11 b 12 b 13 a 14 b 15 a 16 b 17 b 18 b 19 a 20 a 21 a 22 c 23 b 24 d 25 a 1 (1) (2) (3) (4) CPU (IR)(PC)(DR) (AR)(SR) 2
150 3 4 3 3 3 5 6 ROM EPROM RAM 7 8 n n n n n n n 2 n 1
5 151 9 10 ROM ROM 16 ROM 32 16 ROM 8GB 32 ROM ROM 11 ROM D CAD 5.3 1 (1) AR AR, AR 0 (2) R1 R2, R1 R3 (3) PC AR, PC PC+1 (1) AR (2) (3) PC PC IR PC MAR MDR ALU Y
152 ALU ALU Z 2 CPU (1) R2 Memory[MAR] (2) Memory[MAR] R3 (3) R5 Memory[R5] (1) MAR R2 MAR, read DBUS MDR R2 (2) R2 MAR MAR R2 MDR, write (3) R5 R5 R5 MAR, read DBUS MDR R5 3 MOVE R1,R2 R1 R2 PC MAR PC MAR PC 1 PC PC+1 PC MDR IR DBUS MDR IR R1 R2 4 MOVE mem1,mem2 mem1 mem2 PC MAR PC MAR PC 1 PC PC+1 PC MDR IR DBUS MDR IR IR(mem1) MAR
5 153 DBUS MDR IR(mem2) MAR 5 MOVE mem1 (mem2) mem1 mem2 PC MAR PC MAR PC 1 PC PC+1 PC MDR IR DBUS MDR IR IR(mem1) MAR Y DBUS MDR Y IR(mem2) MAR DBUS MDR MAR Y+0 Z Y MDR 6 CPU (1) ADD R1,(mem) (2) STORE (mem),r1 (1) R1 R1 PC MAR, PC+1 PC DBUS MDR MDR IR IR() MAR, DBUS MDR MDR MAR, DBUS MDR MDR Y
154 R1+Y Z Z R1 (2) R1 PC MAR, PC+1 PC DBUS MDR MDR IR IRMAR, DBUS MDR MDR MAR R1 MDR, R2 7 MIPS j 10000 MIPS [1] 10000 4 PC 4 (1) IR = Memory[PC] PC = PC + 4 (2) PC = IR[25 0] << 2 8 CPU 3 (1) ADD R1,R2 ; R1+R2 R1 (2) ADD R1,(R2) ; R1+(R2) R1 (3) ADD R1,(mem) ; R1+(mem) R1 PC MAR, PC+1 PC DBUS MDR IR R2 Y R1 + Y Z Z R1 PC MAR,
5 155 PC+1 PC DBUS MDR IR R2 MAR, DBUS MDR MDR Y R1 + Y Z Z R1 PC MAR, PC+1 PC DBUS MDR IR IR(mem) MAR, DBUS MDR MDR MAR, DBUS MDR MDR Y R1 + Y Z Z R1 3 5-1 PC MAR PC + 1 PC DBUS MDR R2 Y MDR IR R2 MAR IR(mem) MAR DBUS MDR MDR MAR DBUS MDR MDR Y R1 +Y Z Z R1 5-1 8
156 1 3 9 CPU 3 3 4 5-2 PC MAR PC + 1 PC DBUS MDR R2 Y MDR IR R2 MAR IR(mem) MAR DBUS MDR MDR MAR DBUS MDR MDR Y add sub mult div R1 +Y Z R1 Y Z R1 Y Z R1 Y Z Z R1 5-2 9 10 CPU 3 9 ADD (R1), R2 PC MAR, PC+1 PC DBUS MDR IR R1 MAR, MBUS MDR
5 157 MDR Y R2 + Y Z Z MDR, 5-3 6 PC MAR PC + 1 PC DBUS MDR MDR IR R1 Y R1 MAR IR(mem) MAR DBUS MDR MDR MAR DBUS MDR MDR Y R2 +Y Z R2 MAR IR(mem) MAR MBUS MDR MDR MAR MBUS MDR MDR+Y Z Z R2 Z MDR, 5-3 10 MAR
158 11 CPU ADD R3,R1,R2 // R1+R2 R3 MOVE R1,R2 // R1 R2 MOVE R1,mem // R1 mem MOVE mem,r1 // mem R1 MOVE mem1,mem2 // mem1 mem2 JMP #A ADD PC MAR PC+1 PC DBUS MDR MDR IR R1 Y R2+Y Z Z R3 MOVE PC MAR PC+1 PC DBUS MDR MDR IR R1 R2 MOVE PC MAR PC+1 PC DBUS MDR MDR IR IR(mem) MAR R1 MDR, MOVE PC MAR PC+1 PC DBUS MDR MDR IR IR MAR, DBUS MDR R1 MOVE PC MAR PC+1 PC
5 159 DBUS MDR MDR IR IR(mem1) MAR DBUS MDR IR(mem2) MAR JMP PC MAR PC+1 PC DBUS MDR MDR IR PC Y IR+Y Z Z PC 5-4 PC MAR PC + 1 PC DBUS MDR ADD MOVE1 MDR IR MOVE2 MOVE3 MOVE4 JMP R1 Y R1 R2 IR MAR IR MAR, IR MAR, PC Y R2+Y Z R1 MDR, MDR R1 DBUS MDR IR+Y Z Z R3 IR MAR, Z PC 5-4 11 12 1024 32 BCF BAF 16 BCF BAF 1024 = 2 10 BAF 10 BCF 32 16 10 = 6 13 PC MAR
160 PC+1 PC DBUS MDR MDR IR PCout MARin PC+1 MDRin MDRout IRin 6 PC PCout MAR MARin PC+1 PC 1 1 1 1 0 0 0 MDRin MDRout IRin 0 0 0 1 1 1 14 5 5-5 T1 T2 T3 T4 T5 D Q D Q D Q D Q D Q Q Q Q Q Q CLK 5-5 15 CPU ADD R3,R1,R2
5 161 LOAD mem,r1 STORE mem,r1 JMP #A ADD,LOAD,STORE JMP (1) 5-6 T1 T2 T3 T4 T5 ADD IR LOAD STORE JMP 5-6 (2) ADD T1 PCout, MARin, PC+1, Read ;PC MAR, PC+1, read T2 MDRout, IRin ;MDR IR T3 R1out, Yin ;R1 Y T4 R2out, Zin, ADD ;R2+Y Z T5 Zout, R3in ;Z R3 LOAD T1 PCout, MARin, PC+1, Read ;PC MAR, PC+1, read T2 MDRout, IRin ;MDR IR T3 IRout, MARin, Read ;IR MAR, read T4 MDRout, R1in ;MDR R1 STORE T1 PCout, MARin, PC+1, Read ; PC MAR, PC+1, read T2 MDRout, IRin ;MDR IR T3 IRout, MARin ;IR MAR T4 R1out, MDRin, Write ;R1 MDR, write JMP T1 PCout, MARin, PC+1, Read ; PC MAR, PC+1, read T2 MDRout, IRin ;MDR IR T3 PCout, Yin ;PC Y T4 IRout, ADD, Zin ;IR+Y Z
162 T5 Zout, PCin ;Z PC (3) PCout=T1+JMP*T3 PC+1=T1 MARin=T1+STORE*T3+LOAD*T3 MDRout=T2+LOAD*T4 Read=T1+LOAD*T3 IRin=T2 R1out=ADD*T3+STORE*T4 Yin=ADD*T3+JMP*T3 R2out=ADD*T4 Add=ADD*T4+JMP*T4 Zin=ADD*T4+JMP*T4 Zout=ADD*T5+JMP*T5 R3in=ADD*T5 IRout=LOAD*T3+STORE*T3+JMP*T4 R1in=LOAD*T4 PCin=JMP*T5 MDRin=STORE*T4 Write=STORE*T4 END=(LOAD+STORE)*T4+(ADD+JMP)*T5 16 15 8 ROM ROM 00 01 10 11 (1) (2) PCout PC+1 MARin MDRout Read IRin R1out Yin R2out Add Zin Zout R3in IRout R1in PCin MDRin Write 18 T1 T2 T1 1110 1000 0000 0000 00 T2 0001 0100 0000 0000 00 ADDT3 0000 0011 0000 0000 00
5 163 ADDT4 0000 0000 1110 0000 00 ADDT5 0000 0000 0001 1000 00 LOADT3 0010 1000 0000 0100 00 LOADT4 0001 0000 0000 0010 00 STORET3 0010 0000 0000 0100 00 STORET4 0000 0010 0000 0000 11 JMPT3 1000 0001 0000 0000 00 JMPT4 0000 0000 0110 0100 00 JMPT5 0000 0000 0001 0001 00 (3) 5-7 0000 0001 T1 T2 0001 xx10 ADD LOAD STORE 0010 0110 1010 ADDT3 LOADT3 STORET3 0011 0011 0111 0111 1011 1011 ADDT4 LOADT4 STORET4 0100 0100 0000 0000 ADDT5 0000 JMP 1110 JMPT3 1111 1111 JMPT4 1000 1000 JMPT5 0000 5-7 (4) 12 5-7 4 (5) 5-7 BCF BAF 4 BAF 18 BCF(1 ) BAF 4 T1 1110 1000 0000 0000 00 0 0001 T2 0001 0100 0000 0000 00 1 xx10 ADDT3 0000 0011 0000 0000 00 0 0011 ADDT4 0000 0000 1110 0000 00 0 0100 ADDT5 0000 0000 0001 1000 00 0 0000
164 LOADT3 0010 1000 0000 0100 00 0 0111 LOADT4 0001 0000 0000 0010 00 0 0000 STORET3 0010 0000 0000 0100 00 0 1011 STORET4 0000 0010 0000 0000 11 0 0000 JMPT3 1000 0001 0000 0000 00 0 1111 JMPT4 0000 0000 0110 0100 00 0 1000 JMPT5 0000 0000 0001 0001 00 0 0000 (T2) 2 2 10 BCF 5-8 (18 ) BCF BAF 1 0 5-8 17 (1) (2) 5-9 S0 S2 S1 ADD LOAD STORE S5 S7 JMP S9 S3 S6 S8 S10 S4 S11 5-9 (3) S0 1110 1000 0000 0000 00 S1 0001 0100 0000 0000 00
5 165 S2 0000 0011 0000 0000 00 S3 0000 0000 1110 0000 00 S4 0000 0000 0001 1000 00 S5 0010 1000 0000 0100 00 S6 0001 0000 0000 0010 00 S7 0010 0000 0000 0100 00 S8 0000 0010 0000 0000 11 S9 1000 0001 0000 0000 00 S10 0000 0000 0110 0100 00 S11 0000 0000 0001 0001 00 18 IR PC MAR MDR r0 r7 ALU Y ALU ALU Z ADD r1,r2,r3 // r1 r2 + r3 JUMP #a // pc pc +1+ a LOAD r1,1000 // r1 mem[1000] STORE r1,1000 // mem[1000] r1 (1) (2) ER ER 1 (3) (1) 5-10 PC MAR PC + 1 PC DBUS MDR MDR IR add store load jump r2 Y IR( MAR IR( MAR PC Y r3 +Y Z r1 MDR DBUS MDR Y+IR( ) Z Z r1 MDR r1 Z PC 5-10
166 (2) 5-11 (3) E 1 PC MAR PC + 1 PC DBUS MDR MDR IR add store load jump r2 Y IR( MAR IR( MAR PC Y 1 E r3 +Y Z r1 MDR DBUS MDR Y+IR( ) Z Z r1 MDR r1 Z PC 5-11 19 10 C 0 C 9 C i N i N i i 0 1 2 3 4 5 6 7 8 9 N i 4 4 3 11 9 16 7 1 8 22 10 (1) 3+3+2+4+4+5+3+1+4+5=34 (2) 4+4+3+11+9+16+7+1+8+22=85 20 5 5-1
5 167 5-1 I 1 I 2 I 3 I 4 I 5 a, c, e, g, i a, b, d, f, h, j a, d, e, f a a, d, j 5-2 5-2 a b c d e f g h i j I 1 I 2 I 3 I 4 I 5 c, g, i b h 10 7 b c e j 1 2 3 4 5 6 7 a bh cgi d e f j b,c,d 010 101 001 000 2 e,f,g h,i,j 21 20 4 128 30( )
168 (1) (2) (1) 3 20 4 2 128 7 20 2 7 (2) 5-12 2 BCF 4 BAF 7 µar µir A 128 30 D 20 2 7 BCF BAF 7 20 5-12 22 CPU CPU 5-13 CPU PC A MAR Z B R1 A ALU A R2 B ALU B
5 169 / IR PC MAR A MDR B R 0 R n 1 SR A ALU B Z 5-13 CPU
6 6.1 6.1.1 1 CPU ( ) ( ) 2 1 CPU CPU CPU CPU 2 Cache
6 171 3 6.1.2 CPU 1 2
172 6.1.3 1 m EIA-232-D 2 - CPU 3 UART UART EIA-232-D UART 5 8 1 1 1.5 0 1 1 75b/s 19200b/s 6.2
6 173 UART/ DMA 1 2 3 4 5 6 7 8 9 10 11 12 13 14
174 15 16 17 18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 a) b) c) d) 2 a) b) c) d) 3 a) b) c) d) 4
6 175 a) b) c) d) 5 a) b) c) d) 6 a) b) c) d) 7 a) b) c) d) 8 a) b) c) d) 9 a) b) c) d) 10 a) b) c) d) 11 a) b) c) d) 12 a) b) c) d) 13 a) b) c) d) 14
176 a) b) c) d) 15 a) b) c) d) 16 a) b) c) d) 17 a) b) c) d) 18 n a) n b) 3 c) 2+ log 2 n d) 2n+1 19 n a) n b) 3 c) 2+ log 2 n d) 2n+1 20 a) b) c) d) 21 a) b) c) d) 22 a) b) c) d) 23 a) b) c) d) 24 a) CPU IO b) CPU c) CPU d)
6 177 25 a) b) CPU c) CPU d) CPU 26 a) CPU b) c) d) 27 a) b) c) d) 28 / / a) b) c) CPU d) 29 a) b) PROM c) d) 30 a) b) c) d) 1 d 2 a 3 b 4 c 5 b 6 d 7 b 8 c 9 c 10 b 11 c 12 d 13 b 14 a 15 b 16 a 17 c 18 b 19 d 20 b 21 b 22 a 23 d 24 c 25 b 26 c 27 a 28 d 29 a 30 a
178 1 backplane 2 3 3 3 (1) 3 (2) (3) 4 5? (1)
6 179 (2) PCI PC USB P1394 6 3 (1) (2) (3) 6.3 1 8A 16 8 6-1 D0 D1 D2 D3 D4 D5 D6 D7 6-1 1 2 RS-232-C A8 8 1 1 6-2
180 0 0 0 1 0 1 0 1 6-2 2 3 1 8 1 1 1200b/s 8 1+8+1+1=11 8 1200 = 872.72 1+ 8 + 1+ 1 b/s 4 TR0 TR1 TR2 1 BG 0 BG 1 6-1 6-1 TR0 TR1 TR2 BG 1 x x 0 x 1 x 0 x x 1 0 0 0 0 1 6-3 TR0 TR1 TR2 BG 6-3 5 6-2 BR0 BR3 x y BR
6 181 6-2 BR0 BR1 BR2 B R3 BG0 BG1 BG2 BR3 1 x x x 1 0 0 0 0 1 x x 0 1 0 0 0 0 1 x 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 BG0 = BR0 BG1 = BR1* BR0 BG2 = BR2* BR1 * BR0 BG3 = BR3* BR2 * BR1 * BR0 6-4 BG0 BG1 BG2 BG3 BR0 BR1 BR2 BR3 6-4 6 16 32 50MHz 4 32 (1) T =4/50MHz = 4 20 10 9 = 80 10 9 (s) B = 2/T = 2/80 10 9 = 25 10 6 (B/s) (2) 32 B = 4/T = 4/80 10 9 = 50 10 6 (B/s) (3) B = 2 2/T = 50 10 6 (B/s)
182 (1) (2) (3) 7 50MHz 8 8 Cache 4 1 3 8 8 1 2 8 8 3 (1) (2) (3) 65% 35% (1) T m = (1+3+8) 20 10 9 = 240 10 9 (s) B m = 8/T m = 33.3MW/S = 133.3MB/S (2) T m = (1+2+8+3) 20 10 9 = 280 10 9 (s) B m = 8/T m = 28.6MW/S = 114.4MB/S (3) T m = (240 0.65 + 280 0.35) 10 9 = 254 10 9 (s) B m = 8/T m = 31.50MW/S = 126.0MB/S B m =133.3 0.65 + 114.4 0.35 = 126.685 MB/S 8 Cache Cache 0.05 40% Cache 60%Cache CPU Cache 12 14 Cache 0.05 0.40 (12 + 14) + 0.05 0.60 12 =0.02 26 + 0.03 12 = 0.52+0.36 = 0.88 9 1 64 64
6 183 3 2 8 2 32 32 3 1 8 3 1 7 (1) 60% 40% (2) 8 (1) 1 5 2 5 1 = 1/5 = 0.2 W/C W Word C Cycle 2 = 0.60 0.2 + 0.4 0.25 = 0.22 W/C (2) 1 = 8/8 = 1 W/C 2 = 0.60 8/12 + 0.4 8/11 = 0.69 W/C (1) (2) 10 33MHz 4 Cache 4 (1) 2 4 4 (2) 1 4 4 (1) 1+2+4=7 4 4=16 16 33M/7=75.43MB/s (2) 1+1+4=6 4 4=16 16 33M/6=88MB/s
7 7.1 7.1.1 1 1 2 CRT LCD 3 3 2 1 RLL 2 = 512 3 4
7 185 4 3 RAID RAID-0 RAID-1 RAID-2 RAID-3 RAID-4 RAID-5 RAID-6 RAID RAID 4 WORM 3 WORM 1 0 WORM 1 0 7.1.2 1
186 CPU DMA CPU 2 CPU 3 IO 1 2 3 4 - - 5 6 4 CPU CPU CPU CPU CPU CPU CPU 7.1.3 1 CPU
7 187 CPU CPU CPU CPU CPU 3 CPU 2 CPU PC 3
188 CPU CPU 3 CPU CPU CPU CPU CPU 1 0 7.1.4 DMA 1 DMA DMA CPU DMA DMA DMA IO CPU 2 DMA DMA DMA 1 1
7 189 0 0 DMA CPU DMA 3 DMA 1 DMA 3 CPU CPU CPU 2 DMA CPU 3 CPU DMA DMA CPU DMA 7.1.5 1 1 DMA CPU CPU CPU 2 3 2
190 CPU 7.2 1 0 1 0 1 0 1 0 2 RLL 0 1 DMA CPU CPU CPU 1 RAID 2
7 191 3 4 5 6 7 8 9 10 11 CPU 12 13 CPU 14 3 15 16 CPU 8 0 7 CPU 4 CPU 17 18 3 19 20 DMA 3 21 22 23 24 25 26 CPU 27
192 1 RAID-6 RAID-2 RAID-3 RAID-4 RAID-5 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 4 17 18 19 20 21 22 23 24 25 26 PC 27 1 CRT 16 16 80 25 60 RAM a) 2µs b) 0.5µs c) 1µs d) 1.5µs 2 CRT a) b) c) d) 3 a) b) c) c)
7 193 4 a) b) c) d) 5 a) b) c) ROM d) 6 a) ROM b) c) d) 7 a) b) c) FM d) 8 a) b) c) d) ST506/412 9 a) b) c) d) 10 a) b) c) d) 11 a) b) c) d) 12 0 1 a) b) c)
194 d) 13 a) b) c) d) 14 RLL a) b) c) d) 15 a) ST506/412 b) ST506/412 c) d) 16 a) 1/2 b) 1/3 c) 2/3 d) 1 17 a) b) c) d) 18 a) b) c) d) 19 I/O a) b) c) d) 20 a) b) c) d) 21 a) b) c) d) 22 a) b) DMA c) DMA d) DMA 23 a) b) c)
7 195 d) 24 a) b) DMA c) DMA CPU DMA d) 25 a) b) CPU c) d) DMA 26 a) DMA b) SCSI c) d) 27 a) b) c) d) 28CPU a) b) c) d) Cache 29 a) b) c) d) 30 ALU a) b) c) d) 31 a) b) c) d) 32 a) b) c) DMA d) 33 a) b) c) DMA d) 34 CPU a) b) c) d)
196 35 a) b) c) d) 36 a) b) CPU c) CPU d) CPU 37 a) DMA b) DMA CPU c) d) DMA 38 DMA CPU DMA a) CPU b) c) d) DMA 39 DMA CPU a) CPU b) c) d) DMA 40 a) b) c) d) 41 a) b) c) d) 42 a) b) DMA c) d) 43 a) b) c) d) DMA 44 CPU a) b) c) I/O d) 45 a) b) c) d) 1 b 2 a 3 a 4 c 5 a 6 d 7 b 8 a 9 c 10 c
7 197 11 d 12 d 13 a 14 b 15 d 16 a 17 b 18 d 19 a 20 c 21 d 22 a 23 c 24 b 25 d 26 a 27 c 28 c 29 b 30 a 31 a 32 b 33 c 34 b 35 c 36 a 37 d 38 a 39 b 40 a 41 b 42 d 43 c 44 c 45 d 1 n r/min 4 m 256 (1) (2) (3) (1) 4 256 m=1024m (2) nm /min (3) 1/(2n) min 2 : (1) CPU (2) (3) (trap) 3 (1) CPU (2) (3) (4) PC (5)
198 4 1CPU 2 5 6 CPU CPU (1) (2) (3) (4) (5) 7 CPU CPU 8 CPU CPU CPU
7 199 9 CPU 10 DMA DMA DMA 11 DMA DMA CPU DMA DMA DMA CPU DMA DMA CPU 12 DMA DMA CPU CPU DMA 7-1 7-1 13 CPU CPU CPU
200 14 3 5Mb/s 6Mb/s 8Mb/s 8Mb/s 7.3 1?? 3 (1) 68ms (2) (3) (4) (5) 48~135 TPI 8717 ~17434 5.25 3.5 3 2 CD-ROM CD-I DVI Photo CD 20 70 1978 LV 1982 CD-DA(Compact Disk-Digital Audio) CD-DA CD-DA PCM EFM 120mm 0.12µm 0.5µm ~0.6µm T 0.3µm 11T 3T 1 0 1.6µm 160000 5km 8 780nm 1.2m/s
7 201 CD-ROM 1985 1982 CD-DA CD-ROM 1-10 13 2 10 9 CD-ROM 1986 CD-ROM High Sierra High Sierra CD-ROM ISO 9660 1988 CD-ROM/XA 1991 CD-R CD-ROM CD-ROM CD-ROM DVD 1996 DVD CD 650nm 635nm 0.4µm 0.74µm 3.49m/s DVD 8-16EFM PLUS RS-PC(Reed Solomon Product Code)DVD 4 DVD 4.7GB 8.5GB 9.5GB 17GB DVD 10.8MB/s DVD 3 8 4970 63 3600 rpm (1) (2) (3) (4) (1) 8 2 = 16 (2) 4970 (3) 16 4970 63 512 = 2504880 KB (4) 63 512 3600/60 = 1890 KB/s
202 4 t s = r = / n = N = t A = t A t A = t s + 1/(2*r) + n/(n*r) 5 20ms 1MB/s 2ms 5400 512 = 0.5/5400 = 0.0056 = 5.6ms = + + + = 20ms + 5.6ms + 0.5KB/1.0MB/s + 2ms = 20+5.6+0.5+2ms = 28.1ms 6 20MB/s 5400rpm 10ms 64KB 0.5ms Cache (1) Cache 64KB (2) Cache 64KB Cache Cache (3) Cache 0.8 (1) = + + + =0.5 + 10 + (1/2)(60/5400) + max{(64/64)( 60/5400),64K/20M} =0.5 + 10 + 5.56 + max{11.11,3.12}=27.17 ms (2) = +=0.5+3.12=3.65ms (3) =0.8 3.65+(1 0.8) 27.17=2.92+5.43=8.35 ms 7 50s CPU 30s I/O 30s CPU 4 50s CPU I/O 60s 10s T workload = T CPU + T I/O T overlap
7 203 T workload T CPU CPU T I/O I/O T overlap CPU I/O CPU S CPU T CPU (1) CPU I/O T I/O (a) T scale = T CPU /S + T I/O T overlap /S CPU T CPU T scale = 30/5 + 30 10/5 = 34 I/O T I/O (2) CPU (b) CPU CPU I/O T worst = T CPU /S + T I/O max{0, T overlap (c) (T CPU T CPU /S)} CPU I/O T worst = 30/5 + 30 = 36 (d) (3) CPU 7-2 T best = T CPU /S + T I/O min{t overlap, T CPU /S} T best = 30 8 64s CPU I/O 36s CPU 2 CPU I/O 1 7-3 64 CPU I/O 36 7-3 S cpu = 3 T scaled = 64/3 + 36 36/3 = 45.3
204 T best = 36 T worst = 64/3 + 36 0 = 57.3 S cpu =2, S i/o =2 CPU T scaled = 64/2 + 36/2 36/max(2,2) = 32 T best = 32 T worst = 32 CPU T scaled = 64/2 + 36/2 36/max(2,2) = 32 T best = 32 T worst = 64/2 + 36/2 max{0, (36 (64 64/2))} = 32 +18 4 = 46 9 5 1 2 3 4 5 1 4 5 2 3 - L 1 L 2 L 3 L 4 L 5 L 1 1 1 1 1 1 L 2 0 1 1 0 0 L 3 0 0 1 0 0 L 4 0 1 1 1 1 L 5 0 1 1 0 1 10 5 D1 D2 D3 D4 D5 1 2 3 4 5 7-1 5 0 1 7-1 D1 D2 D3 D4 D5 D1 D2 D3 D4 D5 D1 1 1 1 1 1 1 1 0 0 0 0 D2 2 0 1 1 1 1 1 1 0 0 0 D3 3 0 0 1 1 1 1 1 1 0 0 D4 4 0 0 0 1 1 1 1 1 1 1 D5 5 0 0 0 0 1 1 1 1 0 1 (1) (2)
7 205 (3) D1 D2 D3 D4 D5 5 (1) 1 2 3 4 5 (2) 1 2 3 4 5 4 5 3 2 1 (3) D1 D2 D3 D4 D5 5 7-4 1 2 3 4 5 7-4 11 8 1 2 3 4 5 6 7 8 1 3 5 7 2 4 6 8 CPU 5 6 7 8 4 CPU 3 3 CPU CPU 7-5 5 7 6 3 6 8 12
206 1 2 3 4 5 6 7 8 7-5 IG IG IGin IGout 1 IGin 0 0 IGout IG 1 BGI 0 IGout 1 IGin 1 IGout 7-6 IGin S Q R IGout IR 7-6 13 3 100 CPU 50MHz CPU 3 I/O (1) 30 (2) CPU 16 50KB/s (3) 32 2MB/s (1) 30 100=3000 ( )
7 207 CPU 3000/(50 1000000)=0.006% CPU (2) 50KB/2B=25K=25600 () 25600 100=2560000 CPU 2560000/(50 1000000)=5% (3) 2MB/4B=512K () 512 1024 100 = 52.4 1000000 CPU 52.4/50 = 105% CPU 14 13 16 50KB/s () 100 CPU CPU 50KB/2B = 25K = 25600 ( / ) 25600 100 = 2560000 CPU 2560000/(50 1000000) = 5% 15 13 14 DMA DMA 1000 DMA 500 2MB/s DMA 4KB 50MHz DMA DMA 4KB/2MB = 0.002 (s) (1000+500)/0.002 = 750000 CPU 750000/(50 1000000) = 1.5%
208 16 I/O 100MB/s CPU 80MIPS 2 2 15000 4000 100 2.5 100MB 500 3.5 250MB 1250 30 TP-1 1000TPS 10GB TP-1 1 10G/100M = 100 (2+2) 15000 + 4000 = 64000 100 100 30 = 3000 3000/4 = 750 100M/(4 100) = 250000 CPU 80M/64000 = 1250 min(750, 250000, 1250) = 750 2 10G/250M = 40 40 30=1200 1200/4 = 300 min(300, 250000, 1250) = 300 17 16 100 500 = 50, 000 50000/750 = 66.7 40 1250 = 50, 000 50000/300 = 166.7 18 17 CPU 100MB/s I/O TP-1 I/O 100M = 250000 4 100 CPU 64000 250000 = 16GIPS I/O 19 32 2 1 2 2 2 2 10
7 209 800KB/s 200KB/s 6.6KB/s 1.2KB/s 1KB/s 800KB/s 2 6.6KB/s + 2 1.2KB/s + 10 1KB/s = 25.6 KB/s 2 800KB/s + 25.6 KB/s = 1625.6 KB/s 20 SCSI 20MB/s (1) SCSI 500KB/s 4MB/s 6MB/s 20MB/s (2) 4ms 64KB 4ms 256KB (1) r 1 r 2 4 r 1 + n r 2 20 = 20 n = (20 4r 1 )/(20r 2 ) 1 (2) 64KB/4MB/s=16ms 256KB/20MB/s = 12.8ms =16/ 16+4 =0.80 =12.8/ 12.8+4 =0.76
9 inter-connection network 9.1 9.1.1 1 2
9 251 9.1.2 1 2 3 9.1.3 1 N N 1 1 N(N 1)/2 O(N 2 ) 2 1 1 N 1/N
252 M M>1 M 1 N M/N m n 2 2 3 N 0 1N 1 i (i 1)mod N 0 i N 1 n/2 2 N 1 2 n/2 4 2N 4 ( ) i (i 1)mod N (i+w)modn (j W) mod N0 i N 1 W N/2 4 4 2(n 1) n= N n 2n(n 1) 4 2 n/2 2n 2N Illiac-IV PE 0 PE N 1 PE i PE i+1 PE i 1 PE i+r PE i r r= N i (i+1) mod N i (i-1) mod N i (i+r) mod N i (i-r) mod N 5 n N=2 n n=log 2 N n nn/2 N/2 N
9 253 N=2 n+r n 2 r 3 3N/2 3 n n M i 1 i n M N (x n x n-1 x 1 ) (1 i n 0 i=1 i = x i M i 1)(x n x n 1 x i+1 x i x i 1 x 1 )(x n x n 1 x i+1 x i x i 1 x 1 ) 0 x i M i 1 x i x i M i i (M i 1) d d = n ( M i i= 1 L = N d/2 n x x i =(x i 1) mod M i 2n d= M i /2 L=nN N= M i k-ary n-cube k N k n (x n x n 1 x i+1 x i x i 1 x 1 ) (x n x n 1 x i+1 ((x i 1) mod k)x i 1 x 1 ) 2n nn 2k n 1 k 2 n k/2 k>2 k-ary n-cube k-ary n-cube n=2 k-ary n-cube (k=2) 9.1.4 1 1 N 0 N 1 2 x f (x) x 1)
254 3 I(x n 1x n 2 x 1 x 0 ) = x n 1x n 2 x 1 x 0 x n 1x n 2 x 1 x 0 E(x n 1x n 2 x 1 x 0 ) = x n 1x n 2 x 1 x 0 C k (x n 1x n 2 x k+1 x k x k 1 x 1 x 0 )= x n 1x n 2 x k+1 x k x k 1 x 1 x 0 σ (x n 1x n 2 x 1 x 0 ) = x n 2x n 3 x 1 x 0 x n 1 σ -1 (x n 1x n 2 x 1 x 0 ) = x 0 x n 1x n 2 x 1 σ (k)(x n 1x n 2 x k+1 x k x k 1 x 1 x 0 ) = x n 1x n 2 x k+1 x k 1 x 1 x 0 x k σ (k) (x n 1x n 2 x n kx n k 1 x 1 x 0 ) = x n 2x n 3 x n k 1x n 1x n k 2 x 1 x 0 0 k n 1 0 k n 1 (x n 1x n 2 x 1 x 0 ) = x 0 x n 2 x 1 x n 1 (k) (x n 1x n 2 x k+1 x k x k 1 x 1 x 0 ) = x n 1x n 2 x k+1 x 0 x k 1 x 1 x k (k) (x n 1x n 2 x n kx n k 1x n k 2 x 1 x 0 ) = x n k 1x n 2 x n kx n 1x n k 2 x 1 x 0 (x n 1x n 2 x 1 x 0 ) = x 0 x 1 x n 2x n 1 (x) = (x+k) mod N, 0 x N 2 i PM2I PM 2+i (x) = (x + 2 i ) mod N PM 2 i(x) = (x 2 i ) mod N 0 x N 1 0 i log 2 N 1 2 N N N!
9 255 m=log 2 N m 9.1.5 2 2 a b 2 2 n=log 2 N N N/2 c) STARAN STARAN n=log 2 N 2 2 STARAN 0 2 n n n=log 2 N 2 2 n 3 n=log 2 N 2 2 STARAN STARAN n 3
256 0 C0 1 C1 4 Delta Delta a b a N a n b n Delta Delta STARAN n Delta 5 PM2I j(0 j N 1) 3 j j+2 i mod N j 2 i mod N 3 U i H i D i 3 6 L Delta b a STARAN n 7
9 257 3 2log 2 N 1 8 Clos Clos r 1 m r 2 n 1 m r 1 m n 2 Clos r 1 r 2 n 1 n 2 Benus 2 2 Clos Benus Benus Benus N Benus 2log 2 N 1 9.2
258 N N 2 2N N 2 n k-ary n-cube n k-ary n-cube 1 2 3 4 5
9 259 6 7 8 9 10 16 11 4 12 4 1010 0101 13 4 1010 14 3-ary 4-cube 15 8 5 16 17 8 STARAN 2 2 18 3 2 Delta 19 8 8 20 N N (N=2 n ) Shuffle(b n-1 b n-2 b 1 b 0 ) 21 a) STARAN b) n c) d) 22 16 Close 2 2 23 8 Benus 1 2 3 4 5 2 2 6 N 1 1 7 3 8 4 9 10 4 4 11 16 4 12 1011 1001 1101
260 13 1011 1000 1110 0010 14 4 81 15 4 16 N! 17 12 18 27 8 19 19 14 20 b n 2 b 1 b 0 b n 1 21 d 22 3 2 23 5 1 a) b) c) d) 2 a) b) c) d) 3 a) b) c) d) 4 a) 2 b) c) d) 5 a) b) c) d) 6 a) b) c) d) 7 a) (0 1)(2 3)(4 5)(6 7) b) (0 2)(1 3)(4 6)(5 7) c) (0 4)(1 5)(2 6)(3 7) d) (0 1 2 3)(4 5 6 7) 8 a) (0 1 2 3)(4 5 6 7) b) (0)(1 2 4)(3 6 5)(7) c) (0)(1 2 3)(4 5 6)(7) d) (0)(1 2 4 3 5 6)(7) 9 PM2 1 a) ( 6 4 2 0)(7 5 3 1) b) (0 2 4 6)(1 3 5 7) c) (0 1 2 3 4 5 6 7) d) (7 6 5 4 3 2 1 0)
9 261 10 a) b) c) d) 11 16 9 13 a) Cube3 b) PM2 +2 c) PM2 +4 d) 12 a) b) c) d) 13 a) b) c) d) 14 a) b) c) d) 15 a) b) c) d) 16 STARAN a) b) c) d) 17 n a) b) c) d) 18 4 2 0 1 2 3 4 5 6 7 a) 2 3 4 5 6 7 0 1 b) 2 3 0 1 6 7 4 5 c) 1 0 3 2 5 4 7 6 d) 4 5 6 7 0 1 2 3 19 8 2 0 1 2 3 4 5 6 7 a) 2 3 4 5 6 7 0 1 b) 2 3 0 1 6 7 4 5 c) 1 0 3 2 5 4 7 6 d) 4 5 6 7 0 1 2 3 20 a) b) STARAN c) d) Omega 21 Omega a) b) c) d) 22 Omega a) 2 2 b)
262 c) d) 23 a) 2 2 b) 2 2 c) d) 24 a) b) c) d) 25 a) b) c) d) 26 a) b) c) d) 27 a) STARAN b) n c) d) 26 a b(a b) Delta a) b) c) d) 1 a 2 a 3 c 4 c 5 c 6 d 7 a 8 b 9 a 10 a 11 b 12 b 13 a 14 b 15 a 16 d 17 d 18 b 19 a 20 d 21 b 22 b 23 d 24 c 25 a 26 c 27 d 28 a 1 2
9 263 3 1 2 2 4 1 4 1 2 2 1 0 1 1 0 2 3 3 2 2 4 4 2 0 2 1 3 2 0 3 1 1 4 4 1 0 1 1 2 2 3 3 0 4 16 Omega Omega 16 Omega 4 9.3 1 4 4 (mesh) (1) (2) (3) (4) (1) 9-1 9-1 (2) (3) (0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,0), (2,1), (2,2), (2,3), (3,0), (3,1), (3,2), (3,3) (4)
264 2 64 Illiac-IV Illiac-IV 9-2 9-2 Illiac-IV 3 3 3 3 3 9-3 9-3 3 4 k-ary 3-cube (1) (2) (3) (4)
9 265 (5) k-ary 3-cube 3 k (1) k 3 (2) 3 k /2 (3) 3k 3 (4) 2k 2 (5) 6 5 16 0 115 (1) (2) 2 i PM 2+3 PM 2 1 (3) (4) 9? (1) E(1001) = 1000 9 8 (2) PM2 +3 (1001) = (1001+1000) mod 10000 = 0001 9 1 PM2-1 (1001) = (1001 0010) mod 10000 = 0111 9 7 (3) shuffle(1001) = 0011 9 3 (4) Butterfly(1001) = 1001 9 9 6 8 (1) (2) (3) (4) 2 i (1) (0)(1)(2)(3)(4)(5)(6)(7) (2) (0 1)(2 3)(4 5)(6 7) (3) C0 (0 1)(2 3)(4 5)(6 7) C1 (0 2)(1 3)(4 6)(5 7)
266 C2 (0 4)(1 5)(2 6)(3 7) (4) 2 i PM 2+0 (0 1 2 3 4 5 6 7) PM 2 0 (7 6 5 4 3 2 1 0) PM 2+1 (0 2 4 6)(1 3 5 7) PM 2 1 (6 4 2 0)(7 5 3 1) PM 2 2 (0 4)(1 5)(2 6)(3 7) 7 128 0 1 2127σ(C 0 (PM 2-2 )) 8 128 7 PM 2-2 (0001000) = (1000-100) mod 128 = 000100 Cube 0 (0000100) = 0000101 shuffle(0000101 = 0001010 8 16 0 15 0 1 1 2 2 3 3 6 6 7 7 14 14 15 4 3 9 8 8 A=(a ij ) A A T ( 6 3 3 ) a ij i 1 i 2 i 3 j 1 j 2 j 3 i 1 i 2 i 3 j 1 j 2 j 3 i 2 i 3 j 1 j 2 j 3 i 1 i 2 i 3 j 1 j 2 j 3 i 1 i 3 j 1 j 2 j 3 i 1 i 2 i 3 j 1 j 2 j 3 i 1 i 2 j 1 j 2 j 3 i 1 i 2 i 3 a ji 10 8 STARAN 000 001 010 011
9 267 100 101 110 111 8 STARAN STARAN 9-4 0 1 A E I 0 1 2 3 4 5 6 7 B C D G F H J K L 0 1 2 0 1 2 2 3 4 5 6 7 9-4 000 001 010 011 100 101 110 111 0->0 0->1 0->2 0->3 0->4 0->5 0->6 0->7 1->1 1->0 1->3 1->2 1->5 1->4 1->7 1->6 2->2 2->3 2->0 2->1 2->6 2->7 2->4 2->5 3->3 3->2 3->1 3->0 3->7 3->6 3->5 3->4 4->4 4->5 4->6 4->7 4->0 4->1 4->2 4->3 5->5 5->4 5->7 5->6 5->1 5->0 5->3 5->2 6->6 6->7 6->4 6->5 6->2 6->3 6->0 6->1 7->7 7->6 7->5 7->4 7->3 7->2 7->1 7->0 11 STARAN 1 2 2 4 1 4 4 8 1 8 0 (A B C D)1 (E G) (F H) 2 (K L) (I) (J) STARAN (1) 0 C A = C B = C C = C D = 0 1 C F = C H = 0, C G = C E = 0 2 C K = C L = 0, C J = 0, C I = 0 (2) 1 2 0 C A = C B = C C = C D = 1 1 C F = C H = 0, C G = C E = 0
268 2 C K = C L = 0, C J = 0, C I = 0 (3) 2 4 0 C A = C B = C C = C D = 0 1 C F = C H = 1, C G = C E = 1 2 C K = C L = 0, C J = 0, C I = 0 (4) 1 4 0 C A = C B = C C = C D = 1 1 C F = C H = 0, C G = C E = 1 2 C K = C L = 0, C J = 0, C I = 0 (5) 4 8 0 C A = C B = C C = C D = 0 1 C F = C H = 0, C G = C E = 0 2 C K = C L = 1, C J = 1, C I = 1 (6) 1 4 0 C A = C B = C C = C D = 1 1 C F = C H = 0, C G = C E = 1 2 C K = C L = 0, C J = 0, C I = 1 12 I( x) c = 0 E c ( x) = E( x) c = 1 c STARAN STARAN 0 E c σ -1 E c σ -1 E c σ -1 E c σ -1 13? d=2 D=N/2 N d=4 D=2( N 1) 8( N 1) d=log 2 N D=log 2 N (log 2 N) 2 N 9-1 N 4 3
9 269 9-1 N 4 16 64 256 1024 4096 4 16 64 256 1024 4096 4 24 56 120 248 504 4 16 36 64 100 144 9-1 14 n n n β (1) β (2) β (n 1) σ 1 x n 1x n 2 x 1 x 0 β (1) x n 1x n 2 x 0 x 1 β (2) x n 1x n 2 x 1 x 0 x 2 β (n 1) x n 2x n 3 x 1 x 0 x n 1 x n 1x n 2 x 1 x 0 15 16 n 9-5 9-5 16 n 16 16 9-6
270 3 2 1 0 9-6 16 17 8 27 Delta 2 3 9-7 9-7 Delta 18 16 Benus 9-8
9 271 9-8 16 Benus 19 F S 2 SW F S F S N N*S N*S/F N*S 2 /F 2 N*S 2 /F 2 N S N S + F 2 20 2 2 N/2 N/4 N=16
272 9-9 9-9 (1) FFT (2)
P.9 1 1 2 3 P.17 22. a) b) c) d) P.27 13. 8 T T 25% P.33 3 0 0 P.40 1 21. 010101 8 P.41 1 22. 101010 8 P.42 20. P.44 8. 80 16 0 a) b) c) d) P.44-P45 15. a) b) IEEE 754 c) d) 16. a) b) c) d) 17. a) b) c)
d) 18. 1 3 6 2 27/64 a) 0 101 011011 b) 0 100 110110 c) 0 111 110110 d) 0 001 011011 19. 8 a) 1.000111 b) 0.000111 c) 1.001101 d) 0.000001 P.46 30. a) b) c) d) P.46 33 P.47 41. b P.47 (1) [x] =1000 1111 1110 1111 1100 0000 0000 0000 x=-0111 0000 0001 0000 0100 0000 0000 0000=-1880113152 P.87 3-8 A9~A1 AS# A9-7 3:8 A6~A1 WE# CPU we* A ce 64x1x16 D we* A ce 64x1x16 D we* A ce 64x1x16 D D 15-0 D 15-0 D 15-0 D15-0 P.88 6. 32 32 32 4Mb DRAM 32MB P.90 3-10
A 12-2 A 11-2 A 12 CPU CE A CE A CE A CE A CE A CE A CE A CE A 1Kx8 1Kx8 1Kx8 1Kx8 1Kx8 1Kx8 1Kx8 1Kx8 WE# D WE# D WE# WE# D WE# D WE# D WE# D WE# D R/W# D31 ~D 0 D 7-0 D 15-8 D 23-15 D 31-24 D 7-0 D 15-8 D 23-15 D 31-24 P.126 (1) 1000 (2) 2000 (3) 2000 (4) 3000 (5) 3000 (6) 2000 P.134 4-5 4-6 A>B C=0 Z=0 A B C=0 A<B C=1 A B C=1 Z=1 A=B Z=1 A B Z=0 A>B (S V)=0 Z=0 A B (S V)=0 A<B (S V)=1 A B (S V)=1 Z=1 A=B Z=1 A B Z=0 P.134 (4) A B C=1 0 Z=1 C=1 Z=1 P.135 8 (4) A B A>B (S V)=1 Z=1 P.148 15. a) b) c) d) P.148 17. a) b)
c) d) P.153 Y+0 Z Z MDR P.157 PC MAR PC + 1 PC DBUS MDR MDR IR R1 Y R1 MAR IR(mem) MAR DBUS MDR MDR MAR DBUS MDR MDR Y R2 +Y Z R2 MAR IR(mem) MAR MBUS MDR MDR MAR MBUS MDR MDR+Y Z Z R2 Z MDR, P.160 5-5
T1 T2 T3 T4 T5 D Q D Q D Q D Q D Q Q Q Q Q Q CLK P.174 12. P.174 20. b P.179 6-1 D0 D1 D2 D3 D4 D5 D6 D7 P.207 14. 13 16 50KB/S () 100 CPU P.208 4 CPU 64000 250000 = 16GIPS I/O P.214 11 (3) P.223 2 a) P.237 Load Add R1,R1,R0 Loadi R2, #1 Store Store Add R3,R3,R4 P.257 P.258 9 P.288 1 4 1 2 3 4 5 6 7 8 9 10 11 12 IF ID EX M WB IF ID - - EX M WB IF ID EX M WB IF ID - - - EX M WB IF ID - EX M WB IF ID - - EX M WB
100m P.289 [1] 1999