Параллельный алгоритм - Parallel algorithm


Из Википедии, свободной энциклопедии

В информатике , в параллельном алгоритме , в отличие от традиционного последовательного алгоритма , является алгоритм , который может быть выполнен кусок в то время , на многих различных устройствах обработки, а затем объединяется вместе снова в конце , чтобы получить правильный результат.

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

параллелизуемости

Алгоритмы существенно различаются как параллелизуемыми они, начиная от легко параллелизуемые полностью unparallelizable. Кроме того, данная проблема может приспособить различные алгоритмы, которые могут быть более или менее параллелизуемым.

Некоторые проблемы легко разделить на части таким образом , - это называется ошеломляюще параллельных задач . Алгоритмы также используются для таких вещей, как решение Кубики Рубика и для хэш - дешифрования.

Некоторые проблемы не могут быть разделены на параллельные участки, так как они требуют результатов из предыдущего шага , чтобы эффективно вести к следующему шагу - они называются по своей сути последовательной проблемы с . Примеры включают в себя итеративные численные методы , такие как метод Ньютона , итерационные решения для задачи трех тел , и большинство из доступных алгоритмов для вычисления пи (П).

мотивация

Параллельные алгоритмы на отдельные устройства становятся все более распространенным , так как в начале 2000 - х годов из - за существенных улучшений в многопроцессорных системах и рост многоядерных процессоров. Вплоть до конца 2004 года, одноядерный производительность процессора быстро увеличивается с помощью частотного масштабирования , и , таким образом , чтобы легче было построить компьютер с помощью одного быстрого ядра , чем один со многими более медленных ядер с одной и той же пропускной способности , так что многоядерные системы были более ограничены использовать. С 2004 года однако, масштабирование частоты врезался в стену, и , таким образом , многоядерные системы становятся все более широкое распространение, что делает параллельные алгоритмы более общего пользования.

вопросы

связь

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

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

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

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

Балансировки нагрузки

Еще одна проблема , с параллельными алгоритмами гарантирует , что они надлежащим образом балансировка нагрузки , гарантируя , что нагрузка ( в целом работу) сбалансирован, а не размер входного быть сбалансированным. Например, проверяя все числа от одного до ста тысяч для простоты легко разделить между процессорами; Однако, если эти номера просто разделить равномерно (1-1000, 1,001-2,000 и т.д.), объем работ будет несбалансированным, поскольку меньшее число легче обрабатывать с помощью этого алгоритма (проще для проверки простоты), и Таким образом , некоторые процессоры получат больше работы , чтобы сделать , чем другие, которые не будут сидеть без дела до загруженных процессоров в комплекте.

Распределенные алгоритмы

Подтип параллельных алгоритмов, распределенные алгоритмы алгоритмы , предназначенные для работы в кластерных вычислений и распределенных вычислительных средах, где дополнительные проблемы выходит за рамки «классических» параллельных алгоритмов должны быть решены.

Смотрите также

Рекомендации

внешняя ссылка