В начале и при завершении работы анализатор производит специальные действия. При выполнении команды инициализации ядро ищет результаты предыдущего запуска анализатора и в случае успеха загружает ранее полученные дерево контекстов и список массивов. В этом случае результаты нового запуска добавляются к уже имеющимся результатам, что необходимо при наличии нескольких тестов. Когда анализатор получает команду завершения, содержимое дерева контекстов и списка массивов сохраняется в файл.
4.4 Результаты тестирования
Тестирование анализатора проводилось на программах, реализующих решение уравнения Пуассона в трехмерном пространстве классическими итерационными методами: методом Якоби, методом последовательной верхней релаксации (SOR), методом красно-черного упорядочения (RedBlack), а также на программе, реализующей решение системы линейный алгебраических уравнений методом Гаусса.
Основные показатели производительности показаны на Таблице 1. В методах Якоби, SOR и RedBlack использовалась матрица размера 16x16x8. В методе Гаусса решалась система размера 100x100.
Таблица 1 – Показатели производительности
| Метод | Время выполнения, сек | Используемая память, Kb | ||
| без анализатора | с анализатором | без анализатора | с анализатором | |
| Якоби | 0,05 | 4,73 | 924 | 58136 |
| SOR | 0,05 | 2,23 | 908 | 25096 |
| RedBlack | 0,05 | 5,52 | 908 | 65752 |
| Гаусс | 0,04 | 6,45 | 980 | 51756 |
Из приведенных результатов следует, что текущая реализация динамического анализатора замедляет работу программы в 100 и более раз, используя при этом в десятки раз больший объем памяти. Это ограничивает возможности применения анализатора, поскольку для того, чтобы время анализа оставалось в разумных пределах, необходимо сильно уменьшать размерность решаемой задачи.
Следует отметить, что на данный момент не было сделано попыток оптимизации анализатора. Поэтому полученные результаты нельзя считать окончательными, и следует считать указанием на необходимость дальнейшей работы по улучшению метода динамического анализа.
5. Заключение
Подведем некоторые итоги данной работы. Динамический анализ зависимостей по данным обладает рядом преимуществ по сравнению с традиционными статическими методами анализа. Поскольку анализ производится во время выполнения программы, доступна вся информация о производимых доступах в память. Это позволяет получить абсолютно точную информацию о зависимостях по данным независимо от сложности индексных выражений массивов, наличия косвенной индексации или указателей.
Основным недостатком данного метода является отсутствие гарантии того, что все возможные зависимости по данным обнаружены. Это означает, что для проведения анализа необходимо наличие набора тестов, достаточно полно покрывающего различные варианты поведения программы. Кроме того, существенные затраты ресурсов анализатором при каждом запуске программы на выполнение заставляют уменьшать размерность задач для анализа, что, быть может, не всегда возможно.
В рамках данной работы один из методов динамического анализа был реализован в виде библиотеки на языке С++ (около 2500 строк исходного кода). Проведено тестирование анализатора на наборе программ на языке Си, представляющих собой реализации классических итерационных методов (Якоби, SOR, RedBlack) и метода Гаусса. Тем самым показана возможность применения динамического анализа для поиска зависимостей в программах, требующих распараллеливания.
6. Литература
1. ParaWise. The Computer Aided Parallelization Toolkit [HTML, PDF] (http://www.parallelsp.com).
2. Проект V-Ray [HTML] (http://parallel.ru/v-ray).
3. Jacobson T., Stubbendieck G. Dependency Analysis of FOR-Loop Structures for Automatic Parallelization of C Code [PDF] (http://www.css.edu/depts/cis/mics_2003/MICS2003_Papers/Jacobson.PDF).
4. Karkowski I., Corporaal H. Overcoming the Limitations of the Traditional Loop Parallelization // Journal of Future Generation Computer Systems. 1998. № 13. P. 407-416.
5. Petersen P.M. Evaluation of Programs and Parallelizing Compilers Using Dynamic Analysis Techniques. Champaign, IL, USA: University of Illinois at Urbana-Champaign, 1993. 164 p.