Mở đầu Nhiều vấn đề trong các lĩnh vực khai phá dữ liệu, chuẩn đoán bệnh bằng hình ảnh, tìm kiếm và bào chế dược phẩm đặc dụng, công nghệ đa phương tiện, phát triển đồ họa và thực tại ảo, dự báo thời tiết, cảnh báo động đất, sóng thần, vv., đòi hỏi phải thực hiện một khối lượng tính toán khổng lồ với lượng dữ liệu rất lớn trong thời hạn quy định. Những bài toán này không thể giải được trên những máy tính đơn lẻ, với bộ nhớ hạn chế. Ví dụ như khi giải bài toán giá trị biên-ban đầu cho phương trình thủy-nhiệt- động học để dự báo trạng thái của khí quyển cho ngày hôm sau, nhưng do năng lực máy tính hạn chế, nên tính toán phải cần 10 ngày thì kết quả thu được sẽ mất hết ý nghĩa. Để giải quyết các bài toán có khối lượng tính toán rất lớn, người ta thường sử dụng những thuật toán song song trên các máy tính hiệu năng cao.
Tính toán song song liên quan đến các vấn đề sau: 1) hệ thống máy tính song song, 2) các công cụ phần mềm lập trình song song, 3) các thuật toán song song. Sau đây chúng ta sẽ đề cập đến ba vấn đề nêu trên. Tính toán song song [13] là hình thức tính toán trong đó nhiều phép tính được thực hiện đồng thời; nó hoạt động trên nguyên tắc là những vấn đề lớn đều có thể chia thành nhiều phần nhỏ hơn, sau đó được giải quyết tương tranh. Tính toán song song có ưu điểm tiết kiệm thời gian và bộ nhớ, do đó nó có thể giải quyết thành công các vấn đề rất phức tạp trong thực tế.
Máy tính song song sử dụng đồng thời nhiều bộ xử lý để giải quyết những thành phần khác nhau của một bài toán. Như vậy thời gian giải bài toán sẽ được 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Theo lý thuyết, trong trường hợp lý tưởng nếu có n bộ xử lý thì thời gian giải quyết vấn đề sẽ giảm đi n lần so với dùng một bộ xử lý. Tuy nhiên, thời gian giải quyết trong thực tế sẽ lớn hơn thời gian lý tưởng tính trên lý thuyết do nhiều nguyên nhân.
Thứ nhất là ngoài thời gian xử lý bài toán thì còn thời gian đồng bộ và giao tiếp giữa các công việc xử lý song song. Thứ hai là không phải bài toán nào cũng có thể chia thành n phần nhỏ bằng nhau để giao cho các bộ xử lý. Nguyên nhân thứ hai phải khắc phục bằng cách xây dựng các giải thuật khả song song hợp lý. Đối với nguyên nhân thứ nhất thì ngoài việc chú ý đến giải thuật giải quyết vấn đề, ta nên chú ý đến khả năng truyền dữ liệu trong hệ thống máy tính.
Như vậy hiệu quả của việc xây dựng một ứng dụng song song không chỉ phụ thuộc vào giải thuật giải quyết mà còn phụ thuộc nhiều vào hệ thống máy tính. Các hệ thống máy tính song song lần lượt ra đời với nhiều kiến trúc và kỹ thuật xây dựng khác nhau. Hiện tại, các máy tính song song có thể tạm chia làm các loại sau [67]: i. Máy tính song song dùng chung bộ nhớ với bộ xử lý đa lõi (Multicores computers) hoặc với các bộ xử lý đối xứng.
Hệ thống máy tính song song quy mô lớn với bộ nhớ phân tán (Massively parallel systems) dựa trên hệ thống mạng tốc độ cao. Ví dụ như Intel- Paragon, IBM 6000/SP, Cray T3E, vv. Các trạm làm việc liên kết qua đường mạng (Network of workstation). Phần quan trọng quyết định xu hướng của tính toán hiệu năng cao liên quan đến vấn đề xây dựng các siêu máy tính và các phần mềm chạy trên nó.
Ở vào thời điểm năm 1980, một siêu máy tính phải là máy tính có khả năng tính toán trên 100 Mflops (Mflops: triệu phép toán thực trên giây) nhưng ngày nay một máy tính cá nhân cũng có khả năng tính toán mạnh hơn thế. Vấn đề rất được quan tâm là làm sao xây dựng được các siêu máy tính có năng lực tính toán mạnh nhưng giá thành lại thấp. Phương án liên kết các máy tính cá nhân qua đường mạng theo dạng (iii) đã và đang là giải pháp được lựa chọn hiện nay, vì có tỉ lệ giữa giá cả và độ hiệu quả tốt hơn so với các máy tính đa bộ xử lý. Tuy nhiên, trong các ứng dụng song song, thời gian truyền dữ liệu cũng được quan tâm như thời gian tính toán.
Vì vậy, các hệ thống bó máy tính được xây dựng dựa trên việc liên kết các đơn vị tính toán (computing units) qua 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com bộ chuyển mạch tốc độ cao, nhằm bảo đảm tốc độ truyền dữ liệu giữa các nút tính toán mà vẫn không tăng giá thành toàn hệ thống. Vì lý do nói trên, hướng nghiên cứu xây dựng bó máy tính và mô hình tính toán cụm được phát triển mạnh từ hơn thập kỷ qua. Một vấn đề quan trọng khi thiết lập hệ thống này là xây dựng phần mềm quản lý tài nguyên, phân bổ công việc, quản lý công việc, giám sát, vv. Các phần mềm hệ thống này giúp chúng ta sử dụng dễ dàng và hiệu quả tài nguyên trong hệ thống.
Gần đây, nhu cầu giải quyết các bài toán thật lớn trong thực tế dẫn đến việc liên kết các trung tâm máy tính mạnh lại với nhau. Sự hợp tác trong công việc, cùng chia sẻ tài nguyên giữa các cơ quan cũng thúc đẩy ra đời một mô hình hệ thống máy tính mạnh mới là lưới tính toán (Grid Computing) và hướng tính toán mạng lưới. Lưới tính toán [14] là một hệ thống cho phép chia sẻ, lựa chọn và kết hợp các tài nguyên độc lập, rải rác ở nhiều nơi khác nhau để thực thi chương trình tùy thuộc vào tính sẵn sàng, khả năng đáp ứng, độ hiệu quả, giá cả và các yêu cầu về dịch vụ của người sử dụng. Trong thời gian gần đây, tính toán đa năng trên các đơn vị xử lý đồ họa (GPU) là một hướng nghiên cứu mạnh trong kỹ thuật máy tính.
GPUs là các bộ xử lý đồng bộ được tối ưu hóa mạnh cho việc xử lý đồ họa máy tính. Tùy thuộc vào các kiến trúc máy tính song song chúng ta có các mô hình lập trình song song phù hợp. Một mô hình lập trình song song sử dụng một tập hợp các kỹ thuật phần mềm để thể hiện các giải thuật song song và đưa ứng dụng vào thực hiện trong hệ thống song song. Mô hình bao gồm các ứng dụng, ngôn ngữ, bộ biên dịch, thư viện.
Trong thực tế, chưa có một máy tính song song nào cũng như cách phân chia công việc cho các bộ xử lý nào có thể áp dụng có hiệu quả cho mọi bài toán. Do đó, người lập trình phải lựa chọn chính xác mô hình lập trình song song hoặc pha trộn các mô hình đó để phát triển các ứng dụng song song trên một hệ thống riêng biệt. Hiện nay có rất nhiều mô hình lập trình song song: mô hình đa luồng (Threads), mô hình truyền thông điệp (Message Passing), mô hình song song dữ liệu (Data Parallel) và mô hình lai (Hybird) được phát triển phù hợp với các kiến trúc của máy tính song song. Đối với các kiến trúc máy tính song song có bộ nhớ chia sẻ, mô hình lập trình song song đa luồng thường được lựa chọn dựa trên chuẩn đang được sử dụng rộng rãi nhất để phát triển các chương trình song song là OpenMP (Open Multi- Processing).
Quá trình song song hóa chương trình với OpenMP được thực hiện bằng cách chèn vào trong mã nguồn các định hướng biên dịch (directive hoặc 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. OpenMP có thể hỗ trợ các ngôn ngữ thuộc dòng Fortran (Fortran 77/90/95) và C, C++. Với các kiến trúc máy tính song song có bộ nhớ phân tán, mô hình lập trình truyền thông điệp (Message Passing) với hai thư viện tiêu biểu: PVM (Parallel Virtual Machine) và MPI (Message Passing Interface) thường được sử dụng để phát triển các ứng dụng song song. Mô hình lập trình truyền thông điệp còn được nghiên cứu áp dụng cho các hệ thống có bộ nhớ dùng chung (ví dụ như các hệ thống Nec SX-6, Cray SV1ex).
Hiện nay, PVM đã không còn được tập trung phát triển. Trong khi đó, MPI ngày càng nhận được sự chú ý của các nhà cung cấp với các phiên bản LAM/MPI, MPICH. Trong tương lai không xa, phiên bản thống nhất OpenMPI của cộng đồng mã nguồn mở (MPI Forum) được xem là có nhiều triển vọng. Bộ công cụ Globus Toolkit là bộ phần mềm mã nguồn mở, được sử dụng phổ biến để xây dựng các hệ thống tính toán lưới và các ứng dụng trên lưới tính toán.
Để tính toán song song trên các đơn vị xử lý đồ họa (GPU), người ta sử dụng kiến trúc tính toán song song CUDA (Compute Unified Device Architecture - Kiến trúc thiết bị tính toán hợp nhất) do NVIDIA phát triển. Lập trình viên có thể sử dụng ngôn ngữ C for CUDA, dùng trình biên dịch PathScale Open64 C, để cài đặt các thuật toán chạy trên GPU. Kiến trúc CUDA hỗ trợ mọi chức năng tính toán thông qua ngôn ngữ C. Ngoài ra CUDA cũng hỗ trợ các ngôn ngữ Python, Fortran, Java và MATLAB.
CUDA cho phép các nhà phát triển truy nhập vào tập các chỉ lệnh ảo và bộ nhớ của các phần tử tính toán song song trong đơn vị xử lý đồ họa của CUDA (CUDA GPU). Sử dụng CUDA, các GPU mới nhất do NVIDIA sản xuất có thể dễ dàng thực hiện các tính toán như những CPU. Nói chung, các thuật toán tuần tự đều không khai thác tốt được hiệu năng của máy tính song song. Cùng với sự phát triển của các kiến trúc máy tính song song, vấn đề cấp thiết được nhiều nhà khoa học trong nước cũng như trên thế giới quan tâm là phát triển các thuật toán song song.
Luận án này nghiên cứu một số phương pháp song song giải hệ phương trình tuyến tính hoặc phi tuyến kích thước lớn và điều kiện xấu. Xét bài toán: F(x) = y, (1) 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com trong đó F là ánh xạ đưa không gian tuyến tính định chuẩn X vào không gian tuyến tính định chuẩn Y, còn y ∈ Y là dữ liệu đã cho trên bó máy tính. Một hệ phương trình điều kiện xấu và kích thước lớn được hiểu theo nghĩa sau: • Hệ phương trình tuyến tính được gọi là điều kiện xấu nếu một sai số nhỏ của vế phải hoặc của ma trận hệ số có thể gây nên sai số rất lớn ở nghiệm. • Hệ phương trình phi tuyến là điều kiện xấu nếu ma trận Jacobi của vế phải "gần suy biến" tại một số bước lặp nào đó [35].