Формализованное проектирование эффективных многопоточных программ
Предложено совместное использование высокоуровневого инструментария алгеброалгоритмического проектирования, дополненного подсистемой переписывающих правил, а также низкоуровневых профилировщиков для автоматизации проектирования и повышения производительности последовательных и параллельных (многопот...
Saved in:
| Date: | 2007 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут програмних систем НАН України
2007
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/277 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Формализованное проектирование эффективных многопоточных программ / А.Е. Дорошенко, К.А. Жереб, Е.А. Яценко // Пробл. програмув. — 2007. — N 1. — С. 17-30. — Библиогр.: 10 назв. — рус. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860170005974351872 |
|---|---|
| author | Дорошенко, А.Е. Жереб, К.А. Яценко, Е.А. |
| author_facet | Дорошенко, А.Е. Жереб, К.А. Яценко, Е.А. |
| citation_txt | Формализованное проектирование эффективных многопоточных программ / А.Е. Дорошенко, К.А. Жереб, Е.А. Яценко // Пробл. програмув. — 2007. — N 1. — С. 17-30. — Библиогр.: 10 назв. — рус. |
| collection | DSpace DC |
| description | Предложено совместное использование высокоуровневого инструментария алгеброалгоритмического проектирования, дополненного подсистемой переписывающих правил, а также низкоуровневых профилировщиков для автоматизации проектирования и повышения производительности последовательных и параллельных (многопоточных) программ с общей памятью.
|
| first_indexed | 2025-12-07T17:57:37Z |
| format | Article |
| fulltext |
Паралельне програмування
© А.Е. Дорошенко, К.А. Жереб, Е.А. Яценко, 2007
ISSN 1727-4907. Проблеми програмування. 2007. № 1 17
УДК 681.3
А.Е. Дорошенко, К.А. Жереб, Е.А. Яценко
ФОРМАЛИЗОВАННОЕ ПРОЕКТИРОВАНИЕ
ЭФФЕКТИВНЫХ МНОГОПОТОЧНЫХ ПРОГРАММ
Предложено совместное использование высокоуровневого инструментария алгеброалгоритмического
проектирования, дополненного подсистемой переписывающих правил, а также низкоуровневых про-
филировщиков для автоматизации проектирования и повышения производительности последователь-
ных и параллельных (многопоточных) программ с общей памятью.
Введение
Острая необходимость в повыше-
нии производительности программного
обеспечения для решения трудоемких за-
дач, с одной стороны, и новые возможно-
сти распараллеливания вычислений, пре-
доставляемые многоядерными архитекту-
рами современных микропроцессоров − с
другой, побуждает к созданию специали-
зированного инструментария для разра-
ботки параллельных программ для таких
архитектур. Главным способом повыше-
ния производительности программ для та-
ких платформ является распараллеливание
программ с использованием многопоточ-
ности [1]. Проблема заключается не только
в необходимости создания инструментов
для проектирования новых программ, но
также в обеспечении возможности реин-
женерии существующего программного
обеспечения при его перенесении с уста-
ревших на новые многоядерные плат-
формы.
К известным инструментам, ориен-
тированным на облегчение оптимизации
параллельных программ с общей памятью,
относятся, например, Intel Thread Profiler
[2] и VTune [3] (последний предназначен
для оптимизации последовательных про-
грамм). Однако они оба являются доста-
точно низкоуровневыми средствами, кото-
рые так и не получили широкого распро-
странения, поскольку их использование
требует достаточно высокой квалификации
программиста и много ручной работы.
Контролируя работу приложения, эти про-
граммы фиксируют возникающие про-
блемы, и после анализа полученных ре-
зультатов тестирования программы, про-
граммист в итеративном режиме вручную
должен модифицировать код программы,
чтобы затем вновь анализировать ее вы-
полнение с помощью профилировщика.
Разработка эффективных программ
для многоядерных архитектур является
масштабной научно-технической пробле-
мой, успешное решение которой может
быть обеспечено только путем специали-
зации на предметные области и глубокого
охвата этапов жизненного цикла разраба-
тываемых программ с применением
средств автоматизации проектирования и
программирования, от написания первона-
чальных спецификаций до генерации вы-
полняемого кода. Основой для такой авто-
матизации является, прежде всего, высо-
коуровневая формализация конструирова-
ния многопоточных программ и автомати-
зация формальных трансформаций про-
грамм с целью оптимизации их производи-
тельности с применением профилировщи-
ков только как элемента более высокой
формализованной технологии разработки
многопоточных программ. Под оптимиза-
цией программ понимается достижение
требуемых качественных характеристик
программы по заданным критериям (па-
мять, быстродействие, загрузка оборудо-
вания и др.).
В Институте программных систем
НАН Украины разработан интегрирован-
ный инструментарий проектирования и
синтеза (далее «ИПС») программ [4], кото-
рый базируется на представлении алго-
ритмов в системах алгоритмических ал-
гебр (САА) В.М. Глушкова [5] и выпол-
няет синтез последовательных и парал-
лельных (многопоточных) программ на
языках программирования Java и C++ по
схемам алгоритмов. Для автоматизации
Паралельне програмування
18
выполнения трансформаций алгоритмов
(программ) предлагается интегрировать
алгеброалгоритмический инструментарий
«ИПС» с системой символьных вычисле-
ний (на основе парадигмы переписывания
термов) TermWare [6–8], которая расши-
ряет возможности создаваемого инстру-
ментального комплекса и позволит авто-
матизировать решение задач анализа и
обеспечения надежности программного
кода.
В данной работе описана методика
совместного использования вышеназван-
ных средств для формализованного проек-
тирования и трансформации на уровне
схем программ. На примере оптимизации
программы с применением профилиров-
щика Intel Thread Profiler для задачи нахо-
ждения простых чисел [9] продемонстри-
ровано использование метаправил для ав-
томатизации высокоуровневого проекти-
рования.
1. Формализованное
проектирование программ
в интегрированном
инструментарии
В разработанном интегрированном
инструментарии проектирование алгорит-
мов осуществляется с помощью дерева
конструирования в направлении сверху
вниз путем детализации конструкций
САА. По данному дереву автоматически
строятся три формы представления алго-
ритма – естественно-лингвистическая, ал-
гебраическая (регулярная схема) и графо-
вая (граф-схема). В работе [4] детально
рассмотрены алгебраическая и графовая
формы, а также архитектура и интерфейс
инструментария «ИПС». В данной работе
используется естественно-лингвистическая
форма (САА-схемы) алгоритмов, к пре-
имуществам использования которой отно-
сятся, в частности, возможность описания
алгоритмов в форме, удобной для чело-
века, что облегчает достижение требуе-
мого качества программ, а также ориента-
ция на описание весьма сложных алгорит-
мических процессов посредством их по-
уровневого проектирования.
Основными объектами языка САА-
схем (САА/1) [10], используемого в
«ИПС», являются абстракции операторов
(преобразователей данных) и условий
(предикатов). Операторы и условия могут
быть элементарными (базисными) или со-
ставными. Базисный оператор (условие) –
это оператор (условие), который в САА-
схеме считается первичной неделимой
(атомарной) абстракцией. Составные опе-
раторы (условия) строятся из элементар-
ных посредством операций последова-
тельного и параллельного выполнения
операторов:
• оператор1 ЗАТЕМ оператор2 –
последовательное выполнение операторов;
• ЕСЛИ условие ТО оператор1
ИНАЧЕ оператор2 КОНЕЦ ЕСЛИ – опера-
тор ветвления;
• ПОКА НЕ усло-
вие_окончания_цикла ЦИКЛ оператор
КОНЕЦ ЦИКЛА – оператор цикла;
• ПАРАЛЛЕЛЬНО((i) = (1),...,
(n))( оператор ) – асинхронное выполнение
n операторов (ветвей);
• ЖДАТЬ условие – синхрониза-
тор, выполняющий задержку вычислений
до момента, когда указанное условие (на-
зываемое условием синхронизации) станет
истинным;
• КТ условие – контрольная точ-
ка, выполняющая установку условия (ус-
ловия синхронизации) в истинное зна-
чение. Условия синхронизации, указанные
в контрольных точках и синхронизаторах,
связаны между собой;
• и других операций [5, 10].
Операторы и условия в САА-схемах
помечаются смысловыми идентификато-
рами. Идентификатор некоторого опера-
тора (соответственно условия) в САА-
схеме – это обрамленная кавычками (соот-
ветственно апострофами) последователь-
ность произвольной длины любых симво-
лов, за исключением кавычек (соответст-
венно апострофов). Уровни в САА-схемах
помечены левыми частями равенств, а
структура каждого уровня конкретизиро-
вана (в терминах САА) правой частью со-
ответствующего равенства. Левая часть ра-
венства отделяется от правой цепочкой
символов '='.
Пример 1. Далее приведена после-
довательная САА-схема алгоритма нахож-
Паралельне програмування
19
дения простых чисел (данный алгоритм
построен на основе метода, описанного в
[9]), сконструированная в инструментарии
«ИПС».
СХЕМА НАХОЖДЕНИЕ_ПРОСТЫХ_ЧИСЕЛ ====
"Схема последовательного алгоритма нахождения общего количества простых чисел от 1 до
100,000 путем проверки каждого нечетного числа (number), является ли оно нацело делимым на
меньшие нечетные факторы (factor)"
КОНЕЦ КОММЕНТАРИЯ
"ОпределениеГлобальныхДанных"
==== "Определить константу (MAX_NUMBERS) = (100000)";
"Определить массив (Primes) тип (long) размер (MAX_NUMBERS)";
"Определить переменную (PrimeCount) тип (long)"
"ОсновнойСоставнойОператор"
==== "(PrimeCount) := (1)"
ЗАТЕМ
"(Primes[PrimeCount]) := (2)"
ЗАТЕМ
"Вывести сообщение (Определение простых чисел от 1 до ) и значение (MAX_NUMBERS)"
ЗАТЕМ
"Поиск"
ЗАТЕМ
"Вывести сообщение (Найдено простых чисел: ) и значение (PrimeCount)"
"Поиск"
==== ЛОКАЛЬНЫЕ_ПЕРЕМЕННЫЕ
(
"Определить переменную (number) тип (long)";
"Определить переменную (start) тип (long)";
"Определить переменную (end) тип (long)";
"Определить переменную (stride) тип (long)";
"Определить переменную (factor) тип (long)"
)
ЗАТЕМ
"(start) := (1)"
ЗАТЕМ
"(end) := (MAX_NUMBERS)"
ЗАТЕМ
"(stride) := (2)"
ЗАТЕМ
ЕСЛИ '(start) = (1)'
ТО "(start) := (start) + (stride)"
КОНЕЦ ЕСЛИ
ЗАТЕМ
"(number) := (start)"
ЗАТЕМ
ПОКА НЕ '(number) >= (end)'
ЦИКЛ
"(factor) := (3)"
ЗАТЕМ
ПОКА НЕ 'Остаток от деления (number) на (factor) = (0)'
ЦИКЛ
"(factor) := (factor) + (2)"
КОНЕЦ ЦИКЛА
ЗАТЕМ
ЕСЛИ '(factor) = (number)'
ТО "(Primes[PrimeCount]) := (number)"
ЗАТЕМ
"(PrimeCount) := (PrimeCount) + (1)"
КОНЕЦ ЕСЛИ
ЗАТЕМ
"(number) := (number) + (stride)"
КОНЕЦ ЦИКЛА
КОНЕЦ СХЕМЫ НАХОЖДЕНИЕ_ПРОСТЫХ_ЧИСЕЛ
Паралельне програмування
20
Отметим, что по рассмотренной
схеме в инструментарии «ИПС» была сге-
нерирована программа на языке C++. Про-
цесс распараллеливания данного алго-
ритма приведен в подразделе 2.1 в каче-
стве примера оптимизации алгоритма для
выполнения на мультипроцессорной архи-
тектуре.
2. Оптимизация программ на
основе использования
инструментария «ИПС»,
TermWare и Intel Thread Profiler
Инструментарий «ИПС» может
быть дополнен средствами преобразования
схем последовательных и параллельных
алгоритмов, направленных на их улучше-
ние. Преобразование программ базируется
на метаправилах трансформации и пере-
ориентации [10], используемых в алгебрах
алгоритмов, а также применении системы
переписывания термов TermWare [7].
Метаправило трансформации со-
стоит в применении к схемам равенств ви-
да t1 = t2(x1, x2, ..., xs), где t1 и t2 – термы в
рассматриваемой алгебре алгоритмов, за-
висящие от переменных x1, x2, ..., xs. К ра-
венствам относятся тождества, квазитож-
дества и соотношения [10]. Тождества
представляют собой равенства, справедли-
вые при любых значениях переменных
x1, x2, ..., xs. Тождества в алгебре применя-
ются к формулам в направлении слева на-
право или наоборот, справа налево. Квази-
тождества – равенства, которые выполня-
ются лишь при некоторых интерпретациях,
входящих в них переменных. Соотноше-
ния характеризуют особенности выбран-
ной предметной области [10].
Переориентация алгоритма состоит
в последовательном применении к алго-
ритму метаправил свертки и развертки, и
базируется на использовании систем ра-
венств вида I = {v1 = T1, v2 = T2, …, vr = Tr},
где vi – операторные или предикатные пе-
ременные, Ti – термы в алгебре алгорит-
мов. Свертка алгоритма представляет со-
бой замену вхождений в схему непересе-
кающихся правых частей равенств Ti на
соответствующие левые части vi и направ-
лена на абстрагирование схемы. Развертка
алгоритма состоит в замене переменных vi
схемы на соответствующие термы Ti и
ориентирована на конкретизацию схемы.
Частным случаем переориентации явля-
ется переинтерпретация схемы – замена ее
базисных элементов (операторов и преди-
катов).
В инструментарии «ИПС» рассмот-
ренные равенства могут применяться в ав-
томатизированном режиме, для чего раз-
рабатывается библиотека равенств, меха-
низм их выбора и применения.
Далее приведен пример оптимизи-
рующего преобразования – трансформация
последовательного алгоритма в парал-
лельный (на примере задачи нахождения
простых чисел [9]), а также рассмотрена
оптимизация полученного параллельного
алгоритма (и соответствующей ему про-
граммы) с использованием алгеброалго-
ритмического аппарата и системы Intel
Thread Profiler и системы TermWare для
выполнения трансформаций схем.
2.1. Оптимизация 1.
Распараллеливание последова-
тельного алгоритма. Рассмотрим транс-
формацию последовательного алгоритма,
осуществляющего циклическую обработку
одномерной последовательности данных D
длиной n, в соответствующий параллель-
ный алгоритм с m параллельными ветвями
(m ≥ 1). Для параллельной обработки по-
следовательность D разделяется на m при-
близительно равных частей (блоков). Каж-
дая ветвь выполняет обработку блока дли-
ной b = n / m. Указанная трансформация
может быть представлена в САА-М в виде
следующего равенства:
Паралельне програмування
21
Здесь Searial(D), Parallel(D) – опе-
раторы, задающие соответственно страте-
гии последовательной и параллельной об-
работки; i, j, k – индексы; start, end – на-
чальные и конечные значения индексов i,
k; ОБРАБОТКА_ДАННЫХ(D, i) – опера-
тор, выполняющий обработку данных D в
соответствии со значением индекса i, а
также изменяющий значение индекса i в
соответствии с алгоритмом (приращение
или уменьшение значения индекса);
ВЕТВЬ(j) – оператор, реализующий j-ю
ветвь вычислений (j = 0, …, m – 1). Для
синхронизации ветвей в схеме использо-
ваны контрольная точка и синхронизатор
(см. раздел 1).
Для параллельных программ над
общей памятью важной является также
синхронизация параллельных ветвей, ка-
сающаяся защиты совместно используе-
мых ресурсов. В САА-М для синхрониза-
ции фрагмента алгоритма, осуществляю-
щего доступ к разделяемым ресурсам, дан-
ный фрагмент необходимо включить в
блок критической секции, т. е. применить
к схеме следующее равенство:
U = КритическаяСекция (cs) ( U ), (2)
где U – оператор, выполняющийся в па-
раллельной ветви и осуществляющий дос-
туп к разделяемым ресурсам; cs – иденти-
фикатор критической секции.
В некоторых языках программиро-
вания требуется также предварительная
инициализация критической секции. В
этом случае применяется следующее ра-
венство:
Serial(D) = Parallel(D), (1)
где
Serial(D) ::= "(i) := (start)"
ЗАТЕМ
ПОКА НЕ '(i) >= (end)'
ЦИКЛ
ОБРАБОТКА_ДАННЫХ(D, i)
КОНЕЦ ЦИКЛА;
(1.1)
Parallel(D) ::= ПАРАЛЛЕЛЬНО((j) = (0),..., (m–1))
(
ВЕТВЬ(j)
)
ЗАТЕМ
ЖДАТЬ 'Обработка во всех (m) ветвях закончена';
ВЕТВЬ(j) ::= “(start) := (j * b + 1)”
ЗАТЕМ
“(end) := (j * b + b)”
ЗАТЕМ
“(k) := (start)”
ЗАТЕМ
ПОКА НЕ '(k) >= (end)'
ЦИКЛ
ОБРАБОТКА_ДАННЫХ(D, k)
КОНЕЦ ЦИКЛА
ЗАТЕМ
КТ 'Обработка в ветви (j) закончена';
(1.2)
Паралельне програмування
22
V = ИнициализироватьКритиче-
скуюСекцию(cs) ЗАТЕМ V,
(3)
где V – оператор, перед которым необхо-
димо выполнить данную инициализацию.
Пример 2. На основе равенств (1) –
(3) был осуществлен переход от схемы
последовательного алгоритма определения
простых чисел (см. раздел 1, пример 1) к
соответствующей параллельной схеме. В
схему были внесены также и другие изме-
нения: 1) схема дополнена глобальными
константами и переменными
NUM_THREADS, BLOCKSIZE,
LONG_CACHE, factor, ThreadNums,
ThreadHandles, Primes_CS; 2) в функцию
Поиск введен параметр ThreadNum; 3) для
вызова функции Поиск(ThreadNum) из от-
дельной ветви используется промежуточ-
ная функция НайтиПростыеЧисла(Arg); 4)
введена локальная переменная space в
функцию Поиск(ThreadNum); 5) вместо
переменной factor введена замена текста
factor на space[2 * LONG_CACHE] в алго-
ритме; 6) необходимым образом изменены
значения переменных start и end в функции
Поиск(ThreadNum). Переменные
LONG_CACHE, space и промежуточная
функция НайтиПростыеЧисла(Arg) вво-
дятся в параллельной программе для ис-
ключения при выполнении программы
проблемы “64k aliasing” (более подробно
см. [2]).
Полученная в результате трансфор-
мации параллельная схема имеет следую-
щий вид:
СХЕМА НАХОЖДЕНИЕ_ПРОСТЫХ_ЧИСЕЛ/П ====
"Схема параллельного алгоритма нахождения простых чисел от 1 до 100,000"
КОНЕЦ КОММЕНТАРИЯ
"ОпределениеГлобальныхДанных"
==== "Определить константу (NUM_THREADS) = (4)";
"Определить константу (MAX_NUMBERS) = (100000)";
"Определить константу (BLOCKSIZE) = ((MAX_NUMBERS / NUM_THREADS))";
"Определить константу (LONG_CACHE) = (64 / sizeof(long))";
"Определить замену (factor) на (space[2 * LONG_CACHE])";
"Определить массив (ThreadNums) тип (long) размер (NUM_THREADS)";
"Определить массив (ThreadHandles) тип (HANDLE) размер (NUM_THREADS)";
"Определить массив (Primes) тип (long) размер (MAX_NUMBERS)";
"Определить переменную (PrimeCount) тип (long)";
"Определить критическ"ОсновнойСоставнойОператор"
==== "ИнициализироватьКритическуюСекцию(Primes_CS)"
ЗАТЕМ
"(PrimeCount) := (1)"
ЗАТЕМ
"(Primes[PrimeCount]) := (2)"
ЗАТЕМ
"Вывести сообщение (Определение простых чисел от 1 до ) и значение (MAX_NUMBERS)"
ЗАТЕМ
ПАРАЛЛЕЛЬНО((thread) = (0),..., (NUM_THREADS - 1))
(
"НайтиПростыеЧисла(thread)"
)
ЗАТЕМ
ЖДАТЬ 'Обработка во всех (NUM_THREADS) ветвях закончена'
ЗАТЕМ
"Вывести сообщение (Найдено простых чисел: ) и значение (PrimeCount)"
"НайтиПростыеЧисла(Arg)"
==== "Подготовить данные (ThreadNum) для вызова функции"
ЗАТЕМ
"Поиск(ThreadNum)"
Паралельне програмування
23
По приведенной параллельной схе-
ме алгоритма в инструментарии «ИПС»
была сгенерирована многопоточная про-
грамма на языке C++.
2.2. Оптимизация параллельной
программы. Для оптимизации параллель-
ных программ инструментарий «ИПС»
может совместно использоваться с систе-
мой Intel Thread Profiler. Thread Profiler,
контролируя работу многопоточного при-
ложения, фиксирует все возникающие
проблемы, включая рассинхронизацию по-
токов и накладные расходы на переключе-
ние между потоками. Полученные данные
отображаются в графическом виде, кото-
рый позволяет быстро идентифицировать
фрагменты исходных текстов, нуждаю-
щиеся в доработке. Далее в «ИПС» и
TermWare осуществляется автоматизиро-
ванное преобразование алгоритма, направ-
ленное на улучшение программы. После
чего синтезированная программа вновь
анализируется в Thread Profiler для про-
верки того, что проблема решена.
"Поиск(ThreadNum)"
==== ЛОКАЛЬНЫЕ_ПЕРЕМЕННЫЕ
(
"Определить переменную (number) тип (long)";
"Определить переменную (start) тип (long)";
"Определить переменную (end) тип (long)";
"Определить переменную (stride) тип (long)";
"Определить массив (space) тип (long) размер (4 * LONG_CACHE)"
)
ЗАТЕМ
"(start) := (ThreadNum * BLOCKSIZE + 1)"
ЗАТЕМ
"(end) := (ThreadNum * BLOCKSIZE + BLOCKSIZE)"
ЗАТЕМ
"(stride) := (2)"
ЗАТЕМ
ЕСЛИ '(start) = (1)'
ТО "(start) := (start) + (stride)"
КОНЕЦ ЕСЛИ
ЗАТЕМ
"(number) := (start)"
ЗАТЕМ
ПОКА НЕ '(number) >= (end)'
ЦИКЛ
"(factor) := (3)"
ЗАТЕМ
ПОКА НЕ 'Остаток от деления (number) на (factor) = (0)'
ЦИКЛ
"(factor) := (factor) + (2)"
КОНЕЦ ЦИКЛА
ЗАТЕМ
ЕСЛИ '(factor) = (number)'
ТО КритическаяСекция (cs)
(
"(Primes[PrimeCount]) := (number)"
ЗАТЕМ
"(PrimeCount) := (PrimeCount) + (1)"
)
КОНЕЦ ЕСЛИ
ЗАТЕМ
"(number) := (number) + (stride)"
КОНЕЦ ЦИКЛА
ЗАТЕМ
КТ 'Обработка в ветви (ThreadNum) закончена'
КОНЕЦ СХЕМЫ НАХОЖДЕНИЕ_ПРОСТЫХ_ЧИСЕЛ/П
Паралельне програмування
24
Оптимизация 2.1. Сбалансиро-
ванное распределение работы по пото-
кам. В выше-рассмотренной схеме парал-
лельного алгоритма большие числа тре-
буют больше времени для определения то-
го, являются ли они простыми [9], поэтому
последовательное разбиение области вы-
числений на части для обработки каждой
из параллельных ветвей приводит к неэф-
фективному использованию ресурсов про-
цессора. Выполнение данной программы
было проанализировано с помощью Thread
Profiler на ПК с ОС MS Windows XP, про-
цессор Intel Pentium 4 2.34 ГГц без под-
держки технологии Hyper-Threading. На
рис. 1, а показано окно Thread Profiler с
полученными Profile диаграммой (верхняя
половина окна) и временной диаграммой
(нижняя половина окна). На Profile диа-
грамме показаны итоговые данные о вре-
мени, потраченном потоками программы
на критическом пути. При этом результаты
сгруппированы по категории “уровень па-
раллелизма” (concurrency level), которая
обозначает количество одновременно вы-
полняющихся активных потоков (от 0 до
4). Временная диаграмма иллюстрирует
поведение программы с течением времени
и показывает вклад каждого потока в про-
грамму в целом. В Thread Profiler отобра-
жены различными оттенками монохромно-
го изображения последовательные участки
кода (Serial); превышение в данном при-
ложении количества потоков над количе-
ством процессоров в системе (Over
Utilized); время, требуемое для передачи
управления от одного потока к другому
(Overhead). На временной диаграмме от-
дельными оттенками показаны активные
потоки (Active), фазы ожидания потоков
(Wait), стрелками показаны разделения
(Fork) и слияния (Join) потоков.
Как видно из приведенной на
рис. 1, а временной диаграммы, с увеличе-
нием номера потока увеличивается время
его выполнения, т. е. загрузка потоков в
данной программе является несбалансиро-
ванной. С целью улучшения алгоритма
массив чисел разделяется таким образом,
чтобы блоки, обрабатываемые потоками,
были вложенными (перемежающимися).
При этом каждая из ветвей будет работать
как на малых, так и на больших числах.
Для указанной оптимизации алго-
ритма применим к нему метаправило пе-
реинтерпретации, использующее системы
равенств I1 и I2:
a
б
Рис. 1. Результаты анализа в Thread Profiler многопоточной программы определения простых
чисел: а – до оптимизации; б – после оптимизации
Паралельне програмування
25
I1 = { v1 = “(start) :=
=(ThreadNum * BLOCKSIZE + 1)”;
v2 = “(end) :=
= (ThreadNum * BLOCKSIZE +
+ BLOCKSIZE)”;
v3 = “(stride) := (2)”; };
I2 = { v1 = “(start) := (2 * ThreadNum + 1)”;
v2 = “(end) := (MAX_NUMBERS)”;
v3 = “(stride) := (2* NUM_THREADS)”; },
где v1, v2, v3 – операторные переменные.
Вначале к алгоритму применяются
равенства системы I1 в направлении справа
налево (базисные операторы заменяются
на переменные v1, v2, v3). Затем вместо ука-
занных переменных подставляются уже
другие базисные операторы путем приме-
нения равенств системы I2 слева направо.
В результате получаем оптимизированный
алгоритм, в котором работа по нахожде-
нию простых чисел равномерно распреде-
лена между потоками.
По данному алгоритму был выпол-
нен синтез программы в «ИПС», резуль-
таты анализа которой показаны на
рис. 1, б. На Profile диаграмме видно, что
большее время занимает одновременное
выполнение всех 4 потоков, а временная
диаграмма показывает улучшенный баланс
загрузки потоков по сравнению с преды-
дущим вариантом программы. Таким обра-
зом, увеличилась совокупная часть вре-
мени параллельного выполнения про-
граммы по отношению к последовательной
части. Тем не менее, данная программа все
еще требует улучшения – на Profile диа-
грамме изображены издержки при пере-
даче управления от одного потока к дру-
гому, которые становятся видны при уве-
личении масштаба диаграммы.
Оптимизация 2.2. Исключение
накладных расходов при передаче
управления от одной параллельной вет-
ви к другой. Рассматриваемая в данном
пункте трансформация ориентирована ис-
ключение временных издержек, связанных
со входом и выходом из критической сек-
ции в многопоточной программе. Транс-
формация связана с наличием в Win32 API
специализированного средства синхрони-
зации – группы особых функций, названия
которых начинаются с префикса
Interlocked. Суть их в том, что каждая из
них позволяет выполнить пару простых
операций (одну из арифметических (логи-
ческих) операций и операцию проверки
полученного значения), таким образом,
что они выполняются атомарно и их вы-
полнение не может быть прервано другим
потоком. Если критическая секция в про-
грамме содержит операции, которые могут
быть заменены соответствующими
Interlocked-функциями, то это позволит
улучшить выполнение приложения [9].
Указанное преобразование можно пред-
ставить следующим равенством в алгебре
алгоритмов:
КритическаяСекция (cs)
( АтомОп(x1, x2, …, xn) ) =
= БлокАтомОп(x1, x2, …, xn),
где АтомОп(x1, x2, …, xn) – арифметиче-
ская или логическая операция; БлокАто-
мОп(x1, x2, …, xn) – блокирующий аналог
указанной операции, представляемый в
языке программирования соответствую-
щей Interlocked-функцией.
Пример 3. Необходимо исключить
критическую секцию в следующем фраг-
менте алгоритма определения простых чи-
сел (см. пример 2):
КритическаяСекция (cs)
(
"(Primes[PrimeCount]) := (number)"
ЗАТЕМ
"(PrimeCount) := (PrimeCount) + (1)"
)
Шаг 1. Приведение композиции
двух операторов к одному оператору. За-
меняем второй базисный оператор на
“ИНК(PrimeCount)” (применяем метапра-
вило переинтерпретации). Затем подстав-
ляем базисный оператор
“ИНК(PrimeCount)” вместо PrimeCount в
Primes[PrimeCount] (при этом предполага-
ется, что значение выражения
ИНК(PrimeCount) является значением
PrimeCount до того, как применено прира-
щение):
Паралельне програмування
26
КритическаяСекция (cs)
(
"(Primes[ИНК(PrimeCount)]) := (number)"
)
Шаг 2. Заменяем операцию прира-
щения ИНК на соответствующую блоки-
рующую операцию и исключаем критиче-
скую секцию:
"(Primes[БЛОК_ИНК(PrimeCount)]) :=
= (number)"
По оптимизированному таким обра-
зом алгоритму в «ИПС» была сгенериро-
вана программа, выполнение которой было
проанализировано в Thread Profiler. По
сравнению с предыдущими результатами
(см. рис. 1, б), накладные расходы на пере-
дачу управления между потоками исклю-
чены в столбцах Profile диаграммы, отме-
ченных CL:2 и CL:3.
2.3. Использование системы
TermWare для трансформации алго-
ритмов. Для применения равенств к схе-
мам алгоритмов «ИПС» может приме-
няться совместно с системой символьных
вычислений TermWare [6–8]. Система
TermWare – открытая структура переза-
писи термов, которая состоит из двух глав-
ных частей:
1) библиотеки Java, содержащей ос-
новные структуры данных и алгоритмы
для перезаписи термов, правила переза-
писи термов, унификации, стратегии пере-
записи и пр.;
2) структуры Java, содержащей
средства добавления синтаксических ана-
лизаторов, языков программирования и
правил перезаписи с действиями, которые
могут быть введены в прикладные про-
граммы Java и могут быть расширены че-
рез структуру Java.
Главное отличие TermWare от
обычных систем перезаписи термов со-
стоит в том, что эта система перезаписи
термов – не „замкнутая” формальная сис-
тема в том смысле, что она не предназна-
чена для обеспечения полной среды про-
граммирования, и не объединена в пакет
как интерпретатор или транслятор, а пред-
ставляется как библиотека, встраиваемая в
программное приложение.
Для разработчика система термов
выглядит как совокупность экземпляров
класса ITermSystem, с возможностью
управления набором правил и редуциро-
вания термов [8]. База фактов также мо-
жет содержать императивные элементы,
описанные как Java классы. Таким обра-
зом, имеется возможность использовать
декларативную модель программирования
в программных комплексах, основанных
на Java-платформе в тех случаях, когда это
необходимо. Разработчик может исполь-
зовать термальную систему как про-
граммный агент, встраиваемый в общую
инфраструктуру программной системы.
Сами наборы правил описаны на
языке TermWare и хранятся в отдельных
файлах. Основой языка являются термы,
т.е. выражения вида f(x1, ..., xn). В каче-
стве атомарных термов используются
переменные (которые записываются в
виде $identifier), а также константы оп-
ределенных типов данных (числовых,
логических, строковых и атомарного –
неизменяемые строки). Для упрощения
записи и восприятия используются со-
кращения для многих термов, например,
х+у – для plus(x, y); x ? у: z – для
ifelse(x, y, z) и др. Весь набор правил яв-
ляется термом, записанным с использова-
нием этих сокращений. Набор правил со-
держит сами правила, а также дополни-
тельную информацию (название сис-
темы правил, используемая база фактов,
применяемая стратегия). Типичное пра-
вило в TermWare записывается следую-
щим образом:
source [condition] → destination [action].
Здесь используются четыре терма:
source – входной образец; destination –
выходной образец; condition – условие,
определяющее применимость правила;
action – действие, выполняемое при сра-
батывании правила. Выполняемые дейст-
вия и проверяемые условия в основном
являются вызовами методов в БД фактов.
Таким образом, осуществляется связь
между правилами на языке TermWare и
кодом на Java. Кроме того, возможно на-
писание собственной стратегии, опреде-
ляющей порядок применения правил.
Паралельне програмування
27
В результате интеграции системы
TermWare и разработанного инструмента-
рия проектирования и синтеза программ, в
TermWare может передаваться дерево ал-
горитма, подлежащего трансформации и
требуемые для этого равенства. После вы-
полненного в TermWare преобразования
алгоритма, его дерево будет передано об-
ратно в «ИПС». Далее по оптимизирован-
ному алгоритму может быть произведена
генерация соответствующей программы на
языке программирования.
Пример 4 (трансформация после-
довательного алгоритма в параллельный с
использованием TermWare). Вышеприве-
денная трансформация последовательного
алгоритма в параллельный может быть ав-
томатизирована с использованием
TermWare. Исходная схема последова-
тельного алгоритма записывается в виде
терма:
Root(
Globals(
THEN(
Constant(MAX_NUMBERS,100000),
THEN(
Array(Primes,long,MAX_NUMBERS), Variable(PrimeCount,long)))),
Main(
THEN(
Assignment(PrimeCount,1),
THEN(
Assignment( ArrayElement(Primes,PrimeCount),2),
THEN(Print,
THEN(
CALL(Search),
THEN(Print,
END(Main))))))),
Search(
THEN(
LocalVariables(
THEN(
Variable(number,long),
THEN(
Variable(start,long),
THEN(
Variable(end,long),
THEN(
Variable(stride,long),
Variable(factor,long)))))),
THEN(
Assignment(start,1),
THEN(
Assignment(end,MAX_NUMBERS),
THEN(
Assignment(stride,2),
THEN(
IF(
eq(start,1),
Assignment(start, plus(start,stride))),
THEN(
Assignment(number,start),
THEN(
UNTIL(
greater_eq(number,end),
THEN(
Assignment(factor,3),
THEN(
UNTIL(
eq(
mod(number,factor),0),
Assignment(factor, plus(factor,2))),
THEN(
IF(
eq(factor,number),
THEN(
Assignment( ArrayElement(Primes,PrimeCount),number),
Assignment(PrimeCount, plus(PrimeCount,1)))),
Assignment(number, plus(number,stride)))))),
END(Search))))))))))
Паралельне програмування
28
Этот терм соответствует схеме
последовательного алгоритма из примера
1. (Поскольку язык TermWare не позволяет
использовать русскоязычные обозначения
термов, названия элементов схемы
заменены на соответствующие англо-
язычные). Отдельные уровни схемы
("ОпределениеГлобальныхДанных",
"ОсновнойСоставнойОператор", "Поиск")
представлены в виде подтермов терма Root
(Globals, Main, Search). Для записи
арифметических действий использованы
стандартные термы системы TermWare,
что позволяет вводить базисные
операторы и условия в естественном
виде. Например, выражение ThreadNum
* BLOCKSIZE + 1 автоматически
трансформируется в терм
plus(multiply(ThreadNum,BLOCKSIZE),1).
В качестве примера записи правил
рассмотрим первый этап трансформации
(распараллеливание циклов, без устране-
ния проблемы “64k aliasing”). При этом
применяется следующая совокупность
правил:
Первое правило добавляет необхо-
димые глобальные определения (см. при-
мер 2). Правило 2 реализует равенство (3)
– инициализация критической секции.
Правила 3, 5, 6, 8 реализуют основное ра-
венство (1) – асинхронное выполнение
ветвей (правило 3), модификацию началь-
ного и конечного значений для каждой
ветви (правила 5–6) и добавление кон-
трольной точки в конце каждой ветви
(правило 8). Правило 4 добавляет в функ-
ции Поиск параметр ThreadNum (см. при-
мер 2). Правило 7 реализует равенство (2)
– добавление критической секции.
Как видно из этого примера, по ка-
ждому равенству САА можно построить
соответствующее правило (или набор пра-
вил) TermWare, что позволяет автоматизи-
ровать применение равенств.
Ввиду ограниченности объема ра-
боты другие правила трансформации не
приводятся.
Заключение
В работе рассмотрены средства
формализованного проектирования и
трансформации последовательных и
параллельных алгоритмов, базирующиеся
на модифицированных САА. Алгоритмы
представлены в естественно-лингвисти-
ческой форме – в языке САА/1, осо-
1. Globals(THEN(Constant(MAX_NUMBERS,100000),$0))->
Globals(THEN(THEN(Constant(MAX_NUMBERS,100000),$0),
THEN(Constant(NUM_THREADS,4),
THEN(Constant( BLOCKSIZE,divide(MAX_NUMBERS,NUM_THREADS)),
CriticalSection(Primes_CS)))))
2. Main(THEN(Assignment(PrimeCount,1),$0)) ->
Main(THEN(InitCriticalSection(Primes_CS),THEN(Assignment(PrimeCount,1),$0)))
3. CALL(Search) -> THEN(PARALLEL(Parameter(thread,0,minus(NUM_THREADS,1)),
CALL(Search,Parameters(thread))), WAIT(ProcessedAll(NUM_THREADS)))
4. Search($0) -> Search(Parameters(ThreadNum),$0)
5. Assignment(start,1) -> Assignment(start,plus(multiply(ThreadNum,BLOCKSIZE),1))
6. Assignment(end,MAX_NUMBERS) ->
Assignment(end,plus(multiply(ThreadNum,BLOCKSIZE),BLOCKSIZE))
7. IF($0,THEN(Assignment(ArrayElement(Primes,PrimeCount),number),
Assignment(PrimeCount,plus(PrimeCount,1)))) ->
IF($0,CriticalSection(THEN(Assignment(ArrayElement(Primes,PrimeCount),number),
Assignment(PrimeCount,plus( PrimeCount,1)))))
8. THEN(UNTIL($0,$1),END(Search)) ->
THEN(UNTIL($0,$1),THEN(ControlPoint(ThreadComplete),END(Search)))
Паралельне програмування
29
бенностями которого являются простота в
обучении и использовании, а также неза-
висимость от языка программирования и
возможность автоматизированного перево-
да в произвольный язык для обеспечения
адекватности алгоритмов и ассоции-
рованных с ними программ. Оптимизация
алгоритмов базируется на аппарате специ-
альных равенств, –тождеств и соотно-
шений, развитом в алгебрах алгоритмов. В
работе показано, как для автоматизации
применения таких равенств к схемам
может быть применена система символь-
ных вычислений TermWare, преимущес-
твом использования которой является ее
открытость. Кроме того, в процессе
оптимизации программ использована
система Thread Profiler, позволяющая
идентифицировать фрагменты исходных
текстов, нуждающиеся в доработке.
К перспективам развития разра-
ботанных инструментальных средств в
рамках создания эффективных много-
поточных программ следует отнести сле-
дующие:
• перенесение инструментария
«ИПС» и TermWare на платформу MS .Net;
• дополнение существующего ин-
струментария «ИПС» автоматизирован-
ными средствами оценки сложности про-
ектируемых алгоритмов;
• создание базы данных представ-
ленных в алгеброалгоритмическом виде
типичных шаблонов проектирования и оп-
тимизирующих преобразований последо-
вательных и параллельных алгоритмов и
программ (включая использование Intel
Thread Profiler и VTune) для их автомати-
зированного использования (на примере
конкретной предметной области алгорит-
мов сортировки);
• создание на основе технологии
переписывающих правил настраиваемых
стратегий совместного использования
средств «ИПС», TermWare и Intel Thread
Profiler, позволяющих быстро идентифи-
цировать фрагменты программного кода,
критичные с точки зрения производитель-
ности, а также выбирать и применять опти-
мизирующие преобразования программ (на
примере указанной предметной области).
1. Г. Эндрюс. Основы многопоточного, па-
раллельного и распределенного про-
граммирования. – М.: ИД ”Вильямс”, 2003.
– 505 с.
2. Intel Thread Profiler 3.0 for Windows. –
http://www.intel.com/cd/software/products/
asmo-na/eng/threading/286749.htm
3. Intel® VTune™ Performance Analyzers – In-
tel® Software Network
http://www.intel.com/cd/software/products/
asmo-na/eng/vtune/239144.htm
4. Яценко Е.А., Мохница А.С. Инструменталь-
ные средства конструирования синтакси-
чески правильных параллельных алгорит-
мов и программ // Проблемы программи-
рования. – 2004. – № 2–3. – С. 444–450.
5. Дорошенко А.Ю., Фінін Г.С., Цейтлін Г.О.
Алгеброалгоритмічні основи програму-
вання. Об’єктна орієнтація і паралелізм. –
К.: Наук. думка, 2004. – 458 c.
6. Doroshenko A., Shevchenko R. A Rewriting
Framework for Rule-Based Programming Dy-
namic Applications, Fundamenta Infor-
maticae, 2006. – Vol. 72, N1–3. – P. 95–108.
7. TermWare. –
http://www.gradsoft.com.ua/products/term-
ware_rus.html
8. Дорошенко А.Е., Шевченко Р.С. Система
символьных вычислений для программи-
рования динамических приложений // Про-
блемы программирования. – 2005. – № 4. –
С. 718–727.
9. Intel Thread Profiler for Windows. Getting
Started Guide. – 2006.
10. Цейтлин Г.Е. Введение в алгоритмику. −
Киев: Сфера, 1998. − 310 с.
Получено 15.01.2007
Об авторах:
Дорошенко Анатолий Ефимович,
доктор физ.-мат. наук, профессор,
заведующий отделом теории компью-
терных вычислений,
Яценко Елена Анатольевна,
кандидат физ.-мат. наук,
научный сотрудник,
Жереб Константин Анатольевич,
аспирант физико-технического учебно-
научного центра НАН Украины.
Паралельне програмування
30
Место работы авторов:
Институт программных систем
НАН Украины,
проспект Академика Глушкова, 40.
03680, Киев-187, Украина.
тел. (044) 526 1538,
e-mail: dor@isofts.kiev.ua, aiyat@i.com.ua
Физико-технический учебно-научный
центр НАН Украины,
бульвар Вернадского, 36.
03142, Киев-142, Украина.
тел. (044) 424 3025,
e-mail: zhereb@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-277 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-07T17:57:37Z |
| publishDate | 2007 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Дорошенко, А.Е. Жереб, К.А. Яценко, Е.А. 2008-02-22T17:20:48Z 2008-02-22T17:20:48Z 2007 Формализованное проектирование эффективных многопоточных программ / А.Е. Дорошенко, К.А. Жереб, Е.А. Яценко // Пробл. програмув. — 2007. — N 1. — С. 17-30. — Библиогр.: 10 назв. — рус. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/277 681.3 Предложено совместное использование высокоуровневого инструментария алгеброалгоритмического проектирования, дополненного подсистемой переписывающих правил, а также низкоуровневых профилировщиков для автоматизации проектирования и повышения производительности последовательных и параллельных (многопоточных) программ с общей памятью. ru Інститут програмних систем НАН України Паралельне програмування Формализованное проектирование эффективных многопоточных программ Article published earlier |
| spellingShingle | Формализованное проектирование эффективных многопоточных программ Дорошенко, А.Е. Жереб, К.А. Яценко, Е.А. Паралельне програмування |
| title | Формализованное проектирование эффективных многопоточных программ |
| title_full | Формализованное проектирование эффективных многопоточных программ |
| title_fullStr | Формализованное проектирование эффективных многопоточных программ |
| title_full_unstemmed | Формализованное проектирование эффективных многопоточных программ |
| title_short | Формализованное проектирование эффективных многопоточных программ |
| title_sort | формализованное проектирование эффективных многопоточных программ |
| topic | Паралельне програмування |
| topic_facet | Паралельне програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/277 |
| work_keys_str_mv | AT dorošenkoae formalizovannoeproektirovanieéffektivnyhmnogopotočnyhprogramm AT žerebka formalizovannoeproektirovanieéffektivnyhmnogopotočnyhprogramm AT âcenkoea formalizovannoeproektirovanieéffektivnyhmnogopotočnyhprogramm |