Bài tập lớn môn Kiến trúc máy tính về "Bốn nghiên cứu điển hình" | Học viện Công nghệ Bưu chính Viễn thông

lOMoARcPSD| 36991220
Bốn nghiên cứu điển hình được giới thiệu ở đầu chương dẫn đến các chương
trình song song quá phức tạp và quá dài để sử dụng
Thay vào đó, phần này trình bày một phiên bản đơn giản hóa: bộ giải phương
trình. Bộ giải phương trình tìm hiểu sâu hơn và minh họa cách thực hiện một
chương trình song song bằng cách sử dụng ba mô hình lập trình. Tất cả được
viết được viết bằng C hoặc mã giả giống Pascal được tăng cường với các phần
mở rộng đơn giản cho phép song song, do đó thể hiện các giao tiếp nguyên thủy
và đồng bộ hóa cơ bản mà không gian địa chỉ dùng chung hoặc trừu tượng được
cộng tác đề chuyền thông tin. Các ngôn ngữ tuần tự tiêu chuẩn được bổ sung
cho tính song song cũng phản ánh trạng thái của hầu hết các lập trình song song thực tế ngày nay.
2.3.1 Nhân của bộ giải phương trình
Nhân của bộ giải phương trình giải một phương trình vi phân riêng đơn giản trên
lưới, sử dụng phương pháp được gọi là phương pháp vi phân hữu hạn. Nó hoạt
động trên một mảng hai chiều thông thường hoặc một mảng gồm (n+2)x(n+2)
phần tử. Các hàng và cột ở viền của lưới chứa các giá trị biên không thay đổi,
trong khi n x n điểm bên trong được cập nhật bởi bộ giải, bắt đầu từ các giá trị
ban đầu của chúng . Việc tính toán tiến hành qua một số lần quét. Trong mỗi lần
quét, nó hoạt động trên tất cả n x n điểm bên trong của lưới. Đối với mỗi điểm,
nó thay thế giá trị của nó bằng giá trị trung bình có trọng số của chính nó và bốn
điểm lân cận gần nhất - trên, dưới, trái và phải (xem Hình 2.6). Các cập nhật
được thực hiện tại chỗ trong lưới, do đó, tính toán cập nhật cho một điểm sẽ
thấy các giá trị mới của các điểm ở trên và bên trái của điểm đó và các giá trị cũ
của các điểm bên dưới và bên phải của điểm đó. Hình thức cập nhật này được
gọi là phương pháp Gauss Seidel. Trong mỗi lần quét, hạt nhân cũng tính toán
sự khác biệt trung bình của một phần tử được cập nhật so với giá trị trước đó
của nó. Nếu sự khác biệt trung bình này trên tất cả các ments nhỏ hơn một tham
số 'dung sai ' được xác định trước, thì giải pháp được cho là đã hội tụ và bộ giải
sẽ thoát ra khi kết thúc quá trình quét. Nếu không, nó thực hiện một lần quét
khác và kiểm tra sự hội tụ một lần nữa. Mã giả tuần tự được hiển thị trong Hình 2.7. lOMoARcPSD| 36991220
HÌNH 2.6 Điểm đen là A[i,j] trong mảng hai chiều đại diện cho lưới và được cập
nhật bằng cách sử dụng chính nó và bốn điểm tô bóng là lân cận gần nhất của
nó theo phương trình ở bên phải 2.3.2 Phân tách Hình 2.7 lOMoARcPSD| 36991220
Đối với các chương trình có cấu trúc vòng trong các vòng lặp liên tiếp hoặc nhóm
vòng lặp, một cách đơn giản để xác định tính đồng thời là bắt đầu từ chính cấu
trúc vòng lặp. Chúng ta kiểm tra lần lượt các vòng lặp hoặc nhóm vòng lặp trong
chương trình, xem liệu các lần lặp của chúng có thể được thực hiện song song
hay không và xác định xem điều này có đưa ra đủ đồng thời hay không. Sau đó,
chúng ta có thể tìm kiếm sự đồng thời giữa các vòng lặp hoặc thực hiện theo
một cách tiếp cận khác nếu cần. Chúng ta hãy theo dõi cách tiếp cận dựa trên
cấu trúc chương trình này trong Hình 2.7.
Mỗi lần lặp lại của vòng lặp while ngoài cùng, bắt đầu từ dòng 15, sẽ quét qua
toàn bộ lưới. Những lần lặp này rõ ràng là không độc lập vì dữ liệu được sửa đổi
trong mỗi lần lặp và sẽ được truy cập trong lần tiếp theo. Xem xét tổ hợp vòng
lặp ở các dòng 17-24 và bỏ qua các dòng chứa di 昀昀. Xem xét vòng lặp bên
trong trước (vòng lặp thứ j bắt đầu từ dòng 18). Mỗi lần lặp của vòng lặp này
đọc điểm lưới (A[i][j-1]) đã được ghi trong lần lặp trước. Do đó, các lần lặp phụ
thuộc tuần tự và chúng ta gọi đây là vòng lặp tuần tự. Vòng lặp bên ngoài của tổ
hợp lặp này cũng là tuần tự, tính từ phần tử hàng thứ i - 1 được viết trong lần
lặp trước (thứ i-1) của vòng lặp này. Vì vậy, phân tích đơn giản về các vòng lặp
hiện có và sự phụ thuộc của chúng phát hiện ra không có sự đồng thời trong chương trình ví dụ này
Nói chung, một giải pháp thay thế cho việc dựa vào cấu trúc chương trình để tìm
sự đồng thời là quay trở lại sự phụ thuộc cơ bản trong các thuật toán cơ bản
được sử dụng, không phụ thuộc vào chương trình hoặc cấu trúc vòng lặp. Trong
bộ giải phương trình* , chúng ta có thể xem xét phụ thuộc cơ bản trong việc tạo
và sử dụng các giá trị dữ liệu (dữ liệu phụ thuộc) ở mức độ chi tiết của các điểm
lưới riêng lẻ. Như đã thảo luận trước đó, vì tính toán tiến hành từ trái sang phải
và từ trên xuống dưới trong lưới, tính toán a điểm lưới cụ thể trong chương trình
tuần tự sử dụng các giá trị cập nhật của lưới điểm trực tiếp phía trên và bên trái.
Mẫu phụ thuộc dữ liệu này được hiển thị trong Hình 2.8. Kết quả là các phần tử
dọc theo đường chéo nhất định (tây nam đến đông bắc) không có phụ thuộc
giữa chúng với nhau và có thể được tính toán song song, trong khi các điểm
trong đường chéo tiếp theo phụ thuộc vào một số điểm trong đường trước đó
một. Từ sơ đồ này, chúng ta có thể quan sát thấy công việc của O liên quan đến
mỗi quét, có một sự đồng thời cố hữu tỷ lệ với n dọc theo đường chéo chống và
một sự phụ thuộc tuần tự tỷ lệ với n dọc theo đường chéo. lOMoARcPSD| 36991220 Hình 2.8
Giả sử chúng ta quyết định phân chia công việc thành các điểm lưới riêng lẻ để
cập nhật một điểm lưới duy nhất là một nhiệm vụ. Đầu tiên, chúng ta có thể giữ
nguyên cấu trúc vòng lặp của chương trình và chèn đồng bộ hóa điểm-điểm để
đảm bảo rằng giá trị mới cho một điểm lưới đã được tạo ra trong quá trình quét
hiện tại trước khi nó được sử dụng bởi các điểm bên dưới hoặc bên phải. Do đó,
các tổ hợp vòng lặp khác nhau (của chương trình tuần tự) và thậm chí các quá
trình quét khác nhau có thể được tiến hành đồng thời trên các phần tử khác
nhau, miễn là những sự phụ thuộc ở mức phần tử không bị vi phạm. Nhưng chi
phí của đồng bộ hóa này ở cấp điểm lưới có thể quá cao. Thứ hai, chúng ta có
thể thay đổi cấu trúc vòng lặp: vòng lặp for đầu tiên (dòng 17) có thể vượt quá
đường chéo và vòng lặp for bên trong có thể nằm trên các phần tử trong vòng
lặp chống đường chéo. Sau đó, vòng lặp bên trong có thể được thực thi song
song hoàn toàn , với sự đồng bộ hóa toàn cục giữa các lần lặp của vòng lặp for
bên ngoài (để bảo toàn các phụ thuộc một cách thận trọng qua các đường chống
chéo). Sự liên quan sẽ được sắp xếp rất khác nhau trong hai trường hợp, đặc
biệt nếu sự liên quan là trong các thông điệp rõ ràng. Tuy nhiên, cách làm này
cũng có vấn đề. Đồng bộ hóa toàn bộ vẫn diễn ra rất thường xuyên – một lần
cho mỗi lần chống chéo. Ngoài ra, số lần lặp trong vòng lặp song song (bên trong)
thay đổi với các ý tưởng liên tiếp của vòng lặp bên ngoài, khi kích thước của các
đường chống chéo thay đổi, gây ra sự mất cân bằng tải giữa các quá trình, đặc
biệt là trong các đường chống chéo ngắn hơn. Do tần suất đồng bộ hóa, mất cân lOMoARcPSD| 36991220
bằng tải và độ phức tạp của lập trình, cả hai cách tiếp cận này đều không được
sử dụng nhiều trên các kiến trúc hiện đại.
Cách tiếp cận thứ ba và phổ biến nhất là dựa trên việc khai thác kiến thức về vấn
đề vượt ra ngoài sự phụ thuộc trong chính chương trình tuần tự. Thứ tự mà các
điểm nút trong lưới được cập nhật trong thuật toán tuần tự (từ trái sang phải và
từ trên xuống dưới) trên thực tế không phải là cơ bản đối với phương pháp giải
Gauss -Seidel; nó đơn giản là một thứ tự có thể thuận tiện để lập trình tuần tự.
Vì phương pháp GaussSeidel không phải là một phương pháp giải chính xác mà
là lặp lại cho đến khi hội tụ, chúng ta có thể cập nhật các điểm lưới theo một thứ
tự khác miễn là chúng ta sử dụng các giá trị cập nhật cho các điểm lưới đủ
thường xuyên.2 Một thứ tự như vậy thường được sử dụng cho các phiên bản
song song được gọi là thứ tự đỏ-đen . Ý tưởng ở đây là tách các điểm lưới thành
các điểm đỏ và đen xen kẽ như trên bàn cờ (xem Hình 2.9) để không có điểm đỏ
nào tiếp giáp với điểm đen hoặc ngược lại. Vì mỗi điểm chỉ đọc bốn điểm lân cận
gần nhất của nó, để tính một điểm đỏ nhất định, chúng ta không cần giá trị cập
nhật của bất kỳ điểm đỏ nào khác; chúng ta chỉ cần các giá trị cập nhật của các
điểm đen phía trên và bên trái của nó (trong một lần quét tiêu chuẩn) và ngược
lại để tính toán các điểm đen . Do đó, chúng ta có thể chia quét lưới thành hai
giai đoạn, đầu tiên tính toán tất cả các điểm màu đỏ và sau đó tính toán tất cả
các điểm màu đen. Trong mỗi giai đoạn không tồn tại sự phụ thuộc giữa các
điểm lưới, ta có thể tính toán tất cả n^2/2 điểm đỏ song song, đồng bộ hóa toàn
bộ, sau đó tính toán tất cả n2/2 điểm đen song song cùng lúc. Đồng bộ hóa toàn
cục là không nhất thiết và có thể được thay thế bằng đồng bộ hóa điểm điểm ở
cấp điểm lưới vì không phải tất cả các điểm đen cần phải đợi tất cả các điểm đỏ
được tính toán ; nhưng đồng bộ toàn cục rất tiện lợi.
Vì thứ tự màu đỏ-đen khác với thứ tự tuần tự gốc của chúng ta, nó có thể hội tụ
trong ít hoặc nhiều lần quét hơn. Nó cũng có thể tạo ra các giá trị cuối cùng khác
nhau cho các điểm lưới (mặc dù vẫn nằm trong dung sai hội tụ). Trong khi các
bản cập nhật điểm đỏ không thấy các giá trị cập nhật của bất kỳ điểm đen nào,
các điểm đen sẽ thấy các giá trị cập nhật của tất cả các vùng lân cận màu đỏ của
chúng từ giai đoạn đầu tiên của quá trình quét hiện tại, không chỉ các giá trị ở
bên trái và phía trên. Thứ tự mới tuần tự tốt hơn hay xấu hơn thứ tự cũ tùy
thuộc vào vấn đề. Thứ tự màu đỏ-đen cũng có lợi thế là các giá trị được tạo ra
và các thuộc tính hội tụ là dấu hiệu của số lượng bộ xử lý được sử dụng vì không
có sự phụ thuộc nào xảy ra trong một giai đoạn. Nếu bản thân chương trình tuần
tự sử dụng thứ tự đỏ đen, và tính song song hoàn toàn không thay đổi kết quả
hoặc đặc tính hội tụ, điều đó làm cho chương trình song song được xác định lOMoARcPSD| 36991220
Xem xét một phương pháp đơn giản hơn nhưng vẫn phổ biến mà không tách các
điểm thành màu đỏ và màu đen. Phương pháp này chỉ đơn giản là bỏ qua sự
phụ thuộc giữa các điểm lưới trong vòng quét. Trong quá trình quét, một quá
trình chỉ cần cập nhật các giá trị của tất cả các điểm lưới được chỉ định của nó,
truy cập các vùng lân cận gần nhất của nó cho dù
chúng đã được cập nhật trong quá trình quét hiện tại bởi các quy trình được chỉ
định của chúng hay chưa. Khi chỉ sử dụng một quy trình duy nhất, điều này mặc
định là thứ tự cập nhật tuần tự ban đầu. Khi nhiều quy trình được sử dụng, thứ
tự không thể đoán trước được; nó phụ thuộc vào sự phân công của con trỏ tới
các quy trình, số lượng quy trình được sử dụng và tốc độ thực thi các điểm
chuyên biệt khác nhau tại thời điểm chạy. Việc thực thi không còn mang tính
quyết định và số lần quét cần thiết để hội tụ có thể phụ thuộc vào số lượng quy
trình được sử dụng; tuy nhiên, đối với hầu hết các nhiệm vụ, số lần quét sẽ không thay đổi nhiều. Hình 2.9
Nếu chúng ta chọn phân tách thành các lần lặp vòng lặp bên trong riêng lẻ (các
điểm lưới), chúng ta có thể thể hiện chương trình bằng cách sửa lại các dòng 15-
26 của Hình 2.7. Hình 2.10
phần được đánh dấu cho thấy các thay đổi đối với mã in đậm : tất cả những gì
chúng ta đã làm là thay thế từ khóa for trong các vòng lặp song song bằng for_all.
Một vòng lặp for_all chỉ đơn giản là cho hệ thống phần cứng / phần mềm cơ bản lOMoARcPSD| 36991220
rằng tất cả các lần lặp của vòng lặp đều có thể được thực thi song song mà không
cần quan tâm về sự phụ thuộc, nhưng nó không nói gì về việc thay thế. Một tổ
vòng lặp có cả hai cấp độ lồng là for_all có nghĩa là tất cả các lần lặp trong tổ
vòng lặp (n * n hoặc n^2 ở đây) có thể được thực hiện song song. Hệ thống có
thể chỉ định và sắp xếp song song theo bất kỳ cách nào mà nó chọn; các của
chương trình có chức năng về điều này . Tất cả những gì nó giả định là đồng bộ
hóa toàn bộ ngầm định sau một tổ vòng lặp for_all . Hình 2.10
Trên thực tế, chúng ta có thể phân tách việc tính toán không chỉ thành các lần
lặp vòng lặp bên trong riêng lẻ mà thành bất kỳ nhóm lặp tổng hợp nào mà chúng
ta mong muốn. Giả sử chúng ta muốn phân tách thành các hàng điểm lưới để
công việc của toàn bộ hàng là một nhiệm vụ không thể phân tách. Chúng ta có
thể thể hiện điều này bằng cách làm cho vòng lặp bên trong trên dòng 18 trở
thành một vòng lặp tuần tự , thay đổi for_all của nó trở lại thành for , nhưng để
vòng lặp trên các hàng trên dòng 17 là một vòng lặp for_all song song. 2.3.3 Gán
Bằng cách sử dụng phân tách dựa trên hàng, chúng ta hãy xem cách chúng ta có
thể gán các hàng cho các điểm chuyên nghiệp một cách rõ ràng. Tùy chọn đơn
giản nhất là một nhiệm vụ tĩnh (xác định trước) mà mỗi quy trình chịu trách
nhiệm cho một khối hàng liền kề, như được hiển thị trong Hình 2.11, hàng bên trong I
Hàng nội bên trong i được chỉ định xử lý với p là số tiến trình
. Các nhiệm vụ tĩnh thay thế cho việc gán khối , chẳng hạn như gán theo chu
kỳ trong đó các hàng xen kẽ giữa các quy trình (quy trình i được gán các hàng i,
i + p, v.v. ). Chúng ta cũng có thể xem xét một nhiệm vụ động trong đó mỗi quá lOMoARcPSD| 36991220
trình lặp lại việc lấy hàng khả dụng tiếp theo (chưa được tính toán) sau khi nó
kết thúc với một nhiệm vụ. Sự phân chia vấn đề thành những phần đơn giản này
thể hiện sự cân bằng tải tốt các quy trình miễn là số lượng hàng bên trong chia
hết cho số lượng quy trình. Vì công việc trên mỗi hàng là đồng nhất.
Ta thấy rằng các phép gán tĩnh đã làm giảm thêm tính song song hoặc mức độ
đồng thời ; từ n đến p, bằng cách làm cho các tác vụ lớn hơn và phép gán khối
đã giảm giao tiếp cần thiết bằng cách gán các hàng liền kề cho cùng một bộ xử lý. Tỷ lệ
giao tiếp trên tính toán hiện chỉ bằng
Sau khi kiểm tra sự phân tách và gán, chúng ta đã sẵn sàng để điều phối . Điều
này yêu cầu chúng ta ghim mô hình lập trình xuống. Chúng tôi bắt đầu với mô
hình dữ song song dữ liệu mức cao và sau đó lấy hai mô hình kết hợp chương
trình chính mà dữ liệu song song và các mô hình khác có thể biên dịch thành:
không gian địa chỉ dùng chung và sự giao tiếp rõ ràng.
2.3.4 Điều phối theo mô hình dữ liệu song song
Mô hình dữ liệu song song rất tiện lợi đối với hạt nhân của bộ giải phương trình
vì việc coi tính toán như một luồng điều khiển đơn lẻ thực hiện các phép biến
đổi toàn cục trên cấu trúc dữ liệu mảng lớn là điều hiển nhiên ( Hillis 1985; Millis và Steele 1986). lOMoARcPSD| 36991220
Mã giả cho bộ giải phương trình song song dữ liệu được thể hiện trong Hình
2.12. Giả định rằng các khai báo toàn cục (bên ngoài bất kỳ thủ tục nào) mô tả
dữ liệu được chia sẻ và tất cả các dữ liệu khác (ví dụ, dữ liệu trên ngăn chứa thủ
tục) được ưu tiên trong một quy trình. Dữ liệu được chia sẻ được phân bổ động,
chẳng hạn như mảng A, được cấp phát bằng một lệnh gọi G _MALLOC thay vì
một malloc thông thường. G_MALLOC phân bổ dữ liệu trong một vùng được
chia sẻ của bộ nhớ heap có thể được truy cập và sửa đổi bởi bất kỳ quá trình
nào. Sự khác biệt chính (được hiển thị bằng chữ in đậm) từ chương trình tuần
tự là việc sử dụng các vòng lặp for_all cho các vòng lặp, việc sử dụng câu lệnh
DECO, biến mydi 昀昀 riêng cho mỗi quy trình và việc sử dụng một tuyên bố REDUCE .
Chúng ta đã thấy rằng các vòng lặp for_all chỉ định rằng các vòng lặp có thể được
hình thành song song. Các quy trình song song khác với quy trình thực thi chín
luồng kiểm soát được ngầm định trong mô hình dữ liệu song song và chỉ hoạt
động trongcác vòng lặp song song này. Câu lệnh DECOMP có hai mục đích. Đầu
tiên, nó chỉ định việc gán các lần lặp lại cho các quy trình. Ở đây, nó là phép gán lOMoARcPSD| 36991220
[ BLOCK, *, nprocs), có nghĩa là các hàng đầu tiên được phân chia thành các khối
xen kẽ giữa các tiến trình nprocs và phần thứ hai hoàn toàn không được phân
chia. Việc chỉ định [CYCLIC, *, nprocs ] sẽ ngụ ý phân vùng theo chu kỳ hoặc xen
kẽ các hàng giữa các tiến trình nprocs , chỉ định [ BLOCK, BLOCK, nprocs] sẽ ngụ
ý phân vùng khối liền kề 2D và chỉ định [ *, CYCLIC , nprocs] sẽ có ngụ ý phân
vùng xen kẽ các cột. Vai trò thứ hai của DECOMP là nó cũng chỉ định cách dữ liệu
lưới được phân phối giữa các bộ nhớ trên máy. Biến mydi 昀昀 được sử dụng
để cho phép mỗi quá trình lần đầu tiên tính toán độc lập tổng các giá trị chênh
lệch cho các điểm lưới được chỉ định của nó. Sau đó, câu lệnh REDUCE chỉ đạo
hệ thống nối tất cả các giá trị mydi 昀昀 từng phần lại với nhau thành biến di 昀
昀 có thể được chia sẻ. Điều này làm tăng tính đồng thời. Hoạt động REDUCE
thực hiện giảm, là một kịch bản trong đó nhiều quy trình (tất cả, trong một quy
trình giảm toàn cục ) thực hiện các hoạt động liên kết (chẳng hạn như cộng, lấy
mức tối đa, v.v.) trên cùng một dữ liệu được chia sẻ một cách hợp lý . Tính liên
tưởng ngụ ý rằng thứ tự của các hoạt động không quan trọng. Các phép toán
dấu phẩy động chẳng hạn như các phép toán ở đây, không liên kết vì cách tích
làm tròn phụ thuộc vào thứ tự các phép toán. Tuy nhiên, các tác động này rất nhỏ.