Khai thác và áp dụng các giải thuật song song

MỞ ĐẦU Hiện nay, với sự xuất hiện ngày càng nhiều các hệ thống điện tử đã làm cho lượng thông tin trong mọi lĩnh vực phát triển nhanh chóng, có cấu trúc đa dạng và phức tạp. Đặc biệt, trong lĩnh vực xử lý ngôn ngữ tự nhiên, nhận dạng, xử lý ảnh, dự báo thời tiết, v.v. đòi hỏi máy tính phải xử lý một lượng dữ liệu rất lớn, với tốc độ cao. Có thể nói rằng những máy tính xử lý tuần tự kiểu Von Neumann khó có thể đáp ứng được yêu cầu về thời gian và khối lượng công việc thực hiện. Điều này dẫn tới là muốn tăng được khả năng tính toán của các hệ thống máy tính thì đích cuối cùng là phải khai thác được khả năng xử lý song song của chúng. Xử lý song song liên quan trực tiếp đến kiến trúc song song và giải thuật song song. Gần đây, với sự phát triển của máy tính song song và nhờ các giải thuật song song hợp lý đã làm thay đổi nhiều quan niệm về khả năng giải được trong thực tế của những bài toán khác nhau. Nhiều thuật toán trước đây không thể chấp nhận vì khối lượng tính toán quá lớn thì ngày nay lại hoàn toàn khả thi và có hiệu lực lớn. Các bài toán phức tạp trong lĩnh vực toán học đã có thuật toán hữu hiệu để giải nó. Với yêu cầu trên, mục đích của luận văn là nghiên cứu các kiến trúc của máy tính song song, các mô hình và các thuật toán trong xử lý song song. Trên cơ sở đó đề tài sẽ khai thác và áp dụng các giải thuật song song cho việc tìm nghiệm một số bài toán phi tuyến nhằm cải thiện đáng kể thời gian và tốc độ tính toán. Nội dung của đề tài được phân thành 3 chương. Chương 1, sẽ giới thiệu tổng quan về máy tính song song nhằm đưa ra cấu trúc và phân loại, đánh giá các kiến trúc song song đang sử dụng trong thực tế. Chương 2, áp dụng các kiến trúc song song để đưa ra các mô hình lập trình và các nguyên lý thiết kế giải thuật song song. Chương cuối cùng, là phần trọng tâm của đề tài, áp dụng các kiến trúc, mô hình lập trình và giải thuật song song để phân tích và cài đặt một số lớp giải bài toán phi tuyến. CHƯƠNG I TỔNG QUAN VỀ MÁY TÍNH SONG SONG I.1 Giới thiệu chung Tại sao phải xử lý song song? Nhiều lĩnh vực mới như đồ họa máy tính, trí tuệ nhận tạo, phân tích số, v.v. đòi hỏi phải xử lý một khối lượng dữ liệu rất lớn do đó cần phải có những hệ thống máy tính thật mạnh mới thực hiện được những yêu cầu trong thực tế. Những vấn đề về xử lý ngôn ngữ tự nhiên, nhận dạng, xử lý ảnh ba chiều (3-D), dự báo thời tiết, mô hình và mô phỏng những hệ thống lớn, v.v. đều đòi hỏi phải xử lý dữ liệu với tốc độc rất cao, với khối lượng dữ liệu rất lớn. Hầu hết những bài toán này, những máy tính xử lý tuần tự kiểu Von Neumann là không đáp ứng yêu cầu. Mặc dù tốc độ xử lý của các bộ xử lý (BXL) tăng nhưng khả năng tính toán của chúng không thể tăng mãi được do giới hạn về vật lý. Điều này dẫn tới là muốn tăng được khả năng tính toán của các hệ thống máy tính thì đích cuối cùng là phải khai thác được khả năng xử lý song song của chúng. Ngày càng xuất hiện nhiều bài toán mà những hệ thống đơn một bộ xử lý (BXL) không đáp ứng được yêu cầu xử lý về thời gian, do đó đòi hỏi phải sử dụng những hệ thống đa bộ xử lý và đòi hỏi phải 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 đề, nói chung là thực hiện trên những hệ thống đa bộ xử lý [14]. Khái niệm xử lý song song khác với tuần tự: 1. Trong tính toán tuần tự với một BXL thì mỗi thời điểm thực hiện được một phép toán. 2. Trong tính toán song song thì một số BXL cùng kết hợp với nhau để giải quyết cùng một vấn đề cho nên giảm được thời gian xử lý vì mỗi thời điểm có thể có nhiều phép toán được thực hiện đồng thời. Câu hỏi đặt ra là vấn đề xử lý song song hiện nay có hiện thực hay không? Câu trả lời là khẳng định. Ba yếu tố chính dẫn đến việc xử lý song song: 1. Hiện nay giá thành của phần cứng (CPU) giảm mạnh, tạo điều kiện để xây dựng những hệ thống có nhiều BXL với giá thành hợp lý. 2. Sự phát triển của công nghệ mạch tích hợp VLSI cho phép tạo ra những hệ phức hợp có hàng triệu transistor trên một chip. 3. Tốc độ xử lý của các BXL theo kiểu Von Neumann đã dần tiến tới giới hạn, không thể cải tiến thêm được do vậy dẫn tới đòi hỏi phải thực hiện xử lý song song. Những yếu tố trên thúc đẩy các nhà nghiên cứu phải tập trung khai thác công nghệ xử lý song song và tận dụng chúng để giải quyết những bài toán ứng dụng quan trọng của thực tế. Vấn đề xử lý song song liên quan trực tiếp đến: Kiến trúc máy tính, Phần mềm hệ thống (hệ điều hành), Thuật toán, Ngôn ngữ lập trình, v.v. Một máy tính song song là tập hợp các BXL, thường là cùng một loại, kết nối với nhau theo một cách nào đó để có thể hợp tác với nhau trong hoạt động và trao đổi dữ liệu được với nhau [12]. Các máy tính song song có thể phân thành nhiều loại dựa vào kiểu và số lượng các BXL, sự kết nối giữa chúng, dựa vào sơ đồ truyền thông và các thao tác vào/ra, v.v. Phần lớn các hệ điều hành ngày nay đều đã hỗ trợ đa xử lý / đa nhiệm và cho phép nghiên cứu, khai thác các phương pháp lập trình song song. Nhưng điều quan trọng là nhiều BXL phải tham gia "cùng giải một bài toán". Nói cách khác, những tiến trình thực hiện trên mỗi BXL phải kết hợp, trao đổi với nhau để giải quyết một bài toán cho trước. Trường hợp ngược lại không phải là xử lý song song. Ví dụ, nếu một đơn vị dịch chương trình File1.a và một đơn vị khác dịch chương trình File2.a thì không được xem là xử lý song song vì hai công việc đó hoàn toàn độc lập với nhau. Nhưng nếu một đơn vị đang dịch một phần của chương trình File.a và một đơn vị khác lại dịch một phần khác của cùng chương trình thì đó là sự xử lý song song. Một trong các mục đích chính của xử lý song song là nghiên cứu, xây dựng những thuật toán thích hợp để cài đặt trên các máy tính song song, nghĩa là phát triển các thuật toán song song. Câu hỏi tự nhiên là đánh giá một thuật toán song song như thế nào được gọi là thích hợp cho xử lý song song? Đối với thuật toán tuần tự thì chúng ta thống nhất cách đánh giá dựa vào thời gian thực hiện thuật toán, không gian bộ nhớ và khả năng lập trình, v.v. Đánh giá thuật toán song song thì phức tạp hơn nhiều, ngoài những tiêu chuẩn trên còn bổ sung thêm những tham số về số bộ xử lý, khả năng của các bộ nhớ cục bộ, sơ đồ truyền thông, các giao thức đồng bộ hoá, v.v. Để cài đặt các thuật toán song song trên các máy tính song song chúng ta phải sử dụng những ngôn ngữ lập trình song song. Nhiều ngôn ngữ lập trình song song đang được sử dụng như: Fortran 90, nCUBE C, Occam, C-Linda, PVM với C/C++, CDC 6600, v.v. I.2 Phân loại các kiến trúc máy tính Dựa vào các đặc tính về số lượng BXL, số chương trình thực hiện, cấu trúc bộ nhớ, v.v., Michael Flynn (1966) [20] đã đưa ra cách phân loại nổi tiếng được nhiều người chấp nhận. I.2.1 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 (program counter) đượ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. Hình 1-1 mô tả hoạt động của máy tính theo mô hình SISD. Đơn vị điều khiển Bộ nhớ BXL số học Luồng lệnh Luồng dữ liệu Luồng kết quả Tín hiệu điều khiển Hình 1-1 Mô hình của kiến trúc SISD Mô hình SISD còn được gọi là SPSD, đơ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. I.2.2 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ý (nhiều hơn một đơn vị) 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 BXL 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 BXL có luồng dữ liệu riêng. Máy tính SIMD có thể hỗ trợ xử lý kiểu vector, trong đó có thể gán các phần tử của vector cho các phần tử xử lý để tính toán đồng thời. Máy tính vector và các BXL mảng là mô hình chủ yếu thuộc loại này. Hình 1-2 mô tả hoạt động của máy tính theo mô hình SIMD, còn được gọi là SPMD. Đơn vị điều khiển (CU) Phần tử xử lý 1 Tín hiệu điều khiển Phần tử xử lý n Phần tử xử lý 2 . . . Tín hiệu điều khiển Hình 1-2 Mô hình của kiến trúc SIMD 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à Conn-ection Machine CM-2. I.2.3 Mô hình MISD: Đa luồng lệnh, đơn luồng dữ liệu 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 đượ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ý (PU) 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. CU 1 Phần tử xử lý 2 Luồng lệnh 1 Phần tử xử lý n Phần tử xử lý 1 . . . CU 2 CU n . . . Luồng lệnh 2 Luồng lệnh n Luồng dữ liệu 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ả cho PU 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. Hình 1-3 mô tả hoạt động của máy tính theo mô hình MISD Hình 1-3 Mô hình của kiến trúc MISD I.2.4 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 BXL, trong đó mỗi BXL 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 (global) khi cần, do vậy giảm thiểu được sự trao đổi giữa các BXL 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, ví dụ: BBN Butterfly, Alliant FX, iSPC của Intel, v.v. Mô hình của kiến trúc MIMD được mô tả như hình 1-4. CU 1 Phần tử xử lý 2 Luồng lệnh 1 Phần tử xử lý n Phần tử xử lý 1 . . . CU 2 CU n . . . Luồng lệnh 2 Luồng lệnh n Luồng dữ liệu 1 Luồng dữ liệu 2 Luồng dữ liệu n Hình 1-4 Mô hình của kiến trúc MIMD I.3 Kiến trúc máy tính song song MIMD SIMD Hybrid MISD Multiprocessor Multicomputer Data Flow Machine Array Processor Pipelined Vector Processor Pipelined Vector Processor Systolic Array SIMD-MIMD MIMD-SIMD Theo sự phân loại của Flynn thì có hai họ kiến trúc quan trọng cho các máy tính song song đó là SIMD và MIMD. Những kiến trúc khác có thể xếp theo hai mẫu đó. Mẫu hình các kiến trúc xử lý song song có thể phân chia như hình 1-5. Hình 1-5 Các mẫu hình kiến trúc xử lý song song Những kiến trúc khác nhau có thể tạo ra những khả năng khác nhau cho việc xử lý song song. Ngay trong kiến trúc tuần tự chúng ta cũng có thể tận dụng tốc độ cực nhanh của các bộ xử lý để thực hiện xử lý song song theo nguyên lý chia sẻ thời gian và chia sẻ tài nguyên. Tất nhiên đối với những kiến trúc máy tính song song thì mục đích chính là khai thác triệt để khả năng của kiến trúc song song để viết các chương trình song song. I.3.1 Song song hóa trong máy tính tuần tự Mục tiêu của xử lý song song là khai thác đến mức tối đa các khả năng sử dụng của các thiết bị phần cứng nhằm giải quyết nhanh những bài toán đặt ra trong thực tế. Nhưng cấu trúc phần cứng thường là trong suốt đối với những người lập trình. Sau đây chúng ta tìm hiểu về kỹ thuật song song áp dụng trong các máy tính có một BXL. Đa đơn vị chức năng Hầu hết các máy tính truyền thống chỉ có một đơn vị số học và logic (ALU) trong BXL. Ở mỗi thời điểm nó chỉ có thể thực hiện một chức năng. Nhiều máy tính thực tế hiện nay có thể có nhiều đơn vị chức năng (nhất là những chức năng chuyên biệt) và những đơn vị này có thể thực hiện song song được. Ví dụ như trong họ vi xử lý Intel 80XXX có bộ đồng xử lý 80387 làm việc với 80386 hay 80486. Bộ vi xử lý 80386 Bộ đồng vi xử lý 80387 Bộ nhớ chính Các cổng vào / ra Bus hệ thống (dữ liệu, địa chỉ, điều khiển) Hình 1-6 Kết nối bộ đồng xử lý. Bộ đồng xử lý chỉ thực hiện các chức năng riêng biệt ví dụ như khối đồ hoạ (Graphics Unit), khối xử lý tín hiệu (Signal processing Unit), khối xư lý ảnh (Image processing Unit), khối xử lý ma trận, vectơ (Vector and Matrix processor), khối xử lý dấu phẩy động (FPU: Floating Point Unit).v.v. Các khối này có thể thực hiện đồng thời và có tốc độ nhanh hơn rất nhiều so với bộ xử lý chính. Các bộ vi xử lý công nghệ cao hiện nay có thể cấy một vài khối chức năng đặc biệt (SFU: Special Function Unit ) này vào bên trong chip bộ xử lý nhằm giảm tối thiểu thời gian trễ do giao tiếp với SFU và như vậy sẽ làm tăng tốc độ thực hiện các phép xử lý trên chúng. Hoặc máy CDC 6600 (thiết kế năm 1964) có 10 đơn vị chức năng được tổ chức trong một BXL. Những đơn vị chức năng này độc lập với nhau và do vậy có thể thực hiện đồng thời. Thường đó là các đơn vị thực hiện các phép toán rất cơ bản như: phép cộng, nhân, chia, tăng giảm, các phép logic và các phép dịch chuyển (shift). Với 10 đơn vị chức năng và 24 thanh ghi (register), máy tính CDC 6600 có thể thực hiện tính toán với tốc độ tăng lên đáng kể, đáp ứng được nhiều bài toán xử lý song song. Vấn đề chính đối với những máy tính loại này là cần phải xây dựng bộ lập lịch tối ưu để phân chia các câu lệnh thực hiện sao cho tận dụng được tối đa các đơn vị chức năng cũng như các tài nguyên mà máy tính cung cấp. Xử lý theo nguyên lý hình ống trong CPU Nhiều pha thực hiện khác nhau của các câu lệnh có thể thực hiện theo nguyên lý hình ống, ví dụ như một đường ống lệnh được tổ chức gồm 5 phân đoạn: nạp câu lệnh về từ bộ nhớ, giải mã (decode), xác định các toán hạng, thực hiện các phép số học/logic và lưu trữ kết quả. Khi lệnh thứ nhất bắt đầu bước vào thực hiện ở giai đoạn thứ hai thì mã lệnh của lệnh tiếp theo được đọc từ bộ nhớ ra để thực hiện bước một. Bằng cách thực hiện như trên thì trong quá trình thực hiện của bộ xử lý có thể thực hiện được nhiều câu lệnh gối đầu nhau trong cùng một thời gian giống như dòng nước chảy trong đường ống. Những câu lệnh trong chương trình có thể thực hiện gối đầu nhau theo nguyên lý hình ống và nó sẽ hiệu quả hơn khi dựa vào kỹ thuật tạo ra vùng đệm dữ liệu. Sự gối đầu CPU và các thao tác vào/ra (I/O) Nhiều phép vào/ra có thể thực hiện đồng thời đối với nhiều nhiệm vụ tính toán khác nhau bằng cách sử dụng những bộ điều khiển vào/ra, các kênh hay những BXL vào/ra khác nhau. Trong các máy tính hiện nay có nhiều bộ điều khiển thiết bị vào/ra, cho phép đa xử lý vào/ra do vậy tăng được tốc độ trao đổi dữ liệu giữa các thiết bị ngoài với CPU. Các hệ thống bộ nhớ phân cấp Tốc độ các phép toán thực hiện trong BXL nhanh hơn rất nhiều việc truy cập vào bộ nhớ và tốc độ truy cập vào bộ nhớ nguyên thủy (bộ nhớ trong) nhanh hơn đối với bộ nhớ phụ (bộ nhớ ngoài).Hệ thống bộ nhớ phân cấp như thế có thể mô tả như hình1-7 CPU (Registers) Cache Main Memory Fixed Disks, Drum Magnetic Tapes Tăng khả năng lưu trữ Tăng về tốc độ truy cập Hình 1-7 Hệ thống bộ nhớ phân cấp Các thanh ghi được sử dụng trực tiếp cho ALU. Bộ nhớ cache được xem như vùng đệm giữa BXL và bộ nhớ chính. Sự song song hóa trong sự trao đổi dữ liệu theo cấu trúc phân cấp là cách khai thác chung để cải tiến hiệu quả xử lý của hệ thống. Ví dụ, trong khi dữ liệu được chuyển từ bộ nhớ phụ vào bộ nhớ chính thì đồng thời có thể chuyển dữ liệu từ cache vào cho CPU. Đa chương trình và chia sẻ thời gian Các hệ điều hành của máy tính đơn bộ xử lý cho phép thực hiện song song dựa vào cách tiếp cận phần mềm. Trong cùng một khoảng thời gian, có nhiều tiến trình cùng truy cập vào dữ liệu từ những thiết bị vào/ra chung. Chúng ta biết rằng phần lớn các chương trình đều có hai phần: phần vào/ra và các thành phần tính toán trong quá trình xử lý. Các hệ điều hành đa chương trình xáo trộn sự thực hiện của nhiều chương trình các loại khác nhau nhằm cân bằng giải băng thông thực hiện của các đơn vị chức năng. Trong một hệ đa chương trình, một tiến trình tính toán với cường độ cao có thể cắt ngang để tạm thời chiếm dụng CPU trong khi một tiến trình trước đó không đòi hỏi phải kết thúc công việc. Để tránh việc bị chặn lại (blocking) của các thiết bị thì khái niệm chia sẻ thời gian (Time-sharing) được sử dụng. Bộ lập lịch chia sẻ thời gian làm nhiệm vụ phân chia (gán) CPU cho mỗi tiến trình một khoảng thời gian cố định theo phương pháp quay vòng tròn. Bằng cách đó, tất cả các tiến trình đều được sẵn sàng để thực hiện trên cơ sở được phép sử dụng CPU và những tài nguyên khác một cách có cạnh tranh. Vấn đề chia sẻ thời gian cho nhiều tiến trình làm nảy sinh khái niệm các BXL ảo. Nghĩa là, mỗi tiến trình được cung cấp một môi trường được xem như một BXL ảo để thực hiện riêng cho tiến trình đó. Do vậy, về nguyên tắc việc phát triển những chương trình song song trên máy đơn BXL thực hiện được nếu có hệ điều hành cho phép nhiều tiến trình thực hiện, nghĩa là có thể xem hệ thống như là đa bộ xử lý. I.3.2 Mô hình trừu tượng của máy tính song song Thông thường khi xây dựng các thuật toán song song, chúng ta qui ước là phát triển thuật toán cho mô hình trừu tượng này, sau đó ánh xạ sang những máy tính cụ thể với một số các ràng buộc nào đó. CU BXL 1 Mạng kết nối Bộ nhớ chung chia sẻ hoặc kênh truyền thông BXL 2 BXL n Máy tính truy cập ngẫu nhiên song song P-RAM chứa một đơn vị điều khiển, bộ nhớ chung và một tập không giới hạn các BXL, mỗi BXL lại có bộ nhớ riêng (hình 1-8). . . . Hình 1-8 Máy tính P-RAM Mỗi BXL có một chỉ số duy nhất được sử dụng để xác định địa chỉ trong quá trình trao đổi các tín hiệu và quản lý các ngắt. Tất cả các BXL đều chia sẻ bộ nhớ chung với yêu cầu không bị giới hạn. Các câu lệnh có thể bắt đầu thực hiện ở bất kỳ thời điểm nào, ở bất kỳ vị trí nào của bộ nhớ (riêng hoặc chung). Đây là mô hình tổng quát cho máy tính song song kiểu MIMD. Về nguyên tắc, mô hình này cho phép thực hiện nhiều luồng lệnh đồng thời trên nhiều BXL khác nhau. Sau đây là một số điểm cần lưu ý khi phát triển những thuật toán cho các máy tính song song tổng quát. Không bị giới hạn về số lượng BXL Mọi vị trí của bộ nhớ đều truy cập được bởi bất kỳ BXL nào Không giới hạn về dung lượng bộ nhớ chia sẻ trong hệ thống Các BXL có thể đọc bất kỳ một vị trí nào của bộ nhớ, nghĩa là không cần phải chờ để những BXL khác kết thúc công việc truy cập vào bộ nhớ. Khi chuyển những thuật toán được xây dựng cho máy tính song song tổng quát sang máy tính cụ thể (lập trình song song) thì phải áp dụng một số các ràng buộc để đảm bảo chương trình thực hiện được trên những máy tính đó. Về hình thức, chúng ta thực hiện một trong những điều kiện sau: EREW: loại trừ vấn đề xung đột đọc / ghi CREW: cho phép đọc đồng thời, nhưng không cho phép xung đột khi ghi CRCW: Cho phép đọc, ghi đồng thời. Tất nhiên mô hình cho loại này ít có giá trị thực tiễn. Tiếp theo, chúng ta nghiên cứu một số kiến trúc máy tính song song đã có trên thị trường làm cơ sở để thực hiện lập trình sau này. I.3.3 Kiến trúc SIMD Trong máy tính SIMD, tất cả các phần tử xử lý đều được điều hành bởi một đơn vị điều khiển (CU). Tất cả các đơn vị xử lý nhận được cùng một lệnh từ CU nhưng hoạt động trên những tập dữ liệu khác nhau. Mô hình máy tính SIMD được chỉ ra như hình 1-9 có những đặc tính sau: Phân tán việc xử lý trên nhiều phần cứng Thao tác đồng thời trên nhiều phần tử dữ liệu Đơn vị điều khiển Phần tử xử lý 2 Tín hiệu điều khiển Phần tử xử lý n Phần tử xử lý 1 . . . Bộ nhớ Kết quả Luồng lệnh Luồng dữ liệu n Luồng dữ liệu 2 Luồng dữ liệu 1 Thực hiện cùng một tính toán trên tất cả các phần tử dữ liệu. Hình 1-9 Mô hình kiến trúc SIMD Xử lý theo mảng là dạng xử lý song song đầu tiên được nghiên cứu và cài đặt ứng dụng. Có hai loại máy tính xử lý theo mảng [20]: Những máy tính thực hiện các phép toán trên các bit, ví dụ MPP (Massively Parallel Processor), CM-1, CM-2, v.v. Những máy tính thực hiện các phép toán trên các từ (word), ví dụ ILLIAC IV, DAP, v.v. I.3.4 Kiến trúc MISD BXL hình ống chính là BXL kiểu MISD làm việc theo nguyên lý hình ống. Nguyên lý hình ống (pipelined) dựa vào phương pháp phân đoạn hoặc chia nhỏ một tiến trình tính toán thành một số đoạn nhỏ hơn để thực hiện trong các pha liên tiếp. Tất cả các giai đoạn của một tiến trình được thực hiện tuần tự, sẽ truyền kết quả cho pha tiếp theo. Như vậy, trong cách thực hiện theo nguyên lý hình ống, khi một giai đoạn công việc đang thực hiện thì một giai đoạn khác có thể nạp dữ liệu vào, và dữ liệu vào của giai đoạn này có thể là kết quả của giai đoạn trước nó. Ví dụ, hình 1-10 mô tả một tiến trình được phân thành 4 giai đoạn thực hiện tuần tự, nhưng có thể thực hiện song song theo nguyên lý hình ống để tăng tốc độ tính toán khi phải thực hiện nhiều tiến trình như thế. Pha 1 Pha 2 Pha 3 Pha 4 Một tiến trình được chia thành 4 giai đoạn: Pha 1 Pha 2 Pha 3 Pha 4 Pha1 Pha2 Pha3 Pha4 Thực hiện tuần tự hai tiến trình phải qua 8 giai đoạn: Thực hiện theo hình ống hai tiến trình trên chỉ cần trải qua 5 giai đoạn: Pha 1 Pha 2 Pha 3 Pha 4 Pha 1 Pha 2 Pha 3 Pha 4 Hình 1-10 Thực hiện tuần tự và hình ống của hai tiến trình gồm 4 giai đoạn Nếu ký hiệu Si là thời gian cần thiết để thực hiện giai đoạn thứ i thì: Tổng thời gian tính toán tuần tự là: 2 * (S1 + S2 + S3+ S4) Tổng thời gian tính toán hình ống là: S1 + S2 + S3+ S4 + S4 Nguyên lý hình ống có thể áp dụng theo hai mức: Hình ống theo đơn vị số học: Các đơn vị số học và logic ALU được tổ chức thành mảng, các phép toán bên trong được thực hiện theo nguyên lý hình ống (hình 1-11 (a)). Hình ống theo đơn vị câu lệnh: Các đơn vị điều khiển CU được phân đoạn và tổ chức theo hình ống (hình 1-11 (b)). CU ALU ALU . . . ALU Bộ nhớ CU . . . CU CU ALU Bộ nhớ Hình 1-11 (a) Xử lý hình ống theo ALU, (b) Xử lý hình ống theo CU Như chúng ta đã biết, việc xử lý theo hình ống được sử dụng để thực hiện gối đầu nhiều pha thực hiện các câu lệnh liên tiếp và sự truyền thông dữ liệu. Do vậy có thể xây dựng hình ống vòng tròn giữa các BXL, bộ nhớ và mạng liên kết như sau: Read Network Shared Memory Shared Memory Write Network Hình 1-12 Ví dụ về một hình ống vòng tròn Các phép toán thực hiện bởi CU theo kiến trúc này có thể chia thành 5 giai đoạn: Giai đoạn 1. Đọc dữ liệu: đọc dữ liệu từ bộ nhớ chia sẻ. Giai đoạn 2. Chuyển tải dữ liệu: chuyển dữ liệu từ bộ nhớ tới các phần tử xử lý PE thông qua mạng đọc (Read Network). Giai đoạn 3. Thực hiện câu lệnh: sử dụng PE để thực hiện các câu lệnh. Giai đoạn 4. Chuyển tải dữ liệu: chuyển các kết quả từ các PE tới bộ nhớ thông qua mạng ghi (Write Network). Giai đoạn 5. Lưu trữ dữ liệu : ghi lại các kết quả vào bộ nhớ chia sẻ. Nói chung, nguyên lý hình ống cho phép nhiều thao tác gối đầu nhau thực hiện đồng thời và hỗ trợ để khai thác được khả năng của kiến trúc song song theo các mức khác nhau. Mức câu lệnh. Từng câu lệnh chuyển vào cho một đoạn trong chu trình thực hiện sao cho sau khi đưa các lệnh vào hình ống thì chúng sẽ thực hiện lặp lại theo từng chu kỳ. Mức hệ thống con. Nhiều phép toán có thể thực hiện theo hình ống như ADD, MUL, DIV, và SORT thường có trong nhiều kiến trúc của máy tính. Những phép toán này được sử dụng theo hình ống rất thường xuyên. Mức hệ thống. Nhiều đoạn trong hình ống không cần phải thực hiện ở mức phần cứng mà có thể ở mức phần mềm. Kết quả nguyên lý hình ống đã được ứng dụng để thiết kế nhiều hệ máy tính như: CDC STAR 100, Texas Instruments ASC, Cray 1, v.v. I.3.5 Các bộ xử lý mảng tâm thu SAP Năm 1978 Kung và Leiserson đề xuất một loại kiến trúc được gọi là mảng tâm thu (Systolic Array) cho những tính toán đặc biệt. Đây là kết quả của dự án thực hiện ở Carnegie-Mellon University và nó được ứng dụng nhiều trong thiết kế các mạch tích hợp VLSI phục vụ chủ yếu cho việc xử lý tín hiệu và xử lý ảnh. Mảng tâm thu viết tắt là SA, là một mảng các đơn vị xử lý được kết nối cục bộ với nhau. Trong mảng tâm thu SA, mỗi PE được xem như một tế bào, một ô trong mảng, bao gồm: Một số thanh ghi (register) Một bộ cộng (adder) Các mạch điều khiển Đơn vị logic-số học ALU. Systolic Array Controller Host Processor Tín hiệu Dữ liệu vào Kết quả Dựa vào SA người ta xây dựng kiến trúc SAP Hình 1-13 Kiến trúc bộ xử lý mảng tâm thu Dữ liệu được xử lý trong mỗi ô và được truyền sang cho ô các lân cận. Trong kiến trúc SAP nêu trên, bộ điều khiển (Controller) làm nhiệm vụ giao diện cho BXL chính (Host Processor) và gửi các tín hiệu điều khiển quá trình vào/ra dữ liệu cho SA. Hoạt động của hệ thống theo từng nhịp và lặp lại một cách đều đặn để tận dụng được khả năng song song của tất cả các phần tử xử lý. SA có thể tổ chức theo nhiều cấu hình tôpô khác nhau. Hình 1-14 mô tả một số cấu hình phổ biến của SA. (a) (b) (c) Hình 1-14 Một số cấu hình phổ biến của mảng tâm thu: (a) mảng tuyến tính, (b) mảng hình tam giác, (c) mảng hai chiều hình vuông Hiệu quả của SA phụ thuộc rất nhiều vào các đặc tính vào/ra của dữ liệu. Nó sẽ rất hiệu quả đối với những bài toán mà số liệu đọc/ghi thực hiện với nhịp độ cao, đều đều và liên tục như các bài toán xử lý ảnh, qui hoạch tuyến tính, v.v. Ví dụ, xét bài toán nhân hai ma trận cỡ 2 ´ 2: A * B = C. * = a11 a12 b11 b12 c11 c12 a21 a22 b21 b22 c21 c22 Hiển nhiên Cị = åaik*bkj 1 2 4 5 3 9 6 7 8 a11 a21 a12 a22 b22 b12 b21 b11 c11 c12 c21 c22 Chúng ta có thể thiết kế SA có 9 PE để thực hiện nhân hai ma trận trên như sau: Nhập theo hàng Nhập theo cột Hình 1-15 Kiến trúc SA để thực hiện nhân hai ma trận Hệ thống SAP thực hiện như sau: Nhịp 1. Nhập b11, a11 vào ô số 1 và tính b11 * a11 Nhập b21 vào ô số 4 và a12 vào ô số 2 Nhịp 2. Truyền b11 từ ô 1 sang ô 2 Truyền a11 từ ô 1 sang ô 4 và tính a11 * b21 Truyền b11 từ ô 1 sang ô 2 và tính a12 * b11 Truyền b12 từ ô 4 sang ô 5 và a12 từ ô 2 sang ô 5 và tính a12 * b21, đồng thời ở ô số 5 tính c11 = a12 * b11 + a12 * b21 Nhập tiếp b12 vào ô số 4 và a21 vào ô số 2 Nhịp 3. Truyền c11 từ ô 5 sang ô 9 Truyền a21*b11 từ ô 2 sang ô 6 Truyền b12 từ ô 5 sang ô 6 Nhập a22 vào ô 3, và nhập b22 vào ô 7 Nhịp 4: Truyền a22 từ ô 3 sang ô 6 và tính a22 * b21 cộng dồn với kết quả được chuyển từ ố số 2 sẽ cho c21 = a21 * b11 + a22 * b21 Chuyển c11 từ ô 9 ra và gán cho c11 Tương tự đối với các trường hợp còn lại. Năm 1986 Intel kết hợp với Kung đã xây dựng một hệ máy tính kiểu SAP đặt tên là iWrap System, version sau được cải tiến vào năm 1990. Trong những năm 1990 còn có seri máy tính loại mini-super của Convex Computer Corporation được xây dựng từ những bộ CPU 64 bit được gắn với bộ nhớ chung. I.3.6 Kiến trúc máy tính kiểu MIMD Máy tính kiểu MIMD là loại đa BXL hoặc còn gọi là hệ thống đa máy tính, trong đó mỗi BXL có đơn vị điều khiển (CU) riêng và thực hiện chương trình riêng của mình. MIMD có những đặc trưng sau: Xử lý phân tán trên một số BXL độc lập Chia sẻ với nhau một số tài nguyên, trong đó có hệ thống bộ nhớ Mỗi BXL thao tác độc lập và có thể thực hiện đồng thời với nhau Mỗi BXL chạy một chương trình riêng. Đã có những máy tính kiểu MIMD được sản xuất như: (i) Intel iPSC Machine. Đây là những máy tính song song đầu tiên được tung ra thị trường từ 1985 với ver. 1.0, ver. 2.0 (1987), sau đó là iPSC/860 (năm 1990). Hệ thống có khoảng 64 nút và mỗi nút có các BXL 80386 /80387 với bộ nhớ từ 4 MB đến 16 MB. (ii) Carnegie-Mellon Multi-Mini Processor. Hệ C.mmp được xây dựng từ 1971 ở đại học Carnegie-Mellon gồm: 16 minicomputer được kết nối với 16 bộ nhớ thông qua bộ nhớ liên kết chéo nhiều giai đoạn để tạo ra hệ MIMD chia sẻ bộ nhớ. Thế hệ tiếp theo là Cm*. I.4 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. 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 BXL 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.v. 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 giá 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. I.4.1 Bộ nhớ kết hợp Bộ nhớ kết hợp (AM – Associative Memory) bao gồm các ô nhớ (cell) và logic kết hợp. Mỗi ô nhớ của AM có 4 đầu vào và hai đầu ra như hình 1-16. Các đầu vào (input) của mỗi ô nhớ bao gồm: - Bit đối số a - Bit đọc/ghi R/W xác định thao tác tương ứng cần thực hiện - Bit khoá k - Bit lựa chọn s để xác định ô nhớ thích hợp cho việc thực hiện đọc/ghi. Hai kết quả ở đầu ra: s k q a R/W m m Chọn Khoá Đối số Đọc/ghi Kết quả Đối sánh - Bit đối sánh m chỉ ra dữ liệu được lưu trong bộ nhớ có sánh được với bit đối số a. - Bit kết quả ra q. Hình 1-16 Cấu trúc của ô nhớ AM Argument Register Mask Register Buffer Register Tags Match Register Input Input Output Tất cả các bộ nhớ AM được tổ chức thành các từ (word) và được xây dựng thành mảng các ô giống nhau. Hình 1-17 mô tả một khối bộ nhớ AM có n từ và mỗi từ có m bit. 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. 0 1 n-1 . 0 1 . . m-1 Hình 1-17 Cấu trúc của bộ nhớ kết hợp I.4.2 Mô hình bộ nhớ truy cập ngẫu nhiên song song Mô hình tính toán song song được biết dưới tên gọi PRAM bao gồm bộ nhớ chung RAM với m vùng bộ 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 để trao đổi giữa các BXL. Nó cho phép các BXL truy cập vào bộ nhớ đồng thời và có thể hoạt động một cách dị bộ. Ví dụ, bộ xử lý Pi ghi dữ liệu vào một vùng nhớ và dữ liệu này có thể được Pj truy cập, nghĩa là Pi và Pj có thể dùng bộ nhớ chia sẻ để trao đổi với nhau. Mô hình loại này có các dạng sau: 1. Các phương thức truy cập bộ nhớ (Access Memory Primitives) Có một số cách khác nhau để các BXL có thể đọc / ghi một số dữ liệu gối đầu nhau. Đó là: Concurrent Read (CR): nhiều BXL có thể đọc đồng thời cùng một ô nhớ. Exlusive Read (ER): p BXL đọc được p vùng nhớ khác nhau. Mỗi BXL đọc được chính xác một vùng nhớ và mỗi vùng nhớ được đọc bởi một BXL. Concurrent Write (CW): cùng một thời điểm cho phép nhiều BXL ghi vào cùng một vùng nhớ. Exlusive Write (EW): p BXL ghi được vào p vùng nhớ khác nhau. Mỗi BXL ghi được vào chính xác một vùng nhớ và mỗi vùng nhớ được ghi bởi một BXL. 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à người ta phân nó thành các loại như sau: Ghi đồng thời có ưu tiên (Priority CW): các BXL được gắn mức ưu tiên và khi có nhiều BXL muốn ghi dữ liệu vào một vùng nhớ thì ưu tiên cho BXL 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 chung đồng thời (Common CW): tất cả các BXL đượ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 BXL được chọn để ghi dữ liệu đó. Ghi tự do đồng thời (Arbitrary CW): một số BXL muốn ghi dữ liệu đồng thời vào một vùng nhớ, nhưng chỉ một BXL đượ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 BXL thực hiện. Ghi ngẫu nhiên đồng thời (Random CW): BXL được lựa chọn để ghi dữ liệu là ngẫu nhiên. Ghi tổ hợp đồng thời (Combining CW): tất cả các dữ liệu mà các BXL đị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ớ đó. 2. Mô hình UMA của bộ nhớ chia sẻ Trong mô hình này, tất cả các BXL làm việc nhờ cơ chế chuyển mạch tập trung (Central switching) để điều khiển việc truy cập tới bộ nhớ chia sẻ. Thời gian truy cập vào bộ nhớ là như nhau đối với mọi BXL, nghĩa là bộ nhớ là đồng nhất. Có một số cách cài đặt cơ chế chuyển mạch như sau: Sử dụng đường dẫn chung (Common Bus) Lựa chọn chuyển mạch chéo (Crossbar Switch) Mạng nhiều giai đoạn (Multistage Network) 3. Mô hình NUMA của bộ nhớ chia sẻ Ngược lại với cách tổ chức trên, ở đây bộ nhớ phân tán và được chia thành các đơn thể độc lập. Bộ nhớ chia sẻ được phân tán cho tất cả các BXL thành bộ nhớ cục bộ (local) và tuyển tập tất cả các đơn thể bộ nhớ tạo ra bộ nhớ chung cho các BXL. Các BXL được phép truy cập đồng thời tới một hay nhiều đơn thể bộ nhớ và có thể hoạt động ít nhiều độc lập với nhau. Máy tính TC 2000 của BBN System và Technologies of Cambrige, Massachusett, và máy tính Cedar System của đại học Illinois được xây dựng theo cấu trúc bộ nhớ NUMA. TC 2000 có 128 BXL, mỗi BXL có 19 MB bộ nhớ nguyên thuỷ. 4. Kiến trúc bộ nhớ Cache-Only (COMA) Bộ nhớ chính được phân tán và được chuyển thành bộ nhớ cache (cất giữ), tất cả các bộ nhớ cache tạo ra không gian địa chỉ tổng thể. Có một số máy tính đã được xây dựng theo kiến trúc này: + Data Diffusion Machine (DDM) của Swedish Institute of Computer Science (1990). + KSR-1 Machine của Kendall Square Research (1992). 5. Bộ nhớ đa máy tính Mỗi nút trong hệ thống đa máy tính cũng chính là một máy tính có bộ nhớ riêng không chia sẻ với những BXL khác. Các BXL trao đổi với nhau thông qua việc gửi và nhận các thông điệp (message). Việc trao đổi dữ liệu trong mạng là điểm - tới điểm (point – to – point) thông qua sự liên kết tĩnh giữa các BXL. Vậy, với sự phát triển của công nghệ phần cứng dẫn tới xu thế xử lý song song để đáp ứng các yêu cầu tính toán của nhiều bài toán phức tạp trong thực tế. Nhiều máy tính có kiến trúc song song ra đời như các loại máy tính kiểu SIMD, MISD, MIMD đã tạo điều kiện cho công nghệ xử lý song song phát triển cả về mặt công nghệ lẫn triển khai ứng dụng. Xử lý song song cũng có thể thực hiện được trên các máy tuần tự kiểu Von Neumann bằng cách sử dụng nguyên lý xử lý hình ống hay chia sẻ thời gian, v.v. Trọng tâm của chương này là tìm hiểu các kiến trúc, thành phần và mối quan hệ của máy tính song song để tận dụng được hết khả năng xử lý song song của chúng. Các bộ nhớ được tổ chức thành bộ nhớ kết hợp, bộ nhớ truy cập ngẫu nhiên, bộ nhớ chia sẻ, v.v. là các mô hình chính cho máy tính song song. Vấn đề quan trọng trong thiết kế kiến trúc của máy tính song song là xác định cách để kết nối các bộ xử lý với nhau sao cho hoạt động hiệu quả nhất. CHƯƠNG II THUẬT TOÁN SONG SONG & LẬP TRÌNH SONG SONG II.1 Thuật toán song song II.1.1 Nguyên lý thiết kế thuật toán song song. Như trên đã nêu, nói đến xử lý song song là phải xét cả kiến trúc máy tính lẫn các thuật toán song song. Những thuật toán, trong đó có một số thao tác có thể thực hiện đồng thời được gọi là thuật toán song song. Tổng quát hơn, thuật toán song song là một tập các tiến trình hoặc các tác vụ có thể thực hiện đồng thời và có thể trao đổi dữ liệu với nhau để kết hợp cùng giải một bài toán đặt ra. Thuật toán song song có thể xem như là một tập hợp các đơn thể độc lập, một số trong số chúng có thể thực hiện tương tranh trên máy tính song song. Để thiết kế được các thuật toán song song cần phải trả lời các câu hỏi sau: Việc phân chia dữ liệu cho các tác vụ như thế nào? Dữ liệu được truy cập như thế nào, những dữ liệu nào cần phải chia sẻ? Phân các tác vụ cho các tiến trình (bộ xử lý) như thế nào? Các tiến trình được đồng bộ ra sao? Có năm nguyên lý chính trong thiết kế thuật toán song song: Các nguyên lý lập lịch: Tạo lịch trình để giảm tối thiểu các bộ xử lý sử dụng trong thuật toán sao cho thời gian tính toán là không tăng (xét theo khía cạnh độ phức tạp). Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện một dãy các thao tác {T1, T2, . . ., Tn}, trong đó Ti+1 thực hiện sau khi Ti kết thúc. Nguyên lý chia để trị: Chia bài toán thành những phần nhỏ hơn tương đối độc lập với nhau và giải quyết chúng một cách song song. Nguyên lý đồ thị phụ thuộc dữ liệu: Phân tích mối quan hệ dữ liệu trong tính toán để xây dựng đồ thị phụ thuộc dữ liệu và dựa vào đó để xây dựng thuật toán song song. Nguyên lý điều kiện tương tranh : Nếu hai tiến trình cùng muốn truy cập vào cùng một mục dữ liệu chia sẻ thì chúng phải tương tranh với nhau, nghĩa là chúng có thể cản trở lẫn nhau. Ngoài những nguyên lý nêu trên, khi thiết kế thuật toán song song còn một số điểm cần quan tâm. Tương tự như kiến trúc, hiệu quả thực hiện của thuật toán song song có thể rất khác nhau, mà yếu tố quan trọng nhất ảnh hưởng tới độ phức tạp tính toán là cấu hình tô pô liên kết mạng. Ví dụ: DAP là máy tính kiểu SIMD với 64 * 64 bộ xử lý, thời gian nhân ma trận là tuyến tính theo kích cỡ của ma trận và phụ thuộc vào đường truyền dữ liệu giữa các hàng với cột. Thuật toán song song phải được thiết kế dựa trên những kiến thức về kiến trúc máy tính, ngôn ngữ lập trình song song và các phương pháp tính toán. II.1.2 Các cách tiếp cận trong thiết kế Có ba cách tiếp cận để thiết kế thuật toán song song: Thực hiện song song hoá những thuật toán tuần tự, biến đổi những cấu trúc tuần tự để tận dụng được những khả năng song song tự nhiên của tất cả các thành phần trong hệ thống xử lý. Thiết kế những thuật toán song song mới phù hợp với kiến trúc song song. Xây dựng những thuật toán song song từ những thuật toán song song đã được xây dựng cho phù hợp với cấu hình tôpô mạng và môi trường song song thực tế. Như vậy, cách làm khá thông dụng là biến đổi các thuật toán tuần tự về song song, hay chuyển từ một dạng song song về dạng song song phù hợp hơn sao vẫn bảo toàn được tính tương đương trong tính toán. Do đó, khi biến đổi chúng ta cần trả lời hai câu hỏi: Kiến trúc nào phù hợp cho bài toán? Những bài toán loại nào sẽ xử lý hiệu quả trong kiến trúc song song cho trước? Ví dụ: Những máy tính kiểu SIMD không thích hợp để giải các bài toán, trong đó có nhiều tiến trình dị bộ. Ngược lại, máy tính kiểu MIMD lại không hiệu quả để giải quyết những bài toán trong đó có nhiều tiến trình cần phải đồng bộ. II.1.3 Một số phương pháp chuyển đổi từ chương trình tuần tự về song song II.1.3.1 Sự phụ thuộc dữ liệu giữa các tiến trình trong chương trình Như chúng ta đã biết, có rất nhiều phương pháp để chuyển đổi từ chương trình tuần tự sang chương trình song song. Thế nhưng không phải bất kỳ chương trình tuần tự nào chúng ta cũng có thể chuyển đổi sang chương trình song song một cách dễ dàng. Để thực hiện được các khối lệnh song song chúng ta phải hiểu rõ và xác định được tất cả các phụ thuộc dữ liệu của chúng trong chương trình, sau đó mô tả chúng thông qua đồ thị phụ thuộc dữ liệu. Đồ thị phụ thuộc dữ liệu là một đồ thị định hướng G=(V,E), trong đó V là tập các lệnh trong chương trình, E là các phụ thuộc dữ liệu. Ví dụ: Cho dãy lệnh S1, S2, S3 sau: S1: A := B + C S2: B := A + E S3: A := A + B Phân tích kỹ các câu lệnh trên chúng ta phát hiện ra một số sự phụ thuộc của chúng: Lệnh S1 tính giá trị của biến A và biến này được sử dụng trong S2 và S3. Do vậy, có sự phụ thuộc của S2, S3 vào S1 (ký hiệu là d1, d2). Lệnh S2 tính giá trị của biến B và biến này được sử dụng trong S3. Do vậy, có sự phụ thuộc của S3 vào S2 (ký hiệu là d3). Giá trị trước đó của biến B được sử dụng ở S1. Do vậy, có sự phụ thuộc vào S2 (ký hiệu d4 ). Cả hai lệnh S1 và S3 cùng tính giá trị của biến A và do vậy, có sự phụ thuộc (ký hiệu d5). Lệnh S3 tính giá trị của biến A và biến này được sử dụng trong S2 và S3. Do vậy, có sự phụ thuộc của S2, S3 vào S3 (ký hiệu là d6, d7). Sự phụ thuộc dữ liệu giữa các câu lệnh S1, S2, S3 có thể được biểu diễn qua đồ thị phụ thuộc dữ liệu như sau: S1 S2 S3 d1 d2 d4 d6 d7 d3 d5 Hình 2-1 Đồ thị phụ thuộc dữ liệu giữa S1, S2, S3. Trong chương trình chúng ta chỉ xét những sự phụ thuộc giữa các câu lệnh đơn. Có 5 loại phụ thuộc về mặt dữ liệu trong chương trình: Xét dãy lệnh gồm 2 câu lệnh S1, S2. Gọi: - DEF(S1) - tập tất cả các biến có giá trị bị thay đổi khi thực hiện câu lệnh S1. - USE(S1) - tập tất cả các biến được truy cập (được sử dụng) khi thực hiện câu lệnh S1. - DEF(S2) - tập tất cả các biến có giá trị bị thay đổi khi thực hiện câu lệnh S2. - USE(S2) - tập tất cả các biến được truy cập (được sử dụng) khi thực hiện câu lệnh S2. a. Phụ thuộc dòng dữ liệu (Data Flow Dependency): là sự phụ thuộc dữ liệu giữa S1 và S2 khi DEF(S1) ∩ USE(S2) ≠ f. Đây là loại phụ thuộc rất chung và rất khó loại bỏ bởi vì lệnh S2 yêu cầu giá trị của một biến và giá trị này phải được tính ở S1. Nghĩa là khi xuất hiện phụ thuộc dòng dữ liệu giữa các câu lệnh thì chúng không thực hiện song song được. Ví dụ: các phụ thuộc d1, d2, d3 là loại phụ thuộc dòng dữ liệu. Quan hệ phụ thuộc dòng dữ liệu được ký hiệu là: b. Phản phụ thuộc dữ liệu (Data Anti-Dependency): là sự phụ thuộc dữ liệu giữa S1 và S2 khi DEF(S2) ∩ USE(S1) ≠ f. Đây là loại phụ thuộc ngược với loại phụ thuộc nêu trên. Sự phụ thuộc này xuất hiện khi chúng ta sử dụng lại tên gọi của các biến, một biến đã được sử dụng trong S1 và sau đó được định nghĩa lại ở S2. Nghĩa là khi xuất hiện phản phụ thuộc dữ liệu giữa các câu lệnh thì chúng cũng không thực hiện song song được. Ví dụ: các phụ thuộc d4, d6, d7 là loại phản phụ thuộc dữ liệu. Quan hệ phản phụ thuộc dữ liệu được ký hiệu là: c. Phụ thuộc dữ liệu ra (Data Output Dependency): là sự phụ thuộc dữ liệu giữa S1 và S2 khi DEF(S2) ∩ DEF(S1) ≠ f. Sự phụ thuộc này xuất hiện do hai nguyên nhân: thứ nhất sử dụng lại tên của các biến (dùng chung), thứ hai tính tăng giá trị của cùng một biến. Nếu những lệnh này thực hiện đồng thời thì chúng sẽ ghi đè các giá trị vào cùng một ô nhớ. Do vậy, cần phải xác định chính xác thứ tự thực hiện để ngăn ngừa việc sử dụng những giá trị không đúng. Ví dụ: các phụ thuộc d5 là loại phụ thuộc dữ liệu ra. Quan hệ phụ thuộc dữ liệu ra được ký hiệu là: d. Phụ thuộc dữ liệu vào (Data Input Dependency): là sự phụ thuộc dữ liệu giữa S1 và S2 khi USE(S2) ∩ USE(S1) ≠ f. Bởi vì các lệnh này chỉ truy cập (đọc) và không làm thay đổi giá trị của các biến đó, do vậy các lệnh này có thể thực hiện theo bất kỳ thứ tự nào cũng được, nghĩa là có thể thực hiện song song. Quan hệ phụ thuộc dữ liệu vào được ký hiệu là: e. Phụ thuộc điều khiển dữ liệu ( (Data Control Dependency): là sự phụ thuộc dữ liệu giữa S1 và S2 khi sự thực hiện của lệnh này phụ thuộc vào giá trị của các biến được tính ở lệnh kia. Quan hệ phụ thuộc điều khiển dữ liệu được ký hiệu là: II.1.3.2 Một số phương pháp để loại bỏ sự phụ thuộc dữ liệu giữa các tiến trình Sự phụ thuộc giữa các câu lệnh đơn trong dãy lệnh có khả năng làm cho dãy lệnh không thể thực hiện song song được. Mặc dù vậy chúng ta có một số cách để loại bỏ sự phụ thuộc này. - Loại bỏ sự phụ thuộc dữ liệu bằng cách đặt lại tên của các biến để tránh việc chia sẻ các biến và từ đó tăng được mức độ song song của chương trình. S2 S1 Ví dụ: (S1): A = B + X (S2): C = A + D Để loại bỏ sự phụ thuộc dữ liệu giữa (S1) và (S2), ta có thể thay biến A của câu lệnh (S2) bằng A1 như sau: (S1): A = B + X (S2): C = A1 + D - Loại bỏ sự phụ thuộc dữ liệu ra bằng cách sử dụng các biến khác nhau. S1 S2 Ví dụ: (S1): A = B + C + D (S2): A = D * X Để loại bỏ sự phụ thuộc dữ liệu giữa (S1) và (S2), ta có thể thay biến A của câu lệnh (S2) bằng A1 như sau: (S1): A = B + C + D (S2): A1 = D * X - Loại bỏ sự phản phụ thuộc dữ liệu bằng cách sử dụng các biến khác nhau hoặc thực hiện các phép biến đổi (phép thế). S2 S1 Ví dụ 1: (S1): A = C + D (S2): C = D * X Để loại bỏ sự phản phụ thuộc dữ liệu giữa (S1) và (S2), ta có thể sử dụng biến khác cho câu lệnh (S2) như sau: (S1): A = C + D (S2): C1 = D * X Ngoài ra ta có thể sử dụng một số cách biến đổi để loại bỏ các mối quan hệ về dữ liệu giữa các tiến trình. Ví dụ 2: Xét dãy các câu lệnh sau: (S1): A = B + C (S2): B = A * 3 (S3): A = 2 * C (S4): P = B >= 0 if (P is true) (S5): then D = 1 (S6): else D = 2 endif Đồ thị phụ thuộc dữ liệu của đoạn chương trình trên được mô tả như hình vẽ: S1 S2 S3 S4 S6 S5 Hình 2-2 Đồ thị phụ thuộc dữ liệu Để xử lý được song song, thì cần thiết phải loại bỏ đi một số những loại phụ thuộc dữ liệu có thể. Ví dụ loại bỏ những quan hệ phản phụ thuộc dữ liệu và phụ thuộc dữ liệu kết quả bằng cách thay biểu thức tính B ở S1 vào S2, ta thu được đoạn chương trình sau: S2’: B = (B + C) * 3 S3: A = 2 * C S4: P = B >= 0 if (P is true) S5: then D = 1 S6: else D = 2 endif S3 S2’ S4 S5 S6 Đồ thị phụ thuộc dữ liệu rút gọn của đoạn chương trình trên Hình 2-3 Đồ thị phụ thuộc dữ liệu rút gọn Tuy nhiên, không phải lúc nào ta cũng có thể áp dụng thành công các phép biến đổi đơn giản đó. Ví dụ, xét chu trình sau: for (i = 0; i < N; i++) A = A + i; Chu trình trên có sự phụ thuộc dữ liệu ra vì nó làm tăng giá trị của cùng một biến. Nếu thực hiện song song thì chúng ghi đè các giá trị vào cùng một ô nhớ. Điều này khiến chu trình cho kết quả sai khi thực hiện song. Hiển nhiên có thể viết nó dưới dạng tương đương không sử dụng chu trình for i = 0; aa: if(i > N) stop; a = a + i; i++; goto aa; Trong mỗi bước lặp đều phải sử dụng những tên biến khác nhau nếu muốn loại bỏ phản phụ thuộc dữ liệu. Điều này không thể thực hiện được vì số vòng lặp là bất kỳ. Chúng ta cũng cần lưu ý thêm là quan hệ phụ thuộc dữ liệu là không bắc cầu. Nghĩa là nếu S2 phụ thuộc vào S1, S3 phụ thuộc vào S2 thì không kết luận được S3 phụ thuộc dữ liệu vào S1. Ngoài ra, chúng ta xét đến sự phụ thuộc theo chu trình và theo mảng: II.1.3.3 Phụ thuộc theo chu trình và theo mảng Trong thực tế, hầu hết các chương trình đều có các đoạn chương trình lặp theo một cấu trúc lặp nào đó. Chính vì thế nên những phép đặt lại tên biến như trên (thường chỉ áp dụng cho những biến và câu lệnh đơn) trở nên khó khăn. Chúng ta cần phải tập trung nghiên cứu về khả năng song song của các chu trình vì các chu trình lặp thường hướng tới sự xử lý song song trên các tài nguyên được hỗ trợ. Trong các cấu trúc dữ liệu, mảng được xem là cấu trúc dữ liệu đơn giản và phù hợp nhất cho các chu trình. Nhưng nếu xem mảng như là một biến trong khi xem xét sự phụ thuộc dữ liệu trong chu trình thì sẽ làm giảm khả năng xử lý song song của các câu lệnh trong chu trình đó. Thật vậy, để thấy rõ được điều này ta có thể xét ví dụ sau: DO I A[2*I+1] = B[i] (1) D[i] = A[2*I] (2) ENDDO - Nếu xem mảng A như một thực thể đơn thì (1) và (2) phụ thuộc theo dòng dữ liệu. - Nếu xét thêm chỉ số mảng thì phần tử của mảng A trong câu lệnh (1) là phần tử lẻ còn phần tử của mảng A trong câu lệnh thứ (2) là phần tử chẳn, nên (1) và (2) không có sự phụ thuộc vào dữ liệu. Xét ví dụ sau: DO I A[I] = A[I-1] + 1 (*) ENDDO - Khi I = i : A[i] = A[i-1] + 1 - Khi I = j : A[j] = A[j-1] + 1 Không mất tính tổng quát, ta giả sử rằng i<j, khi đó vòng lặp thứ i và thứ j phụ thuộc dữ liệu với nhau khi và chỉ khi i = j -1. Với i, j là các số nguyên và i < j thì phương trình này có vô số nghiệm. Điều này dẫn đến chu trình (*) không thể thực hiện song song được. II.1.3.4 Biến đổi chương trình Như trên đã đề cập, để có được chương trình song song thì phải loại bỏ được sự phụ thuộc của các câu lệnh trong chương trình bằng cách biến đổi các mã lệnh. Sau đây chúng ta xét một số trường hợp biến đổi mã chương trình để loại bỏ những phụ thuộc dữ liệu trong chương trình. a- Các biến qui nạp : Biến qui nạp là loại biến trong chu trình mà các giá trị liên tiếp của nó tạo ra dãy cấp số học. Ví dụ: Xét đoạn chương trình sau: m = 0; DO i = 1 to N m = m + k; (1){m là biến qui nạp} x[m] = a[i] (2) END Hiển nhiên là hai câu lệnh (1) và (2) có quan hệ phản phụ thuộc dữ liệu. Khi vòng lặp trước tính giá trị của m, và giá trị này được sử dụng ở lệnh thứ hai thì vòng lặp hiện thời không biết được giá trị của m. Do đó, chúng phải thực hiện tuần tự. Tuy nhiên, tại mỗi vòng lặp chúng ta có thể dự báo được giá trị của m nên ta cũng có thể loại bỏ được sự phụ thuộc dữ liệu giữa 2 câu lệnh (1) và (2) để từ đó có thể thực hiện song song chu trình trên như sau: Giá trị k là bất biến trong các vòng lặp và được cộng liên tiếp vào sau mỗi vòng lặp, do vậy, ở vòng lặp thứ i, m = i * k. Đoạn chương trình trên được viết thành: DO i = 1 to N x[i*k] = a[i] End Ta nhận thấy ngay, các vòng lặp của chu trình này không phụ thuộc vào nhau, do vậy chúng có thể thực hiện song song. Cách biến đổi loại này cho phép chuyển chương trình tuần tự thành chương trình song song. b- Sự phụ thuộc tiến: Sự phụ thuộc tiến là loại phản phụ thuộc dữ liệu giữa các vòng lặp của chu trình. Ví dụ: Xét chu trình lặp sau: Do i = 1 to N x[i] = x[i+1] end Dễ nhận thấy, chu trình này không thực hiện song song được.Chu trình trên làm nhiệm vụ sao tất cả các phần tử của một mảng sang chính mảng đó với chỉ số giảm đi một, do vậy nó phải thực hiện tuần tự. Tuy nhiên ta có thể khắc phục điều này bằng cách tạo ra một mảng sao của mảng gốc rồi mới thực hiện công việc sao lưu. Chương trình trên có thể khắc phục như sau: Do i = 1 to N x1[i] = x[i] end Do i = 1 to N x[i] = x1[i+1] end Cả hai chu trình trên đều có thể thực hiện song song được. Nếu chúng ta có N bộ xử lý thì chỉ cần hai đơn vị thời gian của CPU là thực hiện được 2 chu trình trên. Lưu ý: Trong trường hợp xử lý song song với các bộ xử lý khác nhau có thể xuất hiện những vấn đề khá nguy hiểm. Chẳng hạn khi bộ xử lý Pk sao xong x[k] cho x1[k] và nó bắt đầu thực hiện ngay x[k] = x1[k+1], trong khi Pk+1 lại chưa thực hiện xong việc sao x[k+1] cho x1[k+1]. Do vậy, có thể dẫn tới vấn đề xung đột dữ liệu. Để khắc phục vấn đề nêu trên, người ta thường đưa ra một hàng rào (barrier) để ngăn cách việc thực hiện của hai chu trình đó. c- Sự phụ thuộc lùi : Ở trên ta đã xét trường hợp xuất hiện phản phụ thuộc dữ liệu khi giá trị của một phần tử mảng được xác định thông qua những phần tử đứng sau nó. Thế khi các phần tử của mảng trong chu trình lại được xác định thông qua những phần tử đứng trước chúng (lùi về phía trước) thì sẽ như thế nào? Lúc này trong chu trình sẽ xuất hiện sự phụ thuộc dữ liệu. Để loại bỏ những phụ thuộc dữ liệu kiểu này thật không đơn giản chút nào. Không có giải pháp chung cho vấn đề loại bỏ phụ thuộc dữ liệu trong trường tổng quát. Ngay cả khi có giải pháp chung cho trường hợp tổng quát này thì cái giá phải trả cho nó là quá đắt. Ví dụ : Xét chu trình sau : Do i = 1 to N x[i] = x[i-1] + y[i] end Trong ví dụ nêu trên, để loại bỏ sự phụ thuộc dữ liệu trong chu trình, ta có thể khai triển và viết lại cách tính x[i] như sau: Do i = 1 to N x[i] = x[0] + y[1]+ y[2]+ … + y[i] end Mặc dù trong chu trình không còn sự phụ thuộc lùi nhưng cái giá phải trả chính là độ phức tạp tính toán của chu trình lại tăng lên khá nhiều. d- Sự phân tách chu trình: Trong nhiều trường hợp chúng ta có thể phân tách một chu trình thành nhiều chu trình con để tránh sự phụ thuộc về quan hệ dữ liệu ngăn cản khả năng song song của chu trình. Ví dụ: Do i = 1 to N a[i] = b[i] + c[i]; (1) c[i] = a[i-1] (2) end Sự tham chiếu giữa các mảng a và c dẫn đến sự phụ thuộc giữa các vòng lặp của chu trình. Chúng ta nhận thấy rằng, giá trị c[i] ở lệnh thứ nhất luôn là những giá trị lưu trữ cũ của mảng c và a[i-1] được sử dụng ở lệnh thứ hai là giá trị đã được tính ở vòng lặp trước đó (vòng thứ i -1). Do vậy để loại bỏ quan hệ phụ thuộc dữ liệu trong chu trình chúng ta có thể tách chu trình trên thành hai chu trình như sau: Do i = 1 to N a[i] = b[i] + c[i]; end Do i = 1 to N c[i] = a[i-1] end Trong hai chu trình trên không còn sự phụ thuộc do vậy có thể thực hiện song song. Tương tự, chúng ta xét trường hợp tiến: Do i = 1 to N a[i] = b[i] + c[i]; c[i] = a[i+1] end Phần tử c[i] ở lệnh hai được tính theo giá trị của a[i+1], là giá trị trước khi nó được cập nhật ở lệnh thứ nhất, ngược lại c[i] được sử dụng ở lệnh thứ nhất lại là giá trị cũ trước khi được cập nhật ở lệnh thứ hai. Trong trường hợp này, để tách được chu trình trên thành hai chu trình chúng ta phải sao mảng c sang mảng phụ x. Kết quả biến đổi chu trình này thành hai chu trình trong đó không còn sự phụ thuộc dữ liệu. Do i = 1 to N x[i] = c[i]; c[i] = a[i+1] end Do i = 1 to N a[i] = b[i] + x[i]; end e- Các chu trình lồng nhau Ở trên chúng ta mới chỉ xét những chu trình có một chỉ số lặp. Tuy nhiên cách biến đổi như trên cũng có thể áp dụng cho các chu trình lồng nhau (chu trình nhiều chỉ số). Ví dụ: Xét hai chu trình lồng nhau: Do i = 1 to N Do j = 1 to N x[i,j] = x[i,j-1] + z[i]; end Có thể nói gì về khả năng thực hiện song song của hai chu trình này? Mảng z được sử dụng trong chu trình hoàn toàn không gây ra sự phụ thuộc nào cả. Chỉ số thứ nhất của mảng x là i, cũng chính là chỉ số của chu trình, nhưng không có sự tham chiếu chéo giữa các vòng lặp. Vậy, chu trình lặp bên trong (chu trình lặp theo i) có thể thực hiện song song. Chỉ số thứ hai của mảng x là j, là chỉ số của chu trình thứ nhất và ở đây có sự tham chiếu chéo giữa các vòng lặp, nghĩa là có sự phụ thuộc dòng dữ liệu của các lần lặp ở vòng ngoài. Trường hợp này không có cách biến đổi đơn giản về dạng khả song song giống như mục c- Sự phụ thuộc lùi II.1.4 Phân tích, đánh giá thuật toán song song Đánh giá thuật toán tuần tự có thể căn cứ chủ yếu vào thời gian thực hiện được tính theo hàm của kích cỡ dữ liệu vào (input). Hàm này được gọi là độ phức tạp tính toán thời gian f(n) của thuật toán và được ký hiệu là O(f(n)). Một cách hình thức O( ) được định nghĩa như sau: Một thuật toán có độ phức tạp tính toán f(x) = O(g(x)) Û Tồn tại số C dương và số nguyên x0 sao cho 0 ≤ f(x) ≤ C * g(x), với mọi số lượng dữ liệu vào x ≥ x0. Hiển nhiên g(x), f(x) là hai hàm có giá trị dương. O(1) ký hiệu cho một hằng số bất kỳ. Độ phức tạp tính toán của thuật toán song song không chỉ phụ thuộc vào kích cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ xử lý được phép sử dụng trong hệ thống. Độ phức tạp thời gian là thước đo quan trọng nhất đánh giá mức độ hiệu quả của thuật toán song song. Chúng ta giả thiết rằng mô hình tính toán có p bộ xử lý. Nghĩa là mức độ song song là có giới hạn. Ngược lại, mức độ song song không bị giới hạn khi số các bộ xử lý là không bị chặn. Độ phức tạp thời gian của thuật toán song song sử dụng p bộ xử lý để giải một bài toán có kích cỡ n là hàm f(n,p) xác định thời gian cực đại trôi qua giữa thời điểm bắt đầu thực hiện thuật toán bởi một bộ xử lý và thời điểm kết thúc của các bộ xử lý đối với bộ dữ liệu vào bất kỳ. Có hai loại thao tác khác nhau trong các thuật toán song song: Các phép toán cơ sở như +, -, *, /, AND, OR, v.v. Các phép toán truyền dữ liệu trên các kênh truyền. Độ phức tạp thời gian của thuật toán song song được xác định bởi số các phép toán cơ sở và số các bước truyền tải dữ liệu giữa các bộ xử lý với nhau. Từ đó suy ra, độ phức tạp thời gian của thuật toán song song không chỉ phụ thuộc vào mô hình tính toán mà còn phụ thuộc vào số bộ xử lý được sử dụng. Nói chung, chương trình tính toán song song thường bắt đầu bằng việc nhập dữ liệu vào bộ nhớ và kích hoạt một phần tử xử lý. Mỗi bước tính toán, phần tử xử lý này có thể đọc một số dữ liệu từ bộ nhớ, thực hiện một số phép toán cơ sở và ghi kết quả vào bộ nhớ riêng hoặc bộ nhớ chung. Đồng thời mỗi bước tính toán, một phần tử xử lý có thể kích hoạt một hay một số phần tử xử lý khác. Thực tế thì các máy tính đều có số bộ xử lý là hữu hạn, nên những thuật toán song song không bị giới hạn chỉ có nghĩa sử dụng khi chúng có thể chuyển đổi về thuật toán song song bị giới hạn. Có ba cách định nghĩa khái niệm [20] liên quan đến độ phức tạp của thuật toán song song: Định nghĩa 1: Một thuật toán song song có độ phức tạp tính toán O(T) với P bộ xử lý khi nó thực hiện nhiều nhất là O(T* P) phép toán cơ sở (định lý Brent). Định nghĩa 2: Một thuật toán song song có độ phức tạp tính toán O(T) sử dụng rất nhiều bộ xử lý để thực hiện O(e) phép toán cơ sở khi cài đặt với P bộ xử lý thì sẽ có độ phức tạp thời gian là O(ée/Pù + T). Định nghĩa 3: Một thuật toán song song có độ phức tạp tính toán O(T) với P bộ xử lý có thể cài đặt với éP/pù , 1≤ p ≤ P bộ xử lý thì sẽ có độ phức tạp thời gian là O(p*T). Định nghĩa 2 chỉ ra rằng khi số bộ xử lý được sử dụng giảm xuống trong một phạm vi nhất định thì thuật toán tiếp tục làm việc nhưng thời gian thực hiện sẽ tăng lên. Định nghĩa 3 khẳng định rằng có cách để cài đặt thuật toán song song khi số các bộ xử lý được sử dụng bị giảm xuống. Mức độ hiệu quả của thuật toán được thể hiện ở mức độ song song của thuật toán. Mức độ song song của thuật toán là số lượng cực đại các phép toán độc lập có thể thực hiện đồng thời ở mỗi thời điểm thực hiện của thuật toán. Ký hiệu P(W) là độ song song của thuật toán, thì thuật toán hiệu quả để giải bài toán có cỡ W là những thuật toán chỉ cần sử dụng nhiều nhất P(W) bộ xử lý. Ngoài ra, để đánh giá được thuật toán song song chúng ta còn phải xét tới hệ số gia tốc của nó. Hệ số gia tốc của thuật toán song song sử dụng p bộ xử lý được xác định như sau: Sp = TS / Tp Trong đó, + TS là thời gian thực hiện tính toán trên một bộ xử lý + Tp là thời gian thực hiện tính toán trên p bộ xử lý. Với giả thiết là bộ xử lý tuần tự và bộ xử lý song song là như nhau. II.2 Các mô hình lập trình song song II.2.1 Lập trình chia sẻ bộ nhớ Giả thiết rằng chúng ta có một hệ thống đa bộ xử lý đối xứng SMP. Đó là hệ thống trong đó tất cả các bộ xử lý là như nhau, không có những bộ xử lý đặc biệt để xử lý vào/ra, cũng không có bộ xử lý được gán cho nhiệm vụ đặc biệt nào khác. Đây là mô hình chung cho các hệ thống đa xử lý. Để nghiên cứu về song song, chúng ta không nhất thiết phải có hệ đa bộ xử lý vật lý. Trong môi trường UNIX, chúng ta có thể tạo ra nhiều tiến trình khác nhau trong hệ thống và chúng được sử dụng để mô phỏng lập trình đa bộ xử lý. Hệ thống UNIX cung cấp những đặc tính như tín hiệu điều khiển Semaphore và bộ nhớ chia sẻ (bộ nhớ có thể chia sẻ cho các tiến trình khác nhau) [14] để các tiến trình có thể xử lý song song như chúng ta cần. Song, tốc độ xử lý bài toán khi chạy chương trình thì không tăng tốc được như mong muốn. Một vấn đề quan trọng cần xem xét khi xử lý song song là cần bao nhiểu nút (bộ xử lý, tiến trình) để chương trình song song thực hiện hiệu quả nhất? Nhiều chương trình được xây dựng phụ thuộc vào một cấu hình xác định. Nói chung, loại chương trình phụ thuộc như vậy là không tốt, vì khi một bộ xử lý bận thì có thể thay đổi chương trình hoặc chờ để bộ xử lý đó quay lại. Trong những hệ thống đa nhiệm như UNIX, số bộ xử lý và số các tiến trình không nhất thiết phải bằng nhau. Hầu hết các hệ UNIX đều cho phép tạo ra một số các tiến trình bất kỳ và chúng được lập lịch cho những bộ xử lý thích hợp (sẵn sàng thực hiện chúng). Như vậy, về nguyên tắc, chương trình là tập các tiến trình và việc viết chương trình là độc lập với các bộ xử lý, việc phân chia các tiến trình cho các bộ xử lý là công việc của hệ điều hành. Tất nhiên vấn đề lập lịch trong hệ thống đa nhiệm là bài toán khó và chúng ta không thảo luận ở đây. Trong lập trình thủ tục tuần tự (như với C, Pascal, Fortran), ta có thể mô hình lời giải một cách độc lập với các ngôn ngữ lập trình. Hầu hết các thuật toán đều dễ dàng cài đặt trên nhiều ngôn ngữ lập trình khác nhau. Điều này thực hiện được bởi hầu hết các ngôn ngữ lập trình thủ tục đều sử dụng những lệnh, cấu trúc điều khiển chuẩn như lệnh gán, rẽ nhánh if-then, các cấu trúc lặp (for, while, repeat), v.v. Tương tự như thế có thể nghĩ về các thành phần tổng quát của lập trình song song trong hệ thống bộ nhớ chia sẻ. Trong môi trường lập trình chia sẻ bộ nhớ có hai ràng buộc quan trọng như sau: Một tiến trình có thể chờ một khoảng thời gian bất kỳ giữa hai lệnh cần thực hiện. Giả sử bộ xử lý P thực hiện một chương trình có một 100 lệnh, bộ xử lý Q thực hiện chương trình có 10 lệnh và cùng bắt đầu thực hiện đồng thời. Thậm chí, tất các lệnh có tốc độ thực hiện như nhau cũng không thể nói rằng Q sẽ kết thúc trước P. (ii) Không thể xem các lệnh thực hiện là nguyên tố ở mức các ngôn ngữ lập trình. Ví dụ, một lệnh đơn giản như: a = a + 1 sẽ là một dãy từ một đến bốn lệnh trong ngôn ngữ máy. Mà ta cũng biết rằng, các tiến trình và hệ điều hành chỉ nhận biết được các câu lệnh của ngôn ngữ máy. II.2.1.1 Lập trình chia sẻ bộ nhớ dựa vào tiến trình Tạo lập và huỷ bỏ tiến trình Yêu cầu đầu tiên của xử lý song song là khả năng tạo ra một số các tiến trình cần thiết cho bài toán. Tương tự là khả năng huỷ bỏ chúng khi phần việc xử lý song song kết thúc để giải phóng các tài nguyên mà các tiến trình đã chiếm giữ và không cản trở hoạt động của những tiến trình khác. Để thêm N tiến trình, chúng ta viết: id = create_process(N); Lệnh này tạo thêm N tiến trình và một tiến trình cha nữa để thực hiện câu lệnh đó, kết quả là có N+1 tiến trình như nhau được tạo ra và mỗi giá trị của id được gán tương ứng cho một tiến trình. Sử dụng những tiến trình đã được tạo ra chúng ta có thể viết chương trình song song dạng: id = create_process(N); switch(id){ case 0: … do NhiemVu0 …; break; case 1: … do NhiemVu1 …; break; case 2: … do NhiemVu2 …; break; . . . case N: … do NhiemVuN …; break; } Sau khi những công việc trên thực hiện xong, chúng ta muốn một tiến trình (như một tiến trình chủ) tiếp tục thực hiện những phần việc tuần tự còn lại, còn những tiến trình khác kết thúc. Khi đó chúng ta viết join_process(N, id); Chỉ tiến trình tương ứng với giá trị id còn tiếp tục hoạt động, những tiến trình là kết thúc sau lời gọi hàm trên. Nếu ta đặt sau nó một câu lệnh thì: Lệnh này sẽ không được thực hiện cho đến khi tất cả các tiến trình đều thực hiện join_process(). Sau đó chỉ còn lại một tiến trình hoạt động, do vậy vấn đề xử lý song song không xuất hiện mà là xử lý tuần tự. Vấn đề là khả năng các tiến trình được tạo lập nhìn thấy dữ liệu của nhau như thế nào? Một mặt một tiến trình có thể muốn giữ một phần dữ liệu cục bộ cho riêng mình, không cho những tiến trình khác nhìn thấy/truy cập tới những dữ liệu đó. Mặt khác, nó cũng muốn trao đổi thông tin với các tiến trình khác. Xử lý vấn đề che giấu hay chia sẻ thông tin như thế nào còn tuỳ thuộc vào mô hình mà chúng ta áp dụng, dựa vào tiến trình hay luồng. Các tiến trình trong UNIX được sử dụng như các đơn vị tính toán độc lập, theo mặc định, việc tính toán và cập nhật bộ nhớ của một tiến trình không là không nhìn thấy được bởi các tiến trình khác. Đối với các luồng, tất cả các thông tin, theo mặc định, là nhìn thấy được. Do vậy, trong mô hình này cần phải cố gắng rất nhiều để che giấu thông tin. Bây giờ chúng ta xét một số hàm điều phối vấn đề chia sẻ bộ nhớ. Khi muốn sử dụng bộ nhớ chung, ta cần phải xin cấp phát bộ nhớ và sau khi sử dụng xong phải giải phóng chúng. Người lập trình phải có trách nhiệm giải phóng bộ nhớ chia sẻ một cách tường minh khi chúng không còn cần thiết sử dụng. Có hai hàm cơ sở: shared(m, &id): giống như malloc(), nhưng cấp phát m byte bộ nhớ chia sẻ cho tiến trình id. free_shm(): giải phóng bộ nhớ đã được cấp. Ví dụ: Bài toán loại trừ nhau. Trước tiên chúng ta xét đoạn chương trình sau: main(){ int id, sid, *i, j; i = (int*)shared(sizeof(int), &sid); *i = 100; j = 100; printf(“Before fork: %d, %d\n”, *i, j); id = create_process(2); *i = id; j = id * 2; // (1) printf(“After fork: &d, %d\n”, *i, j);// (2) join_process(3, id); printf(“After join: &d, %d\n”, *i, j); free_shm(sid); } Chúng ta hãy dự đoán xem các kết quả của hai lệnh printf(“After …”) cho kết quả như thế nào? Lưu ý rằng, i là biến chia sẻ, id là duy nhất (số hiệu) đối với mỗi tiến trình. Giả sử câu lệnh (1) thực hiện với id = 2, liệu dòng (2) có in ra là “After fork: 2, 4” hay không? Câu trả lời là không nhất thiết. Các giá trị của *i, j in ra có thể là 2, 4; 4, 4; 6, 4; bởi vì khi tiến trình thứ i thực hiện xong câu lệnh (1), trước khi nó thực hiện (2) thì có thể các tiến trình khác đã cập nhật lại giá trị của i. Đây là bài học quan trọng của lập trình chia sẻ bộ nhớ. Vấn đề truy cập vào bộ nhớ chia sẻ là phải có sự hợp tác chặt chẽ giữa các tiến trình. Nếu có một tiến trình truy cập vào một vùng nhớ với ý định cập nhật thì nó phải được đảm bảo rằng không một tiến trình nào khác đọc dữ liệu ở vùng đó cho đến khi việc cập nhật đó kết thúc. Muốn giải quyết được vấn đề trên thì phải có cơ chế đảm bảo rằng, các khối lệnh của chương trình được thực thi chỉ bởi một tiến trình tại mỗi thời điểm. Nếu có một tiến trình bắt đầu vào thực hiện một khối lệnh thì những tiến trình khác không được vào khối lệnh đó. Những cơ chế như thế gọi là gài khoá (lock). Khi vào một vùng lệnh thì dùng chìa để khoá nó lại, sau đó mở khoá (unlock) khi ra khỏi vùng đó và trao chìa cho tiến trình khác có nhu cầu. Để thực hiện các yêu cầu đó chúng ta sử dụng: init_lock(Id): Khởi động bộ khoá vùng nhớ chia sẻ, trong đó Id là tên của vùng nhớ sử dụng chung. lock(Id): khoá lại vùng nhớ Id. Nếu một tiến trình đã dùng chìa để khoá lại một vùng nhớ chung thì những tiến trình khác muốn truy cập vào đó sẽ phải chờ. Giả thiết rằng chỉ có một chìa khoá, do vậy chỉ khi chiếc khoá đã được một tiến trình nào đó mở ra thì chìa của nó mới được giao cho tiến trình khác sử dụng. unlock(Id): mở khoá vùng đã bị khoá và trả lại chìa cho tiến trình khác. Sử dụng cơ chế gài khoá để viết lại chương trình trên cho đúng là như sau: main(){ int *lock1,id, sid1, sid2, *i, j; lock1 = (int*)shared(sizeof(int), &sid1); init_lock(lock1); i = (int*)shared(sizeof(int), &sid2); *i = 100; j = 100; printf(“Before fork: %d, %d\n”, *i, j); id = create_process(2); lock(lock1); *i = id; j = id * 2; // (1) printf(“After fork: &d, %d\n”, *i, j);// (2) unlock(lock1); join_process(3, id); printf(“After join: &d, %d\n”, *i, j); free_shm(sid1); free_shm(sid2); } Chúng ta nhận thấy cơ chế gài khoá giải quyết được bài toán loại trừ lẫn nhau, nghĩa là nó chỉ cho phép một tiến trình được vào thực hiện một vùng mã lệnh tại mỗi thời điểm. Ví dụ: Cho trước một đoạn chương trình tính tổng của hai vector: for(i = 0; i < N; i++){ // (1) C[i] = A[i] + B[i]; } Thực hiện song song hoá đoạn chương trình này như thế nào? Tương tự như ví dụ nêu trên, giả sử ta có M tiến trình. Chúng ta có thể chia N phần tử thành M phần (thường ta giả thiết N chia hết cho M, nghĩa là N/M là số nguyên) và gán từng phần đó cho mỗi tiến trình. Chu trình trên có thể viết thành: for(j = id * N/M; j < (id+1)*N/M; j++){ C[j] = A[j] + B[j]; } Trong đó, id là số hiệu của tiến trình, chạy từ 0 đến M-1. Tiến trình thứ i xử lý N/M phần tử liên tiếp kể từ i*N/M+1, ví dụ hình 2-4 (a). Hoặc ta có thể cho phép các tiến trình truy cập xen kẽ vào các phần tử của mảng như sau: Tiến trình Pi bắt đầu từ phần tử thứ i, sau đó bỏ qua M phần tử để xử lý phần từ tiếp theo, nghĩa là nó truy cập đến i, i+M, i+2M, v.v., ví dụ hình 2-4 (b). Chu trình (1) khi đó được viết như sau: for(j = id; j < N; j+=M){ C[j] = A[j] + B[j]; } Ví dụ: Khi N = 15 và M = 5 thì việc gán các phần tử của vector cho các tiến trình sẽ được thực hiện theo cách trên như sau: P1 P2 P3 P4 P5 1 4 7 10 13 2 5 8 11 14 3 6 9 12 15 P1 P2 P3 P4 P5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (a) (b) Hình 2-4 Các cách phân chia chu trình của một mảng tuần tự II.2.1.2 Lập trình chia sẻ bộ nhớ dựa vào luồng Nhiều hệ điều hành hiện nay đều hỗ trợ đa luồng, ví dụ Window, OS/2, và UNIX. Trong hệ thống SMP, những luồng khác nhau có thể được hệ điều hành lập lịch tự động cho những CPU khác nhau. Một số ngôn ngữ lập trình, ví dụ Java cũng hỗ trợ lập trình đa luồng. Một tiến trình là bức tranh về sự hoạt động của một chương trình. Mỗi tiến trình được kết hợp với một hoặc nhiều luồng. Các luồng có thể xem như các tập con của một tiến trình [14]. Các luồng của một tiến trình có thể chia sẻ với nhau về không gian địa chỉ chương trình, các đoạn dữ liệu và môi trường xử lý, đồng thời cũng có vùng dữ liệu riêng để thao tác. Để dễ hiểu hơn về mô hình này, chúng ta có thể hình dung tiến trình như một xí nghiệp và các luồng như là các công nhân làm việc trong xí nghiệp đó. Các công nhân của xí nghiệp cùng chia sẻ nhau diện tích mặt bằng và các tài nguyên của cả xí nghiệp. Song, mỗi công nhân lại có chỗ làm việc được xem như là chỗ riêng của họ và những người khác không truy cập được. Việc tạo ra một công nhân (tuyển dụng lao động) dễ hơn nhiều việc tạo lập ra một xí nghiệp, vì một muốn có một xí nghiệp thì phải có ít nhất một công nhân nào đó theo qui định. Tương tự chúng ta có thể quan sát mối quan hệ giữa tiến trình và luồng về phương diện thông tin. Các công nhân trong xí nghiệp, theo mặc định, được quyền biết về mọi sự thay đổi, mọi việc xảy ra trong xí nghiệp. Nhưng nói chung, những biến động của xí nghiệp thì bình thường những xí nghiệp khác không biết được, trừ khi nó được thông báo trực tiếp cho những xí nghiệp đó. Các tiến trình và các luồng trong hệ thống song song cần phải được đồng bộ, song việc đồng bộ các luồng được thực hiện hiệu quả hơn đổi với các tiến trình. Đồng bộ các tiến trình đòi hỏi tốn thời gian hoạt động của hệ thống, trong khi đối với các luồng thì việc đồng bộ chủ yếu tập trung vào sự truy cập các biến chung của chương trình. Nhiều hệ điều hành hiện nay hỗ trợ đa luồng như: SUN Solaris, Window NT, OS/2, v.v. Bên trong những hệ điều hành này, những đặc tính hỗ trợ cho NSD khai thác được các luồng trong chương trình của mình thường khác nhau. Rất may hiện nay đã có một chuẩn, đó là Pthread của IEEE Portable Operating System Interface, POSIX. Thực hiện các luồng của Pthread Trong Pthread, chương trình chính cũng chính là một luồng. Một luồng có thể được tạo lập và kết thúc bằng những chương trình con sau: Pthread_t aThread; // Khai báo một luồng pthread_create(&aThread,&status,(void*)proc1,(void*)arg); pthread_join(athread, void *status); Hoạt động của các chương trình con trên được mô tả như trong hình 2-5. Một luồng mới được tạo ra và hoạt động ở proc1 và được truyền danh sách các đối số là &arg. Luồng sẽ bị huỷ bỏ sau khi kết thúc hoạt động và giải phóng các tài nguyên. Trang thái kết thúc công việc được trả lại trong pthrread_join(). Chương trình chính . . athread . proc1(&arg) pthread_create(&aThread,&status,(void*)proc1,(void*)arg); { . . . . pthread_join(athread, void *status); . . return(*status); . . } Hình 2-5 Hoạt động của luồng trong Pthread Có thể tạo lập và kết thúc một dãy các luồng. for(int i=0; i <n; i++) pthread_create(&aThread[i],&status,(void*)proc1,(void*)arg); . . . for(int i=0; i <n; i++) pthread_join(aThread[i],NULL); Vấn đề thực hiện loại trừ nhau giữa các luồng Vấn đề thực hiện loại trừ nhau giữa các luồng cũng tương tự như đối với các tiến trình. Chúng ta có bốn hàm nguyên thuỷ: pthread_mutex_init(mutex, NULL) pthread_mutex_lock(mutex) pthread_mutex_unlockinit(mutex) pthread_mutex_destroy(mutex) II.2.1.3 Xử lý luồng trong Java Java là ngôn ngữ lập trình hướng đối tượng hỗ trợ đa luồng, tiện lợi cho các ứng dụng web trên mạng. Trong mô hình hướng đối tượng, tiến trình và thủ tục là thứ yếu, mọi chức năng của chương trình được xác định thông qua các đối tượng. Khái niệm luồng trong Java giống như trong các hệ điều hành được tích hợp vào ngôn ngữ. Cũng giống như trên, các luồng được tạo lập, sau đó thực hiện một số công việc và kết thúc hoạt động khi không còn vai trò sử dụng. Tạo lập các luồng Trong Java có một lớp được xây dựng sẵn là Thread, làm lớp cơ sở để xây dựng những lớp kết thừa mới. class MyClass extends Thread{ . . . } Các tiến trình trong hệ thống bắt đầu thực hiện ở một địa chỉ đặc biệt được xác định bởi phương mức có tên là main() của một lớp chính. Tương tự khi một luồng của lớp MyClass được tạo ra thì nó gọi phương thức run() để thực hiện. Phương thức này được viết đè để thực thi những công việc yêu cầu trong mỗi luồng được tạo ra. class MyClass extends Thread{ // Một số thuộc tính public void run(){ // Các lệnh cần thực hiện theo luồng } // Một số phương thức khác được viết đè hay bổ sung } Khi chương trình chạy nó sẽ gọi một phương thức đặc biệt đã được khai báo trong Thread đó là start() để bắt đầu một luồng đã được tạo ra. Java không hỗ trợ đa kế thừa. Do vậy, nếu người lập trình muốn tạo ra một lớp kế thừa từ một lớp cơ sở và để thực hiện được theo luồng thì nó cũng đồng thời phải kế thừa từ lớp Thread. Điều này không thực hiện được. Java giải quyết hạn chế trên bằng cách xây dựng khái niệm Interface. Giao diện hỗ trợ thực hiện theo luồng là Runnable. Người lập trình thiết kế các lớp thực hiện theo luồng bằng cách cài đặt theo giao diện Runnable. class MyClass implemnets Runnable{ . . . } Các trạng thái của Thread Một luồng có thể ở một trong các trạng thái sau: new: khi một luồng mới được tạo ra với toán tử new(). runnable: khi chúng ta gọi phương thức start() để bắt đầu của một luồng. blocked: từ trạng thái runnable chuyển sang trạng thái “bị chặn” khi gọi một trong các phương thức: sleep(), suspend(), wait(), hay bị chặn lại ở Input/output. dead: luồng chuyển sang trạng thái “chết” khi nó kết thúc hoạt động bình thường, hoặc gặp phải ngoại lệ không thực hiện tiếp được. Hình 2-6 mô tả sơ đồ chuyển trạng của các luồng trong hệ thống. dead new blocked start stop sleep resume Đánh thức notify wait chặn lại bởi I/O Kết thúc I/O suspend runnable Hình 2-6 Sơ đồ trạng thái của Thread II.2.2 Tính toán phân tán: mô hình truyền thông điệp Với sự phát triển của các máy tính PC, ngày càng nhiều dữ liệu được lưu trữ và được xử lý ở những máy tính cá nhân. Những dữ liệu này cần phải được chia sẻ và các tính toán ở nhiều nơi này cũng cần phải được kết hợp lại để giải quyết hiệu quả hơn những bài toán đặt ra trong thực tế. Từ đó xuất hiện mô hình tính toán phân tán [14]. Tính toán phân tán là những tính toán được thực hiện trên cơ sở kết hợp tính toán và truyền thông của hai hay nhiều máy tính trên mạng. Mô hình tính toán phân tán có những ưu điểm: - Cho phép chia sẻ dữ liệu được lưu ở nhiều máy tính khác nhau. - Chia sẻ với nhau về một số chức năng chính của máy tính. - Độ tin cậy và khả năng dung thứ lỗi cao hơn. Trong trường hợp có một máy tính bị trục trặc thì những máy tính khác có thể thay thế để hoàn thành nhiệm vụ của hệ thống. - Tính kinh tế: thường đầu tư vào hệ phân tán sẽ thấp hơn đầu tư cho hệ tập trung. Tuy nhiên, hệ tính toán phân tán cũng đứng trước nhiều thách thức, những vấn đề liên quan đến việc quản trị hệ thống, định vị tài nguyên, vấn đề đảm bảo an toàn, an ninh thông tin, v.v. Xử lý trong các hệ thống phân tán không có bộ nhớ chia sẻ để trao đổi dữ liệu với nhau. Sự trao đổi được thực hiện bằng cách truyền thông điệp. Mô hình ở mức cao hơn, mô hình Client-Server cũng có thể sử dụng cơ chế này để cài đặt. II.2.2.1 Mô hình truyền thông điệp Giống như mô hình chia sẻ bộ nhớ, các đơn vị xử lý song song trong mô hình truyền thông điệp là các tiến trình. Tuy nhiên cũng có một số điểm khác nhau giữa hai mô hình này. Trong mô hình truyền thông điệp: Các tiến trình có thể thực hiện trên những bộ xử lý khác nhau và không truy cập được vào không gian địa chỉ chia sẻ. Vì lý do này, những chương trình trao đổi thông điệp với nhau còn được gọi là các chương trình phân tán. Chỉ có kênh truyền là có thể chia sẻ cho các tiến trình, thường đó là LAN hoặc mạng diện rộng. Việc truyền thông và đồng bộ hoá hoạt động của các tiến trình được thực hiện thông qua hai phương thức send() và receive(). Tất cả các biến là cục bộ của các tiến trình. Vì thế, những vấn đề về xung đột dữ liệu (cần phải khoá dữ liệu khi một tiến trình truy cập), hay tranh chấp thông tin (bài toán loại trừ nhau) không xuất hiện trong mô hình tính toán phân tán. Việc đồng bộ hoá các tiến trình của một chương trình song song được thực hiện theo có chế truyền thông điệp. Khi một tiến trình muốn gửi một thông điệp thì nó phải chờ cho đến khi tiến trình nhận sẵn sàng nhận thông điệp đó và ngược lại, cũng tương tự. Ở đây không có các buffer để tạm lưu giữ các thông điệp cần trao đổi giữa các tiến trình. II.2.2.2 Kênh truyền thông Những hệ thống khác nhau sẽ cung cấp những kênh truyền ở những mức trừu tượng khác nhau. Hầu hết các hệ thống đều đảm bảo rằng các kênh truyền thông không có các lỗi thông thường. Nghĩa là, tất cả các thông điệp được gửi đi và sẽ đến được đích mà không bị sai lạc. Kênh truyền thông có thể được xem như là hàng đợi, và thông điệp sẽ được gửi đến đích theo thứ tự nó được gửi đi. Kênh truyền thông cũng có thể được xem như là hộp thư (mailbox) của một tiến trình nhận/gửi thông điệp. Ở mức trừu tượng này sẽ loại bỏ được ràng buộc về thứ tự đến của các thông điệp. Tiến trình có thể chọn các thông điệp từ hộp thư theo một số tiêu chí nào đó. Một số hệ thống đưa ra khái niệm thông điệp có cấu trúc. Các kênh được định nghĩa theo các kiểu của thông điệp và một số kênh đặc biệt chỉ truyền tải được một số kiểu nhất định. Một tiến trình muốn gia nhập vào một kênh có kiểu xác định thì phải tự gắn bó với kênh đó. Một kênh cũng có thể phục vụ cho một nhóm các tiến trình trong chương trình song song. II.2.2.3 Truyền thông đồng bộ 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. Hệ thống truyền thông điệp đồng bộ hoàn toàn giống như hệ điện thoại, kênh truyền bị chặn lại trong quá trình đàm thoại. Hệ truyền dị bộ lại giống nhiều hơn với hệ thống bưu chính, người nhận phải chờ cho đến khi có thư được gửi đến. Chúng ta hãy phân tích thêm để hiểu rõ sự phát triển của hai mô hình trên. Một mặt, cơ chế truyền thông điệp đồng bộ làm cho nhiều vấn đề trong đồng bộ hoá và việc cấp phát bộ nhớ động trở lên đơn giản hơn. Mặt khác, việc gắn chặt các tiến trình với thời gian phân phát thông điệp cũng được xem như là điều kiện ràng buộc bổ sung đòi hỏi trong thiết kế và thực thi chương trình. Việc bắt tiến trình gửi phải chờ dẫn đến việc làm giảm tính đồng thời của hệ thống. Ngoài ra, để cài đặt hiệu quả các hệ thống truyền tin đồng bộ, đòi hỏi phải có những phần cứng đặc biệt để đảm bảo rằng sự truyền tin cực nhanh và sự trao đổi dữ liệu không ảnh hưởng tới sự tính toán. Mà các mạng truyền thông nhanh có nhiều nút trao đổi với nhau là rất đắt tiền. Vì những lý do trên, nên hệ truyền thông điệp dị bộ làm việc trên LAN sẽ ngày một phổ cập hơn. Các chương trình truyền thông điệp hiển thị nhiều mẫu giao diện khác nhau. Sau đây là một số mẫu chung nhất: Dòng dữ liệu một chiều từ các bộ lọc trên mạng Các yêu cầu và trả lời qua lại giữa khách (Client) và chủ (Server) Phát tin hay quảng bá tin (broadcast) cho các tiến trình trong đồ thị đầy đủ Gửi các dấu hiệu (token) theo các cạnh của đồ thị, v.v. II.2.2.4 Truyền thông dị bộ Truyền thông điệp dị bộ: Trong mô hình này, một kênh truyền được giả thiết là có khả năng tiếp nhận không bị giới hạn. Khả năng không giới hạn được cài đặt trong thực tế bằng cách sử dụng bộ đệm (buffer) để tiếp nhận các thông điệp gửi đến cho mỗi tiến trình. Do vậy, tiến trình gửi sẽ không phải chờ để tiến trình nhận sẵn sàng nhận 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, tiến trình nhận thì phải chờ cho đến khi có được thông điệp của một tiến trình khác gửi cho nó. Từ đó dẫn đến một số điều kiện: - Khi tiến trình A gửi đi một thông điệp cho tiến trình B thì sau đó nó cần phải được biết xem B có nhận được hay không, nghĩa là A phải chờ để nhận được câu trả lời khẳng định của B. - Việc phân phát thông điệp cũng không thể đảm bảo rằng không bị thất bại. Nếu A gửi đi một thông điệp cho B và không nhận được câu trả lời thì nó cũng không có cách nào biết được là thông điệp đó đã được gửi đến đích chưa hoặc tiến trình B bị huỷ bỏ trong quá trình xử lý hoặc ngay cả khi câu trả lời của B không đến được A. - Tất cả các thông điệp đều phải đưa vào bộ đệm (hàng đợi), nhưng trong thực tế không gian hàng đợi là hữu hạn. Khi có quá nhiều thông điệp được gửi đi thì hoặc chương trình sẽ không thực hiện được hoặc phương thức gửi bị chặn lại. Điều này vi phạm ngữ nghĩa của mô hình truyền thông điệp dị bộ. II.2.2.5 Mô hình lập trình II.2.2.5.1 Phát sinh tiến trình Một chức năng quan trọng trong lập trình song song là tạo lập ra nhiều tiến trình để thực hiện những công việc con của một chương trình song song. Nói chung, một chương trình bắt đầu thực hiện như một tiến trình và sau đó phát sinh ra nhiều tiến trình con để khai thác khả năng song song của bài toán. Có hai cách tạo lập tiến trình: tạo lập tĩnh và tạo lập động. Tạo lập tiến trình tĩnh: tất cả các tiến trình được xác định trước khi thực hiện và hệ thống có một số tiến trình xác định trước. Trong hệ thống loại này thường có một tiến trình điều khiển còn được gọi là tiến trình “chủ” (master), những tiến trình khác được gọi là tiến trình tớ (slave). Đây là mô hình SPMD (simple-program, multipe-data). Sau khi chương trình nguồn được viết với các lệnh phân chia công việc cho từng tiến trình, nó sẽ được dịch sang mã thực thi được cho những tiến trình đó. Quá trình này được mô tả như hình 2-7 Hình 2-7 Dịch đơn chương trình, đa thao tác dữ liệu Tạo lập tiến trình động: các tiến trình được tạo lập sau đó chúng có thể thực hiện trong các tiến trình khác. Các tiến trình có thể được tạo lập mới hoặc bị huỷ bỏ có điều kiện và một số tiến trình có thể thay đổi trong quá trình thực hiện. Mô hình cho phép thực hiện tạo lập động là MPMD (Muliple-program muliple-data), trong đó những chương trình khác nhau có thể thực hiện trên những bộ xử lý khác nhau. Tất cả các hệ thư viện truyền thông điệp đều có hàm phát sinh các tiến trình con với cấu trúc tổng quát như sau: spawn(prog: string, host: int, count: int, id[]:int) prog: tên chương trình được nạp xuống như là chương trình con. Kết quả khi thực hiện thành công sẽ trả lại mảng id là địa chỉ của các tiến trình được tạo ra để truyền thông điệp. Mảng id có chỉ số từ 1, tiến trình đầu tiên của chương trình song song có chỉ số là 0. host: tên của tiến trình mà ở đó các tiến trình con được tạo ra. count: số các đại diện của chương trình được tạo ra. II.2.2.5.2 Hàm send và receive Việc gửi một thông điệp được thực hiện bằng cách xác định địa chỉ của một hay tất cả các tiến trình nhận theo một kênh truyền. Lựa chọn thông điệp để nhận có thể dựa vào tiến trình gửi, kênh truyền, hay thẻ bài (tag) của thông điệp, v.v. Lời gọi send() là không bị chặn, không phải chờ câu trả lời của nơi nhận. Nhưng lời gọi receive() sẽ bị chặn lại, chỉ có tiếp tục khi có một thông điệp tương ứng đã được gửi đi. Gửi thông điệp cho một tiến trình id: send(id: int, message: message_type); send(id: int, tag: int, message: message_type); Gửi thông điệp tới một kênh: một thông điệp có thể gửi cho tất cả các tiến trình trên cùng một kênh mych. send(mych: channel, message: message_type); Nhận thông điệp từ một kênh: để nhận một thông điệp đang chờ đợi từ một kênh thì có thể sử dụng lời gọi hàm sau: receive(mych: channel, message: message_type); Nếu thông điệp được ghi thẻ thì tiến trình nhận có thể phân loại thông điệp trong hộp nhận và chọn thông điệp theo thẻ xác định. receive(id: int, tag: int, msg: message_type); Ví dụ: trong C chúng ta có thể gọi send(&x, destination_id); trong tiến trình nguồn và gọi receive(&y, source_id); Ở tiến trình đích để gửi giá trị dữ liệu x từ tiến trình nguồn (source-id) sang biến y cho tiến trình đích. Tất nhiên là x, y phải có cùng kiểu (kiểu tương thích với nhau) và cùng kích cỡ. Hình 2-8 Sự trao đổi thông điệp giữa hai tiến trình Như ở trên đã phân tích, việc gửi và nhận thông điệp có thể thực hiện một cách đồng bộ hoặc dị bộ. Trong trao đổi thông điệp đồng bộ, tiến trình gửi trước tiên phải gửi đi yêu cầu gửi và nó phải chờ đến khi nhận được câu trả lời sẵn sàng nhận của tiến trình đích thì mới tiến hành gửi. Ngược lại, khi có một tiến trình muốn nhận một thông điệp thì nó phải chờ để có một tiến trình khác gửi cho nó thì sau đó mới tiếp tục công việc. Trong mô hình dị bộ thì các thông điệp được gửi đi và được đưa vào bộ đệm để sau đó gửi dần tới cho các tiến trình đích. Để linh hoạt cho việc trao đổi, người ta thường gán cho mỗi thông điệp một thẻ bài (tag) và nó được sử dụng để phân biệt các thông điệp trao quá trình trao đổi. Ví dụ: để gửi thông điệp x từ tiến trình số 1 tới tiến trình số 2 và gán cho y, ta viết: send(&x, 2, 5); ở tiến trình số 1 và ở tiến trình số 2 gọi receive(&y, 1, 5); II.2.2.5.3 Truyền thông nhóm Nhiều chương trình phân tán cần phát tán và nhận dữ liệu từ nhiều tiến trình phân tán, nghĩa là cần trao đổi với từng nhóm trong chương trình song song. Để thực hiện truyền thông theo nhóm, chúng ta có thể sử dụng: Broacast(): phát tán cùng một thông điệp cho tất cả các tiến trình trên kênh mych. Broadcast(mych:channel,tag:int, msg:message_type); Hoạt động của lệnh Broadcast() được mô tả như hình 2-9. Các tiến trình tham gia trao đổi trong phát tán dữ liệu phải được xác định. Trong hình 2-9, tiến trình số 0 được xem như tiến trình gốc chứa dữ liệu ở mảng buf để phát tán cho những tiến trình khác. Theo qui ước của mô hình SPMD, mọi tiến trình đều thực hiện cùng một chương trình nên trong hình 2-9 tất cả các tiến trình đều gọi hàm Broadcast(). Hành động phát tán dữ liệu sẽ không thực hiện được cho đến khi tất cả các tiến trình đều thực hiện lời gọi Broadcast(). Hình 2-9 Hoạt động phát tán dữ liệu Reduce(): thực hiện phép toán số học/logic trong nhóm các tiến trình và gửi kết quả tới tiến trình gốc. Reduce(mych:channel,op:op_type, res:Result_type,root: int,tag:int, msg:message_type); Trong đó, Op_type = {MAX, MIN, SUM, PROD, LAND, LOR, BAND, BOR, LXOR, BXOR}} Ví dụ: hình 2-10 mô tả hàm Reduce() tập hợp các giá trị từ n tiến trình và thực hiện phép cộng (SUM) ở tiến trình gốc. Hình 2-10 Hoạt động của hàm Reduce() Scatter(): phân tán công việc cho các tiến trình. Dữ liệu ở mảng buff được chia nhỏ thành n đoạn và phân tán cho n tiến trình trên kênh mych. Scatter(mych:channel, n:int, Buff[N]:DataType); Hàm này được sử dụng để gửi phần tử thứ i của một mảng dữ liệu tới cho tiến trình thứ i. Hình 2-11 mô tả hoạt động của Scatter(). Tương tự trường hợp của Broadcast(), ở đây nhóm các tiến trình kể cả tiến trình gốc phải được xác định. Hình 2-11 Hoạt động của hàm Scatter() Gather(): ngược lại so với hàm Scatter(), dữ liệu được gửi đi theo hàm Scatter() được xử lý bởi những tiến trình nhận được và sau đó được tập hợp lại cho một tiến trình. Gather(mych:channel,Buff[N]:DataType,root:int,sendbuff[N]:DataType); Ngược lại hàm Scatter(), dữ liệu từ tiến trình thứ i được nhận về ở tiến trình gốc và được đưa vào phần tử thứ i của mảng buf, được mô tả như hình 2-12. Hình 2-12 Hoạt động của hàm Gather() Barrier(): thực hiện việc đồng bộ hoá những tiến trình cùng gia nhập một kênh truyền. Mỗi tiến trình phải chờ cho đến khi tất cả các tiến trình khác trên kênh đạt đến điểm đồng bộ hoá bằng lời gọi Barrier() trong chương trình. Barrier(mych:channel); II.2.3 Lập trình trên cụm máy tính. Mô hình truyền thông điệp nêu trên được sử dụng rất hiệu quả để lập trình song song theo cụm máy tính. Một môi trường cho hệ thống nhiều máy tính, nhất là các cụm máy tính đã được phát triển và được sử dụng phổ biến hiện nay là PVM (Parallel Virtual Machine). PVM cung cấp môi trường phần mềm để truyền thông điệp cho các hệ máy tính thuần nhất và cả không thuần nhất. PVM có một tập hợp các hàm thư viện được viết bằng C hoặc Fortran. Mỗi chương trình được viết bằng C, được biên dịch để chạy trên những kiểu máy tính xác định trên mạng. Nếu mạng gồm những máy tính cùng kiểu thì chương trình chỉ cần dịch một lần. Mỗi nút trong mạng (LAN) phải truy cập đến hệ thống tệp chứa các chương trình đã được dịch để thực hiện. Tập các máy tính được sử dụng trong mạng phải được định nghĩa theo các mức ưu tiên để chạy các chương trình. Điều này được thực hiện trên tập máy ảo song song PVM [5]. Cách thực hiện tốt nhất là tạo ra một danh sách tên gọi của các máy tính và đặt ở hostfile. Tệp này được PVM đọc để thực hiện các chương trình. Mỗi máy tính có thể chạy một hay nhiều tiến trình (chương trình ứng dụng). Các chương trình ứng dụng chạy trong các máy tính thông qua các tiến trình của PVM để trao đổi với nhau trên mạng như hình 2-13. Các tiến trình PVM yêu cầu đủ thông tin để chọn lựa đường truyền dữ liệu. PVM Chương trình ứng dụng PVM Chương trình ứng dụng PVM Chương trình ứng dụng Máy tính trạm Máy tính trạm Máy tính trạm Trao đổi thông điệp trên mạng Hình 2-13 Sự trao đổi thông điệp của các máy tính trong hệ PVM Các chương trình của PVM thường được tổ chức theo mô hình chủ-tớ (master-slave), trong đó tiến trình chủ được thực hiện trước tiên, sau đó các tiến trình tớ sẽ được tạo ra trong tiến trình chủ đó. Hàm phát sinh tiến trình mới trong PVM là: pvm_spawn(). Một tiến trình muốn tham gia vào hệ PVM thì nó phải ghi danh bằng cách gọi hàm pvm_mytid(). Các tiến trình muốn được huỷ bỏ thì gọi hàm pvm_exit(). Các chương trình trao đổi thông điệp với nhau thông qua các hàm pvm_send() và pvm_recv(). Tất cả các thủ tục gửi đều không bị chặn (dị bộ) còn các thủ tục nhận thì hoặc bị chặn (được đồng bộ) hoặc không bị chặn. Các thao tác chính của việc gửi và nhận dữ liệu được thực hiện ở các bộ đệm buffer. Nếu dữ liệu được gửi đi là một danh sách các mục có cùng kiểu thì trong PVM sử dụng pvm_psend() và pvm_precv(). Hình 2-14 mô tả hoạt động của hai tiến trình trao đổi một mảng dữ liệu với nhau. . . . pvm_precv(); . . . Tiến trình 2 send buffer . . . pvm_send(); . . . Tiến trình 1 Chờ thông điệp Tiếp tục xử lý Hình 2-14 Gọi hàm pvm_psend() và pvm_precv() Khi dữ liệu chuyển đi là phức tạp, gồm nhiều kiểu khác nhau thì chúng phải được đóng gói lại (pack) để gửi đến buffer, sau đó tiến trình nhận lại mở gói (unpack) để nhận về dữ liệu tương ứng. Đó là các hàm: pvm_pkint() và pvm_upkint() cho dữ liệu kiểu int pvm_pkfloat() và pvm_upkfloat() cho dữ liệu kiểu float pvm_pkstr() và pvm_upkstr() cho dữ liệu kiểu string, v.v. Lưu ý: thứ tự mở gói để lấy dữ liệu ra phải đúng theo thứ tự mà chúng được đóng gói ở tiến trình gửi. Bộ đệm buffer để gửi dữ liệu là mặc định và nó phải được khởi tạo ở tiến trình gửi bằng lệnh pvm_inítend(). Hình 2-14 mô tả nguyên lý hoạt động nêu trên. Tương tự, các lệnh khác về trao đổi thông điệp theo nhóm như: pvm_bcast(), pvm_scatter(), pvm_gather(), pvm_reduce(), v.v. II.2.4 Đánh giá các chương trình song song Để sử dụng hiệu quả các thuật toán song song, chúng ta cần phải biết cách đánh giá nó. Thời gian thực hiện song song Để đánh giá được độ phức tạp tính toán của các thuật toán song song, ngoài số bước tính toán chúng ta còn cần đánh giá thời gian truyền thông của các tiến trình. Trong một hệ thống truyền thông điệp, thời gian truyền thông điệp cũng phải được xem trong thời gian thực hiện của thuật toán. Thời gian thực hiện song song, ký hiệu là tp gồm hai phần tcomp và tcomm tp = tcomp + tcomm Trong đó, tcomp là thời gian tính toán và tcomm - thời gian truyền thông dữ liệu. Thời gian tính toán tcomp được xác định giống như thuật toán tuần tự. Khi có nhiều tiến trình tiến trình thực hiện đồng thời thì tính thời gian thực hiện của tiến trình phức tạp nhất (thực hiện lâu nhất). Trong phân tích độ phức tạp tính toán, chúng ta luôn giả thiết rằng, tất cả các bộ xử lý là giống nhau và thao tác cùng một tốc độ như nhau. Đối với những cụm máy tính không thuần nhất thì điều này không đảm bảo do vậy, việc đánh giá thời tính toán của những hệ như thế là rất phức tạp. Thời gian truyền thông tcomm lại phụ thuộc vào kích cỡ của các thông điệp, vào cấu hình kết nối mạng đường truyền và cả cách thức truyền tải thông điệp, v.v. Công thức ước lượng thời gian truyền thông được xác định như sau: tcomm = tstartup + n * tdata Trong đó, + tstartup là thời gian cần thiết để gửi những thông điệp không phải là dữ liệu. Nó bao gồm cả thời gian để đóng gói thông điệp ở nơi gửi và thời gian mở gói ở nơi nhận. Để đơn giản chúng ta giả thiết thời gian này là hằng số. + tdata là thời gian cần thiết để chuyển một từ dữ liệu (một mục dữ liệu) từ nơi gửi tới nơi nhận, được giả thiết là hàng số và n là số từ dữ liệu được trao đổi trong hệ thống. Ví dụ: Giả sử cần thực hiện cộng n số trên hai máy tính, trong đó mỗi máy cộng n/2 số với nhau và tất cả các số đó được lưu ở máy tính thứ nhất. Kết quả của máy tính thứ hai khi được tính xong sẽ được chuyển về máy tính thứ nhất để nó công hai kết quả bộ phận với nhau. Bài toán này được phát biểu như sau: Máy tính thứ nhất gửi n/2 số cho máy tính thứ hai Cả hai máy tính cộng n/2 số một cách đồng thời Máy tính thứ hai chuyển kết quả tính được về máy tính thứ nhất Máy tính thứ nhất cộng hai kết quả để có kết quả cuối cùng. Thời gian tính toán (ở bước 2 và 4): tcomp = n/2 + 1 Thời gian truyền thông (ở bước 1 và 3): tcomm = (tstartup + n/2 * tdata) + (tstartup + tdata) = 2*tstartup + (n/2 + 1) * tdata Độ phức tạp tính toán là O(n) và độ phức tạp truyền thông cũng là O(n), do vậy độ phức tạp nói chung của thuật toán trên cũng là O(n). Tóm lại, để giải những bài toán đặt ra một cách hiệu quả trên những máy tính mà chúng ta có, vấn đề chính làm thế nào để xây dựng được những thuật toán song song. Cách làm khá thông dụng là biến đổi các thuật toán tuần tự về song song, hay chuyển từ một dạng song song về dạng song song phù hợp hơn sao vẫn bảo toàn được tính tương đương trong tính toán. Do đó, khi biến đổi chúng ta cần trả lời hai câu hỏi: Kiến trúc nào phù hợp cho bài toán? Những bài toán loại nào sẽ xử lý hiệu quả trong kiến trúc song song cho trước? Và dựa vào những nguyên lý thiết kế chính: nguyên lý lập lịch, nguyên lý hình ống, nguyên lý chia để trị, nguyên lý đồ thị phụ thuộc dữ liệu, nguyên lý điều kiện tranh đua để xây dựng một số thuật toán song song thường dùng như các thuật toán sắp xếp, tìm kiếm, các thuật toán toán tính toán trên ma trận, hay nhiều thuật toán tính toán khác Để đánh giá được tính hiệu quả của thuật toán song song thường phải dựa vào độ phức tạp của thuật toán. Độ phức tạp tính toán của thuật toán song song không chỉ phụ thuộc vào kích cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ xử lý được phép sử dụng trong hệ thống. Để áp dụng cơ chế xử lý song song, chúng ta có thể sử dụng các hệ điều hành hiện nay ví dụ như Window, OS/2, và UNIX và một số ngôn ngữ lập trình, chẳng hạn như C, Java,.. và một số mô hình lập trình song song. Một trong các mô hình lập trình song song đang được sử dụng phổ biến hiện nay là 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 kênh truyền thông. Kênh truyền thông 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: send() và receive(). Để bắt đầu trao đổi được với nhau thì một tiến trình phải gửi đi (send) 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 (receive) thông điệp đó. 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 nêu trên được sử dụng rất hiệu quả để lập trình song song theo cụm máy tính. Một môi trường cho hệ thống nhiều máy tính, nhất là các cụm máy tính đã được phát triển và được sử dụng phổ biến hiện nay là PVM . PVM cung cấp môi trường phần mềm để truyền thông điệp cho các hệ máy tính thuần nhất và cả không thuần nhất. CHƯƠNG III GIẢI THUẬT SONG SONG CHO MỘT SỐ BÀI TOÁN PHI TUYẾN Trong phần này chúng tôi trình bày phương pháp giải một số bài toán phi tuyến. Nhiều bài toán phi tuyến khá phức tạp thì ít khi tìm được nghiệm đúng mà chỉ là xấp xĩ. Khi giải hệ phương trình phi tuyến bằng phương pháp tuyến tính hoá, ta đều phải giải hệ phương trình đại số tuyến tính. Đầu tiên, chúng tôi khảo sát bài toán giải hệ phương trình tuyến tính. III.1 Bài toán giải hệ phương trình tuyến tính Giả sử có hệ phương trình tuyến tính được viết dưới dạng ma trận Ax = b Trong đó, A = (ai,j) là ma trận hằng số cấp n´n, x là vector nghiệm và b là vector hằng số. Một trong các cách giải hệ phương trình tuyến tính là sử dụng phương pháp khử Gaussian để đưa ma trận A về ma trận tam giác trên. Phương pháp Gaussian dựa vào đặc tính của các phương trình tuyến tính là bất kỳ một hàng nào cũng có thể thay thế bằng chính nó được cộng thêm với hàng khác được nhân với một hằng số. Thuật toán Guassian bắt đầu từ hàng thứ nhất và tìm cách khử dần cho đến hàng cuối cùng chỉ còn lại một phần tử. Ở hàng thứ i, những hàng thứ j đứng dưới i ( j > i) được thay bằng: hàng j + (hàng i)*(-aj,i/ai,i), nếu ai,i khác 0. Kết quả là tất cả các phần tử trong cột thứ i đứng dưới hàng i đều trở thành 0. aj,i = aj,i + ai,i (-aj,i / ai,i) = 0 Tất nhiên nếu ai,i = 0 thì phải tìm cách thay đổi thứ tự các hàng trong hệ phương trình tuyến tính sao cho tất cả các phần tử trên đường chéo chính của ma trận A là khác 0. Lưu ý khi ma trận A không suy biến thì luôn chuyển được về dạng sao cho tất cả các phần tử trên đường chéo chính aii ¹ 0. Quá trình này được mô tả như trong hình 3-1. Hàng i Hàng j Hàng cột Bước tiếp theo aj,i Cột i Đã khử về 0 Cần khử về 0 Hình 3-1 Phương pháp khử Gaussian Thuật toán Gaussian (tuần tự) được viết như sau: for(i = 0; i < n-1; i++)/* Trừ hàng đầu tiên */ for(j = i+1; j < n; j++){ m = a[j][i]/a[i][i]; for(k = i; k < n; k++) a[j][k] = a[j][k] – a[i][k]*m; b[j] = b[j] – b[i] * m; } Độ phức tạp tính toán của thuật toán Gaussian là O(n3). Cài đặt thuật toán Gaussian song song. Từ thuật toán tuần tự nêu trên chúng ta thấy chu trình trong cùng làm thay đổi hàng j và thực hiện những phép toán độc lập với nhau. Do vậy, có thể chia nhỏ bài toán bằng cách cho mỗi bộ xử lý giữ một hàng thực hiện trên hàng đó. Thuật toán song song thực hiện như sau: Bộ xử lý P0 giữ hàng 0 và phát tán (broadcast) tất cả các phần tử của hàng đầu tiên cho n-1 bộ xử lý còn lại. Các bộ xử lý thực hiện các phép nhân với những hệ số tương ứng và thay đổi trên hàng của mình. Các phần tử ở hàng thứ i được phân tán bởi Pi là: a[i][i+1], a[i][i+2], …, a[i][n-1] và b[i], tổng cộng là n-i+1 phần tử. Đánh giá thuật toán Giá truyền thông: Giả sử các thông điệp được phát tán trong từng nhịp. Thông điệp được phát tán lần thứ i chứa n-i+1 phần tử, suy ra công thức tính thời gian truyền thông của hệ thống sẽ là: tcomm = (tstartup + (n-i+1)tdata) = ((n-1)tstartup + ((n+1)(n+2)/2 –3)tdata) Vậy độ phức tạp truyền thông là O(n2). Độ phức tạp tính toán: Các bộ xử lý Pj bên dưới Pi sẽ nhận được dữ liệu từ Pi chuyển tới và tính toán trên những n-j+2 số của hàng đó. Chúng thực hiện n-j+2 phép nhân và n-j+2 phép cộng. Do đó, số các phép toán cơ sở sẽ là: tcomp = (n – j + 2) = ((n+3)(n+2)/2 –3) = O(n2). Sau khi đã chuyển ma trận hệ số về dạng ma trận tam giác trên, chúng ta có thể xây dựng thuật toán song song để giải hệ phương trình thu được theo phương pháp thế quay lui. Ví dụ, áp dụng thuật toán khử Gaussian đưa về hệ phương trình dạng: 2x1 - 2x2 - 2x3 + 1x4 = 5 2x2 - 1x3 + 3x4 = 4 1x3 - 3x4 = 0 4x4 = 4 Giải phương trình cuối cùng thu được x4 = 1 sau đó thế vào phương trình thứ ba (ở trên) ta tính được x3 = 3. Bằng cách đó, chúng ta thế những biến đã được xác định quay lui lên phía trên để tính được x2 = 2, x1 = 7. Giả sử A là ma trận tam giác trên và b là vector hằng số. Thuật toán giải hệ phương trình tuyến tính Ax = b được xây dựng như sau: spawn(Pi), 0 < i £ p /* tạo ra p tiến trình *? for(i = n; i > 1; i--){ x[i] = b[i]/a[i,i]; forall Pj where 1 £ j £ p do { for(k = j; k <i; k += p){ b[k] = b[k] – x[i] * a[k][i]; a[k][i] = 0; } } } III.2 Bài toán phi tuyến III.2.1.