Применение технологии статического анализа кода при разработке параллельных программ

Андрей Карпов
Статей: 373



Аннотация

В статье рассматривается вопрос применения статических анализаторов кода в современных процессах разработки параллельных программ. Появившись в 70-80-х годах как дополнение к компиляторам, статические анализаторы перестали пользоваться популярностью у разработчиков в 90-х годах. Вероятно, причиной этого стало повышение качества диагностики ошибок компиляторами. Однако, в 2000-х годах интерес к статическим анализаторам кода вновь начал расти. Это объясняется тем, что были созданы новые статические анализаторы кода, которые начали выявлять достаточно сложные ошибки в программах. Если статические анализаторы прошлого позволяли, например, обнаружить использование неинициализированной переменной, то современные статические анализаторы подходят к тому, чтобы обнаруживать небезопасный доступ к данным из нескольких потоков. Современным направлением развития статических анализаторов стало их применение для диагностики ошибок в параллельных программах. В работе рассмотрены ситуации, в которых применение таких инструментов позволяет существенно упростить создание параллельных программных решений.

Введение

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

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

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

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

1. Перспективы систем разработки и тестирования параллельных программ

Среди специалистов, занимающихся параллельными вычислениями, популярна шутка "Параллельные вычисления - технология будущего: и так будет всегда". Эта шутка не теряет актуальность уже несколько десятилетий. Аналогичные настроения были распространены в сообществе разработчиков архитектур компьютеров, обеспокоенном тем, что скоро будет достигнут предел тактовой частоты процессоров, однако частоты процессоров продолжают повышаться, хотя гораздо медленнее, чем раньше. Сплав оптимизма специалистов по параллельным вычислениям и пессимизма архитекторов систем способствовал появлению революционных многоядерных процессоров [1].

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

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

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

Естественно, со временем многие программисты освоят новые технологии и приобретут умение по созданию параллельного кода. Но пройдет очень много времени, и, скорее всего, не все смогут удачно осуществить такой переход. Дело в том, что технология параллельного программирования на порядок более сложна, чем другие смены технологий, как например переход от C++ к C# или от 32-х битных систем к 64-м битным. Параллельное программирование потребует от человека знаний теории создания параллельных алгоритмов, синхронизации, средств построения параллельного кода и многого другого.

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

В направлении автоматизации и облегчения создания параллельных программных систем сделано много шагов и предложен ряд решений и методологий. Примерами могут быть: MPI, OpenMP, Intel Threading Analysis Tools, или например российская разработка ИПС РАН OpenTS [2]. Но наличие всех этих систем, к сожалению, не дает возможности говорить о комплексном решении проблем, с которыми сталкивается начинающий или опытный разработчик параллельных систем.

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

2. Динамические и статический анализ параллельного кода как наиболее перспективные методы

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

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

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

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

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

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

Просмотр кода (англ. code review). Это самый старый, проверенный и надежный подход к поиску любых типов дефектов. Эта методика основана на совместном чтении кода, с выполнением ряда правил и рекомендаций, хорошо описанным, например, в [5]. К сожалению, эта практика неприменима для крупномасштабной проверки современных программных систем, в силу их большого объема. Хотя этот способ дает наилучшие результаты, он не всегда используется в условиях современных жизненных циклов разработки программного обеспечения, где немаловажным моментом является срок разработки и время выхода продукта на рынок. Поэтому просмотр кода чаще всего сводится к нечастым встречам, целью которых ставится обучение новых и менее опытных сотрудников написанию качественного кода, нежели чем для проверки работоспособностей ряда модулей. Это очень хороший способ повышения квалификации программистов, но его нельзя рассматривать как полноценное средство контроля качества разрабатываемой системы.

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

Динамический анализ кода - анализ программного обеспечения, выполняемый при помощи выполнения программ на реальном или виртуальном процессоре. Часто под динамическим анализом понимают исследование кода программы с целью ее оптимизации. Но мы будем говорить о динамическом анализе как о методе тестирования параллельных программ.

При динамическом подходе к обнаружению состояния гонок (race condition) программа выполняется, после чего сохраняется и анализируется история доступа к памяти. Поскольку такая история это фактически реальное исполнение программы, динамические анализаторы обычно выдают меньше диагностических сообщений, чем статические анализаторы. Другими словами, поскольку реально в программе были выполнены не все возможные ветки кода, то и гарантировать, что все ошибки обнаружены, невозможно. Динамический анализ также привносит накладные расходы в момент выполнения. Поэтому тщательный (то есть вычислительно сложный) анализ истории обычно откладывается на момент завершения работы программы, в отличие от варианта, когда и запись, и анализ истории ведется сразу же, то есть "на лету" [6].

Динамические анализаторы параллельного кода уже представлены коммерческими решениями и нашли достойное место в ряду других систем тестирования кода (яркий пример - комплект инструментов Intel Threading Tools [7]). По этой причине в статье мы не будем говорить об этой методике динамического анализа и надеемся, что она и соответствующие инструменты помогут в создании надежных параллельных систем.

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

Статический анализ кода (англ. static code analysis) - анализ программного обеспечения, производимый без реального выполнения исследуемых программ. В зависимости от используемого инструмента, глубина анализа может варьироваться - от определения поведения отдельных операторов до анализа, включающего весь имеющийся исходный код. В последнее время статический анализ всё больше используется в верификации свойств ПО, используемого в компьютерных системах высокой надежности.

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

3. Области эффективного применения статического анализатора параллельного кода

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

Для этого рассмотрим основные уровни декомпозиции задачи, в случае создания параллельных алгоритмов. Назовем эти уровни:

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

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

Разбиение каждой подзадачи на множество параллельных процедур. С одной стороны, это наиболее интересный уровень для анализа. Именно на уровне параллельных процедур допускается большое количество ошибок, что связано с высокой сложностью таких систем. Этот уровень интересен ещё и тем, что позволяет достигнуть хороших временных показателей от распараллеливания. Именно поэтому, многие исследователи начинают работать на этом уровне со статическим анализом и сталкиваются с большими трудностями. Они разбирают демонстрационные примеры. Но когда дело доходит до реальных систем, тем более написанных на таком сложном языке, как Си++, то создать работающий статический анализатор становится сложнейшей задачей. В результате мы наблюдаем практическое отсутствие коммерческих решений, основанных только на статическом анализе. Практически используется динамическо-статический анализ, когда после этапа выполнения программы выполняется статический анализ по полученным данным и исходному коду.

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

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

Мы рассмотрим возможность применения статических анализаторов кода на примере OpenMP, как наиболее активно развивающейся технологии. Стандарт OpenMP был разработан в 1997 г. и как API ориентирован на написание сортируемых многопоточных приложений. Сначала он был основан на языке Fortran, но позднее включил в себя и C/C++. Последняя версия OpenMP - 2.0; ее полностью поддерживает Visual C++ 2005. Стандарт OpenMP поддерживается и платформой Xbox 360.

4. Статический анализ кода на примере технологии OpenMP

Рассмотрим два простых примера, демонстрирующих, где статические анализаторы могут оказать помощь, например, в процессе написания нового кода. Представим, что программист написал следующий код:

size_t i;
#pragma omp parallel sections num_threads(2)
{
  #pragma omp section
  {
    for (i = 0; i != arraySize; ++i)
      array[i].a = 1;
  }
  #pragma omp section
  {
    for (i = 0; i != arraySize; ++i)
      array[i].b = 2;
  }
}

Рисунок 1 - Первый пример ошибки в OpenMP-коде.

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

Следующий пример тоже прост, но вполне может вызвать необходимость тратить существенное время на поиск ошибки. Данный код приводит к вычислению неверного значения суммы, вызванному отсутствием OpenMP директивы reduction(+: sum).

int sum = 0;
#pragma omp parallel num_threads(2)
{
  #pragma omp for
    for (int i = 0; i < arraySize; ++i)
      sum += array[i];
}
_tprintf(_T("sum=%i\n"), sum);

Рисунок 2 - Второй пример ошибки в OpenMP-коде.

Такие конструкции записи в одну переменную 'sum' из двух потоков также легко диагностируются статическими анализаторами и позволяют существенно облегчить работу по верификации программного кода.

Заключение

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

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

Библиографический список

  • Канг Су Гэтлин, Пит Айсенси. OpenMP и C++ // MSDN Magazine #10, 2005.
  • Абрамов С. М., Адамович А. И., Инюхин А. В., Московский А. А., Роганов В. А., Шевчук Ю. В., Шевчук Е. В. Т-система с открытой архитектурой // Суперкомпьютерные системы и их применение SSA'2004: Труды Международной научной конференции, 26-28 октября 2004 г. Минск, ОИПИ НАН Беларуси. - Минск, 2004, c. 18-22.
  • Дейкстра Э, Дисциплина программирования. М.: Мир, 1978.
  • Валиев М.К. Применение временной логики к спецификации программ. // Программирование. 1998, 2, с. 3-9.
  • Steve McConnell, "Code Complete, 2nd Edition" Microsoft Press, Paperback, 2nd edition, Published June 2004, 914 pages, ISBN: 0-7356-1967-0.
  • Yuan Yu, Tom Rodeheffer, Wei Chen. RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Tracking // SOSP05, October 23-26, 2005, Brighton, United Kingdom.
  • Клэй Р. Бреширз, Комплект инструментов Intel Threading Tools и библиотека OpenMP,


Найдите ошибки в своем C, C++, C# и Java коде

Предлагаем попробовать проверить код вашего проекта с помощью анализатора кода PVS-Studio. Одна найденная в нём ошибка скажет вам о пользе методологии статического анализа кода больше, чем десяток статей.

goto PVS-Studio;


Найденные ошибки

Проверено проектов
346
Собрано ошибок
13 188

А ты совершаешь ошибки в коде?

Проверь с помощью
PVS-Studio

Статический анализ
кода для C, C++, C#
и Java

goto PVS-Studio;