Vấn đề thiết kế giải thuật cho các hệ xử lý song song

Bài viết trình bày quá trình phân rã các chức năng lớn thành các nhiệm vụ con phù hợp với các thông số ràng buộc được kiểm soát. Tiếp theo là bước liên kết nhiệm vụ theo các thông số ràng buộc ở bước trước. Đồng thời bài viết đưa ra một số phương thức tối ưu nhằm phân rã và liên kết các nhiệm vụ trong hệ xử lý song song đa dạng CPU, là dạng có hiệu quả nâng cao hiện nay.
Nội dung trích xuất từ tài liệu:
Vấn đề thiết kế giải thuật cho các hệ xử lý song songTạp chí Khoa học-Công nghệ Thủy sản Số 2/2006Trường Đại học Thủy sảnVẤN ĐỀ THIẾT KẾ GIẢI THUẬT CHO CÁC HỆ XỬ LÝ SONG SONGNguyễn Minh Ngọc, Nguyễn Hữu TrọngTrường Đại học Thuỷ sảnTrong các hệ xử lý song song điều quan trọng nhất là tăng tốc độ xử lý lên mức tối đa. Để làmđược điều đó, cần phải thực hiện được quá trình phân rã các chức năng lớn thành các nhiệm vụ conthật phù hợp với các thông số ràng buộc được kiểm soát. Tiếp theo là bước liên kết nhiệm vụ theo cácthông số ràng buộc ở bước trước. Đây là các quá trình rất phức tạp, đặc biệt đối với các hệ phi tuyến.Trong phần này đưa ra một số phương thức tối ưu nhằm phân rã và liên kết các nhiệm vụ trong hệ xửlý song song dạng đa CPU, là dạng có hiệu năng cao hiện nay.1. ĐẶT VẤN ĐỀPhân rãTrong quá trình thiết kế giải thuật cho các hệ xử lý song songVấnchúng ta phải nêu lên được tính song song, tính biến đổi được vàtính địa phương trong các giải thuật song song cần thiết kế.Liên kết thôngCần phải khẳng định rằng việc thiết kế các giải thuật songsong không phải là một công việc đơn giản. Vì vậy trong việc thiếtTíchkế các giải thuật chúng ta phải thiết kế một cách có phươngpháp, đưa ra được một số phương án thiết kế và đồng thời cungÁnhcấp thông tin ước lượng cho các phương án đó. Chúng ta cầnmô tả các cách tiếp cận và minh hoạ những ứng dụng của cáchtiếp cận đó tới các vấn đề trong việc thiết kế các giải thuật. Thiếtkế giải thuật song song có thể phải trải qua các giai đoạn đượcHình 1: Mô tả giải thuật song songminhhọa trong hình 1 là: Phân rã chức năng, thiết lập giao tiếp,tích tụ và ánh xạ [1,3].2. GIAI ĐOẠN PHÂN RÃ CHỨC NĂNGGiai đoạn phân rã là một giai đoạn thiết kế để phân tích rõ những tình huống có thể thực hiện songsong với nhau. Việc phân rã một vấn đề thành các nhiệm vụ nhỏ nhằm làm cho vấn đề đó được giảiquyết linh hoạt hơn theo những giải thuật song song đã có. Có thể sử dụng phương án phân rã theomiền (Domain Decomposition) hoặc phương án phân rã theo chức năng (Function Decomposition).Sự phân rã theo miền là đề cập tới việc phân ly bài toán, vì thế trước tiên chúng ta quan tâm đếnviệc phân chia dữ liệu liên quan đến bài toán. Nếu có thể chúng ta chia dữ liệu này thành những phầnnhỏ xấp xỉ bằng nhau. Tiếp theo, chúng ta phân chia các tính toán sẽ phải thực hiện, và phải phânchia dữ liệu cho các công việc tương ứng. Sự phân chia này tạo ra một số nhiệm vụ, mà mỗi nhiệmvụ bao gồm một dữ liệu và mộttập hợp các thao tác trên dữliệu đó. Một thao tác có thể yêucầu dữ liệu từ một vài nhiệm vụkhác, trong trường hợp này, liênkết thông tin được yêu cầu đểtrao đổi dữ liệu giữa các nhiệmvụ xác định.Hình 2 minh họa sự phânHình 2: Phân rã theo miền cho một bài toán bao gồm một lưới ba chiều.rã theo miền trong một bài toánđơn giản bao gồm một lưới ba chiều. (lưới này có thể là mô hình khí quyển trong một mô hình thờitiết, hoặc một không gian ba chiều trong xử lý hình ảnh [2, 4, 6]). Việc tính toán được thực hiện lặp lạinhiều lần trên mỗi điểm của lưới. Sự phân rã theo các chiều x, y, và z đều có thể thực hiện được. Ởgiai đoạn thiết kế ban đầu chúng ta công nhận một điều rằng các bài toán đều có thể phân rã, vàtrong trường hợp này chúng ta định nghĩa một công việc là một mắt lưới. Tại mỗi một nhịp thời gianmỗi nhiệm vụ duy trì một trạng thái của nó mà các giá trị của các trạng thái này phục vụ cho việc tínhtoán của nhịp thời gian sau.Sự phân rã có thể là một - hai - và ba chiều, trong trường hợp này dữ liệu có liên qua đến mộtnhiệm vụ đơn được kết hợp. Sự phân rã ba chiều cho ta tính mềm dẻo hơn.Sự phân rã theo chức năng đưa ra một phương pháp khác để giải quyết các bài toán. Theophương pháp này, việc tính toán sẽ được quan tâm nhiều hơn so với việc thao tác dữ liệu. Sau khichúng ta phân chia việc tính toán thành những nhiệm vụ tách rời được nhau, thì ta sẽ thực hiện tiếp13Tạp chí Khoa học-Công nghệ Thủy sản Số 2/2006Trường Đại học Thủy sảnviệc phân chia dữ liệu cho từng nhiệm vụ này. Như vậy, phương pháp phân rã theo miền tạo ra nềntảng cho các thuật toán song song, thì phương pháp phân rã theo chức năng là một phương pháp tốthơn trong việc liên kết các nhiệm vụ để giải quyết bài toán.Hầu hết các bài toán khi được sử dụng phương pháp phân rã theo chức năng đều phù hợp.Trong hình 3 mô tả một phương pháp tìm kiếm các nút trên cây phù hợp với yêu cầu. Thuật toán nàykhông có bất kỳ một cấu trúc dữ liệu rõ ràng nào để có thể phân rã. Tuy nhiên, sự phân rã finegrained (như các tế bào) có thể được sử dụng để phânrã bài toán. Thoạt tiên, một nhiệm vụ đơn được tạo racho gốc của cây. Một nhiệm vụ ước lượng nút của nómô hình khí quyểnvà sau đó, nếu nút đó không phải là một lá cây, sẽ tạora một nhiệm vụ mới cho mỗi lời gọi tìm kiếm (cây con).Mỗi một mô hình thành phần được xem như mộtnhiệm vụ riêng biệt, có thể được đặt song song hoábởi sự phân chia theo miền. Các mũi tên biểu diễn sựbiến đổi dữ l ...