Thuật toán song song - Hướng dẫn nhanh

An algorithmlà một chuỗi các bước lấy đầu vào từ người dùng và sau một số tính toán, tạo ra đầu ra. Aparallel algorithm là một thuật toán có thể thực hiện một số lệnh đồng thời trên các thiết bị xử lý khác nhau và sau đó kết hợp tất cả các đầu ra riêng lẻ để tạo ra kết quả cuối cùng.

Xử lý đồng thời

Sự sẵn có dễ dàng của máy tính cùng với sự phát triển của Internet đã thay đổi cách chúng ta lưu trữ và xử lý dữ liệu. Chúng ta đang sống trong thời đại mà dữ liệu có sẵn rất nhiều. Hàng ngày, chúng tôi xử lý khối lượng dữ liệu khổng lồ đòi hỏi tính toán phức tạp và điều đó cũng diễn ra trong thời gian nhanh chóng. Đôi khi, chúng ta cần tìm nạp dữ liệu từ các sự kiện tương tự hoặc có liên quan xảy ra đồng thời. Đây là nơi chúng tôi yêu cầuconcurrent processing có thể chia một nhiệm vụ phức tạp và xử lý nó nhiều hệ thống để tạo ra kết quả đầu ra trong thời gian nhanh chóng.

Xử lý đồng thời là điều cần thiết khi nhiệm vụ liên quan đến việc xử lý một lượng lớn dữ liệu phức tạp. Ví dụ bao gồm - truy cập cơ sở dữ liệu lớn, thử nghiệm máy bay, tính toán thiên văn, vật lý nguyên tử và hạt nhân, phân tích y sinh, lập kế hoạch kinh tế, xử lý hình ảnh, rô bốt, dự báo thời tiết, dịch vụ dựa trên web, v.v.

Song song là gì?

Parallelismlà quá trình xử lý đồng thời một số tập lệnh. Nó làm giảm tổng thời gian tính toán. Song song có thể được thực hiện bằng cách sử dụngparallel computers,tức là một máy tính có nhiều bộ xử lý. Máy tính song song yêu cầu thuật toán song song, ngôn ngữ lập trình, trình biên dịch và hệ điều hành hỗ trợ đa nhiệm.

Trong hướng dẫn này, chúng ta sẽ chỉ thảo luận về parallel algorithms. Trước khi đi sâu hơn, trước tiên chúng ta hãy thảo luận về các thuật toán và các loại của chúng.

Thuật toán là gì?

An algorithmlà một chuỗi các hướng dẫn theo sau để giải quyết một vấn đề. Trong khi thiết kế một thuật toán, chúng ta nên xem xét kiến ​​trúc của máy tính mà thuật toán sẽ được thực thi. Theo kiến ​​trúc, có hai loại máy tính -

  • Máy tính tuần tự
  • Máy tính song song

Tùy thuộc vào kiến ​​trúc của máy tính, chúng ta có hai loại thuật toán -

  • Sequential Algorithm - Một thuật toán trong đó một số bước hướng dẫn liên tiếp được thực hiện theo trình tự thời gian để giải quyết một vấn đề.

  • Parallel Algorithm- Bài toán được chia thành các bài toán con và được thực hiện song song để lấy các đầu ra riêng lẻ. Sau đó, các đầu ra riêng lẻ này được kết hợp với nhau để có được đầu ra mong muốn cuối cùng.

Không dễ để chia một vấn đề lớn thành sub-problems. Các vấn đề phụ có thể có sự phụ thuộc dữ liệu giữa chúng. Do đó, các bộ xử lý phải giao tiếp với nhau để giải quyết vấn đề.

Người ta thấy rằng thời gian cần thiết của các bộ xử lý trong việc giao tiếp với nhau nhiều hơn thời gian xử lý thực tế. Vì vậy, trong khi thiết kế một thuật toán song song, việc sử dụng CPU hợp lý cần được xem xét để có được một thuật toán hiệu quả.

Để thiết kế một thuật toán đúng cách, chúng ta phải có một ý tưởng rõ ràng về các model of computation trong một máy tính song song.

Mô hình tính toán

Cả hai máy tính tuần tự và song song đều hoạt động trên một tập hợp (dòng) lệnh được gọi là thuật toán. Tập hợp các hướng dẫn (thuật toán) này hướng dẫn máy tính về những gì nó phải làm trong mỗi bước.

Tùy thuộc vào luồng lệnh và luồng dữ liệu, máy tính có thể được phân thành bốn loại:

  • Máy tính luồng hướng dẫn đơn, luồng dữ liệu đơn (SISD)
  • Máy tính một luồng hướng dẫn, nhiều luồng dữ liệu (SIMD)
  • Máy tính đa luồng hướng dẫn, luồng dữ liệu đơn (MISD)
  • Máy tính nhiều luồng hướng dẫn, nhiều luồng dữ liệu (MIMD)

Máy tính SISD

Máy tính SISD chứa one control unit, one processing unit, và one memory unit.

Trong loại máy tính này, bộ xử lý nhận một luồng lệnh từ bộ điều khiển và hoạt động trên một luồng dữ liệu từ bộ nhớ. Trong quá trình tính toán, ở mỗi bước, bộ xử lý nhận một lệnh từ bộ điều khiển và hoạt động trên một dữ liệu duy nhất nhận được từ bộ nhớ.

Máy tính SIMD

Máy tính SIMD chứa one control unit, multiple processing units, và shared memory or interconnection network.

Tại đây, một bộ điều khiển duy nhất sẽ gửi hướng dẫn đến tất cả các bộ phận xử lý. Trong quá trình tính toán, ở mỗi bước, tất cả các bộ xử lý nhận được một bộ lệnh duy nhất từ ​​bộ điều khiển và hoạt động trên bộ dữ liệu khác nhau từ bộ nhớ.

Mỗi đơn vị xử lý có bộ nhớ cục bộ riêng để lưu trữ cả dữ liệu và lệnh. Trong máy tính SIMD, các bộ xử lý cần giao tiếp với nhau. Điều này được thực hiện bởishared memory hoặc bằng cách interconnection network.

Trong khi một số bộ xử lý thực thi một tập hợp các lệnh, các bộ xử lý còn lại sẽ chờ tập các lệnh tiếp theo của chúng. Hướng dẫn từ bộ phận điều khiển quyết định bộ xử lý nào sẽ làactive (thực hiện hướng dẫn) hoặc inactive (chờ hướng dẫn tiếp theo).

Máy tính MISD

Như tên cho thấy, máy tính MISD chứa multiple control units, multiple processing units, và one common memory unit.

Ở đây, mỗi bộ xử lý có bộ điều khiển riêng và chúng chia sẻ một bộ nhớ chung. Tất cả các bộ xử lý nhận được hướng dẫn riêng lẻ từ bộ điều khiển của riêng họ và chúng hoạt động trên một luồng dữ liệu duy nhất theo hướng dẫn mà chúng đã nhận được từ bộ điều khiển tương ứng. Bộ xử lý này hoạt động đồng thời.

Máy tính MIMD

Máy tính MIMD có multiple control units, multiple processing units, và một shared memory hoặc là interconnection network.

Ở đây, mỗi bộ xử lý có bộ điều khiển riêng, bộ nhớ cục bộ, đơn vị số học và logic. Chúng nhận được các bộ hướng dẫn khác nhau từ các đơn vị điều khiển tương ứng và hoạt động trên các bộ dữ liệu khác nhau.

Ghi chú

  • Máy tính MIMD chia sẻ bộ nhớ chung được gọi là multiprocessors, trong khi những mạng sử dụng mạng kết nối được gọi là multicomputers.

  • Dựa trên khoảng cách vật lý của các bộ xử lý, đa máy tính có hai loại:

    • Multicomputer - Khi tất cả các bộ xử lý ở rất gần nhau (ví dụ: trong cùng một phòng).

    • Distributed system - Khi tất cả các bộ xử lý ở xa nhau (ví dụ: ở các thành phố khác nhau)

Phân tích một thuật toán giúp chúng ta xác định xem thuật toán đó có hữu ích hay không. Nói chung, một thuật toán được phân tích dựa trên thời gian thực thi của nó(Time Complexity) và số lượng không gian (Space Complexity) nó yêu cầu.

Vì chúng tôi có sẵn các thiết bị bộ nhớ tinh vi với chi phí hợp lý, không gian lưu trữ không còn là vấn đề. Do đó, sự phức tạp về không gian không được coi trọng như vậy.

Các thuật toán song song được thiết kế để cải thiện tốc độ tính toán của máy tính. Để phân tích một thuật toán song song, chúng tôi thường xem xét các tham số sau:

  • Độ phức tạp về thời gian (Thời gian thực hiện),
  • Tổng số bộ xử lý được sử dụng và
  • Tổng chi phí.

Thời gian phức tạp

Lý do chính đằng sau việc phát triển các thuật toán song song là để giảm thời gian tính toán của một thuật toán. Vì vậy, việc đánh giá thời gian thực thi của một thuật toán là vô cùng quan trọng trong việc phân tích hiệu quả của nó.

Thời gian thực thi được đo trên cơ sở thời gian mà thuật toán thực hiện để giải quyết một vấn đề. Tổng thời gian thực hiện được tính từ lúc thuật toán bắt đầu thực thi đến lúc dừng. Nếu tất cả các bộ xử lý không bắt đầu hoặc kết thúc thực thi cùng một lúc, thì tổng thời gian thực thi của thuật toán là thời điểm khi bộ xử lý đầu tiên bắt đầu thực thi đến thời điểm bộ xử lý cuối cùng ngừng thực thi.

Độ phức tạp về thời gian của một thuật toán có thể được phân thành ba loại

  • Worst-case complexity - Khi lượng thời gian mà thuật toán yêu cầu cho một đầu vào nhất định là maximum.

  • Average-case complexity - Khi lượng thời gian mà thuật toán yêu cầu cho một đầu vào nhất định là average.

  • Best-case complexity - Khi lượng thời gian mà thuật toán yêu cầu cho một đầu vào nhất định là minimum.

Phân tích tiệm cận

Độ phức tạp hoặc hiệu quả của một thuật toán là số bước được thực hiện bởi thuật toán để có được đầu ra mong muốn. Phân tích tiệm cận được thực hiện để tính toán độ phức tạp của một thuật toán trong phân tích lý thuyết của nó. Trong phân tích tiệm cận, độ dài đầu vào lớn được sử dụng để tính hàm phức tạp của thuật toán.

Note - Asymptoticlà điều kiện mà một đường có xu hướng gặp một đường cong, nhưng chúng không cắt nhau. Ở đây đường thẳng và đường cong là tiệm cận của nhau.

Ký hiệu tiệm cận là cách dễ nhất để mô tả thời gian thực thi nhanh nhất và chậm nhất có thể cho một thuật toán sử dụng giới hạn cao và giới hạn thấp về tốc độ. Đối với điều này, chúng tôi sử dụng các ký hiệu sau:

  • Ký hiệu O lớn
  • Ký hiệu Omega
  • Ký hiệu Theta

Ký hiệu O lớn

Trong toán học, ký hiệu Big O được sử dụng để biểu diễn các đặc điểm tiệm cận của các hàm số. Nó thể hiện hành vi của một hàm đối với các đầu vào lớn theo một phương pháp đơn giản và chính xác. Nó là một phương pháp biểu diễn giới hạn trên của thời gian thực thi thuật toán. Nó đại diện cho khoảng thời gian dài nhất mà thuật toán có thể mất để hoàn thành quá trình thực thi của nó. Hàm -

f (n) = O (g (n))

iff có tồn tại các hằng số dương c và n0 như vậy mà f(n) ≤ c * g(n) cho tất cả n Ở đâu n ≥ n0.

Ký hiệu Omega

Ký hiệu Omega là một phương pháp biểu diễn giới hạn dưới của thời gian thực thi thuật toán. Hàm -

f (n) = Ω (g (n))

iff có tồn tại các hằng số dương c và n0 như vậy mà f(n) ≥ c * g(n) cho tất cả n Ở đâu n ≥ n0.

Ký hiệu Theta

Ký hiệu Theta là một phương pháp biểu diễn cả giới hạn dưới và giới hạn trên của thời gian thực hiện thuật toán. Hàm -

f (n) = θ (g (n))

iff có tồn tại các hằng số dương c1, c2, và n0 sao cho c1 * g (n) ≤ f (n) ≤ c2 * g (n) với mọi n Ở đâu n ≥ n0.

Tăng tốc độ của một thuật toán

Hiệu suất của một thuật toán song song được xác định bằng cách tính toán speedup. Tốc độ tăng được định nghĩa là tỷ số giữa thời gian thực hiện trường hợp xấu nhất của thuật toán tuần tự nhanh nhất đã biết cho một vấn đề cụ thể với thời gian thực hiện trường hợp xấu nhất của thuật toán song song.

tăng tốc =
Thời gian thực hiện trường hợp tệ nhất của trình tự nhanh nhất đã biết cho một vấn đề cụ thể / Thời gian thực hiện trường hợp xấu nhất của thuật toán song song

Số lượng bộ xử lý được sử dụng

Số lượng bộ xử lý được sử dụng là một yếu tố quan trọng trong việc phân tích hiệu quả của một thuật toán song song. Chi phí mua, bảo trì và chạy máy tính được tính toán. Số lượng bộ xử lý được sử dụng bởi một thuật toán để giải quyết vấn đề càng lớn thì kết quả thu được càng tốn kém.

Tổng chi phí

Tổng chi phí của một thuật toán song song là tích số của độ phức tạp về thời gian và số lượng bộ xử lý được sử dụng trong thuật toán cụ thể đó.

Tổng chi phí = Độ phức tạp về thời gian × Số bộ xử lý được sử dụng

Do đó, efficiency của một thuật toán song song là -

Hiệu quả =
Thời gian thực hiện trường hợp xấu nhất của thuật toán tuần tự / Thời gian thực hiện trường hợp xấu nhất của thuật toán song song

Mô hình thuật toán song song được phát triển bằng cách xem xét chiến lược phân chia dữ liệu và phương pháp xử lý và áp dụng chiến lược phù hợp để giảm tương tác. Trong chương này, chúng ta sẽ thảo luận về các Mô hình Thuật toán Song song sau:

  • Mô hình song song dữ liệu
  • Mô hình biểu đồ nhiệm vụ
  • Mô hình hồ bơi làm việc
  • Mô hình nô lệ chủ
  • Người tiêu dùng hoặc mô hình đường ống của nhà sản xuất
  • Mô hình lai

Dữ liệu song song

Trong mô hình song song dữ liệu, các tác vụ được gán cho các tiến trình và mỗi tác vụ thực hiện các kiểu hoạt động tương tự trên các dữ liệu khác nhau. Data parallelism là hệ quả của các hoạt động đơn lẻ đang được áp dụng trên nhiều mục dữ liệu.

Mô hình song song dữ liệu có thể được áp dụng trên không gian địa chỉ chia sẻ và mô hình truyền thông điệp. Trong mô hình song song dữ liệu, chi phí tương tác có thể được giảm thiểu bằng cách chọn một khu vực bảo tồn phân hủy, bằng cách sử dụng các quy trình tương tác tập thể được tối ưu hóa hoặc bằng cách tính toán và tương tác chồng chéo.

Đặc điểm cơ bản của các bài toán mô hình song song dữ liệu là cường độ của tính song song dữ liệu tăng lên theo quy mô của bài toán, do đó có thể sử dụng nhiều quy trình hơn để giải quyết các vấn đề lớn hơn.

Example - Phép nhân ma trận dày đặc.

Mô hình biểu đồ nhiệm vụ

Trong mô hình biểu đồ nhiệm vụ, tính song song được biểu thị bằng một task graph. Biểu đồ nhiệm vụ có thể là tầm thường hoặc không tầm thường. Trong mô hình này, mối tương quan giữa các nhiệm vụ được sử dụng để thúc đẩy địa phương hoặc để giảm thiểu chi phí tương tác. Mô hình này được thực thi để giải quyết các vấn đề trong đó số lượng dữ liệu liên quan đến các tác vụ là rất lớn so với số lượng tính toán liên quan đến chúng. Các nhiệm vụ được giao để giúp cải thiện chi phí di chuyển dữ liệu giữa các nhiệm vụ.

Examples - Sắp xếp nhanh song song, phân tích nhân tử ma trận thưa thớt và các thuật toán song song xuất phát từ phương pháp chia để trị.

Ở đây, các bài toán được chia thành các nhiệm vụ nguyên tử và được thực hiện dưới dạng đồ thị. Mỗi nhiệm vụ là một đơn vị công việc độc lập có sự phụ thuộc vào một hoặc nhiều nhiệm vụ tiền nhiệm. Sau khi hoàn thành một tác vụ, đầu ra của một nhiệm vụ trước đó được chuyển cho tác vụ phụ thuộc. Một tác vụ với tác vụ tiền trước chỉ bắt đầu thực thi khi toàn bộ tác vụ tiền trước của nó được hoàn thành. Đầu ra cuối cùng của đồ thị nhận được khi hoàn thành nhiệm vụ phụ thuộc cuối cùng (Nhiệm vụ 6 trong hình trên).

Mô hình Work Pool

Trong mô hình nhóm làm việc, các nhiệm vụ được gán động cho các quy trình để cân bằng tải. Do đó, bất kỳ quy trình nào cũng có thể thực thi bất kỳ tác vụ nào. Mô hình này được sử dụng khi số lượng dữ liệu được liên kết với các tác vụ tương đối nhỏ hơn so với phép tính liên quan đến các tác vụ.

Không có sự giao trước nhiệm vụ mong muốn cho các quy trình. Việc phân công nhiệm vụ mang tính tập trung hoặc phân cấp. Con trỏ đến các nhiệm vụ được lưu trong danh sách chia sẻ vật lý, trong hàng đợi ưu tiên, hoặc trong bảng băm hoặc cây, hoặc chúng có thể được lưu trong cấu trúc dữ liệu phân tán vật lý.

Nhiệm vụ có thể có sẵn ngay từ đầu hoặc có thể được tạo động. Nếu nhiệm vụ được tạo động và thực hiện phân cấp nhiệm vụ, thì thuật toán phát hiện kết thúc là cần thiết để tất cả các quy trình thực sự có thể phát hiện sự hoàn thành của toàn bộ chương trình và ngừng tìm kiếm thêm nhiệm vụ.

Example - Tìm kiếm cây song song

Mô hình Master-Slave

Trong mô hình chủ-tớ, một hoặc nhiều quy trình chính tạo ra nhiệm vụ và phân bổ nó cho các quy trình phụ. Các nhiệm vụ có thể được phân bổ trước nếu -

  • bậc thầy có thể ước tính khối lượng của các nhiệm vụ, hoặc
  • một chỉ định ngẫu nhiên có thể thực hiện công việc cân bằng tải một cách thỏa đáng, hoặc
  • nô lệ được giao những phần nhiệm vụ nhỏ hơn vào những thời điểm khác nhau.

Mô hình này thường phù hợp với shared-address-space hoặc là message-passing paradigms, vì tương tác tự nhiên là hai cách.

Trong một số trường hợp, một nhiệm vụ có thể cần được hoàn thành trong các giai đoạn và nhiệm vụ trong mỗi giai đoạn phải được hoàn thành trước khi nhiệm vụ trong các giai đoạn tiếp theo có thể được tạo ra. Mô hình chủ-tớ có thể được khái quát thànhhierarchical hoặc là multi-level master-slave model trong đó bậc thầy cấp cao nhất cung cấp phần lớn nhiệm vụ cho bậc thầy cấp hai, người này sẽ chia nhỏ các nhiệm vụ giữa các nô lệ của chính nó và có thể tự thực hiện một phần nhiệm vụ.

Các lưu ý khi sử dụng mô hình chủ-tớ

Cần cẩn thận để đảm bảo rằng bản gốc không trở thành điểm nghẽn. Nó có thể xảy ra nếu các nhiệm vụ quá nhỏ hoặc công nhân tương đối nhanh.

Các nhiệm vụ nên được lựa chọn theo cách mà chi phí thực hiện một nhiệm vụ chi phối chi phí truyền thông và chi phí đồng bộ hóa.

Tương tác không đồng bộ có thể giúp tương tác chồng chéo và tính toán liên quan đến việc tạo công việc của chủ.

Mô hình đường ống

Nó còn được gọi là producer-consumer model. Tại đây, một tập hợp dữ liệu được chuyển qua một loạt các quy trình, mỗi quy trình thực hiện một số nhiệm vụ trên đó. Ở đây, sự xuất hiện của dữ liệu mới tạo ra việc thực thi một tác vụ mới bởi một quá trình trong hàng đợi. Các quy trình có thể tạo thành một hàng đợi ở dạng mảng tuyến tính hoặc đa chiều, cây hoặc đồ thị tổng quát có hoặc không có chu trình.

Mô hình này là một chuỗi giữa người sản xuất và người tiêu dùng. Mỗi tiến trình trong hàng đợi có thể được coi là người sử dụng một chuỗi các mục dữ liệu cho quá trình trước nó trong hàng đợi và như một nhà sản xuất dữ liệu cho quá trình theo sau nó trong hàng đợi. Hàng đợi không cần phải là một chuỗi tuyến tính; nó có thể là một đồ thị có hướng. Kỹ thuật giảm thiểu tương tác phổ biến nhất áp dụng cho mô hình này là tương tác chồng chéo với tính toán.

Example - Thuật toán phân tích nhân tử LU song song.

Mô hình kết hợp

Mô hình thuật toán kết hợp được yêu cầu khi có thể cần nhiều hơn một mô hình để giải quyết một vấn đề.

Mô hình kết hợp có thể bao gồm nhiều mô hình được áp dụng phân cấp hoặc nhiều mô hình được áp dụng tuần tự cho các giai đoạn khác nhau của một thuật toán song song.

Example - Sắp xếp nhanh song song

Parallel Random Access Machines (PRAM)là một mô hình, được xem xét cho hầu hết các thuật toán song song. Ở đây, nhiều bộ xử lý được gắn vào một khối bộ nhớ. Mô hình PRAM chứa -

  • Một tập hợp các loại vi xử lý tương tự.

  • Tất cả các bộ xử lý chia sẻ một đơn vị bộ nhớ chung. Các bộ xử lý chỉ có thể giao tiếp với nhau thông qua bộ nhớ dùng chung.

  • Một bộ truy cập bộ nhớ (MAU) kết nối bộ xử lý với một bộ nhớ dùng chung.

Đây, n số lượng bộ xử lý có thể thực hiện các hoạt động độc lập trên nsố lượng dữ liệu trong một đơn vị thời gian cụ thể. Điều này có thể dẫn đến việc truy cập đồng thời vào cùng một vị trí bộ nhớ bởi các bộ xử lý khác nhau.

Để giải quyết vấn đề này, các ràng buộc sau đã được thực thi trên mô hình PRAM:

  • Exclusive Read Exclusive Write (EREW) - Ở đây không có hai bộ vi xử lý nào được phép đọc từ hoặc ghi vào cùng một vị trí bộ nhớ cùng một lúc.

  • Exclusive Read Concurrent Write (ERCW) - Ở đây không có hai bộ xử lý nào được phép đọc đồng thời từ cùng một vị trí bộ nhớ, nhưng được phép ghi vào cùng một vị trí bộ nhớ cùng một lúc.

  • Concurrent Read Exclusive Write (CREW) - Ở đây tất cả các bộ xử lý được phép đọc đồng thời từ cùng một vị trí bộ nhớ, nhưng không được phép ghi đồng thời vào cùng một vị trí bộ nhớ.

  • Concurrent Read Concurrent Write (CRCW) - Tất cả các bộ xử lý được phép đọc hoặc ghi vào cùng một vị trí bộ nhớ cùng một lúc.

Có nhiều phương pháp để triển khai mô hình PRAM, nhưng những phương pháp nổi bật nhất là -

  • Mô hình bộ nhớ dùng chung
  • Mô hình truyền thông điệp
  • Mô hình song song dữ liệu

Mô hình bộ nhớ dùng chung

Bộ nhớ dùng chung nhấn mạnh vào control parallelism hơn trên data parallelism. Trong mô hình bộ nhớ dùng chung, nhiều quá trình thực thi trên các bộ xử lý khác nhau một cách độc lập, nhưng chúng chia sẻ một không gian bộ nhớ chung. Do bất kỳ hoạt động nào của bộ xử lý, nếu có bất kỳ thay đổi nào trong bất kỳ vị trí bộ nhớ nào, phần còn lại của bộ xử lý sẽ hiển thị.

Khi nhiều bộ xử lý truy cập vào cùng một vị trí bộ nhớ, có thể xảy ra vào bất kỳ thời điểm cụ thể nào, nhiều bộ xử lý đang truy cập cùng một vị trí bộ nhớ. Giả sử một người đang đọc vị trí đó và người kia đang viết trên vị trí đó. Nó có thể tạo ra sự nhầm lẫn. Để tránh điều này, một số cơ chế kiểm soát, nhưlock / semaphore, được thực hiện để đảm bảo loại trừ lẫn nhau.

Lập trình bộ nhớ dùng chung đã được thực hiện như sau:

  • Thread libraries- Thư viện luồng cho phép nhiều luồng điều khiển chạy đồng thời trong cùng một vị trí bộ nhớ. Thư viện luồng cung cấp một giao diện hỗ trợ đa luồng thông qua một thư viện chương trình con. Nó chứa các chương trình con cho

    • Tạo và hủy chuỗi
    • Lập lịch thực hiện chuỗi
    • truyền dữ liệu và tin nhắn giữa các chuỗi
    • lưu và khôi phục ngữ cảnh chuỗi

Ví dụ về thư viện luồng bao gồm - luồng SolarisTM cho Solaris, luồng POSIX được triển khai trong Linux, các luồng Win32 có sẵn trong Windows NT và Windows 2000 và các luồng JavaTM như một phần của Bộ phát triển JavaTM tiêu chuẩn (JDK).

  • Distributed Shared Memory (DSM) Systems- Hệ thống DSM tạo ra sự trừu tượng của bộ nhớ dùng chung trên kiến ​​trúc được ghép nối lỏng lẻo để thực hiện lập trình bộ nhớ dùng chung mà không cần hỗ trợ phần cứng. Chúng triển khai các thư viện tiêu chuẩn và sử dụng các tính năng quản lý bộ nhớ cấp người dùng nâng cao có trong các hệ điều hành hiện đại. Ví dụ bao gồm Tread Marks System, Munin, IVY, Shasta, Brazos và Cashmere.

  • Program Annotation Packages- Điều này được thực hiện trên các kiến ​​trúc có đặc tính truy cập bộ nhớ đồng nhất. Ví dụ đáng chú ý nhất về các gói chú thích chương trình là OpenMP. OpenMP thực hiện song song chức năng. Nó chủ yếu tập trung vào việc song song hóa các vòng lặp.

Khái niệm bộ nhớ dùng chung cung cấp khả năng kiểm soát mức độ thấp đối với hệ thống bộ nhớ dùng chung, nhưng nó có xu hướng tẻ nhạt và sai lầm. Nó có thể áp dụng cho lập trình hệ thống hơn là lập trình ứng dụng.

Ưu điểm của lập trình bộ nhớ dùng chung

  • Không gian địa chỉ toàn cục cung cấp cách tiếp cận lập trình thân thiện với người dùng đối với bộ nhớ.

  • Do sự gần gũi của bộ nhớ với CPU, việc chia sẻ dữ liệu giữa các quá trình diễn ra nhanh chóng và đồng nhất.

  • Không cần phải xác định rõ ràng việc truyền dữ liệu giữa các quá trình.

  • Chi phí truyền thông quy trình là không đáng kể.

  • Nó rất dễ học.

Điểm mạnh của lập trình bộ nhớ dùng chung

  • Nó không phải là di động.
  • Quản lý dữ liệu cục bộ là rất khó khăn.

Mô hình chuyển thông báo

Truyền thông điệp là phương pháp lập trình song song được sử dụng phổ biến nhất trong các hệ thống bộ nhớ phân tán. Ở đây, người lập trình phải xác định độ song song. Trong mô hình này, tất cả các bộ xử lý đều có bộ nhớ cục bộ riêng và chúng trao đổi dữ liệu thông qua mạng truyền thông.

Các bộ xử lý sử dụng các thư viện truyền thông điệp để liên lạc với nhau. Cùng với dữ liệu được gửi đi, thông báo có chứa các thành phần sau:

  • Địa chỉ của bộ xử lý mà từ đó tin nhắn được gửi đi;

  • Địa chỉ bắt đầu của vị trí bộ nhớ của dữ liệu trong bộ xử lý gửi;

  • Kiểu dữ liệu của dữ liệu gửi;

  • Kích thước dữ liệu của dữ liệu gửi;

  • Địa chỉ của bộ xử lý mà tin nhắn đang được gửi đến;

  • Địa chỉ bắt đầu của vị trí bộ nhớ cho dữ liệu trong bộ xử lý nhận.

Các bộ xử lý có thể giao tiếp với nhau bằng bất kỳ phương thức nào sau đây:

  • Giao tiếp điểm-điểm
  • Giao tiếp tập thể
  • Giao diện chuyển thông báo

Giao tiếp điểm-điểm

Truyền thông điểm-điểm là hình thức truyền thông điệp đơn giản nhất. Tại đây, một thông báo có thể được gửi từ bộ xử lý gửi đến bộ xử lý nhận bằng bất kỳ chế độ truyền nào sau đây:

  • Synchronous mode - Tin nhắn tiếp theo chỉ được gửi sau khi nhận được xác nhận rằng tin nhắn trước đó đã được gửi, để duy trì trình tự của tin nhắn.

  • Asynchronous mode - Để gửi tin nhắn tiếp theo, không cần nhận được xác nhận đã gửi tin nhắn trước.

Giao tiếp tập thể

Giao tiếp tập thể liên quan đến nhiều hơn hai bộ xử lý để truyền thông điệp. Các chế độ sau cho phép giao tiếp tập thể -

  • Barrier - Chế độ rào cản có thể thực hiện được nếu tất cả các bộ xử lý bao gồm trong giao tiếp chạy một bock cụ thể (được gọi là barrier block) để truyền tin nhắn.

  • Broadcast - Phát thanh có hai loại -

    • One-to-all - Ở đây, một bộ xử lý với một thao tác duy nhất sẽ gửi cùng một thông điệp đến tất cả các bộ xử lý khác.

    • All-to-all - Tại đây, tất cả các bộ xử lý gửi tin nhắn đến tất cả các bộ xử lý khác.

Tin nhắn được phát đi có thể có ba loại -

  • Personalized - Tin nhắn duy nhất được gửi đến tất cả các bộ xử lý đích khác.

  • Non-personalized - Tất cả các bộ xử lý đích đều nhận được cùng một thông báo.

  • Reduction - Trong phát sóng giảm, một bộ xử lý của nhóm thu thập tất cả các thông báo từ tất cả các bộ xử lý khác trong nhóm và kết hợp chúng thành một thông báo duy nhất mà tất cả các bộ xử lý khác trong nhóm có thể truy cập.

Điểm mạnh của việc truyền tin nhắn

  • Cung cấp khả năng điều khiển song song mức thấp;
  • Nó là di động;
  • Ít bị lỗi;
  • Ít chi phí hơn trong đồng bộ hóa song song và phân phối dữ liệu.

Điểm mạnh của việc truyền tin nhắn

  • So với mã bộ nhớ dùng chung song song, mã truyền thông báo thường cần nhiều phần mềm hơn.

Thư viện chuyển thư

Có rất nhiều thư viện chuyển thư. Ở đây, chúng ta sẽ thảo luận về hai trong số các thư viện chuyển thư được sử dụng nhiều nhất -

  • Giao diện truyền thông báo (MPI)
  • Máy ảo song song (PVM)

Giao diện truyền thông báo (MPI)

Đây là một tiêu chuẩn chung để cung cấp giao tiếp giữa tất cả các quá trình đồng thời trong một hệ thống bộ nhớ phân tán. Hầu hết các nền tảng tính toán song song thường được sử dụng đều cung cấp ít nhất một giao diện truyền thông điệp triển khai. Nó đã được triển khai dưới dạng tập hợp các hàm được xác định trước được gọi làlibrary và có thể được gọi từ các ngôn ngữ như C, C ++, Fortran, v.v. MPI vừa nhanh vừa di động so với các thư viện truyền thông báo khác.

Merits of Message Passing Interface

  • Chỉ chạy trên kiến ​​trúc bộ nhớ dùng chung hoặc kiến ​​trúc bộ nhớ phân tán;

  • Mỗi bộ xử lý có các biến cục bộ riêng;

  • So với máy tính bộ nhớ dùng chung lớn, máy tính bộ nhớ phân tán ít tốn kém hơn.

Demerits of Message Passing Interface

  • Cần có nhiều thay đổi lập trình hơn đối với thuật toán song song;
  • Đôi khi khó gỡ lỗi; và
  • Không hoạt động tốt trong mạng giao tiếp giữa các nút.

Máy ảo song song (PVM)

PVM là một hệ thống truyền thông điệp di động, được thiết kế để kết nối các máy chủ không đồng nhất riêng biệt để tạo thành một máy ảo duy nhất. Nó là một tài nguyên máy tính song song có thể quản lý được. Các bài toán tính toán lớn như nghiên cứu siêu dẫn, mô phỏng động học phân tử và thuật toán ma trận có thể được giải quyết hiệu quả hơn về chi phí bằng cách sử dụng bộ nhớ và sức mạnh tổng hợp của nhiều máy tính. Nó quản lý tất cả việc định tuyến tin nhắn, chuyển đổi dữ liệu, lập lịch tác vụ trong mạng các kiến ​​trúc máy tính không tương thích.

Features of PVM

  • Rất dễ cài đặt và cấu hình;
  • Nhiều người dùng có thể sử dụng PVM cùng một lúc;
  • Một người dùng có thể thực thi nhiều ứng dụng;
  • Đó là một gói nhỏ;
  • Hỗ trợ C, C ++, Fortran;
  • Đối với một lần chạy chương trình PVM nhất định, người dùng có thể chọn nhóm máy;
  • Nó là một mô hình truyền thông điệp,
  • Tính toán dựa trên quy trình;
  • Hỗ trợ kiến ​​trúc không đồng nhất.

Lập trình song song dữ liệu

Trọng tâm chính của mô hình lập trình song song dữ liệu là thực hiện đồng thời các hoạt động trên một tập dữ liệu. Tập dữ liệu được tổ chức thành một số cấu trúc như mảng, siêu khối, v.v. Các bộ xử lý thực hiện các hoạt động tập thể trên cùng một cấu trúc dữ liệu. Mỗi tác vụ được thực hiện trên một phân vùng khác nhau của cùng một cấu trúc dữ liệu.

Nó là hạn chế, vì không phải tất cả các thuật toán đều có thể được chỉ định về tính song song dữ liệu. Đây là lý do tại sao song song dữ liệu không phải là phổ quát.

Các ngôn ngữ song song dữ liệu giúp chỉ định phân tách và ánh xạ dữ liệu tới các bộ xử lý. Nó cũng bao gồm các câu lệnh phân phối dữ liệu cho phép lập trình viên có quyền kiểm soát dữ liệu - ví dụ, dữ liệu nào sẽ đi trên bộ xử lý nào - để giảm lượng giao tiếp trong bộ xử lý.

Để áp dụng đúng bất kỳ thuật toán nào, điều rất quan trọng là bạn phải chọn một cấu trúc dữ liệu thích hợp. Đó là vì một thao tác cụ thể được thực hiện trên cấu trúc dữ liệu có thể mất nhiều thời gian hơn so với thao tác tương tự được thực hiện trên cấu trúc dữ liệu khác.

Example- Để truy cập phần tử thứ i trong một tập hợp bằng cách sử dụng một mảng, có thể mất một khoảng thời gian không đổi nhưng bằng cách sử dụng danh sách liên kết, thời gian cần thiết để thực hiện cùng một phép toán có thể trở thành một đa thức.

Do đó, việc lựa chọn cấu trúc dữ liệu phải được thực hiện khi xem xét kiến ​​trúc và kiểu hoạt động sẽ được thực hiện.

Các cấu trúc dữ liệu sau đây thường được sử dụng trong lập trình song song:

  • Danh sách liên kết
  • Arrays
  • Mạng siêu khối

Danh sách liên kết

Danh sách liên kết là cấu trúc dữ liệu có không hoặc nhiều nút được kết nối bằng con trỏ. Các nút có thể chiếm hoặc không các vị trí bộ nhớ liên tiếp. Mỗi nút có hai hoặc ba phần - mộtdata part lưu trữ dữ liệu và hai dữ liệu còn lại link fieldslưu trữ địa chỉ của nút trước đó hoặc nút tiếp theo. Địa chỉ của nút đầu tiên được lưu trữ trong một con trỏ bên ngoài được gọi làhead. Nút cuối cùng, được gọi làtail, thường không chứa bất kỳ địa chỉ nào.

Có ba loại danh sách được liên kết -

  • Danh sách liên kết Singly
  • Danh sách được liên kết gấp đôi
  • Danh sách liên kết hình tròn

Danh sách liên kết Singly

Một nút của danh sách liên kết đơn chứa dữ liệu và địa chỉ của nút tiếp theo. Một con trỏ bên ngoài được gọi làhead lưu trữ địa chỉ của nút đầu tiên.

Danh sách được liên kết gấp đôi

Một nút của danh sách được liên kết kép chứa dữ liệu và địa chỉ của cả nút trước và nút tiếp theo. Một con trỏ bên ngoài được gọi làhead lưu trữ địa chỉ của nút đầu tiên và con trỏ bên ngoài được gọi tail lưu trữ địa chỉ của nút cuối cùng.

Danh sách liên kết hình tròn

Một danh sách liên kết vòng rất giống với danh sách liên kết đơn ngoại trừ thực tế là nút cuối cùng đã lưu địa chỉ của nút đầu tiên.

Mảng

Mảng là một cấu trúc dữ liệu nơi chúng ta có thể lưu trữ các kiểu dữ liệu tương tự. Nó có thể là một chiều hoặc nhiều chiều. Mảng có thể được tạo tĩnh hoặc động.

  • Trong statically declared arrays, kích thước và kích thước của mảng được biết tại thời điểm biên dịch.

  • Trong dynamically declared arrays, thứ nguyên và kích thước của mảng được biết trong thời gian chạy.

Đối với lập trình bộ nhớ dùng chung, các mảng có thể được sử dụng như một bộ nhớ chung và đối với lập trình song song dữ liệu, chúng có thể được sử dụng bằng cách phân vùng thành các mảng con.

Mạng siêu khối

Kiến trúc siêu khối rất hữu ích cho các thuật toán song song mà mỗi tác vụ phải giao tiếp với các tác vụ khác. Cấu trúc liên kết siêu khối có thể dễ dàng nhúng các cấu trúc liên kết khác như vòng và lưới. Nó còn được gọi là n-cubes, trong đónlà số thứ nguyên. Một siêu khối có thể được xây dựng một cách đệ quy.

Lựa chọn một kỹ thuật thiết kế thích hợp cho một thuật toán song song là nhiệm vụ khó khăn và quan trọng nhất. Hầu hết các vấn đề lập trình song song có thể có nhiều hơn một giải pháp. Trong chương này, chúng ta sẽ thảo luận về các kỹ thuật thiết kế sau đây cho các thuật toán song song -

  • Phân chia và chinh phục
  • Phương pháp tham lam
  • Lập trình năng động
  • Backtracking
  • Chi nhánh & Giới hạn
  • Lập trình tuyến tính

Phương pháp phân chia và chinh phục

Trong cách tiếp cận chia để trị, bài toán được chia thành nhiều bài toán con nhỏ. Sau đó, các bài toán con được giải một cách đệ quy và kết hợp để có được lời giải của bài toán ban đầu.

Phương pháp phân chia và chinh phục bao gồm các bước sau ở mỗi cấp độ:

  • Divide - Bài toán ban đầu được chia thành các bài toán con.

  • Conquer - Các bài toán con được giải một cách đệ quy.

  • Combine - Các lời giải của các bài toán con được kết hợp với nhau để có được lời giải của bài toán ban đầu.

Phương pháp phân chia và chinh phục được áp dụng trong các thuật toán sau:

  • Tìm kiếm nhị phân
  • Sắp xếp nhanh chóng
  • Hợp nhất sắp xếp
  • Phép nhân số nguyên
  • Đảo ngược ma trận
  • Phép nhân ma trận

Phương pháp tham lam

Trong thuật toán tham lam của giải pháp tối ưu hóa, giải pháp tốt nhất được chọn bất cứ lúc nào. Một thuật toán tham lam rất dễ áp ​​dụng cho các bài toán phức tạp. Nó quyết định bước nào sẽ đưa ra giải pháp chính xác nhất trong bước tiếp theo.

Thuật toán này được gọi là greedybởi vì khi giải pháp tối ưu cho trường hợp nhỏ hơn được cung cấp, thuật toán không xem xét tổng thể chương trình như một tổng thể. Sau khi một giải pháp được xem xét, thuật toán tham lam không bao giờ xem xét lại cùng một giải pháp.

Một thuật toán tham lam hoạt động tạo ra một cách đệ quy một nhóm các đối tượng từ các phần thành phần nhỏ nhất có thể. Đệ quy là một thủ tục để giải quyết một vấn đề trong đó giải pháp cho một vấn đề cụ thể phụ thuộc vào giải pháp của ví dụ nhỏ hơn của vấn đề đó.

Lập trình năng động

Lập trình động là một kỹ thuật tối ưu hóa, chia vấn đề thành các vấn đề con nhỏ hơn và sau khi giải quyết từng vấn đề con, lập trình động kết hợp tất cả các giải pháp để có được giải pháp cuối cùng. Không giống như phương pháp chia và chinh phục, lập trình động sử dụng lại lời giải cho các bài toán con nhiều lần.

Thuật toán đệ quy cho Dòng Fibonacci là một ví dụ về lập trình động.

Thuật toán bẻ khóa

Backtracking là một kỹ thuật tối ưu hóa để giải quyết các vấn đề tổ hợp. Nó được áp dụng cho cả các bài toán lập trình và trong cuộc sống thực. Bài toán tám nữ hoàng, câu đố Sudoku và đi qua một mê cung là những ví dụ phổ biến trong đó thuật toán quay lui được sử dụng.

Trong backtracking, chúng tôi bắt đầu với một giải pháp khả thi, đáp ứng tất cả các điều kiện bắt buộc. Sau đó, chúng ta chuyển sang cấp độ tiếp theo và nếu cấp độ đó không tạo ra giải pháp thỏa đáng, chúng ta quay trở lại một cấp độ và bắt đầu với một tùy chọn mới.

Chi nhánh và ràng buộc

Thuật toán rẽ nhánh và ràng buộc là một kỹ thuật tối ưu hóa để có được giải pháp tối ưu cho vấn đề. Nó tìm kiếm giải pháp tốt nhất cho một vấn đề nhất định trong toàn bộ không gian của giải pháp. Các giới hạn trong chức năng cần tối ưu hóa được hợp nhất với giá trị của giải pháp tốt nhất mới nhất. Nó cho phép thuật toán hoàn toàn tìm thấy các phần của không gian giải pháp.

Mục đích của tìm kiếm nhánh và tìm kiếm ràng buộc là duy trì đường dẫn chi phí thấp nhất đến mục tiêu. Khi một giải pháp được tìm thấy, nó có thể tiếp tục cải tiến giải pháp. Tìm kiếm nhánh và liên kết được thực hiện trong tìm kiếm giới hạn sâu và tìm kiếm theo chiều sâu trước tiên.

Lập trình tuyến tính

Lập trình tuyến tính mô tả nhiều loại công việc tối ưu hóa trong đó cả tiêu chí tối ưu hóa và các ràng buộc đều là các hàm tuyến tính. Đó là một kỹ thuật để có được kết quả tốt nhất như lợi nhuận tối đa, con đường ngắn nhất hoặc chi phí thấp nhất.

Trong lập trình này, chúng ta có một tập hợp các biến và chúng ta phải gán giá trị tuyệt đối cho chúng để thỏa mãn một tập phương trình tuyến tính và để tối đa hóa hoặc tối thiểu hóa một hàm mục tiêu tuyến tính đã cho.

Ma trận là một tập hợp dữ liệu số và không số được sắp xếp theo một số hàng và cột cố định. Phép nhân ma trận là một thiết kế phép nhân quan trọng trong tính toán song song. Ở đây, chúng ta sẽ thảo luận về việc thực hiện phép nhân ma trận trên các mạng truyền thông khác nhau như mesh và hypercube. Mesh và hypercube có khả năng kết nối mạng cao hơn, vì vậy chúng cho phép giải thuật nhanh hơn các mạng khác như mạng vòng.

Mạng lưới

Cấu trúc liên kết trong đó tập hợp các nút tạo thành lưới p-chiều được gọi là cấu trúc liên kết lưới. Ở đây, tất cả các cạnh song song với trục lưới và tất cả các nút liền kề có thể giao tiếp với nhau.

Tổng số nút = (số nút trong hàng) × (số nút trong cột)

Một mạng lưới có thể được đánh giá bằng cách sử dụng các yếu tố sau:

  • Diameter
  • Chiều rộng vết nứt

Diameter - Trong một mạng lưới, dài nhất distancegiữa hai nút là đường kính của nó. Một mạng lưới p-chiều cókP các nút có đường kính là p(k–1).

Bisection width - Chiều rộng đường chia là số cạnh tối thiểu cần lấy ra khỏi một mạng để chia mạng mắt lưới thành hai nửa.

Phép nhân ma trận sử dụng mạng lưới

Chúng tôi đã xem xét mô hình SIMD mạng lưới 2D có kết nối bao quanh. Chúng tôi sẽ thiết kế một thuật toán để nhân hai mảng n × n bằng cách sử dụng n 2 bộ xử lý trong một khoảng thời gian cụ thể.

Ma trận A và B có các phần tử lần lượt là a ij và b ij . Phần tử xử lý PE ij biểu diễn a ij và b ij . Sắp xếp ma trận A và B sao cho mọi bộ xử lý đều có một cặp phần tử để nhân. Các phần tử của ma trận A sẽ di chuyển theo hướng trái và các phần tử của ma trận B sẽ di chuyển theo hướng lên. Những thay đổi này về vị trí của các phần tử trong ma trận A và B thể hiện mỗi phần tử xử lý, PE, một cặp giá trị mới để nhân.

Các bước trong thuật toán

  • Gán hai ma trận.
  • Tính tất cả các sản phẩm, a ik × b kj
  • Tính tổng khi bước 2 hoàn tất.

Thuật toán

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

Mạng siêu khối

Siêu hình lập phương là một cấu trúc n chiều trong đó các cạnh vuông góc với nhau và có cùng độ dài. Siêu hình lập phương n chiều còn được gọi là hình lập phương n hoặc hình lập phương n chiều.

Đặc điểm của Hypercube với 2 k nút

  • Đường kính = k
  • Chiều rộng đường phân giác = 2 k – 1
  • Số cạnh = k

Phép nhân ma trận sử dụng mạng siêu khối

Đặc điểm kỹ thuật chung của mạng Hypercube -

  • Để cho N = 2mlà tổng số bộ xử lý. Cho các bộ xử lý là P 0, P 1 … ..P N-1 .

  • Gọi i và i b là hai số nguyên, 0 <i, i b <N-1 và biểu diễn nhị phân của nó chỉ khác nhau ở vị trí b, 0 <b <k – 1.

  • Chúng ta hãy xem xét hai ma trận n × n, ma trận A và ma trận B.

  • Step 1- Các phần tử của ma trận A và ma trận B được gán cho n 3 bộ xử lý sao cho bộ xử lý ở vị trí i, j, k sẽ có a ji và b ik .

  • Step 2 - Tất cả bộ xử lý ở vị trí (i, j, k) tính toán sản phẩm

    C (i, j, k) = A (i, j, k) × B (i, j, k)

  • Step 3 - Tổng C (0, j, k) = ΣC (i, j, k) với 0 ≤ i ≤ n-1, trong đó 0 ≤ j, k <n – 1.

Ma trận khối

Ma trận khối hay ma trận phân vùng là ma trận mà mỗi phần tử tự nó đại diện cho một ma trận riêng lẻ. Các phần riêng lẻ này được gọi làblock hoặc là sub-matrix.

Thí dụ

Trong Hình (a), X là một ma trận khối trong đó A, B, C, D là chính ma trận. Hình (f) cho thấy ma trận tổng.

Phép nhân ma trận khối

Khi hai ma trận khối là ma trận vuông, thì chúng được nhân giống như cách chúng ta thực hiện phép nhân ma trận đơn giản. Ví dụ,

Sắp xếp là một quá trình sắp xếp các phần tử trong một nhóm theo một thứ tự cụ thể, tức là thứ tự tăng dần, thứ tự giảm dần, thứ tự bảng chữ cái, v.v. Ở đây chúng ta sẽ thảo luận về những điều sau:

  • Phân loại liệt kê
  • Sắp xếp chuyển vị chẵn lẻ
  • Sắp xếp hợp nhất song song
  • Sắp xếp siêu nhanh

Sắp xếp danh sách các phần tử là một hoạt động rất phổ biến. Thuật toán sắp xếp tuần tự có thể không đủ hiệu quả khi chúng ta phải sắp xếp một khối lượng dữ liệu khổng lồ. Do đó, các thuật toán song song được sử dụng trong việc sắp xếp.

Phân loại liệt kê

Sắp xếp kiểu liệt kê là một phương pháp sắp xếp tất cả các phần tử trong một danh sách bằng cách tìm vị trí cuối cùng của mỗi phần tử trong một danh sách đã sắp xếp. Nó được thực hiện bằng cách so sánh mỗi phần tử với tất cả các phần tử khác và tìm số phần tử có giá trị nhỏ hơn.

Do đó, với bất kỳ hai phần tử nào, a i và a j bất kỳ một trong các trường hợp sau phải đúng:

  • a i <a j
  • a i > a j
  • a i = a j

Thuật toán

procedure ENUM_SORTING (n)

begin
   for each process P1,j do
      C[j] := 0;
		
   for each process Pi, j do
	
      if (A[i] < A[j]) or A[i] = A[j] and i < j) then
         C[j] := 1;
      else
         C[j] := 0;
			
   for each process P1, j do
      A[C[j]] := A[j];
		
end ENUM_SORTING

Sắp xếp chuyển vị chẵn lẻ

Sắp xếp chuyển vị chẵn lẻ dựa trên kỹ thuật Sắp xếp bong bóng. Nó so sánh hai số liền kề và chuyển đổi chúng, nếu số đầu tiên lớn hơn số thứ hai để có được danh sách thứ tự tăng dần. Trường hợp ngược lại áp dụng cho chuỗi thứ tự giảm dần. Sắp xếp chuyển vị Lẻ-Chẵn hoạt động trong hai giai đoạn:odd phase và even phase. Trong cả hai giai đoạn, các quy trình trao đổi số với số liền kề của chúng ở bên phải.

Thuật toán

procedure ODD-EVEN_PAR (n) 

begin 
   id := process's label 
	
   for i := 1 to n do 
   begin 
	
      if i is odd and id is odd then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
      if i is even and id is even then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
   end for
	
end ODD-EVEN_PAR

Sắp xếp hợp nhất song song

Sắp xếp hợp nhất trước tiên chia danh sách chưa được sắp xếp thành các danh sách con nhỏ nhất có thể, so sánh nó với danh sách liền kề và hợp nhất nó theo thứ tự đã sắp xếp. Nó thực hiện song song rất độc đáo bằng cách tuân theo thuật toán chia và chinh phục.

Thuật toán

procedureparallelmergesort(id, n, data, newdata)

begin
   data = sequentialmergesort(data)
	
      for dim = 1 to n
         data = parallelmerge(id, dim, data)
      endfor
		
   newdata = data
end

Sắp xếp siêu nhanh

Sắp xếp siêu nhanh là một triển khai sắp xếp nhanh trên siêu khối. Các bước của nó như sau:

  • Chia danh sách chưa được sắp xếp cho mỗi nút.
  • Sắp xếp cục bộ từng nút.
  • Từ nút 0, phát giá trị trung bình.
  • Tách cục bộ từng danh sách, sau đó trao đổi các nửa theo thứ nguyên cao nhất.
  • Lặp lại bước 3 và bước 4 song song cho đến khi thứ nguyên về 0.

Thuật toán

procedure HYPERQUICKSORT (B, n)
begin

   id := process’s label;
	
   for i := 1 to d do
      begin
      x := pivot;
      partition B into B1 and B2 such that B1 ≤ x < B2;
      if ith bit is 0 then
		
      begin
         send B2 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B1 U C;
      endif
      
      else
         send B1 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B2 U C;
         end else
      end for
		
   sort B using sequential quicksort;
	
end HYPERQUICKSORT

Tìm kiếm là một trong những hoạt động cơ bản trong khoa học máy tính. Nó được sử dụng trong tất cả các ứng dụng mà chúng ta cần tìm xem một phần tử có trong danh sách đã cho hay không. Trong chương này, chúng ta sẽ thảo luận về các thuật toán tìm kiếm sau:

  • Phân chia và chinh phục
  • Tìm kiếm sâu-đầu tiên
  • Breadth-First Search
  • Tìm kiếm đầu tiên tốt nhất

Phân chia và chinh phục

Trong cách tiếp cận phân chia và chinh phục, vấn đề được chia thành nhiều vấn đề phụ nhỏ. Sau đó, các bài toán con được giải một cách đệ quy và kết hợp để có được lời giải của bài toán ban đầu.

Phương pháp phân chia và chinh phục bao gồm các bước sau ở mỗi cấp độ:

  • Divide - Bài toán ban đầu được chia thành các bài toán con.

  • Conquer - Các bài toán con được giải một cách đệ quy.

  • Combine - Các lời giải của các bài toán con được kết hợp với nhau để có được lời giải của bài toán ban đầu.

Tìm kiếm nhị phân là một ví dụ của thuật toán chia và chinh phục.

Mã giả

Binarysearch(a, b, low, high)

if low < high then
   return NOT FOUND
else
   mid ← (low+high) / 2
   if b = key(mid) then
      return key(mid)
   else if b < key(mid) then
      return BinarySearch(a, b, low, mid−1)
   else
   
      return BinarySearch(a, b, mid+1, high)

Tìm kiếm sâu-đầu tiên

Depth-First Search (hoặc DFS) là một thuật toán để tìm kiếm một cây hoặc một cấu trúc dữ liệu đồ thị vô hướng. Ở đây, khái niệm là bắt đầu từ nút bắt đầu được gọi làrootvà đi càng xa càng tốt trong cùng một nhánh. Nếu chúng ta nhận được một nút không có nút kế nhiệm, chúng ta quay lại và tiếp tục với đỉnh, đỉnh vẫn chưa được thăm.

Các bước tìm kiếm chuyên sâu-Đầu tiên

  • Xem xét một nút (gốc) chưa được truy cập trước đó và đánh dấu nó đã được truy cập.

  • Truy cập vào nút kế nhiệm liền kề đầu tiên và đánh dấu nó đã ghé thăm.

  • Nếu tất cả các nút kế thừa của nút được xem xét đã được truy cập hoặc nó không còn nút kế thừa nào nữa, hãy quay lại nút cha của nó.

Mã giả

Để cho v là đỉnh nơi bắt đầu tìm kiếm trong Đồ thị G.

DFS(G,v)

   Stack S := {};
	
   for each vertex u, set visited[u] := false;
   push S, v;
   while (S is not empty) do
     u := pop S;
	  
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbour w of u
            push S, w;
      end if
		
   end while
   
END DFS()

Breadth-First Search

Breadth-First Search (hoặc BFS) là một thuật toán để tìm kiếm một cây hoặc một cấu trúc dữ liệu đồ thị vô hướng. Ở đây, chúng ta bắt đầu với một nút và sau đó truy cập tất cả các nút liền kề trong cùng một cấp và sau đó chuyển đến nút kế tiếp liền kề trong cấp tiếp theo. Điều này còn được gọi làlevel-by-level search.

Các bước của Tìm kiếm theo chiều rộng-Đầu tiên

  • Bắt đầu với nút gốc, đánh dấu nó đã ghé thăm.
  • Vì nút gốc không có nút nào ở cùng cấp, hãy chuyển sang cấp tiếp theo.
  • Truy cập tất cả các nút lân cận và đánh dấu chúng đã được truy cập.
  • Chuyển đến cấp độ tiếp theo và truy cập tất cả các nút liền kề chưa được sử dụng.
  • Tiếp tục quá trình này cho đến khi tất cả các nút được truy cập.

Mã giả

Để cho v là đỉnh nơi bắt đầu tìm kiếm trong Đồ thị G.

BFS(G,v)

   Queue Q := {};
	
   for each vertex u, set visited[u] := false;
   insert Q, v;
   while (Q is not empty) do
      u := delete Q;
		
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbor w of u
            insert Q, w;
      end if
		
   end while
   
END BFS()

Tìm kiếm đầu tiên tốt nhất

Best-First Search là một thuật toán duyệt qua biểu đồ để đạt được mục tiêu theo con đường ngắn nhất có thể. Không giống như BFS và DFS, Best-First Search tuân theo một chức năng đánh giá để xác định nút nào là thích hợp nhất để đi qua tiếp theo.

Các bước của Tìm kiếm Đầu tiên Tốt nhất

  • Bắt đầu với nút gốc, đánh dấu nó đã ghé thăm.
  • Tìm nút thích hợp tiếp theo và đánh dấu nó đã truy cập.
  • Đi đến cấp độ tiếp theo và tìm nút thích hợp và đánh dấu nó đã truy cập.
  • Tiếp tục quá trình này cho đến khi đạt được mục tiêu.

Mã giả

BFS( m )

   Insert( m.StartNode )
   Until PriorityQueue is empty
      c ← PriorityQueue.DeleteMin
      If c is the goal
      Exit
   Else
   
      Foreach neighbor n of c
         If n "Unvisited"
            Mark n "Visited"
            Insert( n )
      Mark c "Examined"
      
End procedure

Biểu đồ là một ký hiệu trừu tượng được sử dụng để biểu diễn kết nối giữa các cặp đối tượng. Một biểu đồ bao gồm -

  • Vertices- Các đối tượng liên kết với nhau trong một đồ thị được gọi là các đỉnh. Dọc còn được gọi lànodes.

  • Edges - Cạnh là liên kết nối các đỉnh.

Có hai loại đồ thị -

  • Directed graph - Trong đồ thị có hướng, các cạnh có hướng, tức là các cạnh đi từ đỉnh này sang đỉnh khác.

  • Undirected graph - Trong đồ thị vô hướng, các cạnh không có hướng.

Tô màu đồ thị

Tô màu đồ thị là phương pháp gán màu cho các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau nào có cùng màu. Một số vấn đề về tô màu đồ thị là -

  • Vertex coloring - Cách tô màu các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau nào cùng màu.

  • Edge Coloring - Là phương pháp gán một màu cho từng cạnh sao cho không có hai cạnh liền nhau nào có cùng màu.

  • Face coloring - Nó chỉ định màu cho từng mặt hoặc từng vùng của đồ thị phẳng sao cho không có hai mặt có chung đường biên nào có cùng màu.

Số màu

Số màu là số màu tối thiểu cần thiết để tô màu một biểu đồ. Ví dụ, số màu của đồ thị sau là 3.

Khái niệm tô màu đồ thị được áp dụng trong việc chuẩn bị thời gian biểu, ấn định tần số vô tuyến điện thoại di động, Suduku, phân bổ thanh ghi và tô màu bản đồ.

Các bước để tô màu đồ thị

  • Đặt giá trị ban đầu của mỗi bộ xử lý trong mảng n chiều thành 1.

  • Bây giờ để gán một màu cụ thể cho một đỉnh, hãy xác định xem màu đó đã được gán cho các đỉnh liền kề hay chưa.

  • Nếu một bộ xử lý phát hiện cùng một màu trong các đỉnh liền kề, nó sẽ đặt giá trị của nó trong mảng thành 0.

  • Sau khi thực hiện n 2 so sánh, nếu bất kỳ phần tử nào của mảng là 1 thì đó là màu hợp lệ.

Mã giả để tô màu đồ thị

begin

   create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
   status[i0,..in-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if aj,k=1 and ij=ikthen
            status[i0,..in-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

Cây kéo dài tối thiểu

Cây khung có tổng trọng lượng (hoặc chiều dài) của tất cả các cạnh của nó nhỏ hơn tất cả các cây khung có thể có khác của đồ thị G được gọi là minimal spanning tree hoặc là minimum cost spanningcây. Hình sau cho thấy một đồ thị liên thông có trọng số.

Một số cây khung có thể có của biểu đồ trên được hiển thị bên dưới:

Trong số tất cả các cây khung ở trên, hình (d) là cây khung tối thiểu. Khái niệm cây bao trùm chi phí tối thiểu được áp dụng trong bài toán nhân viên bán hàng đi du lịch, thiết kế mạch điện tử, Thiết kế mạng hiệu quả và thiết kế các thuật toán định tuyến hiệu quả.

Để triển khai cây bao trùm chi phí tối thiểu, hai phương pháp sau được sử dụng:

  • Thuật toán của Prim
  • Thuật toán Kruskal

Thuật toán của Prim

Thuật toán của Prim là một thuật toán tham lam, giúp chúng ta tìm cây bao trùm tối thiểu cho một đồ thị vô hướng có trọng số. Nó chọn một đỉnh đầu tiên và tìm một cạnh có trọng số nhỏ nhất trên đỉnh đó.

Các bước của thuật toán Prim

  • Chọn một đỉnh bất kỳ, ví dụ v 1 của Đồ thị G.

  • Chọn một cạnh, giả sử e 1 của G sao cho e 1 = v 1 v 2 và v 1 ≠ v 2 và e 1 có trọng số nhỏ nhất trong số các cạnh trùng nhau trên v 1 trong đồ thị G.

  • Bây giờ, theo bước 2, chọn sự cố cạnh có trọng số nhỏ nhất trên v 2 .

  • Tiếp tục điều này cho đến khi n – 1 cạnh đã được chọn. Đâyn là số đỉnh.

Cây bao trùm tối thiểu là -

Thuật toán Kruskal

Thuật toán của Kruskal là một thuật toán tham lam, giúp chúng ta tìm cây bao trùm tối thiểu cho một đồ thị có trọng số được kết nối, thêm các cung chi phí ngày càng tăng ở mỗi bước. Đây là một thuật toán cây bao trùm tối thiểu để tìm một cạnh có trọng lượng nhỏ nhất có thể có thể kết nối hai cây bất kỳ trong rừng.

Các bước của thuật toán Kruskal

  • Chọn một cạnh có trọng lượng tối thiểu; nói e 1 của Đồ thị G và e 1 không phải là một vòng lặp.

  • Chọn cạnh có trọng số nhỏ nhất tiếp theo được kết nối với e 1 .

  • Tiếp tục điều này cho đến khi n – 1 cạnh đã được chọn. Đâyn là số đỉnh.

Cây bao trùm tối thiểu của biểu đồ trên là -

Thuật toán đường dẫn ngắn nhất

Thuật toán Đường đi ngắn nhất là một phương pháp tìm đường đi có chi phí thấp nhất từ ​​nút nguồn (S) đến nút đích (D). Ở đây, chúng ta sẽ thảo luận về thuật toán Moore, còn được gọi là Thuật toán tìm kiếm đầu tiên theo chiều rộng.

Thuật toán Moore

  • Gắn nhãn đỉnh nguồn, S và gắn nhãn nó i và thiết lập i=0.

  • Tìm tất cả các đỉnh không được gắn nhãn liền kề với đỉnh có nhãn i. Nếu không có đỉnh nào được nối với đỉnh, S, thì đỉnh, D, không được nối với S. Nếu có đỉnh nào được nối với S, hãy gắn nhãn chúngi+1.

  • Nếu D được gắn nhãn thì chuyển sang bước 4, còn lại chuyển sang bước 2 để tăng i = i + 1.

  • Dừng lại sau khi tìm được đoạn đường ngắn nhất.

ja/tutorial
es/tutorial
de/tutorial
fr/tutorial
th/tutorial
pt/tutorial
ru/tutorial
vi/tutorial
it/tutorial
ko/tutorial
tr/tutorial
id/tutorial
pl/tutorial
hi/tutorial
japost
espost
depost
frpost
thpost
ptpost
rupost
vipost
itpost
kopost
trpost
idpost
plpost
hipost

© Copyright 2021 - 2024 | All Rights Reserved