Nâng cao hiệu năng tính toán cho thuật toán Dijkstra và Prim
1. Lý do chọn đề tài
Công nghệ thông tin đang phát triển với một tốc độ chóng mặt, di cùng đó là lượng dữ liệu khổng lồ. Để xử lý lượng dữ liệu khổng lồ đó đòi hỏi khối lượng tính toán rất lớn và thời gian là yếu tố quyết định tính thực tiễn của bài toán đó.
Để tăng tốc độ tính toán, các nhà khoa học đã đưa ra hai giải pháp:
Thứ nhất là cải tiến công nghệ, tăng tốc độ xử lý của máy tính. Công việc này đỏi hỏi nhiều thời gian, công sức và tiền bạc nhưng tốc độ thì chỉ đạt đến một giới hạn nhất định.
Thứ hai là chia bài toán ra thành những bài toán nhỏ để chạy song song trên nhiều bộ xử lý.
Các nhà khoa học đã tập trung nghiên cứu ở giải pháp thứ hai, từ đó ra đời thuật toán song song. Đó là việc sử dụng đồng thời nhiều tài nguyên tính toán để giải quyết một bài toán. Các tài nguyên tính toán có thể bao gồm một máy tính với nhiều bộ vi xử lý hay một tập các máy tính kết nối mạng hay là một sự kết hợp của hai dạng trên. Công nghệ tính toán song song cho phép giảm thời gian thực thi bài toán tùy thuộc cách phân chia và số bộ xử lý thực thi chương trình. Nguyên tắc quan trọng nhất của tính toán song song chính là tính đồng thời hay xử lý nhiều tác vụ cùng một lúc.
Với mục đích tìm hiểu và nghiên cứu về thuật toán song song để giải quyết bài toán đồ thị một cách hiệu quả hơn, thời gian xử lý ngắn hơn do đó tôi chọn đề tài: “Nâng cao hiệu năng tính toán cho thuật toán Dijkstra và Prim “
2. Mục tiêu và nhiệm vụ
2.1. Mục tiêu
Tìm hiểu, nghiên cứu và xây dựng thuật toán song song, ứng dụng một thư viện cụ thể nâng cao hiệu năng tính toán cho hai thuật toán Dijkstra và Prim nhằm giảm thời gian thực hiện, góp phần nâng cao hiệu năng hoạt động của hệ thống.
2.2. Nhiệm vụ
- Tìm hiểu về lý thuyết đồ thị.
- Nghiên cứu về xử lý song song và lập trình song song.
- Xây dựng và giải quyết một số bài toán đồ thị dự theo mô hình thư viện MPI.
- Cài đặt và đánh giá kết quả bài toán.
3. Đối tượng và phạm vi nghiên cứu:
3.1. Đối tượng nghiên cứu của đề tài
- XLSS và thuật toán song song.
- Các bài toán đồ thị.
- Lập trình song song với MPI.
3.2. Phạm vi nghiên cứu của đề tài
- Tổng quan về XLSS và phân tán.
- Tổng quan vè lý thuyết đồ thị.
4. Phương pháp nghiên cứu
4.1. Nghiên cứu lý thuyết
- XLSS và thuật toán song song.
- Đồ thị và các bài toán trên đồ thị.
- Tìm hiểu lập trình song song với MPI.
4.2. Nghiên cứu thực nghiệm
- Xây dựng sơ đồ, thuật toán song song.
- Lập trình song song với MPI bằng Visual Studio.
5. Bố cục đề tài
Ngoài phần mở đầu và kết thúc, nội dung chính của luận văn có 4 chương.
Chương 1: Xử lý song song.
Chương 2: Lập trình song song.
Chương 3: Các thuật toán trên đồ thị.
Chương 4: Xây dựng thuật toán song song trên đồ thị MPI.
6. Ý nghĩa khoa học và thực tiễn của đề tài
- Nghiên cứu và nâng cao hiệu năng của hệ thống bằng XLSS.
- Có thể áp dụng cho một số lĩnh vực cụ thể và một số bài toán có độ phức tạp về thời gian lớn, những bào toán thời gian thực
XỬ LÝ SONG SONG
Giới thiệu về xử lý song song
Trong những thâp niên 60, nền tảng để thiết kế máy tính trên thế giới đều dựa trên một mô hình của nhà toán học Hungary John Von Neumann (Hình 1.1), với một đơn vị xử lý được nối với một vùng lưu trữ làm bộ nhớ và tại một thời điểm chỉ có một lệnh được thực thi.
HÌNH 1.1 Mô hình John Von Neumann
Ngày nay, rất nhiều bài toán yêu cầu khả năng tính toán và lưu trữ rất lớn thì mô hình kiến trúc này còn hạn chế. Do đó để giải quyết các bài toán này cần có những hệ thống máy tính đủ mạnh để thực hiện một cách nhanh chóng và hiệu quả. Vì vậy, hướng xử lý song song với việc kết hợp nhiều bộ xử lý vào trong một máy tính được lựa chọn để giải quyết các bài toán đặt ra.
Xử lý song song hay tính toán 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 tính toán trên những hệ thống đa bộ xử lý [1].
Máy tính song song là tập hợp các bộ xử lý kết nối với nhau theo một kiến trúc xác định cùng hợp tác hoạt động và trao đổi song song.
Phân biệt xử lý song song với tuần tự:
Trong tính toán tuần tự với một BXL thì tại mỗi thời điểm chỉ thực hiện được một phép toán.
Trong tính toán song song thì nhiều BXL cùng kết hợp với nhau để giải quyết cùng một bài toán cho nen giảm được thời gian xử lý vì mỗi điểm có thể thực hiện đồng thời nhiều phép toán.
Mục đích của xử lý song song:
Thực hiện tính toán nhanh trên cơ sở sử dụng nhiều BXL đồng thời. Cùng với tốc độ xử lý nhanh hơn, việc xử lý song song cũng sẽ giải được những bài toán phức tạp yêu cầu khối lượng tính toán lớn.
Ba yếu tố chính dẫn đến việc xây dựng cá hệ thống xử lý song song:
Tốc độ xử lý của các BXL thoe 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.
Hiện nay giá thành phần cứng (CPU) giảm mạng, 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ý.
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ệ thống có hàng triệu transistor trên một chip.
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 và ngôn ngữ lập trình,v.v….
Hệ thống máy tính song song: là một tập các BXL (thường là cùng một loại) kết nối với nhau theo một kiến trúc 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.
Chúng ta dễ nhận tấy độ phức tạp của xử lý song song sẽ lớn hơn xử lý tuần tự rất nhiều, và tập trung chủ yếu ở phương diện trao đổi dữ liệu và đồng bộ các tiến trình.
Để 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 lập trình song song đang được sử dụng như: Fortran 90, Pthread với Fortran/C++, MPI với C/C++, PVM với c/C++, OpenMP với C/C++, v.v…
Kiến trúc máy tính song song
Theo Seyed H. Roosta và Michael Flynn, kiến trúc máy tính được phân thành 4 loại:
– SISD (Single Instructions Stream, Single Data Stream): Máy tính một luồng lệnh, một luồng dữ liệu. Các máy tính SISD tương ứng với các máy một bộ xử lý mà chúng ta đã nghiên cứu. 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.
– SIMD (Single Instructions Stream, Multiple Data Stream): Máy tính một luồng lệnh, nhiều luồng dữ liệu. Các máy SIMD có một số lớn các bộ xử lý giống nhau, cùng thực hiện một lệnh giống nhau để xử lý nhiều luồng dữ liệu khác nhau. Mỗi bộ xử lý có bộ nhớ dữ liệu riêng, nhưng chỉ có một bộ nhớ lệnh và một đơn vị điều khiển.
– MISD (Multiple Instructions Stream, Single Data Stream): Máy tính nhiều luồng lệnh, một 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 lệnh trên cùng một mục dữ liệu. Đây là lớp các máy tính yêu cầu những đơn vị xử lý khác nhau có thể nhận được những chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu.
– MIMD (Multiple Instruction Stream, Multiple Data Stream): Máy tính nhiều luồng lệnh, nhiều luồng dữ liệu. Các máy MIMD nổi lên và được xem như một kiến trúc đương nhiên phải chọn cho các máy nhiều bộ xử lý dùng trong các ứng dụng thông thường, một tập hợp các bộ xử lý thực hiện một chuỗi các lệnh khác nhau trên các tập hợp dữ liệu khác nhau. Máy tính loại MIMD còn gọi là đa bộ xử lý. Trong đó, mỗi bộ xử lý có thể thực hiện những luồng lệnh 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.
Mô hình SISD
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 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.2 mô tả hoạt động của máy tính theo mô hình SISD.
HÌNH 1.2 Mô hình kiến trúc song SISD
Mô hình SISD còn được gọi là SPSD (Simple Program Simple Data), đơn chương trình và đơn dữ liệu. Đây chính là mô hình máy tính kiểu Von Neumann.
Kiến trúc song song SIMD
Máy tính loại SISD chỉ có một đơn vị điều khiển (CPU), ở mỗi thời điểm nhiều đơn vị xử lý được thực hiện cùng lúc. CPU phát sinh tín hiệu điều khiển đến các đơn vị xử lý. Tất cả các đơn vị xử lý đều nhận cùng mệnh lệnh từ đơn vị điều khiển nhưng mỗi đơn vị xử lý lại có luồng dữ liệu riêng. Một máy SIMD có những đặc điểm sau: xử lý phân tán trên một số lượng lớn phần cứng, thực hiện đồng thời trên nhiều thành phần dữ liệu khác nhau và thực hiện cùng một câu lệnh trên các thành phần dữ liệu. Mô hình kiến trúc song song SIMD được Seyed H. Roosta trình bày như trong Hình 1.3.
HÌNH 1.3 Mô hình kiến trúc MIMD
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.
Kiến trúc song song MISD
Máy tính loại 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 2 nhóm:
Lớp các máy tính yêu cầu những đơn vị xử lý khác nhau có thể nhận được những chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. Đây là kiến trúc khó và hiện nay chưa có loại máy tính nào được sản xuất theo loại này.
Lớp các máy tính có các luồng dữ liệu được chuyển tuần tự theo dãy các CPU liên tiếp. Đây là 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.4 mô tả hoạt động của máy tính theo mô hình MISD.
HÌNH 1.4 Mô hình MISD chi sẽ bộ nhớ
Mô hình máy tính MIMD
Máy tính MIMD còn gọi là đa bộ xử lý, trong đó mỗi bộ xử lý có thể thực hiện những luồng lệnh (chương trình) khác nhau trên các luồng dữ liệu riêng.
Hầu hết các hệ thống MIMD đều có bộ nhớ riêng và cũng có thể truy cập được vào bộ nhớ chung (global) khi cần, do vậy giảm thiểu được sự trao đổi giữa các bộ xử lý trên 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…
Mô hình MIMD gồm hai loại: loại các bộ kết nối chặt và loại các bộ kết nối rời tùy thuộc vào cách thức mà các bộ xử lý truy cập vào bộ nhớ. Những bộ xử lý kết nối chặt được chia sẻ từ một hệ thống bộ nhớ chung được hiểu là hệ thống chia sẻ bộ nhớ. Mô hình này được Seyed H. Roosta trình bày như trong Hình 1.5.
HÌNH 1.5 Mô hình MIMD chia sẽ bộ nhớ
Đối với hệ thống MIMD kết nối rời chia sẻ từ bộ nhớ hệ thống nhưng mỗi bộ xử lý có một bộ nhớ riêng được hiểu như hệ thống truyền thông điệp. Những máy tính truyền thông điệp gửi đến nhiều máy tính trong đó mỗi bộ xử lý có bộ nhớ riêng và chỉ truy cập đến bộ xử lý đó. Mô hình này được Seyed H. Roosta trình bày như trong Hình 1.6
HÌNH 1.6 Mô hình MIMD truyền thông điệp
Các mô hình lập trình song song
Việc đưa ra một mô hình máy tính chung cho việc lập trình giúp cho việc thiết kế giải thuật trở nên đơn giản hơn. Lập trình song song đưa thêm những khó khăn mới vào mô hình lập trình tuần tự. Nếu chương trình được thực hiện ở mức thấp nhất thì không những số lệnh thực hiện là rất lớn mà nó còn phải trực tiếp quản lý quá trình thực hiện song song của hàng nghìn bộ xử lý và kết hợp hàng triệu tương tác liên bộ xử lý. Bởi vậy khả năng trừu tượng và tính toán module là các đặc tính rất quan trọng trong lập trình song song. Các mô hình thông dụng bao gồm:
- Mô hình chia sẽ bộ nhớ.
- Mô hình luồng.
- Mô hình truyền thông điệp.
- Mô hình song song dữ liệu.
Mô hình chia sẽ bộ nhớ
Trong mô hình này, nhiệm vụ cùng chia sẽ một không gian địa chỉ chung có thể được truy cập đọc ghi theo phương thức không đồng bộ. Các cơ chế khác nhau như khóa (locks) và semaphore được điều khiển để truy cập đến bộ nhớ toàn cục.
Nhược điểm của mô hình này là khó giữ lại được tính nguyên thủy của dữ liệu khi mà nhiều bộ xử lý dùng cũng dữ liệu này.
Lợi thế của mô hình là người lập trình không cần chỉ định việc truyền dữ liệu giữa các task; chương trình được phát triển thường được đơn giản hóa.
Mô hình luồng
Trong mô hình luồng chương trình chính được chia thành các nhiệm vụ. Mỗi nhiệm vụ được thực hiện bởi các luồng một cách đồng thời. Mỗi một luồng có dữ liệu riêng của nó và chia sẽ dữ liệu toàn cục của chương trình chính. Các nhiệm vụ đưa cho mỗi luồng là các thủ tục con của chương trình chính. Bất kỳ luồng nào cũng có thể thực hiện bất kì thử tục con nào tại cùng thời điểm với các luồng khác. Trong mô hình luồng các luồng kết nối với nhau thông qua bộ nhớ toàn cục với việc kết nối này thì chương trình phải được xây dựng một cách đồng bộ để tránh cùng một lúc có nhiều luồng cùng cập nhập một vị trí trong bộ nhớ toàn cục.
Mô hình truyền thông điệp
Trong mô hình truyền thông điệp chương trình song song được chia thành các tác nhiệm. Mỗi tập các tác nhiệm sử dụng bộ nhớ cục bộ riêng của chúng trong quá trình tính toán. Nhiều tác nhiệm có thể nằm trên cùng một máy cũng như nằm trên nhiều máy.
Các tác nhiệm trao đổi dữ liệu thông qua truyền thông bằng cách gửi và nhận các thông điệp.
Có nhiều thư viện truyền thông điệp, nhưng chúng khác nhau đáng kể, gây khó khăn cho các nhà lập trình trong việc phát triển các ứng dụng di động. MPI Forum được lập ra với mục đích thiết lập một chuẩn cho việc triển khai mô hình truyền thông điệp. Hiện nay, MPI là chuẩn mô hình truyền thông điệp.
Mô hình phân hoạch dữ liệu
Mô hình lập trình song song dữ liệu giúp lập trình các chương trình song song được thực hiện trên một tập dữ liệu lớn. Tập dữ liệu ở đây thường được sắp xếp theo một cấu trúc nhất định như là mảng hoặc theo khối. Với mô hình này thì các nhiệm vụ của chương trình làm việc với cùng một cấu trúc dữ liệu. Tuy nhiên mỗi nhiệm vụ sẽ làm việc trên từng phân vùng khác nhau của dữ liệu và các nhiệm vụ phải thực hiện các thao tác giống nhau.
HÌNH 1.8 Mô tả lập trình phân hoạch dữ liệu
Trong kiến trúc chia sẽ bộ nhớ chung, tất cả các nhiệm vụ truy cập vào cấu trúc dữ liệu thông qua bộ nhớ toàn cục. Còn đối với kiến trúc bộ nhớ phân tán thì dữ liệu được chia ra và lưu trữ trên các bộ nhớ cục bộ của các bộ xử lý.
Thuật toán song song
Quy trình thiết kế thuật toán song song
Song song hóa thuật toán là chuyển một thuật toán tuần tự đã có thành một thuật toán song song. Quy trình thiết kế thuật toán song song thực hiện qua bốn công đoạn: phân rã (Partition), truyền thông (Communication), tích tụ (Agglomeration) và ánh xạ (Mapping).
– Phân rã: Khi bài toán được xác định, công việc tính toán và dữ liệu của bài toán được phân rã thành nhiều tác vụ. Ta cố gắng chú trọng vào việc xác định được nhiều tác vụ càng nhiều càng tốt nếu có thể. Số lượng tác vụ có thể lớn hơn nhiều so với số lượng bộ xử lý để linh hoạt hơn khi áp dụng vào mô hình thực tế. Trong giai đoạn này ta chưa đề cập đến vấn đề truyền thông, cấu trúc máy tính song song mà chỉ đề cập đến việc xác định được các khả năng thực hiện song song của bài toán. Mục đích của công đoạn này là ta tìm ra tập các tác vụ độc lập với nhau của bài toán và chú ý việc kết hợp dữ liệu, xác định kết hợp tính toán với dữ liệu như thế nào.
– Truyền thông: Công đoạn truyền thông được thể hiện thông qua luồng thông tin sao cho các tác vụ được tạo ra trong công đoạn trên sẽ được thực hiện đồng thời. Tính toán thực hiện trong một tác vụ thường sẽ yêu cầu dữ liệu kết hợp với các dữ liệu khác. Sau đó, dữ liệu phải được truyền giữa các tác vụ để cho phép thực hiện tính toán.
– Tích tụ: Công đoạn này sẽ gộp các tác vụ nhỏ đã tạo ra ở công đoạn phân rã thành các tác vụ có kích thước lớn hơn. Khi tích tụ các tác vụ nhỏ thành các tác vụ lớn thì chi phí truyền thông sẽ giảm đi nhưng sẽ làm giảm tiềm năng thực hiện đồng thời.
– Ánh xạ: Đây là công đoạn cuối cùng, mỗi tác vụ sẽ được ấn định vào một bộ xử lý nào đó.
Nguyên lý thiết kế 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.
Để thiết kế được các thuật toán song song cần phải thực hiện:
– Phân chia dữ liệu cho các tác vụ.
– Chỉ ra cách truy cập và chia sẻ dữ liệu.
– Phân các tác vụ cho các tiến trình (bộ xử lý).
– 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 [1]:
1. 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).
2. 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.
3. 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.
4. 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.
5. 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:
1. 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.
2. 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.
Các cách tiếp cận trong thiết kế
Song song hóa các thuật toán tuần tự biến đổi những cấu trúc tuần tự để tận dụ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ế thuật toán song song hoàn toàn mới.
Thiết kế thuật toán song song từ những thuật toán song song đã được xây dựng.
Phân tích đánh giá thuật toán song song
Trong thuật toán tuần tự chúng ta chỉ quan tâm đến độ phức tạp về thời gian và không gian, nhưng trong thuật toán song song thường có thêm một số đại lượng đo lường khác. Độ phức tạp thời gian của thuật toán song song không chỉ đơn giản là việc đếm số câu lệnh cơ bản như trong thuật toán tuần tự mà thay vào đó nó phụ thuộc vào các phép toán cơ bản này có thể được thực hiện trên p bộ xử lý như thế nào. Bên cạnh độ phức tạp thời gian độ phức tạp về số bộ xử lý cũng là một đại lượng quan trọng trong phân tích thiết kế thuật toán song song.
Thiết kế thuật toán song song hiệu quả bao gồm việc lựa chọn cấu trúc dữ liệu phù hợp, phân bố bộ xử lý và cuối cùng là thực hiện thuật toán. Ba đại lượng này tác động lẫn nhau như một tổ chức tính toán.
Đánh giá thuật toán song song
Độ 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 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 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 vớ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:
1. Các phép toán cơ sở như +, -, *, /, AND, OR…
2. 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 đề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.
Thời gian tính toá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 xét trong thời gian thực hiện của thuật toán. [5]
Thời gian thực hiện song song, ký hiệu là tp gồm hai phần là tcomp và tcomm
tp = tcomp + tcomm (1.1)
Trong đó tcomp là thời gian tính toán và tcomm là 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 thực hiện đồng thời thì chỉ cần tính thời gian thực hiện của tiến trình phức tạp nhất. Trong phân tích độ phức tạp thuật 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à cùng một tốc độ xử lý 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 nên việc đánh giá thời gian 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à 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 cách thức truyển tải thông điệp. Công thức ước lượng thời gian truyền thông điệp đượ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 mục dữ liệu (data word) 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.
Chi phí cho một thuật toán song song được xác định bằng tích của thời gian tính toán song song và số bộ xử lý được sử dụng. Chi phí này phản ánh tổng số thời gian mà một bộ xử lý dùng để giải quyết bài toán.
Hệ số tăng tốc cũng là yếu tố đáng chú ý khi đánh giá thuật toán song song được song song hoa từ một thuật toán tuần tự.
Hệ số tăng tốc là tỉ lệ giữa thời gian thực hiện của thuật toán tuần tự ts và thời gian thực hiện của thuật toán song song tp với p bộ xử lý
Sp = ts / tp
Giả sử các bộ xử lý trong hệ thống song song hoàn toàn giống với bộ xử lý sử dụng trong tính toán tuần tự và ts là thời gian thực hiện bài toán bằng tính toán tuần tự tối ưu nhất. Hệ số tăng tốc lý tưởng đạt được khi Sp = p.
Rõ ràng khả năng tăng tốc càng lớn thì giải thuật song song càng tốt.
Tuy nhiên, năm 1967 Amdahl đã đưa ra luật về giới hạn khả năng tăng tốc như sau:
Khi tăng số lượng bộ xử lý trong máy tính song song, khối lượng công việc được phân phối với nhiều bộ xử lý thực hiện. Mục tiêu chính là tìm được kết quả bài toán nhanh nhất có thể hay nói cách khác là giảm đến mức tối đa thời gian tính toán.
Luật Amdahl: luật này phát biểu rằng nếu P là tỉ lệ có thể song song hóa của thuật toán tuần tự thì hệ số tăng tốc lớn nhất có thể đạt được khi sử dụng N bộ xử lý là Ta có biểu đồ thể hiện luật Amdahl như hình 1.9.
Hiệu suất của tính toán song song là tỉ số giữa hệ số tăng tốc và số các phần tử xử lý trong hệ thống song song.
Thuật toán song song có thể có độ phức tạp lớn hơn thuật toán tuần tự, do đó rất khó để đánh giá thuật toán song song. Kết quả đạt được thường được đánh giá bằng thực nghiệm chương trình.
Kết luận chương
Để 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à 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 nhưng vẫn bảo toàn được tính tương đương trong tính toán.
Dựa vào bốn công đoạn và 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.
Để đá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 thời gian của thuật toán. Độ phức tạp thời gian 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.
LẬP TRÌNH SONG SONG VỚI MPI
Tổng quan về lập trình song song trong môi trường MPI
Giới thiệu
Message Passing Interface – MPI là một chuẩn mới được sử dụng rộng rãi nhất. Nó không phải là một ngôn ngữ lập trình mới, thay vào đó nó là một thư viện của chương trình con mà có thể được gọi từ chương trình C và Fortran 77.
MPI được phát triển bởi một diễn đàn mở quốc tế, bao gồm các đại diện từ ngành công nghiệp, các học viện và phòng thí nghiệm của chính phủ. Nó đã nhanh chóng được chấp nhận rộng rãi bởi được thiết kế cẩn thận cho phép hiệu suất tối đa trên một loạt các hệ thống, và nó dựa trên truyền thông điệp, một trong những mô hình mạnh mẽ nhất và được sử dụng rộng rãi cho lập trình các hệ thống song song.
Những nỗ lực cho MPI bắt đầu vào mùa hè năm 1991, khi một nhóm nhỏ các nhà nghiên cứu bắt đầu thảo luận tại một nơi hẻo lánh trên núi ở Úc.
Nội dung đó lại được thảo luận tại hội thảo “Tiêu chuẩn cho truyền thông điệp trong một môi trường bộ nhớ phân tán” (Standards for Message Passing in a Distributed Memory environment) tổ chức vào ngày 29 – 30 tháng 4 năm 1992 tại Williamsburg, Virginia. Tại hội thảo này, các tính năng cơ bản cần thiết cho một MPI chuẩn đã được thảo luận, mà một nhóm cộng tác đã được thành lập để tiếp tục quá trình tiêu chuẩn hoá. Jack Dongarra, Rolf Hempel, Tony Hey và David W.Walker đưa ra một bản dự thảo sơ bộ được biết đến như MPI-1 trong tháng 11 năm 1992.
Trong tháng 11 năm 1992, một cuộc họp của nhóm cộng tác MPI đã được tổ chức tại Minneapolis, mà tại đó hội thảo quyết định đặt các quá trình tiêu chuẩn hoá trên một cơ sở chính thức hơn. Nhóm cộng tác MPI đã gặp nhau 6 tuần một lần trong suốt 9 tháng đầu của năm 1993. Bản dự thảo chuẩn MPI đã được trình bày tại hội nghị Siêu máy tính năm 93 trong tháng 11 năm 1993.
Sau một thời gian nhận những ý kiến đóng góp từ cộng đồng, một số kết quả được thay đổi trong MPI, phiên bản 1.0 của MPI được phát hành vào tháng 6 năm 1994. Thông qua những cuộc gặp gỡ và thư điện tử, các nhà nghiên cứu đã thảo luận với nhau thành lập diễn đàn MPI, trong đó tất cả các thành viên của cộng đồng điện toán hiệu suất cao đều có thể đăng ký làm thành viên của diễn đàn.
MPI đã thu hút sự tham gia khoảng 80 người từ 40 tổ chức, chủ yếu là ở Mỹ và Châu Âu. Hầu hết các nhà cung cấp chính của máy tính đều được tham gia vào MPI cùng với các nhà nghiên cứu từ các trường đại học, phòng thí nghiệm của chính phủ và ngành công nghiệp.
Một số đặc điểm của lập trình MPI
MPI là một giao thức truyền thông độc lập với ngôn ngữ dùng để lập trình máy tính song song. MPI hỗ trợ cả giao tiếp điểm – điểm và giao tiếp tập thể. Mục tiêu của MPI là hiệu suất, khả năng mở rộng và khả năng di động cao.
MPI thường xuyên chạy trên các máy tính chia sẻ bộ nhớ. Mặc dù MPI thuộc về lớp thứ 5 và lớp cao hơn của mô hình OSI, nhưng những triển khai có thể bao gồm hầu hết các lớp, với socket và TCP (Transmission Control Protocol) được dùng trong tần vận chuyển.
Hầu hết các triển khai MPI bao gồm một thiết lập định tuyến riêng có thể được gọi trực tiếp từ C, C++, Fortran hay bất kỳ ngôn ngữ nào có giao diện với các thư viện, bao gồm C#, Java hoặc Python. Những ưu điểm ucar MPI vượt qua những thư viện truyền thông điệp cũ là tính di động (MPI có thể được triển khai cho hầu hết các kiến trúc bộ nhớ phân tán) và tốc độ (MPI thực hiện nguyên tắc tối ưu hoá cho phần cứ mà nó chạy).
MPI sử dụng LIS (Language Independent Specifications) để gọi và ràng buộc ngôn ngữ. Phiên bản đầu tiên được phát hành chỉ định ràng buộc ANSI C và Fortran 77 cùng với LIS. Năm 2008, chuẩn MPI-1.3 chứa khoảng 128 chức năng, đây cũng là phát hành cuối cùng của seri MPI-1 trong năm 2008.
Phiên bản MPI-2.2 bao gồm những tính năng mới như là I/O song song, quản lý tiến trình động và điều hành bộ nhớ từ xa. LIS của MPI-2 thiết lập hơn 500 hàm và cung cấp ràng buộc ngôn ngữ cho ANSI C, ANSI C++ và ANSI Fortran (Fortran 90). Khả năng tương tác đối tượng cũng được thêm vào để cho phép lập trình truyền thông điệp bằng ngôn ngữ hỗn hợp dễ dàng hơn.
MPI cung cấp mô hình liên kết ảo, đồng bộ hoá và chức năng liên lạc giữa một tập hợp các tiến trình (đã được ánh xạ tới các nút/máy chủ/máy tính cụ thể) trong một ngôn ngữ độc lập, với cú pháp ngôn ngữ đặc trưng (ràng buộc), cùng với một vài tính năng ngôn ngữ đặc trưng. Những chương trình MPI luôn luôn làm việc với các tiến trình, nhưng những lập trình viên thường xem các tiến trình như là những bộ vi xử lý. Thông thường, để đạt hiệu suất tối đa, mỗi CPU (hoặc 1 nhân trong một máy tính đa nhân) sẽ được giao chỉ một tiến trình duy nhất.
Những chức năng thư viện MPI bao gồm (không giới hạn) những hoạt động nhận/gửi loại điểm – điểm, lựa chọn giữa mô hình xử lý logic Cartesian hoặc mô hình xử lý logic đồ thị tương đồng, trao đổi dữ liệu giữa những cặp tiến trình, kết hợp các kết quả từng phần của tính toán (thu thập và giảm các hoạt động), đồng bộ hoá các nút cũng như thu thập thông tin liên quan đến mạng như số lượng của tiến trình trong phiên tính toán, nhận dạng bộ vi xử lý hiện tại mà bộ vi xử lý được ánh xạ, những tiến trình lân cận truy cập trong một mô hình liên kết logic.
Lập trình song song với môi trường MPI
Giới thiệu
Giao thức truyền thông điệp MPI là một thư viện các hàm và macro có thể được gọi từ các chương trình sử dụng ngôn ngữ C, Fortran, và C++. Như tên gọi của nó MPI được xây dựng nhằm sử dụng trong các chương trình để khai thác hệ thống các bộ xử lý bằng cách truyền thông điệp.
– Thiết kế một giao diện lập trình ứng dụng. Mặc dù MPI gần đây được sử dụng như một chương trình dịch và một thư viện ở thời gian chạy, nhưng thiết kế của MPI chủ yếu phản ánh nhu cầu nhận thức của những người lập trình ứng dụng.
– Cho phép truyền thông một cách hiệu quả: tránh việc sao chép dữ liệu từ bộ nhớ sang bộ nhớ và cho phép gối chồng (overlap) giữa các tính toán và truyền thông và offload để truyền thông đồng xử lý khi có thể.
– Cho phép thực thi trên một môi trường không đồng nhất.
– Có thể được gắn kết dễ dàng vào trong các chương trình ngôn ngữ C và Fortran.
– Cung cấp một giao thức truyền thông tin cậy: người dùng không cần phải lo lắng tới thất bại trong truyền thông. Các thất bại này được xử lý bởi các hệ thống truyền thông cơ sở phía sau.
– Định nghĩa một giao thức không quá khác biệt so với các môi trường song song hiện tại như PVM (Parallel Vitual Machine), NX, Express… và cung cấp các mở rộng cho phép độ linh hoạt cao hơn.
– Định nghĩa một giao thức có thể được thực thi trên các môi trường (flatform) của nhiều nhà cung cấp mà không cần thay đổi nào đáng kể trong truyền thông cơ sở và phần mềm hệ thống.
– Ngữ nghĩa của giao thức là độc lập với ngôn ngữ.
– Giao thức được thiết kế cho phép sử dụng luồng một cách an toàn.
– Một lượng lớn các hàm truyền thông điểm – điểm (phong phú hơn rất nhiều so với các môi trường lập trình song song khác).
– Một lượng lớn các thủ tục truyền thông chọn lọc, được sử dụng để giao tiếp giữa một nhóm các bộ xử lý trong hệ thống.
– Một ngữ cảnh truyền thông hỗ trợ cho việc thiết kế các thư viện phần mềm song song.
– Có khả năng xác định các topology truyền thông.
– Có khả năng định nghĩa các kiểu dữ liệu mới để mô tả các thông báo dựa trên các dữ liệu không liên tục.
Một chương trình MPI bao gồm các bộ xử lý độc lập, thực thi các mã lệnh riêng của chúng trong một mô hình MIMD (Multiple Instruction Multiple Data). Các tập lệnh được thực thi bởi các bộ xử lý không nhất thiết phải giống nhau, việc truyền thông giữa các bộ xử lý được thực hiện thông qua việc gọi các hàm truyền thông của MPI.
MPI không định rõ kiểu thực thi cho mỗi bộ xử lý. Bộ xử lý A có thể chạy tuần tự, hoặc có thể thực thi ở dạng đa luồng với các luồng được kích hoạt đồng thời. Điều này thực hiện được do tính chất luồng an toàn (thread-safe) của MPI bằng cách tránh sử dụng các trạng thái tuyệt đối.
Một ứng dụng MPI có thể được thực thi như là một tập các nhiệm vụ truyền thông đồng thời. Một chương trình bao gồm các đoạn mã của người lập trình được liên kết với các hàm thư viện được cung cấp bởi phần mềm MPI. Mỗi nhiệm vụ được chỉ định một thứ hạng (rank) duy nhất trong khoảng 1-> n-1 với các ứng dụng có n nhiệm vụ. Các hạng này được sử dụng để xác định các nhiệm vụ MPI khác nhau trong việc gửi và nhận tin cũng như thực hiện các thao tác truyền thông nói chung. Nhiệm vụ MPI có thể chạy trên cùng bộ xử lý hoặc các bộ xử lý khác nhau một cách đồng thời. Lợi ích của các rank là làm cho thao tác phối hợp độc lập với vị trí vật lý của các thành phần.
Một số vấn đề hiệu năng
Năng lực tính toán
Việc song song hóa một chương trình nhằm làm cho chương trình đó chạy nhanh hơn, tuy nhiên chương trình đó sẽ chạy nhanh hơn bao nhiêu lần? Định luật Amdahl’s cho phép ta xác định điều này. Giả sử xét về khía cạnh thời gian chạy chương trình, một phần p của chương trình có thể song song hóa và phần 1p còn lại buộc phải chạy tuần tự. Trong trường hợp lý tưởng, nếu thực thi chương trình sử dụng n bộ xử lý, thời gian chạy chương trình sẽ là 1-p + p/n của thời gian chạy chương trình một cách tuần tự. Đây là hệ quả trực tiếp của định luật Amdahl áp dụng cho trường hợp thực thi lý tưởng.
Ví dụ: nếu 80% chương trình có thể được song song hóa, và ta có 4 bộ xử lý, thời gian chạy song song sẽ là: 1 – 0.8 + 0.8/4 = 0.4 tức là bằng 40% thời gian chạy tuần tự.
20 80
HÌNH 2.1 Khả năng tăng tốc độ tính toán, trường hợp lý tưởng
Đối với chương trình trên, thời gian chạy song song sẽ không thể nào nhỏ hơn 20% thời gian chạy tuần tự cho dù ta sử dụng số lượng vô cùng lớn các bộ xử lý.
Trên thực tế, khi chạy một chương trình song song, thường xuất hiện các chi phí truyền thông và việc phân công công việc không cân bằng giữa các bộ xử lý. Do đó thời gian chạy chương trình sẽ là:
HÌNH 2.2 Khả năng tăng tốc độ tính toán, trường hợp thực tế
Do vậy để tăng tốc độ của chương trình ta cần:
- Tăng tỉ lệ (thành phần) được song song hóa của chương trình.
- Phân công công việc một cách công bằng cho các bộ xử lý.
- Giảm tới mức tối thiểu thời gian truyền thông.
Cân bằng tải
Giả sử rằng nếu dữ liệu được phân tán trên các bộ nhớ địa phương của các bộ xử lý trong hệ thống nhiều máy tính, khi đó khối lượng công việc của các bộ xử lý cần phải được phân phối hợp lý trong suốt quá trình tính toán. Trong nhiều trường hợp, giả sử này là đúng, tuy nhiên trong thực tế điều này không phải lúc nào cũng thực hiện được. Giải pháp được đưa ra ở đây là cân bằng tải động nhằm mục đích làm thay đổi sự phân phối khối lượng công viêc giữa các bộ xử lý trong quá trình thực hiện tính toán.
Thông thường sau khi phân phối khối lượng công việc cho các bộ xử lý, quá trình cân bằng tải động thực hiện bốn bước cơ bản sau:
- Giám sát hiệu năng của các bộ xử lý.
- Trao đổi thông tin trạng thái giữa các bộ xử lý.
- Tính toán và ra quyết định phân phối lại khối lượng công việc.
- Thực hiện việc chuyển đổi dữ liệu thực sự.
Để thực hiện được điều này, rất nhiều thuật toán đã được đề xuất. Người ta phân lớp các thuật toán này theo các chiến lược: tập trung, phân tán hoàn toàn (fully distributed) và phân tán một nửa (semi distributed).
Các thuật toán cân bằng tải tập trung
Các thuật toán này thường đưa ra quyết định có tính chất tổng thể trong việc phân phối lại khối lượng công việc cho các bộ xử lý. Một vài thuật toán trong lớp này sử dụng thông tin hệ thống có tính toàn cục để lưu trạng thái các máy tính riêng lẻ. Thông tin này sẽ giúp thuật toán phân phối công việc một cách dễ dàng. Tuy nhiên, khối lượng thông tin tăng theo tỉ lệ thuận với số lượng các bộ xử lý, do đó nó đòi hỏi khối lượng lớn bộ nhớ trên mộtbộ xử lý để lưu thông tin trạng thái. Vì vậy thuật toán thuộc lớp này không được tiếp cận một cách rộng rãi.
Các thuật toán cân bằng tải phân tán hoàn toàn
Trong các thuật toán dạng này, mỗi bộ xử lý có một bản sao về thông tin trạng thái của hệ thống. Các bộ xử lý trao đổi thông tin trạng thái với nhau và sử dụng các thông tin này để làm thay đổi một cách cục bộ việc phân chia công việc. Tuy nhiên các bộ xử lý chỉ có thông tin trạng thái cục bộ nên việc cân bằng tải không tốt bằng các thuật toán cân bằng tải tập trung.
Các thuật toán cân bằng tải phân tán một nửa
Các thuật toán thuộc lớp này chia các bộ xử lý thành từng miền. Trong mỗi miền sử dụng thuật toán cân bằng tải tập trung để phân phối công việc cho các bộ xử lý thuộc miền đó.
E:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\HE THONG THONG TIN/NGUYEN DANG KHOA – K34 – HTTH
