Параллельные вычисления - Parallel computing

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

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

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

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

Теоретическая верхняя граница на Ускорить одной программы в результате распараллеливания определяется законом Амдаля .

Фон

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

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

Масштабирование частоты было основной причиной улучшения производительности компьютеров с середины 1980-х до 2004 года. Время выполнения программы равно количеству инструкций, умноженному на среднее время выполнения одной инструкции. Сохраняя все остальное постоянным, увеличение тактовой частоты уменьшает среднее время, необходимое для выполнения инструкции. Таким образом, увеличение частоты сокращает время выполнения всех программ с привязкой к вычислениям . Однако потребляемая мощность P микросхемой определяется уравнением P = C × V 2 × F , где C - это емкость , переключаемая за тактовый цикл (пропорциональная количеству транзисторов, входы которых изменяются), V - напряжение , а F - частота процессора (циклов в секунду). Увеличение частоты увеличивает количество энергии, потребляемой процессором. Повышение энергопотребления процессоров в конечном итоге привело к отмене Intel 8 мая 2004 года своих процессоров Tejas и Jayhawk , что обычно считается концом масштабирования частот как доминирующей парадигмы компьютерной архитектуры.

Чтобы решить проблему энергопотребления и перегрева, производители основных центральных процессоров (ЦП или процессоров) начали производить энергоэффективные процессоры с несколькими ядрами. Ядро - это вычислительная единица процессора, а в многоядерных процессорах каждое ядро ​​является независимым и может одновременно обращаться к одной и той же памяти. Многоядерные процессоры принесли параллельные вычисления на настольные компьютеры . Таким образом, распараллеливание последовательных программ стало основной задачей программирования. В 2012 году четырехъядерные процессоры стали стандартом для настольных компьютеров , в то время как серверы имеют 10- и 12-ядерные процессоры. Из закона Мура можно предсказать, что количество ядер на процессор будет удваиваться каждые 18–24 месяца. Это может означать, что после 2020 года типичный процессор будет иметь десятки или сотни ядер.

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

Закон Амдала и закон Густафсона

Графическое представление закона Амдала . Ускорение программы от распараллеливания ограничено тем, какая часть программы может быть распараллелена. Например, если 90% программы можно распараллелить, теоретическое максимальное ускорение с использованием параллельных вычислений будет в 10 раз, независимо от того, сколько процессоров используется.
Предположим , что задача состоит из двух независимых частей, A и B . Часть B занимает примерно 25% времени всего вычисления. Очень усердно работая, можно сделать эту часть в 5 раз быстрее, но это лишь немного сократит время для всего вычисления. Напротив, может потребоваться меньше работы, чтобы сделать часть A вдвое быстрее. Это сделает вычисления намного быстрее, чем при оптимизации части B , даже несмотря на то, что ускорение части B в соотношении больше (в 5 раз против 2 раз).

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

Потенциальное ускорение алгоритма на платформе параллельных вычислений определяется законом Амдала.

куда

  • S латентный потенциал убыстрение в латентности исполнения всей задачи;
  • s - ускорение задержки выполнения распараллеливаемой части задачи;
  • p - процент времени выполнения всей задачи относительно распараллеливаемой части задачи до распараллеливания .

Поскольку задержка S <1 / (1 - p ) , это показывает, что небольшая часть программы, которая не может быть распараллелена, ограничит общее ускорение, доступное от распараллеливания. Программа, решающая большие математические или инженерные задачи, обычно состоит из нескольких распараллеливаемых частей и нескольких непараллелизируемых (последовательных) частей. Если на непараллелизируемую часть программы приходится 10% времени выполнения ( p = 0,9), мы можем получить ускорение не более чем в 10 раз, независимо от того, сколько процессоров добавлено. Это устанавливает верхний предел полезности добавления дополнительных модулей параллельного выполнения. «Когда задача не может быть разделена из-за ограничений последовательности, приложение дополнительных усилий не влияет на расписание. Рождение ребенка занимает девять месяцев, независимо от того, сколько женщин назначено».

Графическое представление закона Густафсона

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

И закон Амдала, и закон Густафсона предполагают, что время работы последовательной части программы не зависит от количества процессоров. Закон Амдала предполагает, что вся проблема имеет фиксированный размер, так что общий объем работы, которая должна выполняться параллельно, также не зависит от количества процессоров , тогда как закон Густафсона предполагает, что общий объем работы, которая должна выполняться параллельно, изменяется линейно с количество процессоров .

Зависимости

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

Пусть P i и P j - два программных сегмента. Условия Бернштейна описывают, когда они независимы и могут выполняться параллельно. Для P i пусть I i будет всеми входными переменными, а O i - выходными переменными, и аналогично для P j . P i и P j независимы, если они удовлетворяют

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

Рассмотрим следующие функции, демонстрирующие несколько видов зависимостей:

1: function Dep(a, b)
2: c := a * b
3: d := 3 * c
4: end function

В этом примере команда 3 не может быть выполнена до (или даже параллельно) с инструкцией 2, потому что инструкция 3 использует результат из инструкции 2. Она нарушает условие 1 и, таким образом, вводит зависимость потока.

1: function NoDep(a, b)
2: c := a * b
3: d := 3 * b
4: e := a + b
5: end function

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

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

Условия гонки, взаимное исключение, синхронизация и параллельное замедление

Подзадачи в параллельной программе часто называют потоками . Некоторые параллельные компьютерные архитектуры используют меньшие, облегченные версии потоков, известные как волокна , в то время как другие используют более крупные версии, известные как процессы . Однако «потоки» обычно считаются общим термином для подзадач. Потоки часто нуждаются в синхронизированном доступе к объекту или другому ресурсу , например, когда они должны обновить переменную, которая является общей для них. Без синхронизации инструкции между двумя потоками могут чередоваться в любом порядке. Например, рассмотрим следующую программу:

Поток А Резьба B
1A: чтение переменной V 1B: чтение переменной V
2A: добавить 1 к переменной V 2B: добавить 1 к переменной V
3A: обратная запись в переменную V 3B: обратная запись в переменную V

Если инструкция 1B выполняется между 1A и 3A, или если инструкция 1A выполняется между 1B и 3B, программа выдаст неверные данные. Это известно как состояние гонки . Программист должен использовать блокировку для обеспечения взаимного исключения . Блокировка - это конструкция языка программирования, которая позволяет одному потоку управлять переменной и предотвращать ее чтение или запись другими потоками до тех пор, пока эта переменная не будет разблокирована. Поток, удерживающий блокировку, может выполнить свой критический раздел (раздел программы, требующий монопольного доступа к некоторой переменной) и разблокировать данные по завершении. Следовательно, чтобы гарантировать правильное выполнение программы, указанная выше программа может быть переписана для использования блокировок:

Поток А Резьба B
1A: заблокировать переменную V 1B: заблокировать переменную V
2A: чтение переменной V 2B: чтение переменной V
3A: добавить 1 к переменной V 3B: добавить 1 к переменной V
4A: обратная запись в переменную V 4B: обратная запись в переменную V
5A: переменная разблокировки V 5B: переменная разблокировки V

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

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

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

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

Мелкозернистый, крупнозернистый и неприятный параллелизм

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

Таксономия Флинна

Майкл Дж. Флинн создал одну из самых ранних систем классификации для параллельных (и последовательных) компьютеров и программ, теперь известную как таксономия Флинна . Флинн классифицировал программы и компьютеры по тому, работали ли они с одним набором или с несколькими наборами инструкций, и использовали ли эти инструкции один набор или несколько наборов данных.

Классификация «одна команда - одни данные» (SISD) эквивалентна полностью последовательной программе. Классификация «одна инструкция - несколько данных» (SIMD) аналогична многократному выполнению одной и той же операции над большим набором данных. Обычно это делается в приложениях обработки сигналов . Множественные инструкции-одиночные данные (MISD) - это редко используемая классификация. Несмотря на то, что для решения этой проблемы были разработаны компьютерные архитектуры (например, систолические массивы ), появилось мало приложений, подходящих для этого класса. Программы с множеством инструкций и множеством данных (MIMD) на сегодняшний день являются наиболее распространенным типом параллельных программ.

По словам Дэвида А. Паттерсона и Джона Л. Хеннесси : «Некоторые машины, конечно, являются гибридами этих категорий, но эта классическая модель сохранилась, потому что она проста, легка для понимания и дает хорошее первое приближение. Это также - возможно, из-за его понятности - наиболее широко используемой схемы ».

Типы параллелизма

Битовый параллелизм

Taiwania 3 of Taiwan , параллельное суперкомпьютерное устройство, присоединившееся к исследованию COVID-19 .

С момента появления технологии изготовления компьютерных микросхем очень крупномасштабной интеграции (СБИС) в 1970-х и примерно до 1986 года ускорение компьютерной архитектуры было обусловлено удвоением размера компьютерного слова - объема информации, которым процессор может управлять за цикл. Увеличение размера слова уменьшает количество инструкций, которые процессор должен выполнить, чтобы выполнить операцию с переменными, размер которых превышает длину слова. Например, если 8-битный процессор должен сложить два 16-битных целых числа , процессор должен сначала добавить 8 младших битов из каждого целого числа, используя стандартную инструкцию сложения, а затем добавить 8 старших битов, используя сложение с - инструкция переноса и бит переноса из сложения более низкого порядка; таким образом, 8-битный процессор требует двух инструкций для выполнения одной операции, тогда как 16-битный процессор сможет завершить операцию с помощью одной инструкции.

Исторически 4-битные микропроцессоры были заменены 8-битными, затем 16-битными, затем 32-битными микропроцессорами. Эта тенденция в целом закончилась с появлением 32-разрядных процессоров, которые были стандартом в вычислениях общего назначения в течение двух десятилетий. Только в начале 2000-х, с появлением архитектур x86-64 , 64-битные процессоры стали обычным явлением.

Параллелизм на уровне инструкций

Канонический процессор без конвейера . Для выполнения одной инструкции требуется пять тактовых циклов, и, таким образом, процессор может выдавать субскалярную производительность ( IPC = 0,2 <1 ).

Компьютерная программа - это, по сути, поток инструкций, выполняемых процессором. Без параллелизма на уровне команд процессор может выдавать только менее одной инструкции за такт ( IPC <1 ). Эти процессоры известны как субскалярные процессоры. Эти инструкции можно переупорядочить и объединить в группы, которые затем выполняются параллельно без изменения результата программы. Это называется параллелизмом на уровне инструкций. Достижения в области параллелизма на уровне команд доминировали в компьютерной архитектуре с середины 1980-х до середины 1990-х годов.

Канонический пятиступенчатый конвейерный процессор. В лучшем случае для выполнения одной инструкции требуется один тактовый цикл, и, таким образом, процессор может выдавать скалярную производительность ( IPC = 1 ).

Все современные процессоры имеют многоступенчатые конвейеры команд . Каждый этап конвейера соответствует отдельному действию, которое процессор выполняет над этой инструкцией на этом этапе; процессор с N- ступенчатым конвейером может иметь до N различных инструкций на разных этапах завершения и, таким образом, может выдавать одну инструкцию за такт ( IPC = 1 ). Эти процессоры известны как скалярные процессоры. Каноническим примером конвейерного процессора является процессор RISC с пятью этапами: выборка инструкций (IF), декодирование инструкций (ID), выполнение (EX), доступ к памяти (MEM) и обратная запись в регистр (WB). Процессор Pentium 4 имел 35-ступенчатый конвейер.

Канонический пятиступенчатый конвейерный процессор с двумя исполнительными блоками. В лучшем случае для выполнения двух инструкций требуется один тактовый цикл, и, таким образом, процессор может обеспечить суперскалярную производительность ( IPC = 2> 1 ).

Большинство современных процессоров также имеют несколько исполнительных блоков . Обычно они сочетают эту функцию с конвейерной обработкой и, таким образом, могут выдавать более одной инструкции за такт ( IPC> 1 ). Эти процессоры известны как суперскалярные процессоры. Суперскалярные процессоры отличаются от многоядерных процессоров тем, что несколько исполнительных блоков не являются целыми процессорами (то есть процессорами). Инструкции можно сгруппировать, только если между ними нет зависимости данных . Табло и алгоритм Томасуло (который похож на табло, но использует переименование регистров ) - два наиболее распространенных метода для реализации выполнения вне очереди и параллелизма на уровне команд.

Параллелизм задач

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

Параллелизм на уровне сверхслова

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

Аппаратное обеспечение

Память и общение

Основная память в параллельном компьютере - это либо общая память (совместно используемая всеми обрабатывающими элементами в едином адресном пространстве ), либо распределенная память (в которой каждый обрабатывающий элемент имеет собственное локальное адресное пространство). Распределенная память относится к тому факту, что память распределена логически, но часто подразумевает, что она также распределена физически. Распределенная разделяемая память и виртуализация памяти сочетают в себе два подхода, при которых у обрабатывающего элемента есть собственная локальная память и доступ к памяти на нелокальных процессорах. Доступ к локальной памяти обычно быстрее, чем доступ к нелокальной памяти. На суперкомпьютерах распределенное пространство разделяемой памяти может быть реализовано с использованием такой модели программирования, как PGAS . Эта модель позволяет процессам на одном вычислительном узле получать прозрачный доступ к удаленной памяти другого вычислительного узла. Все вычислительные узлы также подключены к внешней системе с общей памятью через высокоскоростное соединение, такое как Infiniband , эта внешняя система с общей памятью известна как пакетный буфер , который обычно строится из массивов энергонезависимой памяти, физически распределенной по нескольким I / O узлов.

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

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

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

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

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

Классы параллельных компьютеров

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

Многоядерные вычисления

Многоядерный процессор - это процессор, который включает в себя несколько блоков обработки (называемых «ядрами») на одном кристалле. Этот процессор отличается от суперскалярного процессора, который включает в себя несколько исполнительных блоков и может выдавать несколько инструкций за такт из одного потока инструкций (потока); Напротив, многоядерный процессор может выдавать несколько инструкций за такт из нескольких потоков инструкций. IBM «ы сотовый микропроцессор , предназначенный для использования в Sony PlayStation 3 , является известным многоядерным процессором. Каждое ядро ​​многоядерного процессора потенциально также может быть суперскалярным, то есть в каждом тактовом цикле каждое ядро ​​может выдавать несколько инструкций из одного потока.

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

Симметричная многопроцессорная обработка

Симметричный мультипроцессор (SMP) - это компьютерная система с несколькими идентичными процессорами, которые совместно используют память и подключаются через шину . Конкуренция шины препятствует масштабированию архитектуры шины. В результате SMP обычно состоят не более чем из 32 процессоров. Из-за небольшого размера процессоров и значительного снижения требований к полосе пропускания шины, достигаемого за счет больших кэш-памяти, такие симметричные мультипроцессоры чрезвычайно рентабельны при условии наличия достаточной полосы пропускания памяти.

Распределенных вычислений

Распределенный компьютер (также известный как мультипроцессор с распределенной памятью) - это компьютерная система с распределенной памятью, в которой элементы обработки соединены сетью. Распределенные компьютеры обладают высокой масштабируемостью. Термины « параллельные вычисления », «параллельные вычисления» и «распределенные вычисления» во многом пересекаются, и между ними нет четкого различия. Одну и ту же систему можно охарактеризовать как «параллельную» и «распределенную»; процессоры в типичной распределенной системе работают одновременно, параллельно.

Кластерные вычисления

Кластер - это группа слабо связанных компьютеров, которые тесно взаимодействуют друг с другом, поэтому в некоторых отношениях их можно рассматривать как единый компьютер. Кластеры состоят из нескольких автономных машин, соединенных сетью. Хотя машины в кластере не обязательно должны быть симметричными, балансировка нагрузки в противном случае затруднена. Наиболее распространенным типом кластера является кластер Beowulf , который представляет собой кластер, реализованный на нескольких идентичных коммерческих готовых компьютерах, подключенных к локальной сети TCP / IP Ethernet . Технология Беовульф была первоначально разработана Томасом Стерлингом и Дональдом Беккером . 87% всех суперкомпьютеров Top500 - это кластеры. Остальные - это массивно-параллельные процессоры, описание которых приводится ниже.

Поскольку системы грид-вычислений (описанные ниже) могут легко справляться с досадно параллельными проблемами, современные кластеры обычно предназначены для решения более сложных проблем - проблем, которые требуют от узлов более частого обмена промежуточными результатами друг с другом. Для этого требуется широкая полоса пропускания и, что более важно, сеть межсоединений с малой задержкой . Многие старые и современные суперкомпьютеры используют специализированное высокопроизводительное сетевое оборудование, специально разработанное для кластерных вычислений, такое как сеть Cray Gemini. По состоянию на 2014 год в большинстве современных суперкомпьютеров используется стандартное сетевое оборудование, часто Myrinet , InfiniBand или Gigabit Ethernet .

Массивно-параллельные вычисления
Шкаф от IBM «s Blue Gene / L массивно параллельных суперкомпьютеров

Процессор с массовым параллелизмом (MPP) - это отдельный компьютер с множеством сетевых процессоров. MPP имеют многие из тех же характеристик, что и кластеры, но MPP имеют специализированные сети межсоединений (тогда как кластеры используют обычное оборудование для сетей). MPP также имеют тенденцию быть больше, чем кластеры, обычно с «гораздо большим количеством», чем 100 процессоров. В MPP «каждый ЦП содержит свою собственную память и копию операционной системы и приложения. Каждая подсистема взаимодействует с другими через высокоскоростное соединение».

IBM «s Blue Gene / L , пятый самый быстрый суперкомпьютер в мире по июнь 2009 TOP500 рейтинга, является MPP.

Грид-вычисления

Грид-вычисления - это наиболее распространенная форма параллельных вычислений. Он использует компьютеры, обменивающиеся данными через Интернет, для решения данной проблемы. Из-за низкой пропускной способности и чрезвычайно высокой задержки, доступных в Интернете, распределенные вычисления обычно имеют дело только с неприятно параллельными проблемами. Было создано множество приложений для распределенных вычислений, наиболее известными примерами из которых являются SETI @ home и Folding @ home .

Большинство приложений для распределенных вычислений используют промежуточное программное обеспечение (программное обеспечение, которое находится между операционной системой и приложением для управления сетевыми ресурсами и стандартизации программного интерфейса). Наиболее распространенным промежуточным программным обеспечением для распределенных вычислений является открытая инфраструктура Berkeley для сетевых вычислений (BOINC). Часто программное обеспечение распределенных вычислений использует «запасные циклы», выполняя вычисления в то время, когда компьютер простаивает.

Специализированные параллельные компьютеры

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

Реконфигурируемые вычисления с программируемыми вентильными матрицами

Реконфигурируемые вычисления - это использование программируемой вентильной матрицы (FPGA) в качестве сопроцессора для универсального компьютера. ПЛИС - это, по сути, компьютерный чип, который может перепрограммировать себя для данной задачи.

ПЛИС можно программировать с помощью языков описания оборудования, таких как VHDL или Verilog . Однако программирование на этих языках может быть утомительным. Несколько поставщиков создали языки от C до HDL, которые пытаются имитировать синтаксис и семантику языка программирования C , с которыми знакомо большинство программистов. Наиболее известными языками от C до HDL являются Mitrion-C , Impulse C , DIME-C и Handel-C . Для этой цели также могут использоваться определенные подмножества SystemC на основе C ++.

Решение AMD открыть свою технологию HyperTransport для сторонних поставщиков стало технологией, обеспечивающей возможность высокопроизводительных реконфигурируемых вычислений. По словам Майкла Р. Д'Амура, главного операционного директора DRC Computer Corporation , «когда мы впервые пришли в AMD, они назвали нас« похитителями сокетов » . Теперь они называют нас своими партнерами ».

Универсальные вычисления на графических процессорах (GPGPU)

Вычисления общего назначения на графических процессорах (GPGPU) - довольно недавняя тенденция в исследованиях компьютерной инженерии. Графические процессоры - это сопроцессоры, которые были в значительной степени оптимизированы для обработки компьютерной графики . Обработка компьютерной графики - это область, в которой преобладают параллельные операции с данными, особенно операции с матрицами линейной алгебры .

В первые дни программы GPGPU использовали обычные графические API для выполнения программ. Однако было создано несколько новых языков программирования и платформ для выполнения вычислений общего назначения на графических процессорах, причем как Nvidia, так и AMD выпускают среды программирования с CUDA и Stream SDK соответственно. Другие языки программирования GPU включают BrookGPU , PeakStream и RapidMind . Nvidia также выпустила специальные продукты для вычислений в своей серии Tesla . Технологический консорциум Khronos Group выпустил спецификацию OpenCL , которая представляет собой основу для написания программ, которые выполняются на платформах, состоящих из процессоров и графических процессоров. AMD , Apple , Intel , Nvidia и другие поддерживают OpenCL .

Интегральные схемы для конкретных приложений

Для работы с параллельными приложениями было разработано несколько подходов к интегральным схемам для конкретных приложений (ASIC).

Поскольку ASIC (по определению) специфичен для данного приложения, он может быть полностью оптимизирован для этого приложения. В результате для данного приложения ASIC имеет тенденцию превосходить по производительности универсальный компьютер. Однако ASIC создаются с помощью УФ-фотолитографии . Этот процесс требует набора масок, который может быть очень дорогим. Набор масок может стоить более миллиона долларов США. (Чем меньше транзисторы, необходимые для микросхемы, тем дороже будет маска.) Между тем, увеличение производительности в универсальных вычислениях с течением времени (как описано законом Мура ) имеет тенденцию сводить на нет этот выигрыш всего за одно или два поколения микросхем. . Высокая начальная стоимость и тенденция к замене универсальных вычислений, основанных на законе Мура, сделали ASIC неприменимыми для большинства приложений параллельных вычислений. Однако некоторые были построены. Одним из примеров является машина PFLOPS RIKEN MDGRAPE-3, которая использует специальные ASIC для моделирования молекулярной динамики .

Векторные процессоры
Cray-1 представляет собой вектор процессор

Векторный процессор - это ЦП или компьютерная система, которая может выполнять одну и ту же инструкцию для больших наборов данных. Векторные процессоры имеют высокоуровневые операции, которые работают с линейными массивами чисел или векторов. Пример векторной операции: A = B × C , где A , B и C - каждый из 64-элементных векторов 64-битных чисел с плавающей запятой . Они тесно связаны с классификацией SIMD Флинна.

Компьютеры Cray прославились своими компьютерами с векторной обработкой в ​​1970-х и 1980-х годах. Однако векторные процессоры - и как ЦП, и как полноценные компьютерные системы - вообще исчезли. Современные наборы инструкций процессора действительно включают некоторые инструкции вектор обработки, например с Freescale Semiconductor «s AltiVec и Intel » s Streaming SIMD Extensions (SSE).

Программное обеспечение

Языки параллельного программирования

Языки параллельного программирования , библиотеки , API и модели параллельного программирования (такие как алгоритмические скелеты ) были созданы для программирования параллельных компьютеров. Обычно их можно разделить на классы на основе предположений, которые они делают о базовой архитектуре памяти - совместно используемой памяти, распределенной памяти или совместно используемой распределенной памяти. Языки программирования с общей памятью взаимодействуют, манипулируя переменными общей памяти. Распределенная память использует передачу сообщений . POSIX Threads и OpenMP - два наиболее широко используемых API общей памяти, тогда как интерфейс передачи сообщений (MPI) - наиболее широко используемый API системы передачи сообщений. Одна концепция, используемая при программировании параллельных программ, - это концепция будущего , в которой одна часть программы обещает доставить требуемые данные другой части программы в какое-то время в будущем.

CAPS entreprise и Pathscale также координируют свои усилия по превращению директив гибридного многоядерного параллельного программирования (HMPP) в открытый стандарт под названием OpenHMPP . Модель программирования на основе директив OpenHMPP предлагает синтаксис для эффективной разгрузки вычислений на аппаратных ускорителях и для оптимизации перемещения данных в / из аппаратной памяти. Директивы OpenHMPP описывают удаленный вызов процедур (RPC) на устройстве-ускорителе (например, GPU) или, в более общем смысле, на наборе ядер. Директивы аннотируют коды C или Fortran для описания двух наборов функций: выгрузки процедур (обозначенных кодлетами) на удаленное устройство и оптимизации передачи данных между основной памятью ЦП и памятью ускорителя.

Распространение потребительских графических процессоров привело к поддержке вычислительных ядер либо в графических API (называемых вычислительными шейдерами ), либо в специализированных API (таких как OpenCL ), либо в других языковых расширениях.

Автоматическое распараллеливание

Автоматическое распараллеливание последовательной программы компилятором - это «святой Грааль» параллельных вычислений, особенно с учетом вышеупомянутого ограничения частоты процессора. Несмотря на десятилетия работы исследователей компиляторов, автоматическое распараллеливание имело лишь ограниченный успех.

Основные языки параллельного программирования остаются либо явно параллельными, либо (в лучшем случае) частично неявными , в которых программист дает директивы компилятора для распараллеливания. Существует несколько полностью неявных языков параллельного программирования - SISAL , Parallel Haskell , SequenceL , System C (для FPGA ), Mitrion-C , VHDL и Verilog .

Контрольные точки приложения

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

Алгоритмические методы

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

Отказоустойчивость

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

История

ILLIAC IV , «самый печально известный суперкомпьютер»

Истоки истинного (MIMD) параллелизма восходят к Луиджи Федерико Менабреа и его наброску аналитической машины, изобретенной Чарльзом Бэббиджем .

В апреле 1958 года Стэнли Гилл (Ферранти) обсудил параллельное программирование и необходимость ветвления и ожидания. Также в 1958 году исследователи IBM Джон Кок и Дэниел Слотник впервые обсудили использование параллелизма в численных вычислениях. Корпорация Burroughs представила D825 в 1962 году, четырехпроцессорный компьютер, который имел доступ к 16 модулям памяти через переключающий переключатель . В 1967 году Амдал и Слотник опубликовали дискуссию о возможности параллельной обработки на конференции Американской федерации обществ обработки информации. Именно во время этих дебатов был придуман закон Амдала для определения предела ускорения за счет параллелизма.

В 1969 году Honeywell представила свою первую систему Multics - симметричную многопроцессорную систему, способную работать до восьми процессоров параллельно. C.mmp , многопроцессорный проект в Университете Карнеги-Меллона в 1970-х годах, был одним из первых мультипроцессоров с более чем несколькими процессорами. Первым мультипроцессором с подключением к шине и кешами отслеживания был Synapse N + 1 в 1984 году.

История параллельных компьютеров SIMD восходит к 1970-м годам. Мотивация ранних SIMD компьютеров была амортизировать задержку затвора от процессора блока управления над нескольких инструкциями. В 1964 году Слотник предложил построить параллельный компьютер для Ливерморской национальной лаборатории Лоуренса . Его разработка была профинансирована ВВС США , которые были самой ранней разработкой параллельных вычислений SIMD, ILLIAC IV . Ключом к его дизайну был довольно высокий параллелизм, до 256 процессоров, что позволяло машине работать с большими наборами данных в том, что позже будет известно как векторная обработка . Однако ILLIAC IV был назван «самым печально известным из суперкомпьютеров», потому что проект был завершен только на четверть, но занял 11 лет и стоил почти в четыре раза больше первоначальной оценки. Когда в 1976 году он был наконец готов к запуску своего первого реального приложения, он уступил в производительности существующим коммерческим суперкомпьютерам, таким как Cray-1 .

Биологический мозг как массивно-параллельный компьютер

В начале 1970 - х годов, в MIT компьютерных наук и лаборатории искусственного интеллекта , Марвин Мински и Пейперт начал развивать общество Ума теорию, которая рассматривает биологический мозг как МВС . В 1986 году Мински опубликовал «Общество разума» , в котором утверждалось, что «разум формируется из множества маленьких агентов, каждый из которых сам по себе лишен разума». Теория пытается объяснить, как то, что мы называем интеллектом, может быть продуктом взаимодействия неразумных частей. Мински говорит, что самый большой источник идей по поводу теории пришел из его работы по созданию машины, которая использует роботизированную руку, видеокамеру и компьютер для сборки детских кубиков.

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

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

использованная литература

дальнейшее чтение

  • Rodriguez, C .; Villagra, M .; Баран Б. (29 августа 2008 г.). «Асинхронные командные алгоритмы для логической выполнимости». Биологические модели сетевых, информационных и вычислительных систем, 2007. Бионетика, 2007. 2 : 66–69. DOI : 10.1109 / BIMNICS.2007.4610083 . S2CID  15185219 .
  • Сечин, А .; Параллельные вычисления в фотограмметрии. GIM International. №1, 2016, с. 21–23.

внешние ссылки

Послушайте эту статью ( 54 минуты )
Разговорный значок Википедии
Этот аудиофайл был создан на основе редакции этой статьи от 21 августа 2013 года и не отражает последующих правок. ( 2013-08-21 )