Giáo trình Hệ thống vi xử lý tiên tiến - Nguyễn Trung Đồng

s bít cho mỗi khối cache. Với s > r, độ dài thẻ tăng đáng kể. a)Tìm kiếm liên kết trên tất cả các khối đích s s w s Memory Address Tag Word Khối Bộ nhớ chính W0 W1 W2 W3 W4j W(4j+1) W(4j+2) W(4j+3) Tag Cache Data Data Data Data Data Data Data Data B0 Bj Data Data Data Data Bm So sánh Cache hit Cache miss Khung khối s+w s w Hệ Vi xử lý tiên tiến 52 Cách gọi cache liên kết đầy đủ xuất phát từ việc tìm kiếm đường liên kết m bất kỳ trên thẻ được so sánh với tất cả các thẻ khối trong cache. (Xem hình II.14a). Cách tổ chức này tạo nên sự mềm dẻo trong chiến lược thay thế các khối nhằm tạo tỷ lệ cache hit cao hơn. Hình II.14b cho thấy một ví dụ ánh xạ 4 đường theo phương thức tìm kiếm liên kết đầy đủ. Thẻ cache có 4 bit tạo khả năng một trong 16 khối có thể nạp vào một khung khối.  Cache liên kết theo tệp và cache vùng (Set- Associative and Sector Cache) Tổ chức cache theo tệp rất thông dụng và được sử dụng trong máy tính thương mại. Cache ánh xạ theo vùng thường được sử dụng cùng cache liên kết theo tệp. Tag 4 bit Cache Bộ nhớ chính B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15 B0 B1 B2 B3 Hình II.14 b) Mỗi khối có thể được “ánh xạ” đến bất kỳ khung khối nào Nguyễn Trung Đồng Tel. 0983 410 866 53 +) Cache liên kết theo tệp (Set-associative cache) là cách tổ chức thoả hiệp giữa ánh xạ trực tiếp và liên kết đầy đủ. Tổ chức theo phương thức này làm giảm giá thành đáng kể. Trong cache liên kết thứ k có m khung khối cache được chia thành v = m/k tệp, với k khung khối trong mỗi tệp. Mỗi tệp được nhận dạng nhờ số hiệu tệp gồm d bít, 2d = v. Thẻ khối cache bây giờ chỉ cần s – d bít. Trong thực tế, độ lớn của tệp k hay còn gọi là tính liên hợp thường được chọn bằng 2, 4, 8, 16 hoặc 64 phụ thuộc vào độ lớn của khối w, độ lớn dung lượng cache m và giá thành sản phẩm hoàn thiện. Ánh xạ liên kết đầy đủ có thể xem như trường hợp với v = 1, hoặc là trường hợp tính liên hợp với dung lượng cache là m. Khi tìm kiểm trong trường hợp liên kết đường k, thẻ cache được so sánh với với k thẻ trong tệp (Hình II. 15). Có thể hiểu phương thức tổ chức này trên Hình II.15b là ví dụ ánh xạ với n = 16 khối nhớ từ bộ nhớ chính vào cache liên kết 2 đường (k = 2) và số tệp là v = 4 qua m = 8 khung khối. cache s+w w w d s-d Thẻ cache Địa chỉ từ nhớ Tag Set Word B0 B1 B(k-1) B(ik) B(ik+1) B(ik+k-1) B0 B1 B2 B3 B(ik+1) So sánh Bộ nhớ chính set 0 set i Cache hit Cache miss Hình II.15. a) Tìm liên kết đường thứ k trong các tệp có k khối cache Hệ Vi xử lý tiên tiến 54 Với hệ thống i860 của Intel (Hình II.12b) D-cache và I- cache là liên kết 2 đường (k = 2) với 128 tệp trong D-cache, 64 tệp trong I-cache với 256 và 128 khung khối. +) Cache ánh xạ theo vùng (Sector mapping cache) được tổng hợp từ những phương thức trên. Ý tưởng chủ yếu là phân vùng cache và bộ nhớ chính thành từng phân vùng cố định (sectors), sau đó sử dụng phương thức liên kết đầy đủ. Nghĩa là mỗi phân vùng (sector) có thể được nạp vào bất kỳ một khung phân vùng (sector frame) nào có thể. Yêu cầu truy xuất bộ nhớ được đưa đến các khối, chứ không được chuyển đến các vùng. Có thể lọc ra yêu cầu này bằng cách so sánh thẻ vùng trong địa chỉ ô nhớ với tất cả các thẻ vùng sử dụng cách tìm kiếm liên kết đầy đủ. Khi khung vùng phù hợp, (cache hit) vùng khối được sử dụng để định vị khối được yêu cầu trong khung vùng. Bộ nhớ chính B0 B1 B2 B3 B4 B5 B6 B7 B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15 set 0 set 1 set 2 set 3 Thẻ 2 bít cache Hình II.15.b) Ánh xạ khối cache vào liên kết 2 đường và 4 tệp Bộ nhớ chính Địa chỉ ô nhớ Sector Block Word (3 bít) (2 bít) (4 bít) B0 B1 B2 B3 Vùng 0 Nguyễn Trung Đồng Tel. 0983 410 866 55 Hệ Vi xử lý tiên tiến 56 Khi xẩy ra cache miss, chỉ khối bị lỗi được lấy từ bộ nhớ chính và đặt vào khung khối thích hợp trong khung vùng. Có nghĩa là khối thứ i trong vùng phải được đặt đúng vào khung khối thứ i trong khung vùng đích. Bít xác nhận hợp lệ (valid bít) được gắn với mỗi khối khung để chỉ ra khối là hợp lệ hay không hợp lệ. Khi nội dung một khung khối bị thay thế, tất cả các khung khối còn lại sẽ bị đánh dấu là không hợp lệ. Chỉ khung khối mới bị thay thế nhất trong vùng được đánh dấu là hợp lệ cho phép tham chiếu. Nếu so sánh với hai phép ánh xạ đã trình bày trên đây, thì phép ánh xạ vùng có ưu điểm ở sự mềm dẻo của thuật thay thế nội dung các khối và hiệu quả hơn trong việc tìm kiếm liên kết đầy đủ thông qua một số giới hạn thẻ vùng. Hình II.16 là một ví dụ về tổ chức cache ánh xạ vùng với mỗi vùng có 4 khối. Mỗi vùng có thể ánh xạ vào bất kỳ khung vùng nào với phương thức liên kết đầy đủ ở mức vùng. Cách tổ chức này được hiện thực hoá trên hệ thống IBM System/360 Model 85. Tổ chức ở Model 85 có 16 vùng, mỗi vùng có 16 khối, với dung lượng khối là 64 bytes. Như vậy mỗi vùng có 1024 bytes và tổng dung lượng cache là 16KB. Hiệu suất sử dụng cache có thể nhìn nhận trên hai phạm vi liên quan là số chu kỳ (Cycle Count) và tỷ lệ trúng cache (Hit Ratio). Số chu kỳ được tính dựa vào số các chu kỳ máy cần cho một truy xuất cache, bổ sung thông tin và điều khiển liên kết. Tỷ lệ trúng cache xác định tính hiệu quả của sử dụng cache so với tổng thời gian truy xuất bộ nhớ. Cần có sự điều chỉnh cân bằng giữa hai phạm vi này. Các hệ số ảnh hưởng đến tốc độ truy xuất cache và tỷ lệ trúng cache bao gồm việc mô phỏng theo từng bước thực hiện chương Nguyễn Trung Đồng Tel. 0983 410 866 57 trình (program trace-driven simulation) và mô hình hoá phân tích (analytical modeling) quá trình tổ chức và quản lý bộ nhớ cache. Sự thoả hiệp thông qua kết quả của hai quá trình này sẽ đưa tới quyết định tổ chức cấu trúc và phương thức quản lý cache. II.5. Tổ chức bộ nhớ chia sẻ Tổ chức bộ nhớ theo phương thức đan xen (interleaving) tạo ra được giải thông cao hơn cho các hệ thống truy xuất của đường ống đối với các vị trí liên tiếp trong bộ nhớ. Phương pháp định vị và phân vùng bộ nhớ chính cho các chương trình được quan tâm nhất nhằm sử dụng bộ nhớ một cách tối ưu. II.5.1. Tổ chức bộ nhớ đan xen (Interleaved Memory Organization) a) Tổ chức đan xen Có nhiều cách tổ chức bộ nhớ vật lý. Kỹ thuật đan xen được sử dụng để làm giảm nhỏ lỗ hổng (bong bóng) trong tăng tốc truy xuất CPU-cache và bộ nhớ chính. Mục tiêu của thiết kế bộ nhớ là mở rộng hiệu suất băng thông nhớ sao cho nhiều từ nhớ có thể truy xuất được trong một đơn vị thời gian. Mục tiêu cuối cùng chính là phù hợp băng thông nhớ với băng thông của BUS và băng thông của bộ xử lý. Giả sử bộ nhớ chính có m = 2a mô đun, mỗi mô đun nhớ chứa w = 2b từ trong một vị trí nhớ. Tổng dung lượng nhớ sẽ là m.w = 2a+b từ nhớ. Các từ nhớ này được gán các địa chỉ tuyến tính. Các phương thức gán địa chỉ tuyến tính khác nhau sẽ dẫn đến các tổ chức bộ nhớ khác nhau. Ngoài các truy xuất ngẫu nhiên, bộ nhớ chính còn bị truy xuất theo khối tại các vùng có địa chỉ liên tiếp nhau. Hệ Vi xử lý tiên tiến 58 Việc truy xuất theo khối là cần thiết đối với chuỗi lệnh hay cấu trúc dữ liệu tuyến tính. Mỗi truy xuất theo khối tương ứng với độ rộng của khối hoặc một số khối trong cache. Tất nhiên yêu cầu này dẫn đến việc thiết kế bộ nhớ sao cho thích hợp với việc truy xuất theo khối. Hình II.17 a,b chỉ ra hai dạng thức địa chỉ cho đan xen bộ nhớ. Đan xen bậc thấp (Low-order interleaving) trải rộng của các vị trí nhớ liên tục trên m mô đun. Hàm ý bậc thấp tức là a bít thấp của địa chỉ ô nhớ được dùng để xác định mô đun nhớ, trong khi b bit cao là địa chỉ của từ nhớ trong từng mô đun. Lưu ý rằng địa chỉ từ nhớ được đưa đến tất cả các mô đun nhớ đồng thời, còn địa chỉ mô đun nhớ qua giải mã địa chỉ để xác định mô đun nhớ. Hình II.17a. m đường đan xen bậc thấp (Low-order) MDB: Đệm dữ liệu bộ nhớ MAB: Đệm địa chỉ mô đun Mm-1 M1 M0 Địa chỉ ô nhớ BUS dữ liệu Word Mô đun MA 0 m m( MD MAB 1 m+1 mw-m+1) MDB MAB m-1 2m-1 mw-1 MDB W A B MAB 0 m m(w-1) MDB a b Giải mã địa chỉ Đệm địa chỉ từ nhớ Giải mã địa chỉ Mm-1 MA 0 m MAB w w+1 MAB (m-1)w mw MAB 0 1 a Nguyễn Trung Đồng Tel. 0983 410 866 59 Đan xen bậc cao (High-order interleaving) sử dụng các bit bậc cao (a bít) làm địa chỉ của mô đun nhớ còn các bít bậc thấp (b bít) là địa chỉ của từ nhớ. Các vị trí nhớ liên tiếp được đặt trong từng mô đun. Trong mỗi chu kỳ bộ nhớ, chỉ một từ nhớ được truy xuất từ mỗi mô đun nhớ. Đây cũng là nguyên nhân bộ nhớ đan xen bậc cao không thể sử dụng cho truy xuất theo khối các vị trí nhớ liên tiếp nhau. Chỉ bộ nhớ đan xen bậc thấp cho phép truy xuất các vị trí nhớ liên tiếp nhau theo khối trong cơ chế đường ống. b) Truy xuất bộ nhớ đường ống hoá Truy xuất m mô đun nhớ có thể thực hiện gối nhau theo thể thức đường ống hoá. Vì mục đích này, chu kỳ bộ nhớ (chu kỳ chính) được phân chia thành m chu kỳ thứ cấp. Hình II.17. Hai cách tổ chức bộ nhớ đan xen với m = 2a và w = 2b từ trong mỗi mô đun nhớ Hình II.17b. m đường đan xen bậc cao (High-order) Hệ Vi xử lý tiên tiến 60 Một ví dụ về tổ chức bộ nhớ đan xen với m = 8, w = 8, ứng với a = b = 3 được thể hiện trên Hình II.18a. Gọi θ là chu kỳ chính và τ là chu kỳ thứ cấp, ta có: m    trong đó m là bậc đan xen (degree of interleaving). Định thời của truy xuất đường ống hoá 8 từ nhớ liên tiếp trong bộ nhớ được thể hiện trên Hình II.18b. Thể thức truy xuất đồng thời (concurrent access) các từ nhớ liên tiếp nhau được gọi là biểu đồ C-truy xuất. Chu kỳ chính θ là tổng thời gian cần thiết để hoàn thành truy xuất một từ trong mô đun. Chu kỳ thứ cấp τ là thời gian thực tế cần để tạo nên từ, bao gồm việc truy xuất gối kề các mô đun nhớ kế tiếp nhau và được phân tách bởi chu kỳ thứ cấp τ. a)Đan xen bậc thấp 8 đường 1 9 17 25 33 41 49 57 2 10 18 26 34 42 50 58 3 11 19 27 35 43 51 59 4 12 20 28 36 44 52 60 5 13 21 29 37 45 53 61 6 14 22 30 38 46 54 62 7 15 23 31 39 47 55 63 0 8 16 24 32 40 48 56 Thanh ghi địa chỉ ô nhớ Địa chỉ từ nhớ Địa chỉ mô đun Thanh ghi dữ liệu ô nhớ M0 M1 M2 M3 M4 M5 M6 M7 Nguyễn Trung Đồng Tel. 0983 410 866 61 Thấy rằng truy xuất đường ống hoá 8 từ liên tiếp được thực hiện như trên băng tải giữa truy xuất các khối đường ống hoá với các khối khác. Trong khi tổng thời gian truy xuất khối là 2θ, thời gian truy xuất hiệu dụng mỗi từ được rút xuống chỉ còn là τ, như đối với bộ nhớ truy xuất liên tiếp trong phương thức đường ống hoá. II.5.2. Băng thông và dung sai lỗi Năm 1967 Hellerman đã đưa ra biểu thức khảo sát sự tăng hiệu quả theo băng thông qua việc tổ chức bộ nhớ đan xen nhiều đường. Giả sử một mô đun nhớ đơn cho phép truy xuất một từ trong một chu kỳ bộ nhớ thì băng thông B được tính bằng 1.  Băng thông B của bộ nhớ đan xen m đường bị giới hạn trên bởi m và giới hạn dưới bằng 1. Hellerman đưa ra biểu thức khảo sát B như sau: mmB  56.0 W0 W1 W2 W3 W4 W5 W6 W7 Thời gian τ θ 2θ b)Truy xuất đường ống hoá 8 từ liên tiếp trong bộ nhớ truy xuất đồng thời (C-access) Hệ Vi xử lý tiên tiến 62 trong đó m là số các mô đun nhớ đan xen. Thấy ngay rằng nếu sử dụng 16 mô đun nhớ theo tổ chức đan xen, băng thông sẽ gần gấp 4 lần so với bộ nhớ chỉ một mô đun. Trong máy tính xử lý vector, thời gian truy xuất của một vector dài n phần tử với khoảng cách giữa chúng bằng 1 được Cragon khảo sát năm 1992 như sau: Giả sử có n phần tử được lưu giữ liên tiếp trong bộ nhớ đan xem m đường, thời gian trung bình t1 cần để truy xuất 1 phần tử trong vector là: ) 1 1(1 n m m t    Khi n→∞, (vector rất dài), t1→θ/m = τ, còn khi n→1 thì t1 = θ, và có thể kết luận, theo quan điểm này, vector càng dài càng tốt hơn.  Dung sai lỗi : Thấy rằng đan xen bậc cao và đan xen bậc thấp có thể tổ hợp để tạo ra nhiều cách tổ chức bộ nhớ đan xen. Các địa chỉ tuần tự sẽ được gán cho bộ nhơ đan xen bậc cao trong mỗi mô đun nhớ. Nó cho phép dễ dàng loại trừ lỗi mô đun nhớ trong băng nhớ m mô đun. Khi xẩy ra lỗi tại một mô đun, lúc đó các mô đun khác có thể dùng để mở một cửa sổ trong không gian nhớ. Lỗi loại trừ này không xuất hiện trong tổ chức đan xen bậc thấp, vì lỗi mô đun có thể gây rối loạn toàn băng nhớ. Chính vì vậy, bộ nhớ đan xen bậc thấp không thể coi là loại bộ nhớ có dung sai lỗi. II.5.3. Sơ đồ định vị bộ nhớ Ý tưởng bộ nhớ ảo (Virtual Memory) cho phép nhiều quá trình được thực hiện sử dụng chiến lược chia sẻ theo Nguyễn Trung Đồng Tel. 0983 410 866 63 thời gian sử dụng bộ nhớ chính, nguồn tài nguyên quý giá nhưng lại rất hạn chế về dung lượng. Sự phân chia của hệ điều hành về định vị và hoán vị bộ nhớ chính trong quá trình thực thi chương trình được gọi là điều hành bộ nhớ (Memory Manager). Điều hành bộ nhớ thực hiện việc giám sát phần chung của bộ nhớ và xác định quá trình nào sẽ được định vị vào, quá trình nào phải trả về ổ đĩa khi dung lượng bộ nhớ là giới hạn.  Chiến lược định vị (Allocation Policies): Hoán đổi bộ nhớ là quá trình di chuyển các khối thông tin giữa các mức của phân cấp bộ nhớ. Để dễ hiểu, ở đây chỉ trình bày sự hoán vị thông tin giữa bộ nhớ chính và ổ đĩa. Trước tiên chiến lược hoán đổi có thể thực hiện không chỉ với vùng nhớ được ưu tiên hay không được ưu tiên. Trong trường hợp định vị không ưu tiên, khối thông tin đến chỉ có thể được nạp vào vùng rỗi của bộ nhớ chính. Còn trường hợp định vị ưu tiên thì khối thông tin mới sẽ thay thế vị trí tại vùng đang bị chiểm giữ bởi một quá trình. Trong cả hai trường hợp, điều hành bộ nhớ luôn cố gắng định vị thông tin vào vùng được ưu tiên. Khi không gian bộ nhớ chính đã định vị đầy đủ, sơ đồ không ưu tiên hoán vị một số quá trình đang được định vị (hoặc trang) để giành chỗ cho các khối sẽ được chuyển đến. Mặt khác, sơ đồ ưu tiên có sự lựa chọn ưu tiên cho quá trình đang thực thi. Sơ đồ không ưu tiên tuy dễ dàng thực hiện, song sự sử dụng bộ nhớ không được hoàn hảo. Sơ đồ ưu tiên có tính mềm dẻo cao, song nó yêu cầu cơ chế thiết lập để xác định trang nào hay quá trình nào sẽ phải hoán vị khỏi, và ngăn ngừa sự thua thiệt do quá thừa vùng hoán vị giữa các mức bộ nhớ. Hệ Vi xử lý tiên tiến 64 Chiến lược định vị có thể là cục bộ hoặc toàn cục. Chiến lược định vị cục bộ chỉ bao gồm các lớp công việc của các quá trình không tường minh. Chiến lược định vị toàn cục cân nhắc quá khứ của lớp các công việc thuộc các quá trình thường trú để đi đến quyết định hoán vị.  Các hệ thống hoán vị (Swapping Systems) : Thiết bị hoán vị (swap device) là một phần được định trước của đĩa đặt trong vùng tạm lưu để sẽ được hoán vị khỏi bộ nhớ chính. Một phần của vùng nhớ đĩa thiết lập cho thiết bị hoán vị được gọi là không gian hoán vị (Hình II.19). Điều hành bộ nhớ định vị không gian đĩa cho tệp chương trình một khối, nhưng nó lại định không gian cho thiết bị hoán vị một nhóm các khối liền kề. Để dễ hình dung, giả thiết các khối là những trang có dung lượng cố định. Không gian địa chỉ ảo có thể chiếm nhiều trang. Độ lớn của không gian địa chỉ quá trình bị giới hạn bởi dung lượng bộ nhớ chính trong hệ thống hoán vị. a)Di chuyển quá trình (trang) vào vùng hoán vị của đĩa 1023K 400K (63K) (16K) (0) (1K) (17K) 2K 800K 801K (0) Không gian hoán vị (4M) Bộ nhớ chính Bộ nhớ ổ đĩa Nguyễn Trung Đồng Tel. 0983 410 866 65 Hệ thống hoán vị được sử dụng trong máy tính PDP-11 và các hệ thống UNIX gần đây. Nó được dùng để chuyển nội dung của quá trình giữa bộ nhớ chính và thiết bị hoán vị, chứ không chuyển các thành phần (trang) riêng biệt của quá trình. PDP-11 cho phép quá trình có độ dài lớn nhất là 64KB. Cần nhắc lại rằng, mọi quá trình đều phải được nạp vào bộ nhớ chính thì mới có thể thực thi được. Hình II.19 là ví dụ đơn giản mô tả nguyên lý trao đổi thông tin phục vụ thực hiện quá trình có 5 trang hiện hành được xác nhận qua địa chỉ bộ nhớ ảo 0, 1K, 16K, 17K và 63K với giả thiết dung lượng trang là 1K từ (tương đương b)Hoán vị quá trình (trang) vào bộ nhớ Hình II.19. Nguyên lý hoán vị trong bộ nhớ ảo phân cấp (dung lượng trang là 1k từ - 4KB) 1 023K 1023K Bộ nhớ chính Bộ nhớ ổ đĩa 1022K 465K (0) (16K) (63K) (17K) (1K) 4K 700K (0) Không gian hoán vị (4M) b)Hoán vị quá trình (trang) trở lại bộ nhớ chính Hình II.19. Nguyên lý hoán vị bộ nhớ vào trang bộ nhớ ảo phân cấp được nhận dạng bởi giả thiết số lượng trang độ lớn là 1K Hệ Vi xử lý tiên tiến 66 4Kbyte) Hình II.19a chỉ ra sự định vị trong bộ nhớ vật lý trước khi hoán vị. Giả thiết bộ nhớ chính có 1024 khung trang, ổ đĩa có thể điều tiết để có 4M trang. 5 trang thường trú rời rạc trên bộ nhớ chính được được hoán vị khỏi bộ nhớ và sắp xếp lại thành các trang liên tiếp trên thiết bị hoán vị. Sau này, quá trình có thể cần được sắp xếp lại vào bộ nhớ chính như trong Hình II.19b. Các khung trang khác có thể được định vị để điều tiết lại sự sắp xếp các trang. Mục đích của việc ánh xạ các khối liên tiếp vào thiết bị hoán vị là để tăng tốc hoạt động trao đổi thông tin đa khối so với việc di chuyển từng khối.  Các hệ thống lập trang theo yêu cầu (Demand Paging Systems): Hệ thống bộ nhớ theo trang sử dụng lập trang theo yêu cầu trong chiến lược định vị. Chiến lược này chỉ cho phép các trang (không cho phép quá trình) được hoán vị giữa bộ nhớ chính và thiết bị hoán vị. Trên Hình II.19, các trang của quá trình được hoán vị độc lập và đó là hệ thống lập trang theo yêu cầu. Trong hệ thống lập trang theo yêu cầu, toàn bộ quá trình không được chuyển vào bộ nhớ chính để được thực thi, chỉ các trang được nạp vào bộ nhớ chính theo yêu cầu. Ý tưởng lập trang theo yêu cầu tương thích hoàn toàn với nguyên lý tập hiện hành (working-set). Chỉ các tập hiện hành của quá trình đang được thực thi là hiện hữu trong bộ nhớ chính. Back (1996) định nghĩa tập hiện hành của quá trình là tập các trang tham chiếu bởi quá trình trong n tham chiếu cuối cùng, và n được gọi là độ rộng cửa sổ (window size) của tập hiện hành. Nguyễn Trung Đồng Tel. 0983 410 866 67  Các hệ thống nhớ hỗn hợp (Hybrid Memory Systems): Các hệ thống máy tính VAX/VMS và UNIX System V được lắp đặt hệ thống nhớ hỗn hợp ứng dụng những ưu điểm của hai phương thức hoán vị và lập trang theo yêu cầu. Khi một số quá trình đồng thời ở trạng thái sẵn-sàng-chạy đã-được-hoán-vị (ready-to-run-but-swapped), thiết bị hoán vị có thể chọn để hoán vị ra một số quá trình để làm rỗng không gian nhớ cần thiết. Một số hệ thống nhớ ảo có thể sử dụng phương thức lập trang dự đoán (anticipation pagging), nghĩa là nhặt trước các trang theo dự đoán. Sơ đồ làm việc theo phương thức này rất khó thực thi. Cho đến khi các mẫu tham chiếu bộ nhớ có thể tiên đoán được tại thời điểm khi bộ dịch tạo địa chỉ, sơ đồ này không phát huy được thế mạnh. Với các mẫu tham chiếu bộ nhớ ngắn hạn, sẽ dễ dàng hơn để dự đoán thông qua các đặc trưng cục bộ. Hệ Vi xử lý tiên tiến 68 Chương III Các mô hình máy tính xử lý song song Chương này khảo sát kiến trúc hệ thống đa xử lý (MultiProcessors) và kiến trúc hệ thống đa máy tính (MultiComputers). Các vấn đề được quan tâm ở đây gồm phương pháp đồng bộ, các mạch chuyển mạch mạng liên kết, các bộ nhớ đa cổng, mạng nhiều tầng , v. v III.1. Liên kết hệ thống đa xử lý Xử lý song song đòi hỏi việc liên kết hệ thống đảm bảo truyền thông nhanh chóng giữa các bộ Vi xử lý với bộ nhớ chia sẻ, với các thiết bị Vào/Ra và với các thiết bị ngoại vi. BUS phân cấp, các phần tử chuyển mạch và mạng nhiều tầng luôn được sử dụng co các mục tiêu này. Hình III.1 là hệ thống đa xử lý tổng quát. Kiến trúc này tổng hợp các ưu điểm của hệ thống UMA, NUMA và COMA. Mỗi bộ xử lý Pi được gắn thêm mô đun nhớ cục bộ và cache riêng. Các bộ xử lý được liên kết với các mô đun nhớ chia sẻ nhờ mạng kết nối xử lý-bộ nhớ IPMN (Interprocessor-Memory Network). Các bộ xử lý chia sẻ nhau các thiết bị Vào/Ra và các thiết bị ngoại vi khác thông qua mạng kết nối thiết bị Vào/Ra PION (Processor-I/O Network). Hai mạng liên kết IPNM và PION là cần thiết cho việc chia sẻ tài nguyên trong hệ thống đa xử lý. Truyền thông tin trực tiếp giữa các bộ xử lý với nhau được đảm bảo nhờ mạng liên kết truyền thông IPCN (Interprocessor-Communication Network) thay vì phải thông qua bộ nhớ chia sẻ. Nguyễn Trung Đồng Tel. 0983 410 866 69 Hệ Vi xử lý tiên tiến 70 Đặc trưng của mạng: Mỗi một mạng được nêu trên có thể được hiện thực hoá theo nhiều phương pháp. Thông Ngoại vi bao gồm: - Các ổ đĩa - Băng từ - Máy in - Thiết bị đầu cuối Các từ viết tắt: IPMN mạng kết nối các mô đun nhớ với các bộ Vi xử lý PION Mạng kết nối các bộ Vi xử lý với các thiết bị ngoại vi IPCN Mạng kết nối các bộ Vi xử lý Pi Bộ Vi xử lý thứ i Ci Bộ nhớ cache thứ i (của Pi) SM Mô đun nhớ chia sẻ LM Các mô đun nhớ cục bộ Hình III.1. Cấu trúc kết nối hệ thống đa xử lý song song tổng quát với các mô đun nhớ cục bộ, cache riêng, các mô đun nhớ chia sẻ, thiết bị ngoại vi chia sẻ Bộ nhớ chia sẻ Thiết bị ngoại vi chia sẻ S SM2 S SMm IPMN SM1 IPMN Cn Pn LM Cn Pn LM IPCN PION Nguyễn Trung Đồng Tel. 0983 410 866 71 thường, chúng được chọn theo tôpô mạng, thep phương thức định thời, phương pháp chuyển mạch và chiến lược điều khiển. Định thời, chuyển mạch và điều khiển là ba đặc trưng chức năng chính của một mạng liên kết. Điều khiển định thời có thể là đồng bộ hoặc dị bộ. Mạng đồng bộ được điều khiển bằng xung nhịp toàn cục để đồng bộ hoạt động của toàn mạng. Mạng không đồng bộ sử dụng cơ chế bắt tay (Handshaking) hoặc cơ chế liên động (Interlocking Mechanisms) để điều phối đối với các thành phần có tốc độ thu phát thông tin nhanh chậm khác nhau trên cùng một mạng. Mạng có thể chuyển dữ liệu sử dụng mạch chuyển (Circuit Swiching) hoặc gói chuyển (Packet switching). Ở phương thức dùng mạch chuyển, khi một thiết bị được cấp đường truyền trên mạng, thiết bị chiếm đường truyền trong một khoảng thời gian nhất định cho việc truyền dữ liệu. Còn trong phương thức gói chuyển, thông tin được phân thành từng gói nhỏ và chia nhau đường truyền trên mạng. Điều khiển mạng được phân thành 2 loại: tập trung (Centralized) hoặc phân tán (Distributed). Ở phương thức điều khiển tập trung, bộ điều khiển toàn cục tiếp nhận các yêu cầu từ tất cả các thành phần gắn kết trên mạng và phân phối việc truy cập mạng cho một hoặc một số yêu cầu. Còn ở phương thức điều khiển phân tán các yêu cầu được tiếp nhận độc lập nhờ các thiết bị cục bộ. III.1.1. Hệ thống BUS phân cấp Hệ thống BUS bao gồm hệ phân cấp các BUS kết nối các hệ thống và các thành phần trong một máy tính. Mỗi một BUS bao gồm một số các đường dây tín hiệu, đường Hệ Vi xử lý tiên tiến 72 dây điều khiển và cấp nguồn nuôi. Các BUS khác nhau thực hiện các chức năng kết nối khác nhau. Hình III.2 thể hiện các BUS ở các mức khác nhau, bao gồm BUS cục bộ trên vỉ, BUS trên bo mạch chủ, BUS Vào/Ra v.v BUS cục bộ (Local BUS) thông thường được thực hiện bằng các đường mạch in trên vỉ chức năng. Trên bo mạch CPU, BUS cục bộ làm chức năng kết nối truyền thông tin giữa các phần tử chính (chip) được gắn trên bo. Vỉ nhớ sử dụng BUS nhớ (Memory BUS) để kết nối bộ nhớ với giao diện logic. Vỉ Vào/Ra hay vỉ giao diện mạng sử dụng BUS dữ liệu. Các BUS này bao gồm các đường dây tín hiệu và đường dây chức năng tiện dụng. Với phương thức chia sẻ chức năng và tín hiệu trên đường dây, có những đường dây truyền dẫn các tín hiệu khác nhau theo chia sẻ thời gian. BUS bo mạch chủ (Backplane BUS) chính là mạch in có khả năng kết nối thông qua các khối kết nối (connector) để sử dụng cho việc cắm các vỉ chức năng. BUS hệ thống, bao gồm các dường dây tín hiệu chia sẻ và các đường dây đa dụng được thực hiện bằng kết nối mạch in. BUS hệ thống làm chức năng kết nối tất cả các vỉ chức năng trong máy tính. Các BUS này có chuẩn chung và đã được phát triển, sử dụng nhiều như BUS VME (theo chuẩn IEEE Standard 1014-1987), MultiBus II (IEEE Standard 1296-1987) và FutureBus+ (IEEE Standard 896.1-1991). Bo Bo mạch CPU Ngoại vi cục bộ (BUS SCSI) Bo mạch nhớ CPU IOC Các ô nhớ LM Nguyễn Trung Đồng Tel. 0983 410 866 73 BUS Vào/Ra (I/O BUS) kết nối các thiết bị Vào/Ra với hệ thống máy tính. Hệ Vi xử lý tiên tiến 74 Có thể kể ra BUS giao diện hệ thống máy tính nhỏ SCSI (Sma