CHƯƠNG 1. TỔNG QUAN VỀ XỬ LÝ SONG SONG VÀ BÀI TOÁN SẮP XẾP 1.1 Tổng quan về xử lí song song 1.1 Tính toán tuần tự và tính toán 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, với một bộ xử lí đơn được nối với một vùng lưu trữ làm bộ nhớ và tại cùng một thời điểm chỉ có một lệnh được thực thi. Đó là hình thức tính toán tuần tự [1]. Tuy nhiên, hiện nay khoa học kỹ thuật ngày càng phát triển, từ đó sẽ đặt ra nhiều bài toán với khối lượng tính toán rất lớn, trong đó có những bài toán mà kết quả chỉ có ý nghĩa nếu được hoàn thành trong thời gian cho phép.
Từ đó hình thành nên hệ thống xử lí song song. Xử lí song song là quá trình xử lí gồm nhiều tiến trình được kích hoạt đồng thời, được thực hiện trên nhiều bộ xử lí và cùng tham gia vào giải quyết một bài toán.2 dưới đây phần nào cho thấy cái nhìn khái quát về sự khác nhau giữa xử lí tuần tự và xử lí song song.1 Minh họa quá trình xử lí tuần tự Trong xử lí tuần tự (hình 1.1), một CPU sẽ thực hiện lần lượt các lệnh Si để giải quyết bài toán. Với xử lí song song (hình 1.2) các lệnh để giải quyết bài toán được chia ra thành các cụm độc lập, được gọi là các tiến trình và mỗi tiến trình sẽ được thực hiện trên một CPU khác nhau. 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Minh họa quá trình xử lí song song Mục đích xây dựng hệ thống xử lí song song là để thực hiện tính toán nhanh hơn trên cơ sở sử dụng đồng thời nhiều bộ xử lí để giải quyết được những bài toán phức tạp với yêu cầu khối lượng tính toán lớn.
Ví dụ các bài toán tính toán lớn như mô phỏng các hoạt động ở mức lượng tử, tính toán quỹ đạo chuyển động của vật thể trong không gian, dự báo thời tiết, các bài toán nghiên cứu trên ADN… Trong tính toán song song hiện nay, chúng ta có thể sử dụng hai mô hình chính: Thứ nhất là sử dụng các siêu máy tính với rất nhiều các bộ xử lí được tích hợp bên trong và được thiết kế đồng bộ cả về phần cứng lẫn phần mềm. Các công nghệ được áp dụng trong các siêu máy tính thường là các công nghệ tiên tiến làm cho giá thành của hệ thống siêu máy tính thường rất cao. Cách thứ hai là kết nối các đơn máy tính đồng bộ lại với nhau và cùng thực hiện bài toán, hệ thống các máy tính kết nối này là hệ thống tính toán song song phân cụm. Hệ thống này có ưu điểm là giá thành rẻ hơn do nó sử dụng các thiết bị thông thường và tính linh hoạt của hệ thống (số nút, số bộ xử lí, bộ nhớ, thiết bị mạng… đều mang tính tùy biến cao).
Sự phát triển mạnh mẽ của mạng máy tính, các công nghệ mạng hiện nay đã lấp đi sự hạn chế về truyền thông trong hệ thống máy tính song song phân cụm làm cho nó được phát triển rộng rãi. Các lĩnh vực sử dụng hệ thống tính toán song song phân cụm thường yêu cầu tính toán không quá lớn như xử lí ảnh, nhận dạng vân tay, tính toán kết cấu công trình, mô phỏng các thí nghiệm… 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Phần dưới đây sẽ trình bày về các mô hình máy tính song song cơ bản theo phân loại của Flynn giúp chúng ta có cái nhìn tổng quát hơn về các hệ thống song song.2 Kiến trúc máy tính song song Một hệ thống máy tính song song là một máy tính với nhiều hơn một bộ xử lí cho phép thực hiện đồng thời nhiều tiến trình. Định nghĩa này có thể bao quát được tất cả các siêu máy tính với hàng trăm bộ xử lí, các mạng máy tính trạm hay các hệ thống nhúng. Dựa vào sự phân biệt ở cách kết nối giữa các bộ xử lí (hay thành phần xử lí), giữa bộ xử lí và bộ nhớ mà có rất nhiều loại kiến trúc máy tính song song khác nhau.
Nhưng theo phân loại của Flynn dựa trên cấu trúc luồng lệnh và luồng dữ liệu thì có bốn kiến trúc điển hình [1] đó là: Hình 1.3 Phân loại Flynn về các kiến trúc song song SIMD- Single Instruction Multiple Data: Đơn lệnh đa dữ liệu. Đây là một kiểu máy tính song song mà các bộ xử lí thực hiện cùng một lệnh nhưng với các dữ liệu khác nhau. Mô hình này có ưu điểm là đơn giản trong thiết kế phần cứng cũng như phân mềm nhưng chỉ phù hợp để giải quyết các bài toán tương đối đặc thù có tính cân đối cao như trong xử lí như xử lí ảnh, các bài toán với các dữ liệu dạng vecto hoặc ma trận. Các thuật giải cho các đa máy tính thường chạy không hiệu quả trên các máy SIMD.
MIMD- Multiple Instruction Multiple Data: Đa lệnh đa dữ liệu. Đây là một mô hình kiến trúc máy tính song song thông dụng hiện nay. Với mô hình này thì 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com tất cả các bộ xử lí sẽ thực hiện các lệnh khác nhau với các dữ liệu riêng khác nhau. Sự thực thi các lệnh có thể theo cơ chế đồng bộ hoặc không đồng bộ, điều này giúp cho MIMD rất linh hoạt trong việc xử lí song song.
Tuy nhiên, cùng với tính linh hoạt của mình, mô hình MIMD cũng mang theo một sự phức tạp nhất định. Việc lập trình được những bài toán song song theo mô hình này đòi hỏi có nhiều công sức nghiên cứu, phân tích bài toán để tìm ra một cách phân rã tối ưu. Ngoài ra còn có hai loại mô hình khác theo phân loại của Flynn tuy nhiên ít thông dụng: SISD-Single Instruction Single Data: Đơn lệnh đơn dữ liệu và MISD- Multiple Instruction Single Data: Đa lệnh đơn dữ liệu. Với sự đa dạng của các mô hình kiến trúc máy tính song song, thì việc tổ chức và kết nối các bộ xử lí trong các mô hình cũng được quan tâm và nghiên cứu.
Hầu hết các máy tính với đa bộ xử lí đều phải đưa ra một cách để các bộ xử lí tương tác với nhau. Trong một số hệ thống, các bộ xử lí sử dụng kết nối mạng để truy cập vào bộ nhớ chia sẻ, nhưng cũng có một số hệ thống khác thì lại sử dụng phương thức gửi và nhận tin nhắn để truyền thông với nhau. Dưới đây là một số mạng kết nối được sử dụng trong các hệ thống máy tính song song.3 Một số mạng kết nối trên hệ thống song song 1.1 Mạng liên kết tuyến tính và liên kết vòng Với mạng liên kết tuyến tính, các bộ xử lí được liên kết với nhau theo dãy và được đánh số theo thứ tự tăng dần. Trong mạng liên kết này, trừ hai phần tử đầu và cuối của mạng, tất cả các bộ xử lí đều có hai láng giềng là bộ xử lí trước và sau nó.
Đây là dạng liên kết đơn giản, nhưng dữ liệu cũng cần phải chuyển qua nhiều bộ xử lí, do đó sự truyền thông dữ liệu giữa các bộ xử lí đặc biệt là bộ xử lí đầu và cuối sẽ bị chậm lại khi số bộ xử lí lớn.4 Mạng liên kết tuyến tính và mạng vòng 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Mạng liên kết vòng được tổ chức tương tự như mạng liên kết tuyến tính, tuy nhiên, với mạng liên kết vòng, bộ xử lí đầu tiên và cuối cùng được kết nối với nhau để tạo thành một vòng. Trong mạng liên kết vòng, sự trao đổi giữa các bộ xử lí có thể thực hiện theo một chiều gọi là mạng đơn, hoặc theo cả hai chiều gọi là mạng kép. Sự truyền thông trong mạng liên kết vòng, nhất là các bộ xử lí ở xa nhau vẫn bị trễ.2 Mạng liên kết lưới hai chiều (Two-Dimentional mesh) Với mạng liên kết lưới hai chiều, mỗi bộ xử lí được liên kết với các láng giềng: Trên, dưới, trái và phải. Mạng liên kết lưới hai chiều có hai dạng đó là lưới quay vòng lưới không quay vòng.5 Mạng liên kết lưới hai chiều 1.3 Mạng liên kết hình khối (Hypercube Network) Giả sử có 𝑛 bộ xử lí, trong đó 𝑛 là lũy thừa của 2, 𝑛 = 2𝐷 (𝐷 ≥ 0).
Trong mạng này, mỗi bộ xử lí sẽ liên kết với đúng 𝐷 bộ xử lí lân cận. Trong đó, chỉ số của các bộ xử lí được đánh dưới dạng chuỗi nhị phân, hai bộ xử lí được kết nối với nhau nếu chúng sai khác nhau đúng một bit. 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.6 Mạng liên kết khối Trên đây là một số kiểu liên kết các bộ xử lí điển hình được sử dụng trong các mô hình song song. Việc sử dụng kiến trúc song song nào và các thức liên kết giữa các bộ xử lí song song ra sao cũng là một yếu tố quan trọng ảnh hưởng đến khả năng xử lí bài toán.4 Cơ sở đánh giá giải thuật song song Việc sử dụng mô hình song song nào phù hợp với bài toán nào là một vấn đề khá quan trọng trong xử lí song song bởi lẽ một thuật toán có thể phù hợp với mô hình này nhưng chưa chắc đã là tốt với mô hình kia.
Để đánh giá được một giải thuật song song, thông thường chúng ta sẽ dựa vào ba tiêu chí: Thời gian thực hiện, khả năng tăng tốc, độ hiệu quả của thuật toán [4].1 Thời gian thực hiện Khi tốc độ tính toán được coi là mục tiêu chủ yếu khi xây dựng các máy tính song song, thì thời gian thực hiện là một độ đo quan trọng trong việc đánh giá giải thuật. Nó được xác định như là thời gian giải thuật yêu cầu để giải quyết một vấn đề trên máy tính song song, đó là khoảng thời gian kể từ thời điểm ban đầu đến thời điểm kết thúc. Nếu các bộ xử lí khác nhau, tất cả không bắt đầu và kết thúc đồng thời, thì thời gian thực hiện bằng thời gian kéo dài giữa thời điểm bộ xử lí đầu tiên bắt đầu tính toán đến thời điểm cuối cùng bộ xử lí kết thúc tính toán. Trước khi thực sự cài đặt một giải thuật song song hay tuần tự đều có sự phân tích về lý thuyết, giải thuật cần bao nhiêu thời gian để giải quyết vấn đề tính toán đã 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Điều này thường được thực hiện bằng cách tính toán các thao tác cơ bản hoặc các bước mà giải thuật thực hiện trong trường hợp xấu nhất. Số các bước như thế là một hàm của kích thước đầu vào (input size).