MỞ ĐẦU Nhân loại ngày nay đang chứng kiến sự phát triển mạnh mẽ của ngành Công nghệ thông tin, một trong những ngành mũi nhọn của nhiều quốc gia trên thế giới. Sự phát triển vượt bậc của nó là kết quả tất yếu của sự phát triển các thiết bị phần cứng cũng như phần mềm tiện ích. Từ những máy tính đơn giản, tốc độ xử lý chậm, và chỉ được sử dụng trong một số lĩnh vực kỹ thuật nhất định, thì ngày nay chúng đã có khả năng tính toán và tốc độ xử lý vượt trội trở thành một công cụ không thể thiếu trong mọi lĩnh vực của đời sống. Những máy tính ra đời đầu tiên, do hạn chế về tốc độ xử lý và cơ chế vào ra dữ liệu nên việc lập trình rất khó khăn.
Điều này làm cho máy tính không có khả năng sử dụng dễ dàng và phổ cập, nó chỉ được ứng dụng trong một số lĩnh vực khoa học đặc biệt. Ngày nay, cùng với sự phát triển mạnh mẽ của thiết bị lưu trữ, bộ nhớ, tốc độ xử lý và các thiết bị ngoại vi,… máy tính đã trở nên thân thiện hơn với người sử dụng, cũng như tốc độ tính toán nhanh hơn rất nhiều. Nhờ đó mà rất nhiều bài toán lớn đã có khả năng thực thi và nhiều ứng dụng được đưa ra. Tuy nhiên, một thực tế là còn rất nhiều vấn đề lớn với số lượng cần tính toán khổng lồ mà một máy tính thông thường không thể giải quyết được.
Vào thập kỷ 70, các nhà khoa học đã đưa ra ý tưởng về cấu trúc song song nhằm kết hợp sức mạnh của nhiều bộ xử lý trên một máy tính, hoặc kết hợp nhiều máy tính với nhau thông qua mạng máy tính tạo thành máy song song ảo. Ngoài việc tính nhanh, các máy tính song song có độ an toàn cao hơn máy tính đơn, khi một vài bộ xử lý hỏng thì máy tính song song vẫn có thể hoạt động được trong khi máy tính đơn thì không làm được điều đó. Hiện nay trên thế giới đã có những máy tính song song chứa đến hàng nghìn bộ xử lý. Để khai thác tiềm năng và sức mạnh của máy tính song song, cùng với việc thiết kế kiến trúc song song ta còn phải nghiên cứu những vấn đề quan trọng khác như hệ điều hành hỗ trợ xử lý song song, các ngôn ngữ lập trình và thuật toán song song.
Việc nghiên cứu thiết kế các máy tính song song, và các thuật toán song song cũng như các ngôn ngữ lập trình hỗ trợ lập trình song song bắt đầu được quan tâm từ những 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com năm 70, cho đến nay các ứng dụng của chúng đã lan rộng khắp các lĩnh vực của đời sống như đánh giá khả năng rủi ro về tài chính: dùng để mô hình hoá các xu hướng trên thị trường… Hỗ trợ quyết định như phân tích thị trường, dự báo thời tiết… Trí tuệ nhân tạo như thiết kế robot… Xử lý ảnh ứng dụng trong công nghệ nhận dạng… Điều khiển tự động… Trong đó bài toán có liên quan tới ma trận thưa đóng một vai trò quan trọng, hay gặp trong các lời giải lặp của hệ phương trình tuyến tính, hệ phương trình giá trị riêng, … Do vậy việc nghiên cứu các thuật toán ma trận thưa, đặc biệt là các thuật toán song song trên ma trận thưa là rất cần thiết. Trong phạm vi luận văn này trình bày ba phần chính, Chƣơng 1 trình bày tổng quan về xử lý song song, thuật toán song song và giới thiệu lập trình song song với MPI sử dụng Visual của Microsoft; Chƣơng 2 trình bày về các thuật toán thiết kế cho nhân ma trận thưa với véc tơ song song; Chƣơng 3 trình bày một số kết quả thực nghiệm trên một số bộ dữ liệu cho chương trình nhân ma trận thưa với véc tơ song song. Với thời gian tiếp cận vấn đề và lượng thông tin còn hạn chế, luận văn còn nhiều thiếu sót. Tôi rất mong nhận được sự góp ý của các thầy, các cô và các anh/chị để có thể tiếp tục phát triển đề tài đã nghiên cứu và đạt được kết quả.
11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 1 - TỔNG QUAN VỀ XỬ LÝ SONG SONG 1.1 Hệ thống song song 1.1 Khái niệm 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 và cùng tham gia giải quyết một vấn đề, thường được thực hiện trên những hệ thống có nhiều bộ xử lý [1]. Máy tính song song là tập hợp các bộ xử lý, thường cùng một loại, 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.2 Kiến trúc xử lý song song a) Máy tính song song phân chia theo cách thức thực hiện chương trình Có nhiều cách để phân loại máy tính song song, người ta thường sử dụng cách phân loại máy tính song song của M. Cách phân loại này dựa vào sự phân phối dữ liệu và phân phối các lệnh trên mỗi bộ xử lý. Luồng lệnh (instruction stream) là một dãy các lệnh từ một đơn vị điều khiển hướng đến một hay nhiều bộ xử lý.
Luồng dữ liệu (data stream) là một dãy dữ liệu từ một vùng nhớ hướng đến một bộ xử lý hoặc từ một bộ xử lý hướng đến một vùng nhớ. Bốn cấu trúc máy tính song song được phân loại bởi Flynn đó là: Mô hình SISD (đơn luồng lệnh, đơn luồng dữ liệu) Máy tính loại SISD chỉ có một CPU, ở mỗi thời điểm thực hiện một chỉ lệnh và chỉ đọc, ghi một mục dữ liệu. Tất cả các máy tính SISD chỉ có một thanh ghi register được gọi là bộ đếm chương trình được sử dụng để nạp địa chỉ của lệnh tiếp theo khi xử lý tuần tự và kết quả là thực hiện theo một thứ tự xác định của các câu lệnh. Mô hình SISD còn được gọi là SPSD 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com - đơn chương trình và đơn luồng dữ liệu.
Đây chính là mô hình máy tính truyền thống kiểu von Neumann 1. Mô hình SIMD (đơn luồng lệnh, đa luồng 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, nghĩa là mỗi bộ xử lý có luồng dữ liệu riêng. Đây là kiểu tính toán lặp lại các đơn vị số học trong CPU, cho phép những đơn vị khác nhau thực hiện trên những toán hạng khác nhau, nhưng thực hiện cùng một lệnh.
Máy tính SIMD có thể hỗ trợ xử lý kiểu véc tơ, trong đó có thể gán các phần tử của véc tơ cho các phần tử xử lý để tính toán đồng thời. Máy tính véc tơ và các bộ xử lý mảng là mô hình chủ yếu thuộc loại này. Mô hình SIMD còn được gọi là SPMD - đơn chương trình và đa luồng dữ liệu. Đây chính là mô hình máy tính phổ biến có trên thị trường như: ILLIAC IV, DAP và Connection Machine CM-2.
Mô hình MISD (đa luồng lệnh, đơn luồng dữ liệu) 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 đượ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 đơn vị xử lý khác nhau có thể nhận được những chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. Đây là kiến trúc khó và hiện nay chưa có loại máy tính nào được sản xuất theo loại này. - 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.
Đây là loại kiến trúc hình ống thực hiện 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ả 1 Mô hình máy tính do von Neumann (1903-1957) đưa ra, là kiến trúc máy tính phổ biến nhất hiện nay, với đặc trưng là các lệnh được thực hiện một cách tuần tự, mỗi thời điểm chỉ thực hiện được một lệnh. 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com cho đơn vị xử lý thực hiện bước tiếp theo. Hoạt động của máy tính theo kiến trúc loại này giống như hệ tuần hoàn nên còn được gọi là hệ tâm thu. 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 (chương trì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 (toàn cục) 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. Đâ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 và đã có nhiều máy tính được sản xuất theo kiến trúc này như: BBN Butterfly, Aliant FX, iSPC của Intel, … b) Máy tính song song phân chia theo kiến trúc phần cứng Kiến trúc máy tính là một phần rất quan trọng quyết định hiệu quả của công việc, đối với một máy tính song song có một số loại kiến trúc phần cứng cơ bản sau: Máy tính song song với bộ nhớ chia sẻ Trong máy tính song song với bộ nhớ chia sẻ, bộ nhớ là chung cho tất cả các bộ xử lý. Bộ nhớ được phân thành các mô đun nhớ, mỗi mô đun này có kênh vào ra riêng. Các mô đun nhớ này được nối với bộ xử lý trên mỗi CPU thông qua bus hoặc mạng kết nối nội bộ.
Trong mô hình này, các CPU được nối đến ngân hàng bộ nhớ trên cùng một bus, với cùng tốc độ. Các bộ xử lý khi hoạt động cùng chia sẻ dữ liệu ghi trong bộ nhớ chung. Mỗi bộ xử lý đọc dữ liệu mà nó cần trong bộ nhớ chung, xử lý chúng, rồi lại ghi kết quả vào bộ nhớ. Vì các bộ xử lý dùng chung bộ nhớ, có xuất hiện xung đột truy cập, vì vậy loại kết nối dùng trong mô hình này là: bus hoặc crossbar, với bus thì các bộ xử lý được tổ chức liên kết với nhau theo dãy, đây là dạng liên kết đơn giản.
14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.