MỤC LỤC
1
2
CHƯƠNG 3
CÂU 1: Trình bày về Định luật grosch
TRẢ LỜI:
Vào những năm đầu cuối thập niên 40 của thế kỷ 20, H. Grosch đã nghiên
cứu mối quan hệ giữa công suất của một hệ thống máy tính, P, và giá thành của
nó, Ông mặc nhiên công nhận rằng P = K x C
s
, trong đó s và K là các hằng số
dương. Grosch cũng cho rằng giá trị của s
≈
2 . Đơn giản mà nói, định luật
Grosch cho rằng công suất của một hệ thống máy tính tăng tỉ lệ với bình
phương giá thành của nó. Ngoài ra, có thể biểu diễn công thức giá thành của
một hệ thống là C =
KP /
giả sử rằng s = 2. Mối quan hệ giữa công suất tính
toán và giá thành theo quy luật Grosch được biểu diễn trong hình 3.2.
Hình 3.2 Mối quan hệ công suất và giá thành theo định luật Grosch.
Theo định luật Grosch, để bán một máy tính với giá cao gấp đôi, thì công
suất của nó phải nhanh gấp 4 lần. Ngoài ra, để làm một phép tính rẻ gấp 2 lần,
người ta phải làm cho công suất của máy tính đó chậm hơn bốn lần. Với những
tiến bộ về máy tính, thì dễ dàng thấy rằng định luật Grosch dễ bị loại bỏ, và theo
thời gian chúng ta có thể phát triển những máy tính với công suất nhanh hơn và
rẻ hơn.
3
4
Câu 2: Trình bày Định luật Amdahl
Như chúng ta đã biết hệ số tăng tốc của một hệ thống song song là tỷ lệ

n
m
. Một thuật toán đơn giản để thực hiện tính toán như vậy bao gồm ba
bước sau đây:
1. Nút gốc sẽ gửi vector X(m) tới tất cả các bộ vi xử lý O(m log n)
2. Tất cả các bộ VXL thực hiện sản phẩm
Phần không chia được của phép toán (bước 1 và 3) là O (m) + O (m log
n). Do đó, phần tính toán không chia được là (m) = (O (m) + O (m log n)) / O
(m2) = O ((1 + log n) / m). Lưu ý Lim
m
→∞
f (m) = 0. Do đó, trái với định luật
Amdahl, một phép toán cỡ lớn như vậy có thể đạt được tốc độ tăng tuyến tính.
6
Câu 3: Trình bày Định Luật Gustafson-Barsis
Trả lời:
Trong quá trình rút ra định luật của mình, Gustafson thừa nhận rằng một
phần tác vụ không chia được trong một thuật toán nhất định có thể không được
biết trước. Họ cho rằng trong thực tế, kích thước bài toán tỉ lệ với số bộ vi xử lý
n. Điều này mâu thuẫn với các nội dung cơ bản của định luật Amdahl. Như
chúng ta đã biết định luật Amdahl giả sử rằng lượng thời gian dành cho các
phần của chương trình có thể được thực hiện song song, (1 - f), không phụ
thuộc vào số bộ vi xử lý, n. Gustafson và Brasis mặc nhiên công nhận rằng khi
sử dụng một bộ xử lý mạnh hơn, phép toán có xu hướng sử dụng nhiều tài
nguyên hơn. Họ nhận thấy rằng trong gần đúng bậc nhất, phần song song của
chương trình, không phải phần nối tiếp, tỷ lệ với kích thước bài toán. Họ cho
rằng nếu s và p là các đại lượng tương ứng biểu diễn thời gian nối tiếp và song
song trên một hệ thống song song, thế thì s + p × n là thời gian cần thiết để một
bộ xử lý nối tiếp thực hiện tính toán. Do đó họ đưa vào một hệ số mới, được gọi
là hệ số tăng tốc tỷ lệ, SS (n), có thể được tính như sau:

truy cập qua một mạng liên thông tương tự như một bộ xử lý truy cập bộ nhớ
của nó. Tất cả các bộ vi xử lý có thời gian truy cập như nhau vào bất kỳ vị trí nhớ
nào. Mạng liên thông được sử dụng trong UMA có thể là bus đơn, đa bus, hay
một chuyển mạch điểm chéo. Vì truy cập vào bộ nhớ dùng chung được cân
bằng, các hệ thống này còn được gọi là SMP(hệ đa xử lý đối xứng). Mỗi bộ xử lý
có cơ hội bình đẳng để đọc / ghi vào bộ nhớ, kể cả tốc độ truy cập cũng bằng
nhau. Các ví dụ thương mại của SMPS là các server đa xử lý Sun Microsystems
và Silicon Graphics Inc Một máy tính SMP cấu trúc bus điển hình, như biểu
diễn trong hình 4.3, có nhiệm vụ giảm tranh chấp cho bus bằng cách lấy (truy
cập, truy xuất) lệnh và dữ liệu trực tiếp từ mỗi cache riêng biệt, càng nhiều càng
tốt. Trong những trường hợp đặc biệt, sự tranh chấp bus có thể giảm đến không
sau khi các bộ nhớ cache được tải từ bộ nhớ toàn cục, bởi vì có thể tất cả các
lệnh và dữ liệu hoàn toàn được chứa trong bộ nhớ cache. Tổ chức bộ nhớ này
phổ biến nhất trong số các hệ thống bộ nhớ dùng chung. Ví dụ về kiến trúc này
là các server Sun Starfire , seri HP V, và Compaq AlphaServer GS.
Hình 4.2 Bộ nhớ dùng chung qua hai cổng.
9
Hình 4.3 Hệ thống bộ nhớ dùng chung UMA dựa trên bus (SMP).
10
Câu 3: Trình bày đặc điểm, cấu trúc Bộ nhớ truy cập không đồng đều
(NUMA)
Trong hệ thống Numa, mỗi bộ xử lý có một phần bộ nhớ dùng chung đi kèm.
Bộ nhớ có một không gian địa chỉ duy nhất. Vì vậy, bất kỳ bộ vi xử lý nào cũng
có thể truy cập vào bất kỳ vị trí bộ nhớ nào một cách trực tiếp sử dụng địa chỉ
thực của nó. Tuy nhiên, thời gian truy cập vào các module phụ thuộc vào khoảng
cách đến bộ xử lý. Điều này dẫn đến thời gian truy cập bộ nhớ không giống
nhau. Một số kiến trúc được sử dụng để kết nối các bộ xử lý với các mô-đun bộ
nhớ trong Numa. Trong số đó có các mạng bus cây và thứ bậc. Ví dụ về kiến
trúc Numa là BBN TC-2000, SGI Origin 3000, và Cray T3E. Hình 4.4 biểu diễn tổ
chức hệ Numa.

Nếu không, băng thông bus sẽ giới hạn tốc độ của bộ xử lý.
13
Chúng ta định nghĩa các biến hit rate, số bộ vi xử lý, tốc độ xử lý, tốc độ bus,
và tốc độ chu trình làm việc của bộ vi xử lý như sau:
• N = số bộ xử lý;
• h = hit rate của mỗi cache, được
giả sử là giống nhau đối với tất cả
các cache;
• (1 - h)= miss rate của tất cả các
cache;
• B = băng thông của bus, được đo
theo chu kỳ / giây;
• I = chu trình làm việc của bộ xử lý,
được giả sử là giống nhau đối với
tất cả các bộ vi xử lý, tính theo lần
truy cập / chu kỳ; và
• V = tốc độ vi xử lý cực đại, tính
theo số lần truy cập / giây.
Băng thông hiệu dụng của BUS là BI lần truy cập / giây. Nếu mỗi bộ xử lý
đang chạy với tốc độ V, thì một số lượt bỏ lỡ được tạo ra ở tốc độ V (1 - h). Đối
với một hệ N-bộ xử lý, số lượt bỏ lỡ được tạo ra đồng thời với tốc độ N (1 - h) V.
Điều này dẫn đến sự bão hòa của bus khi N bộ xử lý cùng truy cập vào bus. Có
nghĩa là, N (1 - h) V <BI. Số bộ vi xử lý tối đa cùng với các bộ nhớ cache mà bus
có thể hổ trợ được tính bằng CT:
14
Câu 5: Trình bày sự tương hợp bộ nhớ Cache
Trong một hệ thống bộ nhớ cache đơn lẻ, sự tương hợp giữa bộ nhớ và
cache được duy trì bằng cách sử dụng hai phương pháp: (1) write-through (ghi
hoàn toàn), và (2) write-back (ghi lại, viết ngược). Chẳng hạn, khi một tác vụ
đang chạy trên một bộ xử lý P yêu cầu dữ liệu ở vị trí nhớ X, nội dung của X

toàn cục là:
• Write-update và write-through;
• Write-update và write-back;
• Write-invalidate và write-through;
• Write-invalidate và write-back.
Nếu chúng ta cho phép write-update và write-through trực tiếp trên vị trí nhớ
toàn cục X, bus sẽ bắt đầu bận và cuối cùng tất cả các bộ vi xử lý sẽ được rỗi
trong khi chờ quá trình viết hoàn thành. Trong write-update và write-back, chỉ có
các bản sao trong tất cả các cache được cập nhật. Ngược lại, nếu hoạt động viết
bị giới hạn trong bản sao X ở cache Q, các cache sẽ trở nên không nhất quán
trên X. Thiết lập bit dirty ngăn chặn sự mở rộng các giá trị không nhất quán của
X, nhưng tại một số điểm, các bản sao không nhất quán phải được cập nhật.
17
18
Câu 8: Trình bày giao thức Write-Update và Write- Back
Giao thức này cũng tương tự như trước, ngoại trừ việc thay vì viết
trực tiếp vào bộ nhớ bất cứ khi nào khối dùng chung được cập nhật, quá trình
cập nhật bộ nhớ được thực hiện chỉ khi khối được thay thế. Các trạng thái khối
và giao thức được tóm tắt trong bảng 4.12.
Sự kiện Hoạt động
Read-Hit Sử dụng bản sao cục bộ từ bộ nhớ cache.
Read-Miss Nếu bản Dirty không tồn tại, thì cung cấp một phiên bản từ bộ
nhớ toàn cục. Đặt trạng thái của bản sao này thành hợp lệ. Nếu một bản sao
dirty tồn tại, tạo một bản sao từ bộ nhớ cache, các cache chuyển trạng thái sang
Dirty, cập nhật bộ nhớ toàn cục và bộ nhớ cache riêng cùng với bản sao. Đặt
trạng thái thành VALID trong cả hai Cache.
Write-Hit Nếu các bản sao là Dirty hoặc Reserved (dành riêng), thực hiện
thao tác viết cục bộ, và chuyển trạng thái sang Dirty.Nếu trạng thái là Valid, thì
19
phát ra một lệnh không hợp lệ cho các bộ nhớ cache. Cập nhật bộ nhớ toàn cục

• f là xử lý tuyến tính
• (1-f) là xử lý song song
21
Bài tập ví dụ:
Bài 1: cho một hệ VXL có hệ số tăng tốc 10. Thời gian để 1 VXL hoàn thành
tác vụ là 20s. Hãy thực hiện các yêu cầu sau trong trường hợp đối với bài
toán xử lý song song, phí tổn truyền thông 0.5s
a) Trường hợp không có phí tổn truyền thông. Tính số lượng bộ vi xử
lý? Thời gian thực hiện của hệ? hiệu suất của hệ vi xử lý?
b) Trường hợp có phí tổn truyền thông. Tính thời gian thực hiện của
hệ? hệ số tăng tốc?hiệu suất của hệ?
Bài giải:
Tóm tắt:
t
s
=20s
S(n)=10
t
c
=0,5s
22
• Với trường hợp không có phí tổn truyền thông, tính n, t
m
,
• Với bài toán có phí tổn truyền thông, tính t
m
, S(n),
a) Với bài toán không có phí tổn truyền thông.
• Tính thời gian thực hiện của hệ:
• Ta áp dụng công thức tính hệ số tăng tốc (1)

m
=(s)
• Tính hệ số tăng tốc
• Ta có công thức thay số ta được:
•
• Tính hiệu suất
• Ta có công thức thay số ta được:
•
• Như vậy hiệu suất của hệ khi có phí tổn truyền thông là 80%
•
• Câu 2: cho số bộ vi xử lý là 30, thời gian cần thiết cho 1 bộ VXL
hoàn thành tác vụ là 60s. hãy thực hiện các yêu cầu sau đối với
mô hình từng phần nối tiếp, cho f=0,5
a) Trường hợp không có phí tổn truyền thông. Tính hệ số tăng tốc?
Thời gian thực hiện của hệ? hiệu suất của hệ vi xử lý?
b) Trường hợp có phí tổn truyền thông. Tính thời gian thực hiện của
hệ? hệ số tăng tốc?hiệu suất của hệ? cho phí tổn truyền thông bằng
0,5
• Bài giải:
• Tóm tắt: n=30, t
s
=60s, f=0,5
a) Trường hợp không có phí tổn truyền thông
• Tính thời gian thực hiện của hệ
• Áp dụng công thức
• Trong đó: t
m
là thời gian thực hiện của hệ
• t
s

• trong đó S’(n) là hệ số tăng tốc của hệ trong trường hợp có phí tổn
truyền thông
• thay số vào công thức trên ta được:
• Tính hiệu suất của hệ
• Ta có công thức
• Trong đó hiệu suất của hệ ở trường hợp có phí tổn truyền thông
• Thay số vào công thức trên ta có:
• Như vậy hiệu suất của hệ ở trường hợp có phí tổn truyền thông là
6,4%.
•