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

Раздел 3 АРХИТЕКТУРА САПР

УДК 681.324

Л.В. Каляев, В.Ф. Гузик, В.А. Каляев, А.И. Костюк ВОПРОСЫ ОЦЕНКИ ПРОИЗВОДИТЕЛЬНОСТИ ПРОЕКТИРУЕМЫХ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Если принять, что производительность - это реакция системы на конкретный поток заданий, то от того насколько точно отражает используемая модель тестирования реальный поток заданий, зависит корректность получаемой оценки производительности. Основными видами моделей потока заданий [1] на сегодняшний день являются:

• смеси команд;

• эталонные потоки заданий (benchmark);

• стохастические модели;

• трассы.

Рассмотрим основные особенности этих моделей.

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

Benchmark. В качестве benchmark’s используются эталонные программы или эталонные наборы программ. При этом а качестве эталонных программ могут использоваться как реальные практические программы или их фрагменты, так и “искусственные” программы, специально созданные для оценки производительности. При выборе эталонных программ стремятся чтобы их набор максимально характеризовал как производительность отдельных блоков тестируемой системы, так и их взаимодействие между собой. У этого подхода также имеется ряд существенных недостатков. Во-первых, выбор эталонных программ, как правило, производится людьми, заинтересованными в конечных результатах тестирования. Во-вторых, вряд ли практически возможно локализовать эталонный набор программ, характеризующий все основные нюансы работы вычислительной системы. В-третьих, прогон такого эталонного пакета программ даже на существующих вычислительных системах требует зачастую громадных временных ресурсов. Так популярный в мире benchmark SPEC95 [2] требует при реализации на своей эталонной вычислительной системе SPARCstation 10/40 порядка 48-ми часов. Этот подход часто применяют для сравнения производительности существующих систем. Его применение для оценки производительности разрабатываемой вычислительной системы основано на применении эмуляторов и характеризуется довольно низкой эффективностью и значительными накладными расходами.

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

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

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

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

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

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

• “за какое время система выполняет фиксированное задание”

• “сколько фиксированных заданий выполнит система за фиксированное время”.

Некоторые тесты, например Hanoi, базировались на первом из этих критериев, в других

(например, SPEC) использовались оба критерия. По существу различие между этими критериями не является принципиальным. В обоих из них ключевыми понятиями являются “время” и “задание”. Однако, если “время” понятие строго определенное, то термин “задание” строго определить попросту невозможно.

Итак, можно сформулировать следующие требования к эталонному тесту, предназначенному для оценки производительности вычислительных систем:

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

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

3. Результаты тестирования должны быть легко читаемыми

В последние годы появились эталонные тесты (SLALOM, HINT), в которых сделана попытка избавиться по крайней мере от некоторых из перечисленных выше недостатков. Критерием производительности в этих тестах является “качество решения полученное за фиксированное время”. При этом под “качеством решения” понимается точность решения,

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

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

Этот эталонный тест основан на численном моделировании монотонно убывающей функции

у = п----------

где 0<=х<=п. Нетрудно видеть, что у также лежит в пределах от 0 (при х=п) до п (при х=0). Таким образом, вся функция лежит на плоскости внутри квадратной области размером пхп. Что касается п, то можно считать, что это максимально возможное целое число, которое позволяет представить принятый в тестируемой системе формат представления чисел. В любом случае п будет равно 2*, где к- величина, связанная с форматом представления чисел. Например, при использовании формата с фиксированной точкой к - это число разрядов регистра.

Численное моделирование указанной функции сводится к ее кусочно-ступенчатой аппроксимации. При этом аппроксимация ведется сразу с двух сторон (строятся две ломаных): сверху и снизу. Аппроксимация производится в соответствии со следующей схемой. Отрезок (0,п) оси х разбивается на интервалы, границами которых являются целые значения х. Очевидно, что максимально при этом на рассматриваемом отрезке разместятся п интервалов, соответственно (0,1), (1,2), (2,3) и. т. д. Однако интервалов может быть и меньше, так как разбиение на интервалы производится (во всяком случае, для однопроцессорных вычислительных систем) последовательно. Вначале за единственный интервал берется весь отрезок (0,п), затем он разбивается на два интервала (0,п/2) и (п/2,п). На следующем этапе разбивается пополам интервал (0,п/2) и так далее. После каждого нового разбиения на интервалы строятся две аппроксимирующие ломаные:

yi(x) = y*(i-l); (i-1) <= х < i; i = 0,1,2.n

и

Уг(х) = y**(i); (i-l)<=x<i; i = 0,1,2,...,n.

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

Расчет площади этой области является тривиальной задачей, поскольку, в соответствии с алгоритмом, х и у могут принимать только целые значения. Возьмем область, в которой располагается наша функция (напомним, что это квадратная область размером пхп) и разобьем ее на подобласти (квадратики) размером 1x1. Очевидно, что таких подобластей будет п2. Нетрудно заметить, что на любом интервале между ломаными yi и у2 будет располагаться Целое число подобластей. Таким образом, чтобы оценить погрешность аппроксимации после очередного разбиения на интервалы, достаточно для каждого интервала подсчитать число

подобластей, расположенных между ломаными, и просуммировать полученные результаты Если теперь взять общее число подобластей (п2) и разделить на полученную сумму, сформированный результат можно рассматривать как “текущее качество решения”

После окончания процесса тестирования формируется окончательная оценка производительности в соответствии с выражением:

l0

Здесь to и t, соответственно, время начала и окончания процесса тестирования q - качество решения, полученное на последнем шаге. ’

Итак, эталонный тест HINT с одной стороны является достаточно несложным и может

быть реализован в виде компактного программного кода, а с другой стороны позволяет с

достаточной степенью достоверности протестировать такие ресурсы как подсистема памяти и

процессоры. Еще одним достоинством данного эталонного теста является его независимость

от архитектуры тестируемых систем. Он одинаково успешно может использоваться для

тестирования, как последовательных, так и параллельных систем. Конечно HINT т

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

согласовываться с полученными оценками производительности Нг>

_ ". ,1и данный метод может

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

Однако “прямое” использование эталонно го тестя hiwt _

_ „ nirvi для тестирования

многопроцессорных систем с программируемой архитектурой [3] не может дать полного

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

. ". JIU связано с тем, что при

запуске на такой системе единичном задачи ( а именно такой задачей и является HINT) ей

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

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

Более интересным, с этой точки зрения, является запуск HeCKnnbJMv ™ ^ УР параметрами. Например, запускается тест с гт=8, тест с п=9 и тл г °В ° разнь,мИ

сама распределить ресурсы между задачами. Кроме того посколы™ ДОЛЖНа при этоМ

для более простых задач наивысшее возможное качестао 6vl . Р ^ ^ РаЗНЫе’ общего процесса. Система должна будет при этом перераспределить”^!^0 °К°НЧаНИ* ресурсы между другими задачами. Общей оценкой производительности сигамТГж^ являться среднее геометрическое качества решений, полученных для о

Проблемы тестирования естественно усугубляются если р—ГоЧб опенке производительности реально существующих систем а Об г>п оценке

разрабатываемой параллельной вычислительной системы Требова П*50ИЗВ°дительностИ разрабатываемой параллельной системы, можно сформулировать следуют™ ***

1. Тесты должны, по возможности, отражать как- ооразом.

системы ВО всей взаимосвязи ее ресурсов (идеалкнг» СН^Ю ПР0ИЗВ0ДИТеЛЬН0СТЬ

невозможно), так и производительность отдельных рр ЭТ0 сделать по-видимому процессоров). дельных ее компонент ( во всяком случае

2. Тесты должны быть достаточно компаетными с тйы л

группы разработчиков их можно было в реальнм* L чтобЬ| Усилиями небольшой

реальна сроки адаптировать и пропустить

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

3. Наконец, для выбранных тестов желательно иметь результаты их прогона на реально

существующих системах.

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

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

Все упомянутые выше условия предопределяют выбор четырех основных уровней описания системы при ее исследовании:

• уровень системной архитектуры отображает взаимосвязь базовых компонентов

вычислительной системы, а также операционную систему и программы пользователя;

• уровень архитектуры коммутации процессоров определяет структуру связей между

процессорными элементами (ПЭ), входящими в систему, и их взаимодействие;

• уровень архитектуры процессора фиксирует соединение и набор функциональных

модулей ПЭ, описание реализации отдельных команд процессора;

• уровень архитектуры модулей отображает структурную организацию функциональных

модулей и блоков, входящих в состав процессорного элемента.

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

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

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

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

На основе параметрического описания генерируется программа моделирования. В качестве языка моделирования используется язык описания аппаратуры (ЯОА) с расширением возможностей отображения программной компоненты.

Язык описания аппаратуры представляет собой специализированный язык высокого уровня поддерживающий три основных способа определения моделируемой системы: структурный, потока данных и потока команд. Базовой абстракцией ЯОА является архитектурный модуль, имеющий две взаимосвязанные части - описание интерфейса между модулем и внешней средой и описание преобразования входной и выходной информации внутри модуля. Наличие возможности определения потока команд позволят отразить в программе моделирования последовательность команд, соответствующую выбранному уровню проектирования. Таким образом, средствами ЯОА подключаются формируемые в подсистеме программного обеспечения библиотеки, содержащие программы решения прикладных задач: на языке параллельного программирования (ЯПП) для уровня системной архитектуры; на макроассемблере для уровней коммутации ПЭ и отдельного процессорного элемента, а также микропрограммы для реализации функций в модулях ПЭ. Для аппаратных блоков также может быть использована специальная библиотека архитектурных компонентов на ЯОА в состав которой входят как процедуры имитации отдельных модулей различных уровней, так и завершенные программы моделирования систем, разработка которых была осуществлена ранее. Такая организация библиотеки позволит провести испытания выбранного варианта архитектуры на различных задачах, формулируемых при помощи программной подсистемы, в том числе и таких как HINT. По завершении генерации, программа моделирования записывается в библиотеку, после чего проходит трансляция с ЯОА в ассемблер инструментальной ПЭВМ, на которой производятся исследования.

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

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

ЛИТЕРАТУРА

1. Смелянский Р.Л. Методы и средства анализа производительности вычислительных систем с традиционной архитектурой. - М.: Изд-во МГУ, 1989. - 24 с.

2. Kaiwalia Dixit. SPECulations. Defining the SPEC Benchmark // Sun Tech Journal. - 1991. Volume 4, № 1. - P. 53-63.

3. Каляев A.B., Гузик В.Ф. и др. Параллельная обработка информации, том 4: Высокопроизводительные системы параллельной обработки информации. - Киев: Наукова думка, 1988. - 272 с.