Файл: Мультипроцессоры (Мультипроцессорная когерентность кэш – памяти ).pdf

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

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

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

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

Многопроцессорные системы за годы развития вычислительной техники претерпели ряд этапов своего развития. Исторически первой стала осваиваться технология машины типа SIMD (Single Instruction Multiple Data), состоящие из большого числа идентичных процессорных элементов, имеющих собственную память. Все процессорные элементы в такой машине выполняют одну и ту же программу. Однако в настоящее время наметился устойчивый интерес к архитектурам MIMD (Multiple Instruction Multiple Data). Базовой моделью вычислений на MIMD-мультипроцессоре является совокупность независимых процессов, эпизодически обращающихся к разделяемым данным. Архитектура MIMD может использовать все преимущества современной микропроцессорной технологии на основе учета соотношения стоимость/производительность. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров. Поскольку имеется единственная память с одним и тем же временем доступа, эти машины иногда называются UMA (Uniform Memory Access). Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является очень эффективным и представляет собой популярный объект исследования. Именно такая многопроцессорная система и будет являться объектом исследования данной курсовой работы.

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

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

Объект исследования:

В процессе работы программа должна обработать очереди из 100 и 1000 заявок длинной 1-8 и 3-6; каждая очередь должна быть обработана в системе, содержащей 2, 5 и 10 процессоров.

Предмет исследования:

Сумма длин всех заявок данной очереди;

Время, необходимое для обработки данной очереди заданий при наличии 2-х, 5-ти и 10-ти процессоров;

Среднее время простоя процессоров;

Среднее время выполнения 1 заявки.

Все полученные данные должны быть занесены в таблицу.

1. Классификация вычислительных систем

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

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

Параллельные вычислительные системы часто подразделяют согласно таксономии Флинна, предложенной в 1966 году и расширенной в 1972. Выделяются два крупных класса ЭВМ: SIMD – машины (Single Instruction Multiple Data – один поток команд выполняет операции над множеством потоков данных) и MIMD (Multiple Instruction Multiple Data – большое количество потоков команд выполняют операции над множеством потоков данных) [5]. Данная классификация, как и любая другая, несовершенна, так как существуют ЭВМ прямо в неё не попадающие, а также ряд важных признаков не нашли в ней отражение. Как пример, векторные процессоры часто относят к ЭВМ типа SIMD, хотя высокая производительность данного типа машин обусловлена совсем другой формой параллелизма – конвейерной

обработкой данных. Многопроцессорные векторные системы, такие как CRAY EL, CRAY J90, CRAY T90 содержат в себе некоторое количество векторных процессоров и, благодаря этому, их можно выделить в класс MSIMD (Multiple SIMD) [2].

Так же таксономия Флинна не учитывает ещё некоторые достаточно важные для параллельных вычислительных моделей параметры. К таким параметрам можно отнести «зернистость» параллельных вычислений (крупнозернистые алгоритмы содержат в себе большие независимые задачи, которую можно решать параллельно, а мелкозернистые содержат задачи малые) и методы синхронизаций, используемых при решении тех или иных задач.

Можно выделить четыре основных вида вычислительных параллельных архитектур.

1.1 Конвейерная и векторная обработка

В 60-х годах принцип векторной обработки уже стал появляться в универсальных ЭВМ. Но к суперкомпьютерам и большим вычислительным системам данный подход наиболее широко стал применяться только в 80-х –90-х годах. Но активно развивающаяся отрасль производства процессоров вытеснила применение векторных ПЭ. Но, как говорится, всё возвращается на круги своя, и в настоящее время разработчики программных продуктов, требующих от машин высокой производительности, снова вспомнили этот вид параллельной обработки и пытаются внедрить его в свои исходные коды.

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

Как только скорость добавления начнёт значительно расходиться с производительностью конвейера произойдёт простой тех или иных его частей и общая эффективность проводимых вычислений снизится. Векторные команды наиболее часто дают возможность полностью загрузить конвейер данными.

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

1.2 Машины типа SIMD

Данный подход в построении вычислений был внедрён в процессоры общего назначения в начале 90-х годов. Первый набор SIMD инструкций для процессоров имел название SSE. Данный тип выделяется тем, что с момента его разработки усовершенствование идёт до сих пор. Последнее усовершенствование SIMD команд было в 2012 году и имело название AVX-512. Что интересно, машины с поддержкой AVX-512 появятся только в конце 2015 года.

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

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

Если сравнивать векторный процессор, с его ограничениями и тонкостями в организации конвейера, с процессором матричным, использующимся в SIMD – машинах, то последний является куда более гибким [10]. Для обработки матричных процессоров используются универсальные программируемые ЭВМ, в связи с чем решаемые задачи могут быть сложными и содержать в своих алгоритмах решения ветвления. Как правило, в исходном коде данная вычислительная модель представлена почти так же, как и векторные команды, с той лишь разницей, что в данном случае каждая итерация цикла над элементами массива выдаёт результаты, которые никак не будут использованы на последующих итерациях.

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

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

1.3 Машины типа MIMD

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

Так как термин «мультипроцессор» описывает большинство MIMD – систем (точно такая же ситуация и в случае векторных процессоров и SIMD – машин), то, зачастую он используется в качестве синонима при описании систем с MIMD архитектурой. В MIMD – системе каждый из процессорных элементов (ПЭ) обычно работает над своей задачей независимо от остальных процессоров. По причине того, что процессорам всё-таки необходимо иногда

связываться друг с другом необходимо ввести более подробную классификацию MIMD – машин. Мультипроцессоры с общей памятью имеют память данных и команд, доступную для всех процессорных элементов. Связь ПЭ с общей памятью осуществляется посредством общей шины данных и сети обмена. Противоположную структуру имеют многопроцессорные системы с локальной памятью. Для каждого ПЭ выделается свой блок памяти, и он доступен лишь ему [15]. При помощи сети обмена процессорные элементы связываются друг с другом, если возникает необходимость передачи данных между подзадачами.

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