Это часть процессора, которая выполняет один поток инструкций

Обновлено: 07.07.2024

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

Обзор

Что такое параллельные вычисления?

Последовательные вычисления

Традиционно программное обеспечение писалось для последовательных вычислений:

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

Например:

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

Проще говоря, параллельные вычисления — это одновременное использование нескольких вычислительных ресурсов для решения вычислительной задачи:

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

Например:

Вычислительная задача должна уметь:
- Разбить на отдельные части работы, которые можно решать одновременно;
- Выполнение нескольких программных инструкций в любой момент времени;
- Решайте задачи быстрее, используя несколько вычислительных ресурсов, чем один вычислительный ресурс.
- Один компьютер с несколькими процессорами/ядрами
- Произвольное количество таких компьютеров, объединенных в сеть
Параллельные компьютеры
- Сегодня практически все автономные компьютеры параллельны с аппаратной точки зрения:
  - Несколько функциональных блоков (кеш L1, кэш L2, переход, предварительная выборка, декодирование, операции с плавающей запятой, обработка графики (GPU), целые числа и т. д.)
  - Несколько исполнительных блоков/ядер
  - Несколько аппаратных потоков
  - Сети соединяют несколько автономных компьютеров (узлов) для создания больших параллельных компьютерных кластеров.
  - Например, на приведенной ниже схеме показан типичный кластер параллельных компьютеров LLNL:
    - Каждый вычислительный узел сам по себе является многопроцессорным параллельным компьютером
    - Несколько вычислительных узлов объединены в сеть Infiniband.
    - Узлы специального назначения, также многопроцессорные, используются для других целей.
    - Большинство больших параллельных компьютеров (суперкомпьютеров) в мире представляют собой кластеры оборудования, произведенного несколькими (в основном) известными поставщиками.
    Зачем использовать параллельные вычисления?
    
    Реальный мир чрезвычайно сложен
    - В естественном мире множество сложных, взаимосвязанных событий происходит одновременно, но в рамках временной последовательности.
    - По сравнению с последовательными вычислениями параллельные вычисления гораздо лучше подходят для моделирования, имитации и понимания сложных явлений реального мира.
    - Например, представьте себе их последовательное моделирование:
    Основные причины использования параллельного программирования
    
    ЭКОНОМЬТЕ ВРЕМЯ И/ИЛИ ДЕНЬГИ
    - Теоретически, выделение большего количества ресурсов для выполнения задачи сократит время ее выполнения и потенциально сэкономит средства.
    - Параллельные компьютеры могут быть собраны из дешевых, широко распространенных компонентов.
    РЕШАТЬ БОЛЬШИЕ/БОЛЕЕ СЛОЖНЫЕ ПРОБЛЕМЫ
    
    ОБЕСПЕЧИТЬ ПАРАЛЛЕЛЬНОСТЬ
    - Один вычислительный ресурс может одновременно выполнять только одну операцию. Несколько вычислительных ресурсов могут выполнять множество задач одновременно.
    - Пример. Сети для совместной работы представляют собой глобальную площадку, где люди со всего мира могут встречаться и работать «виртуально».
    ИСПОЛЬЗОВАТЬ НЕМЕСТНЫЕ РЕСУРСЫ
    - Использование вычислительных ресурсов в глобальной сети или даже в Интернете, когда локальных вычислительных ресурсов недостаточно или недостаточно.
    - Пример. SETI@home (setiathome.berkeley.edu) насчитывает более 1,7 миллиона пользователей почти во всех странах мира (май 2018 г.).
    ЛУЧШЕ ИСПОЛЬЗОВАТЬ БАЗОВОЕ ПАРАЛЛЕЛЬНОЕ ОБОРУДОВАНИЕ
    - Современные компьютеры, даже ноутбуки, имеют параллельную архитектуру с несколькими процессорами/ядрами.
    - Параллельное программное обеспечение специально предназначено для параллельного оборудования с несколькими ядрами, потоками и т. д.
    - В большинстве случаев последовательные программы, запускаемые на современных компьютерах, «тратят впустую» потенциальную вычислительную мощность.
    Будущее
    
    Кто использует параллельные вычисления?
    
    Наука и техника
    
    Исторически параллельные вычисления считались «высшим уровнем вычислений» и использовались для моделирования сложных задач во многих областях науки и техники:
    - Атмосфера, Земля, Окружающая среда
    - Физика - прикладная, ядерная, частица, конденсированное состояние, высокое давление, термоядерный синтез, фотоника.
    - Бионаука, биотехнология, генетика
    - Химия, молекулярные науки
    - Геология, сейсмология
    - Машиностроение: от протезов до космических кораблей
    - Электротехника, схемотехника, микроэлектроника
    - Информатика, математика
    - Оборона, Оружие
    Промышленные и коммерческие
    
    Сегодня коммерческие приложения являются равной или даже большей движущей силой в разработке более быстрых компьютеров. Эти приложения требуют сложной обработки больших объемов данных. Например:
    
    Существуют различные стили архитектуры системы и памяти, которые необходимо учитывать при разработке программы или параллельной системы. Это очень необходимо, потому что одна система и стиль памяти могут подходить для одной задачи, но могут быть подвержены ошибкам для другой задачи.
    
    Архитектуры компьютерных систем, поддерживающие параллелизм
    
    Майкл Флинн в 1972 году разработал таксономию для классификации различных стилей архитектуры компьютерных систем. Эта таксономия определяет четыре различных стиля следующим образом:
    - Единый поток инструкций, единый поток данных (SISD)
    - Один поток инструкций, множественный поток данных (SIMD)
    - Множественный поток инструкций, один поток данных (MISD)
    - Множественный поток инструкций, множественный поток данных (MIMD).
    Один поток инструкций, один поток данных (SISD)
    
    Как следует из названия, такие системы будут иметь один последовательный входящий поток данных и один единственный процессор для выполнения потока данных. Они похожи на однопроцессорные системы с параллельной вычислительной архитектурой. Ниже приведена архитектура SISD —
    
    Преимущества SISD
    
    Преимущества архитектуры SISD заключаются в следующем:
    - Требуется меньше энергии.
    - Нет проблем со сложным протоколом связи между несколькими ядрами.
    Недостатки SISD
    
    Недостатки архитектуры SISD заключаются в следующем:
    - Скорость архитектуры SISD ограничена, как и у одноядерных процессоров.
    - Он не подходит для больших приложений.
    Один поток инструкций, множественный поток данных (SIMD)
    
    Как следует из названия, такие системы будут иметь несколько входящих потоков данных и количество процессоров, которые могут выполнять одну инструкцию в любой момент времени. Они похожи на многопроцессорные системы с параллельной вычислительной архитектурой. Ниже приведена архитектура SIMD —
    
    Лучшим примером использования SIMD являются видеокарты. Эти карты имеют сотни отдельных процессоров. Если говорить о вычислительной разнице между SISD и SIMD, то для суммирующих массивов [5, 15, 20] и [15, 25, 10] архитектура SISD должна была бы выполнять три разные операции добавления. С другой стороны, с архитектурой SIMD мы можем добавить их за одну операцию добавления.
    
    Преимущества SIMD
    
    Преимущества архитектуры SIMD заключаются в следующем:
    
    Одна и та же операция над несколькими элементами может быть выполнена с использованием только одной инструкции.
    
    Пропускная способность системы может быть увеличена за счет увеличения количества ядер процессора.
    
    Скорость обработки выше, чем у архитектуры SISD.
    
    Недостатки SIMD
    
    Недостатки архитектуры SIMD заключаются в следующем:
    - Существует сложная связь между количеством ядер процессора.
    - Стоимость выше, чем у архитектуры SISD.
    Поток данных с несколькими инструкциями (MISD)
    
    Системы с потоком MISD имеют несколько блоков обработки, выполняющих разные операции, выполняя разные инструкции для одного и того же набора данных. Ниже приведена архитектура MISD —
    
    Представители архитектуры MISD еще не существуют в коммерческих целях.
    
    Поток данных с несколькими инструкциями (MIMD)
    
    В системе, использующей MIMD-архитектуру, каждый процессор в многопроцессорной системе может параллельно выполнять разные наборы инструкций независимо от разных наборов данных. Это противоположно архитектуре SIMD, в которой одна операция выполняется над несколькими наборами данных. Ниже приведена архитектура MIMD —
    
    Обычный мультипроцессор использует архитектуру MIMD. Эти архитектуры в основном используются в ряде прикладных областей, таких как автоматизированное проектирование/автоматизированное производство, моделирование, моделирование, коммуникационные коммутаторы и т. д.
    
    Архитектуры памяти, поддерживающие параллелизм
    
    При работе с такими понятиями, как параллелизм и параллелизм, всегда возникает необходимость ускорить программы. Одним из решений, найденных разработчиками компьютеров, является создание мультикомпьютеров с общей памятью, то есть компьютеров с единым физическим адресным пространством, к которому обращаются все ядра процессора. В этом сценарии может быть несколько различных архитектурных стилей, но ниже приведены три важных архитектурных стиля:
    
    UMA (унифицированный доступ к памяти)
    
    В этой модели все процессоры равномерно используют физическую память. Все процессоры имеют одинаковое время доступа ко всем словам памяти. Каждый процессор может иметь собственную кэш-память. Периферийные устройства подчиняются набору правил.
    
    Когда все процессоры имеют равный доступ ко всем периферийным устройствам, система называется симметричной мультипроцессорной. Когда только один или несколько процессоров могут получить доступ к периферийным устройствам, система называется асимметричной мультипроцессорной.
    
    Неоднородный доступ к памяти (NUMA)
    
    В многопроцессорной модели NUMA время доступа зависит от расположения слова памяти. Здесь общая память физически распределяется между всеми процессорами, называемая локальной памятью. Совокупность всей локальной памяти образует глобальное адресное пространство, к которому могут обращаться все процессоры.
    
    Архитектура кэш-памяти (COMA)
    
    Модель COMA — это специализированная версия модели NUMA.Здесь вся распределенная основная память преобразуется в кэш-память.
    
    Параллельные вычисления — это вычисления, при которых задания разбиваются на отдельные части, которые могут выполняться одновременно. Каждая часть далее разбита на серию инструкций. Инструкции из каждой части выполняются одновременно на разных процессорах. Параллельные системы имеют дело с одновременным использованием нескольких компьютерных ресурсов, которые могут включать один компьютер с несколькими процессорами, несколько компьютеров, соединенных сетью для формирования кластера параллельной обработки, или их комбинацию.
    Параллельные системы более сложны. программировать, чем компьютеры с одним процессором, потому что архитектура параллельных компьютеров соответственно различается, и процессы нескольких процессоров должны координироваться и синхронизироваться.
    
    Основой параллельной обработки являются процессоры. В зависимости от количества инструкций и потоков данных, которые могут обрабатываться одновременно, вычислительные системы подразделяются на четыре основные категории:
    Машины MIMD делятся на MIMD с общей памятью и MIMD с распределенной памятью в зависимости от того, как PE связаны с основной памятью.
    
    Справочник –
    Таксономия Флинна
    Мастерство облачных вычислений: основы и программирование приложений
    
    В этой лекции впервые была представлена базовая структура простого одноядерного процессора. Этот процессор, показанный на рисунке 1, содержит блок выборки/декодирования, АЛУ, а также некоторый контекст и регистры. Лекция была посвящена трем способам, которыми процессоры могут проявлять параллелизм. Во-первых, они могут иметь несколько ядер, что позволяет процессору одновременно выполнять разные инструкции для разных данных. Во-вторых, ядро может содержать несколько АЛУ, что позволяет ему одновременно выполнять один и тот же поток инструкций для нескольких фрагментов данных. Это называется обработкой SIMD. Чтобы SIMD был эффективным, один и тот же код должен выполняться на большом количестве данных; это называется когерентным кодом. Наконец, процессор может хранить несколько контекстов на кристалле, что позволяет переключаться между контекстами различных потоков.
    
    Вторая половина лекции была посвящена памяти. Задержка памяти — это время, необходимое для извлечения памяти, а пропускная способность памяти — это скорость, с которой могут выполняться операции с памятью. Операции с памятью могут занимать сотни тактовых циклов, поэтому важно найти способы предотвратить замедление работы программ. Одним из полезных методов является использование многопоточных процессоров для запуска исполняемого потока, в то время как другой ожидает операции с памятью. Эта стратегия скрывает задержку. Кэши также решают эту проблему, на этот раз уменьшая задержку. Наконец, в лекции обсуждались конкретные процессоры, тип оборудования, которое они используют для параллелизма, и компромиссы, на которые они идут с точки зрения задержки памяти и пропускной способности.
    
    Параллелизм
    
    Предположим, у нас есть базовый воображаемый процессор, который может выполнять только одну инструкцию за такт. Процессор состоит из трех частей: выборка/декодирование, арифметико-логическое устройство (ALU) и контекст выполнения.
    - Выборка/декодирование загружает следующую инструкцию из памяти.
    - АЛУ выполняет инструкцию.
    - Контекст выполнения содержит состояние кода, например регистров.
    Недостаток нашего нынешнего процессора в том, что он выполняет каждую инструкцию последовательно. Однако возможно, что существует несколько независимых инструкций. Вы потенциально можете выполнять эти инструкции параллельно. Если мы изменим наш процессор на суперскалярный процессор, мы сможем выполнять несколько инструкций за такт, используя несколько АЛУ, и получить правильный ответ. Параллельное выполнение нескольких инструкций называется параллелизмом на уровне инструкций (ILP) и используется суперскалярными процессорами.
    
    Этот процессор, как показано на рисунке 2, имеет одно ядро с базовыми блоками, которые мы обсуждали ранее, и дополнительными блоками, как показано на изображении, которые пытаются повысить производительность. Однако, если мы удалим эти части, мы сможем использовать дополнительное пространство для добавления дополнительного ядра к нашему процессору. Это сделает процессор менее сложным, но теперь у нас есть несколько ядер, поэтому мы можем выполнять задачи параллельно. Хотя каждое ядро может работать медленнее, чем наше предыдущее ядро, с дополнительным ускорением, у нас есть два ядра, которые могут работать одновременно, поэтому мы можем работать так же быстро, если не быстрее, как предыдущее ядро. Чтобы воспользоваться преимуществами нескольких ядер, нам нужно найти независимые потоки инструкций. Компилятору чрезвычайно сложно определить, какие потоки являются независимыми, поэтому в некоторых "параллельных" языках есть такие конструкции, как "forall", подразумевающие, что итерации цикла независимы, что позволяет компилятору планировать их в любом порядке.
    
    Теперь рассмотрим, когда мы перебираем числа от 1 до 100 и вычисляем квадрат каждого числа. Тело цикла содержит одну и ту же инструкцию для каждой итерации. В нашем нынешнем процессоре нам нужно будет получить одну и ту же инструкцию 100 раз, чтобы выполнить этот цикл. Если бы мы знали, что будем продолжать использовать одну и ту же инструкцию, мы могли бы сэкономить время, выполнив несколько циклов одновременно. Это известно как одна инструкция, несколько данных (SIMD). Используя SIMD-обработку, мы можем загрузить инструкцию во все ALU, а затем выполнить несколько циклов параллельно на всех ALU. SIMD сохраняет данные в векторном массиве с плавающей запятой и выполняет инструкции для самого вектора. Однако, если в некоторых циклах тело различается, вы все равно можете получить параллелизм, используя несколько ядер, но это может ухудшить векторные инструкции. Например, предположим, что у вас есть условное выражение в цикле for. Каждая итерация цикла может не принимать одну и ту же ветвь в условном выражении.
    
    Условное выполнение может иметь очень низкую производительность. Разные ветки будут выполняться для разных потоков, и мы всегда будем выполнять вычисления, которые будут проигнорированы.
    
    Есть несколько полезных терминов, о которых вам следует знать.
    - Последовательное выполнение. Что происходит, когда многие инструкции похожи. В этом случае выгодно использовать SIMD, поскольку нам нужно получить инструкции только один раз.
    - Дивергентное выполнение: Противоположное согласованному выполнению, то есть инструкции не похожи. Когда разные экземпляры программы должны будут выполнять разные инструкции. Это может произойти, если разные экземпляры используют разные ветви условного оператора или если разные экземпляры выполняют больше итераций цикла, чем другие. SIMD бесполезен для расходящегося выполнения, поскольку инструкции между экземплярами, вероятно, различаются, поэтому мы не можем оптимизировать, заставляя каждую дорожку выполнять одну и ту же инструкцию одновременно.
    - Явный SIMD: распараллеливание, происходящее во время компиляции. Например, если программист использует такие термины, как "forall", компилятор знает, что SIMD можно использовать для оптимизации цикла.
    SIMD будет еще медленнее при расходящемся выполнении, так как ему нужно запускать оба пути ветвления и маскировать результаты
    
    Этот комментарий был отмечен как полезный 0 раз.
    
    Действительно ли маскирование снижает производительность? Я не уверен, что понимаю, почему это обязательно должно быть так.
    
    Этот комментарий был отмечен как полезный 0 раз.
    
    Память
    
    Прежде чем мы обсудим память, нам нужно ознакомиться с парой терминов.
    - Задержка памяти: время, необходимое для выполнения запроса памяти. Обычно это занимает сотни циклов.
    - Пропускная способность памяти: скорость, с которой система памяти может передавать данные процессору.
    - Остановка: происходит, когда процессор не может продолжать выполнение кода из-за зависимости от предыдущей инструкции. Чтобы продолжить выполнение текущей инструкции, процессор должен дождаться завершения предыдущей инструкции. Задержка может произойти, когда нам нужно загрузить память.
    Задержка памяти увеличивает время выполнения программы. Мы хотели бы попытаться уменьшить эффект задержки памяти. Один из способов уменьшить задержку — использовать кеш. Кэши не только уменьшают задержку памяти, но и обеспечивают высокую пропускную способность (лекция 2, слайд 41). Однако, если данные не хранятся в кеше, нам все равно приходится извлекать их из памяти, поэтому у нас все еще есть проблема с задержкой. Мы можем решить эту проблему с помощью предварительной выборки.Если мы можем заранее предсказать, что программа запросит часть памяти, мы можем выполнить предварительную выборку данных, что скроет задержку (примечание: это отличается от уменьшения задержки. Извлечение данных все равно займет такое же количество задержек) .
    
    Несмотря на то, что кэширование и предварительная выборка могут помочь при задержках, иногда нам приходится иметь дело с задержками. Когда процесс останавливается, он не может продолжить выполнение текущей инструкции. Однако возможно, что в другом потоке есть другие части кода, которые мы можем выполнить, пока ждем данные, необходимые для завершения текущей инструкции. Таким образом, мы можем сократить задержки с помощью многопоточности, когда мы запускаем другой поток, в то время как старый поток ожидает своих данных. Вот как мы можем скрыть задержку внутри программы. Запуская другие потоки, мы скрываем тот факт, что теряем информацию для потока, которому нужны данные
    
    Один из недостатков заключается в том, что мы снижаем пропускную способность, поскольку многопоточность увеличивает время, затрачиваемое отдельным потоком на выполнение назначенной задачи. Однако время на выполнение всех задач должно уменьшиться, так как мы почти всегда делаем работу. Многопоточность также требует большой пропускной способности памяти, потому что большее количество потоков обычно означает, что нам потребуется больше данных. У нас есть только ограниченное количество места в кеше, поэтому, если у нас будет больше данных, у нас будет меньше места в кеше для хранения данных для каждого потока. Это означает, что нам, вероятно, придется чаще извлекать данные из памяти. Однако мы можем скрыть эту задержку, используя методы, описанные ранее. Мы можем использовать GPU вместо CPU, если хотим, чтобы наш процессор больше ориентировался на пропускную способность. Процессор имеет большой кеш и мало потоков. С другой стороны, GPU имеет меньший кэш, больше потоков и большую пропускную способность. Несмотря на то, что у графического процессора меньший кеш, он может скрыть задержку памяти с помощью многопоточности. Пока наша пропускная способность позволяет загружать данные и мы можем загружать потоки, мы можем скрывать задержки.
    
    < /p>
    Допустим, мы хотим перемножить два вектора A и B, каждый из которых содержит миллионы элементов. Мы будем выполнять это на графическом процессоре NVIDIA GTX 480, который может выполнять 480 MUL за такт (1,4 ГГц), который может выполнять три операции с памятью (12 байт) для каждого MUL. Можно было бы подумать, что эта задача будет легко распараллеливаться, поскольку каждое умножение независимо. Однако задача ограничена пропускной способностью. Время выполнения умножения требует гораздо меньше времени, чем выборка данных. Для того, чтобы потоки были заняты, нам потребуется около 8,4 ТБ/с пропускной способности. Однако, хотя это и не оптимально, использование GPU все же в 8 раз быстрее, чем CPU. Поэтому, чтобы параллельная программа эффективно использовала ресурсы графического процессора, соотношение между выборкой памяти и вычислениями должно иметь правильный баланс.
    
    Упражнения:
    
    Каковы затраты и преимущества добавления следующего в чип? Для каждого варианта приведите пример кода, который принесет наибольшую пользу от этого варианта.
    - Ядра
    - ALU
    - Контексты потоков
    Традиционно (например, в 15-410) переключение контекста потока реализовывалось путем сохранения состояния потока, с которого был переключен (например, регистры), в памяти ядра и восстановления состояния потока, на который был переключен, из памяти. Чем переключение контекста отличается от аппаратной поддержки потоков? Что мы можем сделать с аппаратной поддержкой, без которой мы не могли бы обойтись?
    
    Рассчитайте, сколько времени потребуется 100 автомобилям, чтобы добраться из Питтсбурга в Филадельфию. В какой-то момент маршрута 4-полосное шоссе переходит в 2-полосное шоссе. Задержка — это время, которое требуется одному автомобилю, чтобы добраться из Питтсбурга в Филадельфию, а пропускная способность — это количество полос на дороге.
    
    Задержка памяти определяется количеством времени, которое требуется для завершения операции с памятью, а пропускная способность определяется скоростью, с которой данные передаются процессору.
    
    Этот комментарий был отмечен как полезный 0 раз.
    
    Выглядит действительно здорово, ребята, спасибо! Одно общее предложение: было бы полезно иметь ссылки на цифры, когда вы говорите о них. Прямо сейчас я не уверен, какое объяснение процессора соответствует какой фигуре. Вместо «этот процессор» было бы гораздо понятнее сказать «процессор, показанный на рис. 2». Спасибо :)
    
    Читайте также: