Luận văn: Thuật toán song song cho một số bài toán trên đồ thị - Đỗ Trung Kiên

Nghiên cứu thuật toán song song áp dụng cho các bài toán trên đồ thị. Luận văn giới thiệu đại cương về tính toán song song, mô hình PRAM và định lý Amdahl.

• Tác giả: Đỗ Trung Kiên
• Trường học: Trường Đại Học Bách Khoa Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Thuật Toán Song Song Cho Một Số Bài Toán Trên Đồ Thị
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2006
• Địa điểm: Hà Nội

Tóm tắt

I. Khái niệm cơ bản về Thuật toán Song song

Thuật toán song song là quá trình xử lý thông tin trong đó nhiều đơn vị dữ liệu được xử lý đồng thời bởi một hay nhiều bộ xử lý để giải quyết bài toán trên đồ thị. Đây là một ngành quan trọng trong lĩnh vực công nghệ thông tin hiện đại. Tính toán song song giúp tăng đáng kể tốc độ xử lý so với các thuật toán tuần tự truyền thống. Các máy tính song parallel được chia thành hai loại chính: máy tính song song dựa trên bộ vi xử lý với tốc độ vừa phải và siêu máy tính với ít bộ xử lý nhưng tốc độ cực cao. Việc áp dụng thuật toán song song cho đồ thị đã mở ra nhiều cơ hội giải quyết các bài toán phức tạp một cách hiệu quả, đặc biệt là trong các lĩnh vực phân tích dữ liệu lớn, mô phỏng khoa học và tối ưu hóa.

1.1. Song song về dữ liệu và điều khiển

Song song về dữ liệu (data parallelism) là cơ chế sử dụng nhiều đơn vị xử lý thực hiện cùng một thao tác trên nhiều đơn vị dữ liệu khác nhau. Song parallel điều khiển (control parallelism) là cơ chế trong đó nhiều thao tác khác nhau tác động lên nhiều đơn vị dữ liệu khác nhau một cách đồng thời. Hai cơ chế này đóng vai trò quan trọng trong việc tối ưu hóa hiệu suất của các thuật toán song song trên đồ thị.

1.2. Dây chuyên và cơ chế xử lý

Dây chuyên (pipeline) là cơ chế chia công việc thành nhiều chặng nối tiếp, mỗi chặng được thực hiện bởi một bộ phận khác nhau. Đầu ra của bộ phận này trở thành đầu vào của bộ phận tiếp theo, tạo ra một quy trình xử lý liên tục. Cơ chế này giúp tối ưu hóa hiệu suất tính toán song song và là nền tảng quan trọng cho nhiều ứng dụng thực tiễn.

II. Các chỉ số đánh giá Hiệu suất Thuật toán Song parallel

Đánh giá hiệu suất của thuật toán song parallel đòi hỏi hiểu biết về các chỉ số quan trọng như tăng tốc, hiệu quả và chi phí tính toán. Tăng tốc (speedup) là tỉ số giữa thời gian thực hiện của thuật toán tuần tự tốt nhất và thời gian thực hiện của thuật toán song parallel. Định lý Amdahl phát biểu rằng tăng tốc bị giới hạn bởi tỷ lệ thao tác tuần tự trong tổng số thao tác phải làm. Hiệu quả (efficiency) được tính bằng tỉ số giữa tăng tốc và số bộ xử lý tham gia tính toán. Chi phí (cost) được tính bằng độ phức tạp tính toán nhân với số lượng bộ xử lý, giúp đánh giá hiệu quả kinh tế của hệ thống xử lý song parallel.

2.1. Định lý Amdahl và tăng tốc

Định lý Amdahl là nguyên lý cơ bản trong tính toán song parallel, phát biểu rằng tăng tốc bị giới hạn bởi tỷ lệ phần đơn điểu trong chương trình. Nếu gọi f là tỷ lệ thao tác tuần tự trên tổng số thao tác, với 0 < f < 1, thì tăng tốc tối đa với p bộ xử lý được xác định bởi công thức toán học cụ thể. Định lý này cho thấy rằng ngay cả với số lượng bộ xử lý vô hạn, tăng tốc cũng bị giới hạn bởi phần tuần tự của chương trình.

2.2. Đơn vị đo lường Flop

Flop (floating point operations per second) là đơn vị đo tốc độ của máy tính song parallel, biểu thị số phép tính toán hạng số thực dấu phay động thực hiện được trong một giây. Các đơn vị lớn hơn bao gồm Megaflop/s (10^6 flop/s), Gigaflop/s (10^9 flop/s) và Teraflop/s (10^12 flop/s). Những chỉ số này cho phép so sánh hiệu suất giữa các hệ thống xử lý song parallel khác nhau.

III. Các mức độ Song parallel trong Bài toán Đồ thị

Các mức độ song parallel được phân chia thành bốn cấp bậc khác nhau. Mức song parallel chương trình là mức cao nhất, nơi các công việc khác nhau được giao cho các máy khác nhau thực hiện. Mức song parallel chương trình con chia mỗi công việc thành các công đoạn (Task) có thể thực hiện song parallel. Mức song parallel câu lệnh cho phép nhiều câu lệnh thực hiện đồng thời, cuối cùng là mức song parallel thao tác ở cấp độ thấp nhất. Đối với bài toán trên đồ thị, việc hiểu rõ các mức độ này giúp thiết kế thuật toán song parallel hiệu quả và tận dụng tối đa khả năng xử lý của hệ thống.

3.1. Phân chia công việc và Task

Trong xử lý song parallel cho đồ thị, công việc được chia thành các Task (công đoạn) nhỏ hơn có thể thực hiện độc lập. Mỗi Task có thể được giao cho một bộ xử lý riêng biệt, từ đó tạo nên song parallel chương trình con. Cách chia Task hợp lý là chìa khóa để đạt hiệu suất cao trong thuật toán song parallel trên đồ thị, đặc biệt khi xử lý các đồ thị lớn với hàng triệu đỉnh và cạnh.

3.2. Mục tiêu tối ưu hóa và cân bằng tải

Cân bằng tải (load balancing) là yếu tố quan trọng trong thiết kế thuật toán song parallel để đạt hiệu suất cao. Mục tiêu là phân phối công việc sao cho tất cả bộ xử lý được sử dụng đều đặn mà không có sự chênh lệch lớn. Trong bài toán trên đồ thị, việc cân bằng tải đòi hỏi phân vùng đồ thị một cách thông minh để đảm bảo mỗi bộ xử lý xử lý khối lượng công việc gần như nhau.

IV. Mô hình PRAM và kiến trúc Xử lý Song parallel

Mô hình PRAM (Parallel Random Access Machine) là mô hình lý thuyết cơ bản trong tính toán song parallel, nơi N bộ xử lý cùng chia xẻ bộ nhớ chung. Mô hình PRAM được chia thành bốn lớp nhỏ dựa trên khả năng đọc/ghi đồng thời trên cùng một ô nhớ. Mỗi lớp có những đặc điểm riêng ảnh hưởng đến khả năng thực hiện thuật toán song parallel. EREW (Exclusive Read, Exclusive Write) không cho phép đọc hoặc ghi đồng thời, là mô hình giới hạn nhất nhưng phổ biến nhất trong thực tế. CREW (Concurrent Read, Exclusive Write) cho phép đọc đồng thời nhưng ghi độc quyền. ERCW cho phép ghi đồng thời nhưng đọc độc quyền. CRCW (Concurrent Read, Concurrent Write) là mô hình mạnh nhất, cho phép đọc/ghi đồng thời, nhưng phức tạp và khó chế tạo. Việc lựa chọn mô hình phù hợp là quyết định quan trọng khi thiết kế thuật toán song parallel cho bài toán đồ thị.

4.1. Các lớp PRAM và khả năng đọc ghi

EREW không cho phép hai bộ xử lý đọc hoặc ghi đồng thời trên cùng một ô nhớ. CREW cho phép bộ xử lý đọc đồng thời nhưng không được phép ghi đồng thời. ERCW cho phép ghi đồng thời nhưng không được phép đọc đồng thời. CRCW cho phép tất cả các hoạt động đọc/ghi đồng thời trên một ô nhớ, nhưng đây là mô hình phức tạp nhất và cần giải quyết xung đột ghi.

4.2. Giải quyết xung đột ghi trong CRCW

Khi nhiều bộ xử lý ghi đồng thời trên cùng một ô nhớ với những giá trị khác nhau, cần giải quyết xung đột. ECR (Equality Conflict Resolution) chỉ cho phép ghi nếu tất cả giá trị giống nhau. PCR (priority Conflict Resolution) dùng chỉ số ưu tiên quyết định giá trị được ghi. ACR (arbitrary Conflict Resolution) chấp nhận bất kỳ giá trị nào, nhưng khó để triển khai. Công nghệ hiện tại thường dùng EREW vì độ khả thi cao hơn.

Trích đoạn nội dung tài liệu

Chương 1: ĐẠI CƯƠNG VỀ TÍNH TOÁN 1. Một số khái niệm và thuật ngữ Tinh toán song song hay xử lý song song : là quả trình xử lý thông tin trong đó nhân. mạnh việc nhiều đơn vị dữ liệu được xử lý đồng thời bởi một hay nhiều bộ xử lý đẻ giải quyết một bài toán. Siêu máy tính : là những máy tính đa năng thông thường cỏ tốc độ tính toán vô cùng, lớn.

Chúng chia làm hai loại - May tính song song dựa trên bộ vi xử lý : được thiết kế với rất nhiều bộ xử lý có tốc độ vừa phải. - Siéu máy tỉnh truyền thông (supercomputer) - ít bộ xử lý hơn nhưng tốc độ của mỗi bộ xử lý đó lại cực cao. Song song vẻ dữ liệu (data parallelism) : Là cơ chế sử dụng nhiều đơn vị xử lý thực hiện cùng một thao tác trên nhiều đơn vị đữ liệu. Song song dieu khien (control parallelism) : la co ché trong đó nhiều thao tác khác nhau tác động lên nhiều đơn vị đữ liệu khác nhau một cách dong thoi.

Dây chuyên (pipeline) : là cơ chẻ chia công việc thành nhiều chặng nối tiếp, môi chặng được thực hiện bởi một bộ phận khác nhau. Đầu ra của bộ phận này là đầu vào của bộ phận tiếp theo, Tăng tốc : tăng tốc của thuật toán song song là tỉ số giữa thời gian thực hiện trong, tình huồng xâu nhất của thuật toán tuân tự tốt nhát và thời gian thực hiện cũng công. việc đỏ của thuật toán song song Liên quan đến tóc độ, năm 1967 Amdahl đã nêu ra định lý sau đây 1 ĐỎ TRUNG KIÊN Chiong I’: Đại cương về tính toán song song Định lý Amdahl : Gọi ƒ lả tỷ lệ thao tác tuân tự trên tổng sỏ thao tác phải làm, trong. đỏ 0 <ƒ< 1 và § là tốc độ tối đa của một may tinh song song với p bộ xử lý khi đó ta có.

1 S<——x—+yz t+ q=#⁄ye Hiệu quả (Effieient) của thuật toán song song được tính bằng, Tốc độ / số bộ xử lý tham gia tỉnh toản Flop : Một đơn vị đo tốc độ của máy tính song song. Flop là viết tắt của floating point operating per second : số phép tính toán hạng số thực dâu phây đông thực hiện được trong một giây. Mega Mfilop/s=105flop/§ Giga — Gflop§=10” Tera — Tflop⁄s=101 Giá (cost) của một quả trình tỉnh toán trên hệ thông song song được tỉnh như sau Giá = đô phức tạp tính toán x số lượng bộ xử lý tham gia tính toán Trong đó độ phức tạp tính toản hay thời gian tỉnh chỉnh là số bước thực hiện thao tác cơ bản (với giả thiết rằng thực hiện một thao tác cơ bản tôn một đơn vị thời gian) 1. Các mức độ song song Giả sử có 10 công việc từng đôi một khác nhau thì ta giao cho 10 may lam, ta cd mức song song cao nhất, và chúng ta gọi là mức chương trình song song.

Mỗi công, việc ta lại chia thảnh các công đoạn (Task) và cỏ thẻ thực hiện song song, ta gọi mức độ song song nảy lả mức song song chương trình con. Môi chương trinh cũng, như chương trinh con lại có hàng loạt câu lệnh, ta cỏ mức độ song song câu lệnh, trong câu lệnh lại có hành loạt thao tác (operation) => mức độ song song thao tác. ĐỎ TRUNG KIÊN Chiong I’: Đại cương về tính toán song song MIMD (multiple mstruction stream, multiple data stream) : Cho phép nhiều lệnh khác nhau có thê đồng thời xử lý nhiều đữ liệu khác nhau trong củng một thời điểm. Mé hinh SIMD M6 hinh kién tric nay con duge goi la PRAM (Parallel Random Access Machine — Máy tính song song truy cập ngẫu nhiên), Trong mô hình nảy, N bộ xử lý củng chia xẻ bộ nhớ chung.

Mô hình PRAM chia thành 4 lớp nhỏ : EREW (Exclusive Read, Exclusive Write) : Độc quyền đọc, độc quyền ghi Không cho phép hai bộ xử lý đọc hoặc ghi đồng thời trên cùng một ô nhớ, CREW (Concurent Read Exclusive Write) : Đọc đồng thời, ghi độc quyền Các bộ xử lý cỏ thể đọc đồng thời, nhưng không được phép ghi đồng thời trên một ô nhở ERCW (Exclusive Read Concurent Write) : Ghi dong thời, đọc độc quyền. Các bộ xử lý có thể ghi đồng thời, nhưng không được phép đọc đồng thời trên một ö nhớ. CRCW (Coneurent Read Coneurent Write) : đọc/ghi đồng thời. Các bộ xử lý có thể đồng thời đọc ghi trên một ô nhớ.

Việc cho phép nhiều bộ xử lý đọc một ô nhớ không khó. Nhưng thiết kế câu trúc ghi đồng thời thi phức tạp hơn. Vẫn đề là ở chỗ nêu các giả trị ghi vào là khác nhau thì cuối củng trong ô nhớ sẽ lưu giả trị nảo ?. Có ba cách giải quyết : ECR (Equallity Confliet Resolution) : Chỉ thực hiện ghi nêu tất cä các bộ xử lỷ đều cùng ghi một giá trị như nhau.

PCR (priority Conflict Resolution) : Mỗi bộ xử lý có một chỉ số ưu tiên, và giá trị trên bộ xử lý có số thứ tự ưu tiên cao nhất sẽ được ghi. ACR (arbitrary Conflict Resolution) : Trong cach giải quyết này sức mạnh. của máy tính tăng dân theo thứ tự trên. Mặc dủ yêu nhất, nhưng công nghệ chế tạo phố biến hiện nay lại là các mảy EREW, còn các máy CRCW, CREW thi dat va kho chế tạo.

Do đỏ ta phải nghĩ tới việc dùng EREW đề mô phỏng các kiến trúc cỏn lại như trình bảy dưới đây. 4 ĐỎ TRUNG KIÊN Chiong I’: Đại cương về tính toán song song Định lý Amdahl : Gọi ƒ lả tỷ lệ thao tác tuân tự trên tổng sỏ thao tác phải làm, trong. đỏ 0 <ƒ< 1 và § là tốc độ tối đa của một may tinh song song với p bộ xử lý khi đó ta có. 1 S<——x—+yz t+ q=#⁄ye Hiệu quả (Effieient) của thuật toán song song được tính bằng, Tốc độ / số bộ xử lý tham gia tỉnh toản Flop : Một đơn vị đo tốc độ của máy tính song song.

Flop là viết tắt của floating point operating per second : số phép tính toán hạng số thực dâu phây đông thực hiện được trong một giây. Mega Mfilop/s=105flop/§ Giga — Gflop§=10” Tera — Tflop⁄s=101 Giá (cost) của một quả trình tỉnh toán trên hệ thông song song được tỉnh như sau Giá = đô phức tạp tính toán x số lượng bộ xử lý tham gia tính toán Trong đó độ phức tạp tính toản hay thời gian tỉnh chỉnh là số bước thực hiện thao tác cơ bản (với giả thiết rằng thực hiện một thao tác cơ bản tôn một đơn vị thời gian) 1. Các mức độ song song Giả sử có 10 công việc từng đôi một khác nhau thì ta giao cho 10 may lam, ta cd mức song song cao nhất, và chúng ta gọi là mức chương trình song song. Mỗi công, việc ta lại chia thảnh các công đoạn (Task) và cỏ thẻ thực hiện song song, ta gọi mức độ song song nảy lả mức song song chương trình con.

Môi chương trinh cũng, như chương trinh con lại có hàng loạt câu lệnh, ta cỏ mức độ song song câu lệnh, trong câu lệnh lại có hành loạt thao tác (operation) => mức độ song song thao tác. ĐỎ TRUNG KIÊN Chiong I’: Đại cương về tính toán song song 1. Ho may MIMD Trong mục trên chúng ta đã xem xét họ máy SIMD, hay còn được gọi là PRAM Sau đây chúng ta xem xét một kiến trúc song song khác — lép may MIMD, Lép nay phân làm 3 loại Hệ đa xử lý với bô nhớ phân tán. Hệ đa xử lý dùng chung bộ nhở.

Hệ đa xử lý với bộ nhớ dùng chung phân tán. Hệ đa xử lý với bộ nhớ phan tin (Multi processor system with distributed memory) Processor Processor (Bộ xử lý) (Bộ xử lý) | St T† A H' = |1 receiver) [ Local Memory |) | Local Memory’ |)! (BO nho eye BO) | Ỉ (Bộ nhớ cục bộ) Ee i | | mg DỊ i Interconmeation network ~~~ ~~~ ~~ ° (Mang lên kết) Đây chính lả hệ song song gồm nhiều máy tỉnh kết nổi thành mạng (multicomputer system) Các bộ xử lý chỉ được quyền truy nhập vùng nhớ cục bộ của mình Liên kết giữa các bộ xử lý được thực hiện theo mô hình chuyển thông bao (message passing) Hệ thống có quy mô lớn, cỏ thê lên tới hảng chục ngản bộ xử lý. Khi số bộ xử lý quá lớn có thẻ làm cho đường truyền mạng trở nên quá tải Kỹ thuật lập trình khá phúc tạp, tương ứng với các môi trường lập trình chuyển thông bảo nhu PVM, MPI Còn được gọi đưới một tên khác là hệ NORMA (no remote memory access model : mô hình không cho phép truy cập vùng nhớ ở xa). Ta thấy mỗi bộ xử lý có một vùng nhớ cục bộ riêng của mình (local memory) và chỉ được quyền 6 DO TRUNG KIÊN Chiong I’: Đại cương về tính toán song song truy nhập vảo đỏ, và nó là vùng nhớ ở xa (remote memory) đôi với các bộ xử lý khác mả chúng không được quyên truy nhập vào đây.

Hệ đa xử lý dùng chung bộ nhớ (Multi processor system with shared memory) -_ Đây là máy tính lớn với nhiều bộ xử lý (multi processor) hoạt động theo cơ chế đa xử lý déi xtmg SMP (Symmetric multi processing) - Céc bé xi ly c6 thé truy cap toản bộ vùng nhớ đủng chung Processor Processor (Bổ sở lý) (80 xử lý) | Interconnection network (Mang liên kế!) amos ‘Shared Memory | -_ Liên lạc giữa các bô xử lý được thực hiện thông qua vùng nhở đủng chung. Giả sử bộ xử lý P: muốn gửi dữ liêu cho P, dữ liêu đó sẽ được ghi vào vùng nhớ đủng chung rỏi báo địa chỉ cho Pa. Pz sẽ đọc tại địa chỉ đó lẫy dữ liệu về ~_ Qui mô của hệ thống tương đổi nhỏ, chỉ cỡ vải trăm bộ xử lý -_ Kỹ thuật lập trình để đảng hơn so với mô hình trên. ~_ Còn được gọi dưới một tên khác là UMA (uniform memory access model : quản lý vả đánh địa chỉ toàn bộ vùng nhớ đủng chung theo một dạng địa chỉ thống nhâÐ.

Ta sẽ thấy hệ NƯMA dưới đây tuy cũng quản lý được toàn bộ vùng nhở dùng chung nhưng không đủng một mả dùng nhiều dạng địa chỉ. Hệ đa xử lý với bộ nhớ dùng chung phân tán (Multi processor system with distributed shared memory) 7 DO TRUNG KIEN Chiong I’: Đại cương về tính toán song song truy nhập vảo đỏ, và nó là vùng nhớ ở xa (remote memory) đôi với các bộ xử lý khác mả chúng không được quyên truy nhập vào đây.