Реальная ценность вычислительных систем (ВС), ориентированных на решение "критических" задач предметной области, определяется качеством оценки требуемой пропускной способности по
Заказчика или покупателя таких ВС в первую очередь интересуют аппаратно-временные затраты на реализацию его алгоритмов, а системные издержки организации вычислений им воспринимаются как накладные расходы. Поэтому алгоритмические затраты должны быть удовлетворены в полном объеме, так как именно они определяют потребительскую ценность создаваемой ВС, а системные аппаратно-временные издержки необходимо минимизировать в ходе разработки, чтобы добиться приемлемого соотношения цены и качества.
В отличие от ЭВМ общего назначения, к которым можно отнести и персональные компьютеры, предметная область создаваемых (Б)ВС всегда характеризуется рекордными параметрами, но при этом она достаточно четко очерчена и потенциальному пользователю хорошо известны представленные выше характеристики. Это обеспечивает высокую степень достоверности оценки требуемой пропускной способности по потокам команд и данных, диктуемых алгоритмом и продолжительностью цикла решения задачи, зная которые, уже можно выбрать необходимую архитектуру и требуемый коэффициент
При таком подходе к проектированию или выбору (Б)ВС:
Такая методика оценки качества (Б)ВС исходит из безусловной поддержки темпа реального времени, диктуемого предметной областью, и для его реализации прежде всего необходимо получить аналитическую оценку "длины" программы $$L_p$$ вычислительного алгоритма "критической" задачи, которую в традиционных вычислительных технологиях измеряют максимальным количеством ассемблерных инструкций, реально расходуемых на ее решение. В нетрадиционных вычислительных технологиях "длину" программы приходится измерять в тех (микро)программных единицах, для которых известен или задан цикл исполнения.
Основная трудность оценки "длины" программы $$L_p$$ связана с нали-чием в вычислительном алгоритме операторов условных переходов типа $$if$$ которые ставят ее в прямую зависимость от содержимого обрабатываемых потоков данных, которые в данном случае необходимо рассматривать как случайные. Для (Б)ВС вносимая операторами $$if$$ "случайность" и вытекающая из нее неопределенность в длине программы ослабляется тем обстоятельством, что в высокоответственные применения оператор условных переходов должен мажорироваться оператором $$for$$, который, с одной стороны, призван лимитировать максимально допустимую по темпу реального времени продолжительность исполнения каждого цикла программы, а с другой стороны, должен повысить ее устойчивость к информационным сбоям, разрывая "бесконечные" циклы, чреватые потерей управления опасными технотронными комп лексами двойного назначения.
Зная "длину" программы $$L_p$$, можно выбрать тип архитектуры, "иде-альной" в том смысле, что при этом были учтены только алгоритмические затраты, а системные издержки считались нулевыми. Для этого достаточно воспользоваться соотношениями (1.5)-(1.7) раздела 1.5 курса "Задачи и модели вычислительных наноструктур" и проверить неравенства: $$L < \max L(ОКОД) = \Delta T_0 /\tau_c$$, $$L < \max L(ОКМД) = T_{k} / \tau_c$$ или $$L < \max L(МКМД) = T _{0}/\tau_c $$, где $$\Delta T_{k}$$ - дискрет времени, диктуемый теоремой Котельникова, $$T_{k} = \Delta T_{k} * N$$ - цикл формирования циклически обрабатываемой выборки данных из $$N$$ операндов, а $$T _{0}$$ - допустимое время задержки в (Б)ВС. Если ни одно из этих неравенств не выполняется, то необходимо переходить на уровень распараллеливания отдельных ассемблерных инструкций, то есть к архитектурам с микрокомандным уровнем доступа, гарантирующим максимально возможное функциональное насыщенное каждого такта работы (Б)ВС. Как показывает практика, выйти за рамки "идеальной" архитектуры разработчику в дальнейшем не удается, и ему остается только разрабатывать комплекс мер, направленных на минимизацию системных аппаратно-временных издержек.
Данная методика апробирована при создании спецпроцессоров обработки сигналов и изображений, как на основе заказных СБИС, так и на основе систолических и бит-матричных СБИС [70, 138-144]. Указанные аппаратные платформы поддерживают предметную область, для которой характерны [70]:
Признав, что циклы $$for$$ являются неотъемлемой составляющей таких (Б)ВС, решаемые ими задачи можно разбить на классы с характерной зависимостью количества арифметико-логических операций от количества операндов $$N$$ в циклически обрабатываемых потоках данных (табл. 1.1 [70]).
Численные значения табл. 1.1 соответствуют параметрам "критических" задач, актуальных на конец 80-х годов прошлого столетия. Тем не менее уже тогда требовались (Б)ВС с производительностью порядка $$10^{12}-10^{15}$$ ассемблерных операций в секунду. Если принять во внимание, что цикл исполнения ЦПОС - и RISC -инструкций был уже постоянен и в тот период времени не превышал 1 ГГЦ, становится ясно, что суммарный коэффициент
| Тип алгоритма | Необходимая производительность |
|---|---|
| Линейные, типа $$O(N)$$: | $$10^{2} -10^{5}$$ |
| Пространственная фильтрация | |
| Свертка | |
| Обнаружение контуров | |
| Второго порядка, типа $$O(N^2)$$: | $$10^{3} 10^{7}$$ |
| Сортировки | |
| Медианная фильтрация | |
| Классификация ближайшего соседа | |
| Третьего порядка, типа $$O(N^3)$$: | $$10^{4}-10^{8}$$ |
| Векторно-матричная алгебра | |
| Спектральные вычисления | |
| Адаптивная фильтрация |
Однако (Б)ВС решают не одну и не одни только "критические" задачи. Поэтому их операционный ресурс постоянно перераспределяется по ходу вычислений между решаемыми задачами, что требует учета системных издержек на организацию вычислений. Данное обстоятельство только подтверждает тот факт, что в любой нетрадиционной архитектуре (Б) ВС всегда найдется уровень управления фон-неймановского типа. В простейшем случае такое управление выполняется по жесткой циклограмме и связанные с ним издержки в основном сводятся к плановой обработке "прерываний", которые неминуемо вызывают "паразитные" перемещения программ и данных по иерархии запоминающих устройств (Б)ВС: регистры - КЭШ - ОЗУ - внешние ЗУ и обратно.
Но циклограмма жестко регламентирует только порядок (пере)запу-ска задач, время решения которых может флуктуировать в достаточно больших пределах (1,5-3 раза и более) из-за наличия циклов по условию. Объясняется это тем, что с помощью мажорирующих циклов $$for$$ удается ограничить только максимально допустимое время выполнения этого цикла, а реальные временные затраты могут оказаться значительно меньше, если сработает оператор $$if$$. В результате трудно рассчитать как время обработки одного планового "прерывания", которое зависит от фазы выполнения прерванной задачи, так и количество таких "прерываний". Основным источником такой неопределенности являются паразитные перезагрузки памяти на участках кеш - ОЗУ - внешние ЗУ, что вынуждает брать в кавычки термин "прерывание".
Отсюда, даже в этом простейшем режиме управления системные временные издержки носят случайный характер с очень высокой дисперсией моментов запуска каждой последующей фазы вычислительного процесса.
Чтобы компенсировать возникающие в реальных условиях временные простои, разработчики (Б)ВС стараются запускать в образующихся "паузах"
В случае ЭВМ общего назначения описанная ситуация резко усугубляется априорной неопределенностью сферы использования, что приводит к усложнению систем управления аппаратными ресурсами во время вычислений, которые сами становятся главными "пожирателями" этих же ресурсов, так как рассчитаны "на все случаи жизни". В результате системные временные затраты такого управления могут на 1-2 порядка превосходить аналогичные затраты на обслуживание алгоритма пользователя.
Такое соотношение между алгоритмическими затратами и системными накладными расходами вынуждало и вынуждает производителей и пользователей ЭВМ и особенно многопроцессорных ВС разрабатывать и использовать различные методы, методики и способы оценки качества создаваемых или покупаемых вычислительных средств, главным показателем которого, как правило, является пропускная способность по
В оценке пропускной способности прежде всего нуждается покупатель ЭВМ, в ее расчете - проектировщик, а к ее измерению обычно прибегают непосредственно в эксплуатации, когда требуется расширить сферу информационных услуг, что ставит пользователя перед дилеммой: реконструировать имеющуюся аппаратную платформу или закупить новую.
При оценке качества вычислительной техники все используемые показатели рекомендуется разбивать на 2 группы [106]: требования и атрибуты, первые из которых представляют собой спецификацию того, что должна делать система, а вторые включают характеристики для предпочтительного выбора при прочих равных условиях. Требования задают необходимые условия, которым должна удовлетворять система, и они выражаются совокупностью как измеряемых, так и качественных показателей: пропускная способность, массо-габариты, потребляемая мощность, стоимость, отказоустойчивость, интеллектуальный уровень программной поддержки и т. п. К атрибутам, как правило, относят субъективные показатели, которые делают проект инвестиционно привлекательным, а созданное изделие - конкурентоспособным. К архитектурным атрибутам обычно относят: гибкость (масштабируемость), расширяемость и комплексируемость, которые в совокупности характеризуют открытость системы.
При оценке пропускной способности по
Пропускную способность (Б)ВС можно также оценить на основе аналитических, событийных или эмпирических моделей, а также прямым измерением характеристик составляющих блоков и устройств. Главные ограничения аналитических моделей связаны с трудностями описания взаимодействий аппаратуры и программного обеспечения, последнее из которых обычно приходится рассматривать как "черный ящик". Главные проблемы событийных и эмпирических моделей, а также прямого измерения состоят в сложности и стоимости их разработки.
В табл. 1.2 приведены эмпирические данные качества применения каждого метода оценки производительности по состоянию на 1985 год [106]. Здесь 1 означает, что метод использовался, но оказался неадекватным, 2 - метод оказался недостаточно полезным, 3 - метод дал хорошие результаты и прочерк - метод не применялся. За прошедшие годы база апробации методов оценки расширилась, сами методики углубились и удешевились за счет создания специализированных инструментальных платформ их реализации.
| Метод оценки | Оценка при выборе системы | Расчет при разработке | Измерение для реконфигурации | |||
|---|---|---|---|---|---|---|
| Новая аппаратура | Новые программы | Создаваемая аппаратура | Создаваемые программы | Реконфигурация аппаратуры | Реконфигурация программ | |
| Длительность цикла | 1 | - | 1 | - | - | - |
| Смесь команд | 1 | - | 1 | - | - | - |
| Представительные программы | 2 | 1 | 2 | 1 | - | 1 |
| Аналитические модели | 2 | 1 | 2 | 1 | 2 | - |
| Испытательные программы | 3 | 3 | 2 | 2 | 2 | |
| Синтетические программы | 3 | 3 | 2 | 2 | 2 | 2 |
| Моделирование | 3 | 3 | 3 | 3 | 3 | 3 |
| Прямое измерение | 2 | 2 | 2 | 2 | 3 | 3 |
Тем не менее, данные табл. 1.2 позволяют сделать следующие выводы, которые справедливы и для современных условий:
Сравнение компьютеров между собой обычно начинают с оценки их производительности. Это потребовало введения соответствующих единиц измерения производительности и разработки стандартных методов ее оценки.
Методы оценки производительности вычислительных систем должны отвечать определенным требованиям. Прежде всего, они должны быть общепризнанными, максимально полно оценивать вычислительные системы и соответствовать задачам пользователя. Должна быть обеспечена их доступность для независимой и самостоятельной экспертизы.
В основе используемых в настоящее время методов оценки и сравнения производительности вычислительных систем лежит время.
Компьютер, который выполняет определенный объем работы за меньшее время, считается более быстродействующим.
Оценка временных характеристик выполняемых процессором работ - далеко не тривиальная задача.
Для пользователя важно время, за которое решается его задача. Но практически нет программ, которые могут работать без некоторой операционной системы. В связи с эти возникают дополнительные накладные временные затраты. Поэтому при измерении производительности чаще всего используется сумма пользовательского и системного времени центрального процессора.
Дополнительные сложности при сравнении временных характеристик решаемых на разных компьютерах задач обусловлены тем, что системный код при решении задачи на одном компьютере на другом компьютере может стать пользовательским.
В ходе измерений появляется значительные методические ошибки, вызванные нарушением базовой концепция построения измерительных систем, в результате чего "измерительный прибор" становится неотъемлемой частью измеряемой системы.
Возникают серьезные методические трудности сравнения производительности компьютеров с разными операционными системами.
В связи с этим в методиках оценки производительности используют разное время:
Для измерения времени, затрачиваемого процессором на выполнение данной программе, используется специальное время, которое называют временем центрального процессора (
Время центрального процессора можно разделить пользовательское и системное.
Все современные ЭВМ работают в общем случае, как минимум, в двух-задачном режиме, обслуживая запросы операционной системы и запросы задачи пользователя.
В случаях, когда функции операционных систем могут быть сведены до одной простой задачи диспетчеризации заданий, системным временем центрального процессора можно пренебречь. Примером могут служить бортовые системы управления авиационных и космических комплексов,
Особенностью процессора как объекта измерения является то, что скорость взаимодействия функциональных устройств процессора чаще всего не зависит от динамических характеристик этих устройств, а задается частотой генератора тактовых импульсов. Поэтому время центрального процессора может быть вычислено двумя способами:
Важной характеристикой процессора является среднее количество тактов синхронизации, необходимых для выполнения одной команды (
Производительность центрального процессора определяется тремя параметрами:
Все эти параметры тесно связаны между собой:
В процессе поиска стандартной метрики для оценки производительности вычислительных систем было выбрано несколько единиц измерения.
Одной из наиболее распространенных среди них является MIPS (Million Instruction Per Second). Она показывает количество команд программы, выполняемых в секунду.
Производительность определяется как обратная ко времени выполнения величина, а более быстродействующий компьютер имеет более высокий MIPS-рейтинг.
На первый взгляд метрика очень проста, но ее использование не позволяет учесть особенности выполняемой программы и архитектуру процессора. Невозможно сравнивать компьютеры, имеющие разные системы команд. Даже на одном компьютере результат меняется при решении разных задач. Серьезные проблемы возникают в связи с использованием сопроцессоров для выполнения команд с плавающей запятой и оптимизирующих компиляторов. Все это не дает возможности выполнять объективное сравнение разных процессоров.
С понятием MIPS в свое время была связано еще две метрики, основанные на производительности эталонных компьютеров VAX 11/780 компании DEC и одной из моделей RS/6000 компании IBM. Производительность этих компьютеров определялась как 1 MIPS. Производительность тестируемых систем вычислялась относительно производительности этих компьютеров, которые являются эталонными. Приблизительное соотношение между этими величинами таково: 1 IBM MIPS равен 1.6 DEC MIPS.
Использование эталонного компьютера сопряжено с серьезными трудностями:
Использование измерения производительности компьютеров в MIPS не всегда объективно. Примером могут служить задачи, связанные с научно-техническими расчетами. В них широко применяется арифметика с плавающей точкой. Решение этих задач требует значительных вычислительных ресурсов. Вопрос оценки производительности используемых при их решении вычислительных систем всегда стоял очень остро. При этом достигнутые показатели производительности служили и служат показателем уровня разработок вычислительной техники.
Поэтому для подобных приложений производительность процессора оценивалась и оценивается в
Современные компьютеры имеют достаточно высокий уровень производительности, поэтому в настоящее время используются производные величины от
Этот показатель в основном характеризует использование компьютеров в научно-технических приложениях. Он предназначен для оценки быстродействия при выполнении вычислительной системой операций плавающей арифметики. В противном случае его использование не всегда корректно.
Этот показатель производительности, так же как и MIPS, зависит от конкретной выполняемой программы и архитектуры процессора.
Однако у
Другая проблема заключается в том, что время выполнения разных операций с плавающей запятой может существенно отличаться, в результате рейтинг
Для оценки показателей производительности в MIPS и
Тестовая смесь
Смесь состоит из ста команд. Из них 53 оператора присваивания, 32 команды управления, 15 вызовов функций. В качестве метрики используется количество
"Ливерморские циклы" представляют собой типичный набор фрагментов программ на языке FORTRAN. [301, 302] В этих программах реализованы разные вычислительные алгоритмы:
Их выбор был основан на богатом опыте создания суперкомпьютеров и проведения сложнейших научных и инженерных расчетов Ливерморской национальной лаборатории им. Э. Лоуренса (Lawrence Livermore National Laboratory,
При тестировании используется либо малый набор (14 циклов), либо большой набор (24 цикла).
Коэффициент распараллеливания применяемых алгоритмов лежит в диапазоне от 0 до 1. Это позволяет использовать "Ливерморские циклы" для оценки производительности вычислительных систем, имеющих различную архитектуру. Тест практически не используется.
Тесты
Применяемые в этих программах алгоритмы широко используются при решении многих практических задач. С эти связана популярность этого теста среди пользователей.
Аргонская национальная лаборатория (
Тест
В основе используемых в
Исходные данные для тестирования представляются в виде вещественных чисел двойной точности. Полученные результаты выражаются в
Тест
В тесте первого уровня
Первый уровень этого теста нельзя применять в вычислительных системах, позволяющих поместить всю исходную матрицу в кэш-памяти.
В этом случае полученные результаты могут существенно превышать реальные возможности системы.
Применение тестов
Для оценки производительности таких систем используется тест
Тестовый пакета
Анализ подходов к оценке производительности вычислительных систем позволяет сделать следующие выводы:
С точки зрения пользователя оценку производительности вычислительной системы лучше всего выполнять с использованием реальных программ, планируемых для использования на ней. Наиболее объективной оценкой производительности вычислительной системы при этом будут временные характеристики их исполнения.
Учитывая это, разработчики инструментальных средств измерения производительности вычислительных систем стремятся смоделировать работу типичных пользовательских приложений.
Рассмотрим основные особенности работы наиболее распространенных на практике стандартных инструментальных платформ измерения производительности компьютеров.
Важнейшей характеристикой вычислительных систем является производительность. Все разработчики компьютерной техники стремятся к установлению рекордов производительности, рассматривая их как инструмент в конкурентной борьбе. Этот инструмент работает только при условии легитимности полученных при тестировании результатов. Именно поэтому на паритетных началах ведущие производители создали несколько организаций, отвечающих за тестирование вычислительных систем.
Одной из таких организаций стала созданная в 1988 году корпорация SPEC (Standard
Цель корпорации состоит в разработке и сопровождении стандартизованных
Для членства в SPEC достаточно подать заявку и оплатить вступительный взнос.
Основное направление деятельности SPEC - подготовка тестов для оценки производительности основных подсистем компьютеров, которые могут использоваться, как разработчиками, так и потребителями вычислительной техники. Вся информация о предлагаемых наборах тестов публикуется.
Чтобы воспользоваться тестами SPEC, необходимо приобрести соответствующую лицензию. Так как целью организации не является получение прибыли, стоимость лицензий покрывает только административные расходы.
Можно выделить два базовых набора тестов SPEC CINT95, CFP95. С их помощью оценивается производительность компьютера и эффективность работы компиляторов. Тесты построены так, чтобы накладные расходы на работу ОС и выполнение операций ввода/вывода были пренебрежимо малы. Тесты ориентированы на ОС UNIX. При этом предусмотрена возможность их импорта на системные платформы Microsoft и других производителей.
Появления третьего по хронологии комплекта тестов была обусловлена рядом причин:
В качестве метрик производительности выполнения операций целочисленной и
Тест CINT95 предназначен для оценки производительности процессора при работе с целыми числами. В него входят восемь программ для решения задач из следующих областей приложения: искусственный интеллект, моделирование, программирование, компрессия, интерпретация языков, обработка, Shell-интерпретатор, базы данных.
В качестве языка программирования используется Си.
Тест CFP95 предназначен для оценки производительности процессора при работе с числами с плавающей точкой. В него входят десять программ для решения задач из следующих областей приложения: гидродинамика, предсказание погоды, квантовая физика, астрофизика, электромагнетизм, гидродинамика, моделирование, квантовая химия.
В качестве языка программирования используется ФОРТРАН.
Тесты
Для многопроцессорных и многозадачных систем необходимо оценивать их пропускную способность, которая равна количеству заданий, выполняемых системой в единицу времени. Тесты
Тест SPECrate был создан для оценки производительности многопроцессорных систем. Алгоритм тестирования достаточно прост. Одновременно запускается несколько одинаковых
Могут быть получены оценки SPECrate_int95, SPECrate_fp95, соответствующие целочисленным операциям и операциям с плавающей запятой. При тестировании измерения проводятся независимо по каждому тесту. Количество запускаемых копий теста зависит от архитектуры исследуемой системы. Измеряется время завершения последней копии тестовой программы.
Для исключения влияния на результаты тестирования работы компилятора используются оценки: SPECrate_base_int95 и SPECrate_base_fp95.
В результате тестирования может быть получена детальная оценка производительности исследуемой вычислительной системы.
Возможны следующие варианты выполнения
В 1988 году по инициативе Омни Шерлин (Omni Serlin) был создан Комитет по тестам производительности обработки транзакций (
Организации должна была объединить усилия производителей по разработке стандартных тестов, методик измерения производительности систем обработки транзакций и публикации результатов.
Все решения в
Рабочими органами
В 1989 году были предложены основные правила проведения испытаний и публикации результатов тестирования и разработан тест
Эти правила действуют и в настоящее время. Для признания результатов официальными данными
Тест
В его основе банковская операция помещения средств на депозит или их изъятие со счета.
Результат измерения показывает, сколько подобных операций может быть выполнено в единицу времени. Транзакция
Отличие теста
Тестовый пакет
В нем моделируется достаточно сложная система, управляющая обработкой заказов.
Тест позволяет выполнить оценку основных компонент системы: терминалов, линий связи, центрального процессора, жестких дисков, баз данных.
В тесте моделируется работа оператора при вводе данных с клавиатуры.
В тесте предусмотрено выполнение следующих транзакций:
Тест обеспечивает измерение скорости транзакций по новым заказам, остальные транзакции выполняются в это время в фоновом режиме.
В качестве модели БД теста используется модель БД оптового поставщика, содержащая следующие таблицы: товарные склады, район, покупатель, заказ, порядок заказов, новый заказ, статья счета, складские запасы и история.
Система может масштабироваться за счет изменения количества товарных складов.
Результаты тестирования:
Стоимость представляет собой совокупную стоимость владения системой в течение пяти лет.
Этот тест является основным продуктом
Организация постоянно стремится создавать тесты, которые отвечают потребностям бурно развивающегося рынка вычислительных систем. Было предпринято несколько попыток создания тестов для оценки производительности серверов (
Тест предназначен для тестирования систем поддержки электронной коммерции.
Тесты
В тесте моделируются следующие нагрузки на систему:
Тест поддерживает следующие профили взаимодействия с клиентами:
Эти тесты предназначены для оценки производительность коммерческих систем поддержки принятия решений.
В них моделируются сложные запросы к базе данных от большого числа пользователей. Данные и запросы соответствуют основным типам запросов в системах поддержки принятия решений, интенсивность запросов отражает усредненную по индустрии бизнес-активность.
Поддержка теста ТPC-D прекращена с 1999 года.
Тесты
В тестах используется две метрики:
Во всех тестах
системы и ее эксплуатацию в течение пяти лет к производительности.
Ни один тест
Одной из независимых организаций, занимающихся оценкой производительности вычислительных систем, является компания
Компания была основана в 1981 году. Сферой ее деятельности является разработка программного обеспечения для измерения производительности вычислительных систем, а также заказное тестирование информационных систем, использующих ОС UNIX.
Используя методики оценок и тестовые смеси, разработанные
Тестовый набор
С его помощью можно получить следующие оценки:
Он позволяет выполнять анализ вычислительной системы без учета работы графического интерфейса и сетевых задержек.
Компания
На основе приведенных данных можно утверждать:
Как видно из вышеизложенного, пользователь или покупатель компьютера сам должен синтезировать
Рассмотрим несколько алгоритмически "прозрачных" задач, позволяющих достаточно эффективно варьировать вычислительной нагрузкой в ЭВМ как последовательной, так и параллельной архитектуры.
Задача о транзитивном замыкании относится к классу типа $$O(N^^{3})$$ и достаточно просто приводится к параллельному виду с помощью алгоритма Уошэлла - Флойда.
Формулировка задачи. Пусть имеется ориентированный граф связности $$G(V,E) $$ с множеством вершин $$V $$ и множеством ребер E. Необходимо пориен-тированный граф рис. 1.1 [70] и ему соответствует матрица смежности:
(рис 1.1) "Внутренний" параллелизм этой задачи в полной мере раскрывает рекурсивный алгоритм Уошэлла - Флойда [70]:
$$For\,\, k\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, j\,\, from\,\, 1\,\, to\,\, N, \\ x_{ij}^k:= x_{ij}^{k-1} + x_{ik}^{k-1} * x_{kj}^{k-1},$$где $$k$$ - шаг рекурсии, $$+$$ - логическое сложение, $$*$$ - логическое умножение. В этом алгоритме три вложенных цикла $$for$$, реализация которых требует $$O(N^^{3})$$
Здесь пунктирными линиями показаны значения, которые пробегают индексы $$i $$ и $$j $$ на каждом шаге рекурсии $$k$$.
Результирующий граф $$G^{+}$$ имеет вид рис. 1.2, и ему соответствует матрица смежности:
(рис 1.2) На рис. 1.2 пунктирными стрелками показаны ребра, порождаемые на каждом шаге рекурсии, откуда видно, что шаг рекурсии $$k$$ соответствует номеру вершины, через которую осуществляется транзитивное замыкание с учетом предыдущих шагов рекурсии.
Таким образом, максимальный коэффициент векторно-конвейерного
Задача о кратчайшем пути аналогична задаче о
В этом случае элементы матрицы $$||А||$$ определяются следующим образом:
Задача о кратчайшем пути заключается в вычислении матрицы $$||А^{+}||$$ кратчайших путей, в которых $$a^{+}_{ij}$$ есть длина такого пути из вершины $$i$$ к вершине $$j$$.
Например, граф связности имеет вид рис. 1.3 и ему соответствует матрица $$||А^{0}|$$ | [70]:
(рис 1.3) Тогда последовательность шагов алгоритма Уошэлла - Флойда примет вид:
с той разницей, что операции $$+$$ соответствует выбор минимального элемента, а операции $$*$$ - простое сложение.
Такая представительная задача позволяет исследовать затраты на управление ходом вычислительного процесса и издержки на организацию обмена с кеш-памятью. Для этого достаточно:
Временные затраты на управление в (1.1), то есть затраты на организацию трех вложенных цикло в $$for$$, зависят от архитектуры устройства управления процессора и в худшем случае определяются соотношением $$T_{u} = (3N)^3\tau_c(p)$$, которое соответствует микропрограммному алгоритму работы простейшего целочисленного устройства управления и при условии, что команда сравнения является двухцикловой:
Шаг 1. Прибавить "единицу" к содержимому $$j : j( t):=j(t-1)+1$$.
Шаг 2. Если содержимое $$j(t) = N$$, то прибавить "единицу" к содержимому $$i: i(t):=i(t-1)+1$$ и перейти к шагу 1. В противном случае выполнить шаг 1.
Шаг 3. Если содержимое $$i(t) = N$$, то прибавить "единицу" к содержимому $$k: k(t):=k(t-1)+1$$ и перейти к шагу 1. В противном случае выполнить шаг 1.
Шаг 4. Если содержимое $$k(t) = N$$, то конец программы (END). В противном случае выполнить шаг 1.
Здесь $$\tau_{c}(p)$$ - стандартный для всех ассемблерных инструкций цикл выполнения, который задается последовательностью синхроимпульсов (СИ).
Если устройство управления процессора выполнить по схеме трехступенчатого конвейера (рис. 1.4), то временные затраты на управление станут линейными $$T_{u} = (N+3)\tau_{c}$$, где 3 такта задержки расходуются на "холостой ход" конвейера.
(рис 1.4) Схема управления тремя вложенными циклами Алгоритмические временные затраты на коммутацию (пересылки данных в одноадресной ЭВМ) в (1.1) определяются организацией работы памяти. Если используется ассоциативная память (АЗУ), в которой операцию логического сложения можно выполнить непосредственным слиянием содержимого ячейки $$x_{ij}^{k-1}$$ с результирующим операндом $$х_{ij}^{k-1}* x_{kj}^{k-1}$$, то $$T_{АЗУ}= 3(N)^3\tau_{АЗУ}$$. В противном случае $$T_{ОЗУ}= 4(N)^3\tau_{ОЗУ}$$.
В однопроцессорных ЭВМ операционные временные затраты на (1.1) определяются соотношением $$T_{ОУ}= 2(N)^3\tau_{ОУ}$$.
Из приведенных данных видно:
В вычислительном алгоритме (1.2) экономия от включения цикла $$if$$ зависит от количества элементов матрицы смежности $$||А^{k}||$$ с "нулевыми" значениями, а в (1.3) - от количества элементов с "единичными" значениями, которое возрастает с ростом индекса $$k$$. Поэтому по мере роста индекса $$k$$ в случае (1.2) экономия от включения цикла $$if$$ будет падать, а в случае (1.3) - возрастать, но в любом случае затраты на управление увеличатся на $$\Delta T_u = (2N)^3\tau_c(p)$$.
Отсюда, в "пользовательском" варианте предпочтение следует отдавать вычислительному алгоритму по варианту (1.3), но в синтетические и испытательные программы для полноты эксперимента необходимо включать все три варианта, так как они моделируют различные условия (не) зависимости временных затрат от содержимого преобразуемых данных.
Алгоритм Уошэлла - Флойда допускает только
Задачи векторно-матричной алгебры перекрывают весь спектр размерностей задач табл. 1.1:
Поэтому эти задачи стараются включать во все испытательные и синтетические программы для оценки пропускной способности ВС по потокам команд и данных практически всех параллельных архитектур.
При всей кажущейся простоте исходного алгоритма умножения матриц, его можно реализовать тремя типами вычислительных алгоритмов, отличающимися порядком формирования результирующей матрицы.
где $${\langle}b_{jk}{\rangle}$$, $${\langle}с_{ik}{\rangle}$$ - соответственно строки матриц $$||B||$$ и $$||C||$$
где $${\langle}a_{ij}{\rangle}$$, $${\langle}с_{ik}{\rangle}$$ - соответственно строки матриц $$||A||$$ и $$||C||$$
Изменение порядка формирования результирующей матрицы сопровождается изменением порядка вызова данных, который может либо совпадать, либо не совпадать с порядком их хранения в ОЗУ. В современных ЭВМ данные в ОЗУ чаще хранятся по строкам и реже по столбцам. Это значит, что при "чтении" данных по столбцам и больших размерах преобразуемых матриц, превышающих размеры доступной пользователю кеш-памяти, возрастают паразитные пересылки страниц между кеш-памятью и ОЗУ и, как следствие, увеличивается продолжительность "среднего" цикла обращения к памяти.
Поэтому с помощью такой представительной задачи можно исследовать издержки на организацию обмена с кеш-памятью, для чего достаточно:
Временные затраты на управление в задачах векторно-матричной алгебры аналогичны затратам задачи о
Операционные временные затраты в данном случае зависят от схемы распараллеливания и не зависят от вычислительного алгоритма. Поэтому имеет смысл говорить только об удельных операционных затратах на формирование одного элемента результирующей матрицы, так как общее время вычисления всех ее элементов определяется доступным пользователю коэффициентом распараллеливания.
В изделиях микроэлектроники наибольшее распространение получили две схемы векторно-конвейерного распараллеливания
(рис 1.5) Схемы соединения "скаляторных" устройствПродолжительность $$T_{ОУ}(c_{ik}) = 2N\tau_c(*)$$ цикла формирования элемента $$c_{ik}$$, результирующей матрицы схемы рис. 1.5-а более чем в 2 раза может превосходить продолжительность $$T_{ОУ}( c_{ik}) = \tau_c (*)+N\tau_c (+)$$ того же цикла схемы рис. 1.5-б. В первом случае темп работы двухступенчатого конвейера из умножителя и сумматора-накопителя регламентирует более медленный умножитель, а во втором случае фаза умножения выполняется по всем входным операндам одновременно и поэтому темп работы $$N$$ ступенчатого конвейера лимитирует только фаза суммирования. Но это справедливо для (полу)заказного исполнения "скаляторов", в рамках которого справедливо неравенство $$\tau_c (*) > \tau_c (+)$$, где $$\tau_c (*)$$ и $$\tau_{c}(+)$$ - соответственно достижимое время цикла срабатывания аппаратно реализованного умножителя и сумматора. В RISC -архитектурах по определению $$\tau_{c}(*) = \tau_{c}(+)$$ и темп вычисления элемента результирующей матрицы по схеме рис. 1.5-б определяется соотношением $$T_{ОУ}(c_{ik}) = (N+1) \tau_{c}(*)$$.
В любом случае такой выигрыш оплачивается практически TV -кратным увеличением аппаратных затрат на схему рис. 1.5-б. Поэтому на практике большее распространение получила схема рис. 1.5-а, на основе которой можно варьировать коэффициентом распараллеливания $$\gamma$$ в пределах $$\gamma = \overline{1,N^2}$$, а не $$\gamma = \overline{1,N^3}$$.
При вычислении одного элемента результирующей матрицы на одном "скаляторном" устройстве рис. 1.5-а удельные алгоритмические временные затраты на коммутацию (пересылки данных в одноадресной ЭВМ) для всех трех алгоритмов определяются соотношением $$T_{ОЗУ}(c_{ik}) = (2N+1)\tau_{ОЗУ}$$. Снизить эти затраты можно в схеме "скалятора" с $$N$$ аккумуляторами, образующими FIFO -регистровую цепочку. Для такой схемы $$T_{ОЗУ}(c_{ik}) = (N+2)\tau_{ОЗУ}$$ (рис. 1.6).
(рис 1.6) Схема "скалятора" с N аккумуляторами"Скалятор" с $$N$$ аккумуляторами наиболее эффективен при построчном формировании элементов результирующей матрицы, так как в этом случае:
Однако такой двукратный выигрыш во времени оплачивается $$N$$ -кратным ростом аппаратных затрат на FIFO -регистровую цепочку аккумуляторов.
Из приведенных данных видно, что эффективное совмещение обработки одной области кеш-памяти с обновлением другой ее области можно получить, если $$T_{ОЗУ}(c_{ik}) = 2N\tau_c(*) \approx T_{ОЗУ}(c_{ik}) = (2N+1)\tau_{ОЗУ}$$, что осуществимо, если $$\tau_{c}(*) \approx \tau_{ОЗУ}$$. Последние условие как раз и предполагает отсутствие паразитных обновлений кеш-памяти за период вычисления матрицы $$||C||$$.
Таким образом, включив в состав синтетических и испытательных программ все три варианта вычислительных алгоритмов умножения матриц, можно с различной степенью интенсивности симулировать паразитные обновления кеш-памяти по ходу вычислений. Это позволяет при одних и тех же исходных данных в процессе испытаний и исследований (Б)ВС варьировать общим временем решения задач векторно-матричной алгебры в пределах 20-40 %.
Как показали эмпирические данные, в пользовательскую библиотеку вычислительных алгоритмов векторно-матричной алгебры, содержащую подпрограммы поэлементного умножения матриц и транспонирования, имеет смысл включить подпрограмму построчного умножения, что улучшает качество работы всего пакета на 20-30 %.
Задача сортировки данных методом "пузырька" относится к классу задач типа $$O(N^{2}) \le; N(N-1)/2$$, и при ее распараллеливании возникают достаточно типичные издержки управления коллективом вычислителей, которые связаны с информационной зависимостью параллельных процессов и которые кардинальным образом снижают фактический коэффициент распараллеливания.
Алгоритм сортировки методом "пузырька":
$$For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, j\,\, from\,\, i+1\,\, to\,\, N, \\ If\,\,x_{i}>x_j\Rigtharrow Tr(x_{i},x_j)$$где $$Tr(x_{i}, x_{j})$$ представляет собой транспозицию (перестановку) сравниваемых элементов $$x_i$$ и $$x_j$$.
Чтобы исследовать издержки управления сортировкой данных методом "пузырька", связанные с ростом коэффициента
Условие останова алгоритма сформулировано в шестом пункте, из чего следует, что его размерность нарастает по $$k: x_{i1} \le x_{i2} ... \le x_{ik}$$. Это условие представляет простейший алгоритм управления многопроцессорной системой, в которой согласно условию четвертого шага запуск следующей итерации многопроцессорной сортировки осуществляется синхронно и синфазно по всем процессорам и после того, как завершил работу самый нагруженный из них. Возникающие при этом "простои" процессоров накапливаются в сумме $$\eta(\{N_{k} \})$$, которая вычисляется на пятом шаге. Поэтому отношение $$\eta(N)/\eta(\{N_k\})$$ характеризует реально полученный "средний" коэффициент
Эмпирические данные говорят о том, что начиная с $$k = 4-5$$ один и более процессоров гарантировано начинают работать "вхолостую" и их количество возрастает с ростом $$k$$ до такой степени, что делает бессмысленным наращивание аппаратной платформы уже при $$k \ge 16$$.
В таких условиях можно варьировать правилами останова, что позволяет симулировать тот или иной вариант управления многопроцессорной архитектурой: распределенной, централизованной, потоком данных и т. п., который призван минимизировать простои базового алгоритма управления.
Таким образом, "представительность" задач сортировки состоит в том, что они позволяют исследовать пропускную способность сильно связанных многопроцессорных систем, не усложняя при этом вычислительное ядро алгоритма.
Одним из главных ограничивающих коэффициент распараллеливания факторов связан с падением вычислительной
В вычислительной технике алгоритм и реализующая его программа считаются вычислительно устойчивыми, если
Методику исследования вычислительной устойчивости алгоритмов проще всего проиллюстрировать на примере программы суммирования членов псевдослучайной последовательности из $$N$$ элементов.
Главными источниками погрешностей являются преобразователи десятичного кода в двоичный, денормализаторы в составе арифметических устройств плавающей запятой и шины данных. Все они имеют $$n$$ -битную разрядную сетку, конечность которой приводит:
В данном случае объектом исследований являются:
Первому алгоритму отвечает схема суммирования рис. 1.7-а, а второй алгоритм можно реализовать на двух типах аппаратных платформ, которые отличаются количеством операций пересылки частных сумм: с иерархической (рис. 1.7-б) и с последовательной (рис. 1.7-в) схемой накопления частных сумм, где количество сумматоров одинаково и равно $$2k -1$$, а время задержки разное и равно соответственно $$]log_{2} k[+1$$ и $$k$$ ( $$]log_{2} k [ $$ - старшее целое $$log_{2} k$$ ).
Методика управления интенсивностью проявления источников погрешности при вычислении суммы членов псевдослучайной последовательности использует следующие факторы:
(рис 1.7) Схемы накопления суммыЧтобы по этой методике исследовать
Из шести возможных вариантов шага 4 наиболее истинное значение $$(\Sigma_f)_{0}$$ накопленной суммы дает упорядоченная по возрастанию последова-тельность, полученная в формате $$double$$, то есть $$(\Sigma_f)_{0}:= \Sigma_{db}(\langle x_{i}\rangle )$$, так как в этом случае оба вычислительных источника имеют минимальную интенсивность.
Чтобы симулировать погрешность представления, шаг 1 необходимо выполнить сначала в формате $$double$$, а затем перейти к формату $$float$$.
Типовой график зависимости
(рис 1.8) Типовой график зависимости абсолютной погрешности суммирования от коэффициента распараллеливания вычислений, выполненных с одинарной точностью Таким образом, для создания полноценных синтетических и исследовательских программ нет необходимости усложнять их операционное ядро, которое резко удорожает разработку инструментальных платформ оценки пропускной способности (Б)ВС по
Реальная ценность вычислительных систем (ВС), ориентированных на решение "критических" задач предметной области, определяется качеством оценки требуемой пропускной способности по
Заказчика или покупателя таких ВС в первую очередь интересуют аппаратно-временные затраты на реализацию его алгоритмов, а системные издержки организации вычислений им воспринимаются как накладные расходы. Поэтому алгоритмические затраты должны быть удовлетворены в полном объеме, так как именно они определяют потребительскую ценность создаваемой ВС, а системные аппаратно-временные издержки необходимо минимизировать в ходе разработки, чтобы добиться приемлемого соотношения цены и качества.
В отличие от ЭВМ общего назначения, к которым можно отнести и персональные компьютеры, предметная область создаваемых (Б)ВС всегда характеризуется рекордными параметрами, но при этом она достаточно четко очерчена и потенциальному пользователю хорошо известны представленные выше характеристики. Это обеспечивает высокую степень достоверности оценки требуемой пропускной способности по потокам команд и данных, диктуемых алгоритмом и продолжительностью цикла решения задачи, зная которые, уже можно выбрать необходимую архитектуру и требуемый коэффициент
При таком подходе к проектированию или выбору (Б)ВС:
Такая методика оценки качества (Б)ВС исходит из безусловной поддержки темпа реального времени, диктуемого предметной областью, и для его реализации прежде всего необходимо получить аналитическую оценку "длины" программы $$L_p$$ вычислительного алгоритма "критической" задачи, которую в традиционных вычислительных технологиях измеряют максимальным количеством ассемблерных инструкций, реально расходуемых на ее решение. В нетрадиционных вычислительных технологиях "длину" программы приходится измерять в тех (микро)программных единицах, для которых известен или задан цикл исполнения.
Основная трудность оценки "длины" программы $$L_p$$ связана с нали-чием в вычислительном алгоритме операторов условных переходов типа $$if$$ которые ставят ее в прямую зависимость от содержимого обрабатываемых потоков данных, которые в данном случае необходимо рассматривать как случайные. Для (Б)ВС вносимая операторами $$if$$ "случайность" и вытекающая из нее неопределенность в длине программы ослабляется тем обстоятельством, что в высокоответственные применения оператор условных переходов должен мажорироваться оператором $$for$$, который, с одной стороны, призван лимитировать максимально допустимую по темпу реального времени продолжительность исполнения каждого цикла программы, а с другой стороны, должен повысить ее устойчивость к информационным сбоям, разрывая "бесконечные" циклы, чреватые потерей управления опасными технотронными комп лексами двойного назначения.
Зная "длину" программы $$L_p$$, можно выбрать тип архитектуры, "иде-альной" в том смысле, что при этом были учтены только алгоритмические затраты, а системные издержки считались нулевыми. Для этого достаточно воспользоваться соотношениями (1.5)-(1.7) раздела 1.5 курса "Задачи и модели вычислительных наноструктур" и проверить неравенства: $$L < \max L(ОКОД) = \Delta T_0 /\tau_c$$, $$L < \max L(ОКМД) = T_{k} / \tau_c$$ или $$L < \max L(МКМД) = T _{0}/\tau_c $$, где $$\Delta T_{k}$$ - дискрет времени, диктуемый теоремой Котельникова, $$T_{k} = \Delta T_{k} * N$$ - цикл формирования циклически обрабатываемой выборки данных из $$N$$ операндов, а $$T _{0}$$ - допустимое время задержки в (Б)ВС. Если ни одно из этих неравенств не выполняется, то необходимо переходить на уровень распараллеливания отдельных ассемблерных инструкций, то есть к архитектурам с микрокомандным уровнем доступа, гарантирующим максимально возможное функциональное насыщенное каждого такта работы (Б)ВС. Как показывает практика, выйти за рамки "идеальной" архитектуры разработчику в дальнейшем не удается, и ему остается только разрабатывать комплекс мер, направленных на минимизацию системных аппаратно-временных издержек.
Данная методика апробирована при создании спецпроцессоров обработки сигналов и изображений, как на основе заказных СБИС, так и на основе систолических и бит-матричных СБИС [70, 138-144]. Указанные аппаратные платформы поддерживают предметную область, для которой характерны [70]:
Признав, что циклы $$for$$ являются неотъемлемой составляющей таких (Б)ВС, решаемые ими задачи можно разбить на классы с характерной зависимостью количества арифметико-логических операций от количества операндов $$N$$ в циклически обрабатываемых потоках данных (табл. 1.1 [70]).
Численные значения табл. 1.1 соответствуют параметрам "критических" задач, актуальных на конец 80-х годов прошлого столетия. Тем не менее уже тогда требовались (Б)ВС с производительностью порядка $$10^{12}-10^{15}$$ ассемблерных операций в секунду. Если принять во внимание, что цикл исполнения ЦПОС - и RISC -инструкций был уже постоянен и в тот период времени не превышал 1 ГГЦ, становится ясно, что суммарный коэффициент
| Тип алгоритма | Необходимая производительность |
|---|---|
| Линейные, типа $$O(N)$$: | $$10^{2} -10^{5}$$ |
| Пространственная фильтрация | |
| Свертка | |
| Обнаружение контуров | |
| Второго порядка, типа $$O(N^2)$$: | $$10^{3} 10^{7}$$ |
| Сортировки | |
| Медианная фильтрация | |
| Классификация ближайшего соседа | |
| Третьего порядка, типа $$O(N^3)$$: | $$10^{4}-10^{8}$$ |
| Векторно-матричная алгебра | |
| Спектральные вычисления | |
| Адаптивная фильтрация |
Однако (Б)ВС решают не одну и не одни только "критические" задачи. Поэтому их операционный ресурс постоянно перераспределяется по ходу вычислений между решаемыми задачами, что требует учета системных издержек на организацию вычислений. Данное обстоятельство только подтверждает тот факт, что в любой нетрадиционной архитектуре (Б) ВС всегда найдется уровень управления фон-неймановского типа. В простейшем случае такое управление выполняется по жесткой циклограмме и связанные с ним издержки в основном сводятся к плановой обработке "прерываний", которые неминуемо вызывают "паразитные" перемещения программ и данных по иерархии запоминающих устройств (Б)ВС: регистры - КЭШ - ОЗУ - внешние ЗУ и обратно.
Но циклограмма жестко регламентирует только порядок (пере)запу-ска задач, время решения которых может флуктуировать в достаточно больших пределах (1,5-3 раза и более) из-за наличия циклов по условию. Объясняется это тем, что с помощью мажорирующих циклов $$for$$ удается ограничить только максимально допустимое время выполнения этого цикла, а реальные временные затраты могут оказаться значительно меньше, если сработает оператор $$if$$. В результате трудно рассчитать как время обработки одного планового "прерывания", которое зависит от фазы выполнения прерванной задачи, так и количество таких "прерываний". Основным источником такой неопределенности являются паразитные перезагрузки памяти на участках кеш - ОЗУ - внешние ЗУ, что вынуждает брать в кавычки термин "прерывание".
Отсюда, даже в этом простейшем режиме управления системные временные издержки носят случайный характер с очень высокой дисперсией моментов запуска каждой последующей фазы вычислительного процесса.
Чтобы компенсировать возникающие в реальных условиях временные простои, разработчики (Б)ВС стараются запускать в образующихся "паузах"
В случае ЭВМ общего назначения описанная ситуация резко усугубляется априорной неопределенностью сферы использования, что приводит к усложнению систем управления аппаратными ресурсами во время вычислений, которые сами становятся главными "пожирателями" этих же ресурсов, так как рассчитаны "на все случаи жизни". В результате системные временные затраты такого управления могут на 1-2 порядка превосходить аналогичные затраты на обслуживание алгоритма пользователя.
Такое соотношение между алгоритмическими затратами и системными накладными расходами вынуждало и вынуждает производителей и пользователей ЭВМ и особенно многопроцессорных ВС разрабатывать и использовать различные методы, методики и способы оценки качества создаваемых или покупаемых вычислительных средств, главным показателем которого, как правило, является пропускная способность по
В оценке пропускной способности прежде всего нуждается покупатель ЭВМ, в ее расчете - проектировщик, а к ее измерению обычно прибегают непосредственно в эксплуатации, когда требуется расширить сферу информационных услуг, что ставит пользователя перед дилеммой: реконструировать имеющуюся аппаратную платформу или закупить новую.
При оценке качества вычислительной техники все используемые показатели рекомендуется разбивать на 2 группы [106]: требования и атрибуты, первые из которых представляют собой спецификацию того, что должна делать система, а вторые включают характеристики для предпочтительного выбора при прочих равных условиях. Требования задают необходимые условия, которым должна удовлетворять система, и они выражаются совокупностью как измеряемых, так и качественных показателей: пропускная способность, массо-габариты, потребляемая мощность, стоимость, отказоустойчивость, интеллектуальный уровень программной поддержки и т. п. К атрибутам, как правило, относят субъективные показатели, которые делают проект инвестиционно привлекательным, а созданное изделие - конкурентоспособным. К архитектурным атрибутам обычно относят: гибкость (масштабируемость), расширяемость и комплексируемость, которые в совокупности характеризуют открытость системы.
При оценке пропускной способности по
Пропускную способность (Б)ВС можно также оценить на основе аналитических, событийных или эмпирических моделей, а также прямым измерением характеристик составляющих блоков и устройств. Главные ограничения аналитических моделей связаны с трудностями описания взаимодействий аппаратуры и программного обеспечения, последнее из которых обычно приходится рассматривать как "черный ящик". Главные проблемы событийных и эмпирических моделей, а также прямого измерения состоят в сложности и стоимости их разработки.
В табл. 1.2 приведены эмпирические данные качества применения каждого метода оценки производительности по состоянию на 1985 год [106]. Здесь 1 означает, что метод использовался, но оказался неадекватным, 2 - метод оказался недостаточно полезным, 3 - метод дал хорошие результаты и прочерк - метод не применялся. За прошедшие годы база апробации методов оценки расширилась, сами методики углубились и удешевились за счет создания специализированных инструментальных платформ их реализации.
| Метод оценки | Оценка при выборе системы | Расчет при разработке | Измерение для реконфигурации | |||
|---|---|---|---|---|---|---|
| Новая аппаратура | Новые программы | Создаваемая аппаратура | Создаваемые программы | Реконфигурация аппаратуры | Реконфигурация программ | |
| Длительность цикла | 1 | - | 1 | - | - | - |
| Смесь команд | 1 | - | 1 | - | - | - |
| Представительные программы | 2 | 1 | 2 | 1 | - | 1 |
| Аналитические модели | 2 | 1 | 2 | 1 | 2 | - |
| Испытательные программы | 3 | 3 | 2 | 2 | 2 | |
| Синтетические программы | 3 | 3 | 2 | 2 | 2 | 2 |
| Моделирование | 3 | 3 | 3 | 3 | 3 | 3 |
| Прямое измерение | 2 | 2 | 2 | 2 | 3 | 3 |
Тем не менее, данные табл. 1.2 позволяют сделать следующие выводы, которые справедливы и для современных условий:
Сравнение компьютеров между собой обычно начинают с оценки их производительности. Это потребовало введения соответствующих единиц измерения производительности и разработки стандартных методов ее оценки.
Методы оценки производительности вычислительных систем должны отвечать определенным требованиям. Прежде всего, они должны быть общепризнанными, максимально полно оценивать вычислительные системы и соответствовать задачам пользователя. Должна быть обеспечена их доступность для независимой и самостоятельной экспертизы.
В основе используемых в настоящее время методов оценки и сравнения производительности вычислительных систем лежит время.
Компьютер, который выполняет определенный объем работы за меньшее время, считается более быстродействующим.
Оценка временных характеристик выполняемых процессором работ - далеко не тривиальная задача.
Для пользователя важно время, за которое решается его задача. Но практически нет программ, которые могут работать без некоторой операционной системы. В связи с эти возникают дополнительные накладные временные затраты. Поэтому при измерении производительности чаще всего используется сумма пользовательского и системного времени центрального процессора.
Дополнительные сложности при сравнении временных характеристик решаемых на разных компьютерах задач обусловлены тем, что системный код при решении задачи на одном компьютере на другом компьютере может стать пользовательским.
В ходе измерений появляется значительные методические ошибки, вызванные нарушением базовой концепция построения измерительных систем, в результате чего "измерительный прибор" становится неотъемлемой частью измеряемой системы.
Возникают серьезные методические трудности сравнения производительности компьютеров с разными операционными системами.
В связи с этим в методиках оценки производительности используют разное время:
Для измерения времени, затрачиваемого процессором на выполнение данной программе, используется специальное время, которое называют временем центрального процессора (
Время центрального процессора можно разделить пользовательское и системное.
Все современные ЭВМ работают в общем случае, как минимум, в двух-задачном режиме, обслуживая запросы операционной системы и запросы задачи пользователя.
В случаях, когда функции операционных систем могут быть сведены до одной простой задачи диспетчеризации заданий, системным временем центрального процессора можно пренебречь. Примером могут служить бортовые системы управления авиационных и космических комплексов,
Особенностью процессора как объекта измерения является то, что скорость взаимодействия функциональных устройств процессора чаще всего не зависит от динамических характеристик этих устройств, а задается частотой генератора тактовых импульсов. Поэтому время центрального процессора может быть вычислено двумя способами:
Важной характеристикой процессора является среднее количество тактов синхронизации, необходимых для выполнения одной команды (
Производительность центрального процессора определяется тремя параметрами:
Все эти параметры тесно связаны между собой:
В процессе поиска стандартной метрики для оценки производительности вычислительных систем было выбрано несколько единиц измерения.
Одной из наиболее распространенных среди них является MIPS (Million Instruction Per Second). Она показывает количество команд программы, выполняемых в секунду.
Производительность определяется как обратная ко времени выполнения величина, а более быстродействующий компьютер имеет более высокий MIPS-рейтинг.
На первый взгляд метрика очень проста, но ее использование не позволяет учесть особенности выполняемой программы и архитектуру процессора. Невозможно сравнивать компьютеры, имеющие разные системы команд. Даже на одном компьютере результат меняется при решении разных задач. Серьезные проблемы возникают в связи с использованием сопроцессоров для выполнения команд с плавающей запятой и оптимизирующих компиляторов. Все это не дает возможности выполнять объективное сравнение разных процессоров.
С понятием MIPS в свое время была связано еще две метрики, основанные на производительности эталонных компьютеров VAX 11/780 компании DEC и одной из моделей RS/6000 компании IBM. Производительность этих компьютеров определялась как 1 MIPS. Производительность тестируемых систем вычислялась относительно производительности этих компьютеров, которые являются эталонными. Приблизительное соотношение между этими величинами таково: 1 IBM MIPS равен 1.6 DEC MIPS.
Использование эталонного компьютера сопряжено с серьезными трудностями:
Использование измерения производительности компьютеров в MIPS не всегда объективно. Примером могут служить задачи, связанные с научно-техническими расчетами. В них широко применяется арифметика с плавающей точкой. Решение этих задач требует значительных вычислительных ресурсов. Вопрос оценки производительности используемых при их решении вычислительных систем всегда стоял очень остро. При этом достигнутые показатели производительности служили и служат показателем уровня разработок вычислительной техники.
Поэтому для подобных приложений производительность процессора оценивалась и оценивается в
Современные компьютеры имеют достаточно высокий уровень производительности, поэтому в настоящее время используются производные величины от
Этот показатель в основном характеризует использование компьютеров в научно-технических приложениях. Он предназначен для оценки быстродействия при выполнении вычислительной системой операций плавающей арифметики. В противном случае его использование не всегда корректно.
Этот показатель производительности, так же как и MIPS, зависит от конкретной выполняемой программы и архитектуры процессора.
Однако у
Другая проблема заключается в том, что время выполнения разных операций с плавающей запятой может существенно отличаться, в результате рейтинг
Для оценки показателей производительности в MIPS и
Тестовая смесь
Смесь состоит из ста команд. Из них 53 оператора присваивания, 32 команды управления, 15 вызовов функций. В качестве метрики используется количество
"Ливерморские циклы" представляют собой типичный набор фрагментов программ на языке FORTRAN. [301, 302] В этих программах реализованы разные вычислительные алгоритмы:
Их выбор был основан на богатом опыте создания суперкомпьютеров и проведения сложнейших научных и инженерных расчетов Ливерморской национальной лаборатории им. Э. Лоуренса (Lawrence Livermore National Laboratory,
При тестировании используется либо малый набор (14 циклов), либо большой набор (24 цикла).
Коэффициент распараллеливания применяемых алгоритмов лежит в диапазоне от 0 до 1. Это позволяет использовать "Ливерморские циклы" для оценки производительности вычислительных систем, имеющих различную архитектуру. Тест практически не используется.
Тесты
Применяемые в этих программах алгоритмы широко используются при решении многих практических задач. С эти связана популярность этого теста среди пользователей.
Аргонская национальная лаборатория (
Тест
В основе используемых в
Исходные данные для тестирования представляются в виде вещественных чисел двойной точности. Полученные результаты выражаются в
Тест
В тесте первого уровня
Первый уровень этого теста нельзя применять в вычислительных системах, позволяющих поместить всю исходную матрицу в кэш-памяти.
В этом случае полученные результаты могут существенно превышать реальные возможности системы.
Применение тестов
Для оценки производительности таких систем используется тест
Тестовый пакета
Анализ подходов к оценке производительности вычислительных систем позволяет сделать следующие выводы:
С точки зрения пользователя оценку производительности вычислительной системы лучше всего выполнять с использованием реальных программ, планируемых для использования на ней. Наиболее объективной оценкой производительности вычислительной системы при этом будут временные характеристики их исполнения.
Учитывая это, разработчики инструментальных средств измерения производительности вычислительных систем стремятся смоделировать работу типичных пользовательских приложений.
Рассмотрим основные особенности работы наиболее распространенных на практике стандартных инструментальных платформ измерения производительности компьютеров.
Важнейшей характеристикой вычислительных систем является производительность. Все разработчики компьютерной техники стремятся к установлению рекордов производительности, рассматривая их как инструмент в конкурентной борьбе. Этот инструмент работает только при условии легитимности полученных при тестировании результатов. Именно поэтому на паритетных началах ведущие производители создали несколько организаций, отвечающих за тестирование вычислительных систем.
Одной из таких организаций стала созданная в 1988 году корпорация SPEC (Standard
Цель корпорации состоит в разработке и сопровождении стандартизованных
Для членства в SPEC достаточно подать заявку и оплатить вступительный взнос.
Основное направление деятельности SPEC - подготовка тестов для оценки производительности основных подсистем компьютеров, которые могут использоваться, как разработчиками, так и потребителями вычислительной техники. Вся информация о предлагаемых наборах тестов публикуется.
Чтобы воспользоваться тестами SPEC, необходимо приобрести соответствующую лицензию. Так как целью организации не является получение прибыли, стоимость лицензий покрывает только административные расходы.
Можно выделить два базовых набора тестов SPEC CINT95, CFP95. С их помощью оценивается производительность компьютера и эффективность работы компиляторов. Тесты построены так, чтобы накладные расходы на работу ОС и выполнение операций ввода/вывода были пренебрежимо малы. Тесты ориентированы на ОС UNIX. При этом предусмотрена возможность их импорта на системные платформы Microsoft и других производителей.
Появления третьего по хронологии комплекта тестов была обусловлена рядом причин:
В качестве метрик производительности выполнения операций целочисленной и
Тест CINT95 предназначен для оценки производительности процессора при работе с целыми числами. В него входят восемь программ для решения задач из следующих областей приложения: искусственный интеллект, моделирование, программирование, компрессия, интерпретация языков, обработка, Shell-интерпретатор, базы данных.
В качестве языка программирования используется Си.
Тест CFP95 предназначен для оценки производительности процессора при работе с числами с плавающей точкой. В него входят десять программ для решения задач из следующих областей приложения: гидродинамика, предсказание погоды, квантовая физика, астрофизика, электромагнетизм, гидродинамика, моделирование, квантовая химия.
В качестве языка программирования используется ФОРТРАН.
Тесты
Для многопроцессорных и многозадачных систем необходимо оценивать их пропускную способность, которая равна количеству заданий, выполняемых системой в единицу времени. Тесты
Тест SPECrate был создан для оценки производительности многопроцессорных систем. Алгоритм тестирования достаточно прост. Одновременно запускается несколько одинаковых
Могут быть получены оценки SPECrate_int95, SPECrate_fp95, соответствующие целочисленным операциям и операциям с плавающей запятой. При тестировании измерения проводятся независимо по каждому тесту. Количество запускаемых копий теста зависит от архитектуры исследуемой системы. Измеряется время завершения последней копии тестовой программы.
Для исключения влияния на результаты тестирования работы компилятора используются оценки: SPECrate_base_int95 и SPECrate_base_fp95.
В результате тестирования может быть получена детальная оценка производительности исследуемой вычислительной системы.
Возможны следующие варианты выполнения
В 1988 году по инициативе Омни Шерлин (Omni Serlin) был создан Комитет по тестам производительности обработки транзакций (
Организации должна была объединить усилия производителей по разработке стандартных тестов, методик измерения производительности систем обработки транзакций и публикации результатов.
Все решения в
Рабочими органами
В 1989 году были предложены основные правила проведения испытаний и публикации результатов тестирования и разработан тест
Эти правила действуют и в настоящее время. Для признания результатов официальными данными
Тест
В его основе банковская операция помещения средств на депозит или их изъятие со счета.
Результат измерения показывает, сколько подобных операций может быть выполнено в единицу времени. Транзакция
Отличие теста
Тестовый пакет
В нем моделируется достаточно сложная система, управляющая обработкой заказов.
Тест позволяет выполнить оценку основных компонент системы: терминалов, линий связи, центрального процессора, жестких дисков, баз данных.
В тесте моделируется работа оператора при вводе данных с клавиатуры.
В тесте предусмотрено выполнение следующих транзакций:
Тест обеспечивает измерение скорости транзакций по новым заказам, остальные транзакции выполняются в это время в фоновом режиме.
В качестве модели БД теста используется модель БД оптового поставщика, содержащая следующие таблицы: товарные склады, район, покупатель, заказ, порядок заказов, новый заказ, статья счета, складские запасы и история.
Система может масштабироваться за счет изменения количества товарных складов.
Результаты тестирования:
Стоимость представляет собой совокупную стоимость владения системой в течение пяти лет.
Этот тест является основным продуктом
Организация постоянно стремится создавать тесты, которые отвечают потребностям бурно развивающегося рынка вычислительных систем. Было предпринято несколько попыток создания тестов для оценки производительности серверов (
Тест предназначен для тестирования систем поддержки электронной коммерции.
Тесты
В тесте моделируются следующие нагрузки на систему:
Тест поддерживает следующие профили взаимодействия с клиентами:
Эти тесты предназначены для оценки производительность коммерческих систем поддержки принятия решений.
В них моделируются сложные запросы к базе данных от большого числа пользователей. Данные и запросы соответствуют основным типам запросов в системах поддержки принятия решений, интенсивность запросов отражает усредненную по индустрии бизнес-активность.
Поддержка теста ТPC-D прекращена с 1999 года.
Тесты
В тестах используется две метрики:
Во всех тестах
системы и ее эксплуатацию в течение пяти лет к производительности.
Ни один тест
Одной из независимых организаций, занимающихся оценкой производительности вычислительных систем, является компания
Компания была основана в 1981 году. Сферой ее деятельности является разработка программного обеспечения для измерения производительности вычислительных систем, а также заказное тестирование информационных систем, использующих ОС UNIX.
Используя методики оценок и тестовые смеси, разработанные
Тестовый набор
С его помощью можно получить следующие оценки:
Он позволяет выполнять анализ вычислительной системы без учета работы графического интерфейса и сетевых задержек.
Компания
На основе приведенных данных можно утверждать:
Как видно из вышеизложенного, пользователь или покупатель компьютера сам должен синтезировать
Рассмотрим несколько алгоритмически "прозрачных" задач, позволяющих достаточно эффективно варьировать вычислительной нагрузкой в ЭВМ как последовательной, так и параллельной архитектуры.
Задача о транзитивном замыкании относится к классу типа $$O(N^^{3})$$ и достаточно просто приводится к параллельному виду с помощью алгоритма Уошэлла - Флойда.
Формулировка задачи. Пусть имеется ориентированный граф связности $$G(V,E) $$ с множеством вершин $$V $$ и множеством ребер E. Необходимо пориен-тированный граф рис. 1.1 [70] и ему соответствует матрица смежности:
(рис 1.1) "Внутренний" параллелизм этой задачи в полной мере раскрывает рекурсивный алгоритм Уошэлла - Флойда [70]:
$$For\,\, k\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, j\,\, from\,\, 1\,\, to\,\, N, \\ x_{ij}^k:= x_{ij}^{k-1} + x_{ik}^{k-1} * x_{kj}^{k-1},$$где $$k$$ - шаг рекурсии, $$+$$ - логическое сложение, $$*$$ - логическое умножение. В этом алгоритме три вложенных цикла $$for$$, реализация которых требует $$O(N^^{3})$$
Здесь пунктирными линиями показаны значения, которые пробегают индексы $$i $$ и $$j $$ на каждом шаге рекурсии $$k$$.
Результирующий граф $$G^{+}$$ имеет вид рис. 1.2, и ему соответствует матрица смежности:
(рис 1.2) На рис. 1.2 пунктирными стрелками показаны ребра, порождаемые на каждом шаге рекурсии, откуда видно, что шаг рекурсии $$k$$ соответствует номеру вершины, через которую осуществляется транзитивное замыкание с учетом предыдущих шагов рекурсии.
Таким образом, максимальный коэффициент векторно-конвейерного
Задача о кратчайшем пути аналогична задаче о
В этом случае элементы матрицы $$||А||$$ определяются следующим образом:
Задача о кратчайшем пути заключается в вычислении матрицы $$||А^{+}||$$ кратчайших путей, в которых $$a^{+}_{ij}$$ есть длина такого пути из вершины $$i$$ к вершине $$j$$.
Например, граф связности имеет вид рис. 1.3 и ему соответствует матрица $$||А^{0}|$$ | [70]:
(рис 1.3) Тогда последовательность шагов алгоритма Уошэлла - Флойда примет вид:
с той разницей, что операции $$+$$ соответствует выбор минимального элемента, а операции $$*$$ - простое сложение.
Такая представительная задача позволяет исследовать затраты на управление ходом вычислительного процесса и издержки на организацию обмена с кеш-памятью. Для этого достаточно:
Временные затраты на управление в (1.1), то есть затраты на организацию трех вложенных цикло в $$for$$, зависят от архитектуры устройства управления процессора и в худшем случае определяются соотношением $$T_{u} = (3N)^3\tau_c(p)$$, которое соответствует микропрограммному алгоритму работы простейшего целочисленного устройства управления и при условии, что команда сравнения является двухцикловой:
Шаг 1. Прибавить "единицу" к содержимому $$j : j( t):=j(t-1)+1$$.
Шаг 2. Если содержимое $$j(t) = N$$, то прибавить "единицу" к содержимому $$i: i(t):=i(t-1)+1$$ и перейти к шагу 1. В противном случае выполнить шаг 1.
Шаг 3. Если содержимое $$i(t) = N$$, то прибавить "единицу" к содержимому $$k: k(t):=k(t-1)+1$$ и перейти к шагу 1. В противном случае выполнить шаг 1.
Шаг 4. Если содержимое $$k(t) = N$$, то конец программы (END). В противном случае выполнить шаг 1.
Здесь $$\tau_{c}(p)$$ - стандартный для всех ассемблерных инструкций цикл выполнения, который задается последовательностью синхроимпульсов (СИ).
Если устройство управления процессора выполнить по схеме трехступенчатого конвейера (рис. 1.4), то временные затраты на управление станут линейными $$T_{u} = (N+3)\tau_{c}$$, где 3 такта задержки расходуются на "холостой ход" конвейера.
(рис 1.4) Схема управления тремя вложенными цикламиАлгоритмические временные затраты на коммутацию (пересылки данных в одноадресной ЭВМ) в (1.1) определяются организацией работы памяти. Если используется ассоциативная память (АЗУ), в которой операцию логического сложения можно выполнить непосредственным слиянием содержимого ячейки $$x_{ij}^{k-1}$$ с результирующим операндом $$х_{ij}^{k-1}* x_{kj}^{k-1}$$, то $$T_{АЗУ}= 3(N)^3\tau_{АЗУ}$$. В противном случае $$T_{ОЗУ}= 4(N)^3\tau_{ОЗУ}$$.
В однопроцессорных ЭВМ операционные временные затраты на (1.1) определяются соотношением $$T_{ОУ}= 2(N)^3\tau_{ОУ}$$.
Из приведенных данных видно:
В вычислительном алгоритме (1.2) экономия от включения цикла $$if$$ зависит от количества элементов матрицы смежности $$||А^{k}||$$ с "нулевыми" значениями, а в (1.3) - от количества элементов с "единичными" значениями, которое возрастает с ростом индекса $$k$$. Поэтому по мере роста индекса $$k$$ в случае (1.2) экономия от включения цикла $$if$$ будет падать, а в случае (1.3) - возрастать, но в любом случае затраты на управление увеличатся на $$\Delta T_u = (2N)^3\tau_c(p)$$.
Отсюда, в "пользовательском" варианте предпочтение следует отдавать вычислительному алгоритму по варианту (1.3), но в синтетические и испытательные программы для полноты эксперимента необходимо включать все три варианта, так как они моделируют различные условия (не) зависимости временных затрат от содержимого преобразуемых данных.
Алгоритм Уошэлла - Флойда допускает только
Задачи векторно-матричной алгебры перекрывают весь спектр размерностей задач табл. 1.1:
Поэтому эти задачи стараются включать во все испытательные и синтетические программы для оценки пропускной способности ВС по потокам команд и данных практически всех параллельных архитектур.
При всей кажущейся простоте исходного алгоритма умножения матриц, его можно реализовать тремя типами вычислительных алгоритмов, отличающимися порядком формирования результирующей матрицы.
где $${\langle}b_{jk}{\rangle}$$, $${\langle}с_{ik}{\rangle}$$ - соответственно строки матриц $$||B||$$ и $$||C||$$
где $${\langle}a_{ij}{\rangle}$$, $${\langle}с_{ik}{\rangle}$$ - соответственно строки матриц $$||A||$$ и $$||C||$$
Изменение порядка формирования результирующей матрицы сопровождается изменением порядка вызова данных, который может либо совпадать, либо не совпадать с порядком их хранения в ОЗУ. В современных ЭВМ данные в ОЗУ чаще хранятся по строкам и реже по столбцам. Это значит, что при "чтении" данных по столбцам и больших размерах преобразуемых матриц, превышающих размеры доступной пользователю кеш-памяти, возрастают паразитные пересылки страниц между кеш-памятью и ОЗУ и, как следствие, увеличивается продолжительность "среднего" цикла обращения к памяти.
Поэтому с помощью такой представительной задачи можно исследовать издержки на организацию обмена с кеш-памятью, для чего достаточно:
Временные затраты на управление в задачах векторно-матричной алгебры аналогичны затратам задачи о
Операционные временные затраты в данном случае зависят от схемы распараллеливания и не зависят от вычислительного алгоритма. Поэтому имеет смысл говорить только об удельных операционных затратах на формирование одного элемента результирующей матрицы, так как общее время вычисления всех ее элементов определяется доступным пользователю коэффициентом распараллеливания.
В изделиях микроэлектроники наибольшее распространение получили две схемы векторно-конвейерного распараллеливания
(рис 1.5) Схемы соединения "скаляторных" устройствПродолжительность $$T_{ОУ}(c_{ik}) = 2N\tau_c(*)$$ цикла формирования элемента $$c_{ik}$$, результирующей матрицы схемы рис. 1.5-а более чем в 2 раза может превосходить продолжительность $$T_{ОУ}( c_{ik}) = \tau_c (*)+N\tau_c (+)$$ того же цикла схемы рис. 1.5-б. В первом случае темп работы двухступенчатого конвейера из умножителя и сумматора-накопителя регламентирует более медленный умножитель, а во втором случае фаза умножения выполняется по всем входным операндам одновременно и поэтому темп работы $$N$$ ступенчатого конвейера лимитирует только фаза суммирования. Но это справедливо для (полу)заказного исполнения "скаляторов", в рамках которого справедливо неравенство $$\tau_c (*) > \tau_c (+)$$, где $$\tau_c (*)$$ и $$\tau_{c}(+)$$ - соответственно достижимое время цикла срабатывания аппаратно реализованного умножителя и сумматора. В RISC -архитектурах по определению $$\tau_{c}(*) = \tau_{c}(+)$$ и темп вычисления элемента результирующей матрицы по схеме рис. 1.5-б определяется соотношением $$T_{ОУ}(c_{ik}) = (N+1) \tau_{c}(*)$$.
В любом случае такой выигрыш оплачивается практически TV -кратным увеличением аппаратных затрат на схему рис. 1.5-б. Поэтому на практике большее распространение получила схема рис. 1.5-а, на основе которой можно варьировать коэффициентом распараллеливания $$\gamma$$ в пределах $$\gamma = \overline{1,N^2}$$, а не $$\gamma = \overline{1,N^3}$$.
При вычислении одного элемента результирующей матрицы на одном "скаляторном" устройстве рис. 1.5-а удельные алгоритмические временные затраты на коммутацию (пересылки данных в одноадресной ЭВМ) для всех трех алгоритмов определяются соотношением $$T_{ОЗУ}(c_{ik}) = (2N+1)\tau_{ОЗУ}$$. Снизить эти затраты можно в схеме "скалятора" с $$N$$ аккумуляторами, образующими FIFO -регистровую цепочку. Для такой схемы $$T_{ОЗУ}(c_{ik}) = (N+2)\tau_{ОЗУ}$$ (рис. 1.6).
(рис 1.6) Схема "скалятора" с N аккумуляторами"Скалятор" с $$N$$ аккумуляторами наиболее эффективен при построчном формировании элементов результирующей матрицы, так как в этом случае:
Однако такой двукратный выигрыш во времени оплачивается $$N$$ -кратным ростом аппаратных затрат на FIFO -регистровую цепочку аккумуляторов.
Из приведенных данных видно, что эффективное совмещение обработки одной области кеш-памяти с обновлением другой ее области можно получить, если $$T_{ОЗУ}(c_{ik}) = 2N\tau_c(*) \approx T_{ОЗУ}(c_{ik}) = (2N+1)\tau_{ОЗУ}$$, что осуществимо, если $$\tau_{c}(*) \approx \tau_{ОЗУ}$$. Последние условие как раз и предполагает отсутствие паразитных обновлений кеш-памяти за период вычисления матрицы $$||C||$$.
Таким образом, включив в состав синтетических и испытательных программ все три варианта вычислительных алгоритмов умножения матриц, можно с различной степенью интенсивности симулировать паразитные обновления кеш-памяти по ходу вычислений. Это позволяет при одних и тех же исходных данных в процессе испытаний и исследований (Б)ВС варьировать общим временем решения задач векторно-матричной алгебры в пределах 20-40 %.
Как показали эмпирические данные, в пользовательскую библиотеку вычислительных алгоритмов векторно-матричной алгебры, содержащую подпрограммы поэлементного умножения матриц и транспонирования, имеет смысл включить подпрограмму построчного умножения, что улучшает качество работы всего пакета на 20-30 %.
Задача сортировки данных методом "пузырька" относится к классу задач типа $$O(N^{2}) \le; N(N-1)/2$$, и при ее распараллеливании возникают достаточно типичные издержки управления коллективом вычислителей, которые связаны с информационной зависимостью параллельных процессов и которые кардинальным образом снижают фактический коэффициент распараллеливания.
Алгоритм сортировки методом "пузырька":
$$For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, j\,\, from\,\, i+1\,\, to\,\, N, \\ If\,\,x_{i}>x_j\Rigtharrow Tr(x_{i},x_j)$$где $$Tr(x_{i}, x_{j})$$ представляет собой транспозицию (перестановку) сравниваемых элементов $$x_i$$ и $$x_j$$.
Чтобы исследовать издержки управления сортировкой данных методом "пузырька", связанные с ростом коэффициента
Условие останова алгоритма сформулировано в шестом пункте, из чего следует, что его размерность нарастает по $$k: x_{i1} \le x_{i2} ... \le x_{ik}$$. Это условие представляет простейший алгоритм управления многопроцессорной системой, в которой согласно условию четвертого шага запуск следующей итерации многопроцессорной сортировки осуществляется синхронно и синфазно по всем процессорам и после того, как завершил работу самый нагруженный из них. Возникающие при этом "простои" процессоров накапливаются в сумме $$\eta(\{N_{k} \})$$, которая вычисляется на пятом шаге. Поэтому отношение $$\eta(N)/\eta(\{N_k\})$$ характеризует реально полученный "средний" коэффициент
Эмпирические данные говорят о том, что начиная с $$k = 4-5$$ один и более процессоров гарантировано начинают работать "вхолостую" и их количество возрастает с ростом $$k$$ до такой степени, что делает бессмысленным наращивание аппаратной платформы уже при $$k \ge 16$$.
В таких условиях можно варьировать правилами останова, что позволяет симулировать тот или иной вариант управления многопроцессорной архитектурой: распределенной, централизованной, потоком данных и т. п., который призван минимизировать простои базового алгоритма управления.
Таким образом, "представительность" задач сортировки состоит в том, что они позволяют исследовать пропускную способность сильно связанных многопроцессорных систем, не усложняя при этом вычислительное ядро алгоритма.
Одним из главных ограничивающих коэффициент распараллеливания факторов связан с падением вычислительной
В вычислительной технике алгоритм и реализующая его программа считаются вычислительно устойчивыми, если
Методику исследования вычислительной устойчивости алгоритмов проще всего проиллюстрировать на примере программы суммирования членов псевдослучайной последовательности из $$N$$ элементов.
Главными источниками погрешностей являются преобразователи десятичного кода в двоичный, денормализаторы в составе арифметических устройств плавающей запятой и шины данных. Все они имеют $$n$$ -битную разрядную сетку, конечность которой приводит:
В данном случае объектом исследований являются:
Первому алгоритму отвечает схема суммирования рис. 1.7-а, а второй алгоритм можно реализовать на двух типах аппаратных платформ, которые отличаются количеством операций пересылки частных сумм: с иерархической (рис. 1.7-б) и с последовательной (рис. 1.7-в) схемой накопления частных сумм, где количество сумматоров одинаково и равно $$2k -1$$, а время задержки разное и равно соответственно $$]log_{2} k[+1$$ и $$k$$ ( $$]log_{2} k [ $$ - старшее целое $$log_{2} k$$ ).
Методика управления интенсивностью проявления источников погрешности при вычислении суммы членов псевдослучайной последовательности использует следующие факторы:
(рис 1.7) Схемы накопления суммыЧтобы по этой методике исследовать
Из шести возможных вариантов шага 4 наиболее истинное значение $$(\Sigma_f)_{0}$$ накопленной суммы дает упорядоченная по возрастанию последова-тельность, полученная в формате $$double$$, то есть $$(\Sigma_f)_{0}:= \Sigma_{db}(\langle x_{i}\rangle )$$, так как в этом случае оба вычислительных источника имеют минимальную интенсивность.
Чтобы симулировать погрешность представления, шаг 1 необходимо выполнить сначала в формате $$double$$, а затем перейти к формату $$float$$.
Типовой график зависимости
(рис 1.8) Типовой график зависимости абсолютной погрешности суммирования от коэффициента распараллеливания вычислений, выполненных с одинарной точностью Таким образом, для создания полноценных синтетических и исследовательских программ нет необходимости усложнять их операционное ядро, которое резко удорожает разработку инструментальных платформ оценки пропускной способности (Б)ВС по
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.