Параллельные вычисления — это тип вычислений , при котором множество вычислений или процессов выполняются одновременно. [1] Большие проблемы часто можно разделить на более мелкие, которые затем можно решить одновременно. Существует несколько различных форм параллельных вычислений: параллелизм на уровне битов , на уровне команд , данных и параллелизм задач . Параллелизм уже давно используется в высокопроизводительных вычислениях , но приобрел более широкий интерес из-за физических ограничений, препятствующих масштабированию частоты . [2] Поскольку энергопотребление (и, следовательно, выделение тепла) компьютерами в последние годы стало проблемой, [3] параллельные вычисления стали доминирующей парадигмой в компьютерной архитектуре , главным образом в форме многоядерных процессоров . [4]
Параллельные вычисления тесно связаны с параллельными вычислениями — они часто используются вместе и часто объединяются, хотя они различны: возможен параллелизм без параллелизма и параллелизм без параллелизма (например, многозадачность посредством разделения времени на одном компьютере). основной процессор). [5] [6] При параллельных вычислениях вычислительная задача обычно разбивается на несколько, часто множество, очень похожих подзадач, которые могут обрабатываться независимо и результаты которых впоследствии объединяются после завершения. Напротив, при параллельных вычислениях различные процессы часто не решают связанные задачи; когда они это делают, что типично для распределенных вычислений , отдельные задачи могут иметь различную природу и часто требуют некоторого межпроцессного взаимодействия во время выполнения.
Параллельные компьютеры можно грубо классифицировать по уровню, на котором аппаратное обеспечение поддерживает параллелизм: многоядерные и многопроцессорные компьютеры имеют несколько вычислительных элементов на одной машине, тогда как кластеры , MPP и сетки используют несколько компьютеров для работы на одной машине. задача. Специализированные параллельные компьютерные архитектуры иногда используются наряду с традиционными процессорами для ускорения конкретных задач.
В некоторых случаях параллелизм прозрачен для программиста, например, при параллелизме на уровне битов или команд, но явно параллельные алгоритмы , особенно те, которые используют параллелизм, писать труднее, чем последовательные , [7] , поскольку параллелизм вводит несколько новых классы потенциальных ошибок программного обеспечения , из которых наиболее распространены состояния гонки . Связь и синхронизация между различными подзадачами обычно являются одними из самых серьезных препятствий на пути достижения оптимальной производительности параллельных программ.
Теоретическая верхняя граница ускорения одной программы в результате распараллеливания дается законом Амдала , который гласит, что оно ограничено долей времени, в течение которого может использоваться распараллеливание .
Традиционно компьютерное программное обеспечение писалось для последовательных вычислений . Для решения проблемы конструируется и реализуется алгоритм в виде последовательного потока инструкций. Эти инструкции выполняются на центральном процессоре одного компьютера. Одновременно может выполняться только одна инструкция — после завершения этой инструкции выполняется следующая. [8]
С другой стороны, параллельные вычисления используют несколько элементов обработки одновременно для решения проблемы. Это достигается путем разбиения задачи на независимые части так, чтобы каждый обрабатывающий элемент мог выполнять свою часть алгоритма одновременно с другими. Элементы обработки могут быть разнообразными и включать в себя такие ресурсы, как один компьютер с несколькими процессорами, несколько сетевых компьютеров, специализированное оборудование или любую комбинацию вышеперечисленного. [8] Исторически параллельные вычисления использовались для научных вычислений и моделирования научных проблем, особенно в естественных и технических науках , таких как метеорология . Это привело к разработке параллельного аппаратного и программного обеспечения, а также высокопроизводительных вычислений . [9]
Масштабирование частоты было основной причиной повышения производительности компьютеров с середины 1980-х до 2004 года. Время выполнения программы равно количеству инструкций, умноженному на среднее время выполнения каждой инструкции. Сохраняя все остальное постоянным, увеличение тактовой частоты уменьшает среднее время, необходимое для выполнения инструкции. Таким образом, увеличение частоты уменьшает время выполнения всех программ , связанных с вычислениями . [10] Однако энергопотребление P чипа определяется уравнением P = C × V 2 × F , где C — переключаемая емкость за такт (пропорциональная количеству транзисторов, входы которых изменяются), V — напряжение , а F — частота процессора (циклов в секунду). [11] Увеличение частоты увеличивает количество энергии, потребляемой процессором. Увеличение энергопотребления процессоров в конечном итоге привело к отказу Intel 8 мая 2004 года от выпуска процессоров Tejas и Jayhawk , что обычно называют концом масштабирования частоты как доминирующей парадигмы компьютерной архитектуры. [12]
Чтобы решить проблему энергопотребления и перегрева, производители основных центральных процессоров (ЦП или процессоров) начали выпускать энергоэффективные процессоры с несколькими ядрами. Ядро — это вычислительная единица процессора, а в многоядерных процессорах каждое ядро независимо и может одновременно обращаться к одной и той же памяти. Многоядерные процессоры принесли параллельные вычисления на настольные компьютеры . Таким образом, распараллеливание последовательных программ стало основной задачей программирования. В 2012 году четырехъядерные процессоры стали стандартом для настольных компьютеров , а серверы имеют более 10 ядерных процессоров. На основе закона Мура можно предсказать, что количество ядер на процессор будет удваиваться каждые 18–24 месяца. Это может означать, что после 2020 года типичный процессор будет иметь десятки или сотни ядер, однако на самом деле стандарт находится где-то в районе от 4 до 16 ядер, при этом некоторые конструкции имеют сочетание ядер производительности и эффективности (например, Big. НЕБОЛЬШАЯ конструкция) из-за тепловых и конструктивных ограничений. [13] [ нужна ссылка ]
Операционная система может гарантировать, что различные задачи и пользовательские программы выполняются параллельно на доступных ядрах. Однако для того, чтобы последовательная программа могла в полной мере воспользоваться преимуществами многоядерной архитектуры, программисту необходимо реструктурировать и распараллелить код. Ускорение выполнения прикладного программного обеспечения больше не будет достигаться за счет масштабирования частоты, вместо этого программистам придется распараллеливать свой программный код, чтобы воспользоваться преимуществами растущей вычислительной мощности многоядерных архитектур. [14]
В оптимальном случае ускорение от распараллеливания должно быть линейным: удвоение количества обрабатывающих элементов должно сократить время выполнения вдвое, а его удвоение во второй раз должно снова сократить время выполнения вдвое. Однако очень немногие параллельные алгоритмы достигают оптимального ускорения. Большинство из них имеют почти линейное ускорение при небольшом количестве обрабатывающих элементов, которое сглаживается до постоянного значения при большом количестве обрабатывающих элементов.
Потенциальное ускорение алгоритма на параллельной вычислительной платформе определяется законом Амдала [15]
где
Поскольку задержка S < 1/(1 - p ) показывает, что небольшая часть программы, которую нельзя распараллелить, будет ограничивать общее ускорение, доступное за счет распараллеливания. Программа, решающая большую математическую или инженерную задачу, обычно состоит из нескольких распараллеливаемых частей и нескольких нераспараллеливаемых (последовательных) частей. Если на нераспараллеливаемую часть программы приходится 10% времени выполнения ( p = 0,9), мы можем получить ускорение не более чем в 10 раз, независимо от того, сколько процессоров будет добавлено. Это накладывает верхний предел на полезность добавления дополнительных параллельных исполнительных блоков. «Когда задача не может быть разделена из-за последовательных ограничений, приложение дополнительных усилий не влияет на график. Вынашивание ребенка занимает девять месяцев, независимо от того, сколько женщин будет назначено». [16]
Закон Амдала применим только к случаям, когда размер задачи фиксирован. На практике, когда становится доступно больше вычислительных ресурсов, они имеют тенденцию использоваться для решения более крупных задач (больших наборов данных), и время, затрачиваемое на распараллеливаемую часть, часто растет намного быстрее, чем на последовательную работу по своей сути. [17] В этом случае закон Густавсона дает менее пессимистическую и более реалистичную оценку параллельной производительности: [18]
И закон Амдала, и закон Густавсона предполагают, что время работы последовательной части программы не зависит от количества процессоров. Закон Амдала предполагает, что вся задача имеет фиксированный размер, так что общий объем работы, которую необходимо выполнить параллельно, также не зависит от количества процессоров , тогда как закон Густавсона предполагает, что общий объем работы, которую необходимо выполнить параллельно, изменяется линейно с увеличением количество процессоров .
Понимание зависимостей данных имеет основополагающее значение для реализации параллельных алгоритмов . Ни одна программа не может работать быстрее, чем самая длинная цепочка зависимых вычислений (известная как критический путь ), поскольку вычисления, зависящие от предыдущих вычислений в цепочке, должны выполняться по порядку. Однако большинство алгоритмов представляют собой не просто длинную цепочку зависимых вычислений; обычно есть возможность параллельно выполнять независимые вычисления.
Пусть P i и P j — два сегмента программы. Условия Бернштейна [19] описывают, когда они независимы и могут выполняться параллельно. Для P i пусть I i будет всеми входными переменными, а O i — выходными переменными, и аналогично для P j . Pi и Pj независимы, если они удовлетворяют
Нарушение первого условия приводит к зависимости потока, соответствующей тому, что первый сегмент создает результат, используемый вторым сегментом. Второе условие представляет собой антизависимость, когда второй сегмент создает переменную, необходимую первому сегменту. Третье и последнее условие представляет собой зависимость вывода: когда два сегмента записывают в одно и то же место, результат поступает из логически последнего выполненного сегмента. [20]
Рассмотрим следующие функции, которые демонстрируют несколько видов зависимостей:
1: функция Dep(a, b)2: с := а * б3: д := 3 * с4: конечная функция
В этом примере инструкция 3 не может быть выполнена до инструкции 2 (или даже параллельно с ней), поскольку инструкция 3 использует результат инструкции 2. Она нарушает условие 1 и, таким образом, вводит зависимость от потока.
1: функция NoDep(a, b)2: с := а * б3: д := 3 * б4: е := а + б5: конечная функция
В этом примере между инструкциями нет зависимостей, поэтому все они могут выполняться параллельно.
Условия Бернштейна не позволяют распределять память между разными процессами. Для этого необходимы некоторые средства обеспечения порядка между доступами, такие как семафоры , барьеры или какой-либо другой метод синхронизации .
Подзадачи в параллельной программе часто называют потоками . В некоторых параллельных компьютерных архитектурах используются меньшие и облегченные версии потоков, известные как волокна , в то время как в других используются более крупные версии, известные как процессы . Однако «потоки» обычно воспринимаются как общий термин для подзадач. [21] Потокам часто требуется синхронизированный доступ к объекту или другому ресурсу , например, когда им необходимо обновить переменную , которая является общей для них. Без синхронизации инструкции между двумя потоками могут чередоваться в любом порядке. Например, рассмотрим следующую программу:
Если инструкция 1B выполняется между 1A и 3A или если инструкция 1A выполняется между 1B и 3B, программа выдаст неверные данные. Это известно как состояние гонки . Программист должен использовать блокировку для обеспечения взаимного исключения . Блокировка — это конструкция языка программирования, которая позволяет одному потоку получить контроль над переменной и запретить другим потокам читать или записывать ее, пока эта переменная не будет разблокирована. Поток, удерживающий блокировку, может свободно выполнить свою критическую секцию (раздел программы, требующий монопольного доступа к некоторой переменной) и разблокировать данные после ее завершения. Поэтому, чтобы гарантировать правильное выполнение программы, приведенную выше программу можно переписать с использованием блокировок:
Один поток успешно заблокирует переменную V, в то время как другой поток будет заблокирован и не сможет продолжить работу, пока V не будет снова разблокирован. Это гарантирует корректное выполнение программы. Блокировки могут быть необходимы для обеспечения корректного выполнения программы, когда потоки должны сериализовать доступ к ресурсам, но их использование может сильно замедлить работу программы и повлиять на ее надежность . [22]
Блокировка нескольких переменных с помощью неатомарных блокировок приводит к возможности тупиковой ситуации в программе . Атомная блокировка блокирует несколько переменных одновременно. Если он не может заблокировать их все, он не блокирует ни один из них. Если каждому из двух потоков необходимо заблокировать одни и те же две переменные с использованием неатомарных блокировок, возможно, что один поток заблокирует одну из них, а второй поток заблокирует вторую переменную. В таком случае ни один поток не может завершиться, и возникает взаимоблокировка. [23]
Многие параллельные программы требуют, чтобы их подзадачи выполнялись синхронно . Это требует использования барьера . Барьеры обычно реализуются с помощью блокировки или семафора . [24] Один класс алгоритмов, известный как алгоритмы без блокировок и без ожидания , вообще избегает использования блокировок и барьеров. Однако этот подход, как правило, сложен в реализации и требует правильно спроектированных структур данных. [25]
Не всякое распараллеливание приводит к ускорению. Как правило, поскольку задача разбивается на все больше и больше потоков, эти потоки тратят все большую часть своего времени на общение друг с другом или ожидание друг друга для доступа к ресурсам. [26] [27] Как только накладные расходы из-за конкуренции за ресурсы или связи преобладают над временем, затрачиваемым на другие вычисления, дальнейшее распараллеливание (то есть разделение рабочей нагрузки на еще большее количество потоков) увеличивает, а не уменьшает количество времени, необходимое для завершения. Эту проблему, известную как параллельное замедление [28] , в некоторых случаях можно решить путем анализа и перепроектирования программного обеспечения. [29]
Приложения часто классифицируются в зависимости от того, как часто их подзадачам необходимо синхронизироваться или взаимодействовать друг с другом. Приложение демонстрирует детальный параллелизм, если его подзадачи должны обмениваться данными много раз в секунду; он демонстрирует грубый параллелизм, если они не обмениваются данными много раз в секунду, и демонстрирует смущающий параллелизм , если им редко или никогда не приходится общаться. Невероятно параллельные приложения считаются самыми простыми для распараллеливания.
Майкл Дж. Флинн создал одну из самых ранних систем классификации параллельных (и последовательных) компьютеров и программ, теперь известную как таксономия Флинна . Флинн классифицировал программы и компьютеры по тому, работали ли они с использованием одного или нескольких наборов инструкций, а также по тому, использовали ли эти инструкции один или несколько наборов данных.
Классификация «одна инструкция — одни данные» (SISD) эквивалентна полностью последовательной программе. Классификация «одна инструкция — несколько данных» (SIMD) аналогична многократному выполнению одной и той же операции над большим набором данных. Обычно это делается в приложениях обработки сигналов . Классификация «множественные инструкции — одни данные» (MISD) — редко используемая классификация. Хотя были разработаны компьютерные архитектуры для решения этой проблемы (например, систолические массивы ), реализовано лишь несколько приложений, соответствующих этому классу. Программы с несколькими инструкциями и несколькими данными (MIMD) на сегодняшний день являются наиболее распространенным типом параллельных программ.
По словам Дэвида А. Паттерсона и Джона Л. Хеннесси : «Некоторые машины, конечно, представляют собой гибриды этих категорий, но эта классическая модель выжила, потому что она проста, ее легко понять и дает хорошее первое приближение. возможно, из-за ее понятности — наиболее широко используемой схемы». [31]
С момента появления технологии производства компьютерных чипов сверхкрупной интеграции (СБИС) в 1970-х годах и примерно до 1986 года ускорение компьютерной архитектуры было обусловлено удвоением размера компьютерного слова — количества информации, которой процессор может манипулировать за цикл. [32] Увеличение размера слова уменьшает количество инструкций, которые процессор должен выполнить для выполнения операции над переменными, размеры которых превышают длину слова. Например, если 8-битный процессор должен сложить два 16-битных целых числа , процессор должен сначала сложить 8 младших битов каждого целого числа, используя стандартную инструкцию сложения, а затем сложить 8 старших битов, используя команду сложения. - инструкция переноса и бит переноса из сложения младшего порядка; таким образом, 8-битному процессору для выполнения одной операции требуются две инструкции, тогда как 16-битный процессор сможет выполнить операцию с помощью одной инструкции.
Исторически 4-битные микропроцессоры были заменены 8-битными, затем 16-битными, а затем 32-битными микропроцессорами. Эта тенденция в целом закончилась с появлением 32-битных процессоров, которые на протяжении двух десятилетий были стандартом в вычислениях общего назначения. Лишь в начале 2000-х годов, с появлением архитектур x86-64 , 64-битные процессоры стали обычным явлением.
Компьютерная программа, по сути, представляет собой поток инструкций, выполняемых процессором. Без параллелизма на уровне команд процессор может выдавать только менее одной инструкции за такт ( IPC < 1 ). Эти процессоры известны как субскалярные процессоры. Эти инструкции можно переупорядочивать и объединять в группы, которые затем выполняются параллельно без изменения результата программы. Это известно как параллелизм на уровне инструкций. Достижения в области параллелизма на уровне команд доминировали в компьютерной архитектуре с середины 1980-х до середины 1990-х годов. [33]
Все современные процессоры имеют многоступенчатые конвейеры команд . Каждый этап конвейера соответствует отдельному действию, которое процессор выполняет над этой инструкцией на этом этапе; процессор с N -этапным конвейером может иметь до N различных инструкций на разных стадиях завершения и, таким образом, может выдавать одну инструкцию за такт ( IPC = 1 ). Эти процессоры известны как скалярные процессоры. Каноническим примером конвейерного процессора является RISC- процессор с пятью этапами: выборка инструкций (IF), декодирование инструкций (ID), выполнение (EX), доступ к памяти (MEM) и обратная запись в регистр (WB). Процессор Pentium 4 имел 35-ступенчатый конвейер. [34]
Большинство современных процессоров также имеют несколько исполнительных блоков . Обычно они сочетают эту функцию с конвейерной обработкой и, таким образом, могут выдавать более одной инструкции за такт ( IPC > 1 ). Эти процессоры известны как суперскалярные процессоры. Суперскалярные процессоры отличаются от многоядерных процессоров тем, что несколько исполнительных блоков не являются целыми процессорами (т.е. процессорами). Инструкции можно группировать вместе только в том случае, если между ними нет зависимости данных . Табло и алгоритм Томасуло (который похож на табло, но использует переименование регистров ) — два наиболее распространенных метода реализации внеочередного выполнения и параллелизма на уровне инструкций.
Параллелизм задач — это характеристика параллельной программы, заключающаяся в том, что «совершенно разные вычисления могут выполняться как с одними и теми же, так и с разными наборами данных». [35] Это контрастирует с параллелизмом данных, когда одни и те же вычисления выполняются на одних и тех же или разных наборах данных. Параллелизм задач предполагает разложение задачи на подзадачи и последующее выделение каждой подзадачи процессору для выполнения. Затем процессоры будут выполнять эти подзадачи одновременно и часто совместно. Параллелизм задач обычно не зависит от размера проблемы. [36]
Параллелизм на уровне суперслов — это метод векторизации , основанный на развертывании цикла и базовой векторизации блоков. Он отличается от алгоритмов векторизации цикла тем, что может использовать параллелизм встроенного кода , например, при манипулировании координатами, цветовыми каналами или в циклах, развернутых вручную. [37]
Основная память в параллельном компьютере представляет собой либо разделяемую память (разделяемую всеми обрабатывающими элементами в одном адресном пространстве ), либо распределенную память (в которой каждый обрабатывающий элемент имеет собственное локальное адресное пространство). [38] Распределенная память означает тот факт, что память распределена логически, но часто подразумевается, что она также распределена физически. Распределенная общая память и виртуализация памяти объединяют два подхода, при которых обрабатывающий элемент имеет собственную локальную память и доступ к памяти на нелокальных процессорах. Доступ к локальной памяти обычно происходит быстрее, чем доступ к нелокальной памяти. На суперкомпьютерах распределенное общее пространство памяти может быть реализовано с использованием модели программирования, такой как PGAS . Эта модель позволяет процессам на одном вычислительном узле прозрачно получать доступ к удаленной памяти другого вычислительного узла. Все вычислительные узлы также подключены к внешней системе общей памяти через высокоскоростное межсоединение, такое как Infiniband . Эта внешняя система общей памяти известна как пакетный буфер , который обычно создается из массивов энергонезависимой памяти , физически распределенных по нескольким устройствам ввода-вывода. О узлы.
Компьютерные архитектуры, в которых к каждому элементу основной памяти можно получить доступ с одинаковой задержкой и пропускной способностью , известны как системы унифицированного доступа к памяти (UMA). Обычно этого можно достичь только с помощью системы с общей памятью , в которой память физически не распределена. Система, не обладающая этим свойством, называется архитектурой неоднородного доступа к памяти (NUMA). Системы с распределенной памятью имеют неравномерный доступ к памяти.
Компьютерные системы используют кэши — небольшие и быстрые запоминающие устройства, расположенные рядом с процессором, в которых хранятся временные копии значений памяти (поблизости как в физическом, так и в логическом смысле). В параллельных компьютерных системах возникают трудности с кэшами, которые могут хранить одно и то же значение в нескольких местах, что может привести к неправильному выполнению программы. Этим компьютерам требуется система согласованности кэша , которая отслеживает кэшированные значения и стратегически очищает их, обеспечивая тем самым правильное выполнение программы. Отслеживание шины — один из наиболее распространенных методов отслеживания того, к каким значениям осуществляется доступ (и, следовательно, их следует очищать). Проектирование больших, высокопроизводительных систем когерентности кэша — очень сложная проблема в компьютерной архитектуре. В результате компьютерные архитектуры с общей памятью не масштабируются так хорошо, как системы с распределенной памятью. [38]
Связь процессор-процессор и процессор-память может быть реализована аппаратно несколькими способами, в том числе через общую (многопортовую или мультиплексированную ) память, перекрестный коммутатор , общую шину или сеть межсоединений с множеством топологий , включая звезду , кольцо , дерево . , гиперкуб , толстый гиперкуб (гиперкуб с более чем одним процессором в узле) или n-мерная сетка .
Параллельные компьютеры, основанные на взаимосвязанных сетях, должны иметь некоторую маршрутизацию , позволяющую передавать сообщения между узлами, которые не связаны напрямую. В больших многопроцессорных машинах среда, используемая для связи между процессорами, скорее всего, будет иерархической.
Параллельные компьютеры можно грубо классифицировать по уровню, на котором оборудование поддерживает параллелизм. Эта классификация во многом аналогична расстоянию между базовыми вычислительными узлами. Они не являются взаимоисключающими; например, относительно распространены кластеры симметричных мультипроцессоров.
Многоядерный процессор — это процессор, который включает в себя несколько процессоров (называемых «ядрами») на одном кристалле. Этот процессор отличается от суперскалярного процессора, который включает в себя несколько исполнительных блоков и может выдавать несколько инструкций за такт из одного потока команд (потока); напротив, многоядерный процессор может выдавать несколько инструкций за такт из нескольких потоков команд. Микропроцессор IBM Cell , разработанный для использования в Sony PlayStation 3 , является выдающимся многоядерным процессором. Каждое ядро многоядерного процессора потенциально также может быть суперскалярным, то есть за каждый такт каждое ядро может выдавать несколько инструкций из одного потока.
Одновременная многопоточность (из которой наиболее известна технология Intel Hyper-Threading ) была ранней формой псевдомногоядерности. Процессор, поддерживающий параллельную многопоточность, включает в себя несколько исполнительных блоков в одном процессоре (то есть он имеет суперскалярную архитектуру) и может выдавать несколько инструкций за такт из нескольких потоков. С другой стороны , временная многопоточность включает в себя один исполнительный блок в одном и том же процессоре и может выдавать по одной инструкции одновременно из нескольких потоков.
Симметричный мультипроцессор (SMP) — это компьютерная система с несколькими идентичными процессорами, которые совместно используют память и подключаются через шину . [39] Конфликты на шинах препятствуют масштабированию шинных архитектур. В результате SMP обычно не содержат более 32 процессоров. [40] Из-за небольшого размера процессоров и значительного снижения требований к пропускной способности шины, достигаемого за счет больших кэшей, такие симметричные мультипроцессоры чрезвычайно эффективны с точки зрения затрат при условии, что существует достаточный объем пропускной способности памяти. [39]
Распределенный компьютер (также известный как мультипроцессор с распределенной памятью) — это компьютерная система с распределенной памятью, в которой обрабатывающие элементы соединены сетью. Распределенные компьютеры обладают высокой масштабируемостью. Термины « параллельные вычисления », «параллельные вычисления» и «распределенные вычисления» во многом совпадают, и между ними не существует четкого различия. [41] Одну и ту же систему можно охарактеризовать как «параллельную», так и «распределенную»; процессоры в типичной распределенной системе работают одновременно и параллельно. [42]
Кластер — это группа слабо связанных компьютеров, которые тесно взаимодействуют друг с другом, поэтому в некоторых отношениях их можно рассматривать как один компьютер. [43] Кластеры состоят из нескольких автономных компьютеров, соединенных сетью. Хотя машины в кластере не обязательно должны быть симметричными, в противном случае балансировка нагрузки будет сложнее. Наиболее распространенным типом кластера является кластер «Беовульф» , который представляет собой кластер, реализованный на нескольких идентичных коммерческих готовых компьютерах, подключенных к локальной сети TCP/IP Ethernet . [44] Технология Беовульфа была первоначально разработана Томасом Стерлингом и Дональдом Беккером . 87% всех суперкомпьютеров Top500 являются кластерами. [45] Остальные — это процессоры с массовым параллелизмом, описание которых приведено ниже.
Поскольку системы грид-вычислений (описанные ниже) могут легко решать сложные параллельные задачи, современные кластеры обычно предназначены для решения более сложных задач — проблем, которые требуют, чтобы узлы чаще обменивались промежуточными результатами друг с другом. Для этого требуется высокая пропускная способность и, что более важно, сеть межсоединений с малой задержкой . Многие исторические и современные суперкомпьютеры используют специализированное высокопроизводительное сетевое оборудование, специально разработанное для кластерных вычислений, например сеть Cray Gemini. [46] По состоянию на 2014 год в большинстве современных суперкомпьютеров используется стандартное сетевое оборудование, часто Myrinet , InfiniBand или Gigabit Ethernet .
Процессор с массовым параллелизмом (MPP) — это один компьютер с множеством сетевых процессоров. MPP имеют многие из тех же характеристик, что и кластеры, но MPP имеют специализированные межсетевые сети (тогда как кластеры используют обычное оборудование для создания сетей). MPP также обычно больше кластеров и обычно имеют «гораздо больше», чем 100 процессоров. [47] В MPP «каждый процессор содержит собственную память и копию операционной системы и приложений. Каждая подсистема взаимодействует с другими через высокоскоростное соединение». [48]
IBM Blue Gene/L , пятый по скорости суперкомпьютер в мире согласно рейтингу TOP500 за июнь 2009 года , является MPP.
Грид-вычисления — это наиболее распределенная форма параллельных вычислений. Он использует компьютеры, обменивающиеся данными через Интернет , для решения конкретной проблемы. Из-за низкой пропускной способности и чрезвычайно высоких задержек, доступных в Интернете, распределенные вычисления обычно имеют дело только с до невозможности параллельными задачами.
Большинство приложений грид-вычислений используют промежуточное программное обеспечение (программное обеспечение, которое находится между операционной системой и приложением для управления сетевыми ресурсами и стандартизации программного интерфейса). Наиболее распространенным промежуточным программным обеспечением для грид-вычислений является открытая инфраструктура для сетевых вычислений Беркли (BOINC). Часто добровольное вычислительное программное обеспечение использует «запасные циклы», выполняя вычисления в то время, когда компьютер простаивает. [49]
Повсеместное распространение Интернета открыло возможность крупномасштабных облачных вычислений.
В рамках параллельных вычислений существуют специализированные параллельные устройства, которые остаются нишевыми областями интересов. Хотя они и не зависят от предметной области , они, как правило, применимы лишь к нескольким классам параллельных задач.
Реконфигурируемые вычисления — это использование программируемой вентильной матрицы (FPGA) в качестве сопроцессора компьютера общего назначения. По сути, FPGA — это компьютерный чип, который может перемонтироваться для решения конкретной задачи.
FPGA можно программировать с использованием языков описания аппаратного обеспечения , таких как VHDL [50] или Verilog . [51] Несколько поставщиков создали языки C to HDL , которые пытаются эмулировать синтаксис и семантику языка программирования C , с которым знакомо большинство программистов. Наиболее известные языки от C до HDL — Mitrion-C , Impulse C и Handel-C . Для этой цели также можно использовать определенные подмножества SystemC , основанные на C++.
Решение AMD открыть свою технологию HyperTransport для сторонних поставщиков стало технологией, позволяющей создавать высокопроизводительные реконфигурируемые вычисления. [52] По словам Майкла Р. Д'Амура, главного операционного директора DRC Computer Corporation, «когда мы впервые пришли в AMD, нас назвали « похитителями сокетов ». Теперь они называют нас своими партнерами». [52]
Вычисления общего назначения на графических процессорах (GPGPU) — довольно недавнее направление в исследованиях в области компьютерной техники. Графические процессоры — это сопроцессоры, которые были сильно оптимизированы для обработки компьютерной графики . [53] Обработка компьютерной графики — это область, в которой доминируют параллельные операции с данными, особенно матричные операции линейной алгебры .
Вначале программы GPGPU использовали обычные графические API для выполнения программ. Однако было создано несколько новых языков программирования и платформ для выполнения вычислений общего назначения на графических процессорах, причем как Nvidia , так и AMD выпустили среды программирования с CUDA и Stream SDK соответственно. Другие языки программирования графических процессоров включают BrookGPU , PeakStream и RapidMind . Nvidia также выпустила специальные продукты для вычислений в своей серии Tesla . Технологический консорциум Khronos Group выпустил спецификацию OpenCL , которая представляет собой основу для написания программ, которые выполняются на платформах, состоящих из центральных и графических процессоров. AMD , Apple , Intel , Nvidia и другие поддерживают OpenCL .
Для работы с параллельными приложениями было разработано несколько подходов к интегральным схемам для конкретных приложений (ASIC). [54] [55] [56]
Поскольку ASIC (по определению) специфичен для конкретного приложения, его можно полностью оптимизировать для этого приложения. В результате для данного приложения ASIC имеет тенденцию превосходить компьютер общего назначения. Однако ASIC создаются с помощью УФ-фотолитографии . Для этого процесса требуется набор масок, который может быть чрезвычайно дорогим. Набор масок может стоить более миллиона долларов США. [57] (Чем меньше транзисторов требуется для чипа, тем дороже будет маска.) Между тем, увеличение производительности в вычислениях общего назначения с течением времени (как описано законом Мура ) имеет тенденцию сводить на нет этот выигрыш только в одном или нескольких случаях. два поколения чипов. [52] Высокая первоначальная стоимость и тенденция к вытеснению универсальных вычислений, основанных на законе Мура, сделали ASIC непригодными для большинства приложений параллельных вычислений. Однако некоторые из них были построены. Одним из примеров является машина PFLOPS RIKEN MDGRAPE-3 , в которой используются специальные ASIC для моделирования молекулярной динамики .
Векторный процессор — это ЦП или компьютерная система, которая может выполнять одну и ту же инструкцию для больших наборов данных. Векторные процессоры имеют операции высокого уровня, которые работают с линейными массивами чисел или векторов. Примером векторной операции является A = B × C , где A , B и C — каждый из 64-элементных векторов 64-битных чисел с плавающей запятой . [58] Они тесно связаны с классификацией SIMD Флинна. [58]
Компьютеры Cray прославились своими компьютерами векторной обработки в 1970-х и 1980-х годах. Однако векторные процессоры — как центральные процессоры, так и полноценные компьютерные системы — в целом исчезли. Современные наборы инструкций процессора включают некоторые инструкции векторной обработки, например, AltiVec от Freescale Semiconductor и Streaming SIMD Extensions (SSE) от Intel .
Для программирования параллельных компьютеров были созданы языки параллельного программирования , библиотеки , API и модели параллельного программирования (например, алгоритмические скелеты ). Обычно их можно разделить на классы на основе предположений, которые они делают о базовой архитектуре памяти — разделяемая память, распределенная память или совместно используемая распределенная память. Языки программирования с общей памятью взаимодействуют посредством манипулирования переменными общей памяти. Распределенная память использует передачу сообщений . POSIX Threads и OpenMP — два наиболее широко используемых API общей памяти, тогда как интерфейс передачи сообщений (MPI) — наиболее широко используемый системный API передачи сообщений. [59] Одной из концепций, используемых при программировании параллельных программ, является концепция будущего , где одна часть программы обещает доставить необходимые данные в другую часть программы в какой-то момент в будущем.
Усилия по стандартизации параллельного программирования включают открытый стандарт OpenHMPP для гибридного многоядерного параллельного программирования. Модель программирования на основе директив OpenHMPP предлагает синтаксис для эффективной разгрузки вычислений на аппаратных ускорителях и оптимизации перемещения данных в/из аппаратной памяти с помощью удаленных вызовов процедур .
Рост потребительских графических процессоров привел к поддержке вычислительных ядер либо в графических API (называемых вычислительными шейдерами ), либо в специализированных API (таких как OpenCL ), либо в других языковых расширениях.
Автоматическое распараллеливание последовательной программы компилятором является «Святым Граалем» параллельных вычислений, особенно с вышеупомянутым ограничением частоты процессора. Несмотря на десятилетия работы исследователей компиляторов, автоматическое распараллеливание имело лишь ограниченный успех. [60]
Основные языки параллельного программирования остаются либо явно параллельными , либо (в лучшем случае) частично неявными , в которых программист дает компилятору директивы для распараллеливания. Существует несколько полностью неявных языков параллельного программирования — SISAL , Parallel Haskell , SequenceL , System C (для FPGA ), Mitrion-C, VHDL и Verilog .
По мере усложнения компьютерной системы среднее время наработки на отказ обычно уменьшается. Контрольная точка приложения — это метод, при котором компьютерная система делает «снимок» приложения — запись всех текущих распределений ресурсов и состояний переменных, что похоже на дамп ядра —; эту информацию можно использовать для восстановления программы в случае сбоя компьютера. Контрольная точка приложения означает, что программа должна перезапуститься только с последней контрольной точки, а не с начала. Хотя контрольные точки дают преимущества в различных ситуациях, они особенно полезны в высокопараллельных системах с большим количеством процессоров, используемых в высокопроизводительных вычислениях . [61]
Поскольку параллельные компьютеры становятся больше и быстрее, мы теперь можем решать проблемы, решение которых раньше занимало слишком много времени. Такие разнообразные области, как биоинформатика ( сворачивание белков и анализ последовательностей ) и экономика ( математические финансы ), воспользовались преимуществами параллельных вычислений. Общие типы проблем в приложениях параллельных вычислений включают: [62]
Параллельные вычисления также могут применяться для проектирования отказоустойчивых компьютерных систем , особенно с помощью синхронизированных систем, выполняющих одну и ту же операцию параллельно. Это обеспечивает резервирование в случае выхода из строя одного компонента, а также позволяет автоматически обнаруживать и исправлять ошибки, если результаты отличаются. Эти методы можно использовать для предотвращения единичных сбоев, вызванных временными ошибками. [64] Хотя во встроенных или специализированных системах могут потребоваться дополнительные меры, этот метод может обеспечить экономически эффективный подход для достижения n-модульной избыточности в коммерческих готовых системах.
Истоки истинного (MIMD) параллелизма восходят к Луиджи Федерико Менабреа и его «Очерку аналитической машины, изобретенной Чарльзом Бэббиджем» . [66] [67] [68]
В 1957 году компания Compagnie des Machines Bull анонсировала первую компьютерную архитектуру, специально разработанную для параллелизма, — Gamma 60 . [69] Он использовал модель разветвленного соединения и «распределитель программ» для отправки и сбора данных в независимые процессоры, подключенные к центральной памяти, и обратно. [70] [71]
В апреле 1958 года Стэнли Гилл (Ферранти) обсуждал параллельное программирование и необходимость ветвления и ожидания. [72] Также в 1958 году исследователи IBM Джон Кок и Дэниел Слотник впервые обсудили использование параллелизма в числовых вычислениях. [73] Корпорация Burroughs представила D825 в 1962 году, четырехпроцессорный компьютер, который имел доступ к 16 модулям памяти через перекрестный переключатель . [74] В 1967 году Амдал и Слотник опубликовали дискуссию о возможности параллельной обработки на конференции Американской федерации обществ обработки информации. [73] Именно во время этих дебатов был придуман закон Амдала , определяющий предел ускорения из-за параллелизма.
В 1969 году компания Honeywell представила свою первую систему Multics — симметричную многопроцессорную систему, способную параллельно использовать до восьми процессоров. [73] C.mmp , многопроцессорный проект в Университете Карнеги-Меллона в 1970-х годах, был одним из первых мультипроцессоров с более чем несколькими процессорами. Первым мультипроцессором с отслеживающим кэшем, подключенным к шине, стал Synapse N+1, выпущенный в 1984 году. [67]
История параллельных компьютеров SIMD восходит к 1970-м годам. Основанием для создания первых SIMD-компьютеров была попытка амортизировать задержку вентиля блока управления процессора при выполнении нескольких инструкций. [75] В 1964 году Слотник предложил построить компьютер с массовым параллелизмом для Ливерморской национальной лаборатории имени Лоуренса . [73] Его разработка была профинансирована ВВС США , что было самой ранней разработкой параллельных вычислений SIMD, ILLIAC IV . [73] Ключом к ее конструкции был довольно высокий уровень параллелизма, до 256 процессоров, что позволяло машине работать с большими наборами данных в том, что позже будет известно как векторная обработка . Однако ILLIAC IV называли «самым печально известным из суперкомпьютеров», поскольку проект был завершен лишь на четверть, но занял 11 лет и стоил почти в четыре раза дороже первоначальной сметы. [65] Когда в 1976 году он наконец был готов к запуску своего первого реального приложения, он уступил по производительности существующим коммерческим суперкомпьютерам, таким как Cray -1 .
В начале 1970-х годов в Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института Марвин Мински и Сеймур Пейперт начали разрабатывать теорию Общества разума , которая рассматривает биологический мозг как массово-параллельный компьютер . В 1986 году Мински опубликовал «Общество разума» , в котором утверждается, что «разум формируется из множества маленьких агентов, каждый из которых сам по себе бессмыслен». [76] Теория пытается объяснить, как то, что мы называем интеллектом, может быть продуктом взаимодействия неразумных частей. Мински говорит, что самый большой источник идей по поводу теории пришел из его работы по созданию машины, которая использует роботизированную руку, видеокамеру и компьютер для сборки из детских кубиков. [77]
Подобные модели (которые также рассматривают биологический мозг как массивно-параллельный компьютер, т. е. мозг состоит из созвездия независимых или полунезависимых агентов) также были описаны:
{{cite book}}
: CS1 maint: дата и год ( ссылка ){{cite book}}
: |website=
игнорируется ( помощь ){{cite book}}
: CS1 maint: несколько имен: список авторов ( ссылка )Все моделируемые схемы были описаны на языке описания аппаратного обеспечения сверхбыстрых интегральных схем (VHSIC) (VHDL). Аппаратное моделирование проводилось на Xilinx FPGA Artix 7 xc7a200tfbg484-2.
Однако Святой Грааль таких исследований — автоматическое распараллеливание последовательных программ — еще не материализовался. Хотя автоматическое распараллеливание определенных классов алгоритмов было продемонстрировано, такой успех в основном ограничивался научными и численными приложениями с предсказуемым управлением потоком данных (например, структурами вложенных циклов со статически определяемым количеством итераций) и статически анализируемыми шаблонами доступа к памяти. (например, обход больших многомерных массивов данных с плавающей запятой).