Алгоритм разбиения программы на нити
Разбиение на нити
Маскирующие преобразования программ
Анализ маскирующих преобразований
Новый метод маскировки программ
Автоматическое выявление уязвимостей защиты программ
Виды уязвимостей защиты
Инструментальные средства для обнаружения уязвимостей защиты
Интегрированная среда
Навигация
Разбиение на нити
О некоторых задачах анализа и трансформации программ
74118
знаков
11
таблиц
4
изображения
2.1.3. Разбиение на нити
На этом шаге производится собственно разбиение графа зависимостей по данным на нити. Количество нитей является параметром алгоритма. Так как целью разбиения является получение выигрыша по времени, возникающего из-за увеличения количества событий локальности в каждой нити, то необходимо привязать каждую нить к одному конкретному процессору или, точнее, к конкретному кэшу. Поэтому количество нитей, на которые производится разбиение, обычно равно количеству процессоров в системе.
Алгоритм разбиения состоит в итерировании списка узлов графа, еще не назначенных конкретной нити, и определения нити для какого-либо из узлов (группы таких алгоритмов обычно называются list scheduling). На каждом шаге такой алгоритм делает локально оптимальный выбор. Это значит, что при выборе очередного узла из списка делается попытка присвоить его каждой из имеющихся нитей, после чего выбирается лучшая.
Для того, чтобы иметь возможность оценивать варианты присвоения узла нити, необходимо ввести некоторую оценочную функцию. В нашем случае такая функция содержит время выполнения нити, а также среднеквадратичное отклонение времен выполнения всех нитей. Это следует из того соображения, что в оптимальном разбиении времена выполнения нитей должны быть достаточно близки друг к другу. Возможно включение и других параметров.
При включении узла в какую-либо нить необходимо провести пересчет вре-мени выполнения этой нити. Алгоритм пересчета состоит из следующих шагов:
Учет времени, необходимого на синхронизацию с другими нитями, если она требуется.
Учет возникающих событий локальности.
Рассмотрим более подробно каждый из этих шагов.
2.1.3.1. Учет времени на синхронизацию
Обрабатываемый на текущем этапе узел может зависеть по данным от некоторых других. В этом случае необходимо дождаться выполнения каждой нити, которые содержит такие узлы. Порядок обхода узлов в списке должен быть таков, чтобы гарантировалось, что все такие узлы уже были распределены на нити. Для этого можно обходить узлы в естественном порядке, то есть так, как они расположены в последовательной программе, либо выполнить тополо-гическую сортировку графа зависимостей по данным. Еще раз подчеркнем, что иерархичность графа обеспечивает то, что он является ациклическим.
Таким образом, к моменту обработки некоторого узла все узлы, от которых он зависит по данным, уже распределены на нити. Если какие-либо из таких узлов находятся в других нитях, то перед выполнением текущего узла необходимо провести синхронизацию со всеми такими нитями. Для того, чтобы осуществить такую синхронизацию, нужно завести по одной общей переменной для каждой нити. Присваивание значения i такой переменной для некоторой нити j означает, что эта нить выполнила узел i. Нить, ждущая результатов вычисления узла i, должна ждать, пока соответствующая общая переменная не примет нужного значения. Пример такой синхронизации показан на Рис. 2.
Времена выполнения каждой из нитей, проводящих синхронизацию, должны быть увеличены соответствующим образом. Нить, пишущая в общую переменную о результатах выполнения узла, дополнительно работает время t1. Нить, ждущая данных от нескольких узлов, ожидает последний из выполняющихся узлов, после чего тратит время t2. Эти времена являются параметрами алгоритма.
Рис. 2. Пример синзронизации
Для учета событий локальности для каждой нити необходимо эмулировать кэш процессора, на котором она выполняется. При распределении текущего узла на какую-либо нить необходимо проверить все переменные, которые читаются либо пишутся узлом, на попадание в кэш. Если попадание произошло, то время выполнения узла должно быть уменьшено на интервал времени t3, также являющийся параметром алгоритма.
Рис. 3. Пример эмулирования кэша
Для учета событий как временной, так и пространственной локальности необходимо моделирование линий кэша, т.е. помещение в кэш не одной переменной, а некоторого блока памяти, окружающего нужную переменную. Моделирование различных типов кэшей приведет к разным результатам при разделении на нити.
Пример моделирования событий локальности изображен на Рис. 3.
2.2. Экспериментальные результаты
Мы применили нашу реализацию алгоритма к тестовой функции, решающей алгебраическое уравнение четвертой степени x4+ax3+bx2+cx+d=0.
Функция не содержит циклов и не может быть распараллелена традиционными способами. Полученная многопоточная версия функции была реализована с помощью библиотеки pthread под операционной системой Linux. Экспериментальные запуски были проведены на четырехпроцессорном Intel Itanium, на которых установлена ОС RedHat Linux 7; использовались компиляторы GCC 3.3.1 и ICC 8.00b. Программа запускалась 100 раз, время ее выполнения измерялось с помощью высокоточных аппаратных счетчиков. Вычислялось среднее значение времени выполнения μ и среднеквадратичное отклонение σ. Все значения времени выполнения, не укладывающиеся в промежуток [μ-2σ,μ+2σ] удалялись из выборки, после чего среднее значение пересчитывалось. Эта величина использовалась для подсчета ускорения. Результаты эксперимента приведены на Рис. 4.
Рис. 4. Ускорение, достигнутое на Itanium
Похожие работы
... из-за динамической подзагрузки программы из файловой системы) и отлаживать его производительность по той же методике, которая была описана выше применительно к программе целиком. 5. Средство анализа эффективности MPI программ 5.1 Постановка задачи В системе DVM существуют развитые средства анализа эффективности выполнения параллельной DVM-программы. Эти средства являются более мощными, ...
... . Замена привлекает внимание созвучием исходного и заменяющего компонентов. Заголовок - это способ дать читателю возможность с первого взгляда сориентироваться, нужно ли читать остальной текст. Трансформация фразеологизма обусловлена стремлением авторов усилить экспрессивную окраску заголовка. Мы выяснили, что такое изменение фразеологизмов служит «противоядием» от речевых штампов. Преобразуя ...
... , причем вполне сознательно. Ведь доктринерский либерализм априори исходит из того, что индивидуумы всегда эффективнее потратят денежные средства, чем "бюрократическое" государство. 4 Что впереди? трансформация рыночная экономика Следует надеяться, и президент, и правительство нашей страны хорошо понимают, что она фактически стоит перед дилеммой: остаться и впредь экспортером преимущественно ...
... же важны при экономико-географическом анализе. По всем этим показателям существуют весьма ощутимые различия между тремя группами стран. Характеристики трансформаций социально-экономических систем в КНР и Венгрии 2.1 Трансформации социально-экономической системы КНР 2.1.1 Предыстория и цели трансформации Социально-экономические сдвиги в Китае 1918-1927 гг. Завершение Национальной ...
0 комментариев