Luận văn thạc sĩ một số phương pháp thiết kế thuật toán cơ bản trong tính toán song song và ứng dụng

Luận văn thạc sĩ toán học nghiên cứu một số phương pháp thiết kế thuật toán cơ bản trong tính toán song song và ứng dụng, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải

• Tác giả: Ngô Thị Minh Nguyệt
• Người hướng dẫn: PGS. Nguyễn Hữu Điển
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Cơ sở toán cho tin học
• Đề tài: Phương Pháp Thiết Kế Thuật Toán Trong Tính Toán Song Song
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• 1. Chương 1: TÍNH TOÁN SONG SONG
• 1.1. Tổng quan về xử lý song song
• 1.2. Các mô hình lập trình song song
• 1.3. Mô hình chia sẻ bộ nhớ
• 1.4. Mô hình luồng
• 1.5. Mô hình truyền thông điệp
• 1.6. Mô hình phân hoạch dữ liệu
• 1.7. Thiết kế và đánh giá thuật toán song song
• 1.8. Định nghĩa thuật toán song song
• 1.9. Các nguyên lý thiết kế thuật toán song song
• 1.10. Các cách tiếp cận trong thiết kế thuật toán song song
• 1.11. Phân tích và đánh giá thuật toán song song
• 1.12. Mô hình lập trình truyền thông điệp – MPI song song
• 1.13. Giới thiệu mô hình truyền thông điệp
• 1.14. Lập trình truyền thông điệp - MPI
• 1.15. Cấu trúc chương trình MPI
• 2. Chương 2: SONG SONG HÓA THUẬT TOÁN TÌM XÂU CON CHUNG DÀI NHẤT
• 2.1. Bài toán tìm xâu con chung dài nhất
• 2.2. Thuật toán quy hoạch động giải bài toán tìm xâu con chung dài nhất của hai xâu
• 2.3. Phương pháp phần tử trội trong bài toán xâu con chung dài nhất
• 2.4. Phương pháp song song trong bài toán xâu con chung dài nhất
• 2.5. Kết luận chương
• 3. Chương 3: KẾT QUẢ THỰC NGHIỆM
• 3.1. Bộ dữ liệu
• 3.2. Môi trường chạy
• 3.3. Kết quả chạy thực nghiệm
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về phương pháp thiết kế thuật toán trong tính toán song song

Trong bối cảnh công nghệ thông tin phát triển mạnh mẽ, thuật toán song song đã trở thành một phần không thể thiếu trong việc tối ưu hóa hiệu suất tính toán. Phương pháp thiết kế thuật toán trong tính toán song song không chỉ giúp giảm thời gian xử lý mà còn nâng cao khả năng xử lý của hệ thống. Việc hiểu rõ các nguyên lý và mô hình thiết kế là rất quan trọng để phát triển các ứng dụng hiệu quả.

1.1. Định nghĩa và vai trò của thuật toán song song

Thuật toán song song là một phương pháp xử lý thông tin trong đó nhiều đơn vị dữ liệu được xử lý đồng thời. Điều này giúp giải quyết các bài toán phức tạp một cách nhanh chóng và hiệu quả hơn. Việc áp dụng tính toán song song trong các lĩnh vực như khoa học máy tính, tài chính, và trí tuệ nhân tạo đã chứng minh được giá trị của nó.

1.2. Lịch sử phát triển của tính toán song song

Từ những năm 70, khái niệm về thiết kế thuật toán song song đã được hình thành. Các nhà khoa học đã nghiên cứu và phát triển nhiều mô hình khác nhau để tối ưu hóa khả năng xử lý của máy tính. Sự phát triển này đã mở ra nhiều cơ hội mới trong việc giải quyết các bài toán lớn mà trước đây không thể thực hiện được.

II. Các thách thức trong thiết kế thuật toán song song

Mặc dù có nhiều lợi ích, việc thiết kế thuật toán song song cũng gặp phải nhiều thách thức. Các vấn đề như đồng bộ hóa, phân phối dữ liệu và quản lý tài nguyên là những yếu tố quan trọng cần được xem xét. Hiểu rõ các thách thức này sẽ giúp các nhà phát triển tìm ra giải pháp hiệu quả hơn.

2.1. Vấn đề đồng bộ hóa trong thuật toán song song

Đồng bộ hóa là một trong những thách thức lớn nhất trong tính toán song song. Khi nhiều bộ xử lý cùng truy cập vào một tài nguyên chung, việc đảm bảo tính nhất quán và tránh xung đột là rất quan trọng. Các kỹ thuật như khóa và semaphore thường được sử dụng để giải quyết vấn đề này.

2.2. Phân phối dữ liệu và quản lý tài nguyên

Phân phối dữ liệu hiệu quả là một yếu tố quyết định đến hiệu suất của thuật toán song song. Việc lựa chọn mô hình phân phối phù hợp có thể giúp giảm thiểu độ trễ và tăng tốc độ xử lý. Ngoài ra, quản lý tài nguyên cũng cần được tối ưu hóa để đảm bảo rằng tất cả các bộ xử lý đều hoạt động hiệu quả.

III. Phương pháp thiết kế thuật toán song song hiệu quả

Để thiết kế một thuật toán song song hiệu quả, cần áp dụng các phương pháp và nguyên lý cụ thể. Các phương pháp này không chỉ giúp tối ưu hóa hiệu suất mà còn giảm thiểu độ phức tạp trong quá trình phát triển.

3.1. Nguyên lý phân tán trong thiết kế thuật toán

Nguyên lý phân tán là một trong những phương pháp quan trọng trong thiết kế thuật toán song song. Bằng cách chia nhỏ bài toán thành các phần độc lập, có thể xử lý đồng thời trên nhiều bộ xử lý, từ đó giảm thiểu thời gian xử lý tổng thể.

3.2. Sử dụng mô hình lập trình song song

Mô hình lập trình như MPI (Message Passing Interface) và OpenMP là những công cụ hữu ích trong việc phát triển thuật toán song song. Những mô hình này cung cấp các phương thức để quản lý và điều phối các tác vụ song song, giúp tối ưu hóa hiệu suất tính toán.

IV. Ứng dụng thực tiễn của thuật toán song song

Các ứng dụng của tính toán song song rất đa dạng, từ khoa học máy tính đến tài chính và y tế. Việc áp dụng các thuật toán song song đã giúp giải quyết nhiều bài toán phức tạp trong thời gian ngắn hơn.

4.1. Ứng dụng trong khoa học máy tính

Trong lĩnh vực khoa học máy tính, thuật toán song song được sử dụng để xử lý dữ liệu lớn, mô phỏng và phân tích. Các ứng dụng này yêu cầu khả năng tính toán cao và thường xuyên phải xử lý hàng triệu phép toán đồng thời.

4.2. Ứng dụng trong tài chính và y tế

Trong tài chính, tính toán song song giúp phân tích rủi ro và dự đoán xu hướng thị trường. Trong y tế, nó hỗ trợ trong việc phân tích dữ liệu bệnh nhân và mô phỏng các phương pháp điều trị, từ đó nâng cao chất lượng dịch vụ.

V. Kết luận và tương lai của thiết kế thuật toán song song

Thiết kế thuật toán song song đang ngày càng trở nên quan trọng trong bối cảnh công nghệ phát triển nhanh chóng. Tương lai của lĩnh vực này hứa hẹn sẽ mang lại nhiều đột phá mới, giúp giải quyết các bài toán phức tạp hơn trong thời gian ngắn hơn.

5.1. Xu hướng phát triển trong thiết kế thuật toán

Xu hướng hiện nay là phát triển các thuật toán song song có khả năng tự động tối ưu hóa hiệu suất. Các công nghệ mới như trí tuệ nhân tạo và học máy đang được áp dụng để cải thiện khả năng xử lý và phân tích dữ liệu.

5.2. Thách thức trong tương lai

Mặc dù có nhiều tiềm năng, việc phát triển thuật toán song song cũng đối mặt với nhiều thách thức như độ phức tạp trong lập trình và yêu cầu về phần cứng. Cần có những nghiên cứu và phát triển liên tục để vượt qua những thách thức này.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của ngành Công nghệ thông tin, tính toán song song đã trở thành một lĩnh vực trọng điểm nhằm giải quyết các bài toán có khối lượng tính toán lớn mà máy tính đơn lẻ không thể xử lý hiệu quả. Theo ước tính, các hệ thống máy tính song song hiện nay có thể chứa hàng nghìn bộ xử lý, giúp tăng tốc độ xử lý và độ an toàn trong tính toán. Tuy nhiên, để khai thác tối đa sức mạnh của các hệ thống này, việc thiết kế thuật toán song song phù hợp là rất cần thiết.

Luận văn tập trung nghiên cứu một số phương pháp thiết kế thuật toán cơ bản trong tính toán song song, đặc biệt là ứng dụng vào bài toán tìm dãy con chung dài nhất (Longest Common Subsequence - LCS) trong lĩnh vực tin sinh học. Bài toán này có ý nghĩa quan trọng trong việc phân tích dữ liệu sinh học với độ dài xâu ký tự có thể lên đến khoảng 10^12, đòi hỏi các giải thuật hiệu quả và khả năng xử lý song song để giảm thời gian tính toán.

Phạm vi nghiên cứu tập trung vào việc áp dụng các mô hình lập trình song song, đặc biệt là mô hình truyền thông điệp MPI, để song song hóa thuật toán tìm dãy con chung dài nhất cho nhiều xâu ký tự. Thời gian nghiên cứu chủ yếu trong giai đoạn 2008-2014 tại Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội. Kết quả nghiên cứu góp phần nâng cao hiệu quả tính toán trong các bài toán lớn, đặc biệt trong tin sinh học và các ứng dụng liên quan đến xử lý dữ liệu chuỗi.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Mô hình kiến trúc máy tính song song Flynn: Phân loại kiến trúc thành SISD, SIMD, MISD và MIMD, trong đó MIMD được sử dụng phổ biến nhất cho các hệ thống đa bộ xử lý hiện đại.
• Mô hình lập trình song song: Bao gồm mô hình chia sẻ bộ nhớ, mô hình luồng, mô hình truyền thông điệp và mô hình phân hoạch dữ liệu. Trong đó, mô hình truyền thông điệp (MPI) được lựa chọn làm nền tảng cho việc thiết kế và triển khai thuật toán song song.
• Nguyên lý thiết kế thuật toán song song: Bao gồm nguyên lý lập lịch, nguyên lý hình ống, nguyên lý chia để trị, nguyên lý đồ thị phụ thuộc dữ liệu và nguyên lý điều kiện tương tranh. Các nguyên lý này giúp phân chia công việc, đồng bộ tiến trình và tối ưu hóa hiệu suất tính toán.
• Phương pháp phần tử trội: Giúp giảm chi phí lưu trữ và tính toán trong bài toán tìm dãy con chung dài nhất bằng cách chỉ tập trung vào các điểm trội trong ma trận phương án thay vì toàn bộ ma trận.

Các khái niệm chính bao gồm: xâu con chung dài nhất (LCS), điểm khớp, điểm trội, điểm cha, mô hình MPI, hệ số tăng tốc, hiệu suất tính toán song song.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Sử dụng các bộ dữ liệu sinh học với độ dài xâu ký tự đa dạng từ khoảng 10^2 đến 10^12, bao gồm protein, ARN, gen và ADN.
• Phương pháp phân tích: Áp dụng thuật toán quy hoạch động để giải bài toán tìm dãy con chung dài nhất, kết hợp với phương pháp phần tử trội để tối ưu bộ nhớ và tính toán. Thuật toán được song song hóa dựa trên mô hình truyền thông điệp MPI, phân chia không gian tìm kiếm thành các ô độc lập để xử lý đồng thời trên nhiều bộ xử lý.
• Cỡ mẫu và chọn mẫu: Thực nghiệm được tiến hành trên các bộ dữ liệu với số lượng xâu từ 2 đến 8, độ dài xâu từ 64 đến 4096 ký tự, sử dụng từ 2 đến 8 bộ xử lý song song.
• Timeline nghiên cứu: Nghiên cứu và phát triển thuật toán từ năm 2008 đến 2014, với các bước chính gồm tổng quan lý thuyết, thiết kế thuật toán, triển khai mô hình MPI, thực nghiệm và đánh giá kết quả.

Phương pháp nghiên cứu kết hợp lý thuyết, thiết kế thuật toán và thực nghiệm trên môi trường tính toán hiệu năng cao nhằm đánh giá hiệu quả của giải pháp.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả của phương pháp phần tử trội: Phương pháp này giúp giảm đáng kể kích thước ma trận phương án trong bài toán tìm dãy con chung dài nhất, từ đó giảm bộ nhớ sử dụng và tăng tốc độ tính toán. Số lượng phần tử trội ít hơn rất nhiều so với tổng số điểm trong ma trận, giúp tiết kiệm tài nguyên.

2. Tăng tốc đáng kể nhờ song song hóa: Thuật toán song song dựa trên mô hình MPI cho thấy thời gian chạy giảm rõ rệt khi tăng số bộ xử lý. Ví dụ, với 2 xâu độ dài 4096 ký tự trên bảng chữ cái 20 ký tự, hệ số tăng tốc đạt gần bằng số bộ xử lý sử dụng, thể hiện hiệu quả phân chia công việc và đồng bộ tốt.

3. Phân chia không gian tìm kiếm thành các ô độc lập: Việc chia không gian tìm kiếm thành các ô chữ nhật độc lập cho phép các bộ xử lý thực hiện song song mà không gây xung đột dữ liệu. Với 4 bộ xử lý, số bước tuần tự thực hiện là 7, thấp hơn nhiều so với thuật toán tuần tự.

4. Khả năng mở rộng với số lượng xâu và bộ xử lý: Khi số xâu ký tự tăng lên, số lượng ô độc lập cũng tăng, giúp tận dụng tối đa khả năng song song của hệ thống. Số bước tuần tự được tính theo công thức $d \times (k-1) + 1$, với $d$ là số xâu và $k$ là số bộ xử lý, cho thấy thuật toán có thể mở rộng hiệu quả.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả trên là do việc áp dụng mô hình truyền thông điệp MPI giúp phân phối công việc rõ ràng, đồng thời phương pháp phần tử trội giảm thiểu bộ nhớ và tính toán không cần thiết. So với các nghiên cứu trước đây chỉ tập trung vào thuật toán tuần tự hoặc song song hóa đơn giản, giải pháp này tận dụng tốt hơn kiến trúc phần cứng hiện đại.

Kết quả thực nghiệm được trình bày qua các biểu đồ thời gian chạy, hệ số tăng tốc và hiệu suất trên các bộ dữ liệu khác nhau, minh họa rõ ràng sự cải thiện khi tăng số bộ xử lý. So với các phương pháp truyền thống, phương pháp này giảm thời gian tính toán từ hàng chục phút xuống còn vài phút hoặc giây tùy theo cấu hình.

Ý nghĩa của nghiên cứu không chỉ nằm ở việc cải thiện thuật toán tìm dãy con chung dài nhất mà còn mở rộng khả năng ứng dụng trong các bài toán tính toán song song phức tạp khác trong tin sinh học và khoa học máy tính.

Đề xuất và khuyến nghị

1. Tăng cường ứng dụng mô hình MPI trong các bài toán tính toán song song: Khuyến nghị các nhà nghiên cứu và phát triển phần mềm tính toán hiệu năng cao áp dụng mô hình truyền thông điệp MPI để tận dụng tối đa khả năng mở rộng và hiệu suất của hệ thống đa bộ xử lý.

2. Phát triển thêm các thuật toán song song dựa trên phương pháp phần tử trội: Động viên nghiên cứu mở rộng phương pháp phần tử trội cho các bài toán tương tự trong xử lý chuỗi và dữ liệu lớn nhằm giảm chi phí bộ nhớ và tăng tốc độ tính toán.

3. Tối ưu hóa phân chia không gian tìm kiếm và đồng bộ tiến trình: Đề xuất cải tiến thuật toán phân chia không gian tìm kiếm thành các ô độc lập phù hợp với số lượng bộ xử lý thực tế, đồng thời nâng cao hiệu quả đồng bộ để giảm thiểu thời gian chờ giữa các bước tuần tự.

4. Triển khai thực nghiệm trên các hệ thống tính toán hiệu năng cao hiện đại: Khuyến nghị thực hiện các thử nghiệm trên các cụm máy tính và siêu máy tính hiện đại để đánh giá khả năng mở rộng và hiệu quả thực tế của thuật toán trong môi trường đa bộ xử lý lớn.

Các giải pháp trên nên được thực hiện trong vòng 1-2 năm tới bởi các nhóm nghiên cứu và trung tâm tính toán hiệu năng cao nhằm nâng cao năng lực xử lý các bài toán lớn trong tin sinh học và các lĩnh vực liên quan.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành khoa học máy tính, tin sinh học: Luận văn cung cấp kiến thức sâu về thuật toán song song, mô hình MPI và ứng dụng trong bài toán tìm dãy con chung dài nhất, hỗ trợ phát triển các đề tài nghiên cứu liên quan.

2. Kỹ sư phát triển phần mềm tính toán hiệu năng cao: Các kỹ sư có thể áp dụng các phương pháp và thuật toán được trình bày để tối ưu hóa phần mềm xử lý dữ liệu lớn, đặc biệt trong lĩnh vực sinh học phân tử và phân tích chuỗi.

3. Trung tâm tính toán hiệu năng cao và các tổ chức nghiên cứu: Luận văn cung cấp cơ sở lý thuyết và thực nghiệm để triển khai các giải pháp tính toán song song trên các hệ thống đa bộ xử lý, giúp nâng cao hiệu quả sử dụng tài nguyên.

4. Doanh nghiệp công nghệ và y sinh học: Các công ty phát triển công nghệ sinh học, phân tích dữ liệu gen có thể tham khảo để cải tiến các công cụ phân tích, rút ngắn thời gian xử lý và nâng cao độ chính xác.

Mỗi nhóm đối tượng sẽ nhận được lợi ích cụ thể như nâng cao kiến thức chuyên môn, cải thiện hiệu suất phần mềm, tối ưu hóa tài nguyên tính toán và tăng cường khả năng ứng dụng thực tế.

Câu hỏi thường gặp

1. Tại sao cần sử dụng tính toán song song trong bài toán tìm dãy con chung dài nhất?
   Tính toán song song giúp xử lý các bài toán có kích thước dữ liệu rất lớn mà thuật toán tuần tự không thể giải quyết hiệu quả do giới hạn về thời gian và bộ nhớ. Ví dụ, với các chuỗi ADN có độ dài lên đến 10^12, song song hóa giúp giảm thời gian tính toán từ hàng giờ xuống còn vài phút.

2. Phương pháp phần tử trội có ưu điểm gì so với phương pháp truyền thống?
   Phương pháp phần tử trội chỉ lưu trữ và tính toán trên các điểm quan trọng trong ma trận phương án, giảm đáng kể bộ nhớ và chi phí tính toán so với việc xử lý toàn bộ ma trận, đặc biệt hiệu quả khi số lượng phần tử trội nhỏ hơn nhiều so với tổng số điểm.

3. Mô hình truyền thông điệp MPI có những tính năng nổi bật nào?
   MPI hỗ trợ giao tiếp giữa các tiến trình trên các máy tính phân tán, có khả năng mở rộng cao, linh hoạt, hỗ trợ truyền thông đồng bộ và bất đồng bộ, quản lý tiến trình động và vào/ra song song, phù hợp với các hệ thống tính toán hiệu năng cao.

4. Làm thế nào để phân chia không gian tìm kiếm thành các ô độc lập trong thuật toán song song?
   Không gian tìm kiếm được chia thành các ô chữ nhật dựa trên số bộ xử lý và số chiều của dữ liệu. Các ô không trội hơn nhau có thể tính toán đồng thời trên các bộ xử lý khác nhau, giúp tận dụng tối đa khả năng song song và giảm thời gian chờ đồng bộ.

5. Luật Amdahl ảnh hưởng như thế nào đến hiệu suất của thuật toán song song?
   Luật Amdahl chỉ ra rằng hiệu suất tăng tốc của thuật toán song song bị giới hạn bởi phần không thể song song hóa của bài toán. Do đó, dù tăng số bộ xử lý, tốc độ xử lý không thể tăng tuyến tính vô hạn, điều này cần được cân nhắc khi thiết kế và triển khai thuật toán.

Kết luận

• Luận văn đã trình bày các phương pháp thiết kế thuật toán cơ bản trong tính toán song song, tập trung vào bài toán tìm dãy con chung dài nhất với ứng dụng trong tin sinh học.
• Phương pháp phần tử trội giúp giảm chi phí bộ nhớ và tăng tốc độ tính toán đáng kể so với phương pháp truyền thống.
• Thuật toán song song dựa trên mô hình MPI và phân chia không gian tìm kiếm thành các ô độc lập cho hiệu suất cao, khả năng mở rộng tốt với số lượng bộ xử lý và số xâu tăng lên.
• Kết quả thực nghiệm chứng minh hiệu quả vượt trội của giải pháp so với thuật toán tuần tự, đặc biệt trên các bộ dữ liệu lớn và phức tạp.
• Đề xuất các hướng phát triển tiếp theo bao gồm mở rộng ứng dụng mô hình MPI, tối ưu hóa phân chia công việc và triển khai trên các hệ thống tính toán hiệu năng cao hiện đại.

Để tiếp tục phát triển đề tài, các nhà nghiên cứu và kỹ sư được khuyến khích áp dụng và thử nghiệm thuật toán trên các môi trường tính toán đa bộ xử lý hiện đại, đồng thời mở rộng nghiên cứu sang các bài toán tính toán song song khác trong khoa học và công nghiệp. Hãy bắt đầu áp dụng các phương pháp này để nâng cao hiệu quả xử lý dữ liệu lớn trong lĩnh vực của bạn ngay hôm nay!

Trích đoạn nội dung tài liệu

Chương 1 – TÍNH TOÁN SONG SONG 1. Tổng quan về xử lý song song Trong những thập niên 60, nền tảng để thiết kế máy tính đều dựa trên mô hình của John Von Neumann (Hình 1.10), 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 được thực thi. [14] Bộ nhớ Câu lệnh Ghi dữ liệu Đọc dữ liệu Bộ xử lý Hình 1. Mô tả kiến trúc Von Neumann Với những bài toán yêu cầu về khả năng tính toán và lưu trữ lớn thì mô hình kiến trúc này còn hạn chế.

Để 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 đưa ra kiến trúc mới, với ý tưởng kết hợp nhiều bộ xử lý vào trong một máy tính, hay gọi là xử lý song song 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 mạng (máy tính song song). Kể từ lúc này, để khai thác được sức mạnh tiềm tàng trong mô hình máy tính nhiều bộ xử lý song song, cũng như trong mô hình mạng máy tính xử lý song song thì việc xây dựng thiết kế giải thuật song song là điều quan trọng. Giải thuật song song có thể phân rã công việc trên các phần tử xử lý khác nhau 1. Một số khái niệm về xử lý song song Định nghĩa về xử lý song song Tính toán song song hay xử lý song song: là quá trình xử lý thông tin trong đó nhiều đơn vị dữ liệu được xử lý đồng thời bởi một hay nhiều bộ xử lý để giải quyết một bài toán.

[1] 3 TIEU LUAN MOI download : [e-mail] Máy tính song song là tập hợp các bộ xử lý kết nối với nhau theo một kiến trúc xác định để cùng hợp tác hoạt động và trao đổi dữ liệu. [1] Phân biệt xử lý song song và xử lý tuần tự Trong tính toán tuần tự với một bộ xử lý thì tại mỗi thời điểm chỉ được thực hiện một phép toán. Trong tính toán song song thì nhiều bộ xử lý cùng kết hợp với nhau để giải quyết cùng một bài toán cho nên giảm được thời gian xử lý vì mỗi thời điểm có thể thực hiện đồng thời nhiều phép toán. Mục đích của xử lý song song Thực hiện tính toán nhanh trên cơ sở sử dụng nhiều bộ xử lý đồng thời.

Cùng với tốc độ xử lý nhanh, việc xử lý song song cũng sẽ giải được những bài toán phức tạp yêu cầu khối lượng tính toán lớn. Vấn đề xử lý song song Liên quan trực tiếp đến kiến trúc máy tính, phần mềm hệ thống (hệ điều hành), giải thuật và ngôn ngữ lập trình, … Độ phức tạp Độ phức tạp của tính toán song song không chỉ phụ thuộc vào kích cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ xử lý được phép sử dụng trong hệ thống. Cài đặt giải thuật song song Để cài đặt các giải thuật song song trên các máy tính song song, phải sử dụng những ngôn ngữ lập trình song song như: OpenMP với C/C++, MPI với C/C++, v. Phân loại các kiến trúc của máy tinh song song 1.

Phân loại theo kiến trúc máy tính của Flynn. Một trong những phân loại hay được nhắc tới là của Flynn – 1966 [6]. Michael Flynn phân các kiến trúc máy tính thành bốn loại dựa vào sự phân phối luông dữ liệu (data stream ) và phân phối các luồng lệnh (instruction stream) trên mỗi bộ xử lý. 4 TIEU LUAN MOI download : [e-mail]  Mô hình SISD (đơn luồng lệnh, đơn luồng dữ liệu) Đây chính là kiến trúc tuần tự Von Neuman , máy tính SISD chỉ có một CPU, các dòng lệnh được thực hiện một cách tuần tự.

Hệ thống SISD (hình 1.2: trong đó tại mỗi thời điểm chỉ thực hiện một lệnh trên một mục dữ liệu) Hình 1.2: Mô hình máy SISD  Mô hình SIMD (Đơn luồng lệnh, đa dữ liệu ) Máy tính loại SIMD có một đơn vị điều khiển để điều khiển nhiều đơn vị xử lý thực hiện theo một luồng các câu lệnh. CPU phát sinh tín hiệu điều khiển tới tất cả các phần tử xử lý, những bộ xử lý này cùng thực hiện một phép toán trên các mục dữ liệu khác nhau.3: Mô hình máy tính SIMD  Mô hình MISD (Đa luồng lệnh, đơn dữ liệu) Máy tính MISD có thể thực hiện nhiều nhiều lệnh trên cùng một mục dữ liệu, 5 TIEU LUAN MOI download : [e-mail] - Các máy tính yêu cầu mỗi đơn vị xử lý (PU) nhận những lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. - Các máy tính có các luồng dữ liệu được chuyển tuần tự theo dãy các CPU liên tiếp gọi là kiến trúc hình ống xử lýtheo vector thông qua một dãy các bước, trong đó mỗi bước thực hiện một chức năng và sau đó chuyển kết quảcho PU thực hiện bước tiếp theo  Mô hình MIMD (đa luồng lệnh, đa luồng dữ liệu) Máy tính loại MIMD còn gọi là đa bộ xử lý, trong đó mỗi bộ xử lý có thể thực hiện những luồng lệnh khác nhau trên các luồng dữ liệu riêng. Hầu hết các hệ thống MIMD đều có bộ nhớ riêng và cũng có thể truy cập vào được bộ nhớ chung khi cần, do vậy giảm thiểu được sự trao đổi giữa các bộ xử lý trong hệ thống.4: Mô hình máy MIMD Đây là kiến trúc phức tạp nhất, nhưng nó là mô hình hỗ trợ xử lý song song cao nhất, bởi chúng có thể thực thi các lệnh khác nhau trên nhiều dòng dữ liệu khác nhau tại một thời điểm.

Theo Flynn: có hai họ kiến trúc quan trọng cho các máy tính song song: SIMD và MIMD. Những kiến trúc khác có thể xếp theo hai mẫu đó. Mục tiêu của xử lý song song là khai thác đến mức tối đa các khả năng sử dụng của các thiết bị phần cứng nhằm giải quyết nhanh những bài toán đặt ra trong thực tế. 6 TIEU LUAN MOI download : skknchat@gmail.

Phân loại theo mô hình bộ nhớ  Mô hình bộ nhớ chia sẻ Đặc điểm của máy tính song song loại này là các nút tính toán đều có thể truy nhập vào bộ nhớ dùng chung như là bộ nhó toàn cục. Nhiều bộ xử lý hoạt động độc lập nhưng cùng sử dụng chung một bộ nhớ, mỗi sự thay đổi nội dung các ngăn nhớ đều được các bộ xử lý biết. Ưu điểm chính của mô hình này là cung cấp một vúng nhớ toàn cục do đó dễ dàng cho việc lập trình về mặt sử dụng bộ nhớ đồng thời việc trao đổi thông tin giữa các modul tính toán là tương đối nhanh chóng và dễ dàng.5: Máy tính chia sẻ bộ nhớ Nhược điểm của mô hình này chính là sự mất cân đối giữa CPU và bộ nhớ. Việc tăng CPU làm tăng thêm lưu lượng trên đường dẫn từ bộ nhớ tới CPU.

 Mô hình bộ nhớ phân tán Mô hình này yêu cầu một mạng truyền thông để kết nối các bộ nhớ của các bộ vi xử lý. Mỗi CPU đều gắn với một bộ nhớ riêng và các thao tác của mỗi CPU trên bộ nhớ của mình thì không được các CPU khác biết tới. Ưu điểm của mô hình này là kích thước bộ nhớ cân bằng với số lượng các bộ xử lý.6: Máy tính bộ nhớ phân tán 7 TIEU LUAN MOI download : [e-mail] Nhược điểm chính của mô hình này chính là người lập trình phải tự thiết lập lấy phương thức trao đổi thông tin giữa các CPU trong quá trình tính toán mà việc này đôi khi là rất khó khăn.  Mô hình bộ nhớ lai.

Hầu hết các máy tính nhanh và lớn ngày nay đều xây dựng dựa trên sự kết hợp giữa kiến trúc chia sẻ bộ nhớ chung và bộ nhớ phân tán. Sự kết hợp đó tạo nên một máy tính với tên gọi máy tính có bộ nhớ lai 1. Song song hóa máy tính tuần tự Trong kiến trúc tuần tự có thể tận dụng tốc độ cực nhanh của bộ xử lý để thực hiện xử lý song song theo nguyên lý chia sẻ thời gian và chia sẻ tài nguyên. Các thanh ghi được sử dụng trực tiếp cho ALU.

Bộ nhớ cache được xem như vùng đệm giữa bộ xử lý chính. Sự song song hóa trong sự trao đổi dữ liệu theo cấu trúc phân cấp là cách khai thác chung để cải tiến hiệu quả xử lý của hệ hống. Các hệ điều hành của máy tính đơn bộ xử lý cho phép thực hiện song song dựa vào cách tiếp cận phần mềm. Trong cùng một khoảng thời gian, có nhiều tiến trình cùng truy cập vào dữ iệu từ những thiết bị vào/ra chung.

Phần lớn các chương trình đều có hai phần: phần vào/ra và các thành phần tính toán trong quá trình xử lý. Các hệ điều hành đa chương trình luân phiên thực hiện các chương trình khác nhau. Để thực hiện việc này hệ điều hành sử dụng Bộ lập lịch chia sẻ thời gian làm nhiệm vụ phân chia CPU cho mỗi tiến trình một khoảng thời gian cố định theo phương pháp quay vòng tròn. Bằng cách đó, tất cả các tiến trình đều được sẵn sàng để thực hiện trên cơ sở được phép sử dụng CPU và những tài nguyên khác của hệ thống.

Do vậy, về nguyên tắc việc phát triển những chương trình song song trên máy đơn bộ xử lý thực hiện được nếu có hệ điều hành cho phép nhiều tiến trình thực hiện, nghĩa là có thể xem hệ thống như là đa bộ xử lý. 8 TIEU LUAN MOI download : skknchat@gmail. Các mô hình lập trình song song Việc đưa ra một mô hình máy tính chung cho việc lập trình giúp cho việc thiết kế giải thuật giải thuật trở nên đơn giản hơn. Lập trình song song đưa thêm những khó khăn mới vào mô hình lập trình tuần tự.

Nếu chương trình được thực hiện ở mức thấp nhất thì không những số lệnh thực hiện là rất lớn mà nó còn phải quản lý trực tiếp quá trình thực hiện song song của hàng nghìn bộ xử lý và kết hợp hàng triệu tương tác liên bộ xử lý. Bởi vậy khả năng trừu tượng và tính toán module là các đặc tính rất quan trọng trong lập trình song song. Các mô hình thông dụng bao gồm: - Mô hình chia sẻ bộ nhớ. - Mô hình luồng.

- Mô hình truyền thông điệp. - Mô hình song song dữ liệu. Mô hình chia sẻ bộ nhớ Trong mô hình này, nhiệm vụ cùng chia sẻ một không gian địa chỉ chung có thể được truy cập đọc ghi theo phương thức không đồng bộ.Các cơ chế khác nhau như khóa (locks) và semaphore được điều khiển để truy cập đến bộ nhớ toàn cục.