Топологии связей в массово параллельных системах

Структуры массово параллельных систем с распределенной памятью можно классифицировать по типу и пропускной способности коммутирующей сети:

структуры с топологий решетка (двухмерная, трехмерная);

структуры с топологий гиперкуб;

структуры с топологий «каждый с каждым»

структуры с топологией «распределенный коммутатор».

Структуры с топологий решетка

В этой структуре пары из процессора и модуля памяти (процессорный элемент) соединены непосредственными связями со своими соседями (4-мя - в случае двухмерной решетки, 6-ю - в случае трехмерной решетки). Каждый процессорный элемент имеет одно и то же число подключений к сети вне зависимости от числа процессорных элементов в системе. Общая пропускная способность такой сети растет линейно относительно числа процессорных элементов. Пример двухмерной решетки приведен на рис. 10. Примеры других топологий приведены на рисунках 11--15.

Рис.10. Сеть с топологией 2D решетка(тор)

Рис. 11. Сеть с топологией 2D тор

Рис. 12. Сеть с топологией «клика»

Рис. 13. Сеть с топологией «каждый с каждым» - полный граф.

Рис. 14. Сеть с топологией кольцо

Рис. 15. Топология типа 3-х мерный куб

Контрольные вопросы

1. Структурные особенности системы Cray XT5

2. Структура связей в системе Cray XT5

3. К какому классу систем можно отнести Cray XT5

4. Структурные особенности системы Cray XT5h

5. Структурные особенности системы Cray XЕ6

6. Струтурные особенности системы BlueGene/L

7. Струтурные особенности системы RoadRunner

8. Какие топологии связей испльзуются в массово параллельных системах?

Оценка производительности параллельных вычислительных систем

Содержание

Необходимость оценки производительности параллельных вычислительных систем

Способы оценки пиковой производительно­сти

Реальная производительность параллельных вычислительных систем

Связь реальной и пиковой производительности

Закон Амдала

Влияние на реальную производительность параллельных вычислительных систем соответствия их структуры и структуры программ

Влияние структуры параллельных вычислительных систем на реальную производительность

Анализ реальной производительности («узких» мест) МВС с общей оперативной памятью

Анализ реальной производительности («узких» мест) кластерных систем с распределённой оперативной памятью

Необходимость оценки производительности параллельных вычислительных систем

Оценивать и сравнивать всегда было делом трудным и неблагодарным. Можно потратить массу сил и времени на выработку критериев и проведение ана­лиза, но обязательно найдется специалист, с точки зрения которого результаты должны быть точно противоположными. Сколько людей — столько мнений. Желание получить объективную оценку немедленно наталкивается на мно­жество субъективных факторов: разные постановки задачи, разные критерии сравнения, разные цели оценивания и т. п. Более того, любая оценка не­вольно приводит к сравнению, к явному или неявному ранжированию, вы­делению лучших и самых лучших. В этом вопросе редко удается прийти к единодушному согласию, поскольку убеждают только железные, неоспори­мые факты.

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

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

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

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

Пиковая производительность вычислительной системы вычисляется однозначно, спорить не о чем, и уже этим данная характеристика хороша. Более того, подсознательно всегда возникает связь между пиковой производительностью вычислительной системы и ее возможностями в решении задач. Чем больше пиковая производительность, тем, вроде бы, быстрее пользователь сможет решить свою задачу. В целом данный тезис не лишен некоторого смысла, но лишь некоторого и "очень некоторого". Полагаться на него полностью нельзя ни в коем случае. С момента появления первых параллельных вычислительных систем пользователи убедились, что разброс в значениях реальной производительности может быть огромным. На одних задачах удавалось получать 90% от пиковой производительности, а на других лишь 2%. Если кто-то мог использовать независимость и конвейерность всех функциональных устройств вычислительной системы, производительность получалась высокой. Если в вычислениях были информационные зависимости, то конвейерность не использовалась, и производительность снижалась. Если в алгоритме явно преобладал один тип опера­ций, то часть устройств простаивала, вызывая дальнейшее падение производи­тельности.

Структура программы и структура вычислительной системы тесно связаны. Пользова­теля не интересуют потенциальные возможности вычислительной системы. Ему нужно решить его конкретную задачу. Именно с этой точки зрения он и хочет оценить "качество" вычислительной системы. Для обработки данных эксперимен­та в физике высоких энергий не требуется высокоскоростной коммуникаци­онной среды. Главное — это большое число вычислительных узлов. Для та­ких целей вполне подойдет локальная 100-мегабитная сеть организации из ста рабочих станций. Ее можно рассматривать в качестве параллельной вычислительной системы, и ночью целиком отдавать под такие задачи. Теперь попробуй­те на такой вычислительной системе запустить серьезную модель расчета изменения климата. Скорее всего, никакого ускорения решения задачи не будет. Имеем вычислительную систему с хорошим показателем пиковой производительности. Но для одних задач он подходит идеально, а для других никуда не годится.

Способы оценки пиковой производительно­сти

Традиционно используются два способа оценки пиковой производительно­сти вычислительной системы. Один из них опирается на число команд, выполняемых вычислительной системы в единицу времени. Единицей измерения, как правило, является MIPS (Million Instructions Per Second). Для определенного класса приложе­ний такой подход является вполне приемлемым, поскольку общее представ­ление о скорости работы вычислительной системы получить можно. Но, опять-таки, только самое общее. Производительность, выраженная в MIPS, говорит о скорости выполнения вычислительной системой своих же инструкций. Но в какое число инструкций отобразится программа пользователя или отдельный ее опера­тор? Заранее не ясно. К тому же каждая программа обладает своей специ­фикой, число команд той или иной группы от программы к программе мо­жет меняться очень сильно. В этом контексте данная характеристика действительно дает лишь самое общее представление о производительности вычислительной системы.

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

При обсуждении производительности вычислительной системы не менее важен и вопрос о формате используемых данных. Если процессор за один такт может выполнять операции над 32-разрядными вещественными числами, то его же производительность при работе с 64-разрядной арифметикой может упасть во много раз. Известно, что первая матричная вычислительная система ILLIAC IV могла выполнять до 10 миллиардов операций в секунду. И это в 1974 году! Если брать за основу только цифры, то впечатляет. А если посмотреть вглубь, то это верно лишь для простых команд, оперирующих с байтами. 64-разрядные числа процессорные элементы ILLIAC IV могли интерпретировать и обрабатывать только как данные уменьшенного формата. Например, одно слово они могли рассматривать как два 32-разрядных числа или восемь однобайтовых. Именно этот дополнительный внутренний параллелизм и позволял получить столь внушительные характеристики.

Для задач вычислительного характера, в которых важна высокая скорость выполнения операций над вещественными числами, подход к определению производительности также не должен опираться на скорость выполнения машинных инструкций. Во многих случаях операции над вещественными числами выполняются медленнее, чем, скажем, управляющие или регистровые операции. За время выполнения одной операции умножения двух чисел в формате с плавающей запятой может выполниться десяток простых инструкций. Это послужило причиной введения другого способа измерения пиковой производительности: число вещественных операций, выполняемых вычислительной системой в единицу времени. Единицу измерения назвали FLOPS, что является сокращением от Floating point operations per second. Такой способ, безусловно, ближе и понятнее пользователю. Операция а + b в тексте программы соответствует одной операции сложения в коде программы. Пользователь знает вычислительную сложность своей программы, а на основе этой характеристики может получить нижнюю оценку времени ее выполнения.

Да, к сожалению, оценка будет только нижней. В этом и кроется причина недовольства и разочарований. Взяв за ориентир пиковую производительность вычислительной системы, пользователь рассчитывает и на своей программе полу­чить столько же. Совершенно не учитывается тот факт, что пиковая производительность получается при работе вычислительной системы в идеальных условиях. Нет конфликтов при обращении к оперативной памяти, все данные берутся из регистров, все функциональные устройства постоянно и равномерно загружены и т. п. Но в жизни так бывает редко. В каждой программе пользователя есть свои особенности, которые эти идеальные условия нарушают, обнажая «узкие» места структуры вычислительной системы. Особенности структуры процессора, системы команд, состав функциональных устройств, строение и объем кэш-памяти, структура подсистемы доступа в оперативную память, реализация ввода-вывода — все это, и не только это, может влиять на выполнение реальной программы. Причем заметим, перечислены только части аппаратуры, а говорить надо о программно-аппаратной среде выполнения программ в целом. Если для вычислительной системы нет эффективных компиляторов, то пиковая производительность будет вводить в заблуж­дение еще сильнее.

Значит нужно отойти от характеристик аппаратуры и оценить эффектив­ность работы программно-аппаратной среды на фиксированном наборе за­дач. Бессмысленно для каждой вычислительной системы показывать свой набор. Разра­ботчики без труда придумают такие программы, на которых их вычислительная система достигает производительности, близкой к пиковой. Такие примеры никого не убедят. Набор тестовых программ должен быть зафиксирован. Эти про­граммы будут играть роль эталона, по которому будут судить о возможно­стях вычислительной системы.

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

Тест LINPACK

Что имело бы смысл взять в качестве подобного теста? Что-то несложное и известное всем. Таким тестом стал LINPACK. Эта программа предназначена для решения системы линейных алгебраических уравнений с плотной мат­рицей с выбором главного элемента по строке. Простой алгоритм, регуляр­ные структуры данных, значительная вычислительная емкость, возможность получения показателей производительности, близких к пиковым, — все эти черты сделали тест исключительно популярным.

Во втором варианте теста размер матрицы увеличивается до 1000x1000.

С появлением больших массово параллельных вычислительных систем вопрос подбора размера матрицы стал исключительно актуальным. На матрицах 100x100 1000x1000 никаких разумных показателей получить не удавалось. Эти задачи были слишком малы. Матрица размера 1000x1000 занимает лишь 0,01—0,001% всей доступной оперативной памяти вычислительной системы. Первые эксперименты с тестом LINPACK на реальных массово параллельных вычислительных системах показали, что и фиксировать какой-либо один размер задачи тоже нельзя.

В последнем варианте теста разрешено использовать матрицы сколь угодно большого размера. Сколько есть оперативной памяти на всех вычислительных узлax системы, столько и можно использовать. Для современных вычислительных систем размер матрицы уже перевалил за миллионы.

Раз­решается как внесение изменений в текст подпрограммы, реализующей заложенный авторами метод решения системы, так и изменение самого мето­да. Единственное ограничение — это использование стандартной вызы­вающей части теста, которая выполняет инициализацию матрицы, вызывает подпрограмму решения системы и проверяет корректность результатов.

В этой же части вычисляется и показанная вычислительной системой производительность, исходя из формулы для числа операций 2n³/3 + 2n² (n — это размер матрицы), вне зависимости от вычислительной сложности реально использованного алгоритма.

В данном варианте теста достигались значения производительности, близкие к пиковой. Этому способствовали и значительный размер матрицы, и возможность внесения изменений в программу или алгоритм. Отсюда появи­сь и специальное название данного варианта — LINPACK TPP, Toward Performance.

Для работы теста LINPACK на вычислительных системах с распределенной оперативной памятью была создана специальная версия HPL (High-Performance LINPACK). В отличие от стандартной реализации, в HPL пользователь могут управлять большим числом параметров для достижения высокой произ­водительности на своей установке.

В настоящее время тест LINPACK используется для формирования списка TOP500 — пятисот самых мощных вычислительных систем мира (www.top500.org). Кроме ­пиковой производительности Rpeak для каждой вычислительной системы указывается величина Rmax, равная производительности вычислительной системы на тесте LINPACK с матрицей максимального для данной вычислительной системы размера Nmax. По значе­нию Rmax отсортирован весь список. Как показывает анализ представленных данных, величина Rmax составляет 50—70% от значения Rpeak. Интерес для анализа функционирования вычислительной системы представляет и указанное значение N1/2, показывающее, на матрице какого размера достигается половина производительности Rmax.

Что же показывают данные теста LINPACK? Только одно — насколько хорошо вычислительная система может решать системы уравнений с плотной матрицей указанным методом. Поскольку задача имеет хорошие свойства, то и корреляция производительности на тесте LINPACK с пиковой производительностью вычислительной системы высока. Операции ввода-вывода не затрагиваются, отношение числа выполненных операций к объему используемых данных высокое, ре­гулярность структур данных и вычислений, простая коммуникационная схема, относительно небольшой объем передач между процессорами, и дру­гие свойства программы делают данный тест "удобным". Безусловно, по данным этого теста можно получить много полезной информации о вычис­лительной системе и с этим никто не спорит. Но нужно ясно понимать и то, что высокая производительность на тесте LINPACK совершенно не означает того, что и на конкретной программе потребителя будет достигнута высокая про­изводительность.

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

Ключевыми в тесте являются следующие следующие операции:

a(i) = q * b(i)

a(i) = b(i) + q * c(i)

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

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

Предполагается, что в хорошо сбалансированной структуре скорость выполнения арифметических операций должна быть согласована со скоростью доступа в оперативную память. В современных высокопроизводительных вычислительных системах это выполняется, но, как правило, только при работе с верхними уровнями иерархии памяти. Если данные попали в кэш-память первого уровня, то все будет хорошо. А что делать в других случаях? Именно по этой причине тесты STRЕАМ работают с очень большими векторами, хранящимися в оперативной памяти. Попробуйте на доступной вам вычислительной системе провести сле­дующий эксперимент. С помощью, например, четвертого теста определите реальную скорость передачи данных между процессором и оперативной памятью. Разделите пиковую производительность вычислительной системы на только что полученное значение. Чем больше полученное вами число, тем менее сбалансированы в структуре скорости обработки и передачи данных (меньше единицы данное значение бывает далеко не всегда).

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

Это в полной мере касается таких простых тестов, как LINPACK или STRЕАМ. Однако, если задуматься, то возникает замкнутый круг. С одной стороны, тесты должны быть легко переносимыми с платформы на платформу, а потому должны быть простыми. Чтобы поместиться в оперативной памяти каждой вычислительной системы, структуры данных должны быть небольшими. Более того, чтобы получить широкое признание, тест должен иметь понятную формулировку решаемой задачи. Перемножение матриц, метод Гаусса решения системы линейных уравнений, быстрое преобразование Фурье, метод Монте-Карло — это все доступно, компактно, используется многими, легко переносится. С другой стороны, к подобным программам всегда было отношение, как к чему-то несерьезному, как к "игрушкам". Фиксированный размер задачи, характерное вычислительное ядро, отсутствие интенсивного ввода-вывода, упрощенный код и другие свойства тестов дают веские основания для подобного отношения. Доля истины в таких рассуждениях, безусловно, есть. Жизнь всегда намного богаче и разнообразнее, чем теория.

Точно так же и реальные программы по отношению к тестам. Что же в ре­зультате мы имеем? Средства для оценки производительности вычислительных систем необходимы. Чтобы использоваться широко, они должны быть простыми. Простые тесты не дают полной картины и в каждом случае нужно исполь­зовать дополнительные средства. Простота необходима, но простота не при­водит к искомому результату.