RO GIAO DUC VA DAO TAO TRUONG DAI HOC BACH KHOA HA NOI LUAN VAN THAC S¥ KHOA HOC NGANH: CO HOC KY THUAT KY THUAT TÍNH TOÁN SONG SONG TRONG MOT SO UNG DUNG CO HOC NGHIEM BAO LONG HA NOI 2006 DANH MỤC HÌNH Hình 1.1: Luật Moore về tốc độ của bộ xử lý 7 Hình 1.2: Hiệu năng tính toán của các cấp độ trưng tâm tỉnh toán song song 9 Hình 3.1: Mô hình máy tính cá nhân gồm một bộ xứ lý và một bộ nhớ 1S Hình 3.2: Mã hình máy tính song song bộ nhớ chia sẽ 16 Ilinh 3.3: So đề đơn giản kiến trúc máy tính lõi đôi của Pentium. 16 Hình 3 4: Sơ dễ kiến trủc máy tính lỗi tử của Pentium 17 Hình 3.5: Mô hỉnh máy tính song song bệ nhớ phân tán.6: IIệ thống mạng kết nếi từng cặp máy tính với nhau 18 Hinh 3.7: Hệ thống mạng dạng lưới hai chiều 20 Hình 3.8: Hê thông mạng siêu lập phương ba chiều 21 Ilinh 3.9: Phân rã theo miễn cho bai loan trong không gian ba chiều 21 Hinh 3.10: Hệ thống mạng siêu lập phương bốn chiều 22 Hình 3.11: Hệ thống mạng máy trạm.12: Hệ thống máy tinh Beowulf 23 Hình 3.13: Số lượng cô định các tiển trình độc lập trong 24 TIỉnh 3.14: Lượng Liên trình động, độc lập trên nên PVM 25 Hinh 3.15: M6 hinh thực hiện của các tiến trình thu được trên nền PVM: _ 25 Hình 3.16: Dềng bộ hóa các tiến trình theo thuật giải butterfly sử dụng hàm.17: Tính tổng của 16 số hạng sử dụng giải thuật butterfiy 27 TIình 3.18: Tính tích phân số băng tổng diện tích các hinh thang 28 Hình 3.19: Tỉnh số pi theo công thức tổng diện tích hình thang 28 Hình 3.20: Kỹ thuật tính toán song song pipeline 29 TIình 3.21: Mô hình hóa bài toán giải phương trình truyền nhiệt hai chiều 30 Hình 3.22: Mô hình tính toán hệ số tăng tốc 31 TIình 4.1: Cấu trúc cơ bản của một chương trình sử dụng giao thức MPI 34 Hình 4 2: Các tập hợp Iruyền thang tong MPT 35 Hình 4.3: Chỉ tiết mô hình truyền thông điểm tới điểm 37 Hình 4.4: Mô hình quảng bả truyền thông 39 Hinh 4.5: Ma hinh tổng hợp truyền thông 40 Hinh 4 6: M6 hinh tap hop di ligu truyén thông 41 Hình 4 7: Mô hình tích hợp quảng bá và tổng hợp truyền thông 42 Hình 4.8: Mô hình phân tán dữ liêu truyền thông 43 Hinh 4.9: Téng két mét sé mô hình gói truyền thông 44 Hình 5.1: Các thư viên linh toán song song thông dựng 40 Hinh 5.2: Phân tản thành các tiễn trình độc lập 52 Ilinh $.3: Song song hóa Matlab với giao thức truyền thông điệp MPI_ 54 Hình 5.4: Tính toán hiệu năng cao qua dịch vụ sử dụng các siêu máy tính _ %6 Hình 5.5: Mô hỉnh biên dich ma Matlab thanh mã thư viện tính toán song, song.6: I arợng băng thông cúa hệ thống song song sử dụng Matlab __61 Hình 5.7: Hiệu quả tăng tốc của MatlabMPI khi so với thuật giải tuần tự tốt.8: 8o sánh chỉ phí lập trỉnh với hiệu quá tính toán của các công cụ lập trình sơng song 63 Hình 6.1: Rời rạc hóa miền khảo sát đỂ giải phương trinh vị phân 67 Hình 6.3: Sơ đề tính toán tuần tự giải thuật lặp don 72 Ilinh 6.3: So luge về các bước thiết kế giải thuật song song 73 Mé dau Khoảng hai năm trở lại dây, chúng ta bắt dầu nghe nhiều dến hộ xử lý lõi kép của Intel. Bộ xử lý này chính làm một trong những kiến trúc máy tính song song dang được thương mai boa béi cả Intel và AMD, hai nhà sẵn xuất chíp lớn. Điều đó vẫn chưa cha ta thấy rõ rằng đã có các siêu máy tính tích hợp đến hơn mười ngàn bộ xử lý đo các công ty không lễ như IEM hay IIP thiết kế dễ thực hiện các dự án trọng diém quốc pia.
Hiệu ứng nghiền cứu tính toán song song lan rất rộng khi xuất hiên các mô hình tính toán song song sử dung mạng máy tính kết nối hàng ngàn bộ xử lý đơn để giải quyết một bài toán. Các bài toán cơ học hiện đại thực hiện ngảy cảng nhiều trên máy tính Phương pháp phần tử hữu hạn, phương pháp số hay phương pháp phần tử biên ngày cảng tăng nhu cầu tỉnh toán khi giải quyết các bi toán cỡ lớn (số phần tử lớn) hay các bải toán phi tuyên. Nhu cầu tất yếu là tìm một phương pháp tính toán có hiệu năng cao hơn đề giải quyết các bài loắn này. Luan vin trinb bay về các kỹ thuật tính toán song song vả cách thức sử dụng kỹ thuật này giải các bải toán cơ học sau đó đưa vào các kiến trúc máy tỉnh song song chỉ phí thấp để thực hiện.
Luin văn gằm gồm sáu chương, trình bảy và đánh giá sự phát triển của kỹ thuật tính toán song song cũng như nhu cầu ngảy cảng lớn của việc ứng dựng tỉnh toán song song vào các bài toán kỹ thuật nói chung và sác bài toán cơ học nói riêng. Ngoài ra luận văn mô tả chỉ tiết và khá đầy đủ về các kỹ thuật tính toán song song hiện tại từ đơn giản đến phức tạp hơn. Ngoài việc xây dựng một thư viện các mê dun ma trân sử dụng giải thuât tĩnh toán song, song, luận văn còn giải quyết một bài toán cơ học cụ thể, bài toán nay có thể 4p dụng vào thực tiễn ngay hay phát triển thêm để tận đụng triệt để hơn gác phát triển của vi xứ lý theo dịnh luật Moore. GẦn như ngay sau do cac ¥ tưởng, về tính toán song song đã xuất hiện, tuy nhiên phải đến thập niên 90 thì các img dung tỉnh toán song song mới tỏ ra hiệu quả trên các siêu máy tính đắt tiền của các hãng máy tỉnh nỗi tiếng như IBMI hay HP.
Đến thời diém hiện nay số lượng đẻn điện tử tích hợp trong một chíp điện tử gần như bão hoà (kích thước chíp điện tử đã đạt đến 60 nanomet và có khả năng khó phát triển thêm thì các nhả cung cắp chíp bắt đầu xu hướng tích hợp nhiêu lõi trong một bộ xử lý như bộ xử lý Intel đua] core hay AMD dual core. R6 rang ta thay xu hướng áp dụng tính toán song song là xu hướng khó đão ngược 1.2 Trong vật lý và cơ học Rất nhiều bài toán vật lý hiện nay yêu cầu lượng tính toán rất lớn, điễn hính là bài toán mô phỏng hệ nhiều vật trong không gian. Mỗi vật đều chịu tương tác lá lực hẳn dẫn của các vật thể còn lại trong không gian. Da đỏ nếu có N vật Thì ta phải tính tới N? phép tính cho mỗi vật.
Irong ngân hà có 101! ngôi sao, giả sử mỗi phép tỉnh chỉ tiêu tốn 1s thi phải mất tới 10® năm để tính toán. Đã có những công trình nghiên cứu áp dụng tính toán sơng song thành công và có kết quả bước đầu về bài toán nay. Đơn giản hơn, các bài toán mô phóng rô bốt có bậc Lự đo lớn hơn 6 cũng yêu cầu lượng tính toán lớn và dé đảm bảo thời gian thực thì yêu cầu về tính toán song song là rất lớn. Trong phương pháp số các bai loan yêu cầu lượng tính Loán lớn như giải hệ phương trình đại số tuyến tính cỡ lớn, giải hệ phương trình đại số phí tuyến, giải phương trình vi phân tuyến tinh va phi tuyến cũng rất cần ứng dụng tính toán song song.
DANH MUC BANG Bảng 3.1: Một số hệ thống siêu máy tính giá rẻ hiện dang được sử dụng 23 Bang 4.1: Các kiểu đữ hiệu điển hình trong giao thức MIPI 35 Bang 4.2: Kiểu dữ liệu tương ứng với các tham số truyền vào các hàm MPI 36 Bang 4.3: Các mô hình gửi thông điệp MEI hỗ trợ 38 Bang 4.4: Các thao tác Lông hợp dữ liệu hảm MPI Recduco gó thể thực hiện được 40 Bang 5.1: Bang các cau lệnh được cung cấp với mpd 41 Bảng 5.2: Bắng các lựa chọn được cung cập với smpd 47 Bảng 5.3: Các lựa chọn với câu lệnh mpiexec 48 Bang 5.4: Báng các phần mềm hỗ trợ phân lán các tiến trình độc lập trên Matlab 53 Bang 5.5: Bảng các phần mềm hỗ trợ truyền thông diép trén Matlab 55 Bang 5.6: Băng các địch vụ hỗ trợ Linh Loan song song trén Matlab 57 Bảng 5.7: Hãng các phần mềm giúp dich va ứng dụng các chương trình song song ma Matlab se Các bải toán về phương pháp phần tử hữu han hay phần tử biên cũng đòi hỏi lượng lớn tính toán khi số phần tử trong bài toán lớn, làm cho số ẩn cần giải quyết tăng theo Trên đây chỉ là những ứng dụng có thể áp dụng tính toán song song theo tầm hiểu biết của tác giả, còn rất nhiều ứng dụng khác nữa như trong công nghệ nano, hoá học, y tế, năng lượng, quân sự đều đòi hỏi kỹ thuật tính toán hiệu năng cao. Bằng chứng là sự phát triển của các siêu máy tính của các cơ quan quốc phòng của Mỹ là rất mạnh mẽ. Sau đây là mô hình phát triển tính toán song song tại Mỹ 10 Petaflops 1 Petaflops Trung tâm nghiên cứu quốc gia 100 Teraflops 20 Teraflops 'Viện nghiên cứu lớn 10 Teraflops 4 Teraflops Bộ phận 1 Terafiop: nhóm nghiên cứu Hình 1.2: Hiệu năng tính toán của các cấp độ trung tâm tính toan song song Trong đó 1 flops là một phép tính thực hiện trên một giây - 1Teraflops = 10° flops - 1Petaflops x 10” flops Máy tính cá nhân mạnh hiện nay tính được khoảng 10! flops Hình 6.4: Phân rã tối da, mỗi tiến trình xử lý một nút Hình 6.5: Truyền thông giữa các tiến trình láng giéng 75 Ilinh 6.6: Tích tụ bài toán vào p tiến trình, mỗi tiến trình xử lý m nút 76 Hình 6.8: Kết quả tính toán số tại một vài bước lặp của mô hình tính toán song song.9: Giao diện chương trình điêu khiển tiễn trình.10: Nhập vảo tệp cần thực hiện 80 Hình 6.11: Nhập cầu hình máy phân tin 80 Hình 6.12: Nhập cấu hình một máy 80 Hình 6.13: Danh sách các máy đã được khởi tạo.14: Kết quả sau khi tính toán.15: Lỗi khi không nhập tệp cần thực hiện 82 Hình 6.16: Lỗi khi không nhập vào cấu hình máy tính song song 82 CHUONG 1 NHU CAU TINH TOAN SONG SONG TRONG KHOA HOC TÍNH TOÁN vA CO HOC 1.1 Dinh luat Moore về sự phát triển tốc độ của bộ xử lý Ngay từ những ngày đầu trong qua trinh phat triển của máy tỉnh điện tử, năm 1965, Gordon Moore đã đưa ra định luật nêu rằng tốc độ xử lý của máy tính sẽ tăng lên gấp đôi sau mỗi một năm. Đây chính là luật Moore nồi tiếng.
Số lượng đèn điện tir Bộ xử ý Pentum®4 100,000,000 Bộ xử ý Pendum® HI Bộ xử lý Pemtlum® II 10.