Потребность решения сложных прикладных задач с большим объемом вычислений и принципиальная ограниченность максимального быстродействия «классических» – по схеме фон Неймана – ЭВМ привели к появлению многопроцессорных вычислительных систем (МВС) или суперкомпьютеров.
Широкое распространение параллельные вычисления приобрели с переходом компьютерной индустрии на массовый выпуск многоядерных процессоров с векторными расширениями. В настоящие время практически все устройства – от карманных гаджетов и до самых мощных суперкомпьютеров – оснащены многоядерными процессорами. И если вы пишите последовательную программу, не применив распределение работы между разными ядрами центрального процессора и не проведя векторизацию, то вы используете только часть вычислительных возможностей центрального процессора.
Пройдя этот курс, вы познакомитесь с основными архитектурами МВС, с двумя стандартами (OpenMP и MPI), позволяющими писать параллельные программы для систем с общей и распределенной памятью. На простых примерах будут разобраны основные конструкции и способы распределения работы. Выполнение практических заданий позволит вам приобрести практические навыки создания параллельных программ. Курс будет интересен всем, кто занимается программированием.
Для участия в курсе слушателю необходимо иметь базовые знания по программированию с использованием С/С++.
Курс состоит из 9 недель. Каждая неделя курса содержит видеолекции, а также проверочные задания. Сертификат получают слушатели, набравшие более 80 % от максимально возможного количества баллов. При этом итоговый результат, представленный как 100 %, складывается из следующих составляющих: тесты 1–5 недели дают 4 %, тесты 6–9 недели дают 5 %, все практические задания дают 10 %, кроме итогового практического задания по OpenMP, которое дает 20 %.
Na lição
Введение в параллельный мир
На этой неделе мы рассмотрим историю развития высокопроизводительных вычислительных систем. Разберемся, как устроена память в компьютере и какие есть у нее особенности. Также мы с вами узнаем, как устроена оперативная память в многопроцессорных вычислительных системах, и рассмотрим их основные архитектуры. Рассмотрим несколько примеров задач, для решения которых необходимо применять суперЭВМ, и некоторые инструменты создания параллельных программ.
Николай Николаевич Богословский (Nikolay N. Bogoslovskiy)
Кандидат физико-математических наук, доцент (Сandidate of Physics and Mathematics, Associate Professor) Кафедра вычислительной математики и компьютерного моделирования ММФ (Department of Calculus Mathematics and Computer Modelling, Mechanics and Mathematics Faculty)
Евгений Александрович Данилкин (Evgeniy A. Danilkin)
Кандидат физико-математических наук, доцент (Сandidate of Physics and Mathematics, Associate Professor) Кафедра вычислительной математики и компьютерного моделирования ММФ (Department of Calculus Mathematics and Computer Modelling, Mechanics and Mathematics Faculty)
[МУЗЫКА]
[МУЗЫКА]
Здравствуйте!
В прошлой лекции я задал вопрос о том, почему
время выполнения двух программ, решающих одну и ту же задачу, бывает различным.
Давайте разберемся.
Я наглядно это продемонстрирую, а потом мы с вами рассмотрим основные
архитектуры многопроцессорных вычислительных систем.
Итак, у нас есть 2 матрицы, которые мы перемножаем.
Напомню, что в языке C/C++ матрицы в памяти располагаются построчно.
То есть сначала записаны все элементы первой строки,
следом за ней — элементы второй строки и так далее.
Еще раз напомню, в более высокий уровень памяти
в иерархической структуре копируется блок данных,
содержащий необходимую информацию, а не отдельные значения.
Также давайте для упрощения будем считать, что у нас только 1 уровень кэш-памяти.
Сначала рассмотрим самую медленную версию программы с порядком циклов j, k, i.
Мы начинаем умножать матрицы, и для проведения операции
в указанной строке нам требуются элементы A00, B00 и C00.
Так как это только начало выполнения программы,
то при попытке найти эти элементы в кэш-памяти произойдет промах,
и поиск будет осуществлен в оперативной памяти.
Там этот элемент есть, и произойдет копирование блока данных,
содержащего данный элемент.
Предположим, что вместе с необходимым элементом копируются еще 3 элемента,
то есть в данном случае скопируются в кэш элементы: A00, A01, A02 и A03.
Для матрицы B и С — элементы с такими же номерами.
Далее, элементы A00, B00 и С00 скопируются в регистры,
произведется операция перемножения A00 на B00 и сложение с элементом C00.
Затем счетчик A увеличится на 1 и будет равен 1.
Теперь необходимо будет выполнить следующую операцию.
C[1][0] = C[1][0] + A[1][0] ∗ B[0][0],
то есть для выполнения операции нам потребуются элементы C10, A10 и B00.
Сначала проводится проверка: есть ли эти элементы в кэш-памяти.
Из этих 3-х элементов в кэш находится только элемент B00.
Поэтому элементы C10 и A10 будут копироваться из оперативной памяти.
Это медленнее, чем читать из кэш-памяти.
Далее вы можете проверить сами, что такая ситуация будет повторяться.
Теперь давайте рассмотрим программу с порядком циклов i, k, j.
Мы начинаем умножать матрицы, и для проведения операции C[0][0] = C[0][0]
+ A[0][0] ∗ B[0][0] нам требуются элементы: A00, B00 и С00.
Далее произойдет все то же самое, что и в предыдущей программе.
В кэш-память скопируется по 4 элемента первой строки каждой матрицы.
Элементы, необходимые для выполнения операции,
скопируются в регистры и операция будет выполнена.
Далее счетчик j увеличивается на 1 и будет равен 1.
Теперь необходимо будет выполнить следующую операцию:
C[0][1] = C[0][1] + A[0][0] ∗ B[0][1].
То есть, для выполнения операции нам потребуются элементы C01, A00 и B01.
Сначала проводится проверка, есть ли эти элементы в кэш-памяти.
Все 3 элемента есть в кэш-памяти, поэтому элементы будут копироваться
из кэш-памяти в регистры и будет проведена операция.
И так далее.
Как видите,
при таком порядке цикла максимально эффективно используется кэш-память,
и время получения значений, необходимых для вычислений, будет существенно меньше,
так как время доступа из кэш-памяти намного меньше, чем из оперативной памяти.
Поэтому очень важно в правильном порядке хранить данные и в правильном порядке
их обрабатывать.
Я думаю, что вы поняли, что если вы хотите написать эффективную программу,
то нужно аккуратно работать с памятью и с данными.
Ну а теперь давайте мы рассмотрим архитектуры высокопроизводительных
вычислительных систем и их классификацию.
К сожалению, увеличение быстродействия центральных процессоров ограничено.
Это ограничение связано с физическими свойствами.
И к сожалению, их пока преодолеть не удается и я думаю,
что в ближайшем будущем этого не произойдет.
Вследствие этих причин для повышения производительности
приходится идти по пути создания параллельных вычислительных систем.
То есть систем,
в которых предусмотрена одновременная реализация ряда вычислительных процессов,
связанных с решением одной задачи на разных процессорных элементах.
Все современные процессоры имеют несколько ядер.
Уже никого не удивишь компьютером с четырехъядерным процессором или телефоном.
Но как мы увидели, когда рассматривали историю,
параллельность и многопроцессорность появилась уже давно.
Последние десятилетия характеризуются бурным развитием микроэлектроники.
Как следствие,
появилось очень много разнообразных архитектур вычислительных систем.
И так же бурно развиваются параллельные вычисления,
поэтому все современные суперкомпьютеры являются параллельными системами.
Давайте внесем немного ясности в архитектуру вычислительных систем,
рассмотрев одну из классификаций.
Среди всех рассматриваемых систем, классификаций, наибольшее признание
получила классификация, предложенная в 1966 году Флинном.
В ее основу положено понятие потока, под которым понимается последовательность
элементов, команд или данных, обрабатываемых процессором.
В зависимости от количества потоков, команд и потоков данных,
Флинн выделяет 4 класса архитектур.
Первый класс — это SISD, одиночный поток команд и одиночный поток данных.
Представителями этого класса являются прежде всего классические
фон-неймановские компьютеры, где имеется только один поток команд,
команды обрабатываются последовательно,
и каждая команда инициирует одну операцию, с одним потоком данных.
Второй класс — это MISD, множественный поток команд и одиночный поток данных.
Из определения следует, что в архитектуре вычислительной системы присутствует
множество процессоров, обрабатывающих один и тот же поток данных.
Ни сам Флинн, ни другие специалисты в области архитектуры компьютеров
до сих пор не сумели представить убедительный пример реально существующей
вычислительной системы, построенной на данном принципе.
Третий класс — SIMD, одиночный поток команд и множественный поток данных.
Компьютеры данной архитектуры позволяют выполнять одну арифметическую
операцию сразу над многими данными, элементами вектора.
Бесспорными представителями класса SIMD считаются матрицы процессоров, где
единое управляющее устройство контролирует множество процессорных элементов.
Все процессорные элементы получают от устройства управления одинаковую команду
и выполняют ее над своими локальными данными.
В принципе, в этот класс можно включить и векторно-конвейерные компьютеры,
если каждый элемент вектора рассматривать как отдельный элемент потока данных.
Последний класс, MIMD — множественный поток команд и множественный поток данных.
Класс предполагает наличие в вычислительной системе множества
устройств обработки команд, объединенных в единый комплекс и работающих
как каждый со своим потоком команд и данных.
Класс MIMD чрезвычайно широк,
поскольку включает в себя всевозможные мультипроцессорные системы.
Схема классификации Флинна является в настоящее время наиболее распространенной,
она позволяет произвести первоначальную оценку параллельно-вычислительной системы,
и, как правило, этого бывает достаточно.
Архитектуры параллельных вычислительных систем развиваются очень бурно,
существует множество различных вариантов.
Но если отбросить все мелочи и оставить основную суть,
то останется на самом деле всего 2 класса.
Первый класс — это компьютеры с общей памятью.
Системы, построенные по такому принципу,
иногда называют мультипроцессорные системы или просто мультипроцессорами.
В системе присутствуют несколько равноправных процессоров,
имеющих одинаковый доступ к единой памяти.
Все процессоры разделяют между собой общую память,
отсюда еще одно название компьютеров этого класса — компьютеры с общей памятью.
Все процессоры работают с единым адресным пространством.
И если один процессор записал значение 79 в слово по адресу F1, то другой процессор,
прочитав слово, расположенное по адресу F1, получит то же значение 79.
Второй класс — это компьютеры с распределенной памятью, которые по
аналогии с предыдущим классом иногда будем называть мультикомпьютерными системами.
По сути дела, каждый вычислительный узел является полноценным компьютером со своим
Николай Николаевич Богословский (Nikolay N. Bogoslovskiy)Кандидат физико-математических наук, доцент (Сandidate of Physics and Mathematics, Associate Professor)
Евгений Александрович Данилкин (Evgeniy A. Danilkin)Кандидат физико-математических наук, доцент (Сandidate of Physics and Mathematics, Associate Professor)
