Tài liệu tham khảo công nghệ thông tin Nghiên cứu tính toán lưới và thử nghiệm một số thuật toán lý thuyết đồ thị
Giới thiệu
Các khái niệm
Vào đầu thập niên 90, nhiều nhóm nghiên cứu đã khai thác tài nguyên tính toán phân tán trên Internet, sử dụng hàng trăm máy trạm cho các chương trình song song như thiết kế phân tử và đồ họa máy tính Đồng thời, các nhóm khác đã kết hợp các siêu máy tính lớn thành một siêu máy tính ảo, phân phối ứng dụng lớn qua mạng diện rộng, như mô phỏng tương tác giữa chất lỏng và cánh quạt tàu Những dự án này đã chỉ ra tiềm năng to lớn của mạng máy tính, cùng với cơ sở phần mềm và công nghệ thông tin để phát triển hơn nữa.
Hệ thống đa bộ xử lý (Multiprocessor Systems - MPs), Cluster và Grids là những ví dụ tiêu biểu của kiến trúc tính toán phân tán Trong các hệ thống MPs, các bộ xử lý được kết nối chặt chẽ thông qua bộ nhớ chia sẻ chung và các đường truyền kết nối, tạo nên hiệu suất cao và khả năng xử lý đồng thời.
Cluster là các máy tính đơn hoặc đa bộ xử lý được kết hợp qua mạng, dẫn đến tốc độ chậm hơn từ 1 đến 2 lần so với kết nối MP Ví dụ, cluster Beowulf chạy Linux và TCF (Technical Compute Farm) của Sun với hệ điều hành Solaris/TM, thường được sử dụng cho các tính toán lớn Chúng phân phối các tác vụ tính toán không song song cho các bộ xử lý và thu thập kết quả vào kết quả toàn cục Các ứng dụng của cluster bao gồm hiển thị hàng ngàn khung hình cho phim, giả lập kiểm tra và thiết kế chip VLSI thế hệ tiếp theo, cũng như cắt lớp hàng trăm ngàn chuỗi gen trong công nghệ sinh học.
Grid điện toán khác biệt với các hệ thống MPs và Cluster đơn giản, vì nó bao gồm nhiều cluster của mạng MPs và/hoặc cluster trải rộng trên nhiều domain khác nhau Các grid này thường được phân bố ở nhiều phòng ban, xí nghiệp hoặc thậm chí trên mạng Internet Điều này dẫn đến độ phức tạp cao hơn trong việc thực thi, quản lý và sử dụng tài nguyên tính toán phân tán, đặc biệt ở tầng trung gian Ở tầng ứng dụng, việc thiết kế, phát triển và chạy phần mềm để triển khai grid một cách hiệu quả cũng trở nên quan trọng hơn.
Grid là kiến trúc tính toán phân tán cho phép chuyển giao tài nguyên lưu trữ và tính toán như dịch vụ trên Internet, đánh dấu bước phát triển mới trong cơ sở hạ tầng kỹ thuật Nó kết nối máy tính, thiết bị lưu trữ, thiết bị di động, công cụ, cơ sở dữ liệu và ứng dụng phần mềm, tạo điều kiện cho việc tính toán, trao đổi thông tin và hợp tác Một số hệ thống grid hiện tại bao gồm NASA Information Power Grid (IPG), DoD Distance Computing, NetSolve cho phần mềm toán học, Nimrod cho chia sẻ tài nguyên trong trường học, SETI@Home cho tìm kiếm trí thông minh ngoài trái đất, và APGrid kết nối các trung tâm máy tính tại vành đai Châu Á Thái Bình Dương.
Grid là một hạ tầng phần cứng và phần mềm cung cấp truy cập linh hoạt, toàn diện và tiết kiệm chi phí vào khả năng tính toán Trong tương lai gần, grid sẽ được sử dụng rộng rãi bởi kỹ sư, nhà khoa học, tổ chức giáo dục và nhiều đối tượng khác cho các mục đích như tính toán theo yêu cầu, xử lý thông tin nhạy cảm, tính toán cộng tác và siêu tính toán, dựa trên nhu cầu của khách hàng và nhà cung cấp.
Hiện nay, chúng ta chứng kiến những nỗ lực đầu tiên trong việc khai thác hệ thống các nguồn tài nguyên tính toán lưới trên Internet thông qua các dự án peer-to-peer computing như SETI@home, Distributed.Net và Folderol Những dự án này cho phép người dùng tải xuống dữ liệu khoa học, thực hiện xử lý trên máy cá nhân và gửi kết quả về cơ sở dữ liệu trung tâm Gần đây, một dự án tại trường đại học mang tên Compute Power Market đã được phát triển nhằm xây dựng các kỹ thuật phần mềm cho phép tạo lập các Grid, nơi mọi người có thể mua hoặc bán khả năng tính toán tương tự như cách sử dụng tài nguyên khác.
Những thách thức đối với tính toán lưới
Các kỹ thuật phức tạp cho Grid hiện nay vẫn đang được phát triển, với các môi trường mẫu như Globus và Legion Đồ án EcoGrid nghiên cứu quản lý tài nguyên, trong khi các khối xây dựng tương tự đã có trong phần mềm thương mại Sun Grid Engine.
Diễn đàn Grid (GGF – Global Grid Forum), được thành lập vào năm
Năm 1998, hàng trăm nhà khoa học đã được tập hợp để nghiên cứu và thảo luận về một kiến trúc Grid chung, mặc dù vẫn còn tồn tại một số thách thức cần được giải quyết.
• Phát triền phần mềm ứng dụng cho Grid
• Chỉ ra và truy cập các nguồn tài nguyên tính toán thích hợp trên môi trường phân tán
• Định nghĩa những giao tiếp chuẩn cho phép giao tiếp giữa các khối Grid với nhau, nhằm đáp ứng nhu cầu phát triển ứng dụng
• Bảo đảm các truy cập được xác nhận và truyền dữ liệu an toàn
• Cung cấp các dịch vụ cho phép theo dõi, quảng cáo và kết xuất báo cáo
• Thiết kế các nghi thức mạng cho việc trao đổi và định dạng thông điệp.
Tính toán song song và phân bố
Khái niệm
Trong bối cảnh công nghệ phát triển nhanh chóng, nhu cầu về tốc độ tính toán của hệ thống máy tính ngày càng gia tăng Các lĩnh vực như mô hình số và giả lập trong khoa học và công nghệ đòi hỏi hiệu suất tính toán cao để đáp ứng các yêu cầu ngày càng phức tạp.
Ngoài ra nó còn nhằm giải quyết các lọai vấn đề cần tốc độ xử lý cao như:
• Mô hình hóa và giả lập
Mô hình các mẫu DNA
Mô hình hóa chuyển động của các phi hành gia
• Xử lý/Thao tác trên các dữ liệu rất lớn
Xử lý ảnh và tín hiệu
Khai thác dữ liệu và cơ sở dữ liệu
• Các vấn đề “grand challenge” (là những vấn đề không thể giải quyết trong thời gian “hợp lý”, như cần 100, 1000,…năm để có đáp án)
Sự chuyển động của chất lỏng
Mô hình chất bán dẫn
Xuất phát từ nhu cầu đó đã dẫn đến sự cần thiết phải có những hệ thống
Nền tảng tính toán song song và phân bố
Trong phần này, chúng ta sẽ khám phá cách tổ chức logic và vật lý của các nền tảng song song và phân tán Cách tổ chức logic phản ánh quan điểm của lập trình viên về kiến trúc xử lý song song và phân bố, trong khi cách tổ chức vật lý đề cập đến cấu trúc thực tế của phần cứng Trong tính toán song song, từ góc độ lập trình viên, có hai thành phần quan trọng: cách thể hiện các tác vụ song song thông qua cấu trúc điều khiển và các phương pháp xác định tương tác giữa các tác vụ qua mô hình giao tiếp.
2.2.1 Kiến trúc xử lý song song và phân bố
Máy tính song song được chia thành hai loại chính: dòng điều khiển và dòng dữ liệu Dòng điều khiển dựa trên nguyên tắc của máy tính Von Neumann, cho phép nhiều dòng điều khiển thực hiện đồng thời Ngược lại, dòng dữ liệu, hay còn gọi là "phi Von Neumann", không sử dụng con trỏ để chỉ vào các chỉ thị hiện hành hay trung tâm điều khiển Bài viết này sẽ tập trung vào máy tính song song dòng điều khiển.
Năm 1966, M.J.Flynn đã phân chia các hệ thống máy tính dựa trên dòng chỉ thị và dòng điều khiển thành 4 loại sau:
• SISD (Single Instruction stream, a Single Data stream)
• SIMD (Single Instruction stream, Multiple Data streams)
• MISD (Multiple Instruction streams, a Single Data stream)
• MIMD (Multiple Instruction streams, Multiple Data streams)
Phân theo mức độ hay được sử dụng:
Ins truct ion Stre am (s) SISD
Globa l Di st rib u te d Me mory
Hình 2-1 : Phân lọai hệ thống máy tính theo Flynn-Johnson
Kiến trúc SISD tương tự như kiến trúc Von Neumann, trong đó một đơn vị điều khiển nhận chỉ thị từ bộ nhớ, chuyển giao cho bộ xử lý để thực thi trên đơn vị dữ liệu được chỉ định Cuối cùng, kết quả được đưa trở lại bộ nhớ.
Hầu hết các máy tính song song ban đầu được thiết kế theo kiến trúc SIMD, trong đó một đơn vị xử lý trung tâm thực hiện việc thông dịch và quảng bá Kiến trúc SIMD giúp người dùng dễ dàng lập trình ứng dụng và tối ưu hóa hiệu suất của các thiết bị phần cứng.
Hình 2-3 : Kiến trúc SIMD Bên trong SIMD, tồn tại hai lựa chọn thiết kế cơ bản sau:
1 SIMD đồng bộ và bất đồng bộ Trong một máy SIMD, từng bộ xử lý có thể thực thi hay bỏ qua các chỉ thị được quảng bá dựa vào trạng thái cục bộ của nó hay những điều kiện phụ thuộc vào dữ liệu Tuy nhiên điều này có thể dẫn đến xử lý một vài tính toán điều kiện không hiệu quả Một cách giải quyết khả thi là sử dụng phiên bản bất đồng bộ của S1IMD, được biết đến là SPMD (Single Program chương trình chung Điểm thuận lợi của SPMD là trong lúc tính toán biểu thức điều kiện “if-then-else”, từng bộ xử lý sẽ chỉ thực hiện ở nhánh thích hợp mà không mất thời gian cho các chi phí tính toán khác.
2 Chip SIMD tùy chọn hay thống nhất (commodity) Một máy SIMD có thể được thiết kế dựa trên những thành phần thống nhất hay là từ những con chip tùy chọn Trong cách tiếp cận thứ nhất thì các thành phần có xu hướng rẻ hơn do sản xuất hàng loạt Tuy nhiên những thành phần mang mục đích chung như vậy có thể chứa các yếu tố không cần thiết cho một thiết kế cụ thể nào đó Những thành phần thêm vào có thể làm phức tạp việc thiết kế, sản xuất và kiểm thử các máy SIMD và cũng có thể đem lại khiếm khuyết về tốc độ xử lý Còn các thành phần tùy chọn thì nhìn chung hỗ trợ tốt hơn cho thực thi tuy nhiên nó cũng dẫn đến chi phí cao hơn cho việc phát triển Khi việc tích hợp nhiều bộ xử lý cùng với bộ nhớ dư dật trên một con chip VLSI đơn trở nên khả thi, thì việc kết hợp ưu điểm của
2 cách tiếp cận trên là hoàn toàn có thể.
Mô hình MISD (Multiple Instruction, Single Data) ít được sử dụng trong các ứng dụng do khó khăn trong việc áp dụng vào kiến trúc này Việc thiết kế một kiến trúc MISD để phục vụ cho nhiều mục đích chung là điều không khả thi Tuy nhiên, các bộ xử lý song song theo kiểu MISD vẫn có thể được áp dụng hiệu quả trong những ứng dụng cụ thể.
Kiến trúc MISD (Multiple Instruction, Single Data) là một mô hình xử lý song song trong đó một dòng dữ liệu duy nhất được đưa vào một máy tính có 5 bộ xử lý Mỗi bộ xử lý thực hiện nhiều phép biến đổi khác nhau trên cùng một đơn vị dữ liệu trước khi nó được chuyển đến một hoặc nhiều bộ xử lý khác Các đơn vị dữ liệu tiếp theo có thể trải qua các phép biến đổi khác nhau nhờ vào tính độc lập dữ liệu của các dòng chỉ thị hoặc các thẻ điều khiển đặc biệt đi kèm với dữ liệu Do đó, kiến trúc MISD có thể được coi là một hệ thống ống lệnh phức tạp với nhiều đường dẫn, trong đó từng giai đoạn xử lý có thể được lập trình độc lập.
2.2.1.4 MIMD Được tiên đoán bởi các doanh nghiệp vào thập niên 90, mô hình MIMD gần đây đã trở nên khá phổ biến Lý do cho sự thay đổi này là vì tính uyển chuyển cao của kiến trúc MIMD và bởi khả năng tận dụng được những ưu điểm của các bộ vi xử lý được sản xuất hàng lọat (commodity microprocessors), vì thế tránh được những vòng phát triển dài dòng và qua đó có thể được phát triển cùng với sự cải thiện của các bộ xử lý Các máy tính MIMD được áp dụng rất hiệu quả cho các ứng dụng song song mà vấn đề của nó được phân rã từ trung bình cho đến tốt (medium- to coarse-grain parallel chuyển cao trong việc khai thác nhiều dạng thức song song khác nhau, dễ phân chia nhỏ hơn cho các bộ xử lý độc lập trong môi trường đa người dùng (tính chất này là ngụ ý quan trọng cho tính dung lỗi), ít khó khăn trong việc mở rộng (scalability) Nhưng bên cạnh đó kiến trúc này cũng có khuyết điểm là sự quá tải do giao tiếp giữa các bộ xử lý và việc lập trình gặp nhiều khó khăn
Trong kiến trúc MIMD, có ba loại vấn đề cơ bản nổi bật, được giải quyết hiệu quả nhờ vào một số lượng lớn các bộ xử lý độc lập Kiến trúc này cho phép các xử lý thực hiện đồng thời các tác vụ khác nhau, mang lại hiệu suất cao và linh hoạt trong việc xử lý dữ liệu.
Theo luật Amdahl, việc sử dụng “bầy voi” thích hợp hơn cho các phần tuần tự trong tính toán, trong khi “đàn kiến” lại tối ưu cho các phần song song Không có câu trả lời chung cho vấn đề này, vì sự lựa chọn tốt nhất phụ thuộc vào loại công nghệ và ứng dụng cụ thể đang được áp dụng.
2 MIMD “chặt chẽ” hay “lỏng lẻo” Cách tiếp cận nào tốt hơn cho việc tính toán hiệu năng cao, bằng cách sử dụng đa bộ xử lý được thiết kế đặc biệt trên nhiều máy tính hay là tập hợp của những máy trạm bình thường được kết nối với nhau bởi các hệ thống mạng “tiện nghi” (như là Ethernet hay ATM) và những tương tác nào sẽ được kết nối với nhau bằng hệ thống phần mềm đặc biệt và các hệ thống tập tin phân tán? Cách tiếp cận thứ hai đôi khi được biết đến là mạng của các máy trạm (network of workstations hay là NOW) hay là tính toán cluster, đã được sử dụng rộng rãi trong những năm gần đây Tuy nhiên vẫn còn nhiều vấn đề mở còn tồn tại nhằm phát huy tối đa khả năng của những kiến trúc có nền tảng là mạng Thiết bị phần cứng, hệ thống phần mềm, và những khía cạnh ứng dụng của NOW đang được đầu tư tìm hiểu bởi một số lượng lớn các nhóm ngiên cứu Một cách tiếp cận trung gian là kết hợp các cluster những bộ xử lý thông qua môi trường mạng Điều này về cơ bản là một phương pháp phân nhánh, đặc biệt thích hợp khi có một sự truy cập rất lớn đến dữ liệu cục bộ.
3 Truyền thông điệp tường minh hay chia sẽ bộ nhớ ảo Lọai nào sẽ tốt hơn, cho phép người dùng chỉ ra tất cả các loại thông điệp sẽ được truyền giữa các bộ xử lý hay là cho phép họ lập trình ở một cấp độ trừu tượng cao hơn, cùng với các thông điệp cần thiết tự động được phát sinh bởi hệ thống phần mềm? Câu hỏi này về cơ bản là ngữ lập trình cấp cao và bộ nhớ ảo Tại một vài thời điểm trong quá khứ, việc lập trình bằng hợp ngữ và thực hiện trao đổi giữa bộ nhớ chính và bộ nhớ phụ có thể đem lại hiệu quả cao hơn Tuy nhiên, do ngày nay các phầm mềm đã đạt đến mức quá phức tạp, các trình biên dịch cùng với hệ điều hành cũng đã quá cấp cao đến nỗi việc tối ưu các chương trình bằng tay không còn là điều gì quá khó Tuy nhiên chúng ta vẫn chưa ở thời điểm xử lý song song đáng kể, và việc che giấu cấu trúc giao tiếp tường minh giữa các máy tính song song ra khỏi người lập trình sẽ đem lại hiệu năng thực thi rất đáng kể.
2.2.2 Tổ chức vật lý của các nền tảng song song và phân bố
Mô hình máy tính song song lý tưởng PRAM là một cách mở rộng tự nhiên của mô hình tính toán tuần tự RAM, bao gồm p bộ xử lý và một vùng nhớ toàn cục có kích thước không giới hạn Tất cả các bộ xử lý đều chia sẻ cùng một không gian địa chỉ và có thể truy cập vùng nhớ này đồng thời Các bộ xử lý trong mô hình PRAM có thể sử dụng chung một đồng hồ hoặc thực thi các chỉ thị khác nhau trên cùng một chu kỳ Tùy thuộc vào cách thức truy cập bộ nhớ, PRAM được phân thành bốn loại khác nhau, mỗi loại có đặc điểm và ứng dụng riêng.
1 Toàn quyền đọc - Toàn quyền ghi (exclusive-read, exclusive write)
Trong mô hình EREW, truy cập vào vùng nhớ được thực hiện một cách toàn quyền, nhưng không cho phép các thao tác đọc ghi Đây là một trong những mô hình PRAM không chắc chắn nhất, chỉ hỗ trợ truy cập đồng thời vào bộ nhớ với mức tối thiểu.
2 Đồng thời đọc – Toàn quyền ghi (concurrent read, exclusive write)
CREW Cho phép nhiều thao tác đọc cùng lúc trên cùng một vùng
Một số mô hình lập trình song song thông dụng
2.3.1 Mô hình chia sẽ không gian bộ nhớ
Lập trình song song tường minh yêu cầu xác định rõ ràng các tác vụ song song và các tương tác giữa chúng, có thể là đồng bộ giữa các tiến trình hoặc giao tiếp giữa các kết quả trung gian Trong kiến trúc chia sẻ không gian bộ nhớ, giao tiếp giữa các tiến trình được coi là ngụ ý, vì tất cả bộ xử lý có quyền truy cập vào một hoặc nhiều bộ nhớ Do đó, mô hình lập trình cho máy tính chia sẻ không gian địa chỉ tập trung vào các phương pháp thực thi đồng thời, đồng bộ hóa và giảm thiểu quá tải do tương tác.
Các mô hình lập trình chia sẻ không gian địa lý có sự khác biệt trong cách thức chia sẻ dữ liệu, mô hình đồng thời và hỗ trợ đồng bộ hóa Những mô hình này thường giả định rằng dữ liệu của tiến trình không được truy cập trực tiếp, điều này giúp bảo mật trong hệ thống đa người dùng Tuy nhiên, khi các tiến trình hợp tác để giải quyết vấn đề chung, việc bảo vệ dữ liệu này trở nên không cần thiết Chi phí bảo vệ dữ liệu gia tăng có thể làm giảm tính hiệu quả của lập trình song song Ngược lại, các tiến trình và tiểu trình coi toàn bộ bộ nhớ là toàn cục, thực hiện trao đổi thông tin một cách trực tiếp qua việc đọc và ghi lên các biến chia sẻ.
Hình 2-6 : Mô hình chía sẽ không gian bộ nhớ
Các tiến trình có quyền truy cập đồng thời vào vùng nhớ chung, vì vậy cần thiết phải có cơ chế đồng bộ hóa để đảm bảo tính chính xác khi thao tác với dữ liệu.
2.3.2 Mô hình truyền thông điệp
Có nhiều ngôn ngữ lập trình và thư viện dành cho lập trình song song, mỗi loại có cách nhìn khác nhau về không gian địa chỉ, mức độ đồng bộ trong các chỉ thị song song và sự đa dạng của chương trình Mô hình lập trình truyền thông điệp là một trong những mô hình lâu đời và phổ biến nhất cho lập trình trên máy tính song song, chủ yếu do yêu cầu phần cứng tối thiểu mà nó đòi hỏi.
Hình 2-7 : Mô hình truyền thông điệp
Có 2 tính chất quan trọng tạo nên bản chất của mô hình truyền thông điệp là: thứ nhất là nó giả sử không gian địa chỉ được phân chia và thứ hai là nó chỉ hỗ trợ song song hóa tường minh
Cấu trúc của những chương trình truyền thông điệp
Các chương trình truyền thông điệp thường sử dụng mô hình bất đồng bộ hoặc ít đồng bộ Mô hình bất đồng bộ cho phép thực thi tất cả các tác vụ song song một cách độc lập, nhưng gây khó khăn trong việc suy ra và dự đoán hành vi của chương trình Ngược lại, mô hình ít đồng bộ kết hợp đồng bộ hóa cho các tương tác trong khi vẫn cho phép các tác vụ được thực thi bất đồng bộ, giúp việc suy ra chương trình trở nên dễ dàng hơn Nhiều thuật toán song song phổ biến được triển khai hiệu quả thông qua các chương trình ít đồng bộ.
Mô hình truyền thông điệp hỗ trợ thực thi cho các chương trình trên từng bộ xử lý, mang lại tính linh hoạt cao trong lập trình song song Tuy nhiên, điều này cũng khiến việc viết các chương trình song song trở nên khó khăn hơn, đặc biệt khi áp dụng phương pháp single program multiple data (SPMD) Trong các chương trình SPMD, các tiến trình khác nhau thực thi đoạn mã tương tự nhau, ngoại trừ một số tiến trình “gốc” Điều này không có nghĩa là các tiến trình hoạt động đồng bộ; các chương trình SPMD có thể hoạt động ít đồng bộ hoặc hoàn toàn bất đồng bộ.
Cách thức xây dựng một chương trình song song và phân bố
Phát triển thuật toán là yếu tố then chốt trong việc giải quyết vấn đề bằng máy tính Thuật toán tuần tự là chuỗi các bước thực hiện để xử lý vấn đề, trong khi thuật toán song song sử dụng nhiều bộ xử lý để giải quyết vấn đề hiệu quả hơn Việc thiết kế thuật toán song song không chỉ đơn thuần là xác định từng bước, mà còn yêu cầu tính đồng thời, cho phép xác định các bước có thể xử lý song song nhằm tối ưu hóa khả năng tính toán Quá trình thiết kế thuật toán song song thường phức tạp và có thể liên quan đến nhiều yếu tố khác nhau.
• Chỉ ra những phần của công việc có thể được thực thi đồng thời
• Ánh xạ các phần của công việc vào nhiều bộ xử lý chạy song song
• Phân tán dữ liệu nhập, xuất và trung gian cùng với chương trình
• Quản lý truy cập vào dữ liệu chung giữa các bộ xử lý
• Đồng bộ hóa các bộ xử lý khi thực thi các chương trình song song
2.4.1 Các thuật ngữ căn bản
Phân hoạch là quá trình chia nhỏ một vấn đề phức tạp thành các kiện tiên quyết nhằm rút ngắn thời gian giải quyết Các tác vụ trong quá trình này có thể có kích thước khác nhau Đồ thị phụ thuộc thể hiện mối quan hệ và thứ tự thực hiện giữa các tác vụ, được mô tả bằng một đồ thị có hướng Trong đó, mỗi nút đại diện cho một tác vụ và các cạnh có hướng biểu thị sự phụ thuộc giữa chúng; một tác vụ chỉ được thực hiện khi các tác vụ trước đó đã hoàn thành Trong đồ thị phụ thuộc, tập hợp các cạnh có thể là rỗng.
Hình 2-8 : Đồ thị phụ thuộc tác vụ
Granularity đề cập đến số lượng và kích thước của các tác vụ sau khi phân hoạch Bước phân hoạch một vấn đề lớn thành nhiều vấn đề nhỏ được gọi là fine-grained, trong khi việc phân hoạch thành ít vấn đề lớn hơn được gọi là coarse-grained Đồ thị tương tác là mô hình thể hiện sự tương tác giữa các tác vụ.
Trong đồ thị tương tác, các nút biểu thị các tác vụ, trong khi các cạnh nối thể hiện sự tương tác giữa chúng Thông thường, các cung trong đồ thị này là vô hướng Tập hợp các cạnh thường là tập hợp cha của các cạnh trong đồ thị phụ thuộc.
Hình 2-9 :Đồ thi tương tác trong bài toán nhân ma trận với vector
2.4.2 Thiết kế thuật toán song song
Phân chia công việc tính toán thành các phần nhỏ hơn và phân bổ chúng cho các bộ xử lý khác nhau để thực hiện song song là hai bước cơ bản trong thiết kế thuật toán song song.
2.4.2.1 Một số phương pháp phân hoạch
Để giải quyết vấn đề theo hướng song song, bước đầu tiên là phân chia các phép toán thành những tác vụ nhỏ hơn nhằm xử lý đồng thời Trong phần này, chúng ta sẽ trình bày một số kỹ thuật phân hoạch phổ biến cho xử lý đồng hành Mặc dù không phải tất cả các kỹ thuật phân hoạch đều được đề cập, và không có đảm bảo rằng những phương pháp này sẽ dẫn đến thuật toán song song tối ưu cho mọi vấn đề, nhưng chúng vẫn là điểm khởi đầu tốt Việc kết hợp một hoặc nhiều kỹ thuật này có thể giúp đạt được phân hoạch hiệu quả cho nhiều loại vấn đề khác nhau.
Các kỹ thuật phân họach phân họach ở đây có thể phân thành các lọai sau phân họach đệ quy, phân họach dữ liệu, phân họach thăm dò và phân
Phân họach đệ quy là một kỹ thuật hiệu quả trong việc giải quyết các vấn đề thông qua phương pháp chia-và-trị Phương pháp này bắt đầu bằng cách chia nhỏ một vấn đề thành các vấn đề con độc lập, sau đó tiếp tục áp dụng quy trình này cho từng vấn đề con cho đến khi chúng trở nên đơn giản hơn Cuối cùng, kết quả của vấn đề lớn được hình thành từ sự kết hợp của các kết quả từ các vấn đề con nhỏ hơn.
Phân hoạch theo dữ liệu là một phương pháp hiệu quả, phổ biến trong việc xác định tính đồng hành của các thuật toán, giúp thao tác trên các cấu trúc dữ liệu lớn một cách hiệu quả Phương pháp này mang lại nhiều lợi ích trong việc tối ưu hóa quá trình xử lý thông tin.
Trong quy trình này, bước đầu tiên là phân chia dữ liệu thành các phần riêng biệt, sau đó trong bước thứ hai, các phần dữ liệu này sẽ được chuyển đổi thành các tác vụ cụ thể Các thao tác mà các tác vụ thực hiện trên các phần dữ liệu thường có tính chất tương tự hoặc được lựa chọn từ một tập hợp các thao tác nhỏ hơn.
Trong phần dưới đây, chúng ta sẽ khám phá các phương pháp phân chia dữ liệu khác nhau Người thiết kế cần tự đánh giá và lựa chọn cách phân chia dữ liệu phù hợp nhất, đảm bảo tính tự nhiên và hiệu quả trong quá trình thiết kế.
Phân chia dữ liệu xuất
Trong các phần tính toán, các phần xuất có thể được xử lý độc lập, cho phép phân chia dữ liệu xuất tự động Việc này dẫn đến việc phân hoạch vấn đề thành các tác vụ riêng biệt, mỗi tác vụ được gán cho công việc tính toán một phần của kết quả xuất, ví dụ như nhân ma trận.
Trong bài viết này, chúng ta sẽ xem xét vấn đề nhân hai ma trận nxn A và B, với kết quả là ma trận C Để thực hiện phép nhân, trước tiên, chúng ta chia mỗi ma trận thành bốn khối hoặc ma trận con bằng cách chia các chiều của ma trận thành hai phần Kết quả là bốn ma trận con của ma trận C, mỗi phần có kích thước n/2 x n/2, có thể được tính toán độc lập thông qua bốn tác vụ khác nhau.
Hình 2-10 : (a) Phân các ma trận nhập và xuất thành các ma trận con
(b) Phân hoạch phép nhân ma trận thành 4 tác vụ
Hầu hết các thuật toán ma trận, như nhận ma trận với vector và nhân ma trận với ma trận, có thể được biểu diễn dưới dạng các thao tác trên khối ma trận Trong đó, mỗi ma trận được chia thành các khối hay ma trận con, và các phép toán được thực hiện trên từng phần tử, sau đó thay thế bằng các phép toán trên các khối ma trận con Kết quả thu được từ từng phần tử và các khối là tương tự nhau Thuật toán ma trận khối thường được áp dụng để hỗ trợ cho quá trình phân hoạch.
Phân hoạch theo dữ liệu và phân hoạch các phép tính thành các tác vụ là hai khái niệm khác nhau, mặc dù chúng thường liên quan và hỗ trợ lẫn nhau Một kết quả phân hoạch dữ liệu không chỉ có một phương pháp duy nhất để phân chia thành các tác vụ.
Phân chia dữ liệu nhập
Phân chia dữ liệu xuất chỉ khả thi khi mỗi kết quả có thể tính toán theo chức năng nhập Việc phân chia dữ liệu nhập là khả thi và có thể sử dụng kết quả để thực hiện tính toán đồng thời Mỗi tác vụ được tạo ra cho từng phần dữ liệu nhập, tối đa hóa phép tính trên dữ liệu cục bộ Tuy nhiên, giải pháp cho các tác vụ từ dữ liệu nhập có thể không trực tiếp giải quyết vấn đề gốc Trong trường hợp này, kết quả tính toán có thể "nổi bọt" lên phía trên Chẳng hạn, khi tính tổng của N số bằng p tiến trình (p < N), dữ liệu nhập có thể chia thành p phần con gần bằng nhau, mỗi tác vụ cộng các số trong phần con, và kết quả cuối cùng là tổng của p phần con đã tính.
Phân chia cả dữ liệu xuất và nhập
Trong nhiều trường hợp việc phân chia theo cả kết quả xuất và dữ liệu nhập có thể làm tăng khả năng xử lý đồng thời
Phân chia dữ liệu trung gian
