Thiết kế nhân ma trận thưa với véctơ trong tính toán song song và ứng dụng

  • Số trang: 102 |
  • Loại file: PDF |
  • Lượt xem: 57 |
  • Lượt tải: 0
tailieuonline

Đã đăng 27372 tài liệu

Mô tả:

®¹i häc quèc gia hµ néi tr-êng ®¹i häc khoa häc tù nhiªn Ng« thÞ nh¹n ThiÕt kÕ nh©n ma trËn th-a víi vÐct¬ trong tÝnh to¸n song song vµ øng dông luËn v¨n th¹c sÜ khoa häc Hµ Néi - N¨m 2011 1 ®¹i häc quèc gia hµ néi tr-êng ®¹i häc khoa häc tù nhiªn Ng« thÞ nh¹n ThiÕt kÕ nh©n ma trËn th-a víi vÐct¬ trong tÝnh to¸n song song vµ øng dông Chuyªn ngµnh: B¶o ®¶m to¸n häc cho m¸y tÝnh vµ hÖ thèng tÝnh to¸n M· sè: 60 46 35 luËn v¨n th¹c sÜ khoa häc ng-êi h-íng dÉn khoa häc: nguyÔn h÷u ®iÓn Hµ Néi - N¨m 2011 2 MỤC LỤC Trang Trang phụ bìa ......................................................................................................................... Mục lục ................................................................................................................................... Danh mục các ký hiệu ............................................................................................................ Danh mục các bảng ................................................................................................................ Danh mục các hình vẽ ............................................................................................................ Danh mục các thuật toán ........................................................................................................ MỞ ĐẦU .............................................................................................................................. 1 Chƣơng 1 - TỔNG QUAN VỀ XỬ LÝ SONG SONG .................................................. 12 1.1 Hệ thống song song.................................................................................................. 12 1.1.1 Khái niệm xử lý song song ............................................................................... 12 1.1.2 Kiến trúc xử lý song song ................................................................................. 12 1.2 Các thành phần của máy tính song song .................................................................. 15 1.2.1 Bộ nhớ .............................................................................................................. 15 1.2.2 Chương trình dịch và các hệ điều hành ............................................................ 17 1.3 Các mô hình lập trình song song ............................................................................. 19 1.3.1 Mô hình chia sẻ bộ nhớ .................................................................................... 19 1.3.2 Mô hình tuyến ................................................................................................... 20 1.3.3 Mô hình song song dữ liệu ............................................................................... 20 1.3.4 Mô hình truyền thông điệp ............................................................................... 21 1.4 Nguyên lý thiết kế thuật toán song song .................................................................. 22 1.4.1 Định nghĩa thuật toán song song ...................................................................... 22 1.4.2 Các giai đoạn của thiết kế thuật toán song song............................................... 22 4 1.4.3 Đánh giá độ phức tạp của thuật toán song song ............................................... 25 1.5 Lập trình song song với MPI ................................................................................... 27 1.5.1 Giao diện truyền thông điệp - MPI ................................................................... 27 1.5.2 Giới thiệu gói CCP của Microsoft .................................................................... 31 1.5.3 Lập trình MPI với VS.NET .............................................................................. 34 1.6 Kiến trúc cụm máy tính ........................................................................................... 35 Chƣơng 2 – THUẬT TOÁN SONG SONG NHÂN MA TRẬN THƢA VỚI VÉCTƠ ............................................................................................................................................ 38 2.1 Ma trận thưa ............................................................................................................. 38 2.1.1 Đặt vấn đề ......................................................................................................... 38 2.1.2 Cấu trúc dữ liệu cho ma trận thưa .................................................................... 43 2.2 Nhân ma trận thưa với véc tơ song song ................................................................. 48 2.2.1 Thuật toán song song ........................................................................................ 48 2.2.2 Phân phối ma trận ............................................................................................. 53 2.2.3 Phân phối véc tơ ............................................................................................... 60 2.2.3.1 Cận dưới địa phương cho số truyền thông cực đại ................................... 62 2.2.3.2 Phân phối các véc tơ độc lập ..................................................................... 71 2.2.3.3 Phân phối các véc tơ đồng thời ................................................................. 78 Chƣơng 3 – KẾT QUẢ THỰC NGHIỆM ..................................................................... 83 3.1 Bộ dữ liệu ................................................................................................................. 83 3.2 Kết quả ..................................................................................................................... 83 KẾT LUẬN ........................................................................................................................ 93 TÀI LIỆU THAM KHẢO .................................................................................................. 94 PHỤ LỤC ........................................................................................................................... 96 5 BẢNG THUẬT NGỮ VIẾT TẮT Thuật ngữ CCS Tiếng Anh Compressed Column Storage Nghĩa tiếng Việt Lưu trữ nén cột CRS Compressed Row Storage Lưu trữ nén dòng CPU Central Processing Unit Bộ xử lý trung tâm HPC High Performance Computing Tính toán/máy tính hiệu năng cao ICRS Incremental Compressed Row Storage Lưu trữ nén dòng có gia số JDS Jagged Diagonal Storage Lưu trữ đường chéo răng cưa Multi Instruction Stream, Multi Data Stream Multi Instruction Stream, Single Data Stream Đa luồng lệnh, đa luồng dữ liệu MPI Message Passing Interface Giao diện truyền thông điệp NUMA Non-Uniform Memory Access Truy cập bộ nhớ không đồng thời PRAM Parallel Random Access Machine Máy truy trập ngẫu nhiên song song Đơn luồng lệnh, đa luồng dữ liệu TCP Single Instruction Stream, Multi Data Stream Single Instruction Stream, Single Data Stream Transmission Control Protocol UDP User Datagram Protocol Giao thức gói người dùng UMA Uniform Memory Access Truy cập bộ nhớ đồng thời WS Workstation Máy trạm WSC Workstation Cluster Cụm máy trạm MIMD MISD SIMD SISD 6 Đa luồng lệnh, đơn luồng dữ liệu Đơn luồng lệnh, đơn luồng dữ liệu Giao thức điều khiển truyền thông DANH MỤC CÁC BẢNG Trang Bảng 3.1 Các file dữ liệu ma trận ...................................................................................... 83 Bảng 3.2 Thống kê cho ma trận bcsstk13 .......................................................................... 85 Bảng 3.3 Thống kê cho ma trận lp_cycle ........................................................................... 86 Bảng 3.4 Thống kê cho ma trận onetone2 ......................................................................... 87 Bảng 3.5 Thống kê cho ma trận epb2 ................................................................................ 88 Bảng 3.7 Thống kê cho ma trận random20k ...................................................................... 90 7 DANH MỤC HÌNH VẼ Trang Hình 1.1 Phân cấp hệ thống bộ nhớ ................................................................................... 15 Hình 1.2 Mô hình tuyến ..................................................................................................... 20 Hình 1.3 Các giai đoạn của quá trình thiết kế thuật toán ................................................... 23 Hình 1.4 Luật Amdahl........................................................................................................ 27 Hình 1.5 Mô phỏng kiến trúc một cụm tính toán ............................................................... 32 Hình 1.6 Mô hình kiến trúc lập lịch ................................................................................... 33 Hình 2.1 Mô phỏng động lực học bằng ma trận lực thưa .................................................. 40 Hình 2.2 Minh hoạ nhân ma trận thưa với véc tơ song song ............................................. 49 Hình 2.3 Minh hoạ truyền thông nhân ma trận thưa với véc tơ ......................................... 51 Hình 2.4 Phân phối của ma trận impcol_b ......................................................................... 58 Hình 3.1 Hình dạng thưa của ma trận bcsstk13 ................................................................. 84 Hình 3.2 Hình dạng thưa của ma trận lp_cycle .................................................................. 85 Hình 3.3 Hình dạng thưa của ma trận onetone2................................................................. 86 Hình 3.4 Hình dạng thưa của ma trận epb2 ....................................................................... 87 Hình 3.5 Hình dạng thưa của ma trận nasa2910 ................................................................ 88 Hình 3.6 Phân phối LA cho random20k với P = 4 ............................................................ 91 Hình 3.7 Phân phối LA cho lp_cycle với P = 4 ................................................................. 92 8 DANH MỤC CÁC THUẬT TOÁN Trang Thuật toán 2.1 Thuật toán nhân ma trận thưa với véc tơ tuần tự ....................................... 39 Thuật toán 2.2 Thuật toán tuần tự nhân ma trận thưa với véc tơ sử dụng CRS ................. 45 Thuật toán 2.3 Thuật toán tuần tự nhân ma trận thưa với véc tơ sử dụng ICRS ............... 46 Thuật toán 2.4 Nhân ma trận thưa với véc tơ song song ................................................... 50 Thuật toán 2.5 Thuật toán Mondrian phân hoạch ma trận thưa ......................................... 59 Thuật toán 2.6 Xây dựng cận dưới địa phương của bộ xử lý s .......................................... 64 Thuật toán 2.7 Chuyển tập C  thành C   0,..., C   1...................................................... 66 Thuật toán 2.8 Tạo cận dưới địa phương tổng quát cho bộ xử lý s ................................... 69 Thuật toán 2.9 Thuật toán biên địa phương (LA) .............................................................. 73 Thuật toán 2.10 Thuật toán phân phối véc tơ đồng thời (LAvu)......................................... 80 9 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 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 Chƣơng 1 - TỔNG QUAN VỀ XỬ LÝ SONG SONG 1.1 Hệ thống song song 1.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. 1.1.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.J. Flynn (1966) [13]. 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 - đơ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 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  Máy tính song song với bộ nhớ phân tán Trong mô hình này mỗi CPU có bộ nhớ riêng, mỗi CPU truy nhập đến bộ nhớ riêng của mình với tốc độ nhanh, còn truy cập đến bộ nhớ của CPU khác thì chậm hơn. Trong mô hình này mỗi bộ xử lý ngoài việc sử dụng dữ liệu trong bộ nhớ riêng, nó còn có thể đọc trên một hoặc nhiều kênh truyền thông từ các bộ xử lý khác mà nó cần, thực hiện xử lý, rồi lại có thể truyền kết quả cho bộ xử lý khác. Do đó thới gian thực hiện trong kiến trúc phụ thuộc vào thời gian di chuyển dữ liệu giữa các bộ xử lý. Nhìn chung mạng liên kết không cho phép kết nối tất cả các CPU với nhau, mỗi CPU chỉ được kết nối với một số CPU khác.  Mô hình hỗn hợp Mô hình này là sự kết hợp giữa các mô hình đã trình bày ở trên, nó dung hoà được các ưu nhược điểm của hai kiến trúc trên, các bộ xử lý được liên kết với nhau thông qua một mạng giao tiếp tạo thành một hệ thống liên cụm, mỗi cụm có kiến trúc dùng chung (chia sẻ). 1.2 Các thành phần của máy tính song song 1.2.1 Bộ nhớ Một trong các thành phần quan trọng nhất của kiến trúc máy tính là bộ nhớ. Bộ nhớ thường được chia thành n mức như hình 1.1 [1]. BXL Mức cao nhất Bộ nhớ mức 1 Nhỏ, nhanh và đắt Bộ nhớ mức 2 Mức thấp nhất Bộ nhớ mức n Lớn, chậm và rẻ Hình 1.1 Phân cấp hệ thống bộ nhớ 15 Bộ nhớ mức 1 là mức bộ nhớ cao nhất có dung lượng nhỏ nhất, nhanh và đắt nhất, thường gắn chặt với mỗi bộ xử lý thành bộ nhớ cục bộ. Bộ nhớ mức 2 thường nhỏ hơn, chậm hơn và rẻ hơn mức 1, … Về nguyên tắc, dữ liệu được chuyển đổi giữa các mức lân cận của các bộ nhớ và hoàn toàn được điều khiển bởi bộ nhớ mức 1. Về lý thuyết, trong cấu trúc phân cấp bộ nhớ, tốc độ truy cập bộ nhớ trung bình gần bằng tốc độ truy cập ở mức cao (mức 1), nhưng chi phí của các đơn vị nhớ trung bình lại gần với chi phí của bộ nhớ ở mức thấp nhất (mức n). Sau đây chúng ta xét một số mô hình bộ nhớ của các máy tính song song:  Bộ nhớ kết hợp Bộ nhớ kết hợp (AM – Associative Memory) bao gồm các ô nhớ và logic kết hợp. Mỗi ô nhớ của AM có 4 đầu vào và hai đầu ra. Tất cả các bộ nhớ AM được tổ chức thành các từ và được xây dựng thành mảng các ô giống nhau. Mỗi ô trong số m  n ô nhớ và nó có một mạch vòng để so sánh đối số với giá trị được lưu trữ trong các ô nhớ, đồng thời chỉ ra kết quả khi đối sánh thành công. Hệ thống có thanh ghi lưu trữ đối số, một thanh ghi đánh dấu những trường của mỗi từ mà bộ nhớ cần so sánh và thanh ghi đối sánh (các bít đối sánh) chỉ ra những từ tìm thấy.  Mô hình bộ nhớ truy cập ngẫu nhiên song song Mô hình tính toán song song PRAM bao gồm bộ nhớ chung RAM với m vùng nhớ đủ lớn để chia sẻ cho p bộ xử lý. Bộ nhớ chung được sử dụng để lưu trữ dữ liệu và là vùng nhớ để trao đổi giữa các bộ xử lý. Có một số cách khác nhau để các bộ xử lý có thể đọc/ghi dữ liệu, đó là: - Concurrent Read (CR): nhiều bộ xử lý có thể đọc đồng thời cùng một ô nhớ. - Exlusive Read (ER): p bộ xử lý đọc được p vùng nhớ khác nhau. Mỗi bộ xử lý đọc được chính xác một vùng nhớ và mỗi vùng nhớ được đọc bởi một bộ xử lý. 16 - Concurrent Write (CW): cùng một thời điểm cho phép nhiều bộ xử lý ghi vào cùng một vùng nhớ. - Exlusive Write (EW): p bộ xử lý ghi được vào p vùng nhớ khác nhau. Mỗi bộ xử lý ghi được vào chính xác một vùng nhớ và ngược lại. Dễ nhận thấy rằng: ER, EW là trường hợp đăc biệt của CR và CW. Trong đó, CW là cần phải chú ý nhất và được phân nhỏ thành các loại như sau: - Ghi đồng thời có ưu tiên (Priority CW): các bộ xử lý được gắn mức ưu tiên và khi có nhiều bộ xử lý muốn ghi dữ liệu vào một vùng nhớ thì ưu tiên cho bộ xử lý có mức ưu tiên cao nhất. Các mức ưu tiên có thể gắn tĩnh hoặc động theo những qui tắc được xác định khi thực hiện. - Ghi đồng thời chung (Common CW): tất cả các bộ xử lý được phép ghi vào cùng một vùng nhớ chỉ khi chúng ghi cùng một giá trị. Trong trường hợp này, một bộ xử lý được chọn để ghi dữ liệu đó. - Ghi đồng thời tự do (Arbitrary CW): một số bộ xử lý muốn ghi dữ liệu đồng thời vào một vùng nhớ, nhưng chỉ một bộ xử lý được phép thay đổi giá trị của vùng nhớ đó. Trong trường hợp này, chúng ta phải chỉ ra cách để lựa chọn bộ xử lý thực hiện. - Ghi đồng thời ngẫu nhiên (Random CW): bộ xử lý được lựa chọn để ghi dữ liệu là ngẫu nhiên. - Ghi đồng thời phối hợp (Combining CW): tất cả các dữ liệu mà các bộ xử lý định ghi đồng thời vào bộ nhớ được tổ hợp lại thành một giá trị. Giá trị này sẽ được ghi vào bộ nhớ đó. 1.2.2 Chƣơng trình dịch và các hệ điều hành Chương trình dịch Chương trình được viết bằng các ngôn ngữ lập trình truyền thống thì phải được dịch sang dạng mã mà phần cứng hiểu được nó, đó là ngôn ngữ máy. Chương trình dịch và 17 chương trình thông dịch được sử dụng để thực hiện các chuyển đổi đó. Có ba cách tiếp cận để xây dựng chương trình dịch cho các máy tính song song: - Phân hoạch và lập lịch khi chạy: Cách tiếp cận này khá phù hợp với một số ứng dụng thực tế. Tuy nhiên, nó có hạn chế là việc lập lịch và phân hoạch được thực hiện lúc chạy chương trình sẽ làm giảm hiệu suất của hệ thống. - Phân hoạch khi biên dịch và lập lịch khi chạy: Đây là mô hình chung để xây dựng chương trình dịch cho đa bộ xử lý. Lập lịch phân việc được thực hiện lúc chương trình chạy, nhưng việc phân hoạch công việc thành các khối được thực hiện bởi người lập trình và chương trình dịch. Theo cách tiếp cận này, sự đồng bộ hóa các tiến trình và truyền thông phải được xác định rõ trong hệ thống. - Phân hoạch và lập lịch khi biên dịch: Phân hoạch công việc và lập lịch được thực hiện ở giai đoạn dịch chương trình. Do vậy, chương trình dịch loại này đòi hỏi phải rất hoàn hảo. Nhưng điều này khá khó, bởi vì rất khó đánh giá được thời gian thực hiện chương trình, đặc biệt là vấn đề lập lịch trước sẽ không thể thực hiện tối ưu được. Hệ điều hành Hệ điều hành là một chương trình làm nhiệm vụ phối hợp các hoạt động của máy tính. Hệ điều hành thực hiện các chức năng chính sau: - Khởi động hệ thống. - Phân đoạn chương trình và lập lịch cho các tiến trình. - Trao đổi và đồng bộ hóa các tiến trình. - Quản lý và điều hành hệ thống, v.v. Nhiệm vụ chính của hệ điều hành đa bộ xử lý là tích hợp các tài nguyên tính toán và các bộ xử lý trao đổi với nhau thông qua mạng liên kết để tạo thành một hệ thống nhất làm việc cho hiệu quả. Nói chung, hệ điều hành đa bộ xử lý cũng giống như hệ điều hành tập trung, phải chứa các thành phần quản trị hệ thống như: quản trị các tiến trình, quản trị bộ nhớ, quản 18 trị tài nguyên và quản trị các tệp. Người ta phân các hệ điều hành cho các máy tính song song thành ba loại: - Những hệ điều hành mở rộng và phát triển từ những hệ đơn bộ xử lý để chạy được trên những kiến trúc song song, như VMS, UNIX. - Những hệ điều hành được thiết kế riêng cho những kiến trúc song song, như: hệ Hydra cho C.mmp, Medusa cho Cm*, cả hai đều được phát triển ở CarnegieMellon University. - Những hệ điều hành tổng hợp được thiết kế để cài đặt được trên những kiến trúc song song khác nhau, ví dụ MACH Multiprocessor. Hầu hết các phiên bản mới của hệ điều hành UNIX đều thực hiện trên các hệ đa bộ xử lý. Trong số đó có thể kể ra như Solaris của Sun, HP UNIX của HP, Digital UNIX của Digital, AIX của IBM, … Những hệ điều hành mới nhất như Window NT của Microsoft cũng được thiết kế để chạy trên những hệ thống đa bộ xử lý. 1.3 Các mô hình lập trình song song 1.3.1 Mô hình chia sẻ bộ nhớ Trong mô hình này, các bộ xử lý đều được kết nối tới một bộ nhớ chung, thông qua các phương tiện phần cứng hoặc phần mềm. Có các cơ chế khác nhau như khóa/semaphores sử dụng để kiểm soát truy cập vào bộ nhớ chung đó. Điểm bất lợi của mô hình này là khả năng phát triển tới 32 bộ xử lý là rất khó, và mô hình bộ nhớ chia sẻ là ít linh hoạt hơn mô hình bộ nhớ phân tán. Dạng đường bus Các máy MIMD với bộ nhớ chia sẻ có các bộ xử lý cùng chia sẻ một vùng nhớ tập trung chung. Nói đơn giản nhất, mọi bộ xử lý đều kết nối bằng một đường bus tới bộ nhớ. Cách kết nối này gọi là dựa trên đường bus, và có quá nhiều xung đột trên đó. Dạng phân cấp Các máy MIMD với bộ nhớ chia sẻ phân cấp sử dụng một hệ thống phân chia các bus cho phép các bộ xử lý truy cập tới các bộ nhớ của những bộ xử lý khác. Các bộ xử lý 19 ở các vùng khác nhau có thể giao tiếp thông qua các nút nối. Các bus hỗ trợ giao tiếp giữa các máy. Với kiến trúc này, các máy có thể hỗ trợ tới hàng ngàn bộ xử lý. 1.3.2 Mô hình tuyến Trong mô hình tuyến (hay mô hình luồng) của lập trình song song, một tiến trình đơn có thể bao gồm nhiều tuyến thực hiện đồng thời, minh họa hình 1.2. Mỗi luồng có dữ liệu cục bộ, nhưng đồng thời chia sẻ toàn bộ tài nguyên của tiến trình chủ. Điều này tiết kiệm các chi phí liên quan đến việc sao chép các tài nguyên của chương trình cho mỗi tuyến. Có hai chuẩn triển khai luồng đó là: POSIX Threads và OpenMP. Microsoft có triển khai luồng riêng, không liên quan đến các chuẩn UNIX POSIX hay OpenMP. Hình 1.2 Mô hình tuyến Hình 1,2 mô tả chương trình trong tệp a.out, chương trình khởi động chạy như một tiến trình đơn, sau đó các tiến trình được khởi tạo để chạy đồng thời, các tiến trình có thể sử dụng tài nguyên của a.out và có thể kết thúc riêng rẽ. 1.3.3 Mô hình song song dữ liệu Mô hình song song dữ liệu hay gặp khi phần lớn công việc song song tập trung vào việc thực hiện các tác vụ trên một tập dữ liệu. Tập dữ liệu thường được tổ chức thành một cấu trúc thông dụng, như mảng hay khối lập phương. Một tập các tác nhiệm làm việc trên cùng một cấu trúc dữ liệu, tuy nhiên, mỗi tác nhiệm làm việc trên một phân vùng khác 20 nhau của cùng một cấu trúc dữ liệu. Các tác nhiệm thực hiện cùng một tác vụ trên phân vùng làm việc của chúng. Trên các kiến trúc bộ nhớ chia sẻ, tất cả các tác nhiệm có thể truy cập vào cấu trúc dữ liệu thông qua bộ nhớ toàn cục. Trên các kiến trúc bộ nhớ phân tán, cấu trúc dữ liệu được chia ra và được đặt như là các phần trong bộ nhớ cục bộ của mỗi tác nhiệm. 1.3.4 Mô hình truyền thông điệp Trong mô hình truyền thông điệp, các tiến trình chia sẻ với nhau qua các kênh truyền thông. Kênh là khái niệm trừu tượng của đường truyền thông vật lý giữa các tiến trình. Các kênh được truy cập bởi hai phương thức gửi và nhận thông điệp: send() và receive(). Khi một tiến trình gửi đi một thông điệp vào kênh truyền và có một tiến trình khác yêu cầu nhận thông điệp đó thì diễn ra sự trao đổi dữ liệu và sự trao đổi được hoàn tất khi dữ liệu đã được chuyển từ nơi gửi tới nơi nhận. Mô hình truyền thông điệp có các đặc điểm sau: - Một tập các tác nhiệm sử dụng bộ nhớ cục bộ riêng của chúng trong quá trình tính toán. Nhiều tác nhiệm có thể nằm trên cùng một máy cũng như nằm trên nhiều máy. - Các tác nhiệm vụ trao đổi dữ liệu thông qua truyền thông bằng cách gửi và nhận các thông điệp. - Truyền dữ liệu thường đòi hỏi sự hợp tác giữa các tiến trình. Ví dụ, một tác vụ gửi thông điệp phải có một tác vụ nhận thông điệp tương ứng. Có hai mô hình truyền thông điệp cơ bản là: - Truyền thông điệp đồng bộ: Trong mô hình này, tiến trình gửi bị chặn lại cho đến khi tiến trình nhận sẵn sàng nhận. Ở đây, sự truyền thông và đồng bộ hoá luôn gắn chặt với nhau. - Truyền thông điệp dị bộ: Trong mô hình này, tiến trình gửi sẽ không phải chờ đến khi tiến trình nhận sẵn sàng mà cứ gửi khi có yêu cầu. Như vậy, hai tiến trình gửi và nhận có thể hoạt động gần như đọc lập với nhau và thông điệp có thể nhận được sau một khoảng thời gian nào đó (lâu bất kỳ) kể từ khi nó được gửi đi. Tuy nhiên, 21
- Xem thêm -