Thiết kế giải thuật song song(79 trang)
Mở đầu 3
Chương I Tổng quan về tính toán song song 7
1. 1 Kiến trúc Von Neumann 7
1. 2. Phân loại Flynn 7
1. 3 Các kiến trúc bộ nhớ máy tính song song 9
1. 3. 1 Bộ nhớ dùng chung 9
1. 3. 2 Bộ nhớ phân tán 10
1. 3. 3 Bộ nhớ kết hợp 11
1. 4 Các mô hình lập trình song song 11
1. 4. 1 Lập trình bộ nhớ dùng chung 11
1. 4. 2 Truyền thông điệp 12
1. 4. 3 Mô hình song song dữ liệu 12
1. 4. 4 Mô hình hướng đối tượng 13
1. 4. 5 Mô hình logic 13
1. 5 Truyền thông trong mô hình Multicomputer 13
Chương 2 Thiết kế Giải Thuật song song 16
2. 1 Mô hình thiết kế 16
2. 2 Phương pháp thiết kế 17
2. 3 Phân rã 19
2. 3. 1. Phân rã theo miền 19
2. 3. 2 Phân rã chức năng 20
2. 3. 3 Các vấn đề cần quan tâm 22
2. 4 Truyền thông 23
2. 4. 1 Truyền thông cục bộ 23
2. 4. 2 Truyền thông toàn cục 24
2. 4. 3 Các vấn đề cần quan tâm 26
2. 5 Tích tụ 26
2. 5. 1Gia tăng kích thước tác vụ 28
2. 5. 2 Duy trì khả năng linh động 30
2. 5. 4 Các vấn đề cần quan tâm 30
2. 6 ánh xạ 31
2. 6. 1 Các giải thuật cân bằng nạp 32
2. 6. 2 Các giải thuật lập lịch trình tác vụ 33
2. 6. 3 Các vấn đề cần quan tâm 34
Chương 3 Mạng kết nối 35
3. 1 Các mạng kết nối thông dụng 35
3. 1. 1 Mạng Mesh 36
3. 1. 2 Mạng busstar/ 36
3. 1. 3 Mạng cây nhị phân 37
3. 1. 4 Mạng Hypertree 37
3. 1. 5 Mạng hình chóp 38
3. 1. 6 Mạng Butterfly 39
3. 1. 7 Mạng Hypercube 39
3. 1. 8 Mạng Cube-Connected Cycles 40
3. 1. 9 Mạng shuffle-exchange 41
3. 1. 10 Mạng de Bruijn 41
3. 2 ánh xạ dữ liệu 42
3. 2. 1 Ring sang 2-D Mesh 44
3. 2. 2 Mesh 2-D sang Mesh 2-D 44
3. 2. 3 Cây nhị phân hoàn chỉnh sang 2D Mesh 45
3. 2. 4 Cây nhị thức sang Mesh2-D 45
3. 2. 5 Nhúng đồ thị vào trong mạng Hypercube 45
3. 2. 6 Cây nhị thức sang Hypercube 46
3. 2. 7 Rings và Meshes sang Hypercube 46
Chương 4 cơ sở đánh giá giải thuật song song 49
4. 1 Thời gian thực hiện 49
4. 1. 1 Thời gian tính toán 50
4. 1. 2 Thời gian truyền thông 50
4. 1. 3 Thời gian rỗi (Idle) 52
4. 2 Tăng tốc và hiệu quả. 52
4. 3 Tính qui mô 53
Chương 5 giải hệ phương trình tuyến tính 55
5. 1 Tách A = LƯ dựa theo giải thuật khử Guassian 55
5. 1. 1 Giải thuật song song theo hàng 59
5. 1. 2 Giải thuật song song theo cột 61
5. 1. 3 Giải thuật song song hai chiều 62
5. 1. 4 Khử Gauss với kỹ thuật lựa chọn phần tử xoay 64
5. 2 Giải hệ phương trình với ma trận hệ số tam giác 64
5. 2. 1 Giải thuật song song tích tụ theo hàng 67
5. 2. 2 Giải thuật song song tích tụ theo cột 70
5. 2. 3 Giải thuật song song hai chiều 72
5. 3 Thực thi giải thuật 74
5. 3. 1 Xây dựng chương trình 74
5. 3. 2 Các kết quả thực hiện Error! Bookmark not defined.
5. 3. 3 Các hạn chế và hướng phát triển chương trình 77
Kết luận 78
Tài liệu tham khảo 79
Mở đầu
M
áy tính điện tử là một trong những phát minh vĩ đại nhất của thế kỷ 20, vừa ra đời sau chiến tranh thế giới hai nhưng nó đã phát triển một cách nhanh chóng và có sức sống mãnh liệt. Trong những thập niên 60, nền tảng để thiết kế máy tính số đều dựa trên mô hình của John von Newman với một đơn vị xử lý được nối với một vùng lưu trữ làm bộ nhớ và tại một thời điểm chỉ có một lệnh máy được thực thi. Kiến trúc truyền thống này ngày có nhiều hạn chế do thúc đẩy của các bài toán xuất phát từ những yêu cầu thực tế và được khoa học hiện nay coi như những thánh thức lớn “grand challenges”, đây là các bài toán đặt ra để mô phỏng thế giới thực của một vấn đề, hiện tượng có yêu cầu về tính toán và khả năng lưu trữ lớn.
Để đáp ứng nhu cầu của khoa học, kiến trúc máy tính cũng thay đổi nhanh chóng nhằm tăng cường sức mạnh tính toán và xử lý theo từng thế hệ. Sức mạnh của máy tính theo kiến trúc John von Newman có thể được cải thiện theo hai xu hướng khác nhau:
- Thứ nhất : Dựa vào sự phát triển của công nghệ
- Thứ hai : Dựa vào sự cải tiến về kiến trúc
Các cải tiến về kiến trúc có thể tăng khối lượng công việc thực hiện cho mỗi chu kỳ lệnh, trong khi tiến bộ về công nghệ có thể giảm thời gian cần thiết cho mỗi chu kỳ lệnh.
Sự cải tiến về công nghệ đã trải qua nhiều giai đoạn phát triển khác nhau và trở thành một chỉ tiêu quan trọng trong khi phân chia các thế hệ máy tính. Từ thế hệ thứ nhất dùng đèn điện tử, thế hệ thứ hai dùng công nghệ bán dẫn, đến thế hệ thứ ba dùng công nghệ mạch tích hợp lớn VLSI
( Very Large Scale Intergrated Circuit). Với công nghệ này, các VLSI có thể tích hợp từ hàng trăm nghìn đến hàng triệu transistors trên một đơn chíp và có thể tạo ra các tần số đồng hồ hàng trăm MHz. Sự cải tiến về mặt công nghệ hy vọng còn tiếp tục phát triển nhờ vào sự tích hợp ngày càng lớn mật độ các thành phần trên một chip, do đó giảm được thời gian trễ vận chuyển giữa các thành phần trên chíp.
Vào giữa thập niên 1970, các tiến bộ kiến trúc quan trọng như bộ nhớ song song bit( bit-parallel memory), số học song song bit ( bit-parallel arithmetic), bộ nhớ truy nhập nhanh (cache memory), pipeline lệnh (instruction pipelining), khối đa chức năng (multiple functional units), pipeline dữ liệu (data pipelining) - đã được kết hợp trong thiết kế máy supercomputer hay mainframe. Từ đó, để năng cao hiệu năng của các bộ xử lý đơn người ta có ý định giảm thời gian chu kỳ lệnh.
Tuy nhiên với công nghệ VLSI kết hợp với những tiến bộ kiến trúc cho phép máy tính đơn có khả năng tính toán cao, thực hiện hàng trăm triệu phép tính trên một giây nhưng điều này vẫn chưa đáp ứng được các thách thức khoa học với các bài toán như mô hình thời tiết và môi trường toàn cầu, tính toán chu trình đại dương. vũ trụ học và thiên văn học, y học và mô hình các xương và cơ quan con người, phản ứng hoá học và hạt nhân. v. v.
Ngày nay, các ứng dụng có tính thương mại đang tác động đến việc phát triển máy tính song song bởi những ứng dụng này yêu cầu xử lý số lượng lớn dữ liệu theo các cách thức phức tạp. Ví dụ như cơ sở dữ liệu song song, khai phá dữ liệu, tìm kiếm dầu mỏ, chuẩn đoán dưới sự trợ giúp của máy tính trong y học, quản lý của các công ty kinh doanh, tổ chức đa quốc gia, công nghệ multimedia và video trên mạng. v. v.
Nguyên nhân chính hạn chế trong việc phát triển máy tính đơn có tốc độ cao là do sự hạn chế vật lý của IC, chúng ta không thể gia tăng mãi khả năng tích hợp các linh kiện bán dẫn trên cùng một chíp và tốc độ truyền tải tín hiệu của mạch điện bị hạn chế không vượt quá tốc độ ánh sáng.
Để tăng cường sức mạnh tính toán giải quyết các bài toán lớn có độ tính toán cao, người ta phát triển theo hướng kiến trúc máy tính, với ý tưởng kết hợp nhiều bộ xử lý vào trong một máy tính mà người ta hay gọi là máy tính song song Multiprocessor hoặc kết hợp sức mạnh tính toán của nhiều máy tính dựa trên kết nối của mạng cục bộ đã có, người ta gọi là máy tính song song Multicomputer. Điều này đã được Daniel Slotnick ở trường đại học Illinois thực hiện với thiết kế hai máy tính song song là máy Solomon được xây dựng bởi công ty Westinghouse Electric Company vào đầu những năm 1960 và sau đó vào đầu những năm 1970, máy tính ILLIAC IV được lắp ráp tại công ty Burroughs Corporation. Tại trường đại học Carnegie-Mellon, hai máy tính song song là C. mmp và Cm* - được xây dựng trong suốt những năm 1970. Trong những năm đầu 1980, các nhà nghiên cứu tại Caltech đã xây dựng ra máy Cosmic Cube, một hình thức sơ khai của máy tính song song Multicomputer.
Sự hội tụ giữa kiến trúc song song và công nghệ xây dựng các máy lớn truyền thống đã dẫn đến sự phát triển các máy tính song song có hàng chục, trăm, hoặc thậm chí hàng nghìn các microprocessor. Với hiệu năng cao nhất, các máy tính song song như Intels’ Paragon XPS/ , MasPars’ MP-2 và Thinking Machines’ Cm 5 , đã vượt qua tốc độ của các máy supercomputer đơn bộ xử lý truyền thống như Cray ÝMP và NEC SX-3 .
Đối với việc xây dựng các máy tính song song có hàng trăm đến hàng ngàn bộ xử lý với bộ nhớ chính có kích thước lớn sẽ rất tốn kém, không hiện thực đối với nhu cầu thực tế nhưng bù lại sẽ có môi trường tính toán ổn định và sức mạnh tính toán lớn. Với máy tính song song kết nối nhiều máy tính sẵn có thông qua mạng cục bộ sẽ đáp ứng được về giá thành, tận dụng được máy tính sẵn có, khả năng lưu trữ dữ liệu sẽ lớn hơn và hiện nay với mạng LAN tốc độ cao sẽ cho phép ta thực hiện được điều này. Tuy nhiên với môi trường tính toán không đồng nhất về tốc độ xử lý trên mỗi máy tính, khả năng lưu trữ. . sẽ làm cho việc thực hiện bài toán trở nên khó khăn. Để giải quyết vấn đề này các phần mềm được xây dựng ra như PVM ( Parallel Virtual Machine ), MPI, Linda, P4, . v. v. cho phép thực thi song song bài toán trên mô hình Multicomputer.
Ngoài việc có sức mạnh tính toán nhanh, máy tính song song có khả năng lưu trữ lớn với mô hình bộ nhớ phân tán và khả năng chịu hỏng tốt hơn máy tính đơn bộ xử lý. Đối với máy tính đơn, khi bộ xử lý bị sự cố thì cả hệ thống dừng hoạt động còn các máy tính song song vẫn có thể thực hiện công việc khi một vài bộ xử lý hay máy tính có sự cố. Việc bảo đảm độ tin cậy cao có tầm quan trọng khi sử dụng máy tính trong các lĩnh vực mà sự cố có thể xảy ra thảm hoạ như điều khiển phóng vệ tinh, kiểm soát và điều khiển các nhà máy điện nguyên tử. . v. v.
Tuy nhiên, để khai thác được sức mạnh tiềm tàng trong các máy tính song song lớn yêu cầu sự phát triển và kết hợp hợp lý của kiến trúc, hệ điều hành, ngôn ngữ lập trình và giải thuật, phần mềm tính toán song song. Bởi vì giải thuật tuần tự không còn phù hợp nữa khi thực hiện trên máy song song, nên việc xây dựng, thiết kế giải thuật song song là điều quan trọng từ đó có thể phân rã công việc trên các phần tử xử lý khác nhau. Việc phân rã có thể được tiến hành theo hai cách, phân rã theo miền và phân rã theo chức năng. Tiếp theo là mã hoá công việc đó theo một ngôn ngữ hỗ trợ việc tính toán song song và hệ điều hành điều khiển hoạt động tính toán phải có sự hỗ trợ. Nếu trong quá trình tính toán mà lựa chọn không tốt kiến trúc song song sẽ làm cho hiệu quả thực hiện giảm đi.
Để xây dựng một giải thuật song song ta phải có sự phân tích bài toán hoặc giải thuật tuần tự, từ đó cho phép ta có kết luận có thể song song bài toán hay không. Nếu được, ta sẽ tiếp tục xây dựng giải thuật bằng cách phân rã bài toán ra thành các công việc nhỏ, xây mối liên hệ giữa các công việc, quyết định được có thể song song được những tác vụ nào, sau đó ấn định vào mô hình máy tính song song cụ thể. Trong khi xây dựng có thể có nhiều phương hướng thiết kế khác nhau tạo ra các giải thuật khác nhau. Việc đánh giá hiệu quả của từng giải thuật cho phép ta quyết định giải thuật nào sẽ được áp dụng dựa trên mô hình hiệu năng. Để đánh giá tốt hiệu quả giải thuật, chúng ta cần xem xét các chỉ tiêu như tốc độ ( Speedup), hiệu quả (Efficiency), linh động ( Scalability). Điều này cần có kiến thức về tính toán độ phức tạp giải thuật, tổ chức mạng kết nối giữa các phần tử xử lý, chi phí truyền thông giữa các phần tử trong giải thuật.
Những vấn đề này sẽ được đề cập trong đồ án tốt nghiệp với mong ước góp phần nhỏ bé của mình vào việc phát triển nghiên cứu về lĩnh vực tính toán song song. Đề tài cho đồ án tốt nghiệp là : “ Thiết kế giải thuật song song”
Nhiệm vụ của đồ án bao gồm:
1. Tìm hiểu kỹ thuật tổ chức giải thuật tính toán song song.
2. Nghiên cứu các vấn đề liên quan đến phương pháp phân rã bài toán, phục vụ cho việc xây dựng giải thuật song song và đánh giá được các phương pháp phân rã.
3. áp dụng cho bài toán giải hệ phương trình tuyến tính bằng phương pháp phân rã LU. Đưa ra các giải thuật song song cho bài toán và đánh giá hiệu quả của các giải thuật.
4. Mô phỏng một số giải thuật phân rã bài toán giải hệ phương trình tuyến tính.
Nội dung của đồ án tốt nghiệp gồm 5 chương và tài liệu tham khảo.
Chương 1 sẽ đề cập tổng quan về tính toán song song với các vấn đề liên quan đến việc thiết kế giải thuật song song như các mô hình tính toán song song, kiến trúc bộ nhớ máy tính song song, các mô hình lập trình song song.
Chương 2 đề cập đến mô hình thiết kế giải thuật, các công đoạn trong quá trình thiết kế. Trong mỗi công đoạn sẽ đưa ra được những vấn đề cần quan tâm cho người thiết kế.
Chương 3 sẽ đề cập đến mạng kết nối giữa các bộ xử lý và đi sâu vào vấn đề ánh xạ tĩnh các tác vụ phân rã theo miền vào kiến trúc máy tính song song cụ thể.
Chương 4 đề cập đến mô hình hiệu năng đánh giá hiệu quả của giải thuật song song sau khi thiết kế và phân tích tính qui mô của giải thuật. Những đánh giá này sẽ giúp cho người thiết kế có khả năng chọn lựa giải thuật trong công đoạn thiết kế.
Chương 5 sẽ đi sâu thiết kế giải thuật song song cho bài toán giải hệ phương trình tuyến tính theo phương pháp tách LU. Mô phỏng một số giải thuật và thử nghiệm một số bài toán giải hệ.
80 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2353 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Thiết kế giải thuật song song, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
xö lý trªn m¸y ®Ých.
HiÖu n¨ng cña gi¶i thuËt cã thÓ gi¶m ®i khi ®å thÞ gi¶i thuËt kh«ng lµ ®å thÞ con cña ®å thÞ con cña tæ chøc bé xö lý. LÊy vÝ dô nh, gi¶ sö chóng ta thùc thi gi¶i thuËt song song trªn m« h×nh multicomputer sö dông kü thuËt ®Þnh ®êng store and forward vµ hai ®Ønh kÕt nèi trong ®å thÞ gi¶i thuËt ¸nh x¹ sang hai nót xa nhau (H×nh a ).
Khi truyÒn mét message tõ mét bé xö lý tíi bé xö lý kh¸c sÏ yªu cÇu thêi gian xÊp xØ gÊp hai lÇn thêi gian truyÒn gi÷a hai bé xö lý c¹nh nhau hoÆc gi¶ sö chóng ta thùc thi mét gi¶i thuËt song song trªn m« h×nh multicomputer víi kü thuËt chuyÓn m¹ch vµ c¸c ®Ønh kh¸c nhau trong ®å thÞ gi¶i thuËt ¸nh x¹ sang mét liªn kÕt chung trªn m¸y ( H×nh b).
NÕu truyÒn th«ng ®ång thêi x¶y ra gi÷a hai cÆp nót th× tèc ®é truyÒn th«ng sÏ bÞ ¶nh hëng kh«ng tèt khi dïng chung cïng kÕt nèi. Trªn mét vµi hÖ thèng, mét message sÏ bÞ kho¸ tËn ®Õn khi message kh¸c kÕt thóc viÖc truyÒn cßn trªn c¸c hÖ thèng kh¸c th× kÕt nèi vËt lý sÏ bÞ dån l¹i gi÷a hai kÕt nèi ¶o, c¾t mét nöa b¨ng th«ng cña mçi kÕt nèi. Trong trêng hîp nµy, hiÖu n¨ng sÏ gi¶m thÊp ®i bëi v× mét message kh«ng ®îc sö dông riªng mét ®êng truyÒn th«ng.
H×nh (b)
H×nh (a)
§Þnh nghÜa : Gi¶ sö lµ hµm nhóng (embedding ) ®å thÞ G=(V, E) vµo trong ®å thÞ G(V, E). Dilation cña hµm nhóng ®îc ®Þnh nghÜa nh sau: dil() = max { dist((u), (v)) | (u, v) E} víi dist(a, b) lµ kho¶ng c¸ch gi÷a hai ®Ønh a vµ b trong ®å thÞ G. Víi V, V lµ tËp c¸c ®Ønh E, E lµ tËp c¸c c¹nh cña G vµ G.
VÝ dô : Dilation =1 nÕu G lµ ®å thÞ con cña G.
G
G
Load (N¹p t¶i) cña hµm : G G lµ sè ®Ønh lín nhÊt trong V ®îc ¸nh x¹ sang mét ®Ønh ®¬n trong V.
Congestion ( Sù t¾c nghÏn) cña hµm : G G lµ sè c¹nh lín nhÊt trong E ®îc ¸nh x¹ sang mét ®Ønh ®¬n trong E.
Ta ®Òu mong muèn cã thÓ ®¹t ®îc Dilation, Load, Congestion ®Òu b»ng 1, tuy nhiªn ®iÒu lý tëng nµy khã cã thÓ ®¹t ®îc trong thùc tÕ.
§Ó tèi u viÖc ¸nh x¹ cña ®å thÞ t¸c vô bÊt kú vµo trong kiÕn tróc m¸y ®Ých bÊt kú lµ bµi to¸n khã cã thÓ gi¶i quyÕt ®îc ( cã ®é phøc t¹p thêi gian lµ NP- complete).
Do ®ã ë ®©y ta chØ xem xÐt bèn ®å thÞ gi¶i thuËt quan träng lµ c©y nhÞ ph©n hoµn chØnh, c©y nhÞ thøc( Binomial Tree), Ring vµ Mesh sang m¹ng bé xö lý thêng ®îc øng dông lµ Mesh hai chiÒu vµ Hypercube.
3. 2. 1 Ring sang 2-D Mesh
Ring ®îc g¾n vµo trong ®å thÞ Mesh 2-D. Gi¶ sö hai ®å thÞ cã cïng sè ®Ønh. Khi ®ã, viÖc nhóng víi dilation =1 sÏ tån t¹i nÕu mesh cã sè ch½n c¸c hµng. NÕu mesh cã sè lÎ hµng, cét th× kh«ng cã c¸ch nµo ®Ó nhóng Ring vµo trong Mesh mµ kh«ng t¨ng dilation.
H×nh 3. 11 Nhóng Ring vµo trong Mesh 2-D
3. 2. 2 Mesh 2-D sang Mesh 2-D
Mét Mesh 2-D cña ®å thÞ gi¶i thuËt cã thÓ chuyÓn sang Mesh 2-D cña ®å thÞ trªn kiÕn tróc ®Ých víi dilation= 1 nÕu (1) A M vµ A M hoÆc (2) A M vµ A M. víi A, A lµ sè hµng, cét cña ®å thÞ gi¶i thuËt, M, Mlµ sè hµng cét cña ®å thÞ Mesh 2-D.
H×nh 2. 12 M« t¶ chuyÓn Mesh 2-D sang Mesh 2-D víi dialtion-1
3. 2. 3 C©y nhÞ ph©n hoµn chØnh sang 2D Mesh
C©y nhÞ ph©n hoµn chØnh trong ®å thÞ gi¶i thuËt cã chiÒu cao n cã dilation = khi chuyÓn vµo kiÕn tróc ®Ých 2D Mesh.
H×nh 2. 13 ChuyÓn c©y nhÞ ph©n chiÒu cao 3 vµo Mesh 2-D víi dilation=1
3. 2. 4 C©y nhÞ thøc sang Mesh2-D
C©y nhÞ thøc (Binimial Tree) trong ®å thÞ gi¶i thuËt cã chiÒu cao n, cã dilation = khi chuyÓn vµo ®å thÞ Mesh 2-D trong kiÕn tróc ®Ých.
H×nh 2. 14 ChuyÓn c©y nhÞ thøc chiÒu cao 4 vµo Mesh 2-D víi dilation=1
3. 2. 5 Nhóng ®å thÞ vµo trong m¹ng Hypercube
Mét ®å thÞ G lµ cã tÝnh h×nh khèi nÕu ta cã thÓ nhóng G vµo trong m¹ng hypercube víi dilation=1. Bµi to¸n x¸c ®Þnh mét ®å thÞ bÊt kú G cã tÝnh h×nh khèi hay kh«ng cã ®é phøc t¹p NP-complete.
Tuy nhiªn, bµi to¸n nhóng cña mét ®å thÞ kÕt nèi G vµo trong mét m¹ng hypercube víi n nót tån t¹i khi vµ chØ khi cã thÓ g¸n nh·n c¸c c¹nh cña G theo c¸c sè nguyªn {1, . . . . , n} nh sau:
C¸c c¹nh g¾n liÒn víi mét ®Ønh chung cã c¸c nh·n kh¸c nhau
Trong mçi ®êng cña G, Ýt nhÊt ph¶i cã mét nh·n xuÊt hiÖn sè lÎ lÇn
4
2
1
4
(a)
2
1
1
2
1
3
(b)
(c)
Trong mçi chu tr×nh cña G kh«ng cã nh·n ®îc g¸n lÎ lÇn.
H×nh 2. 15 M« t¶ c¸c trêng hîp kh«ng thÓ nhóng G vµo hypercube víi dilation=1
3. 2. 6 C©y nhÞ thøc sang Hypercube
C©y nhÞ thøc chiÒu cao n cã thÓ ®îc chuyÓn vµo ®å thÞ hypercube cã n chiÒu víi dilation =1.
H×nh 2. 16 §¸nh sè c¸c c¹nh cña c©y nhÞ thøc chiÒu cao 4, cã thÓ chuyÓn vµo Hypercube cã 4 chiÒu víi dilation-1
3. 2. 7 Rings vµ Meshes sang Hypercube
Gi¶ sö hypercube cã p = 2 bé xö lý. Gi¶ sö G(i) lµ sè hiÖu bé xö lý g¸n cho vÞ trÝ vßng thø i, víi 0 i < p. ViÖc m· ho¸ G(i) ph¶i cã c¸c tiªu chuÈn sau:
C¸c gi¸ trÞ ph¶i duy nhÊt, cã nghÜa lµ G(i) = G(j) i = j
G(i) vµ G(i+1) ph¶i kh¸c nhau chØ 1 bÝt, víi tÊt c¶ i: 0 i < p-1
G(p-1) vµ G(0) ph¶i kh¸c nhau chØ 1 bÝt
C¸c tiªu chuÈn nµy thiÕt lËp lªn ®Þnh nghÜa cña m· Gray ( gray code). Cã nhiÒu c¸c x©y dùng m· Gray, ë ®©y ta tr×nh bµy x©y dùng m· Gray dµi h¬n tõ m· Gray ng¾n h¬n. Mét m· bÝt Gray lµ { 0, 1}, tøc lµ G(0) = 0 vµ G(1) = 1. Gi¶ sö ta cã m· Gray d bÝt, m· Gray (d+1) bÝt cã thÓ ®îc x©y dùng bëi liÖt kª m· Gray d bit víi tiÒn tè lµ 0, tiÕp theo tiÒn tè lµ 1. Sö dông kü thuËt nµy chóng ta x©y dùng m· Gray 2 bÝt nh sau.
01 11 10
Tõ m· Gray 2 bÝt ta x©y dùng m· Gray 3 bÝt nh sau:
000 001 011 010 110 111 101 100
M· Gray ngîc ®îc ®Þnh nghÜa nh sau ; G(i) = j khi vµ chØ khi G(j) =i Chóng ta sö dông c¶ m· Gray vµ m· Gray ngîc ®Ó chuyÓn ®å thÞ Ring vµ Mesh vµo trong hypercube
VÝ dô nh, hµm díi ®©y ®Þnh nghÜa bé xö lý kÕt tiÕp cña bé xö lý i trªn ®å thÞ ring cã 2 nót. lµ :
Successor (i) = 0 nÕu i = 2
Successor (i) = G(G(i) + 1) trong trêng hîp cßn l¹i.
C¸c hµm viÕt theo ng«n ng÷ C tÝnh to¸n G(i) vµ G(i) nh sau:
/* i lµ vÞ trÝ vßng, hµm Gray sÏ ®a ra sè hiÖu bé xö lý chiÕm gi÷ vÞ trÝ nµy */
int gray(i)
{
return ( i ^( i/2));
}
/ * TruyÒn vµo sè hiÖu bé xö lý i, hµm gray-inverse sÏ tÝnh vÞ trÝ cña bé xö lý nµy trong d·y m· Gray*/
int gray-inverse(i)
{
int answer, mask;
answer = i;
mask = answer /2;
while ( mask > 0)
{
answer = answer ^ mask ;
mask = mask /2;
}
return ( answer);
}
H×nh 2. 17 Nhóng ®å thÞ Ring 8 nót vµo m¹ng hypercube cã 8 bé xö lý
B©y giê ta ¸nh x¹ ®å thÞ mesh nhiÒu chiÒu cã c¸c kÕt nèi vßng l¹i vµo trong hypercube. Sö dông m· Gray, víi ®iÒu kiÖn kÝch thíc trong mçi chiÒu ph¶i lµ luü thõa cña 2. Mçi chiÒu cña ®å thÞ mesh sÏ ®îc g¸n mét sè lîng bit chÝnh x¸c trong chuçi m· ho¸. DuyÖt c¸c nót ®å thÞ mesh däc theo chiÒu nµy sÏ ®îc mét vßng trßn. M· Gray x¸c ®Þnh c¸c gi¸ trÞ g¸n cho trêng bit.
VÝ dô, xem xÐt ¸nh x¹ ®å thÞ mesh 4 8 trong ®å thÞ hypercube 32 bÝt. Hai bÝt ®îc dµnh ®Ó m· ho¸ hµng vµ 3 bÝt ®Ó m· ho¸ cét. M· gray cho ¸nh x¹ ®å thÞ mesh kÝch thíc 4 8 vµo trong ®å thÞ hypercube 32 nót nh sau:
00000 00001 00011 00010 00110 00111 00101 00100
01000 01001 01011 01010 01110 01111 01101 01100
11000 11001 11011 11010 11110 11111 11101 11100
10000 10001 10011 10010 10110 10111 10101 10100
H×nh 2. 18 Nhóng ®å thÞ Mesh 44 vµo m¹ng hypercube 4 chiÒu víi dilation =1 bëi v× mesh lµ ®å thÞ con cña hypercube.
BÊt kú ®å thÞ mesh víi n ®Ønh cã thÓ ®îc chuyÓn vµo trong ®å thÞ hypercube cã chiÒu víi dilation=2.
Ch¬ng nµy ®· t×m hiÓu vÒ kiÕn tróc c¸c m¹ng kÕt nèi vµ ®¸nh gi¸ ¶nh hëng cña m¹ng ®Õn ®é trÔ vµ b¨ng th«ng trong chi phÝ thêi gian truyÒn th«ng, còng nh viÖc ¸nh x¹ tÜnh tõ ®å thÞ t¸c vô vµo trong kiÕn tróc m¹ng kÕt nèi. Nh÷ng vÊn ®Ò nµy sÏ ¶nh hëng ®Õn chi phÝ truyÒn th«ng trong c¸c tiªu chuÈn ®¸nh gi¸ gi¶i thuËt.
Ch¬ng 4 c¬ së ®¸nh gi¸ gi¶i thuËt song song
Qu¸ tr×nh thiÕt kÕ t¹o ra nhiÒu gi¶i thuËt song song cho bµi to¸n, viÖc chän ra mét gi¶i thuËt tèi u cÇn ph¶i dùa vµo mét sè tiªu chuÈn ®¸nh gi¸. C¸c tiªu chuÈn ®ã lµ : Thêi gian thùc hiÖn, kh¶ n¨ng t¨ng tèc, hiÖu qu¶ vµ tÝnh qui m« cña gi¶i thuËt.
4. 1 Thêi gian thùc hiÖn
Khi tèc ®é tÝnh to¸n ®îc coi lµ nguyªn nh©n chñ yÕu cña sù quan t©m trong viÖc x©y dùng c¸c m¸y tÝnh song song, mét ®é ®o quan träng trong viÖc ®¸nh gi¸ lµ thêi gian thùc hiÖn. Nã ®îc x¸c ®Þnh nh lµ thêi gian gi¶i thuËt yªu cÇu ®Ó gi¶i quyÕt mét vÊn ®Ò trªn m¸y tÝnh song song, ®ã lµ kho¶ng thêi gian kÓ tõ thêi ®iÓm ban ®Çu ®Õn thêi ®iÓm kÕt thóc. NÕu c¸c bé xö lý kh¸c nhau, tÊt c¶ kh«ng b¾t ®Çu vµ kÕt thóc ®ång thêi, khi ®ã thêi gian thùc hiÖn b»ng thêi gian kÐo dµi gi÷a thêi ®iÓm bé xö lý ®Çu tiªn b¾t ®Çu tÝnh to¸n ®Õn thêi ®iÓm bé xö lý cuèi cïng kÕt thóc tÝnh to¸n.
Tríc khi thùc sù cµi ®Æt mét gi¶i thuËt song song hay tuÇn tù ®Òu cã sù ph©n tÝch vÒ lý thuyÕt, gi¶i thuËt cÇn bao nhiªu thêi gian ®Ó gi¶i quyÕt vÊn ®Ò tÝnh to¸n ®· cho. §iÒu nµy thêng ®îc thùc hiÖn b»ng c¸ch tÝnh sè c¸c thao t¸c c¬ b¶n hoÆc c¸c bíc mµ gi¶i thuËt thùc hiÖn trong trêng hîp xÊu nhÊt. Sè c¸c bíc nh thÕ lµ mét hµm cña kÝch thíc ®Çu vµo ( input size ). C¸c thao t¸c c¬ b¶n cã thÓ lµ phÐp céng, so s¸nh hoÆc ®æi chç, truyÒn d÷ liÖu. Mçi thao t¸c nh vËy yªu cÇu mét sè cè ®Þnh c¸c ®¬n vÞ thêi gian trªn m¸y tÝnh ®¬n bé xö lý truyÒn thèng.
Kh¸c víi gi¶i thuËt tuÇn tù, thêi gian thùc hiÖn cña gi¶i thuËt song song lµ hµm phô thuéc vµo nhiÒu tham sè nh kÝch thíc bµi to¸n N, sè bé xö lý, sè t¸c vô U vµ c¸c ®Æc ®iÓm vÒ gi¶i thuËt vµ phÇn cøng kh¸c.
NÕu gäi T lµ thêi gian thùc hiÖn song song th× T= f( N, U, P, . . . )
Trong suèt thêi gian thùc hiÖn, mçi bé xö lý sÏ ®ang tÝnh to¸n, truyÒn th«ng hoÆc r¶nh rçi.
T = ( T + T + T) /p.
Trong ®ã :
T lµ tæng thêi gian tÝnh to¸n
T lµ tæng thêi gian truyÒn th«ng
T lµ tæng thêi gian rçi.
P lµ sè bé xö lý
H×nh 3. 1 M« t¶ qu¸ tr×nh tÝnh to¸n cña 8 bé xö lý
4. 1. 1 Thêi gian tÝnh to¸n
Thêi gian tÝnh to¸n cña gi¶i thuËt song song lµ thêi gian dµnh ®Ó thùc hiÖn tÝnh to¸n. §èi víi gi¶i thuËt tuÇn tù th× thêi gian nµy chØ phô thuéc vµo kÝch thíc cña bµi to¸n nhng víi tÝnh to¸n song song th× viÖc tÝnh to¸n lÆp trªn c¸c t¸c vô cã thÓ cã. Do ®ã thêi gian tÝnh to¸n sÏ phô thuéc vµo sè t¸c vô thùc hiÖn. §èi víi m« h×nh bé nhí chung th× sè lîng bé xö lý còng ¶nh hëng ®Õn tèc ®é thùc thi trªn mçi bé xö lý.
Th«ng thêng ta cã thÓ x¸c ®Þnh b»ng thêi gian thùc hiÖn tuÇn tù céng víi bÊt kú thêi gian nµo thªm vµo do thùc hiÖn song song. Ch¼ng h¹n nh thêi gian tÝnh to¸n lÆp l¹i cïng mét c«ng viÖc trªn c¸c t¸c vô.
4. 1. 2 Thêi gian truyÒn th«ng
Thêi gian truyÒn th«ng cña mét gi¶i thuËt lµ thêi gian c¸c t¸c vô dµnh ®Ó göi vµ nhËn message. Cã hai lo¹i truyÒn th«ng cÇn x¸c ®Þnh : truyÒn th«ng gi÷a hai t¸c vô trªn hai bé xö lý kh¸c nhau vµ truyÒn th«ng gi÷a hai t¸c vô cïng n»m trªn cïng bé xö lý. Th«ng thêng thêi gian truyÒn bªn trong bé xö lý lín h¬n nhiÒu so víi thêi gian truyÒn gi÷a hai bé xö lý, nhÊt lµ ®èi víi m« h×nh m¸y tÝnh song song multicomputers.
Trong m« h×nh multicomputers lý tëng th× chi phÝ ®Ó göi mét message gi÷a hai t¸c vô ®Þnh vÞ trªn bé xö lý kh¸c nhau phô thuéc vµo hai tham sè sau :
Thêi gian khëi t¹o message: t lµ thêi gian cÇn thiÕt ®Ó khëi t¹o truyÒn th«ng
Thêi gian truyÒn d÷ liÖu: t lµ thêi gian cÇn thiÕt ®Ó truyÒn ®i d÷ liÖu cã kÝch thíc mét word ( 2 byte). t ®îc x¸c ®Þnh bëi b¨ng th«ng vËt lý cña kªnh truyÒn th«ng kÕt nèi bé xö lý nguån vµ ®Ých.
C«ng thøc tÝnh thêi gian göi message cã kÝch thíc L (®¬n vÞ lµ word) lµ:
T = t + L t w
NÕu lîng d÷ liÖu truyÒn lµ nhá th× thêi gian khëi t¹o chiÕm phÇn lín, cßn khi lîng d÷ liÖu lín th× thêi gian truyÒn sÏ chiÕm tû träng cao.
H×nh 3. 2 M« t¶ mèi quan hÖ c¸c tham sè trong c«ng thøc tÝnh
thêi gian truyÒn th«ng
Th«ng thêng ts vµ tw lµ c¸c th«ng sè ®îc tÝnh to¸n phô thuéc vµo cô thÓ kiÕn tróc m¸y tÝnh song song.
H×nh 3. 3 B¶ng xÊp xØ th«ng sè mét sè m¸y tÝnh song song ( ®¬n vÞ : ms)
Tuy nhiªn ®èi víi m« h×nh multicomputer thùc tÕ, ta cÇn ph©n tÝch sù ¶nh hëng cña hai kü thuËt ®Þnh ®êng truyÒn th«ng lµ store and forward vµ circuit-switched còng nh ¶nh hëng cña tranh chÊp b¨ng th«ng trªn ®êng truyÒn gi÷a c¸c bé xö lý.
Trong s¬ ®å cña c¬ chÕ store and forward, thêi gian cÇn thiÕt ®Ó göi mét message tõ mét bé xö lý tíi mét bé xö lý kh¸c t¨ng tuyÕn tÝnh víi sè bíc nh¶y ( hops) mµ message ph¶i t¹o ra ®Ó ®Õn ®îc ®Ých. Ngîc l¹i, thêi gian cÇn thiÕt ®Ó göi mét message tõ mét bé xö lý tíi mét bé xö lý kh¸c trong lîc ®å chuyÓn m¹ch lµ phô thuéc rÊt Ýt víi kho¶ng c¸ch gi÷a c¸c bé xö lý.
Do ®ã ta cã thÓ ph¸t triÓn thµnh c¸c c«ng thøc sau :
§èi víi truyÒn th«ng ®Þnh ®êng theo c¬ chÕ store and forward:
Tmsg = ( ts + tw L) D
Víi D lµ kho¶ng c¸ch gi÷a nót nhËn vµ göi trong bíc ®Þnh ®êng.
§èi víi truyÒn th«ng ®Þnh ®êng theo c¬ chÕ circuit-switched:
Tmsg = ts + tw L – th D
Víi D lµ kho¶ng c¸ch gi÷a nót nhËn vµ göi trong bíc ®Þnh ®êng
Th lµ chi phÝ gia t¨ng cho mçi bíc ®Þnh ®êng.
Trong thùc tÕ, th thêng rÊt nhá, ta cã thÓ bá qua ®îc.
Khi xem xÐt ®Õn sù tranh chÊp b¨ng th«ng truyÒn trªn m¹ng kÕt nèi th× c«ng thøc tÝnh ®îc thay ®æi nh sau:
Tmsg = ts + tw S L
Trong ®ã S lµ sè bé xö lý göi ®ång thêi trªn cïng mét ®êng d©y.
4. 1. 3 Thêi gian rçi (Idle)
Thêi gian tÝnh to¸n vµ truyÒn th«ng thêng ®¬n gi¶n h¬n trong viÖc x¸c ®Þnh bëi v× ta cã thÓ x¸c ®Þnh sù ph©n bè cña nã ®èi víi thêi gian thùc hiÖn. Thêi r¶nh rçi khã cã thÓ x¸c ®Þnh bëi v× phô thuéc vµo tr×nh tù c¸c phÐp ®îc thùc hiÖn.
Mét bé xö lý cã thÓ ®Æt trong tr¹ng th¸i rçi nÕu thiÕu tÝnh to¸n hoÆc d÷ liÖu ®Ó tÝnh to¸n. Trong trêng hîp ®Çu tiªn, thêi gian r¶nh rçi cã thÓ tr¸nh ®îc b»ng c¸ch sö dông kü thuËt c¨n b»ng n¹p ®éng. Trong trêng hîp thø hai, bé xö lý rçi trong khi tÝnh to¸n ®ang chê d÷ liªu d÷ liÖu tõ xa mµ d÷ liÖu nµy l¹i ®ang trong tr¹ng th¸i sö dông. Thêi nµy cã thÓ ®îc tr¸nh nÕu ta cÊu tróc ch¬ng tr×nh ®Ó cã thÓ thùc tÝnh to¸n hoÆc truyÒn th«ng trong khÝ ®ang chê d÷ liÖu tõ xa. Kü thuËt nµy thêng ®îc gäi lµ xen kÏ tÝnh to¸n vµ truyÒn th«ng ( overlapping computation and communication) bëi v× tÝnh to¸n víi d÷ liÖu côc bé ®îc thùc hiÖn ®ång thêi víi tÝnh to¸n vµ truyÒn th«ng d÷ liÖu xa.
C¸ch ®¬n gi¶n ®Ó ®¹t ®îc ®iÒu nµy lµ t¹o ra nhiÒu t¸c vô trªn mét bé xö lý. Trong khi mét t¸c vô ®ang bÞ dïng ®Ó chê d÷ liÖu ë xa th× tÝnh to¸n cã thÓ chuyÓn sang t¸c vô kh¸c mµ d÷ liÖu ®· s½n cã.
H×nh 3. 4 M« t¶ kü thuËt xen kÏ tÝnh to¸n vµ truyÒn th«ng gi÷a P1 vµ P2.
HÇu hÕt c¸c m¸y tÝnh song song ®Òu hç trî thùc hiÖn kü thuËt lËp lÞch tr×nh, xen kÏ tÝnh to¸n vµ truyÒn th«ng do ®ã thêi gian rçi chiÕm tû träng rÊt nhá trong toµn bé thêi gian tÝnh to¸n, nªn th«ng thêng cã thÓ bá qua ®îc.
4. 2 T¨ng tèc vµ hiÖu qu¶.
Thêi gian thùc hiÖn kh«ng lu«n lµ thíc ®o thuËn tiªn nhÊt ®Ó ®¸nh gi¸ hiÖu n¨ng cña gi¶i thuËt. Khi thêi gian thùc hiÖn cã xu híng biÕn ®æi theo kÝch thíc bµi to¸n, thêi gian thùc hiÖn ph¶i ®îc tiªu chuÈn ho¸ khi so s¸nh hiÖu n¨ng gi¶i thuËt víi kÝch thíc bµi to¸n kh¸c nhau.
HiÖu qu¶ cña gi¶i thu©t ®îc ®Þnh nghÜa lµ phÇn thêi gian mµ c¸c bé xö lý dïng ®Ó thùc hiÖn c«ng viÖc cã Ých, chØ ra møc ®é hiÖu qu¶ cña mét gi¶i thuËt khi sö dông c¸c tµi nguyªn tÝnh to¸n cña mét m¸y tÝnh song song theo híng ®éc lËp víi kÝch thíc bµi to¸n, ®îc x¸c ®Þnh theo c«ng thøc sau:
Ep =
Víi T1 lµ thêi gian thùc hiÖn gi¶i thuËt tuÇn tù.
Tp lµ thêi gian thùc hiÖn gi¶i thuËt song song
Ep lµ hiÖu qu¶ gi¶i thuËt
p lµ sè bé xö lý
Th«ng thêng, Ep 1.
Mét ®é ®o kh¸c ®¸nh gi¸ ®îc hiÖu n¨ng cña gi¶i thuËt lµ kh¶ n¨ng t¨ng tèc, ®©y lµ hÖ sè mµ thêi gian thùc hiÖn ®îc gi¶m ®i khi thùc hiÖn bµi to¸n trªn p bé xö lý. §îc x¸c ®Þnh theo c«ng thøc sau:
Sp =
Víi Sp lµ kh¶ n¨ng t¨ng tèc
T1 lµ thêi gian thùc hiÖn gi¶i thuËt tuÇn tù.
Tp lµ thêi gian thùc hiÖn gi¶i thuËt song song
HÇu hÕt c¸c trêng hîp th× Sp p.
Râ rµng kh¶ n¨ng t¨ng tèc cµng lín th× gi¶i thuËt song song cµng tèt.
Tuy nhiªn n¨m 1967 Amdahl ®· ®a ra luËt vÒ giíi h¹n kh¶ n¨ng t¨ng tèc nh sau:
LuËt Amdahl : Gi¶ sö s lµ phÇn thao t¸c tÝnh to¸n cÇn ph¶i thùc hiÖn tuÇn tù, trong ®ã 0 s 1. Kh¶ n¨ng t¨ng tèc tèi ®a Sp ®¹t ®îc bëi mét m¸y tÝnh song song cã P bé xö lý thùc hiÖn tÝnh to¸n lµ :
Sp
LuËt trªn ®· sím ®em l¹i sù bi quan vÒ mét tiÒm n¨ng cña tÝnh to¸n song song. Tuy nhiªn nÕu ta më réng vÊn ®Ò ra cã thÓ thÊy luËt Amdahl thÝch hîp chØ ®èi víi bµi to¸n cè ®Þnh hoÆc phÇn tr¨m tuÇn tù lµ ®éc lËp víi kÝch thíc bµi to¸n. §iÒu nµy thêng Ýt gÆp trong thùc tÕ v× c¸c bµi to¸n gi¶i quyÕt song song thêng lín, khi ®ã phÇn tÝnh to¸n tuÇn tù sÏ gi¶m xuèng khi kÝch thíc t¨ng.
4. 3 TÝnh qui m«
Mét gi¶i thuËt cã tÝnh qui m« nÕu møc ®é song song Ýt nhÊt còng gia t¨ng tuyÕn tÝnh theo kÝch thíc bµi to¸n. Mét kiÕn tróc cã tÝnh qui m« nÕu nã tiÕp tôc mang l¹i cïng hiÖu n¨ng cho tõng bé xö lý, mÆc dï c¸c bé xö lý ®îc dïng trong bµi to¸n kÝch thíc lín h¬n, khi sè lîng bé xö lý gia t¨ng. TÝnh qui m« vÒ thuËt to¸n vµ kiÕn tróc lµ quan träng, bëi v× tõ ®ã míi cã thÓ cho phÐp ngêi sö dông gi¶i quyÕt c¸c bµi to¸n lín h¬n trong sè lîng thêi gian nh nhau b»ng c¸ch mua mét m¸y tÝnh song song víi nhiÒu bé xö lý h¬n.
ViÖc ®¸nh gi¸ tÝnh qui m« cña gi¶i thuËt thêng th«ng qua mét tiªu chuÈn phô thuéc vµo tÝnh hiÖu qu¶. NÕu nh gi¶i thuËt cã thÓ duy tr× hiÖu qu¶ lµ mét h»ng sè hoÆc Ýt nhÊt lµ giíi h¹n díi > 0 khi sè bé xö lý gia t¨ng do kÝch thíc bµi to¸n t¨ng lªn. Theo c«ng thøc tÝnh hiÖu qu¶:
Ep =
§Ó duy tr× Ep lµ h»ng sè khi T1 cÇn ph¶i tû lÖ víi pTp.
C¸c gi¶i thuËt song song theo d÷ liÖu th× linh ®éng h¬n c¸c gi¶i thuËt song song theo chøc n¨ng, bëi v× møc ®é song song chøc n¨ng thêng lµ mét h»ng sè, ®éc lËp víi kÝch thíc bµi to¸n, trong khi møc ®é song song d÷ liÖu lµ mét hµm t¨ng theo kÝch thíc bµi to¸n.
ViÖc t×m hiÓu c¸c c¬ së ®¸nh gi¸ gi¶i thuËt gióp cho ta cã thÓ xem xÐt l¹i c¸c thiÕt kÕ ®a ra. Chän lùa gi¶i thuËt tèt cho m« h×nh m¸y tÝnh cô thÓ lµ mét bµi to¸n kh«ng ®¬n gi¶n. Nh÷ng ®¸nh gi¸ trªn míi chØ mang tÝnh lý thuyÕt, nhng lµ c¬ së quan träng khi ta thiÕt kÕ gi¶i thuËt song song.
Ch¬ng 5 gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh
Sau khi tr×nh bµy lý thuyÕt vÒ thiÕt kÕ gi¶i thuËt song song, ch¬ng sau ®©y sÏ ¸p dông cô thÓ vµo bµi to¸n gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh. §©y lµ bµi to¸n quan träng, thêng ®îc ¸p dông trong nhiÒu bµi to¸n khoa häc vµ kü thuËt.
VÒ lý thuyÕt, gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh A x= b ta cã thÓ thùc hiÖn nh sau:
T×m ma trËn nghÞch ®¶o A cña A
Sau ®ã tÝnh x= Ab.
Tuy nhiªn, trong thùc tÕ viÖc tÝnh ma trËn nghÞch ®¶o trùc tiÕp sÏ rÊt phøc t¹p vµ h¬n n÷a kh«ng ph¶i ma trËn nµo còng cã ma trËn nghÞch ®¶o.
Dùa vµo c¸c phÐp biÕn ®æi hÖ ph¬ng tr×nh nh ho¸n vÞ, nh©n hµng víi mét h»ng sè. v. v. ®Ó hÖ trë lªn dÔ gi¶i h¬n. §iÓn h×nh lµ dïng phÐp to¸n víi hµng ®Ó ®a ma trËn hÖ sè vÒ ma trËn tam gi¸c, khö Gauss lµ dùa theo ph¬ng ph¸p nµy.
Trong luËn v¨n nµy ®Ò cËp ®Õn mét ph¬ng ph¸p gi¶i hÖ tuyÕn tÝnh dùa vµo ph¬ng ph¸p khö Gauss ®ã lµ t¸ch LU. Sau khi ®· ®a hÖ ph¬ng tr×nh vÒ ma trËn tam gi¸c sÏ dïng c¸c gi¶i thuËt thay thÕ tiÕn ( forward substitution) vµ gi¶i thuËt quay lui ( backward substitution) ®Ó tÝnh to¸n ra ®îc kÕt qu¶.
Gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh sau:
ax + ax+ ax+. . . . + ax= b
ax + ax+ ax+. . . + ax= b2
a31x1 + a32x + a33 x+. . . . + a 3n x= b3
. . . . . . . . . . . . . .
a n1x + a n2x+ a n3x+. . . . + a nnx= bn
Ta cã thÓ viÕt díi d¹ng
A x = b
Trong ®ã A lµ ma trËn hÖ sè, b lµ cét vÕ ph¶i, x lµ cét Èn sè cña hÖ ph¬ng tr×nh.
C¸c bíc tiÕn hµnh gi¶i thuËt t¸ch LU nh sau:
1) Ph©n t¸ch A = L * U dùa theo gi¶i thuËt khö Gauss.
2) Gi¶i hÖ L * y= b => t×m ra vect¬ y theo thuËt to¸n thay thÕ tiÕn
3) Gi¶i hÖ U *x = y => t×m ra nghiÖm cña bµi to¸n gèc x theo thuËt to¸n thay thÕ quay lui.
Nh vËy, ®Ó gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh, ta cÇn gi¶i quyÕt hai bµi to¸n : t¸ch A= L*U theo gi¶i thuËt khö Gauss vµ gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh cã hÖ sè lµ ma trËn tam gi¸c.
5. 1 T¸ch A = L*U dùa theo gi¶i thuËt khö Guassian
Gi¶i thuËt khö Gauss dùa trªn c¸c phÐp ®æi s¬ cÊp ®èi víi hµng cña ma trËn hÖ sè kh«ng lµm thay ®æi hÖ nh sau:
Nh©n c¸c phÇn tö cña hµng j víi mét sè kh¸c kh«ng
§æi chç hai hµng i vµ j cho nhau.
Céng vµo hµng i c¸c phÇn tö t¬ng øng víi hµng j.
Trong gi¶i thuËt khö Gauss, ®èi víi mçi cét i khö c¸c phÇn tö díi ®êng chÐo chÝnh b»ng c¸ch céng víi béi sè cña hµng i víi c¸c hµng phÝa díi.
Gi¶i thuËt khö tuÇn tù nh sau:
For k = 1 to n-1
For j= k + 1 to n
For i = k+1 to n
a = a– (a/ a)*a
C«ng viÖc tÝnh to¸n trong mét bíc ®îc minh ho¹ nh h×nh vÏ díi ®©y:
(k, k)
(k, i)
(j, k)
cét k
cét i
hµng k
hµng j i
(i, j)
Khö
CËp nhËt
H×nh 5. 1 M« t¶ tÝnh to¸n trong gi¶i thuËt khö Guass
Gi¶i thuËt t¸ch ma trËn A = L * U dùa theo gi¶i thuËt khö Gauss ta sÏ ®îc L lµ ma trËn tam gi¸c díi víi c¸c phÇn tö n»m trªn ®êng chÐo chÝnh =1 vµ U lµ ma trËn tam gi¸c trªn. Sau khi kÕt thóc thñ tôc t¸ch, th× L ®îc lu tr÷ trong phÇn díi ®êng chÐo chÝnh vµ U ®îc lu tr÷ trong phÇn trªn cña A.
Gi¶i thuËt t¸ch tuÇn tù ®îc tr×nh bµy nh sau:
For k = 1 to n-1
For i= k + 1 to n
l = a/a
end
for j = k +1 to n
For i = k +1 to n
a = a - l. a
end
end
end
Trong gi¶i thuËt tuÇn tù, c«ng viÖc tÝnh to¸n l ®îc ®îc ra ngoµi vßng lÆp trong ®Ó gi¶m chi phÝ tÝnh to¸n trong mçi bíc lÆp.
A
=
L
U
Th«ng thêng, gi¶i thuËt khö Gauss cã sù ho¸n ®æi gi÷a c¸c hµng ®Ó t×m ra phÇn tö xoay cã gi¸ trÞ tuyÖt ®èi lín nhÊt. Tuy nhiªn, ®Ó ®¬n gi¶n ho¸ bµi to¸n, t¹m thêi bá qua vÊn ®Ò t×m phÇn tö xoay cã gi¸ trÞ lín nhÊt. Xem xÐt ®é phøc t¹p cña gi¶i thuËt.
Gi¶i thuËt khö Gauss tuÇn tù yªu cÇu kho¶ng n/3 cÆp phÐp to¸n céng nh©n, bëi vËy thêi gian yªu cÇu thùc hiÖn lµ T= t n/3 víi t lµ thêi gian yªu cÇu thùc hiÖn phÐp céng -nh©n.
Qu¸ tr×nh thiÕt kÕ gi¶i thuËt song song ®îc tr×nh bµy nh sau:
a. Ph©n r·
§èi víi 2 vßng for i, j = 1, …. , n sÏ h×nh thµnh lªn ma trËn cã n phÇn tö Mét c¸ch tù nhiªn, ta ph©n r· ma trËn thµnh n t¸c vô, mçi t¸c vô t¹i vÞ trÝ (i, j) sÏ lu tr÷ hÖ sè a, tÝnh to¸n vµ lu tr÷ c¸c phÇn tö sau:
u nÕu i j
l nÕu i > j
C¸c phÇn tö 0 díi ®êng chÐo chÝnh trong ma trËn U, phÇn tö =0 phÝa trªn ®êng chÐo chÝnh vµ c¸c phÇn tö =1 trªn ®êng chÐo chÝnh kh«ng cÇn ph¶i tÝnh to¸n vµ lu tr÷, ta mÆc ®Þnh trong kÕt qu¶.
b. TruyÒn th«ng
C¸c bíc tÝnh to¸n cã sù phô thuéc d÷ liÖu lÉn nhau nªn truyÒn th«ng lµ cÇn thiÕt gi÷a c¸c t¸c vô. TruyÒn th«ng gi÷a c¸c t¸c vô ®îc m« t¶ nh h×nh díi ®©y.
H×nh 5. 2 M« t¶ truyÒn th«ng gi÷a c¸c t¸c vô
Khi ®ã ta cã ch¬ng tr×nh m« pháng cho tõng t¸c vô nh sau:
Program for task(i, j)
For k= 1 to min (i, j) –1
Recv a
Recv l
a= a- l* a
end
if i j then
broadcast a to task(k, j), k = i +1, …. , n
else
recv a
l= a/ a
broadcast l to tasks(i, j), k = j+1, …, n
end
c. TÝch tô
Víi m¶ng hai chiÒu n n c¸c t¸c vô, c¸c chiÕn lîc kÕt hîp t¸c vô nh sau:
1-D: kÕt hîp n/p hµng hoÆc cét
2-D: kÕt hîp c¸c t¸c vô thµnh m¶ng con 2 chiÒu (n/) (n/)
víi c¸c chiÕn lîc nµy, c«ng ®o¹n tÝch tô ®Òu t¹o ra p t¸c vô lín h¬n.
d. ¸nh x¹
Mçi t¸c vô t¹o ra tõ c«ng ®o¹n kÕt hîp sÏ ®îc Ên ®Þnh vµo mét trong p bé xö lý.
Víi mçi chiÕn lîc tÝch tô, ta cã mét gi¶i thuËt song song song t¬ng øng.
5. 1. 1 Gi¶i thuËt song song theo hµng
Trong c«ng ®o¹n tÝch tô c¸c t¸c vô, gi¶i thuËt híng theo hµng sÏ thùc hiÖn viÖc kÕt hîp n/p hµng c¸c t¸c vô ban ®Çu thµnh mét t¸c vô lín. Khi ®ã kh«ng cÇn thiÕt broadcast l theo chiÒu ngang bëi v× c¸c t¸c vô nµy ®îc thùc thi chØ trong mét t¸c vô.
Tuy nhiªn, chiÕn lîc tÝch tô nµy kh«ng song song ®îc viÖc cËp nhËt c¸c phÇn tö n»m cïng trong mét hµng. VÉn yªu cÇu broadcast theo chiÒu däc ®Ó truyÒn d÷ liÖu trong mçi hµng ë trªn tíi c¸c t¸c vô ë díi ®Ó cËp nhËt d÷ liÖu.
H×nh 5. 3 M« t¶ truyÒn th«ng gi÷a c¸c t¸c vô tÝch tô theo hµng
Gi¶i thuËt theo hµng 1-D nh sau:
For k=1 to n-1
If k myrows then
Broadcast { a: k < j < n } to other tasks
Else
Recv{ a: k jn }
End
For i myrows, i > k,
l = a/a.
end
for j = k+1 to n
for i myrows, i > k,
a= a- l*a
end
end
end
Thêi gian thùc hiÖn
TÝnh to¸n ®é phøc t¹p tÝnh to¸n cña thuËt to¸n.
-T¹i bíc thø k, viÖc cËp nhËt c¸c t¸c vô yªu cÇu kho¶ng
(n-k)/p phÐp to¸n.
- §é phøc t¹p cho toµn bé n-1 bíc sÏ lµ :
T t n/(3p).
TÝnh to¸n ®é phøc t¹p vÒ truyÒn th«ng.
T¬ng tù nh tÝnh to¸n ®é phøc t¹p, sè lîng d÷ liÖu broadcast t¹i bíc thø k lµ kho¶ng n-k, bëi vËy trªn m« h×nh 1-D Mesh, c¸c bé xö lý nèi nhau thµnh ®êng th¼ng vµ truyÒn th«ng víi nhau b»ng kü thuËt circuit-switched víi ¶nh hëng cña kho¶ng c¸ch gi÷a c¸c bé xö lý t h nhá cã thÓ bá qua. Ta cã chi phÝ cho truyÒn th«ng sÏ lµ
T (p-1) tn + (p-1)t n/2
Tæng thêi gian thùc hiÖn lµ :
T t n /(3p) + t(p-1)n + t(p-1) n/2
C¸c vÊn ®Ò ®Æt ra cho viÖc thùc thi gi¶i thuËt song song theo hµng lµ:
Ph©n t¸n c«ng viÖc kh«ng ®Òu, mçi t¸c vô sÏ ®i vµo tr¹ng th¸i rçi ngay khi hµng cuèi cïng ®îc hoµn thµnh.
NÕu t¸c vô qu¶n lý khèi c¸c hµng liªn tiÕp th× bé xö lý ®îc Ên ®Þnh t¬ng øng sÏ rçi thêi gian rÊt l©u tríc khi toµn bé tÝnh to¸n ®îc hoµn thµnh.
H¬n n÷a, c«ng viÖc cËp nhËt c¸c hµng sÏ Ýt ®i nhanh chãng khi sè hiÖu hµng gia t¨ng.
C¸c ph¬ng ph¸p gi¶i quyÕt cho vÊn ®Ò nµy lµ:
Ên ®Þnh c¸c hµng tíi c¸c t¸c vô theo chu tr×nh, víi hµng thø i ®îc Ên ®Þnh tíi task thø i mod n hoÆc Ên ®Þnh theo kiÓu chu tr×nh khèi (block-cyclic) hoÆc
Pipeline viÖc tÝnh to¸n vµ truyÒn d÷ liÖu, víi ph¬ng ph¸p nµy sÏ c¶i thiÖn ®îc hiÖu n¨ng cña gi¶i thuËt song song. Thay v× lµm viÖc trªn cïng mét bíc lÆp t¹i mét thêi ®iÓm, tÊt c¶ c¸c bé xö lý cã thÓ ®îc lËp lÞch tr×nh thùc hiÖn mét c¸ch kh«ng ®ång bé. Trong khi pipeline gi¶i thuËt khö Gauss th× mçi bé xö lý sÏ thùc hiÖn ®éc lËp bÊt kú ho¹t ®éng göi hoÆc tÝnh to¸n trõ phi nã ®ang chê nhËn d÷ liÖu dïng cho ho¹t ®éng ®ã.
+ T¹i bíc k, mçi t¸c vô hoµn thµnh cËp nhËt phÇn cßn l¹i cña nã tríc khi chuyÓn tíi bíc tiÕp theo k+1. Tuy nhiªn t¸c vô qu¶n lý hµng k+1 cã thÓ broadcast ngay sau khi nã ®îc cËp nhËt tríc khi nã tiÕp tôc viÖc cËp nhËt phÇn cßn l¹i cña bíc thø k.
+ Víi chiÕn lîc göi tríc “ send ahead” sÏ cho phÐp c¸c t¸c vô kh¸c b¾t ®Çu tiÕn hµnh c«ng viÖc trªn t¸c vô tiÕp theo sím h¬n bëi v× thêi gian chê ®îi d÷ liÖu cÇn thiÕt cho viÖc tÝnh to¸n ®· ®îc rót gän.
5. 1. 2 Gi¶i thuËt song song theo cét
ViÖc tÝch tô theo cét còng t¬ng tù nh gi¶i thuËt theo hµng, víi n/p cét c¸c t¸c vô c¬ së t¹o thµnh mét t¸c vô lín.
Khi thùc thi gi¶i thuËt sÏ kh«ng ph¶i broadcast c¸c hµng theo chiÒu däc nhng ngîc l¹i ph¶i broadcast theo chiÒu ngang cho c¸c task vô n»m bªn ph¶i.
Kh«ng song song ®îc viÖc tÝnh to¸n hÖ sè nh©n cña c¸c hµng dïng vµo viÖc khö c¸c phÇn tö díi ®êng chÐo chÝnh còng nh song song viÖc cËp nhËt c¸c phÇn tö bÊt kú cét nµo ®a ra.
H×nh 5. 4 M« pháng truyÒn th«ng gi÷a c¸c t¸c vô tÝch tô theo c«t
Gi¶i thuËt LU theo cét ®îc m« pháng nh sau:
For k=1 to n-1
If k mycols then
For i=k+1 to n
l= a/a
end
broadcast { l: k < i n } to other tasks
Else
Recv{ l: k jn }
End
For i mycols, j > k,
For i= k +1 to n
a= a- l*a
end
end
end
TÝnh to¸n ®é phøc t¹p gi¶i thuËt, c¸c vÊn ®Ò còng nh ph¬ng ph¸p gi¶i quyÕt còng t¬ng tù nh gi¶i thuËt song song tÝch tô theo hµng.
5. 1. 3 Gi¶i thuËt song song hai chiÒu
TiÕp theo chóng ta sÏ xem xÐt gi¶i thuËt t¸ch A=L*U hai chiÒu, khi ®ã m¶ng (n/) (n/) c¸c t¸c vô c¬ së sÏ ®îc kÕt hîp l¹i t¹o thµnh t¸c vô lín. ViÖc tÝch tô nµy sÏ kÕt hîp ®Æc ®iÓm cña gi¶i thuËt theo cét vµ gi¶i thuËt theo hµng. Nh broadcast theo chiÒu ngang vµ chiÒu däc ®îc yªu cÇu ®Ó truyÒn th«ng c¸c ®o¹n ma trËn theo hµng vµ c¸c hÖ sè nh©n theo cét
H×nh 5. 5 M« pháng truyÒn th«ng gi÷a c¸c t¸c vô tÝch tô kÕt hîp
Gi¶i thuËt song song kÕt hîp ®îc m« pháng nh sau:
For k=1 to n-1
If k myrows then
Broadcast { a: j mycols, j > k} to other tasks
in my task column
Else
Recv{ a: j mycols, j > k}
End
If k mycols then
For i myrows, i < k
l = a/a.
end
broadcast { l: i myrows, i > k} to other tasks in my task row
end
else
recv { l: i myrows, i > k}
end
for j mycols, j > k
for i myrows, i > k,
a= a - l a
end
end
end
TÝnh to¸n thêi gian thùc hiÖn cña thuËt to¸n.
T¹i bíc thø k, viÖc cËp nhËt bëi mçi t¸c vô yªu cÇu kho¶ng (n-k)/p phÐp to¸n. Do ®ã tæng sè trªn n-1 bíc sÏ lµ :
T t tn/(3p)
Sè lîng d÷ liÖu broadcast t¹i bíc k däc theo mçi hµng mçi cét cña mçi t¸c vô kho¶ng (n-k)/, bëi vËy trªn m« h×nh 2-D mesh
Ta cã T 2 tn + tn/
Tæng thêi gian thùc hiÖn lµ:
T tn/(3p) + 2 tn + t n/
Còng t¬ng tù nh gi¶i thuËt tÝch tô theo hµng hoÆc cét, gi¶i thuËt kÕt hîp cã c¸c vÊn ®Ò nh:
Mçi t¸c vô sÏ trë nªn rçi ngay sau khi c¸c hµng vµ cét cña nã hoµn thµnh. Sè lîng c«ng viÖc tÝnh to¸n Ýt ®i khi sè hiÖu hµng vµ cét t¨ng lªn.
§Ó c¶i thiÖn vÊn ®Ò c©n b»ng n¹p vµ tÝnh ®ång thêi ngêi ta cã thÓ Ên ®Þnh hµng cét vµo t¸c vô theo chu tr×nh, víi hÖ sè cña ma trËn A lµ a Ên ®Þnh vµo t¸c vô (i mod , j mod ). Ngoµi ra cã thÓ Ên ®Þnh theo khèi- chu tr×nh (block-cyclic).
HiÖu n¨ng cã thÓ n¨ng cao b»ng c¸ch pipeline tÝnh to¸n vµ truyÒn d÷ liÖu.
T¹i bíc thø k, mçi t¸c vô sÏ hoµn thµnh viÖc cËp nhËt ma trËn con cßn l¹i tríc khi chuyÓn ®Õn bíc thø k+1.
C«ng viÖc broadcast mçi ®o¹n cña hµng k+1, tÝnh to¸n vµ broadcast mçi ®o¹n hÖ sè nh©n cho bíc thø k+1 cã thÓ ®îc khëi t¹o ngay sau khi c¸c ®o¹n liªn quan ®Õn hµng k+1 vµ cét k+1 ®îc cËp nhËt bëi t¸c vô qu¶n lý nã, tríc khi hoµn thµnh viÖc cËp nhËt cßn l¹i cho bíc thø k
Víi chiÕn lîc göi tríc “send ahead” sÏ cho phÐp c¸c t¸c vô kh¸c tiÕn hµnh c«ng viÖc trªn bíc tiÕp theo sím h¬n.
5. 1. 4 Khö Gauss víi kü thuËt lùa chän phÇn tö xoay
Do c¸c hµng cña hÖ ph¬ng tr×nh tuyÕn tÝnh kh«ng rµng buéc thø tù, cho nªn ta cã thÓ ho¸n ®æi c¸c hµng cho nhau mµ kh«ng ¶nh hëng ®Õn hÖ. ViÖc chän phÇn tö xoay a sao cho gi¸ trÞ tuyÖt ®èi lín nhÊt nh»m tr¸nh kh¶ n¨ng chia cho phÇn tö rÊt nhá vµ nh»m ®¶m b¶o ch¾c ch¾n r»ng sè nh©n kh«ng vît qu¸ 1 vÒ ®é lín, lµm gi¶m ®i sù khuyÕch ®¹i lçi do lµm trßn.
Víi partial pivoting dÉn ®Õn sù t¸ch L*U theo h×nh thøc sau:
PA = LU
Víi P lµ ma trËn chuyÓn vÞ cña A
NÕu PA=LU th× hÖ Ax=b sÏ trë thµnh PAx = LU x= Pb
Tõ ®ã ta cã gi¶i hÖ tam gi¸c díi Ly= Pb theo gi¶i thuËt rót gän tiÕn, tiÕp theo sÏ gi¶i hÖ tam gi¸c trªn víi gi¶i thuËt rót gän quay lui U x= y.
Víi kü thuËt partial pivoting sÏ lµm phøc t¹p viÖc thùc thi song song gi¶i thuËt khö Gauss vµ ¶nh hëng thùc sù ®Õn hiÖu n¨ng.
§èi víi gi¶i thuËt tÝch tô theo cét th× viÖc t×m kiÕm theo phÇn tö xoay lµ kh«ng yªu cÇu truyÒn th«ng gi÷a c¸c t¸c vô nhng tÝnh to¸n hoµn toµn tuÇn tù. Mçi khi phÇn tö xoay ®îc t×m thÊy th× chØ sè cña hµng xoay ph¶i ®îc truyÒn th«ng tíi c¸c t¸c vô kh¸c, vµ c¸c hµng ph¶i ®îc ho¸n chuyÓn mét c¸c hoµn toµn hay h×nh thøc trong mçi t¸c vô.
Víi gi¶i thuËt tÝch tô theo hµng, t×m kiÕm phÇn tö trôc xoay sÏ ®îc song song nhng yªu cÇu truyÒn th«ng gi÷a c¸c t¸c vô vµ ng¨n c¶n pipeline gi÷a c¸c bíc tÝnh to¸n liªn tiÕp.
NÕu ho¸n chuyÓn hµng hoµn toµn th× chØ cã hai t¸c vô liªn quan ®Õn, cßn nÕu ho¸n chuyÓn h×nh thøc( chØ sè hµng ®îc thay ®æi ) th× viÖc ¸nh x¹ c¸c hµng tíi c¸c t¸c vô sÏ ®ùîc thay ®æi, ®iÒu nµy cã thÓ lµm gi¶m ®i tÝnh ®ång thêi vµ c©n b»ng n¹p cña gi¶i thuËt.
Víi gi¶i thuËt kÕt hîp hµng vµ cét, t×m kiÕm trôc xoay ®îc song song nhng yªu cÇu truyÒn th«ng gi÷a c¸c t¸c vô däc trªn cét vµ ng¨n c¶n pipeline gi÷a c¸c bíc tÝnh to¸n liªn tiÕp.
Do kü thuËt partial pivoting t¸c ®éng lµm gi¶m hiÖu n¨ng nªn cã mét vµi lùa chän ®îc ®a ra nh»m h¹n chÕ vÊn ®Ò t×m kiÕm :
T×m kiÕm phÇn tö xoay chØ n»m trong khèi c¸c hµng
T×m kiÕm cã møc ngìng
5. 2 Gi¶i hÖ ph¬ng tr×nh víi ma trËn hÖ sè tam gi¸c
Sau khi thùc hiÖn ph©n r· A= L*U, ta sÏ thu ®îc:
L lµ ma trËn tam gi¸c díi ( lower triangular ) bëi v× tÊt c¶ c¸c phÇn tö phÝa trªn ®êng chÐo chÝnh ®Òu = 0, l= 0 víi i < j.
U lµ ma trËn tam gi¸c trªn ( upper triangular) bëi v× tÊt c¶ c¸c phÇn tö phÝa díi ®êng chÐo chÝnh ®Òu = 0, u= 0 víi i> j.
§èi víi c¸c gi¶i thuËt trùc tiÕp gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh th× viÖc ®a ma trËn hÖ sè vÒ ma trËn tam gi¸c lµ ®iÒu quan träng bëi v× hÖ tuyÕn tÝnh ma trËn hÖ sè tam gi¸c thêng dÔ gi¶i b»ng c¸c bíc khö liªn tiÕp.
Gi¶i thuËt tuÇn tù gi¶i L* y = b.
§èi víi hÖ ph¬ng tr×nh tam gi¸c thÊp, y cã thÓ t×m ®îc b»ng gi¶i thuËt rót gän tiÕn. Gi¶i thuËt ®îc tr×nh bµy nh sau:
x=(b- , i=1, …, n
for j=1 to n
x= b/l
for i = j+1 to n
b= b- lx
end
end
Gi¶i thuËt tuÇn tù gi¶i U * x = y
§èi víi hÖ ph¬ng tr×nh tam gi¸c trªn, x cã thÓ t×m ®îc b»ng gi¶i thuËt rót gän quay lui. Gi¶i thuËt ®îc tr×nh bµy nh sau:
x=(b- , i=1, …, n
for j=1 to n
x= b/u
for i = 1 to j-1
b= b- ux
end
end
Ph©n tÝch ®é phøc t¹p cña gi¶i thuËt tuÇn tù.
Gi¶i thuËt rót gän tiÕn vµ rót gän quay lui yªu cÇu kho¶ng n/2 phÐp nh©n vµ sè lîng t¬ng tù ®èi víi phÐp céng, bëi vËy thêi gian tÝnh to¸n ®èi víi m« h×nh tuÇn tù lµ:
T= t n/2
Víi t lµ thêi gian tÝnh to¸n cho cÆp phÐp nh©n vµ céng.
Trong môc nµy chØ xem xÐt x©y dùng gi¶i thuËt song song ®èi víi hÖ ph¬ng tr×nh tam gi¸c díi, hÖ ph¬ng tr×nh tam gi¸c trªn sÏ ®îc gi¶i t¬ng tù.
Ph©n r·
Ph©n r· bµi to¸n thµnh c¸c t¸c vô, mçi t¸c vô t¬ng øng víi mét phÇn tö trong ma trËn L cÇn cËp nhËt.
For i=2, …, n, j= 1, …, i-1 t¸c vô (i, j). Mçi t¸c vô sÏ
+ lu tr÷ l
+ tÝnh to¸n lx
- For i = 1, …, n, t¸c vô (i, i). Mçi t¸c vô sÏ
+ lu tr÷ l vµ b
+ tÝnh tæng t=
+ tÝnh to¸n vµ lu tr÷ x= (b- t)/l
Víi viÖc ph©n chia nµy dÉn ®Õn m¶ng 2 chiÒu tam gi¸c n( n-1)/2 t¸c vô.
b. TruyÒn th«ng
§èi víi c¸c t¸c vô for j=1, …, n-1, mçi t¸c vô task(j, j) sÏ broadcast x tíi task(j, j), i=j+1, . . , n.
for i=2, . . , n tÝnh tæng c¸c kÕt qu¶ thu gän lx tõ c¸c t¸c vô task(i, j), j=1, …, i-1. tíi task(i, i).
TruyÒn th«ng gi÷a c¸c t¸c vô ®îc m« pháng theo h×nh vÏ sau:
H×nh 5. 6 M« t¶ truyÒn th«ng gi÷a c¸c t¸c vô
Program for task (i, j), ij
If i=j then
If i> 1 then
Recv sum reduction t else t=0 end
x=(b-t)/l
broadcast x to tasks(k, i), k=i+1, . . , n
else
recv x
t = lx
send t for sum reduction across tasks (i, k),
k=1, …. , i-1, to task(i, i)
end
c. TÝch tô
Víi m¶ng hai chiÒu t¸c vô, c¸c chiÕn lîc tÝch tô tù nhiªn lµ :
KÕt hîp n/p hµng hoÆc cét
KÕt hîp hµng cét víi ma trËn con kÝch thíc (n/) (n/)
trong c¶ hai trêng hîp ®Òu ®em l¹i p t¸c vô
d. ¸nh x¹
Mçi t¸c vô sÏ ®îc Ên ®Þnh vµo mét trong p bé xö lý.
5. 2. 1 Gi¶i thuËt song song tÝch tô theo hµng
Khi ®ã sÏ kÕt hîp p hµng t¸c vô c¬ së t¹o ra mét t¸c vô lín. Víi c¸c tÝch tô nµy sÏ kh«ng cÇn truyÒn th«ng ®Ó thùc hiÖn rót gän tæng trªn hµng bëi v× bÊt kú hµng nµo ®îc ®a ra ®Òu ®îc chøa toµn bé trong mét t¸c vô. Kh«ng thùc hiÖn song song trong viÖc tÝnh nh÷ng tæng nµy. Tuy nhiªn vÉn yªu cÇu broadcast theo chiÒu däc ®Ó truyÒn th«ng c¸c thµnh phÇn cña x.
H×nh 5. 7 M« t¶ truyÒn th«ng gi÷a c¸c t¸c vô tÝch tô theo hµng
Gi¶i thuËt song song tÝch tô theo hµng ®îc m« pháng nh sau:
For j=1 to n
If j myrows then
x= b/l
broadcast x to other tasks
else
recv x
end
for i myrows, i > j,
b= b- l x
end
end
C¸c vÊn ®Ò ®Æt ra khi kÕt hîp theo hµng
Mçi t¸c vô sÏ rçi ngay sau khi thµnh phÇn lêi gi¶i t¬ng øng víi hµng cuèi cïng trong t¸c vô ®ã ®îc t×m ra.
NÕu ta kÕt hîp liªn tiÕp c¸c hµng vµo mét t¸c vô th× cã thÓ t¸c vô sÏ rçi mét thêi gian l©u trong khi toµn bé tÝnh to¸n hoµn thµnh
TÝnh to¸n sÏ nhiÒu lªn khi sè hiÖu hµng t¨ng lªn
C¸c ph¬ng ph¸p gi¶i quyÕt
C©n b»ng n¹p vµ tÝnh ®ång thêi cã thÓ ®îc c¶i thiÖn b»ng c¸ch Ên ®Þnh c¸c hµng vµo c¸c t¸c vô theo chu tr×nh víi hµng i ®îc Ên ®Þnh vµo t¸c vô i mod p.
Cã c¸c c¸ch ¸nh x¹ kh¸c nh chu tr×nh-khèi (block-cyclic) hay ®èi ®Çu ( reflection ).
H×nh 5. 8 M« t¶ truyÒn th«ng gi÷a c¸c t¸c vô ¸nh x¹ chu tr×nh
H×nh 5. 9 M« t¶ truyÒn th«ng gi÷a c¸c t¸c vô ¸nh x¹ ®èi ®Çu
TÝnh to¸n thêi gian thùc hiÖn cña gi¶i thuËt
NÕu c¸c bíc liªn tiÕp ®îc pipeline th× thêi gian thùc hiÖn xÊp xØ lµ
T= t(n + 2n(p-1))/(2p) + (t+ t)(n-1)
- NÕu kh«ng pipeline ®îc c¸c bíc tÝnh to¸n liªn tiÕp th× sè h¹ng thÓ hiÖn chi phÝ truyÒn th«ng ®îc nh©n thªm víi mét hÖ sè :
+ p-1 ®èi víi m¸y tÝnh song song cã m¹ng kÕt nèi bé xö lý h×nh
1-D Mesh
+ 2(-1) ®èi víi m¸y tÝnh song song cã m¹ng kÕt nèi bé xö lý h×nh 2-D Mesh
+ log(p) ®èi víi m¸y tÝnh song song cã m¹ng kÕt nèi bé xö lý h×nh hypercube
Nh÷ng hÖ sè nµy thÓ hiÖn chiÒu dµi ®êng truyÒn th«ng thùc hiÖn broadcast.
C¶i thiÖn hiÖu n¨ng
HiÖu n¨ng cã thÓ c¶i thiÖn thùc sù b»ng chiÕn lîc “göi tríc “( send ahead) trong ®ã t¹i mçi bíc thø j t¸c vô qu¶n lý hµng j+1 cã thÓ tÝnh to¸n x vµ broadcast x tríc khi hoµn thµnh cËp nhËt ®èi víi x.
HiÖu qu¶ ®¹t ®îc cña pipeline bÞ t¸c ®éng m¹nh bëi cÊu tróc m¹ng vµ ¸nh x¹ c¸c hµng tíi c¸c t¸c vô. VÝ dô ¸nh x¹ chu tr×nh trªn m¹ng Ring cho phÐp hoµn thµnh hÇu hÕt kh¶ n¨ng pipeline trong khi kiÕn tróc Hypercube th× thÊp h¬n nhiÒu.
5. 2. 2 Gi¶i thuËt song song tÝch tô theo cét
TiÕp theo chóng ta sÏ xem xÐt viÖc tÝch tô theo 1 chiÒu híng cét, víi n/p cét c¸c t¸c vô c¬ së h×nh thµnh nªn t¸c vô lín.
Khi tÝch tô theo cét th× kh«ng cÇn thiÕt broadcast c¸c thµnh phÇn cña x theo chiÒu däc, bëi v× bÊt kú cét ma trËn nµo ®a ra ®Òu n»m hoµn toµn trong cïng mét t¸c vô. TruyÒn th«ng theo chiÒu ngang vÉn ®îc yªu cÇu ®Ó rót gän c¸c tæng tÝnh ë vßng lÆp bªn trong.
Tuy nhiªn kh«ng cã thùc thi song song trong viÖc tÝnh to¸n c¸c tÝch sè cã kÕt qu¶ tõ thµnh phÇn ®îc ®a ra tõ x.
H×nh 5. 9 M« t¶ truyÒn th«ng gi÷a c¸c t¸c vô tÝch tô theo cét
Gi¶i thuËt ®îc m« pháng nh sau
For j=1 to n
t= 0
for j mycols, j < i
t = t + lx
end
if i mycols then
recv sum reduction of t
x= ( b-t)/l
else
send t for sum reduction across tasks
end
end
Còng t¬ng tù gi¶i thuËt ®èi víi hµng, c¸c vÊn ®Ò ®Æt ra trong c©n b»ng n¹p vµ tÝnh ®ång thêi gåm cã:
C¸c t¸c vô vÉn cßn rçi tËn ®Õn khi phÇn tö lêi gi¶i t¬ng øng víi cét ®Çu tiªn cña nã ®îc tÝnh.
NÕu mçi t¸c vô qu¶n lý mét khèi liªn tôc c¸c cét th× mét t¸c vô vÉn cã thÓ rçi trong suèt thêi gian hÇu hÕt c«ng viÖc tÝnh to¸n.
Sè lîng c«ng viÖc tÝnh to¸n sÏ gi¶m ®i khi sè hiÖu cét t¨ng lªn.
C¸c ph¬ng ph¸p gi¶i quyÕt
Ên ®Þnh c¸c cét vµo c¸c t¸c vô theo chu tr×nh víi cét thø j Ên ®Þnh vµo trong task j mod p
ViÖc ¸nh x¹ kh¸c còng cã thÓ thùc hiÖn nh chu tr×nh khèi
( block-cyclic) hay ®èi ®Çu (reflection)
H×nh 5. 10 M« t¶ truyÒn th«ng gi÷a c¸c t¸c vô tÝch tô ¸nh x¹ chu tr×nh
H×nh 5. 11 M« t¶ truyÒn th«ng tÝch tô ¸nh x¹ ®èi ®Çu
5. 2. 3 Gi¶i thuËt song song hai chiÒu
TiÕp theo ta xem xÐt viÖc tÝch tô theo hai chiÒu víi mçi t¸c vô lín ®îc t¹o thµnh bëi kÕt hîp m¶ng con hai chiÒu ( n/) ( n/) t¸c vô ban ®Çu. Gi¶i thuËt nµy kÕt hîp ®Æc ®iÓm cña hai gi¶i thuËt tÝch tô theo cét vµ theo hµng.
Víi gi¶i thuËt nµy, broadcast ®îc yªu cÇu theo chiÒu däc vµ rót gän tæng theo chiÒu ngang ®îc yªu cÇu truyÒn th«ng gi÷a c¸c thµnh phÇn lêi gi¶i vµ tÝch luü c¸c kÕt qu¶ vßng lÆp bªn trong mét c¸ch t¬ng øng.
C¸c vÊn ®Ò ®èi víi gi¶i thuËt
NÕu mçi t¸c vô qu¶n lý mét khèi liªn tiÕp hµng vµ cét th× chóng ta sÏ cã mét gi¶i thuËt khèi c¸c t¸c vô nhá víi hiÖu qu¶ vµ tÝnh ®ång thêi thÊp. H¬n n÷a víi c¸ch tiÕp cËn nµy sÏ dÉn ®Õn chØ cã (p + ) /2 lµ kh«ng trèng rçng. L·ng phÝ gÇn mét nöa c¸c bé xö lý trong ma trËn Mesh 2-D. §Ó gi¶i quyÕt vÊn ®Ò nµy th× viÖc Ên ®Þnh theo c¸ch chu tr×nh c¸c hµng vµ cét tíi c¸c t¸c vô, víi phÇn tö ma trËn hÖ sè l ®îc Ên ®Þnh vµo t¸c vô (i mod , j mod ), kÕt qu¶ lµ cã p t¸c vô kh«ng trèng rçng, bëi vËy ma trËn Mesh 2-D cã thÓ ®îc sö dông.
H×nh 5. 12 M« t¶ truyÒn th«ng tÝch tô kÕt hîp
H×nh 5. 13 M« truyÒn th«ng gi÷a c¸c t¸c vô ¸nh x¹ chu tr×nh
Nhng ta nhËn thÊy vßng lÆp trªn c¸c thµnh phÇn lêi gi¶i liªn tiÕp vµ thùc hiÖn t¬ng øng víi rót gän tæng theo chiÒu ngang vµ broadcast theo chiÒu däc, do ®ã vÉn cã h¹n chÕ vÒ tÝnh ®ång thêi bëi v× thùc hiÖn tÝnh to¸n cho mçi thµnh phÇn chØ liªn quan ®Õn mét hµng t¸c vô vµ mét cét t¸c vô.
§Ó gi¶i quyÕt vÊn ®Ò nµy, mét gi¶i thuËt tèt h¬n cã thÓ ®¹t ®îc b»ng c¸ch tÝnh to¸n c¸c thµnh phÇn lêi gi¶i trong mét nhãm , ®iÒu nµy cho phÐp tÊt c¶ c¸c t¸c vô cËp nhËt kÕt qu¶ mét c¸ch ®ång thêi.
Mçi bíc cña gi¶i thuËt nµy gåm cã 4 pha nh sau:
ViÖc tÝnh to¸n thµnh phÇn lêi gi¶i tiÕp theo bëi c¸c t¸c vô trong ma trËn tam gi¸c thÊp sö dông gi¶i thuËt song song tÝch tô hai chiÒu.
ViÖc broadcast c¸c thµnh phÇn lêi gi¶i kÕt qu¶ theo chiÒu däc tõ c¸c t¸c vô trªn ®êng chÐo chÝnh tíi c¸c t¸c vô trong ma trËn tam gi¸c trªn
TÝnh to¸n cËp nhËt kÕt qu¶ ®îc thùc hiÖn bëi tÊt c¶ c¸c t¸c vô.
Rót gän tæng theo chiÒu ngang sÏ ®îc thùc hiÖn bëi c¸c t¸c vô trong ma trËn tam gi¸c trªn ®Õn c¸c t¸c vô trªn ®êng chÐo chÝnh.
H×nh 5. 14 M« t¶ c¸c pha trong gi¶i thuËt tÝnh to¸n theo nhãm
TÝnh to¸n thêi gian thùc hiÖn
Toµn bé thêi gian yªu cÇu ®îc tÝnh to¸n mét c¸ch xÊp xØ lµ:
T= tn/(2p)+ (4(t+ t) + 5 t) n víi s lµ chiÒu dµi ®o¹n.
Nh v©y ta ®· ¸p dông tiÕn tr×nh thiÕt kÕ vµo trong bµi to¸n gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh. §©y lµ bµi to¸n c¬ b¶n, cã nhiÒu øng dông trong c¸c gi¶i thuËt song song thiÕt kÕ cho bµi to¸n phøc t¹p. Ch¬ng tiÕp sÏ tr×nh bµy ph¬ng ph¸p m« pháng mét sè gi¶i thuËt song song ®· thiÕt kÕ vµ ®¸nh gi¸ qua thêi gian thùc hiÖn.
5. 3 Thùc thi gi¶i thuËt
C¸c gi¶i thuËt song song cho bµi to¸n gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh ®îc thiÕt kÕ cho m« h×nh tÝnh to¸n nhiÒu bé xö lý. Mçi m¸y tÝnh thùc hiÖn mét hoÆc nhiÒu tiÕn tr×nh, trao ®æi d÷ liÖu th«ng qua m¹ng truyÒn th«ng kÕt nèi. Tuy nhiªn ta vÉn cã thÓ m« pháng ®îc gi¶i thuËt trªn m« h×nh m¸y tÝnh ®¬n bé xö lý víi viÖc ph©n chia thêi gian, xö lý mét c¸ch xen kÏ c¸c tiÕn tr×nh.
5. 3. 1 X©y dùng ch¬ng tr×nh
Trªn mét m¸y tÝnh ®¬n bé xö lý th× t¹i mét thêi ®iÓm chØ cã mét tiÕn tr×nh thùc hiÖn, do ®ã c¸c tiÕn tr×nh kh«ng thÓ ®ång thêi thùc hiÖn song song nhiÒu dßng lÖnh trªn m¸y tÝnh mét bé xö lý. Trong c¸c hÖ ®iÒu hµnh hç trî tÝnh to¸n song song th× vÊn ®Ò nµy cã thÓ gi¶i quyÕt b»ng c¸ch t¹o ra c¸c processor logic, mçi processor nµy qu¶n lý mét tiÕn tr×nh t¬ng øng vµ thùc hiÖn tiÕn tr×nh khi nhËn ®îc processor vËt lý. Víi m« h×nh ph©n chia thêi gian nµy, c¸c tiÕn tr×nh sÏ cã c¶m gi¸c nh ®ang chØ cã duy nhÊt mét tiÕn tr×nh sö dông hÖ thèng.
Trong khi thùc thi tiÕn tr×nh song song, mçi tiÕn tr×nh cã thÓ thuéc mét trong ba tr¹ng th¸i sau:
NhËp
Khëi t¹o
S½n sµng
Thùc hiÖn
Ng¾t
KÕt thóc
Vµo tõ chÕ ®é ph©n chia thêi gian
Ra trong chÕ ®é ph©n chia thêi gian
H×nh 6. 1 C«ng viÖc vµ tr¹ng th¸i tiÕn tr×nh
TiÕn tr×nh n»m trong tr¹ng th¸i s½n sµng khi ®· ®îc cung cÊp ®Çy ®ñ tµi nguyªn ®Ó thùc hiÖn, chê ®îi ®îc cung cÊp processor vËt lý. TiÕn tr×nh trong tr¹ng th¸i thùc khi ®ang thùc hiÖn c¸c lÖnh trªn processor vËt lý. Cßn tiÕn tr×nh trong tr¹ng th¸i ng¾t khi ®îi xuÊt hiÖn mét sù kiÖn hoÆc cung cÊp tµi nguyªn ®Ó thùc hiÖn.
T¹i mçi thêi ®iÓm, cã nhiÒu tiÕn tr×nh ®ang tån t¹i vµ cã tr¹ng th¸i riªng. Do ®ã, ®Ó qu¶n lý ®îc c¸c tiÕn tr×nh song song trong m¸y tÝnh ®¬n bé xö lý, c¸c hÖ ®iÒu hµnh cÇn ph¶i tæ chøc lu th«ng tin tr¹ng th¸i tiÕn tr×nh vµo khèi ®iÒu khiÓn tiÕn tr×nh PCB ( Process Control Block). Khèi ®iÒu khiÓn nµy sÏ chøa toµn bé tr¹ng th¸i cña tiÕn tr×nh.
C¸c tiÕn tr×nh chñ yÕu n»m trong hai tr¹ng th¸i lµ s½n sµng vµ ng¾t. Tæ chøc c¸c tiÕn tr×nh trong cïng mét tr¹ng th¸i thµnh mét dßng hµng ®îi thùc sù ( tøc lµ tæ chøc theo kiÓu FIFO).
Khi mét tiÕn tr×nh ®îc cung cÊp processor vËt lý, c¸c th«ng tin trong b¶ng m« t¶ nh bé ®Õm ch¬ng tr×nh, c¸c thanh ghi, con trá stack ®îc n¹p vµo trong processsor vµ lu tr÷ gi¸ trÞ hiÖn thêi cña CPU.
Khi dõng tiÕn tr×nh l¹i ®Ó chuyÓn sang tiÕn tr×nh kh¸c, cÇn thiÕt ph¶i lu tr¹ng th¸i cña c¸c thanh ghi vµo PCB.
Khi b¾t ®Çu thùc hiÖn mét tiÕn tr×nh míi, cÇn n¹p c¸c tr¹ng th¸i ®îc lu trong PCB vµo trong processor. Ch¬ng tr×nh cÇn duy tr× ®îc c¸c hµng ®îi tr¹ng th¸i trong khi thùc hiÖn, bëi v× c¸c hµng ®îi thÓ hiÖn tr¹ng th¸i cña tÊt c¶ c¸c tiÕn tr×nh ®ang tån t¹i.
C«ng cô ®Ó c¸c tiÕn tr×nh cã thÓ thùc hiÖn chÝnh x¸c lµ ng¾t. Ng¾t sÏ ph©n chia thêi gian tÝnh to¸n cho tõng tiÕn tr×nh, c¸c thiÕt bÞ ngo¹i vi sö dông ng¾t ®Ó b¸o cho processor biÕt sù thay ®æi tr¹ng th¸i cña m×nh.
Trªn quan ®iÓm lËp tr×nh, tõ gãc ®é processor, ta cã thÓ ®Þnh nghÜa ng¾t ngõng ®ét xuÊt viÖc thùc hiÖn mét tiÕn tr×nh ®Ó chuyÓn sang thùc hiÖn tiÕn tr×nh kh¸c khi cã mét sù kiÖn nµo ®ã x¶y ra. Nh vËy ng¾t lµ c«ng cô chuyÓn ®iÒu khiÓn tíi mét tiÕn tr×nh kh¸c mµ tiÕn tr×nh hiÖn t¹i kh«ng biÕt.
PhÇn lín c¸c m¸y tÝnh ®Òu cã ®ång hå ®éc lËp ®o kho¶ng thêi gian. Do ®ã cã thÓ dïng ®ång hå ®Ó ®iÒu khiÓn processor theo thêi gian. CÇn x¸c lËp mét kho¶ng thêi gian nhÊt ®Þnh cho ®ång hå vµ gi¸ trÞ nµy tù ®éng ®îc gi¶m dÇn cho ®Õn khi xuÊt hiÖn tÝn hiÖu ng¾t ®ång hå. B»ng c¸ch nµy cã thÓ t¹o ®ång hå riªng cho tõng tiÕn tr×nh vµ viÖc xö lý dßng xÕp hµng kÕt hîp víi thø tù u tiªn trë nªn dÔ dµng h¬n nhiÒu. mçi phÇn tö cña danh s¸ch øng víi dßng xÕp hµng chøa tªn tiÕn tr×nh vµ kho¶ng thêi gian cÇn cung cÊp processor. Mçi lÇn cã ng¾t ®ång hå b¸o hÕt thêi gian th× hÖ thèng kÝch ho¹t tiÕn tr×nh kh¸c vµ n¹p kho¶ng thêi gian míi bé ®Õm thêi gian.
Tuy nhiªn ®Ó qu¶n lý c¸c tiÕn tr×nh nh c¸c hÖ ®iÒu hµnh 32 bÝt, ta cÇn truy xuÊt vµo hÖ thèng, lÊy ®îc c¸c tr¹ng th¸i cña tiÕn tr×nh ®ang thùc hiÖn. Víi c¸c ng«n ng÷ lËp tr×nh th«ng thêng th× viÖc thùc hiÖn c¸c tiÕn tr×nh song song nh thÕ sÏ rÊt khã bëi v× ngêi lËp tr×nh ph¶i phô thuéc vµo tr×nh biªn dÞch cña ng«n ng÷ cô thÓ.
§èi víi bµi to¸n gi¶i hÖ ph¬ng tr×nh tuyÕn tÝnh th× c¸c tiÕn tr×nh ®îc thiÕt kÕ phô thuéc vµo tham sè hµng, cét. Do ®ã, ®¬n vÞ ph©n chia lµ thêi gian thùc hiÖn mét hµng cét, mçi tiÕn tr×nh sÏ thùc hiÖn mét hµng hoÆc cét sau ®ã chuyÓn sang tiÕn tr×nh kh¸c thùc hiÖn.
Lý do gi¶i quyÕt bµi to¸n lín v× nÕu víi bµi to¸n nhá do tèc ®é cña m¸y tÝnh lµ qu¸ lín nªn thêi gian ®Ó gi¶i quyÕt mét bµi to¸n lµ rÊt nhá ( chØ kho¶ng micro gi©y) nªn ta kh«ng thÓ nhËn biÕt ®îc lîi Ých cña viÖc thùc hiÖn song song. V× vËy, bµi to¸n ®a ra thö nghiÖp yªu cÇu cÇn ph¶i cã sè bËc lín. MÆt kh¸c, do h¹n chÕ vÒ ng«n ng÷ thùc hiÖn (ng«n ng÷ C), bé nhí dµnh cho ch¬ng tr×nh tèi ®a lµ 640KB nªn viÖc lu tr÷ vµ trao ®æi d÷ liÖu lµ h¹n chÕ. §Ó cã thÓ gi¶i quyÕt ®îc bµi to¸n lín ta ph¶i thùc hiÖn viÖc lu tr÷ vµ truy xuÊt víi bé nhí bªn ngoµi ( æ ®Üa cøng). Cô thÓ viÖc thùc hiÖn ®îc minh ho¹ nh sau:
TÊt c¶ c¸c hÖ sè cña hÖ ph¬ng tr×nh ®îc lu tr÷ ë bé nhí ngoµi. Khi cÇn mét hÖ sè nµo th× hÖ sè ®ã sÏ ®îc ®äc vµo bé nhí trong ( biÕn t¹m thêi).
Sau khi xö lý xong th× tÊt c¶ c¸c biÕn t¹m thêi ®ã l¹i ®îc lu trë l¹i bé nhí ngoµi ( tÊt c¶ c¸c biÕn ®· xö lý vµ cha xö lý).
Qu¸ tr×nh cø tiÕp tôc nh vËy cho ®Õn khi ch¬ng tr×nh kÕt thóc. KÕt qu¶ sÏ ®îc lu ra bé nhí ngoµi.
Thíc ®o ®¸nh gi¸ sù kh¸c biÖt gi÷a thùc hiÖn song song vµ thùc hiÖn tuÇn tù ®ã lµ thêi gian thùc hiÖn cña ch¬ng tr×nh víi cïng mét ®Çu vµo. Thêi gian thùc hiÖn song song sÏ ®îc tÝnh to¸n theo c¸ch sau :
Khi b¾t ®Çu thùc hiÖn tiÕn tr×nh ta khëi t¹o bé ®Õm thêi gian (sÏ lÊy theo ®ång hå hÖ thèng). Nh vËy mçi tiÕn tr×nh sÏ cã mét bé ®Õm thêi gian riªng.
Khi tiÕn tr×nh thùc hiÖn xong ( mét hµng hoÆc mét cét), bé ®Õm ®îc lu l¹i vµ sÏ ®îc tiÕp tôc tÝnh to¸n khi ta b¾t ®Çu l¹i tiÕn tr×nh nµy ( gi¸ trÞ khëi t¹o cho bé ®Õm thêi gian cña tiÕn tr×nh nµy lµ thêi gian cña viÖc thùc hiÖn tiÕn tr×nh nµy tríc ®ã).
Sau khi thùc hiÖn xong th× thêi gian thùc hiÖn song song sÏ b»ng thêi gian lín nhÊt mµ mét trong c¸c tiÕn tr×nh trªn thùc hiÖn.
§Ó so s¸nh ta sÏ thùc hiÖn gi¶i bµi to¸n nµy theo gi¶i thuËt tuÇn tù vµ sÏ thu ®îc thêi gian thùc hiÖn tuÇn tù nµy, sau ®ã ®em so s¸nh thêi gian ®· thu ®îc ë bíc thùc hiÖn song song ®Ó thÊy ®îc hiÖu qu¶ cña gi¶i thuËt song song.
5. 3. 3 C¸c h¹n chÕ vµ híng ph¸t triÓn ch¬ng tr×nh
Ch¬ng tr×nh ®îc thùc hiÖn trªn m« h×nh m¸y tÝnh ®¬n bé xö lý nªn nh÷ng ®¸nh gi¸ vÒ thêi gian kh«ng hîp lý bëi v× cha tÝnh to¸n ®îc chi phÝ thêi gian truyÒn th«ng. Ngoµi ra cha thÓ ¸p dông ph©n chia thêi gian vµo bµi to¸n bÊt kú.
C¸c gi¶i thuËt song song ®îc thiÕt kÕ trªn m« h×nh nhiÒu bé xö lý, do ®ã ®Ó ®¸nh gi¸ ®îc gi¶i thuËt còng nh thÊy®îc hiÖu qu¶ vÒ thêi gian, ta nªn x©y dùng ch¬ng tr×nh trªn m« h×nh m¸y tÝnh song song Multiprocessor hoÆc Multicomputer. Th«ng thêng ®Ó gi¶m chi phÝ s¶n xuÊt m¸y tÝnh song song, c¸c bµi to¸n song song thêng ®îc thùc thi trªn m¹ng côc bé kÕt nèi c¸c m¸y tÝnh c¸ nh©n s½n cã dùa trªn hç trî cña hÖ ®iÒu hµnh m¹ng nh Unix, Window NT víi m«i trêng tÝnh to¸n PVM hay MPI.
KÕt luËn
B¸o c¸o ®· ®Ò cËp ®Õn nh÷ng vÊn ®Ò chung khi thiÕt kÕ gi¶i thuËt song song nh c¸c m« h×nh tæ chøc gi¶i thuËt song song, ®a ra c¸c c«ng ®o¹n trong qu¸ tr×nh thiÕt kÕ, còng nh c¸c vÊn ®Ò liªn quan khi ®¸nh gi¸ hiÖu qu¶ gi¶i thuËt. ¸p dông vµo bµi to¸n cô thÓ vµ x©y dùng ch¬ng tr×nh minh ho¹ cho nh÷ng thiÕt kÕ.
Tuy nhiªn, víi h¹n chÕ vÒ thêi gian vµ kiÕn thøc nªn cha x©y dùng ®îc ch¬ng tr×nh m« pháng trªn nhiÒu m¸y tÝnh kh¸c nhau ®Ó cã thÓ ®¸nh gi¸ ®îc ®óng thêi gian thùc hiÖn gi¶i thuËt song song.
HiÖn nay, tÝnh to¸n song song ®ang ®ãng vai trß quan träng trong c¸c øng dông thùc tÕ còng nh c¸c bµi to¸n phôc vô nghiªn cøu khoa häc. T×m hiÓu ®îc c¸c vÊn ®Ò liªn quan ®Õn thiÕt kÕ gi¶i thuËt sÏ ®ãng vai trß quan träng khi ph¸t triÓn øng dông song song.
Tµi liÖu tham kh¶o
NguyÔn Thanh Tïng, Gi¸o tr×nh c¬ së chuyªn nghµnh hÖ ®iÒu hµnh, 1995.
NguyÔn §×nh TrÝ, To¸n cao cÊp I, NXB Gi¸o dôc, 1998.
§ç Xu©n L«i, CÊu tróc d÷ liÖu vµ gi¶i thuËt, NXB Gi¸o dôc, 1998.
NguyÔn Thóc H¶i, M¹ng m¸y tÝnh vµ hÖ thèng më, NXB Gi¸o dôc, 1997.
Michael J. Quinn, Parallel Computing Theory and Practice, NXB McGraw-Hill, 1994.
Albert Y. Zomaya, Parallel and Distributed Computing Handbook, NXB McGraw-Hill, 1996.
M. Sasikumar, Dinesh Shikhare, P. Ravi Prakash, Introduction To Parallel Processing, Prentice Hall of India, 2000
Joel M. CrichLow, An Introduction to Distributed and Parallel Computing, Prentice Hall, 1997
Ian Foster, Designing and Building Parallel Programs, 1995
10. htttp://www. llnl. gov/computing/turorials/workshops/workshop /parallel_computing
11. Michael Tischer, CÈm nang lËp tr×nh hÖ thèng, NXB Gi¸o dôc, 1996
Các file đính kèm theo tài liệu này:
- Thiết kế giải thuật song song.DOC
