ООО «Системы программной верификации» Конференция CEE-SECR 2009 Авторы:Карпов Андрей Рыжков Евгений

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

Одна из основных сложностей параллельного программирования – выявление ошибок и отладка Гейзенбаг - термин, используемый в программировании для описания программной ошибки, которая исчезает или меняет свои свойства при попытке её обнаружения. К гейзенбагам относятся ошибки синхронизации в многопоточных приложениях.

Статический анализ кода Преимущества: – Раннее выявление ошибок – Независимость от среды исполнения – Анализ кода редко получающего управление – Хорошая масштабируемость – Функция обучения Недостатки: – Невозможность выявления ряда ошибок – Ложные срабатывания – Высокий уровень самодисциплины Статический анализ кода (англ. static code analysis) анализ программного обеспечения, производимый без реального выполнения исследуемых программ. Является альтернативой методологии обзора кода (англ. code review).

Инструменты статического анализа для выявления ошибок параллельности Не следует путать возможность выявления ошибок в параллельном коде и выявление ошибок связанных с использованием параллельности. Инструменты статического анализа для выявления ошибок параллельности в начале пути развития. Рассмотрим три инструмента: PC-Lint, Intel C++ (Parallel Lint), PVS-Studio (VivaMP).

Разные инструменты для разных технологий параллельного программирования POSIX threads (Pthreads); MPI; OpenMP; Intel Threading Building Blocks (TBB); Windows Threads.

PC-Lint PC-Lint – продукт компании Gimpel Software. Не имеет GUI, но его можно самостоятельно интегрировать в Visual Studio 2005/2008 или использовать оболочку Visual Lint. В девятой версии Gimpel Software PC-lint реализована диагностика ошибок в параллельных программах, построенных на основе технологии POSIX threads или схожих с ней.

Принцип работы PC-Lint Каждый файл обрабатывается отдельно Необходимо расставить «подсказки» Пример: //lint -sem(f, thread) void Foo(float value) { static int n = SlowFoo(); /*... */ } Поддержка POSIX threads

PC-Lint. Демонстрационный пример (PC-lint/FlexeLint 9.0 Manual Excerpts) 454 – Возврат управления при захваченном мьютекс 455 – Освобождение не захваченного мьютекса 456 – Возможна ошибка синхронизации, так как работа с мьютексом зависит от условия //lint -sem( lock, thread_lock ) //lint -sem( unlock, thread_unlock ) extern int g(); void lock(void), unlock(void); void f() { lock(); unlock(); // great // lock(); if( g() ) { unlock(); return; // ok } unlock(); // still ok // lock(); if( g() ) return; // Warning 454 unlock(); if( g() ) { lock(); unlock(); unlock(); // Warning 455 return; } // if( g() ) lock(); { // Warning 456 // do something interesting } if( g() ) unlock(); } // Warning 454 and 456

Intel C++ Parallel Lint Начиная с версии 11.1 в состав Intel C++ Compiler входит подсистема статического анализа OpenMP кода, получившая название Parallel Lint. Компилятор Intel C++ может интегрироваться в среду Visual Studio.

Принцип работы Intel C++ (Parallel Lint)

Intel C++. Демонстрационный пример (проект parallel_lint из дистрибутива Intel C++) int main(int argc, char *argv[]) { int i, j, limit; int start, end; intnumber_of_primes=0; int number_of_41primes=0; int number_of_43primes=0; start = 1; end = ; #pragma omp parallel for for(i = start; i

PVS-Studio (VivaMP) VivaMP – статический анализатор кода для проверки OpenMP программ. Входит в состав PVS-Studio. Интегрируется в Visual Studio 2005/2008. Справочная система интегрируется в MSDN.

Принцип работы PVS-Studio (VivaMP) Технология OpenMP способствует возникновению локальных распараллеленных участков кода. В результате большую часть ошибок можно выявить обрабатывая каждый файл отдельно. Не требуется какой либо адаптации проекта или специальных настроек. Фильтрация сообщений в режиме on-the-fly. Сохранение и загрузка списка предупреждений.

PVS-Studio. Демонстрационный пример #pragma omp parallel for for (size_t i = 0; i != n; ++i) { float *array = new float[10000]; delete [] array; } Анализатор VivaMP диагностирует в данном коде ошибку: V1302. The new operator cannot be used outside of a try..catch block in a parallel section. Ошибка связана с бросанием исключения из параллельного блока. pragma omp parallel { static int st = SlowFoo();... } Статическая переменная начнет процесс инициализации сразу в нескольких потоках, что может привести к неопределенному результату. В отличии от распараллеливания с использованием POSIX Threads, здесь анализатор легко может понять, что код находится в параллельной секции.

Сравнение Intel C++ (Parallel Lint) и PVS-Studio (VivaMP) primes_omp1.cpp(70): warning #12246: flow data dependence from (file:primes_omp1.cpp line:70) to (file:primes_omp1.cpp line:73), due to "limit" may lead to incorrect program execution in parallel mode primes_omp1.cpp(70): warning #12248: output data dependence from (file:primes_omp1.cpp line:70) to (file:primes_omp1.cpp line:70), due to "limit" may lead to incorrect program execution in parallel mode primes_omp1.cpp(75): warning #12246: flow data dependence from (file:primes_omp1.cpp line:75) to (file:primes_omp1.cpp line:73), due to "j" may lead to incorrect program execution in parallel mode primes_omp1.cpp(75): warning #12246: flow data dependence from (file:primes_omp1.cpp line:75) to (file:primes_omp1.cpp line:74), due to "j" may lead to incorrect program execution in parallel mode primes_omp1.cpp(75): warning #12246: flow data dependence from (file:primes_omp1.cpp line:75) to (file:primes_omp1.cpp line:75), due to "j" may lead to incorrect program execution in parallel mode primes_omp1.cpp(75): warning #12248: output data dependence from (file:primes_omp1.cpp line:75) to (file:primes_omp1.cpp line:72), due to "j" may lead to incorrect program execution in parallel mode primes_omp1.cpp(75): warning #12248: output data dependence from (file:primes_omp1.cpp line:75) to (file:primes_omp1.cpp line:75), due to "j" may lead to incorrect program execution in parallel mode primes_omp1.cpp(79): warning #12246: flow data dependence from (file:primes_omp1.cpp line:79) to (file:primes_omp1.cpp line:79), due to "number_of_primes" may lead to incorrect program execution in parallel mode primes_omp1.cpp(79): warning #12248: output data dependence from (file:primes_omp1.cpp line:79) to (file:primes_omp1.cpp line:79), due to "number_of_primes" may lead to incorrect program execution in parallel mode primes_omp1.cpp(80): warning #12246: flow data dependence from (file:primes_omp1.cpp line:80) to (file:primes_omp1.cpp line: 80), due to "number_of_41primes" may lead to incorrect program execution in parallel mode primes_omp1.cpp(80): warning #12248: output data dependence from (file:primes_omp1.cpp line:80) to (file:primes_omp1.cpp line:80), due to "number_of_41primes" may lead to incorrect program execution in parallel mode primes_omp1.cpp(81): warning #12246: flow data dependence from (file:primes_omp1.cpp line:81) to (file:primes_omp1.cpp line:81), due to "number_of_43primes" may lead to incorrect program execution in parallel mode primes_omp1.cpp(81): warning #12248: output data dependence from (file:primes_omp1.cpp line:81) to (file:primes_omp1.cpp line:81), due to "number_of_43primes" may lead to incorrect program execution in parallel mode Сравнение на базе parallel_lint из дистрибутива Intel C++ (всего 6 ошибок): Warning 1 error V1205: Data race risk. Unprotected concurrent operation with the 'limit' variable. r:\primes\primes_omp1\primes_omp1.cpp 69 Warning 2 error V1205: Data race risk. Unprotected concurrent operation with the 'j' variable. r:\primes\primes_omp1\primes_omp1.cpp 71 Warning 3 error V1205: Data race risk. Unprotected concurrent operation with the 'j' variable. r:\primes\primes_omp1\primes_omp1.cpp 74 Warning 4 error V1205: Data race risk. Unprotected concurrent operation with the 'number_of_primes' variable. r:\primes\primes_omp1\primes_omp1.cpp 78 Warning 5 error V1205: Data race risk. Unprotected concurrent operation with the 'number_of_41primes' variable. r:\primes\primes_omp1\primes_omp1.cpp 79 Warning 6 error V1205: Data race risk. Unprotected concurrent operation with the 'number_of_43primes' variable. r:\primes\primes_omp1\primes_omp1.cpp 80 Parallel Lint (Найдено 6 ошибок из 6. Количество предупреждений: 13) VivaMP (Найдено 6 ошибок из 6. Количество предупреждений: 6)

Некорректная таблица сравнения Intel C++ (Parallel Lint) и PVS- Studio (VivaMP) Вывод: Parallel Lint удобен тем, кто уже использует Intel C++ для сборки своих проектов PVS-Studio (VivaMP) подходит для разработчиков, использующих Visual C++

Преимущества от ранней диагностики ошибок Средняя стоимость исправления дефектов в зависимости от времени их внесения и обнаружения (данные для таблицы взяты из книги С. Макконнелла "Совершеннй Код").

void Foo() { #pragma omp for for (int i = 0; I < n; ++i) … } Цикл, вопреки ожиданиям программиста, будет выполняться только одним потоком. #pragma single { … } Забытая директива omp. И хотя компилятор VC++ выдаст сообщение "warning C4068: unknown pragma", это предупреждение может быть проигнорирована в больших сложных проектах, или быть вообще отключено. #pragma omp parallel { omp_set_num_threads(2); … } Количество потоков нельзя переопределять внутри параллельной секции. Это приводит к ошибке во время выполнения программы и ее аварийному завершению. Приложение. Дополнительные примеры

int a = 0; #pragma omp parallel for num_threads(4) for (int i = 0; i < ; i++) { a++; } Состояние гонки возникает тогда, когда несколько потоков многопоточного приложения пытаются одновременно получить доступ к данным, причем хотя бы один поток выполняет запись. Состояния гонки могут давать непредсказуемые результаты, и зачастую их сложно выявить. Иногда последствия состояния гонки проявляются только через большой промежуток времени и в совсем другой части приложения. Кроме того, ошибки такого рода невероятно сложно воспроизвести повторно. int a = 1; #pragma omp parallel for private(a) for (int i = 10; i < 100; ++i) { #pragma omp flush(a);... } Неэффективным следует считать использование директивы flush для локальных переменных (объявленных в параллельной секции), а также переменных помеченных как threadprivate, private, lastprivate, firstprivate. Директива flush не имеет для перечисленных переменных смысла, так как эти переменные всегда содержат актуальные значения. И дополнительно снижает производительность кода.

Дополнительная информация Статьи по тематике презентации: Андрей Карпов. Что такое "Parallel Lint"? Алексей Колосов, Евгений Рыжков, Андрей Карпов. 32 подводных камня OpenMP при программировании на Си++ Доклад подготовлен сотрудниками компании ООО «СиПроВер» Компания СиПроВер занимается разработкой программного обеспечения в области анализа исходного кода программ. Основные направления наших работ: верификация программ, статический анализ кода, развитие открытой библиотеки разбора и анализа Си/Си++ кода, создание инструментария для тестирования программных продуктов. Контактная информация: , Россия, Тула, Металлургов Web: Телефон: +7 (4872) Рабочее время: 09:00 – 18:00 (GMT +3:00)