Thuật toán song song - Phân tích

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ị nhớ phức tạp với chi phí hợp lý, không gian lưu trữ không còn là vấn đề nữa. 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ừ thời điểm thuật toán bắt đầu thực thi đến thời điểm dừng. Nếu tất cả các bộ xử lý không bắt đầu hoặc kết thúc việ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 Big O
Ký hiệu Omega
Ký hiệu Theta

Ký hiệu Big O

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. 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 việc thực thi. Hàm -

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

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

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à n₀ như vậy mà f(n) ≥ c * g(n) cho tất cả n Ở đâu n ≥ n₀.

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 c₁, c₂, và n₀ sao cho c1 * g (n) ≤ f (n) ≤ c2 * g (n) với mọi n Ở đâu n ≥ n₀.

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ăng tốc được định nghĩa là tỷ số giữa thời gian thực hiện trong 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 trong 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 xấu nhất của tuần 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à vận hành 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 một vấn đề càng lớn thì kết quả thu được càng tốn kém.