Đồ Án Thiết kế giải thuật song song

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ệ.