Экспериментальные исследования – задачи, характеристика. Сравнение теоретических и экспериментальных данных. Возможные причины отклонений.
Экспериментальные исследования.
Они могут быть использованы как на ранних стадиях проектирования, так и во время разработки – для сравнения ожидаемых и полученных результатов.
Первым шагом в экспериментальных исследованиях должно быть определение данных, какие мы рассчитываем получить.
Обычно эксперименты выпадают на некотором диапазоне данных – различном размещением задачи и различном количестве процессоров. Увеличивая количество точек измерения, мы снижаем влияние ошибок. Когда эмпирические данные используются для оценки качества реализации, диапазон определяет также точность модели и выявляет области, в каких она неадекватна.
След шагом является планирование экспериментов. Критической точкой здесь является уверенность, что мы измеряем именно то, что собирались.
Задачей экспериментальных исследований является получение точных и воспроизводимых результатов. Так, время выполнения может быть определено различными путями
Эксперименты всегда выполняются неоднократно, чтобы обеспечить воспроизводимые результаты. Как правило, результаты не должны заметно отличаться – 2-3% может быть достаточно много, если требуется тонкая настройка модели. Возможные причины отклонений следующие:
недетерминированный алгоритм – используются случайные числа, выполняется поиск в дереве или работа распределена по процессорам с зависимости от времени. Недетерминизм, обусловленный случайными числами, исключается путем использования воспроизводящих генераторов. Использование, зависящее от времени, представляет более сложную проблему.
Неточный таймер – недостаточное разрешение или недостаточная точность. Недостаточное разрешение устраняется путем повторения работы или увеличения размера задачи. Неточность таймера – только выбором другого способа.
Затраты на запуск и завершение. Время выполнения системных функций, обеспечивающих запуск и завершение программы, выделение виртуальной памяти, выделение и освобождение процессоров и др. может значительно изменяться в зависимости от состояния системы. Поэтому как правило, это время стараются исключить.
Вложенность других программ. Если ресурсы компьютера разделяются между несколькими задачами, это может очень сильно исказить результаты измерений.
Коллизии (?)
Случайное распределение ресурсов – операционная система может использовать случайную стратегию выделения ресурсов, сильно влияя на измерение времени выполнения.
Изучение вариабельности результатов эксперимента поможет нам определить источники ошибок или неопределенностей в наших измерениях. Однако, даже достигнув воспроизводимости результатов, мы еще не можем быть уверенными, что они правильные. Увеличить степень достоверности можно, выполнив измерения несколькими способами и сравнив результаты. Например, кроме измерения времени выполнения отдельных комплектов, можно измерить еще время выполнения всей программы.
Сопоставление с моделью.
Если эксперименты используются для калибрования модели, мы должны сопоставить данные эксперимента с результатами моделирования. Это может быть выполнено, в частности, графическим путем.
Оценка реализации.
Модели производительности важны не только при проектировании, но и при реализации спроектированного алгоритма. Сравнение предсказанного и реального времени выполнения позволяет своевременно внести изменения в реализацию.
Даже при тщательной проработке проекта, идеальный характер моделей приводит к тому, что предсказанное и реальное значения редко совпадают. Значительные расхождения показывают, что либо модель недостаточно точна, либо реализация неверна. В первом случае мы можем определить области, в которых модель адекватна и неадекватна, а также переоценить некоторые решения, сделанные на основании этой модели. Во втором случае, с помощью модели мы можем оценить недостатки реализации.
В случае значительных расхождений первым шагом должно быть изучение как модели, так и реализации с целью определения, измеряем ли мы одно и то же. Следующим шагом будет получение профиля выполнения. Целью этого является более подробное изучение хода выполнения программы и идентификации участков, вызывающих расхождения. В идеале эти данные должны быть положительны на диапазоне размещения задачи и числа процессоров. Получив и проанализировав экспериментальный и модельный профили, можно сделать выводы о причине расхождений.
Неучтенные накладные расходы. Аномалии ускорения. Проблемы ввода-вывода.
Неучтенность накладных расходов.
Если время выполнения, определенное экспериментально, превышает предсказанное моделью, причина обычно лежит в неучтенных накладных расходах. Это означает, что модель неполна – некоторые аспекты остались неучтенными, либо были ошибочно отброшены как незначительные.
Аномалии ускорения.
В некоторых случаях приложение может выполняться быстрее, чем предсказывалось моделью. Если этот эффект увеличивается с увеличением числа процессоров, говорят об аномальном ускорении – наблюдаемое ускорение более, чем предсказанное. Это наблюдается в след случаях:
эффективность кэширования. На большинстве параллельных компьютеров каждый процессор имеет свой кэш. Если задача разделена на большое число процессоров, значительная часть данных может помещаться в быстрый кэш, значительно ускоряя обработку. Если уменьшение времени вычисления в результате этого эффекта превышает увеличение времени коммуникаций и простоя, то эффективность станет больше единицы и говорят о сверхлинейном ускорении.
Аномалия поиска. Это явление встречается в некоторых алгоритмах параллельного поиска, таких как ветви и графы. Если дерево поиска содержит решения на различной глубине, то поиск сначала-в-глубину в параллельном варианте в среднем посещает меньше узлов, чем при последовательном. Надо отметить, что в этом случае используются различные алгоритмы для последовательного и параллельного вариантов.
Ввод-вывод.
Производительность многих параллельных программ ограничена временем, необходимым для обмена с внешней памятью. Это связано со следующим:
контрольные точки. При проведении длительных вычислений необходимо сохранять промежуточные результаты, чтобы минимизировать ущерб от сбоев;
сохранение данных моделирования. Многие научные и инженерные вычисления требуют сохранять состояния для последующей визуализации или анализа.
объем обработанных данных. Многие задачи требуют объема данных, превышающий физическую память. Хотя подсистемы виртуальной памяти решают эту проблему, часто оказывается эффективнее управлять обменом непосредственно в приложении, к тому же не все параллельные компьютеры обеспечены виртуальной памятью;
анализ данных; многие приложения включают анализ больших количеств данных.
Общее описание параллельного ввода-вывода невозможно составить, т. к. эта подсистема очень сильно варьируется от компьютера к компьютеру. Однако некоторые общие принципы все же можно указать.
Ввод-вывод можно моделировать таким же образом, как и в межпроцессорных коммуникациях, с использованием ts и tw (хотя ts обычно намного больше). Как и при межпроцессорных коммуникациях, для повышения производительности необходимо максимально использовать имеющиеся каналы обмена, а также минимизировать начальную задержку. Разумеется, если компьютер содержит только один диск либо несколько дисков, подсоединенных к процессору, пространства для оптимизации нет. Однако на практике обычно имеется ряд альтернативных путей от процессоров к дискам, либо через отдельные «узлы ввода-вывода», либо при непосредственном подключении дисков к процессорам. В таких архитектурах
требуется организовать ввод-вывод так, чтобы операции чтения и записи шли одновременно по различным путям.
Кроме максимальной конкурентности в операциях ввода-вывода, следует также учесть количество таких операций. Часто именно количество операций ввода-вывода оказывает большее влияние на производительность, чем количество передаваемых данных. Количество операций часто зависит от раположения данных в оперативной памяти и на диске. При этом, если расположение в памяти определяется приложением, то расположение на диске может определяться как прикладным пакетом, так и операционной системой.
Если расположение на диске и в памяти отличается, то может потребоваться значительное количество операций ввода-вывода. Программа аналогична программе «перераспределения» данных, когда 2 комплекта параллельной программы используют различное размещение данных. Есть 2 варианта решения – переделать один из комплектов, и второй – явно перераспределить данные перед или во время передачи.