[МУЗЫКА]
[МУЗЫКА]
Здравствуйте!
В прошлой лекции я задал вопрос о том, почему
время выполнения двух программ, решающих одну и ту же задачу, бывает различным.
Давайте разберемся.
Я наглядно это продемонстрирую, а потом мы с вами рассмотрим основные
архитектуры многопроцессорных вычислительных систем.
Итак, у нас есть 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.
Второй класс — это компьютеры с распределенной памятью, которые по
аналогии с предыдущим классом иногда будем называть мультикомпьютерными системами.
По сути дела, каждый вычислительный узел является полноценным компьютером со своим
процессором, памятью, подсистемой ввода-вывода, операционной системой.
В такой ситуации, если один процессор запишет значение 79 по адресу F1,
то это никак не повлияет на то, что по тому же адресу прочитает другой процессор,
поскольку каждый из них работает в своем адресном пространстве.
В каждом из этих классов есть еще деление и детализация архитектур компьютеров.
Но на начальном этапе достаточно определить,
к какому из этих основных классов относится вычислительная система,
чтобы выбрать инструменты создания параллельных программ.
На этой лекции мы с вами рассмотрели популярную классификацию Флинна и 2
основные архитектуры параллельных вычислительных систем.
Я думаю, что у каждого из вас есть компьютер дома.
А к какой архитектуре вы отнесете свой компьютер?
К архитектурным системам общей памяти или распределенной памяти?
А также попытайтесь классифицировать свой компьютер по классификации Флинна.
До встречи!
Николай Николаевич Богословский (Nikolay N. Bogoslovskiy)Кандидат физико-математических наук, доцент (Сandidate of Physics and Mathematics, Associate Professor)
Евгений Александрович Данилкин (Evgeniy A. Danilkin)Кандидат физико-математических наук, доцент (Сandidate of Physics and Mathematics, Associate Professor)
