даже те последовательные алгоритмы, которые по сути итерационны, т. е. выполняются пошагово при реализации на однопроцессорном компьютере, могут быть эффективно распараллелены для выполнения на многопроцессорных машинах. В этой статье был рассмотрен один из алгоритмов нахождения минимального остовного дерева – алгоритм Прима. Мы обсудили последовательный и параллельный варианты этого алгоритма и могли увидеть, что второй алгоритм имеет лучшее время выполнения, а именно Θ(n2/p) + Θ(n log p), против времени (n2) последовательной реализации, где n – количество вершин исходного графа, p – число используемых процессоров. В целом, распараллеливание алгоритмов является весьма перспективным направлением современной вычислительной науки в связи с распространением многопроцессорных компьютеров и с тем, что может быть достигнуто гораздо более хорошее время выполнения алгоритмов на таких машинах по сравнению с последовательными вариантами этих же алгоритмов.




Проблемы с карьерой, не ценят на работе, маленькая зарплата? Есть выход! Теперь каждый желающий может купить документ о повышении квалификации, качественно изготовленный, по умеренным тарифам. Купить удостоверение о повышении квалификации - это простой выход из сложной ситуации!