Распараллелить уже линейно-временной алгоритм

Question

На практике, есть ли случай, когда уже линейно-временной алгоритм должен быть распараллелен? Мой учитель утверждает, что это не стоит, но я не верю.

Answer 1

Ваш учитель ошибается.Сложность времени выполнения (O (n), O (log n) и т. Д.) Алгоритма с одним ЦП не имеет отношения к тому, выиграет ли он от распараллеливания.

Изменение кода при использовании1 CPU для использования K CPU в лучшем случае разделит время выполнения на коэффициент K. Поскольку вы не можете произвольно создавать CPU из воздуха, K фактически является постоянной величиной.Таким образом, сложность во время выполнения не зависит от распараллеливания.Все, на что вы можете надеяться, это получить постоянное улучшение фактора.

Это не означает, что делать это не стоит - в некоторых случаях двукратное улучшение чрезвычайно полезно.Кроме того, в массивно параллельной системе с тысячами процессоров эта константа становится довольно большой.

Answer 2

Определенно ДА.Графические карты обеспечивают параллелизм, а переключение с центрального процессора на параллельное вычисление на графическом процессоре может сэкономить много времени.Алгоритм линейного времени может иметь значительное ускорение при параллельном выполнении.См. GPGPU и раздел «Приложения» или Google для «вычисления графической карты».

Хотя вы не спрашивали, ответ в теории также определенно да,есть класс сложности NC для задач, которые могут быть «эффективно распараллелены» (могут быть решены за логарифмическое время с учетом полиномиального числа процессоров), и «P-полные» задачи, которые могут быть решены за полиномиальное время, но предположительно не будутв NC.(точно так же, как есть проблемы P и NP-complete, и предполагается, что NP-complete не находятся в P)

Answer 3

Я тоже не согласен с вашим учителем. Я утверждаю, что многие из алгоритмов, которые работают на MapReduce , являются алгоритмами с линейным временем.

Например, индексирование, просмотр множества html-страниц (например, всех страниц в википедии) и поиск определенных слов - это алгоритм, который является линейным при вводе. Тем не менее, вы не можете запустить его без параллелизма.

Answer 4

Если учить одноядерный, одноядерный процессор, среду с одним компьютером и задачу, связанную с процессором, ваш учитель прав.(хотя можно утверждать, что в этом случае, даже если вы работаете с несколькими потоками, они на самом деле не работают параллельно, просто учитывая иллюзию параллельной работы)

Однако в наши дни одноядерные системыредко, даже многие смартфоны переходят на многоядерные, поэтому на практике вы, вероятно, выиграете от распараллеливания.Я говорю, вероятно, потому что, если задачи небольшие, стоимость создания потока будет выше, чем выгода, также есть переключение контекста, которое стоит процессорных циклов.Если не сделать это с умом, всегда есть вероятность, что выполнение параллельной операции фактически замедлит ее.

Answer 5

Учитывая достаточно большой ввод, оно стоит .Всегда.

Пример. Наивный алгоритм поиска наибольшего числа в неупорядоченном «Списке» просто пересекает список.Чтобы найти запись, потребуется время O(n).

Это нормально, если у вас 100 или 1000 записей.

Что если у вас миллиард записей?Вы разделяете список на несколько процессоров, каждый находит максимум, и у вас появляется новый меньший список для работы.Вы можете разделить это снова => Параллельно, и быстрее.Я полагаю, что O(log(n)), если вы эффективно разделите и уменьшите, и имеют n процессоров .

Дело в том, что если ваш ввод достаточно большой, O(n) недостаточно хорошВ зависимости от того, что нужно сделать, O (n) может вырасти до слишком большого количества секунд, минут, часов по сравнению с тем, что вы хотели бы.

Примечание: Когда я говорю O(n) или O(log(n)) выше, яссылаясь на время, необходимое для завершения поиска.то есть не 'общая работа', выполняемая всеми процессорами.Обычно распараллеливание алгоритма несколько увеличивает общую работу, выполняемую процессорами.