Link tải luận văn miễn phí cho ae Kết Nối
MỤC LỤC
MỤC LỤC 1
A. MỞ ĐẦU 2
B. NỘI DUNG 3
I. Những khái niệm cơ bản về tính toán song song 3
1. Nhu cầu tính toán hiệu năng cao và tính khả dụng của tính toán song song. 3
2. Những khái niệm cơ bản: 6
II. Lập trình song song với OPENMP 8
1. OpenMP: Open specifications for Multi Processing 8
2. Mô hình song song OpenMP: 9
3. Viết chương trình song song với OpenMp 10
4. Các hàm OpenMP 11
III. Ứng dụng vào bài toán “Connected component” 14
1. Phân tích bài toán 14
2. Mô tả thuật toán 16
3. Code 17
4. Hướng dẫn sử dụng: 21
C. KẾT LUẬN 24
TÀI LIỆU THAM KHẢO 25
A. MỞ ĐẦU
Bốn thập kỷ qua chứng kiến sự phát triển bùng nổ về sức mạnh máy tính, tạo tiền đề cho những bước tiến chưa từng thấy về phát minh, năng suất lao động và phúc lợi cho con người. Nhưng quá trình đó giờ đây đứng trước một trở ngại mà ít ai nghĩ đến: sự kết thúc của quá trình mở rộng sức mạnh điện toán. Ngành tin học đã đạt đến giới hạn của những gì từng khả thi với một hay hai vi xử lý trung tâm hoạt động theo chuỗi truyền thống (serial processing). Ngành nào vẫn dựa vào mô hình đó để tiếp tục phát triển năng suất, tăng trưởng kinh tế và phát triển xã hội thì cần bắt đầu một bước nhảy mới vào điện toán xử lý song song (parallel processing).
Năm 1965, nhà đồng sáng lập hãng Intel là Gordon Moore đăng một bài viết trong đó dự báo số bóng bán dẫn transistor trên mạch tích hợp sẽ tăng gấp đôi mỗi năm (về sau điều chỉnh lại là "tăng gấp đôi theo chu kỳ 18 tháng"), sau này được biết đến là “định luật MORE”. Tuy nhiên với sự phát triển như vũ bão của công nghệ, và sự hạn chế của kỹ thuật, lượng transistor không còn tăng được nữa, tính quy mô của định luật MORE không còn. Đã đến lúc cần 1 giải pháp khác cho sự phát triển của công nghệ điện toán. Và điện toán song song sẽ có thể đem đến một nền tảng phát triển mới. Định luật MORE đã chết, bây giờ là thời kỳ của tính toán song song.
Minh họa một cách đơn giản, tính toán truyền thống giống như việc một người đọc bài văn theo kiểu tuần tự từ đầu đến cuối, còn tính toán song song thì giống như tách bài văn đó thành các phần và cho nhiều người khác nhau cùng đọc một lúc để có kết quả nhanh hơn. Tính toán song song mang lại một nền tảng mới cho sự phát triển của công nghệ xử lý. Đây là một hướng đi mới, đúng đắn và hiệu quả cho công nghệ điện toán trong tương lai. Bài viết sau đây về đề tài “Tìm hiểu về tính toán song song , áp dụng giải quyết một số bài toán” phần nào thể hiện được những kiến thức cơ bản đầu tiên về tính toán song song, tính đúng đắn và ứng dụng của nó.
B. NỘI DUNG
I. Những khái niệm cơ bản về tính toán song song
1. Nhu cầu tính toán hiệu năng cao và tính khả dụng của tính toán song song.
a. Nhu cầu tính toán song song
Ví dụ 1: Oregon State University:
– Mô phỏng các dòng chảy lưu thông của đại dương -> xác định nguyên nhân gây trái đất đang nóng dần lên.
– Phân chia đại dương thành:
• 4096 vùng từ đông sang tây.
• 1024 vùng từ bắc sang nam.
• 12 tầng biển.
• Xấp sỉ 50 triệu khối trong không gian 3 chiều.
– Mô phỏng lưu thông thực hiện ~ 30 tỷ phép tính trong 10 phút. Công việc này thực hiện liên tục trong năm.
Ví dụ 2: Dự báo thời tiết (weather forecasting):
– Chia bầu khí quyển theo không gian 3 chiều, mỗi khối kích thước 1mile x 1mile x 1mile.
– Ước tính khoảng 5x10^8 khối (cells).
– Trên mỗi khối cần thực hiện ~ 200 phép toán -> cần thực hiện ~ 10^11 phép toán.
– Nếu cần dự báo cho 1 tuần, chu kỳ 1 phút -> cần thực hiện 10^4 lần, mỗi lần 10^11phép toán.
– Siêu máy tính có thể thực hiện: 10^9 phép toán trên 1 giây -> cần 10^6 giây ~ 10 ngày để thực hiện.
Ví dụ 3: Mô phỏng tương tác của các protein với phân tử nước (Levin 1990):
– Thực hiện trên máy Cray X/MP (~800 triệu phép toán / 1 giây): để mô phỏng 10^-12 giây phản ứng protein cần 1 giờ thực hiện.
– Nếu mô phỏng một phản ứng thực sự trên cùng máy Cray X/MP cần 31,688 năm.
TÓM LẠI:
Yêu cầu về thực nghiệm nghiên cứu, mô phỏng -> giải quyết những bài toán có khối lượng tính toán lớn trong một khoảng thời gian chấp nhận được.
Phương hướng giải quyết vấn đề:
– Thực hiện trên các siêu máy tính mạnh.
– Thực hiện phân chia công việc thực hiện song song trên hệ thống các máy tính
b. Tính khả dụng của tính toán song song
SIÊU MÁY TÍNH: Khả năng tính toán phụ thuộc nhiều vào tốc độ xử lý của CPU -> phụ thuộc vào cấu trúc và số lượng transistors chứa trong CPU –> Có những giới hạn nhất định về kích thước, nhiệt độ -> không thể tăng số transistors lên mãi được
THỰC HIỆN SONG SONG:
• Nguyên tắc: thực hiện phân chia công việc chính thành các công việc con, có thể thực hiện song song với nhau.
• Xây dựng hệ thống song song từ nhiều bộ xử lý riêng biệt. Thực hiện các công việc song song trên các bộ xử lý đó.
• Vấn đề:
– Phương pháp phân chia công việc.
– Môi trường hỗ trợ thực hiện song song.
Ví dụ: Xếp sách trong thư viện
• Sách trong thư viện được phân loại theo chữ cái đầu tiên và sắp xếp theo thứ tự.
• Sách cùng nhóm được xếp trên cùng một giá. Các giá đặt trong các tủ sách.
• Thư viện nhập một số lượng sách lớn -> yêu cầu thủ thư phải sắp xếp sách theo đúng nguyên tắc.
• Cách giải quyết hiệu quả nhất?
Nếu chỉ có 1 thủ thư
• Cách thứ nhất: Lấy từng cuốn sách rồi sắp xếp vào vị trí thích hợp ->không hiệu quả.
• Cách thứ hai: Sắp xếp các cuốn sách theo thứ tự trước rồi mang từng chồng sách cùng vị trí đi sắp xếp.
• Rõ ràng cách thứ 2 hiệu quả hơn.
• Muốn hiệu quả hơn nữa thì cần có nhiều người làm hơn.
Nhiều thủ thư hơn
• Cách thứ nhất: Mỗi người lấy 1 cuốn rồi đi sắp đặt vị trí -> không hiệu quả.
• Cách thứ hai: Phân chia mỗi người một nhóm ký tự, khi đó mỗi người chỉ mang sách thuộc nhóm mình đi sắp xếp.
• Cách thứ ba: Sắp xếp sách trước khi mang đi đặt vị trí. Mỗi người đảm nhận một số ký tự:
– Nếu cuốn sách đang cầm của mình thì đặt vào chồng sách của mình.
– Nếu của người khác thì chuyển cho người đấy.
– Sau đó mang sách đi sắp xếp.
->cách thứ ba hiệu quả nhất.
Ý nghĩa của tính toán song song
• Thực hiện công việc trong khoảng thời gian ngắn hơn -> tiết kiệm thời gian.
• Thực hiện được với số lượng phép toán lớn hơn -> giải quyết được bài toán lớn.
• Hỗ trợ giải quyết nhiều công việc đồng thời.
2. Những khái niệm cơ bản:
• Task: là một công việc cần thực hiện.
• Parallel Task: công việc cần thực hiện song song.
• Serial Execution: thực hiện tuần tự.
• Parallel Execution: thực hiện song song.
• Shared Memory: bộ nhớ dùng chung.
• Distributed Memory: bộ nhớ phân tán.
• Communication: sự liên lạc, trao đổi thông tin
giữa các chương trình chạy song song.
• Synchronization: sự đồng bộ hóa trong thựchiện song song
• Flops (floating point operation per second) là số phép toán thực hiện trên một giây.
• Rpeak: là khả năng tính toán tối đa của siêu máy tính do nhà sản xuất công bố.
• Rmax: là khả năng thực tế của siêu máy tính được xác định thông qua các phần mềm kiểm định.
• Ví dụ: 1 máy tính có CPU 1GHz, DRAM có thời gian truy
nhập dữ liệu là 100ns, giả sử CPU thực hiện 1 lệnh/1ns khi đó:
– Theo lý thuyết: Rpeak = 10^9flops. (1ns = 10^-9s)
a. Đồ thị và thành phần liên thông
Đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh và E là tập các cặp không có thứ tự gồm 2 phần tử khác nhau của V gọi là các cạnh
Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G
Đồ thị vô hướng G được gọi là liên thông nếu luôn tìm được đường đi giãu 2 đỉnh bất kỳ của nó. Đối với các đồ thị không liên thông, các đồ thị con liên thông của nó được gọi là các thành phần liên thông cảu đồ thị.
Xét đồ thị G=(V,E) có n đỉnh. Ma trận A[n][n] với A[j]=1 nếu (i,j) là cạch của đồ thị, ngược lại A[j]=0, được gọi là ma trận kề của đồ thị.
b. Tìm kiếm theo chiều sâu(DFS) và ứng dụng tìm thành phần liên thông của đồ thị:
Tư tưởng của tìm kiếm theo chiều sâu: “Đi sâu nhất có thể, nếu không được thì quay lại”
Thủ tục tìm kiếm theo chiều sâu là một thủ tục đệ quy. Ta sẽ tìm kiếm từ một đỉnh s nào đó của đồ thi. Sau đó chọn u trong số các đỉnh kề của s và lặp lại quá trình đó. Nếu trong các đỉnh kề của đỉnh s tìm được đỉnh chưa thăm thì thực hiện thủ tục DFS với đỉnh đó. Nếu không tìm được thì s được duyệt xong, quay trở lại tìm kiếm tiếp tục với đỉnh xét trước s.
Do thủ tục DFS(s) cho phép thăm tất cả các đỉnh thuộc thành phần liên thông với s nên số thành phần liên thông của đồ thị chính bằng số lần gọi đến thủ tục DFS.
1. Mô tả thuật toán
Như đã trình bày ở trên, ta ứng dụng thủ tục DFS kết hợp với các chỉ thị song song để tìm thành phần liên thông trong đồ thị. Ý tưởng là chia nhỏ đồ thị thành từng phần nhỏ tiến hành DFS mỗi phần trên một luồng rồi tổng hợp dữ liệu đưa ra kết quả. Cụ thể ta chia ma trận kề của đồ thị thành p phần tương ứng với p luồng dữ liệu (p bộ xử lý).Tiến hành thủ tục DFS ở mỗi phần. Dùng hàm Union(x,y) để tổng hợp dữ liệu.
Ví dụ: Ta có đồ thị như hình vẽ và 2 bộ xử lý. Chia dữ liệu như hình vẽ cho 2 bộ xử lý thực hiện DFS.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
MỤC LỤC
MỤC LỤC 1
A. MỞ ĐẦU 2
B. NỘI DUNG 3
I. Những khái niệm cơ bản về tính toán song song 3
1. Nhu cầu tính toán hiệu năng cao và tính khả dụng của tính toán song song. 3
2. Những khái niệm cơ bản: 6
II. Lập trình song song với OPENMP 8
1. OpenMP: Open specifications for Multi Processing 8
2. Mô hình song song OpenMP: 9
3. Viết chương trình song song với OpenMp 10
4. Các hàm OpenMP 11
III. Ứng dụng vào bài toán “Connected component” 14
1. Phân tích bài toán 14
2. Mô tả thuật toán 16
3. Code 17
4. Hướng dẫn sử dụng: 21
C. KẾT LUẬN 24
TÀI LIỆU THAM KHẢO 25
A. MỞ ĐẦU
Bốn thập kỷ qua chứng kiến sự phát triển bùng nổ về sức mạnh máy tính, tạo tiền đề cho những bước tiến chưa từng thấy về phát minh, năng suất lao động và phúc lợi cho con người. Nhưng quá trình đó giờ đây đứng trước một trở ngại mà ít ai nghĩ đến: sự kết thúc của quá trình mở rộng sức mạnh điện toán. Ngành tin học đã đạt đến giới hạn của những gì từng khả thi với một hay hai vi xử lý trung tâm hoạt động theo chuỗi truyền thống (serial processing). Ngành nào vẫn dựa vào mô hình đó để tiếp tục phát triển năng suất, tăng trưởng kinh tế và phát triển xã hội thì cần bắt đầu một bước nhảy mới vào điện toán xử lý song song (parallel processing).
Năm 1965, nhà đồng sáng lập hãng Intel là Gordon Moore đăng một bài viết trong đó dự báo số bóng bán dẫn transistor trên mạch tích hợp sẽ tăng gấp đôi mỗi năm (về sau điều chỉnh lại là "tăng gấp đôi theo chu kỳ 18 tháng"), sau này được biết đến là “định luật MORE”. Tuy nhiên với sự phát triển như vũ bão của công nghệ, và sự hạn chế của kỹ thuật, lượng transistor không còn tăng được nữa, tính quy mô của định luật MORE không còn. Đã đến lúc cần 1 giải pháp khác cho sự phát triển của công nghệ điện toán. Và điện toán song song sẽ có thể đem đến một nền tảng phát triển mới. Định luật MORE đã chết, bây giờ là thời kỳ của tính toán song song.
Minh họa một cách đơn giản, tính toán truyền thống giống như việc một người đọc bài văn theo kiểu tuần tự từ đầu đến cuối, còn tính toán song song thì giống như tách bài văn đó thành các phần và cho nhiều người khác nhau cùng đọc một lúc để có kết quả nhanh hơn. Tính toán song song mang lại một nền tảng mới cho sự phát triển của công nghệ xử lý. Đây là một hướng đi mới, đúng đắn và hiệu quả cho công nghệ điện toán trong tương lai. Bài viết sau đây về đề tài “Tìm hiểu về tính toán song song , áp dụng giải quyết một số bài toán” phần nào thể hiện được những kiến thức cơ bản đầu tiên về tính toán song song, tính đúng đắn và ứng dụng của nó.
B. NỘI DUNG
I. Những khái niệm cơ bản về tính toán song song
1. Nhu cầu tính toán hiệu năng cao và tính khả dụng của tính toán song song.
a. Nhu cầu tính toán song song
Ví dụ 1: Oregon State University:
– Mô phỏng các dòng chảy lưu thông của đại dương -> xác định nguyên nhân gây trái đất đang nóng dần lên.
– Phân chia đại dương thành:
• 4096 vùng từ đông sang tây.
• 1024 vùng từ bắc sang nam.
• 12 tầng biển.
• Xấp sỉ 50 triệu khối trong không gian 3 chiều.
– Mô phỏng lưu thông thực hiện ~ 30 tỷ phép tính trong 10 phút. Công việc này thực hiện liên tục trong năm.
Ví dụ 2: Dự báo thời tiết (weather forecasting):
– Chia bầu khí quyển theo không gian 3 chiều, mỗi khối kích thước 1mile x 1mile x 1mile.
– Ước tính khoảng 5x10^8 khối (cells).
– Trên mỗi khối cần thực hiện ~ 200 phép toán -> cần thực hiện ~ 10^11 phép toán.
– Nếu cần dự báo cho 1 tuần, chu kỳ 1 phút -> cần thực hiện 10^4 lần, mỗi lần 10^11phép toán.
– Siêu máy tính có thể thực hiện: 10^9 phép toán trên 1 giây -> cần 10^6 giây ~ 10 ngày để thực hiện.
Ví dụ 3: Mô phỏng tương tác của các protein với phân tử nước (Levin 1990):
– Thực hiện trên máy Cray X/MP (~800 triệu phép toán / 1 giây): để mô phỏng 10^-12 giây phản ứng protein cần 1 giờ thực hiện.
– Nếu mô phỏng một phản ứng thực sự trên cùng máy Cray X/MP cần 31,688 năm.
TÓM LẠI:
Yêu cầu về thực nghiệm nghiên cứu, mô phỏng -> giải quyết những bài toán có khối lượng tính toán lớn trong một khoảng thời gian chấp nhận được.
Phương hướng giải quyết vấn đề:
– Thực hiện trên các siêu máy tính mạnh.
– Thực hiện phân chia công việc thực hiện song song trên hệ thống các máy tính
b. Tính khả dụng của tính toán song song
SIÊU MÁY TÍNH: Khả năng tính toán phụ thuộc nhiều vào tốc độ xử lý của CPU -> phụ thuộc vào cấu trúc và số lượng transistors chứa trong CPU –> Có những giới hạn nhất định về kích thước, nhiệt độ -> không thể tăng số transistors lên mãi được
THỰC HIỆN SONG SONG:
• Nguyên tắc: thực hiện phân chia công việc chính thành các công việc con, có thể thực hiện song song với nhau.
• Xây dựng hệ thống song song từ nhiều bộ xử lý riêng biệt. Thực hiện các công việc song song trên các bộ xử lý đó.
• Vấn đề:
– Phương pháp phân chia công việc.
– Môi trường hỗ trợ thực hiện song song.
Ví dụ: Xếp sách trong thư viện
• Sách trong thư viện được phân loại theo chữ cái đầu tiên và sắp xếp theo thứ tự.
• Sách cùng nhóm được xếp trên cùng một giá. Các giá đặt trong các tủ sách.
• Thư viện nhập một số lượng sách lớn -> yêu cầu thủ thư phải sắp xếp sách theo đúng nguyên tắc.
• Cách giải quyết hiệu quả nhất?
Nếu chỉ có 1 thủ thư
• Cách thứ nhất: Lấy từng cuốn sách rồi sắp xếp vào vị trí thích hợp ->không hiệu quả.
• Cách thứ hai: Sắp xếp các cuốn sách theo thứ tự trước rồi mang từng chồng sách cùng vị trí đi sắp xếp.
• Rõ ràng cách thứ 2 hiệu quả hơn.
• Muốn hiệu quả hơn nữa thì cần có nhiều người làm hơn.
Nhiều thủ thư hơn
• Cách thứ nhất: Mỗi người lấy 1 cuốn rồi đi sắp đặt vị trí -> không hiệu quả.
• Cách thứ hai: Phân chia mỗi người một nhóm ký tự, khi đó mỗi người chỉ mang sách thuộc nhóm mình đi sắp xếp.
• Cách thứ ba: Sắp xếp sách trước khi mang đi đặt vị trí. Mỗi người đảm nhận một số ký tự:
– Nếu cuốn sách đang cầm của mình thì đặt vào chồng sách của mình.
– Nếu của người khác thì chuyển cho người đấy.
– Sau đó mang sách đi sắp xếp.
->cách thứ ba hiệu quả nhất.
Ý nghĩa của tính toán song song
• Thực hiện công việc trong khoảng thời gian ngắn hơn -> tiết kiệm thời gian.
• Thực hiện được với số lượng phép toán lớn hơn -> giải quyết được bài toán lớn.
• Hỗ trợ giải quyết nhiều công việc đồng thời.
2. Những khái niệm cơ bản:
• Task: là một công việc cần thực hiện.
• Parallel Task: công việc cần thực hiện song song.
• Serial Execution: thực hiện tuần tự.
• Parallel Execution: thực hiện song song.
• Shared Memory: bộ nhớ dùng chung.
• Distributed Memory: bộ nhớ phân tán.
• Communication: sự liên lạc, trao đổi thông tin
giữa các chương trình chạy song song.
• Synchronization: sự đồng bộ hóa trong thựchiện song song
• Flops (floating point operation per second) là số phép toán thực hiện trên một giây.
• Rpeak: là khả năng tính toán tối đa của siêu máy tính do nhà sản xuất công bố.
• Rmax: là khả năng thực tế của siêu máy tính được xác định thông qua các phần mềm kiểm định.
• Ví dụ: 1 máy tính có CPU 1GHz, DRAM có thời gian truy
nhập dữ liệu là 100ns, giả sử CPU thực hiện 1 lệnh/1ns khi đó:
– Theo lý thuyết: Rpeak = 10^9flops. (1ns = 10^-9s)
a. Đồ thị và thành phần liên thông
Đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh và E là tập các cặp không có thứ tự gồm 2 phần tử khác nhau của V gọi là các cạnh
Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G
Đồ thị vô hướng G được gọi là liên thông nếu luôn tìm được đường đi giãu 2 đỉnh bất kỳ của nó. Đối với các đồ thị không liên thông, các đồ thị con liên thông của nó được gọi là các thành phần liên thông cảu đồ thị.
Xét đồ thị G=(V,E) có n đỉnh. Ma trận A[n][n] với A[j]=1 nếu (i,j) là cạch của đồ thị, ngược lại A[j]=0, được gọi là ma trận kề của đồ thị.
b. Tìm kiếm theo chiều sâu(DFS) và ứng dụng tìm thành phần liên thông của đồ thị:
Tư tưởng của tìm kiếm theo chiều sâu: “Đi sâu nhất có thể, nếu không được thì quay lại”
Thủ tục tìm kiếm theo chiều sâu là một thủ tục đệ quy. Ta sẽ tìm kiếm từ một đỉnh s nào đó của đồ thi. Sau đó chọn u trong số các đỉnh kề của s và lặp lại quá trình đó. Nếu trong các đỉnh kề của đỉnh s tìm được đỉnh chưa thăm thì thực hiện thủ tục DFS với đỉnh đó. Nếu không tìm được thì s được duyệt xong, quay trở lại tìm kiếm tiếp tục với đỉnh xét trước s.
Do thủ tục DFS(s) cho phép thăm tất cả các đỉnh thuộc thành phần liên thông với s nên số thành phần liên thông của đồ thị chính bằng số lần gọi đến thủ tục DFS.
1. Mô tả thuật toán
Như đã trình bày ở trên, ta ứng dụng thủ tục DFS kết hợp với các chỉ thị song song để tìm thành phần liên thông trong đồ thị. Ý tưởng là chia nhỏ đồ thị thành từng phần nhỏ tiến hành DFS mỗi phần trên một luồng rồi tổng hợp dữ liệu đưa ra kết quả. Cụ thể ta chia ma trận kề của đồ thị thành p phần tương ứng với p luồng dữ liệu (p bộ xử lý).Tiến hành thủ tục DFS ở mỗi phần. Dùng hàm Union(x,y) để tổng hợp dữ liệu.
Ví dụ: Ta có đồ thị như hình vẽ và 2 bộ xử lý. Chia dữ liệu như hình vẽ cho 2 bộ xử lý thực hiện DFS.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: