Hệ thống nhớ máy tính

1 KiÕn tróc m¸y tÝnh Ch¬ng 3- Hệ thống nhớ máy tính [email protected] 2 Néi dung về hệ thống nhớ  Tæng quan vÒ hÖ thèng nhí  Bé nhí b¸n dÉn  Bé nhí chÝnh  Bé nhí cache  Bé nhí ngoµi. 3 1. Tổng quan về hệ thống nhớ Bộ nhớ (memmory) là không gian làm việc của bộ vi xử lý. Đó là nơi cất giữ tạm thời các chương trình và dữ liệu đang được thao tác với bộ vi xử lý. Việc lưu trữ bộ nhớ được xem tạm thời vì dữ liệu chỉ tồn tại trong thời gian máy đang hoạt động và không bị khởi động lại. Trước khi khởi động lại hay tắt máy, dữ liệu đã thay đổi cần được ghi vào các thiết bị lưu trữ lâu dài – storage – (thường là ổ đĩa cứng) để sau này có thể nạp lại vào bộ nhớ. 4 Tổng quan về hệ thống nhớ Một điểm quan trọng mà chúng ta cần ghi nhớ đó là: một file khi được nạp vào trong bộ nhớ, nó chỉ là bản sao của file đó, còn thực chất file đó vẫn tồn tại trong ổ đĩa. Vì tính chất tạm thời của bộ nhớ cho nên file đã bị thay đổi cần được ghi lại vào đĩa cứng trước khi tắt máy, vì khi tắt máy dữ liệu trong bộ nhớ sẽ bị xoá. 5 Tổng quan về hệ thống nhớ Bộ nhớ lưu trữ các chương trình đang chạy và dữ liệu của chúng sử dụng. Các chip nhớ có lúc được gọi là “lưu trữ không ổn định” (volatile storage) bởi vì khi tắt máy hoặc có sự cố về nguồn điện, lưu trữ trong RAM sẽ bị mất. Vì bản chất bất ổn định như vậy cho nên nhiều người dùng có thói quen ghi lại thường xuyên (một số chương trình ứng dụng có thể ghi một cách tự động theo thời gian đã định). 6 2. C¸c ®Æc trng cña hÖ thèng nhí  VÞ trÝ (location) „ Bªn trong Bé xö lý: TËp c¸c thanh ghi, cache „ Bé nhí trong: Bé nhí chÝnh Bé nhí cache „ Bé nhí ngoµi: C¸c thiÕt bÞ nhí, §Üa tõ, b¨ng tõ §Üa quang  Dung lîng (capacity) „ §é dµi tõ nhí (®¬n vÞ lµ bit)- KÝch thíc trªn 1 ®¬n vÞ lu tr÷. „ Sè lîng tõ nhí- Dung lîng bé nhí 7 C¸c ®Æc trng cña hÖ thèng nhí  §¬n vÞ truyÒn (unit of transfer) „ TruyÒn theo tõ nhí- TruyÒn tuÇn tù tõng Word „ TruyÒn theo khèi nhí- TruyÒn 1 khèi gåm n Word  HiÖu n¨ng „ Thêi gian truy cËp. „ Chu kú truy xuÊt bé nhí. „ Tèc ®é truyÒn. 8 C¸c ®Æc trng cña hÖ thèng nhí  Ph¬ng ph¸p truy nhËp (access method) „ Truy nhËp tuÇn tù (b¨ng tõ)- §Ó ®Õn ®îc ®iÓm n ®Çu tõ ph¶i duyÖt qua n-1 vÞ trÝ tríc. „ Truy nhËp trùc tiÕp (®Üa tõ, ®Üa quang)- §Çu tõ di chuyÓn trùc tiÕp ®Õn vÞ trÝ cÇn ®äc. „ Truy nhËp ngÉu nhiªn (bé nhí trong)- « nhí cÇn ®äc sÏ ®îc gi¶i m· ®Ó lÊy th«ng tin ngay lËp tøc. „ Truy nhËp liªn kÕt (bé nhí cache)- Truy cËp th«ng qua b¶n sao cña « nhí cÇn ®äc. 9 C¸c ®Æc trng cña hÖ thèng nhí  KiÓu vËt lý cña bé nhí (physical type) „ Bé nhí b¸n dÉn- Lu tr÷ b»ng ®iÖn „ Bé nhí tõ- Lu tr÷ dïng tõ tÝnh. „ Bé nhí quang: Lu tr÷ sö dông c«ng nghÖ Laze  C¸c ®Æc trng vËt lý (physical characteristics) „ Bé nhí kh¶ biÕn / kh«ng kh¶ biÕn „ Bé nhí xãa ®îc / kh«ng xãa ®îc 10 3. M« h×nh ph©n cÊp hÖ thèng nhí Việc trao đổi dữ liệu giữa BVXL và BNC là một thao tác quan trọng, chiếm đa số trong các lệnh xử lý dữ liệu nên nó quyết định hiệu suất của hệ thống VXL nói chung và máy tính nói riêng. Bộ nhớ chính và bộ nhớ ngoài thường có tốc độ trao đổi dữ liệu chậm (chênh lệch) hơn so với tốc độ làm việc của CPU (kể cả việc vận chuyển dữ liệu trong BVXL). Để nâng cao tốc độ xử lý dữ liệu chung của toàn hệ thống, người ta tìm cách nâng cao tốc độ trao đổi dữ liệu (kể cả lệnh) giữa BVXL và bộ nhớ. Dựa trên nguyên lý cục bộ về không gian và thời gian mà người ta xây dựng hệ thống nhớ 5 cấp như sau: 11 3. M« h×nh ph©n cÊp hÖ thèng nhí CPU Registers 100s Bytes 1s ns Cache K Bytes 4 ns 1-0.1 cents/bit Main Memory M Bytes 100ns- 300ns $.0001-.00001 cents /bit Disk G Bytes, 10 ms (10,000,000 ns) 10 - 10 cents/bit Capacity Access Time Cost Tape infinite sec-min 10 -8 Upper Level -5 -6 Registers Cache Memory Disk Tape Instr. Operands Blocks Pages Files Staging Xfer Unit prog./compiler 1-8 bytes cache cntl 8-128 bytes OS 512-4K bytes user/operator Mbytes Lower Level faster Larger 12 3. M« h×nh ph©n cÊp hÖ thèng nhí Cấp 0: Tập các thanh ghi nằm trong bộ vi xử lý. Thanh ghi là bộ nhớ kiểu SRAM nên tác động nhanh và thông tin ổn định. Đây là thành phần nhớ có tốc độ trao đổi dữ liệu nhanh nhất trong hệ thống vì nó gần ALU và CU. Tuy nhiên nó có dung lượng nhỏ. 13 3. M« h×nh ph©n cÊp hÖ thèng nhí Cấp 1: Primary cache (cache sơ cấp): Là bộ nhớ có tốc độ trao đổi dữ liệu rất nhanh (nhỏ hơn thanh ghi), có dung lượng nhỏ và được đặt trong bộ vi xử lý, nhưng cũng có thể nằm ngoài bộ vi xử lý. Trong các bộ vi xử lý tiên tiến, bộ nhớ cache thường được tách (chia) làm 2 với mục đích tránh xung đột trong xử lý song song (đại diện là pipeline) là Icache: dành cho lệnh và Dcache: dành cho dữ liệu. 14 3. M« h×nh ph©n cÊp hÖ thèng nhí Cấp 2: Secondary cache (cache thứ cấp): Cũng giống như Primary cache, nhưng loại này nằm ngoài bộ vi xử lý. Nó chỉ có khi có Primary cache (ngược lại, nó chính là Primary cache). Dung lượng của Secondary cache thường lớn hơn Primary cache và nhỏ hơn bộ nhớ. 15 3. M« h×nh ph©n cÊp hÖ thèng nhí Cấp 3: Main Memory (Bộ nhớ chính): Chứa chương trình và dữ liệu đang hoạt động. BN này được BVXL đánh địa chỉ trực tiếp và quản lý thông qua địa chỉ đó. Một phần của chương trình đang được thi hành có thể nằm trong cache (lệnh và dữ liệu) nhằm tăng tốc độ hoạt động của hệ thống. Dung lượng của BN chính thường lớn hơn rất nhiều lần dung lượng BN cache. Như đã biết, trong các hệ thống máy tính hiện đại ngày nay thì BNC thường là DRAM. 16 3. M« h×nh ph©n cÊp hÖ thèng nhí Cấp 4: Secondary memory (Bộ nhớ thứ cấp – bộ nhớ ngoài): Bộ nhớ này có dung lượng rất lớn nhưng tốc độ trao đổi dữ liệu chậm. Bộ nhớ này để lưu trữ chương trình và dữ liệu một cách lâu dài, cho nhiều người sử dụng (ghi/đọc, mất nguồn điện vẫn còn thông tin). Đại diện cho các bộ nhớ loại này đó chính là các ổ đĩa cứng, mềm CD ROM, CD – WOM, CD WR, băng từ, … 17 3. M« h×nh ph©n cÊp hÖ thèng nhí Tõ tr¸i sang ph¶i: „ Dung lîng t¨ng dÇn „ Tèc ®é trao ®æi d÷ liÖu gi¶m dÇn „ Gi¸ thµnh /1 bit gi¶m dÇn „ TÇn suÊt BXL truy nhËp gi¶m dÇn „ Møc tr¸i chøa mét phÇn d÷ liÖu cña møc ph¶i TËp thanh ghi Cache L1 Cache L2 Bé nhí chÝnh Bé nhí ngoµi Bé xö lý 18 4. Bé nhí b¸n dÉn  Ph©n lo¹i  Tæ chøc chip nhí b¸n dÉn  ThiÕt kÕ c¸c modul nhí b¸n dÉn  Bµi tËp 19 Bé nhí b¸n dÉn KiÓu bé nhí Tiªu chuÈn Kh¶ n¨ng xãa C¬ chÕ ghi TÝnh thay ®æi Read Only Memory (ROM) Bé nhí chØ ®äc Kh«ng xãa ®îc MÆt n¹ Kh«ng kh¶ biÕn Programmable ROM (PROM) B»ng ®iÖn Erasable PROM (EPROM) Bé nhí hÇu nh chØ ®äc B»ng tia cùc tÝm, c¶ chip Electrically Erasable PROM (EEPROM) B»ng ®iÖn, møc tõng byte Flash memory Bé nhí ®äc - ghi B»ng ®iÖn, tõng khèi Random Access Memory (RAM) B»ng ®iÖn, tõng byte Kh¶ biÕn 20 ROM (Read Only Memory)  Lµ lo¹i bé nhí kh«ng kh¶ biÕn  Lu tr÷ c¸c th«ng tin: „ Th viÖn c¸c ch¬ng tr×nh con „ C¸c ch¬ng tr×nh hÖ thèng (BIOS) „ C¸c b¶ng chøc n¨ng „ Vi ch¬ng tr×nh 21 C¸c kiÓu ROM  ROM mÆt n¹ (ROM cè ®Þnh): „ Th«ng tin ®îc ghi ngay khi s¶n xuÊt „ RÊt ®¾t  PROM (Programmble ROM): „ Khi s¶n xuÊt cha ghi d÷ liÖu „ CÇn thiÕt bÞ chuyªn dïng ®Ó ghi b»ng ch¬ng tr×nh, chØ ghi ®îc mét lÇn  EPROM (Erasable PROM): „ Khi s¶n xuÊt cha ghi d÷ liÖu „ CÇn thiÕt bÞ chuyªn dông ®Ó ghi b»ng ch¬ng tr×nh, ghi ®- îc nhiÒu lÇn „ Tríc khi ghi l¹i, ph¶i xãa b»ng tia cùc tÝm 22 C¸c kiÓu ROM  EEPROM (Electrically Erasable PROM): „ Cã thÓ ghi theo tõng byte „ Xãa b»ng ®iÖn „ Ghi l©u h¬n ®äc  Flash memory (bé nhí cùc nhanh) „ Ghi theo khèi „ Xãa b»ng ®iÖn 23 RAM (Random Access Memory)  Bé nhí ®äc / ghi  Kh¶ biÕn  Lu tr÷ th«ng tin t¹m thêi  Cã hai lo¹i RAM: „ SRAM (Static RAM) „ DRAM (Dynamic RAM) 24 C¸c kiÓu RAM  DRAM „ C¸c bit ®îc lu tr÷ trªn tô ®iÖn  cÇn ph¶i cã m¹ch lµm t¬i „ CÊu tróc ®¬n gi¶n „ Dung lîng lín „ Tèc ®é chËm h¬n SRAM „ RÎ h¬n SRAM „ Dïng lµm bé nhí chÝnh 25 C¸c kiÓu RAM  SRAM „ C¸c bit ®îc lu tr÷ b»ng c¸c Flip-Flop „ Kh«ng cÇn m¹ch lµm t¬i „ CÊu tróc phøc t¹p h¬n DRAM „ Dung lîng nhá „ Tèc ®é nhanh h¬n DRAM „ §¾t h¬n DRAM „ Dïng lµm bé nhí cache 26 VÝ dô vÒ DRAM 27 Tæ chøc « nhí  ¤ nhí lµ phÇn tö nhí ®îc 1 bit th«ng tin  C¸c tÝn hiÖu: „ TÝn hiÖu chän ®îc göi ®Õn ®Ó chän « nhí „ TÝn hiÖu ®iÒu khiÓn chØ thÞ viÖc ghi hay ®äc „ TÝn hiÖu thø ba lµ ®êng d÷ liÖu Chän §iÒu khiÓn D÷ liÖu vµo Chän §iÒu khiÓn D÷ liÖu ra ¤ nhí ¤ nhí a) Ghi b) §äc 28 Tæ chøc cña chip nhí (SRAM) Chip nhí D 0 D 1 D m - 1 A 0 A 1 A n - 1 CS RD WR . . . . . . . . 29 C¸c tÝn hiÖu cña chip nhí (SRAM)  C¸c ®êng ®Þa chØ: A0  An - 1  cã 2 n ng¨n nhí.  C¸c ®êng d÷ liÖu: D0  Dm - 1  ®é dµi ng¨n nhí lµ m bit.  Dung lîng chip nhí: 2n x m bit  C¸c ®êng ®iÒu khiÓn: „ TÝn hiÖu chän chip: CS (Chip Select)/CE „ TÝn hiÖu ®iÒu khiÓn ®äc: RD / OE „ TÝn hiÖu ®iÒu khiÓn ghi: WR / WE 30 Tæ chøc cña DRAM  Dïng n ®êng ®Þa chØ dån kªnh  cho phÐp truyÒn 2n bit ®Þa chØ  TÝn hiÖu chän ®Þa chØ hµng RAS (Row Address Select)  TÝn hiÖu chän ®Þa chØ cét CAS (Column Address Select)  Dung lîng cña DRAM: 22n x m bit 31 VÝ dô: chip 16Mb DRAM (4M x 4 bit) 32 C¸c chip nhí (nh×n bªn ngoµi) 33 ThiÕt kÕ modul nhí b¸n dÉn  Dung lîng chip nhí lµ 2n x m bit  CÇn thiÕt kÕ ®Ó t¨ng dung lîng: „ T¨ng ®é dµi ng¨n nhí (t¨ng m) „ T¨ng sè lîng ng¨n nhí (t¨ng n) „ KÕt hîp c¶ hai lo¹i (t¨ng m vµ n) 34 T¨ng ®é dµi ng¨n nhí  VÝ dô 1: „ Cho chip nhí SRAM: 8K x 4 bit „ H·y thiÕt kÕ modul nhí 8K x 8 bit  Gi¶i: „ Dung lîng chip nhí: 213 x 4 bit „ Chip nhí cã: 13 ®êng ®Þa chØ (A0  A12), 4 ®êng d÷ liÖu (D0  D3) „ Modul nhí cÇn cã: 13 ®êng ®Þa chØ (A0  A12), 8 ®êng d÷ liÖu (D0  D7) 35 H×nh vÏ (vÝ dô 1) A0  A12 8K x 4 bit D0  D3 CS WE OE A0  A12 A0  A12 8K x 4 bit D0  D3 CS WE OE CS WE OE D0D3 D4D7 36 T¨ng ®é dµi ng¨n nhí Bµi to¸n t¨ng ®é dµi tæng qu¸t:  Cho chip nhí 2n x m bit  CÇn thiÕt kÕ modul nhí 2n x (k.m) bit  CÇn ghÐp nèi k chip nhí (k>=1) 37 T¨ng sè lîng ng¨n nhí  VÝ dô 2: „ Cho chip nhí SRAM: 4K x 4 bit „ H·y thiÕt kÕ modul nhí 8K x 4 bit  Gi¶i: „ Dung lîng chip nhí: 212 x 4 bit „ Chip nhí cã: 12 ®êng ®Þa chØ (A0  A11), 4 ®êng d÷ liÖu (D0  D3) „ Modul nhí cÇn cã: 13 ®êng ®Þa chØ (A0  A12), 4 ®êng d÷ liÖu (D0  D3) 38 H×nh vÏ (vÝ dô 2) A0A11 D0D3 CS WE OE A0A11 D0D3 CS WE OE G A Y1 Y0 0 0 0 1 0 1 1 0 1 X 1 1 A0  A11 WE OE A Y0 G Y1 A12 D0  D3 CS 39 T¨ng sè lîng ng¨n nhí  Bµi to¸n t¨ng sè lîng tæng qu¸t:  Cho chip nhí 2n x m bit  CÇn ghÐp nèi modul nhí: 2k+n x m bit  CÇn ghÐp nèi 2k chip vµ ph¶i dïng bé gi¶i m· k: 2k (k  2k) 40 T¨ng sè lîng vµ ®é dµi ng¨n nhí  VÝ dô 3: „ Cho chip nhí SRAM: 8K x 4 bit „ H·y thiÕt kÕ modul nhí 16K x 8 bit  Gi¶i: „ Dung lîng chip nhí: 213 x 4 bit „ Chip nhí cã: 13 ®êng ®Þa chØ (A0  A12), 4 ®êng d÷ liÖu (D0  D3) „ Modul nhí cÇn cã: 14 ®êng ®Þa chØ (A0  A13), 8 ®êng d÷ liÖu (D0  D7) 41 H×nh vÏ (vÝ dô 3) A0A12 D0D3 CS WE OE A0A12 D0D3 CS WE OE A0A12 D0D3 CS WE OE A0A12 D0D3 CS WE OE A Y0 G Y1 A0A12 WE OE A13 CS D0D7 D0D7 42 T¨ng sè lîng vµ ®é dµi ng¨n nhí  Bµi to¸n t¨ng sè lîng vµ ®é dµi tæng qu¸t:  Cho chip nhí 2n x m bit  CÇn ghÐp nèi modul nhí: 2p+n x (q.m) bit  CÇn ghÐp nèi q.2p chip thµnh 2p bé, mçi bé q chip vµ ph¶i dïng bé gi¶i m· p: 2p (p  2p) 43 5. Bé nhí chÝnh  C¸c ®Æc trng c¬ b¶n „ Chøa c¸c ch¬ng tr×nh ®ang thùc hiÖn vµ c¸c d÷ liÖu ®ang ®îc sö dông „ Tån t¹i trªn mäi hÖ thèng m¸y tÝnh „ §îc ®¸nh ®Þa chØ trùc tiÕp bëi CPU: cã nhiÒu ng¨n nhí, mçi ng¨n nhí ®îc g¸n mét ®Þa chØ x¸c ®Þnh „ ViÖc qu¶n lý l«gic BNC tïy thuéc vµo tõng H§H „ VÒ nguyªn t¾c, ngêi lËp tr×nh cã thÓ can thiÖp trùc tiÕp vµo toµn bé BNC cña m¸y tÝnh 44 Bé nhí chÝnh  Tæ chøc bé nhí ®an xen „ §é réng cña bus d÷ liÖu ®Ó trao ®æi víi bé nhí: m = 8, 16, 32, 64, ... bit „ C¸c ng¨n nhí tæ chøc theo byte 45 VÝ dô: m = 8 bit Bus hÖ thèng Bank nhí §Þa chØ 0 1 2 3 n . . . . . 46 m = 16 bit Bus hÖ thèng Bank 0 Bank 1 §Þa chØ . . . . . 0 2 4 6 2n §Þa chØ 1 3 5 7 2n+1 . . . . . 47 m = 32 bit Bus hÖ thèng Bank 0 §Þa chØ . . . . . 0 4 8 12 4n Bank 1 §Þa chØ . . . . . 1 5 9 13 4n+1 Bank 2 §Þa chØ . . . . . 2 6 10 14 4n+2 Bank 3 . . . . . 3 7 11 15 4n+3 §Þa chØ 48 6. Bé nhí cache  Nguyªn t¾c chung  C¸c kü thuËt ¸nh x¹ ®Þa chØ  C¸c thuËt to¸n thay thÕ  Ho¹t ®éng cña cache  Bµi tËp 49 Nguyªn t¾c chung  Cache cã tèc ®é nhanh h¬n bé nhí chÝnh  Cache ®îc ®Æt gi÷a CPU vµ bé nhí chÝnh nh»m t¨ng tèc ®é truy nhËp bé nhí cña CPU  Cache cã thÓ ®îc ®Æt trªn chip CPU 50 C¸c kh¸i niÖm  Cache hit, cache miss: „ Cache hit (tróng cache): khi CPU truy nhËp mét tõ nhí mµ tõ nhí ®ã ®ang cã trong cache. „ Cache miss (trît cache): khi CPU truy nhËp mét tõ nhí mµ tõ nhí ®ã kh«ng cã trong cache.  Nguyªn lý ®Þnh vÞ tham sè bé nhí: „ §Þnh vÞ vÒ thêi gian: Mét môc th«ng tin võa ®îc truy nhËp th× cã x¸c suÊt lín lµ ngay sau ®ã nã ®îc truy nhËp l¹i. „ §Þnh vÞ vÒ kh«ng gian: Mét môc th«ng tin võa ®îc truy nhËp th× cã x¸c suÊt lín lµ ngay sau ®ã c¸c môc l©n cËn sÏ ®îc truy nhËp. 51 C¸c kh¸i niÖm  Trao ®æi th«ng tin gi÷a cache vµ BNC: „ BNC ®îc chia thµnh c¸c Block nhí „ Cache ®îc chia thµnh c¸c Line nhí „ KÝch thíc Line b»ng kÝch thíc Block  Sè lîng Line << Sè lîng Block  Mçi Line trong cache ®îc g¾n thªm mét Tag ®Ó x¸c ®Þnh Block nµo (cña BNC) ®ang ë trong Line 52 H×nh vÏ minh häa BXL Tag D÷ liÖu Bé nhí cache Bé nhí chÝnh L 0 L 1 L m-2 L m-1 B 0 B 1 B 2 B p-2 B p-1 . . . . . . . . . . . . . . 53 C¸c kü thuËt ¸nh x¹ ®Þa chØ  Ánh x¹ trùc tiÕp (direct mapping)  Ánh x¹ liªn kÕt hoµn toµn (fully associative mapping)  Ánh x¹ liªn kÕt tËp hîp (set associative mapping) 54 Ánh x¹ trùc tiÕp  Mçi Block cña BNC chØ ®îc ¸nh x¹ vµo mét Line duy nhÊt: i = j mod m „ i: sè hiÖu Line trong cache „ j: sè hiÖu Block trong BNC „ m: sè lîng Line trong cache  Cô thÓ: B0  L0 Bm  L0 . . . B1  L1 Bm+1  L1 . . . . . . . . . Bm-1  Lm-1 B2m-1  Lm-1 . . . 55 Ánh x¹ trùc tiÕp  Nh vËy: L0 : B0, Bm, B2m, ..., Bnm L1 : B1, Bm+1, B2m+1, ..., Bnm+1 . . . . . . . Lm-1: Bm-1, B2m-1, B3m-1, ..., B(n+1)m-1 56 Ánh x¹ trùc tiÕp  Khi ®ã, ®Þa chØ do CPU ph¸t ra gåm 3 trêng: „ Word: x¸c ®Þnh sè hiÖu ng¨n nhí trong Block  Block (Line) cã 2w ng¨n nhí „ Line: x¸c ®Þnh sè hiÖu Line trong cache  Cache cã 2r Line, cache chøa 2r + w ng¨n nhí „ Tag: x¸c ®Þnh Block nµo ®ang ë trong Line  BNC chøa 2(s - r) + r + w = 2s + w ng¨n nhí Tag Line Word s - r bit w bit r bit 57 VÝ dô 1  Cho m¸y tÝnh cã dung lîng: „ BNC = 128 MB, cache = 256 KB, line = 32 byte, „ §é dµi ng¨n nhí = 1 byte. T×m d¹ng ®Þa chØ do BXL ph¸t ra?  Gi¶i: Ta cã: „ BNC = 128 MB = 27 * 220 byte = 227 byte „ Cache = 256 KB = 28 * 210 byte = 218 byte „ Line = 32 byte = 25 byte  w = 5 „ Sè lîng Line trong cache: 218/25 = 213  r = 13 „ Sè bit cña phÇn Tag: 27 - 13 - 5 = 9, s - r = 9 5 13 9 58 VÝ dô 2  Cho m¸y tÝnh cã dung lîng: „ BNC = 256 MB, cache = 64 KB, line = 16 byte, „ §é dµi ng¨n nhí = 4 byte. T×m d¹ng ®Þa chØ do BXL ph¸t ra?  Gi¶i: Ta cã: „ BNC = 256 MB = 228 byte = 228/22 = 226 ng/nhí „ Cache = 64 KB = 216 byte = 216/22 = 214 ng/nhí „ Line = 16 byte =24/22 = 22 ng/nhí  w = 2 „ Sè lîng Line trong cache: 214/22 = 212  r = 12 „ Sè bit cña phÇn Tag: 26 - 12 - 2 = 12, s - r = 12 2 12 12 59 S¬ ®å thùc hiÖn 60 NhËn xÐt  Ưu ®iÓm: „ DÔ thùc hiÖn, v× mét Block ®îc ¸nh x¹ cè ®Þnh vµo mét Line  kh«ng cÇn thuËt to¸n chän Line. „ ThiÕt kÕ m¹ch ®¬n gi¶n.  Nhîc ®iÓm: „ TØ lÖ cache hit thÊp. 61 Ánh x¹ liªn kÕt hoµn toµn  Mçi Block trong BNC ®îc ¸nh x¹ vµo mét Line bÊt kú trong Cache  Khi ®ã, ®Þa chØ do BXL ph¸t ra cã d¹ng: „ Word: x¸c ®Þnh ng¨n nhí trong Block  Block cã 2w ng¨n nhí „ Tag: x¸c ®Þnh Block ®ang ë trong Line  Sè lîng Block: 2s  Dung lîng BNC: 2s + w ng¨n nhí Tag Word s bit w bit 62 S¬ ®å thùc hiÖn 63 NhËn xÐt  Ưu ®iÓm: „ TØ lÖ cache hit cao h¬n ¸nh x¹ trùc tiÕp v× mét Block ®îc phÐp vµo mét Line bÊt kú.  Nhîc ®iÓm: „ ThiÕt kÕ m¹ch t¬ng ®èi phøc t¹p, thÓ hiÖn ë m¹ch so s¸nh. 64 Ánh x¹ liªn kÕt tËp hîp  Cache ®îc chia thµnh nhiÒu Set, mçi Set gåm nhiÒu Line liªn tiÕp  Mét Block cña BNC chØ ®îc ¸nh x¹ vµo mét Set duy nhÊt trong cache, nhng ®îc ¸nh x¹ vµo Line bÊt kú trong set ®ã: i = j mod v „ i: sè hiÖu Set trong cache „ j: sè hiÖu Block trong BNC „ v: sè lîng Set trong cache 65 Ánh x¹ liªn kÕt tËp hîp  Khi ®ã, ®Þa chØ do BXL ph¸t ra gåm: „ Word: x¸c ®Þnh sè hiÖu ng¨n nhí trong Block  Block (Line) cã 2w ng¨n nhí „ Set: x¸c ®Þnh sè hiÖu Set trong cache  Cache cã 2d Set „ Tag: x¸c ®Þnh Block nµo ®ang ë trong Line  BNC chøa 2(s - d) + d + w = 2s + w ng¨n nhí Tag Set Word s - d bit w bit d bit 66 VÝ dô 1  Cho m¸y tÝnh cã dung lîng: „ BNC = 512 MB, cache = 128 KB, line = 32 byte, „ Set = 8 Line, ®é dµi ng¨n nhí = 1 byte. T×m d¹ng ®Þa chØ do BXL ph¸t ra?  Gi¶i: Ta cã: „ BNC = 512 MB = 229 byte; Cache = 128 KB = 217 byte „ Line = 25 byte  w = 5 „ Dung lîng Set: 23 * 25 = 28 byte  sè lîng Set trong Cache: 217/28 = 29  d = 9 „ Sè bit cña phÇn Tag: 29 - 9 - 5 = 15, s - d = 15 5 9 15 67 VÝ dô 2  Cho m¸y tÝnh cã dung lîng: „ BNC = 256 MB, cache = 128 KB, line = 64 byte, „ Set = 4 Line, ®é dµi ng¨n nhí = 4 byte. T×m d¹ng ®Þa chØ do BXL ph¸t ra?  Gi¶i: Ta cã: „ BNC = 228 byte = 228/22 = 226 ng/nhí „ Cache = 217 byte = 217/22 = 215 ng/nhí „ Line = 26/22 = 24 ng/nhí  w = 4 „ D/l Set: 22 * 24= 26  s/l Set: 215/26 = 29  d = 9 „ Sè bit cña phÇn Tag: 26 - 9 - 4 = 13, s - d = 13 4 9 13 68 S¬ ®å thùc hiÖn 69 NhËn xÐt  Ưu ®iÓm: „ TØ lÖ cache hit cao v× mét Block ®îc phÐp vµo mét Line bÊt kú trong Set, vµ dÔ so s¸nh. „ §©y lµ kü thuËt ¸nh x¹ tèt nhÊt trong 3 kü thuËt.  Nhîc ®iÓm: „ ThiÕt kÕ m¹ch phøc t¹p. 70 C¸c thuËt to¸n thay thÕ  Kü thuËt ¸nh x¹ trùc tiÕp: Kh«ng thay ®îc  Hai kü thuËt ¸nh x¹ liªn kÕt: cã 4 thuËt to¸n „ Random: thay ngÉu nhiªn mét Block cò nµo ®ã  DÔ thùc hiÖn, nhanh nhÊt, tØ lÖ cache hit thÊp. „ FIFO (First In - First Out): thay Block ë ®Çu tiªn trong sè c¸c Block ®ang cã trong cache  tØ lÖ cache hit kh«ng cao „ LFU (Least Frequently Used): thay Block ®îc dïng víi tÇn suÊt Ýt nhÊt  tØ lÖ cache hit t¬ng ®èi cao „ LRU (Least Recently Used): thay Block ®îc dïng gÇn ®©y Ýt nhÊt  tØ lÖ cache hit cao 71 Ho¹t ®éng cña cache  §äc: „ NÕu cache hit: ®äc ng¨n nhí tõ cache „ NÕu cache miss: thay Block  cache hit  Ghi: „ NÕu cache hit: cã 2 ph¬ng ph¸p:  Write through: ghi d÷ liÖu vµo c¶ cache vµ c¶ BNC  kh«ng cÇn thiÕt, tèc ®é chËm, m¹ch ®¬n gi¶n.  Write back: chØ ghi vµo cache, khi nµo Block (trong cache) ®îc ghi bÞ thay ®i  ghi vµo BNC  tèc ®é nhanh, m¹ch phøc t¹p. „ NÕu cache miss: thay Block  cache hit 72 Ho¹t ®éng cña cache BXL Cache BNC a) Write Through BXL Cache BNC b) Write Back 73 VÝ dô cache trªn c¸c bé xö lý Intel