Luận án Tối ưu hóa và đánh giá hiệu năng của tổ chức cache trong hệ thống vi xử lý thế hệ sau

đều sử dụng cách ghi thông suốt [72]. 
 Để nâng cao hiệu năng của quá trình CPU ghi nội dung vào cache bằng cách 
sử dụng giải pháp đưa vào một bộ đệm ghi sử dụng công nghệ SRAM, và đặt nó 
giữa bộ nhớ chính và CPU hoặc giữa L1 cache và L2 cache như hình 2.12 [72]. 
 Cache 
 Bộ nhớ 
 CPU 
 Bộ đệm chính 
 ghi 
 (a): Bộ đệm ghi ở giữa CPU và bộ nhớ chính. 
 L1 cache 
 Bộ nhớ 
 CPU L2 cache chính 
 Bộ đệm 
 ghi 
 (b): Bộ đệm ghi ở giữa L1 cache và L2 cache. 
 Hình 2.12: Kỹ thuật bộ đệm ghi [72]. 
 Trong trường hợp bộ đệm ghi đặt giữa CPU và bộ nhớ chính: CPU ghi nội 
dung đồng thời ra dòng cache và bộ đệm ghi với tốc độ cao hơn so với thời gian 
CPU ghi ra bộ nhớ chính công nghệ DRAM, sau đó đơn vị điều khiển bộ nhớ thực 
hiện ghi tiếp nội dung mới từ bộ đệm ghi ra khối nhớ tương ứng trong bộ nhớ chính 
mà không chiếm thời gian của CPU và cache. 
 Trong trường hợp bộ đệm ghi đặt giữa CPU và L2 cache: CPU đồng thời ghi 
nội dung ra dòng L1 cache và bộ đệm ghi, sau đó điều khiển cache sẽ thực hiện ghi 
tiếp nội dung của bộ đệm ghi ra L2 cache mà không chiếm thời gian của CPU và L1 
cache. 
 46 
 Như vậy, kỹ thuật bộ đệm ghi cho phép giảm được trễ do CPU không truy 
nhập bộ nhớ chính (hay L2 cache) khi sử dụng cách ghi thông suốt, và trong trường 
hợp sử dụng cách ghi trở lại thì chỉ thực hiện sao lưu từ bộ đệm ghi ra khối nhớ của 
bộ nhớ chính mà không cần sử dụng tới CPU và cache. 
 2.4.2. Đọc cache 
 Hầu hết các tham chiếu của CPU đến bộ nhớ chính là các tham chiếu để đọc 
nội dung từ bộ nhớ. Có hai trường hợp để đọc cache: CPU đọc một từ (mã lệnh 
hoặc dữ liệu) từ dòng cache khi trúng cache và CPU đọc một từ (mã lệnh hoặc dữ 
liệu) từ bộ nhớ chính khi trượt cache. Có hai kiến trúc đọc cache đó là: đọc bên 
cạnh và đọc thông suốt [24, 72]. 
 2.4.2.1. Đọc bên cạnh 
 Hình 2.13 là sơ đồ đơn giản của kiến trúc đọc bên cạnh: bộ nhớ chính và cache 
nằm ở hai phía đối diện của giao tiếp của hệ thống. Như vậy, bộ nhớ chính và cache 
có thể đồng thời thực hiện các chu kỳ bus riêng của mình. 
 CPU Giao tiếp Bộ nhớ 
 hệ thống 
 chính 
 Cache Bộ điều Thẻ RAM 
 (SRAM) khiển cache (TRAM) 
 Hình 2.13: Đọc bên cạnh [72]. 
 Khi CPU bắt đầu chu kỳ đọc bộ nhớ, tùy thuộc vào tổ chức cache, có sự so 
sánh để tìm kiếm dữ liệu yêu cầu có hay không trong một dòng cache nào đó: 
 - Nếu trúng cache, thì chu kỳ đọc cache được thực hiện: CPU đọc dữ liệu từ 
dòng cache được lựa chọn, và không cần phải tham chiếu bộ nhớ chính. 
 - Nếu trượt cache, thì chu kỳ đọc bộ nhớ chính được thực hiện: CPU đọc dữ 
liệu từ bộ nhớ chính và đồng thời khối chứa dữ liệu đó được đọc về dòng cache 
tương ứng, bởi vì theo dự đoán nhờ các nguyên tắc tham chiếu, có thể ngay sau đó 
dữ liệu này hoặc những dữ liệu lân cận trong khối có thể nhanh chóng được CPU 
tham chiếu. 
 47 
 Kỹ thuật đọc này có cấu trúc không phức tạp, chi phí thấp, bảo đảm thời gian 
đọc nhỏ khi trượt cache, vì sự truyền tải khối từ bộ nhớ chính đến cache có thể thực 
hiện độc lập bằng các chu kỳ bus của mình và chúng không ảnh hưởng đến điều 
khiển các truy nhập của các thiết bị khác thông qua giao tiếp hệ thống. 
 2.5.2.2. Đọc thông suốt 
 Hình 2.14 là sơ đồ đơn giản của kiến trúc đọc thông suốt. Nó có đặc điểm: bộ 
nhớ chính ở phía bên đối diện của giao tiếp hệ thống, cache nằm giữa CPU và bộ 
nhớ chính. Như vậy, cache có chu kỳ của CPU trước khi chuyển chu kỳ của CPU 
đến giao tiếp hệ thống. Khi CPU bắt đầu chu kỳ đọc bộ nhớ, tùy thuộc vào tổ chức 
cache, có sự so sánh để tìm kiếm từ yêu cầu có hay không trong một dòng cache 
nào đó: 
 CPU 
 Cache Bộ điều Thẻ RAM 
 (SRAM) khiển cache (TRAM) 
 Giao tiếp 
 hệ thống 
 Bộ nhớ 
 chính 
 Hình 2.14: Đọc thông suốt [72]. 
 - Nếu trúng cache, thì chu kỳ đọc cache được thực hiện: CPU đọc từ yêu cầu 
từ dòng cache được lựa chọn và không cần phải tham chiếu bộ nhớ chính. 
 - Nếu trượt cache, thì chu kỳ đọc bộ nhớ chính được thực hiện: CPU đọc từ 
yêu cầu từ bộ nhớ chính thông suốt qua cache, trong đó có từ yêu cầu được đọc về 
dòng cache tương ứng, bởi vì theo dự đoán của các nguyên tắc tham chiếu, có thể 
ngay sau đó từ này hoặc những từ lân cận trong khối có thể nhanh chóng được CPU 
tham chiếu. 
 Kỹ thuật đọc thông suốt cho phép thực hiện thao tác với cache trong khi vẫn 
dành bus hệ thống cho các thiết bị khác để tham chiếu đến bộ nhớ chính, ví dụ, thực 
 48 
hiện DMA giữa bộ nhớ chính và thiết bị nhớ ngoài như HDD, CD/DVD. Kỹ thuật 
này phức tạp cho điều khiển các truy nhập của CPU cho các thành phần còn lại của 
hệ thống máy tính, do đó chi phí cũng lớn. Khi có trượt cache, phải thực hiện chu 
kỳ đọc từ bộ nhớ chính về CPU thông qua bus hệ thống và hệ thống cache, do đó 
làm chậm truy nhập của các thiết bị khác qua bus hệ thống. Để khắc phục hiện 
tượng này cần phải tăng tỷ số trúng cache. 
2.5. Cache chia sẻ thông minh 
 2.5.1. Tổ chức phân cấp cache trong các chip đa xử lý 
 Trong các CMP đa luồng, mỗi lõi xử lý có L1I cache và L1D cache riêng, 
nhưng L2 cache hoặc có thể riêng cho từng lõi [11, 29, 38, 50] hoặc có thể chia sẻ 
cho tất cả các lõi [2, 8, 16, 17, 29, 38, 72] như hình 2.15. 
 a) b) 
 Hình 2.15: CMP đa luồng hai cấp cache; a) với L2 cache riêng và 
 (b) với L2 cache chung cho tất cả các lõi [38,72]. 
 Trong một số CMP đa luồng có thể có L3 cache chia sẻ cho các lõi, khi đó L2 
cache là riêng cho từng lõi như hình 2.16. 
Hình 2.16: Tổ chức cache trong các bộ xử lý 8-lõi của Intel Xeon họ 5500 [13, 14, 64, 65]. 
 49 
 Với xu hướng công nghệ là tăng số lượng lõi để tiết kiệm không gian, các kiến 
trúc đa lõi hiện nay hầu hết sử dụng L2 cache chia sẻ. Các lõi với L1 Icache và L1 
Dcache riêng kết hợp vào trong chip và các lõi chia sẻ L2 cache. Ví dụ, kiến trúc 
Tiled CMP 16-lõi như hình 2.17. Ở đây, L2 cache được tổ chức thành các mảnh 
phân bố đều theo các lõi được chia sẻ, một mảnh L2 cache chia sẻ cho 4-lõi kề. 
Kiến trúc này cho phép linh hoạt trong cấu hình lại L2 cache chia sẻ cho các lõi 
theo nhu cầu dung lượng, giảm đáng kể yêu cầu băng thông tổng thể, và tăng hiệu 
năng của hệ thống [9, 49, 50]. 
 Hình 2.17: Tiled CMP 16-lõi với kiến trúc L2 cache chia sẻ [49, 50]. 
 2.5.2. Cache chia sẻ thông minh 
 Cache thông minh đầu tiên được đưa ra bởi kiến trúc Intel® Advanced Smart 
Cache có cache chia sẻ ở cấp cuối cùng, từ kiến trúc Nehalem họ Xeon 5500 và tiếp 
tục đến các kiến trúc Corei (L3 smart cache) [66]. AMD và Sun cũng đưa ra các đặc 
tính thông minh của cache chia sẻ ở cấp cache cuối. Cache chia sẻ thông minh có 
những đặc điểm sau đây: 
 Cache chia sẻ cho tốc độ chuyển dữ liệu giữa các lõi nhanh hơn so với bộ 
 nhớ chính. 
 Kiến trúc cache chia sẻ đem lại nhiều lợi ích và đảm bảo tỷ số hiệu năng/chi 
 phí tốt hơn so với cache riêng. 
 Sử dụng hiệu quả cache chia sẻ 
 - Nếu một lõi rỗi, lõi còn lại chiếm lấy toàn bộ dung lượng của cache chia sẻ. 
 - Giảm sự không sử dụng của cache chia sẻ. 
 50 
 Linh hoạt cho người lập trình 
 - Có nhiều khả năng chia sẻ dữ liệu cho các luồng chạy trên từng lõi riêng mà 
chúng cùng chia sẻ cache. 
 - Một lõi có thể xử lý trước hoặc xử lý sau dữ liệu cho các lõi còn lại. 
 - Có các cơ chế truyền thông thay phiên nhau giữa các lõi. 
 Giảm được sự phức tạp của liên kết logic cache 
 - Giảm sự chia sẻ bị lỗi của cache chia sẻ. 
 - Tải nhỏ hơn cho duy trì sự kết dính với nhau so với kiến trúc cache riêng. 
 Giảm dư thừa lưu trữ dữ liệu 
 - Cùng một dữ liệu chỉ cần lưu trữ một lần. 
 - Các luồng lệnh giống nhau chạy ở các lõi riêng nhưng trên dữ liệu khác 
nhau cùng chia sẻ các địa chỉ lệnh. Khi đó, các địa chỉ lệnh được sao chép cho tất cả 
các cache (riêng và chia sẻ) sẽ gây ra sự lãng phí, mà chỉ cần có một bản sao của 
các lệnh trên cache chia sẻ. 
 Giảm lưu lượng của bus bộ nhớ 
 Chia sẻ dữ liệu hiệu quả giữa các lõi, cho phép dữ liệu yêu cầu được giải 
quyết ở cấp cache chia sẻ cuối cùng thay vì tất cả đi đến bộ nhớ chính. 
2.6. Tính nhất quán cache trong các chip đa xử lý, đa luồng 
 2.6.1. Thế nào là nhất quán cache 
 Nhất quán cache: Tính nhất quán của cache là khi cache chứa bản sao của một 
phần của bộ nhớ chính, điều quan trọng là cache luôn phản ánh nội dung bộ nhớ 
chính [64, 67]. Một số thuật ngữ được dùng để mô tả quá trình duy trì tính nhất 
quán của bộ nhớ cache: 
 Snoop: 
 Snoop là khi cache đang giám sát các đường địa chỉ cho giao tác. Chức năng 
này cho phép cache biết được các giao tác đang truy nhập đến vùng bộ nhớ có nội 
dung mà nó đang giữ. 
 51 
 Snarf: 
 Cache được gọi là đã snarf dữ liệu khi nó có được những thông tin từ các 
đường dữ liệu. Chức năng này cho phép cache cập nhật và duy trì tính nhất quán 
của nó. 
 Như vậy, snoop và snarf là hai cơ chế mà cache dùng để duy trì tính nhất quán 
cache. 
 Nhất quán cache chỉ có trong kiến trúc chip đa lõi, bởi vì các lõi đều cùng chia 
sẻ cache và bộ nhớ. Xét trường hợp cụ thể sau đây: Cho rằng CPU là chip đa xử lý 
có 2-lõi là P1 và P2. Giai đoạn thứ nhất P2 thực hiện lệnh: ld r2, x (nạp nội dung 
của ngăn nhớ x từ bộ nhớ chính về thanh ghi r2 của P2) như hình 2.18. 
 Hình 2.18: P2 thực hiện lệnh ld r2, x về thanh ghi r2 của P2 [67]. 
 Giai đoạn thứ hai, P1 thực hiện lệnh ld r2, x (nạp nội dung ngăn nhớ x từ bộ 
nhớ chính về thanh ghi r2 của P1) như hình 2.19. 
 Hình 2.19: P1 thực hiện lệnh ld r2, x [67]. Hình 2.20: P1 thực hiện các lệnh: add r1, 
 r2, r4; st x, r1 [67]. 
 Lúc này, nội dung ngăn nhớ x giống với nội dung ở các thanh ghi r2 của P1 và 
P2. Tiếp theo, P1 thực hiện liên tiếp các lệnh add r1, r2, r4 (cộng nội dung của các 
 52 
thanh ghi r1, r2, r4 và lưu kết quả vào r1), st x, r1 (chuyển nội dung của r1 vào 
ngăn nhớ x) như hình 2.20. Đến đây, có thể thấy rằng nội dung của ngăn nhớ x trên 
bộ nhớ chính đã thay đổi khác với nội dung của nó đã được lưu trên các thanh ghi 
r2 của P1 và P2. 
 2.6.2. Các giao thức nhất quán cache 
 Có hai kỹ thuật để đảm bảo tính nhất quán cache: Dựa vào thư mục và rình mò 
[25, 34, 62]. 
 Trong giao thức dựa vào thư mục, một thư mục trung tâm chứa trạng thái của 
chia sẻ một khối của bộ nhớ chính, giao thức dựa vào thư mục được sử dụng trong 
các chip đa xử lý có bộ nhớ chia sẻ phân tán (DSM), nhưng giao thức này trễ cao 
hơn so với giao thức “rình mò”. 
 Trong giao thức rình mò, không cần có thư mục trung tâm, từng cache “rình 
mò” hoặc nghe để đảm bảo tính nhất quán trong các cache. Giao thức rình mò được 
sử dụng trong các chip đa xử lý có bộ nhớ chia sẻ tập trung (CSM) sử dụng mạng 
liên kết có cấu hình Bus và Ring [43]. 
2.7. Kết luận chương 2 
 - Chương này đã nghiên cứu các tổ chức cache của kiến trúc CMP đa luồng; 
các đặc tính hiệu năng cache, và các cách ghi và đọc cache. Đồng thời, nghiên cứu 
đã đánh giá các tổ chức cache và lựa chọn được tổ chức cache liên kết tập hợp n-
dòng cho hiệu năng xử lý cao nhất. 
 - Nghiên cứu các chính sách thay thế cache cho kiến trúc CMP đa luồng nhằm 
nâng cao hiệu năng xử lý. 
 Tuy nhiên, các nghiên cứu hiện nay đều tập trung tổ chức cache 2 cấp với L2 
cache chia sẻ cho tất cả các lõi. Với kiến trúc chip có 2 cấp cache như vậy, khi số 
lượng lõi tăng lên sẽ làm hạn chế băng thông, làm tăng độ trễ, và gây nghẽn nút cổ 
chai tại cấp cache chia sẻ. Vì vậy, việc nghiên cứu đánh giá, đề xuất mô hình tổ 
chức cache phù hợp nhằm cải thiện và nâng cao hiệu năng của CMP đa luồng là hết 
sức cần thiết. 
 53 
 Chương 3 
 PHÂN TÍCH ĐÁNH GIÁ HIỆU NĂNG CỦA TỔ CHỨC 
CACHE TRONG KIẾN TRÚC CHIP ĐA XỬ LÝ, ĐA LUỒNG 
3.1. Cơ sở lý thuyết để phân tích đánh giá hiệu năng của tổ chức cache [6, 
 23, 42] 
 3.1.1. Kiến trúc chip đa xử lý, đa luồng là mạng xếp hàng đóng đa lớp có 
 dạng tích các xác suất (MCPFQN) 
 3.1.1.1. Khái quát mạng xếp hàng đóng 
 Mạng xếp hàng đóng là mạng xếp hàng không có các cửa vào và các cửa ra, 
mà thay vào đó là các liên kết hồi tiếp từ một số cửa ra của một số hàng đợi nào đó 
đến một số cửa vào của một số hàng đợi khác. Như vậy, trong mạng xếp hàng đóng 
không có khách hàng (bản tin) nào có thể vào và hoặc ra khỏi mạng và tổng số 
khách hàng là một số không đổi và được xác định. Hình 3.1 là ví dụ một mô hình 
mạng xếp hàng đóng. Tùy theo số lượng lớp công việc (khách hàng) mà có mạng 
xếp hàng đóng đơn lớp công việc và mạng xếp hàng đóng đa lớp công việc. 
 µ2 
 µ1 µ3 
 µN 
 Hình 3.1: Mô hình mạng xếp hàng đóng [23]. 
  Các loại nút hàng đợi 
 Mô hình mạng xếp hàng đóng thường sử dụng một số loại nút hàng đợi sau: 
 Loại 1: M/M/m-FCFS 
 Trong đó, M đầu tiên biểu thị thời gian giữa các lần đến phân bố theo hàm mũ, 
M thứ hai biểu thị thời gian phục vụ phân bố theo hàm mũ, và m là số lượng server 
(m ≥ 1). Loại này có nguyên tắc phục vụ là khách hàng vào trước được phục vụ 
trước (FCFS), các thiết bị nhớ thường được mô hình như một nút hàng đợi loại này. 
 54 
 Loại 2: M/G/m-PS 
 Trong đó, M biểu thị thời gian giữa các lần đến phân bố theo hàm mũ, G biểu 
thị thời gian phục vụ theo phân bố chung, m số lượng server (m ≥ 1), và nguyên tắc 
phục vụ là chia sẻ xử lý (PS). Các CPU của máy tính thường được mô hình như một 
nút hàng đợi loại này. 
 Lọai 3: M/G/∞ (server vô hạn) 
 Trong đó, M biểu thị thời gian giữa các lần đến phân bố theo hàm mũ, G biểu 
thị thời gian phục vụ theo phân bố chung, và số lượng server là vô hạn, các thiết bị 
đầu cuối có thể được mô hình như các nút hàng đợi loại này. 
 Loại 4: M/G/1-LCFS PR 
 Trong đó, M biểu thị thời gian giữa các lần đến phân bố theo hàm mũ, G biểu 
thị thời gian phục vụ theo phân bố chung, số lượng server bằng 1, và nguyên tắc 
phục vụ là khách hàng vào sau được phục vụ trước theo kiểu quay vòng (LCFS PR), 
trong thực tế không ứng dụng mô hình nút loại 4 này trong các hệ thống máy tính. 
  Đặc điểm của mạng xếp hàng đóng 
 Mạng xếp hàng đóng có đặc điểm sau đây: 
 - Có K nút trong mạng; i = 1, 2,, K 
 - ni: số lượng khách hàng ở nút i; với i = 1, 2,, K 
 - Tổng số khách hàng (công việc) cùng loại (lớp) vận hành trong mạng đóng 
 K
 N = ni (3.1) 
 i=1
 - Không có khách hàng mới nào từ ngoài mạng đến bất kỳ nút i trong mạng,
λ0i 0, tức là p0i = 0. Không có khách hàng nào từ bất kỳ nút i nào ra khỏi mạng, 
tức là pi0 = 0. Do đó, tổng số khách hàng ở trong mạng xếp hàng đóng là cố định 
không đổi. 
 - Với pij là xác suất định tuyến từ nút i đến nút j thỏa mãn cho mạng đóng 
 K
  pij 1 ; i = 1, 2, , K (3.2) 
 j 1
 55 
 - Tổng tốc độ của các khách hàng đến nút i được xác định là λi 
 K
 λi = λj p ji với i = 1, 2, , K (3.3) 
 j=1
 - Số cuộc trung bình đến nút i (tốc độ tương đối đến nút i) của khách hàng là 
 λi
ν = hay 
 i λ
 KK
 pν λ p
 λ j ji  j ji K
 λi j=1 j=1
 νi = = = = ν j p ji ; với i = 1, 2, , K (3.4) 
 λ λ λ j=1
 - Mỗi server ở nút i có thời gian phục vụ khách hàng trung bình ES i có phân 
 1
bố hàm mũ với giá trị ES  và độc lập với các thời gian phục vụ ở các nút 
 i μ
 i 
khác, độc lập với các quá trình đến. 
 - Mức độ sử dụng của nút i là 
 λi
 Ui = < 1 (3.5a) 
 miμ i
 Trong đó: mi là số server trong từng nút i. 
 Nếu mi = 1, ta có hàng đợi loại M/M/1, thì mức độ sử dụng của nút i là 
 λi
 Ui = < 1 hay λi < μ i (3.5b) 
 μi
 - Đối với mạng đóng chỉ có thể xác định các giá trị tốc độ đến tương đối νi . 
Do đó, mức độ sử dụng tương đối của nút i được xác định 
 νi λ i
 Ui = = (3.5c) 
 miμi m i μ i λ
 - Các tốc độ phục vụ của từng nút là hàm phụ thuộc số công việc 
 ni× μ i ; n i m i
 μi (n i ) (3.6) 
 mi× μ i ; n i m i
 56 
 Trong trường hợp mạng xếp hàng đóng có đa lớp công việc 
 - R: số lượng các lớp công việc trong một mạng, với r = 1, 2,.., R. 
 - nir : số lượng các công việc của lớp thứ r ở nút i 
 KR
  nir = N (3.7) 
 i=1 j=1
 - Nr: số lượng công việc của lớp thứ r trong toàn mạng 
 K
 nir = N r (3.8) 
 i=1
 - N: tổng số công việc thuộc tất cả các lớp của toàn mạng là một vector tổng 
các số lượng công việc của từng lớp, với N = (N1, N2,.., NR). 
 - Si: trạng thái của nút i của mạng, Si = (ni1, ni2,, niR), và thỏa mãn 
 K
 Si = N (3.9) 
 i=1
 - S: trạng thái của toàn mạng gồm nhiều lớp, các công việc là vector 
 S = (S1, S2, SN) 
 - μir : tốc độ phục vụ của nút i cho tất cả các công việc thuộc lớp r. 
 - pir,js : xác suất định tuyến mà công việc của lớp r ở nút i được chuyển đến lớp 
s ở nút j. 
 3.1.1.2. Khái quát mạng xếp hàng đóng có dạng tích các xác suất 
 Mạng xếp hàng đóng có dạng tích các xác suất là mạng Gordon-Newell được 
mở rộng từ định lý Jackson của mạng xếp hàng mở. 
  Định nghĩa mạng Gordon-Newell 
 Gordon-Newell định nghĩa như sau: 
 Một mạng gồm K nút kết nối với nhau được gọi là mạng Gordon-Newell nếu 
nó thỏa mãn các điều kiện sau đây: 
 - Là một mạng đóng (không có khách hàng từ bên ngoài vào mạng và không 
có khách hàng nào từ bên trong đi ra khỏi mạng). 
 57 
 - Tất cả thời gian phục vụ được phân bố theo hàm mũ và nguyên tắc phục vụ 
ở tất cả các nút là FCFS (hay FIFO). 
 - Một khách hàng được phục xong ở nút i sẽ chuyển một số nút j khác với xác 
 K
suất chuyển tiếp pij, thỏa mãn p ji 1. 
 j 1
 - Mức độ sử dụng của tất cả các nút đều nhỏ hơn 1. 
  Định lý Gordon-Newell 
 Định lý Gordon-Newell phát biểu rằng: trong một mạng Gordon-Newell gồm 
 K
K nút, với tổng số khách hàng N ni , trong đó ni: số lượng khách hàng ở nút i, 
 i 1
thì có tích xác suất trạng thái bền vững 
 1 K
 π(n) π(n,n,...,n1 2 K )  F(n)i i (3.10) 
 G(N) i 1
 Trong đó, G(N): hằng số bình thường hóa, và thỏa mãn điều kiện bình thường 
hóa là tổng tất các các xác suất trạng thái mạng bằng 1 
 K
 G(N)   Fi (n i ) (3.11) 
 n1 n 2 ... n K N i 1
 Trong đó, Fi(ni): là các hàm tương ứng với các xác suất πi(ni) của nút i, được 
cho bởi 
 n i
 νi 1
 Fi( n i ) = × (3.12) 
 μi β i(ni )
 Trong đó, νi : là số cuộc trung bình đến nút i, được xác định theo (3.4). 
 Hàm βi n i được xác định theo 
 ni ! ; n i m i
 ni m i
 β(n)i i m!m i i ; n i m i (3.13) 
 1 ; mi 1
 Cho các ứng dụng khác nhau, mà các tốc độ phục vụ phụ thuộc vào số lượng 
các công việc ở từng nút, dạng chung của hàm F(ni i )được cho bằng 
 58 
 ni
 νi
 Fi (n i ) = (3.14) 
 Ai (n i )
 n
 i
 μi (j) ; n i 0
 Với: Ai (n i ) j 1 (3.15) 
 1 ; ni 0
 Với quan hệ (3.6) có thể dễ dàng nhận thấy rằng: trường hợp các tốc độ phục 
vụ là hằng số thì đẳng thức (3.12) là trường hợp riêng của đẳng thức (3.14). 
  Tính các xác suất trạng thái theo phương pháp Gordon-Newell 
 Tính các xác suất trạng thái theo phương pháp Gordon-Newell có thể thực 
hiện theo 4 bước: 
 Bước 1: Tính các số cuộc trung bình đến tất cả các nút i = 1, 2,..., K của mạng 
xếp hàng đóng theo công thức (3.4). 
 Bước 2: Đối với tất cả các nút i = 1, 2,..., K, tính các hàm Fi(ni) theo công thức 
(3.14). 
 Bước 3: Tính hằng số bình thường hóa G(N) theo công thức (3.11). 
 Bước 4: Tính các xác suất trạng thái của mạng theo công thức (3.10). 
 3.1.1.3. Kiến trúc chip đa xử lý, đa luồng là mạng xếp hàng đóng đa lớp có 
 dạng tích các xác suất (MCPFQN) 
 Một CMP đa luồng được coi là một hệ thống mạng xếp hàng đa lớp công việc. 
Các công việc trong mạng đa lớp được coi là song song mức lệnh (ILP) hay song 
song mức luồng (TLP), mỗi lệnh hay mỗi luồng lệnh có đặc điểm riêng được coi là 
một lớp. CMP đa luồng chỉ xử lý một số luồng hay một số lệnh cố định (không 
thêm vào, không bớt đi) nên được mô hình hóa bằng mạng xếp hàng đóng. Vì các 
luồng có thể khác nhau về thời gian phục vụ (do độ dài luồng, tính chất các lệnh và 
dữ liệu của luồng) nên mạng xếp hàng đóng được gọi là mạng xếp hàng đóng đa 
lớp. Trong CMP đa luồng các lệnh hay luồng lệnh có cùng thời gian phục vụ, cùng 
tính chất thuộc vào một lớp. 
 59 
 Kiến trúc CMP đa luồng là một hệ thống đóng tìm được nghiệm của các đẳng 
thức cân bằng toàn cục, nghiệm này có dạng tích các xác suất. 
 Do đó, kiến trúc CMP đa luồng được mô hình hóa bằng một mạng xếp hàng 
đóng đa lớp có dạng tích các xác suất (MCPFQN). 
 3.1.2. Thuật toán phân tích giá trị trung bình (MVA) đánh giá hiệu năng cho 
 các mạng xếp hàng đ