CHƯƠNG 1. TỔNG QUAN VỀ TÍNH TOÁN SONG SONG 1.1 CÁC MÔ HÌNH TÍNH TOÁN SONG SONG Có nhiều cách phân loại các kiến trúc tính toán khác nhau trong đó sự phân loại của M. Flynn được dùng phổ biến nhất. Flynn phân loại kiến trúc máy tính dựa trên một số đặc tính như: số lượng bộ xử lý, số lượng các chương trình chúng có thể thực hiện và cấu trúc của bộ nhớ.
Sự phân loại này đã dẫn đến bốn mô hình kiến trúc tính toán như sau: 1.1 Mô hình SISD (Single Instruction, Single Data) Những máy tính SISD chỉ có một CPU mà tại một thời điểm chúng chỉ thực hiện duy nhất một lệnh (Single Instruction) và chỉ có thể xử lý một đối tượng dữ liệu (Single Data). Control Signals Arithmetic Control Unit Processor Instruction Results Data Stream Memory Hình 1. Mô hình máy tính SISD Chẳng hạn, khi thực hiện phép tính C = A + B và A = B*2 thì máy sẽ thực hiện tuần tự như sau: 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Mô hình SISD chính là mô hình máy tính truyền thống kiểu Von Neumann.2 Mô hình SIMD (Single Instruction, Multiple Data) Những máy tính SIMD có một bộ điều khiển và chỉ thực hiện một lệnh tại một thời điểm nhưng chúng có nhiều phần tử xử lý. Control Unit Cotrol signals Cotrol signals Processing Processing Processing Element 1 Element 2 Element 3 Hình 1.
Mô hình máy tính SIMD Bộ điều khiển phát ra tín hiệu điều khiển cho các phần tử xử lý và các phần tử xử lý này sẽ thực hiện cùng một thao tác trên các đối tượng dữ liệu khác nhau.3 Mô hình MISD (Multiple Instruction, Single Data) Máy tính loại MISD là ngược lại với SIMD. Máy tính MISD có thể thực hiện nhiều chương trình (nhiều lệnh) trên cùng một mục dữ liệu, nên còn 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp được gọi là MPSD (đa chương trình, đơn luồng dữ liệu). Kiến trúc kiểu này có thể chia thành hai nhóm: Lớp các máy tính yêu cầu những bộ xử lý khác nhau có thể nhận được những lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. Instruction Stream 1 Control Unit1 Arithmetic Processor 1 Instruction Stream2 Arithmetic Data Control Unit 2 stream Processor 2 Instruction Stream n Arithmetic Control Unit n Processor n Hình 1.
Mô hình MISD Lớp 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.4 Mô hình MIMD (Multiple Instruction, Multiple Data) MIMD là một hệ thống đa bộ xử lý hoặc đa máy tính. Mỗi bộ xử lý trong hệ thống này có một bộ điều khiển riêng. 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Instruction Stream 1 Control Unit1 Arithmetic Data Stream 1 Processor 1 Instruction Stream2 Arithmetic Data Stream 2 Control Unit 2 Processor 2 Instruction Stream n Control Unit n Arithmetic Data Stream n Processor n Hình 1. Mô hình máy tính MIMD Hệ thống MIMD có các đặc trưng sau: Chúng phân tán tiến trình cho một số bộ xử lý độc lập.
Tất cả các bộ xử lý chia sẻ tài nguyên được lưu trữ trong bộ nhớ chính. Các bộ xử lý hoạt động đồng thời và độc lập với nhau. Mỗi bộ xử lý chạy một chương trình riêng.2 MỘT SỐ KỸ THUẬT PHÂN RÃ TRONG TÍNH TOÁN SONG SONG Quá trình phân chia một bài toán thành các bài toán nhỏ hơn, một số hoặc tất cả các bài toán nhỏ đó có thể được thực hiện song song, được gọi là phân rã. Việc thực hiện đồng thời nhiều tính toán là chìa khóa để giảm thời 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp gian cần thiết để giải quyết toàn bộ bài toán.
Các bài toán có thể có kích thước tùy ý, nhưng một khi đã xác định, chúng được coi là đơn vị chia của bài toán. Các bài toán được phân rã có thể có kích thước không giống nhau. Trong mục này, chúng ta sẽ mô tả một số kỹ thuật phân rã thường được sử dụng để đạt được sự tương tranh. Đây không phải là đầy đủ tất cả các kỹ thuật phân rã có thể có.
Ngoài ra, mỗi một phân rã không phải lúc nào cũng dẫn đến một thuật toán song song tốt nhất cho bài toán xác định. Mặc dù có những thiếu sót song các kỹ thuật phân rã mô tả trong phần này thường tạo một khởi đầu tốt cho nhiều bài toán và sự kết hợp của các kỹ thuật này có thể được sử dụng để có được sự phân rã hiệu quả cho nhiều bài toán. Các kỹ thuật phân rã bao gồm: phân rã đệ quy (recursive decomposition), phân rã dữ liệu (data-decomposition) và phân rã thăm dò (exploratory decomposition). Phân rã đệ quy Phân rã đệ quy là một phương pháp đạt được sự tương tranh trong các bài toán giải được bằng chiến lược chia để trị.
Trong kỹ thuật này, để giải một bài toán các thuật toán gọi đến chính nó một hoặc nhiều lần để xử lý các bài toán con liên quan. Đầu tiên, ta chia bài toán thành các bài toán con tương tự với bài toán ban đầu nhưng kích thước nhỏ hơn. Sau đó giải đệ quy các bài toán con và kết hợp các lời giải để được lời giải cho bài toán ban đầu.1: Xét bài toán sắp xếp dãy n phần tử A sử dụng thuật toán quicksort (giả sử n = 12). Quicksort là một thuật toán chia để trị mà bắt đầu chọn một phần tử trục x.
Sau đó phân hoạch dãy A thành 2 dãy con A0 và A1 sao cho các phần tử của A0 nhỏ hơn x và các phần tử của A1 lớn hơn hoặc bằng x. Đây là bước chia 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp của thuật toán. Sau đó, mỗi một dãy con A0 và A1 được sắp xếp bằng cách gọi đệ quy thủ tục quicksort. Phân rã đệ quy sắp xếp một dãy gồm 12 số Hình vẽ trên là đồ thị thực hiện của bài toán.
Lúc đầu chỉ có một dãy (là nút gốc của cây), và chúng ta chỉ cần dùng một quá trình duy nhất để phân rã nó. Hoàn thành quá trình phân rã ở nút gốc ta được hai dãy con (A0 và A1, tương ứng với hai nút đầu tiên của cây) và mỗi dãy có thể thực hiện phân rã song song với nhau. Tương tự như vậy, sự tương tranh tiếp tục tăng lên khi ta di chuyển dần xuống đến nút lá của cây. Phân rã dữ liệu Phân rã dữ liệu là một phương pháp mạnh và thường được sử dụng để tạo ra sự tương tranh trong các thuật toán chạy trên các bộ dữ liệu lớn.
Trong phương pháp này, sự phân rã các tính toán được thực hiện theo hai bước: Bước 1: Dữ liệu mà các tính toán sử dụng được phân rã; Bước 2: Các dữ liệu được phân rã này được sử dụng để tạo ra sự phân rã của các tính toán trong các công việc. 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Các thao tác mà những công việc này thực hiện trên các phân vùng dữ liệu khác nhau thường tương tự (như ví dụ nhân ma trận) hoặc được chọn từ một nhóm nhỏ các thao tác. Một số cách phân rã dữ liệu như sau: Phân hoạch dữ liệu đầu ra: Trong nhiều bài toán, mỗi yếu tố đầu ra có thể được tính toán một cách độc lập như một chức năng của đầu vào. Trong các bài toán như vậy, một phân hoạch của dữ liệu đầu ra tự động tạo ra một sự phân rã của các bài toán cho mỗi công việc, mỗi công việc được phân công tính toán một phần của đầu ra.
Ta xét bài toán nhân ma trận trong ví dụ dưới đây để minh họa cho việc phân rã dựa vào phân hoạch dữ liệu đầu ra.2: Xét bài toán nhân hai ma trận vuông A và B cấp n để được ma trận C.6 cho thấy sự phân rã bài toán này thành bốn công việc. Mỗi ma trận được xem là sự hợp thành của bốn khối hay các ma trận con được xác định bằng cách chia đôi kích thước của ma trận. Bốn ma trận con của C, kích thước của mỗi ma trận là (n/2) × (n/2), được tính toán một cách độc lập bởi bốn công việc là tổng của các ma trận con của A và B. Phân rã bài toán nhân ma trận a) Phân hoạch các ma trận đầu vào và đầu ra thành 2x2 ma trận con b) Một phân rã của phép nhân ma trận thành bốn công việc dựa trên các phân hoạch của các ma trận trong (a) 14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LUẬN VĂN CAO HỌC Song song hóa một số thuật toán tổ hợp Phân hoạch dữ liệu đầu vào: Phân hoạch dữ liệu đầu ra chỉ thực hiện được khi mỗi dữ liệu đầu ra có thể được tính toán như một chức năng của đầu vào.
Trong nhiều thuật toán, khó hoặc không thể phân hoạch được dữ liệu đầu ra. Ví dụ, trong tìm kiếm phần tử max, min hoặc tổng của một tập hợp số, dữ liệu đầu ra là một giá trị chưa xác định. Trong thuật toán sắp xếp, mỗi phần tử đầu ra riêng biệt không thể được xác định hiệu quả khi đứng riêng biệt. Trong các trường hợp như vậy, có thể sử dụng phân hoạch dữ liệu đầu vào để đạt được sự tương tranh.
Mỗi phân hoạch được tạo ra sẽ được tính toán bởi một công việc. Sau đó sẽ có một công việc để tổng hợp các kết quả. Ví dụ, trong tính tổng của một dãy N số sử dụng p bộ xử lý (N > p), ta có thể phân hoạch đầu vào thành p dãy con có kích thước gần bằng nhau. Mỗi công việc sẽ tính tổng các phần tử trong mỗi dãy con, sau đó p kết quả thành phần sẽ được tổng hợp lại thành kết quả cuối cùng.
Phân hoạch dữ liệu trung gian: Các thuật toán thường được cấu trúc như những tính toán nhiều tầng sao cho dữ liệu đầu ra của tầng này là đầu vào của tầng tiếp theo. Sự phân rã như vậy của một thuật toán có thể suy ra từ việc phân hoạch dữ liệu đầu vào hoặc dữ liệu đầu ra của một tầng trung gian của thuật toán. Việc phân hoạch dữ liệu trung gian đôi khi có thể đạt được sự tương tranh cao hơn so với việc phân hoạch dữ liệu đầu vào hoặc dữ liệu đầu ra.