Тестирование высокопроизводительных вычислительных приложений
Приложения для высокопроизводительных вычислений, выполняемые на с массовым параллелизмом, суперкомпьютерах состоят из параллельных программ, разработанных с использованием многопоточных и многопроцессных моделей . Приложения могут состоять из различных конструкций ( потоков , локальных процессов, распределенных процессов и т. д.) с различной степенью параллелизма. Хотя высокопроизводительные параллельные программы используют те же шаблоны, модели и принципы проектирования, что и последовательные программы, в отличие от последовательных программ они обычно демонстрируют недетерминированное поведение. Вероятность ошибок увеличивается с увеличением количества взаимодействий между различными параллельными конструкциями. Условия гонки , гонки данных, взаимоблокировки , пропущенные сигналы и активная блокировка — это распространенные типы ошибок.
Проблемы
[ редактировать ]Параллельные программы можно разделить на две основные категории: явно и неявно параллельные . Использование конструкций параллельного языка, определенных для создания процессов, связи и синхронизации, делает приложение явно параллельным. Использование инструмента или распараллеливающего компилятора для преобразования последовательной программы в параллельную делает ее неявно параллельной. Обе категории одинаково подвержены ошибкам.
Гейзенбакс
[ редактировать ]Параллельные приложения должны корректно выполняться при каждом возможном расписании потоков в базовой операционной системе. Однако традиционные методы тестирования обнаруживают мало ошибок, в основном из-за ошибок Heisenbugs. [1] проблема. Heisenbug — это ошибка, которая изменяется или исчезает при попытке изолировать и проверить ее с помощью отладчика путем добавления некоторых конструкций, таких как запросы синхронизации или операторы задержки.
Неповторяемость
[ редактировать ]Другая проблема возникает из-за непредсказуемого поведения планировщика . Различия в загрузке системы влияют на поведение планировщика. Это поведение нельзя изменить вручную. Чтобы противостоять этому индетерминизму, программу необходимо выполнять много раз в различных средах выполнения. Тем не менее, не гарантируется, что ошибка может быть воспроизведена. Большую часть времени программа работает корректно, и ошибка видна только при выполнении определенных условий. В результате неповторяемость параллельных программ является основным препятствием для обнаружения ошибок. В качестве примера рассмотрим следующее.
void thread1(void *t)
{
mutex_lock(a);
mutex_lock(b);
// do some work
.
.
.
mutex_unlock(b);
mutex_unlock(a);
}
|
void thread2(void *t)
{
mutex_lock(b);
mutex_lock(a);
// do some work
.
.
.
mutex_unlock(a);
mutex_unlock(b);
}
|
Очевидно, что здесь возникает проблема возникновения взаимоблокировок. Тем не менее, это может привести к тупиковой ситуации в некоторых запусках программы, в то время как в других она может работать успешно.
Эффект зонда
[ редактировать ]Эффект зондирования наблюдается в параллельных программах, когда операторы задержки вставляются в параллельные программы, сталкивающиеся с проблемами синхронизации. Этот эффект, как и эффект Гейзенбага, меняет поведение, которое может скрыть проблемы. Обнаружение источника пробного эффекта является серьезной проблемой при тестировании параллельных приложений.
Основное различие между эффектом пробы и Heisenbugs заключается в том, что Heisenbugs наблюдаются, когда к параллельному приложению во время тестирования добавляются дополнительные операторы задержки и/или запросы синхронизации, тогда как эффект зондирования наблюдается, когда разработчик добавляет операторы задержки в параллельные приложения с плохой синхронизацией.
Стратегии тестирования
[ редактировать ]Различия между последовательными и параллельными программами приводят к различиям в их стратегиях тестирования. Стратегии последовательных программ могут быть изменены, чтобы сделать их подходящими для параллельных приложений. Также были разработаны специализированные стратегии. Традиционно тестирование включает в себя разработку тестовых примеров и проверку того, что программа дает ожидаемые результаты. Таким образом, ошибки в спецификации, функциональности и т. д. выявляются путем запуска приложения и подвергания его таким методам тестирования, как функциональное тестирование , тестирование белого ящика , тестирование черного ящика и серого ящика . [2] Статический анализ также используется для обнаружения ошибок в высокопроизводительном программном обеспечении с использованием таких методов, как анализ потока данных , анализ потока управления , цикломатические сложности , анализ побега потоков и анализ статического среза для поиска проблем. Использование статического анализа перед тестированием функциональности может сэкономить время. Он может определить, «в чем заключается ошибка», найти источник ошибки. Методы статического анализа могут обнаруживать такие проблемы, как отсутствие синхронизации , неправильная синхронизация, прогнозировать возникновение взаимоблокировок и после ожидания ошибок в запросах рандеву .
Подробности:
Детерминированное планирование/воспроизводимое тестирование
[ редактировать ]Неопределенность планирования имеет два источника. [1]
- 1. Разделение времени
- Планировщик переключает контексты через равные промежутки времени. Этот интервал зависит от скорости отдельных процессоров, состояния иерархии кэш-памяти и загрузки системы. Даже на одном и том же процессоре при одинаковой нагрузке интервал меняется незначительно из-за незначительных изменений частоты системных часов.
- 2. Ошибки страницы
- Планировщик приостанавливает выполнение программы в случае возникновения ошибки страницы , позволяя другим потокам продолжить работу, пока система извлекает страницу. Поскольку возникновение ошибок страниц зависит от того, какие другие процессы выполняются, время переключения контекста становится неопределенным.
Чтобы сделать параллельные программы повторяемыми, используется внешний планировщик. Тестируемая программа предназначена для добавления вызовов в этот планировщик. Такие вызовы выполняются в начале и конце каждого потока, а также перед каждым запросом синхронизации. Этот планировщик выборочно блокирует потоки выполнения, поддерживая семафор, связанный с каждым потоком, так что в любой момент времени к выполнению готов только один поток. Таким образом, он преобразует параллельное недетерминированное приложение в последовательную последовательность выполнения для достижения повторяемости. Количество решений планирования, принимаемых планировщиком сериализации, определяется выражением –
(N * K / P)*{(N + P)!}
Where
N = number of threads
K = potential context switch points
P = budget of pre-emptive context switches
Тестирование, ориентированное на обратную связь
[ редактировать ]Чтобы получить более точные результаты с использованием детерминированного планирования, можно выбрать альтернативный подход. Несколько правильно размещенных приоритетов в параллельной программе могут обнаружить ошибки, связанные с гонками данных. [1] Ошибки встречаются кластерами. Существование одной ошибки устанавливает высокую вероятность появления большего количества ошибок в одном и том же участке кода. Таким образом, каждый этап процесса тестирования выявляет участки кода с ошибками. Следующий проход более тщательно исследует эти разделы, добавляя к ним вызовы планировщика. Разрешение выполнения проблемных мест в другом порядке может привести к неожиданному поведению.
Тестирование, связанное со временем
[ редактировать ]Эта стратегия гарантирует, что приложение не будет подвержено эффекту зондирования. Источники ошибок, вызывающих эффект зондирования, могут варьироваться от проблем с созданием задач до проблем с синхронизацией и связью. Требования к тестам, связанным с хронометражем: [3]
- Продолжительность задержки должна варьироваться
- Точки задержки должны охватывать соответствующие места программы.
- Операторы задержки должны быть вставлены, удалены или перемещены, чтобы вызвать эффект зондирования.
Количество тестовых случаев на набор входных данных равно:
nC1 + nC1 + … + nC1 = 2n -1
Where n = total number of synchronization, process creation and communication calls.
Это уравнение имеет экспоненциальный порядок. Чтобы уменьшить количество тестовых случаев, либо метод детерминированного выполнения (DET), либо метод множественного выполнения используется (MET). Необходимо решить различные вопросы:
- Отложенное выполнение
- Добавление задержек — простая задача. Типичный оператор Sleep() может использоваться для вставки задержек.
- Решаем, где вставить задержки
- Места вставки известны как точки задержки. Поскольку целью тестовых случаев, связанных с синхронизацией, является обнаружение ошибок синхронизации, связи и создания потоков, операторы задержки добавляются непосредственно перед этими операторами.
Преимущества
[ редактировать ]- Легко реализовать на нескольких процессорах без необходимости упорядочивания запросов синхронизации.
- Нет необходимости создавать график параллелизма
- Более эффективен для обнаружения неисправностей
- Общее количество тестовых случаев меньше, но покрытие кода больше благодаря статическому анализу.
Все испытания Du-Path
[ редактировать ]В этом методе применяется концепция пары «определение-использование» для определения путей, подлежащих тестированию.
Стратегии проверки
[ редактировать ]Проверка программного обеспечения — это процесс, который доказывает, что программное обеспечение работает правильно и выполняет поставленную задачу так, как задумано.
Тестовые расчеты
[ редактировать ]Входные данные передаются системе для генерации известного результата. Эта пара входных данных-результатов может быть получена на основе предыдущих эмпирических результатов и/или ручных расчетов. [4] Это тест на уровне системы, который можно выполнить только после интеграции всех соответствующих модулей. Более того, это лишь показывает, что ошибки существуют. Он не предлагает подробной информации о количестве ошибок, их местоположении или характере.
Тесты на симметрию
[ редактировать ]Эти тесты в основном используются для научного моделирования. Результат моделирования часто невозможно предсказать. Поскольку эти симуляции пытаются описать научные законы, симуляция должна учитывать любые симметрии в теории. Таким образом, изменяя входные условия вдоль линий симметрии и затем сравнивая полученные результаты с результатами, полученными извне, можно обнаружить наличие ошибок. [4]
В научных вычислениях большая часть данных находится в центральной области условий моделирования. В результате сложно выполнить тестирование граничных значений. [2] с экспериментальными данными в реальном времени. Таким образом, центр моделирования (например, для значения данных 10 на рисунке 1) смещается к одной из границ, чтобы эффективно проверить граничное условие.
Параллельные тесты реализации
[ редактировать ]Тесты параллельной реализации обычно используются для приложений, использующих модели программирования с распределенной памятью, такие как передача сообщений . Эти тесты часто применяются к программам, использующим обычные сетки процессоров. [4] [ нужны разъяснения ]
Глобальное суммирование
[ редактировать ]Многие параллельные базы данных используют распределенную параллельную обработку для выполнения запросов. При выполнении агрегатной функции, такой как sum, используется следующая стратегия: [5]
- Вычислите частичную сумму локально и одновременно на каждом процессоре, используя данные, имеющиеся в связанном с ним разделе диска.
- Добавьте эти локальные промежуточные итоги, чтобы получить окончательный результат.
Конечный результат может содержать некоторую ошибку округления, поскольку каждый процессор независимо округляет локальные результаты. Один из тестов – убедиться, что такие ошибки не возникают. Для этого необходимо показать, что совокупная сумма не зависит от разложения. Альтернативная схема суммирования заключается в отправке всех отдельных значений в один процессор для суммирования. Этот результат можно сравнить с распределенным результатом, чтобы обеспечить согласованность.
Инструменты
[ редактировать ]Microsoft Шахматы
[ редактировать ]Этот инструмент устраняет неопределенность с помощью детерминированного планирования. Он отслеживает пути расписания, выполненные ранее, и гарантирует, что каждый раз выполняется новый путь расписания. [1] [ нужны разъяснения ]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д Томас Болл; Себастьян Буркхардт; Пели де Алле; Маданлал Мусувати; Шаз Кадир (май – июнь 2011 г.). «Предсказуемое и прогрессивное тестирование многопоточного кода». Программное обеспечение IEEE . 28 (3): 75–83. дои : 10.1109/MS.2010.64 .
- ^ Перейти обратно: а б Искусство тестирования программного обеспечения, второе издание . Джон Уайли и сыновья. 2004. с. 256. ИСБН 978-0-471-46912-4 .
- ^ Чир-Сунь Ян; Лори Л. Поллок (1997). «Проблемы автоматического тестирования многопоточных программ». Материалы 14-й Международной конференции по тестированию компьютерного программного обеспечения : 157–166. CiteSeerX 10.1.1.52.8791 .
- ^ Перейти обратно: а б с Стивен Бут; Дэвид Хенти (2004). «Стратегии проверки программного обеспечения для высокопроизводительных вычислений». «Разработка программного обеспечения для приложений высокопроизводительных вычислительных систем (HPCS)» Семинар W3S — 26-я Международная конференция по разработке программного обеспечения . Том. 2004. стр. 24–26. дои : 10.1049/ic:20040413 . ISBN 0-86341-418-4 .
- ^ Корт, Генри . Концепции системы баз данных . МакГроу-Хилл.