Об оценке сложности и координации вычислений в многопоточных программах
Предложен метод оценки вычислительной сложности алгоритмов на основе алгебраического подхода. Разработана методика применения системы переписывания правил для преобразования конструкций координации вычислений в многопоточных программах. Приведены примеры трансформаций параллельных программ и результ...
Saved in:
| Date: | 2007 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут програмних систем НАН України
2007
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/286 |
| 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 2. — С. 41-55. — Библиогр.: 15 назв. — рус. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859907736259526656 |
|---|---|
| author | Дорошенко, А.Ю. Жереб, К.А. Яценко, Е.А. |
| author_facet | Дорошенко, А.Ю. Жереб, К.А. Яценко, Е.А. |
| citation_txt | Об оценке сложности и координации вычислений в многопоточных программах / А.Е. Дорошенко, К.А. Жереб, Е.А. Яценко // Пробл. програмув. — 2007. — N 2. — С. 41-55. — Библиогр.: 15 назв. — рус. |
| collection | DSpace DC |
| description | Предложен метод оценки вычислительной сложности алгоритмов на основе алгебраического подхода. Разработана методика применения системы переписывания правил для преобразования конструкций координации вычислений в многопоточных программах. Приведены примеры трансформаций параллельных программ и результаты их выполнения на многоядерной архитектуре.
|
| first_indexed | 2025-12-07T16:00:48Z |
| format | Article |
| fulltext |
Паралельне програмування
© А.Е. Дорошенко, К.А. Жереб, Е.А. Яценко, 2007
ISSN 1727-4907. Проблеми програмування. 2007. № 2 41
УДК 681.3
А.Е. Дорошенко, К.А. Жереб, Е.А. Яценко
ОБ ОЦЕНКЕ СЛОЖНОСТИ И КООРДИНАЦИИ
ВЫЧИСЛЕНИЙ В МНОГОПОТОЧНЫХ ПРОГРАММАХ
Предложен метод оценки вычислительной сложности алгоритмов на основе алгебраического подхода.
Разработана методика применения системы переписывания правил для преобразования конструкций
координации вычислений в многопоточных программах. Приведены примеры трансформаций парал-
лельных программ и результаты их выполнения на многоядерной архитектуре.
Введение
В работе [1] авторами было рас-
смотрено совместное использование раз-
работанных алгеброалгоритмического ин-
струментария проектирования и синтеза
программ («ИПС») и системы переписы-
вания правил TermWare для автоматизации
трансформации многопоточных программ
с общей памятью. Инструментарий «ИПС»
базируется на диалоговом конструирова-
нии схем алгоритмов в системах алгорит-
мических алгебр (САА) и допускает синтез
последовательных и параллельных про-
грамм в различных, в том числе, объектно-
ориентированных языках программирова-
ния (Java, C++ и др.).
В данной работе предложен метод
оценки сложности последовательных и па-
раллельных алгоритмов, представленных
САА-схемами. Разработана также мето-
дика применения TermWare для преобра-
зования конструкций координации вычис-
лений в многопоточных программах для
многоядерных архитектур [2]. Координа-
ционный аспект параллельных вычисле-
ний, как известно [3], отражает свойства
средств синхронизации и обменов между
процессорами, которые могут существенно
влиять на производительность параллель-
ной системы. К средствам координации
относятся классические средства (сема-
форы, критические секции, мониторы) и
более сложные (конвейеры, архитектура
клиент-сервер и др.), а также правила ко-
ординации, которые устанавливают зави-
симости между координируемыми объек-
тами (потоками или процессами) и сред-
ства реализации таких зависимостей. Пра-
вила также описывают переход от одних
средств координации объектов к другим,
более эффективным по тем или иным кри-
териям. Автоматизированное применение
таких правил к алгоритму или программе
позволяет осуществлять система символь-
ных вычислений TermWare. При этом для
проектирования программы на более вы-
соком уровне представления (например, в
естественно-лингвистическом или граф-
схемном виде [4]), применяется инстру-
ментарий «ИПС». Помимо стандартных
средств синхронизации, реализованных в
языках программирования, могут также
использоваться специализированные сред-
ства, разработанные вручную, позволяю-
щие повысить эффективность многопо-
точных программ. Отметим, что с задачей
разработки эффективных алгоритмов не-
посредственно связана задача оценки их
сложности.
Материал работы подчинен сле-
дующей структуре. В разделе 1 предложен
метод получения оценок сложности для
САА-схем алгоритмов. В разделе 2 рас-
сматривается методика применения сис-
темы TermWare совместно с «ИПС» для
разработки многопоточных программ. В
разделе 3 использование данной системы
проиллюстрировано на задаче определения
простых чисел (Primes), анализ которой
начат в [1], и программе моделирования
броуновского движения (Brown), которая
может быть отнесена к классу программ с
интенсивной синхронизацией. Приведены
результаты экспериментов по выполнению
различных вариантов данных программ на
многоядерной платформе.
Паралельне програмування
42
1. Оценка вычислительной сложности
схем алгоритмов
При анализе сложности алгоритма
обычно осуществляется оценка порядка
роста необходимых для решения задачи
времени и емкости памяти при увеличении
размера n входных данных. Напомним [5],
что под временной сложностью T(n) алго-
ритма понимается время, затрачиваемое
алгоритмом, как функция размера задачи
n. Поведение этой сложности в пределе
при увеличении размера задачи называется
асимптотической временной сложностью.
Аналогично можно определить емкостную
сложность (емкость памяти, требуемую
для решения задачи как функцию размера
задачи) и асимптотическую емкостную
сложность. Отметим, что именно асимпто-
тическая сложность алгоритма определяет
в итоге размер задач, которые можно ре-
шить этим алгоритмом. Для описания
асимптотической скорости роста функций
используется O-символика. Далее приве-
дены основные правила для определения
асимптотической сложности [6]:
)),(())(*( nfOnfkO =
где k ≠ 0 – константа;
))((*))(())(*)(( ngOnfOngnfO = или
))((/))(())(/)(( ngOnfOngnfO = ;
}).)(,)((max{))(())(( ngnfOngOnfO =+
Алгоритмы по их асимптотической
вычислительной сложности могут быть
классифицированы следующим образом:
• )1(O – постоянные. Cложность
таких алгоритмов не зависит от n (пример:
проверка числа на четность или нечет-
ность);
• )(nO – линейные (например, ал-
горитм нахождения элемента в неотсорти-
рованном списке);
• )(log nO – логарифмические.
Эта сложность встречается обычно в алго-
ритмах, которые разделяют задачу на под-
задачи и решают их по отдельности (на-
пример, бинарный поиск);
• )log( nnO – квазилинейные. Та-
кая сложность характерна для алгоритмов,
которые разделяют задачу на подзадачи, а
затем, решив их, соединяют полученные
решения (сортировка методом Шелла, сор-
тировка слиянием);
• )( cnO – полиномиальные, где
1>c – константа. Примеры: )( 2nO – квад-
ратичная сложность (некоторые алго-
ритмы сортировки); )( 3nO – кубическая
сложность;
• )( ncO – экспоненциальные
( 1>c ); )!(nO – факториальные. Такие
алгоритмы чаще всего возникают в резуль-
тате подхода, известного как “метод гру-
бой силы” (например, полный перебор со-
четаний элементов).
Временная сложность алгоритма
может быть вычислена исходя из анализа
его управляющих структур (таблица). В
таблице конструкции алгоритма представ-
лены в САА [3]; O(условие) и O(оператор)
обозначают соответственно асимптотиче-
скую сложность для некоторого условия и
оператора.
Определение сложности алгоритма
в основном сводится к анализу циклов и
рекурсивных вызовов. В общем случае
существуют два способа анализа сложно-
сти алгоритма: восходящий (от внутрен-
них управляющих структур к внешним) и
нисходящий (от внешних к внутренним)
[6]. Для оценки сложности параллельных
алгоритмов предлагается вычислять общее
количество операций, выполняемых в наи-
более трудоемкой ветви.
Пример 1. Рассмотрим схему алго-
ритма:
"(i) := (1)"
ЗАТЕМ
ПОКА НЕ '(i) > (n)'
ЦИКЛ
…
ЗАТЕМ
"(i) := (i) + (1)"
КОНЕЦ ЦИКЛА
Паралельне програмування
43
При условии, что сложность тела
цикла – O(1), сложность данного алго-
ритма будет O(n).
Если один цикл вложен в другой и
оба цикла зависят от размера одной и той
же переменной (n), то вся конструкция ха-
рактеризуется квадратичной сложно-
стью )( 2nO :
"(i) := (1)"
ЗАТЕМ
ПОКА НЕ '(i) > (n)'
ЦИКЛ
…
"(j) := (1)"
ЗАТЕМ
ПОКА НЕ '(j) > (n)'
ЦИКЛ
…
"(j) := (j) + (1)"
КОНЕЦ ЦИКЛА
...
"(i) := (i) + (1)"
КОНЕЦ ЦИКЛА
При оценке сложности программ
обычно рассматривается средний случай –
ожидаемое время работы программы на
“типичных” входных данных, и худший
случай – ожидаемое время работы про-
граммы на самых “плохих” входных дан-
ных. Лучший, средний и худший случаи
играют значительную роль в задачах сор-
тировки [7].
Анализ асимптотической сложности
получил широкое распространение во
многих практических приложениях. Тем
не менее, к основным недостаткам данного
подхода можно отнести следующие [6]:
1) для сложных алгоритмов
получение O-оценок, как правило, либо
очень трудоемко, либо практически невоз-
можно;
2) часто трудно определить слож-
ность “в среднем”;
3) O-оценки являются достаточно
грубыми для отображения более тонких
отличий алгоритмов;
4) O-анализ дает слишком мало
информации (или вовсе ее не дает) для
анализа поведения алгоритмов при обра-
ботке небольших объемов данных.
Определение сложности в O-обо-
значениях – далеко не тривиальная задача.
В частности, эффективность бинарного
поиска определяется не глубиной вложен-
ности циклов, а способом выбора каждой
очередной попытки. Из-за трудностей, свя-
занных с проведением анализа временной
сложности алгоритма “в среднем”, часто
приходится довольствоваться оценками
для худшего и лучшего случаев.
Таким образом, оценка вычисли-
тельной сложности алгоритма, получаемая
на основе рассмотренного метода, может
быть не совсем точной. В этом случае до-
полнительно предлагается использовать
способ получения оценки через вычисле-
ние количества выполняемых базисных
операций при различных размерах n вход-
ных данных. При этом могут подсчиты-
ваться либо все базисные операции алго-
Таблица. Вычисление асимптотической временной сложности для конструкций алгоритма
Вид управляющей структуры Сложность
Базисный оператор или базисное условие O(1)
оператор1 ЗАТЕМ оператор2 O(оператор1) + O(оператор2)
ЕСЛИ условие ТО оператор1 ИНАЧЕ
оператор2 КОНЕЦ ЕСЛИ
max{O(условие), O(оператор1),
O(оператор2)}
ПОКА НЕ условие_окончания_цикла ЦИКЛ
оператор КОНЕЦ ЦИКЛА
O(n) * O(оператор)
оператор1 ПАРАЛЛЕЛЬНО оператор2 max{O(оператор1), O(оператор2)}
ПАРАЛЛЕЛЬНО((i) = (1),..., (n)) ( оператор ) O(оператор)
ЖДАТЬ условие O(условие)
КТ условие O(условие)
Паралельне програмування
44
ритма, либо только существенные для
данной задачи (например, для сортировок
обычно вычисляется количество сравне-
ний и перестановок элементов). Далее по
результатам строится график временной
сложности T(n), анализ которого позволит
определить порядок функции T(n). На
рис. 1 показаны примеры зависимостей
T(n) для последовательных алгоритмов
сортировки массивов [7]: 2)( 2 −+= nnnT
(пузырьковая сортировка),
2/)65()( 2 −+= nnnT (челночная) и
)log()( nnOnT = (сортировка слиянием).
Для вычисления емкостной слож-
ности алгоритма требуется проанализиро-
вать блоки глобального и локального объ-
явлений переменных [1] схемы алгоритма
с учетом типов их данных. Отметим, что
определение емкости алгоритма тесно свя-
зано с условиями его реализации для кон-
кретной ЭВМ и используемого языка про-
граммирования [8]. С другой стороны, на-
бор типов данных, используемых в вычис-
лениях, относительно постоянен. Среди
скалярных величин это целочисленные
типы, вещественные типы, строковые
типы. Среди векторных величин это, в ос-
новном, массивы скаляров, объем которых
определяется совокупным объемом соот-
ветствующих скаляров. Для вычисления
объема памяти в байтах, необходимого для
хранения данных некоторого алгоритма,
могут использоваться величины S = 1 (для
символьного типа), ,21 =Z 42 =Z (для це-
лочисленных типов); ,41 =R ,82 =R
103 =R (для вещественных типов). Мас-
сив, состоящий из n элементов, имеет раз-
мер nX, где X – размер скаляра.
Пример 2. Для иллюстрации полу-
чения оценки временной сложности для
параллельных вычислений, рассмотрим
САА-схему алгоритма моделирования
броуновского движения. Суть данного ал-
горитма состоит в совместном функциони-
ровании NUM_THREADS параллельных по-
токов, каждый из которых моделирует
движение некоторой частицы (примеси) в
одномерном кристалле (массиве) Crystal
длины CrystalLen > 0. Количество по-
токов равно количеству примесей:
NUM_THREADS = AdmixtureCount. При
инициализации программы все примеси
находятся в первой ячейке кристалла.
Одна итерация каждого потока заключа-
ется в переходе частицы в соседнюю (ле-
вую или правую) ячейку кристалла в зави-
симости от сгенерированного случайного
числа. Новая позиция частицы вычисля-
ется в операторе “ОпределитьНовуюПо-
зицию”. Сокращенная САА-схема для
данного алгоритма имеет вид
0
100
200
300
400
500
600
700
0 10 20 30
n
T(
n
)
T(n) = n 2̂ + n -2
T(n) = (n 2̂ + 5n - 6)/2
T(n) = O(n log n)
Рис. 1. Примеры графиков временной сложности T(n)
Паралельне програмування
45
Рассмотрим процесс вычисления
для приведенного алгоритма асимптотиче-
ской временной сложности T(n), при n
равном количеству итераций в каждом по-
токе (IterationAmount). Выполним вос-
ходящий анализ управляющих структур
алгоритма (от внутренних к внешним) в
соответствии с правилами из таблицы.
Представим последовательность
вычислений сложности конструкций со-
ставного оператора “ДвижениеЧа-
стицы(ThreadNum)” следующими фор-
мулами:
O(cs) = O(1) + O(1) = O(1);
O(if) = max{O(1), O(cs) + O(1)} =
= max{O(1), O(1) + O(1)} = O(1);
O(cycle) = O(n) · (O(1) + O(if)) =
= O(n) · (O(1) + O(1)) = O(n);
O(co) = O(1) + O(cycle) =
= O(1) + O(n) = O(n),
где O(cs), O(if), O(cycle), O(co) – асимпто-
тическая сложность для критической сек-
ции, условного оператора, цикла и состав-
ного оператора “ДвижениеЧасти-
цы(ThreadNum)” соответственно.
Далее приведена последователь-
ность вычислений сложности для основ-
ного составного оператора алгоритма:
O(par) = O(co) = O(n);
O(algo) = O(1) + O(par) + O(1) =
= O(1) + O(n) + O(1) = O(n),
СХЕМА БРОУНОВСКОЕ_ДВИЖЕНИЕ/П
"ОсновнойСоставнойОператор"
==== "Инициализация данных"
ЗАТЕМ
ПАРАЛЛЕЛЬНО((ThreadNum) = (0), ..., (NUM_THREADS - 1))
(
"ДвижениеЧастицы(ThreadNum)"
)
ЗАТЕМ
ЖДАТЬ 'Обработка во всех (NUM_THREADS) ветвях закончена'
"ОпределитьНовуюПозицию(right_margin, pos, limit, ThreadNum)"
==== "(res) := (pos)"
ЗАТЕМ
"Сгенерировать случайное число (r) из отрезка [0..1]"
ЗАТЕМ
ЕСЛИ '(r) >= (limit)' И НЕ('(pos) = (right_margin)')
ТО "(res) := (pos + 1)"
КОНЕЦ ЕСЛИ
ЗАТЕМ
ЕСЛИ '(r) < (limit)' И НЕ('(pos) = (0)')
ТО "(res) := (pos - 1)"
КОНЕЦ ЕСЛИ
"ДвижениеЧастицы(ThreadNum)"
==== "Инициализировать генератор случайных чисел"
ЗАТЕМ
ДЛЯ '(iteration_counter) от (1) до (IterationAmount)'
ЦИКЛ
"(nextx) = ОпределитьНовуюПозицию(CrystalLen - 1, x, ProbabilityLimit, ThreadNum)"
ЗАТЕМ
ЕСЛИ НЕ('(nextx) = (x)')
ТО КритическаяСекция(Admixture_CS)
(
"Уменьшить (Crystal[x]) на (1)"
ЗАТЕМ
"Увеличить (Crystal[nextx]) на (1)"
)
ЗАТЕМ
"(x) := (nextx)"
КОНЕЦ ЕСЛИ
КОНЕЦ ЦИКЛА
КОНЕЦ СХЕМЫ
Паралельне програмування
46
где O(par), O(algo) – асимптотическая
сложность для параллельной конструкции
и всего алгоритма соответственно. Таким
образом, рассмотренный параллельный ал-
горитм имеет линейную сложность O(n).
Отметим, что сложность соответствую-
щего ему последовательного алгоритма
составляет )( 2nO .
2. Методика применения системы
TermWare совместно
с инструментарием «ИПС»
Как уже упоминалось [1], использо-
вание системы TermWare позволяет до-
полнить «ИПС» возможностью автомати-
зированного выполнения преобразований.
Поскольку система TermWare [9–11] явля-
ется достаточно гибкой, возможны раз-
личные варианты ее применения, перечис-
ленные далее.
1. Создание правил для автома-
тизации конкретного преобразования. Та-
кие правила позволяют быстро осуществ-
лять достаточно сложные преобразования.
При этом правила могут как вводиться
вручную (в текстовой или визуальной
форме), так и генерироваться автоматиче-
ски на основании действий пользователя.
Во втором случае пользователь вручную
осуществляет некоторое преобразование
схемы алгоритма, при этом отмечая начало
и конец трансформации. На основании
этих данных система автоматически соз-
дает правила, переводящие начальный
терм в конечный (эта возможность анало-
гична записи макроса в современных сре-
дах разработки; при этом «макрос» пред-
ставляется в декларативном виде). Полу-
ченные правила будут соответствовать
преобразованию конкретной программы;
однако есть возможность редактировать
эти правила, в частности, заменяя отдель-
ные подтермы на переменные. При этом
пользователь указывает терм, конкретное
значение которого не существенно для
корректности правила; все вхождения
этого терма автоматически заменяются пе-
ременной TermWare с уникальным назва-
нием. Данная возможность позволяет
пользователям, незнакомым с системой
TermWare, использовать возможности ав-
томатизации, а также изучать TermWare на
конкретных примерах.
2. Восстановление САА-схемы из
исходного кода. Для этого используется
парсер целевого языка (C/C++, Java, C# и
др.), который преобразовывает исходный
код в терм специального вида, соответст-
вующий дереву синтаксического разбора.
После этого происходит автоматизирован-
ное преобразование полученного терма в
терм, соответствующий схеме алгоритма.
Для каждого элемента схемы задаются
правила, которые обнаруживают данный
элемент в дереве синтаксического разбора.
После применения этих правил, система
проверяет наличие в полученном терме
элементов, которые не могут быть частью
САА-схемы (т.е. конструкций, не преду-
смотренных в правилах). Пользователь
вручную задает правила обработки этих
элементов (например, они могут игнори-
роваться или сохраняться в виде специаль-
ных элементов схемы, не предназначенных
для дальнейшей модификации). Таким об-
разом, пользователь может начать работу с
«ИПС», не изучая детально правила созда-
ния схем.
3. Преобразования конструкций,
характерных для определенной платформы
(языка). Многие элементы схем (в особен-
ности конструкции координации многопо-
точных программ) имеют похожую семан-
тику, но различный синтаксис в разных
языках или при использовании разных
библиотек. Возможно создание правил,
осуществляющих преобразования между
такими конструкциями. Это позволяет об-
легчить переход от одной платформы к
другой.
4. Применение преобразований,
ориентированных на определенные классы
задач. Разработка преобразований, кото-
рые автоматически оптимизируют любую
программу, представляется практически
невозможной. Тем не менее, существуют
определенные классы задач, для которых
можно построить оптимизирующие преоб-
разования, применимые ко всем задачам
данного класса. Поэтому возможно созда-
ние библиотеки таких преобразований, при
этом пользователю предоставляется воз-
можность выбора конкретной системы
Паралельне програмування
47
правил. Даже если общие правила непри-
менимы к данной задаче, они могут ис-
пользоваться в качестве основы для напи-
сания специализированных правил. Воз-
можно также создание правил, опреде-
ляющих возможность применения данного
преобразования.
Основой функционирования сис-
темы TermWare в рамках «ИПС» является
создание и применение систем правил.
Каждая система правил соответствует не-
которому преобразованию схемы алго-
ритма. Кроме самих правил TermWare,
система правил может включать дополни-
тельную информацию, например, описание
преобразования или ссылки на другие сис-
темы правил, которые могут применяться
совместно с данной. Возможны также ин-
формационные системы правил, которые
не осуществляют преобразование схемы, а
вычисляют некоторые ее характеристики.
Кроме работы с системами правил,
TermWare позволяет выполнять и другие
действия. Например, уже упоминалась
возможность автоматического создания
правил, исходя из начального и конечного
терма, а также модификации правил с по-
мощью замены подтерма на переменную.
Есть возможность отслеживания опреде-
ленных термов; например, при преобразо-
вании в терм, который должен соответст-
вовать некоторым требованиям (быть кор-
ректной САА-схемой, соответствовать
конкретной платформе) система указывает
пользователю на не преобразованные
термы (которые не удовлетворяют требо-
ваниям). Можно также использовать так
называемые TODO-термы. Эти термы
имеют вид TODO_TermName и представ-
ляют терм вида TermName, который может
требовать определенной доработки.
TODO-термы отслеживаются в двух слу-
чаях: они выводятся как список задач,
стоящих перед пользователем (аналогично
использованию комментариев, содержа-
щих TODO, в современных средствах раз-
работки). Кроме того, если элемент
TermName является допустимым в конеч-
ном терме, возможно автоматическое соз-
дание правил TODO_TermName →
TermName.
3. Примеры использования системы
TermWare
3.1. Пример: задача нахождения
простых чисел (Primes). В качестве при-
мера использования TermWare рассмотрим
задачу определения общего количества
простых чисел от 1 до некоторого
числа [1]. Вычисления в ней осуществля-
ются путем проверки каждого нечетного
числа, является ли оно нацело делимым на
меньшие нечетные факторы. Данная за-
дача принадлежит к классу задач, в кото-
рых осуществляются некоторые независи-
мые вычисления, после чего результат вы-
числений сохраняется в общую память.
Такие алгоритмы достаточно легко подда-
ются распараллеливанию, однако при этом
есть некоторые особенности, влияющие на
производительность многопоточной про-
граммы. В качестве исходной схемы для
данной задачи в [1] рассмотрена последо-
вательная программа (Sequential), которая
была преобразована в параллельную путем
разбиения главного цикла (в котором пе-
ребираются числа – кандидаты в простые)
на NUM_THREADS циклов (где
NUM_THREADS – количество потоков). В
простейшем варианте программы
(BlockTasksThread) каждый поток обраба-
тывает последовательные числа.
Эта программа позволяет использовать ап-
паратные средства многоядерных систем,
но недостаточно эффективно. Для повы-
шения производительности вычисления в
каждом потоке модифицируются таким
образом, чтобы все потоки выполняли
примерно одинаковый объем работ; при
этом получается достаточно эффективная
программа InterleavedTaskThread. Сле-
дующим шагом является улучшение про-
граммы за счет использования функций
типа Interlocked. При этом была полу-
чена еще более эффективная программа
InterlockedThread, хотя изменение произ-
водительности по сравнению с предыду-
щей программой InterleavedTaskThread
оказывается незначительным. Перечис-
ленные преобразования были применены к
алгоритмам с использованием правил в
системе TermWare.
Паралельне програмування
48
На рис. 2 и 3 показаны результаты
сравнения производительности получен-
ных программ, выполненных на процес-
соре Intel Core Duo. Приведены зависимости
времени исполнения от количества чисел,
а также от количества потоков.
Как видно из графиков, простейший
способ распараллеливания (BlockTasks-
Thread) позволяет использовать аппарат-
ные ресурсы двухядерной платформы, но
не полностью. Использование более пра-
вильной схемы распараллеливания позво-
ляет повысить производительность прак-
тически вдвое по сравнению с последова-
тельным случаем, т.е. полностью исполь-
зовать аппаратные ресурсы. Заметим
также, что при использовании большего
количества потоков производительность
реализации BlockTasksThread возрастает,
приближаясь к более эффективным
InterleavedTaskThread и InterlockedThread;
таким образом, при использовании более
мелких задач правильное распределение
вычислений между ними становится не
столь существенным.
Time(threads )
0
0,2
0,4
0,6
0,8
1
1,2
1 2 3 4 5 6 7 8
Threads
T
im
e,
s
Sequentia l
BlockTas ks T hread
InterleavedT as ksT hread
InterlockedT hread
Рис. 3. Зависимость времени исполнения от количества потоков (50000 чисел)
Time(number)
0
0,5
1
1,5
2
2,5
3
3,5
4
4,5
1 2 3 4 5 6 7 8 9 10
Number, *10000
T
im
e
,s
Sequential
Bloc kTas ks Thread
In terleavedT as ksT hread
In terlockedT hread
Рис. 2. Зависимость времени исполнения от количества чисел (2 потока)
Паралельне програмування
49
3.2. Пример: задача Brown. В ка-
честве примера применения алгебраиче-
ского подхода для преобразования средств
координации вычислений рассмотрим
многопоточную программу моделирования
броуновского движения, реализованную
по схеме алгоритма из примера 2 (см. раз-
дел 1).
Особенностью данной задачи явля-
ется то, что большая часть времени в ней
расходуется не на вычисления, а на син-
хронизации потоков. Поэтому простые
способы реализации оказываются малоэф-
фективными. Например, исходная реали-
зация задачи (программа SmallLockThread,
которая реализована с использованием
критической секции) на двуядерной сис-
теме работает медленнее, чем последова-
тельная реализация (Sequential).
На примере этой задачи можно
продемонстрировать использование раз-
личных типов преобразований, не меняю-
щих вычислительной части программы, но
затрагивающих координационный аспект.
Первым типом преобразования является
изменение критической области. Воз-
можно либо расширение критической об-
ласти (включение в нее дополнительных
операторов), либо разбиение критической
области на несколько меньших критиче-
ских областей. В первом случае преобра-
зования осуществляются автоматически,
во втором от разработчика требуется ука-
зать идентификаторы новых критических
областей. В частности, в данной задаче
имеет смысл использовать массив крити-
ческих секций и блокировать каждую опе-
рацию с помощью критической секции,
соответствующей номеру изменяемой
ячейки кристалла. Проиллюстрируем упо-
мянутые преобразования.
Рассмотренному в примере 2 со-
ставному оператору "ДвижениеЧа-
стицы(ThreadNum)", реализующему в
схеме БРОУНОВСКОЕ_ДВИЖЕНИЕ/П отдель-
ный поток, соответствует следующий терм
MoveParticle(
Parameters(ThreadNum),
THEN(InitRandom,
THEN(
FOR(Parameters(iteration_counter, 1, IterationAmount),
THEN(
Assignment(nextx, CalculateNewPosition(minus(CrystalLen, 1), x,
ProbabilityLimit, ThreadNum)),
THEN(
IF(logical_not(eq(nextx, x)),
THEN(
CriticalSection(Admixture_CS,
THEN(
Decrement(ArrayElement(Crystal, x)),
THEN(
Increment(ArrayElement(Crystal, nextx)), NIL))),
THEN(
Assignment(x, nextx), NIL))), NIL))), NIL))).
Расширение критической секции использует правила следующего вида (система
правил R1):
1. THEN(CriticalSection($x0, $x1), $x2) → CriticalSection($x0, THEN($x1, $x2)).
2. THEN($x0, CriticalSection($x1, $x2)) → CriticalSection($x1, THEN($x0, $x2)).
3. IF($x0, CriticalSection($x1, $x2)) → CriticalSection($x1, IF($x0, $x2)).
Паралельне програмування
50
системы TermWare:
Первые два правила определяют
расширение критической секции по ли-
нейным участкам кода; третье определяет
включение в критическую секцию конст-
рукций if (подобные правила можно соз-
дать и для других управляющих конструк-
ций). В результате применения этих пра-
вил исходный терм преобразуется в терм,
соответствующий реализации потока в но-
вой программе BigLockThread:
Разбиение критической секции на не-
сколько меньших критических секций
осуществляется с помощью следующих
правил (R2):
Первое правило выделяет первый опе-
ратор из критической секции в отдельную
критическую секцию. Второе правило
описывает последовательное выделение
элементов критической секции в отдель-
ные критические секции, а третье – усло-
вие остановки. При этом термы, описыва-
ющие новые критические секции, полу-
чают специальное название – Critical-
Section1 вместо CriticalSection. Это
позволяет в дальнейшем использовать
правила, которые действуют только на та-
кие преобразованные критические секции.
Далее в алгоритме можно использовать
массив критических секций и блокировать
каждую операцию с помощью критичес-
кой секции, соответствующей номеру из-
меняемой ячейки кристалла. В этом случае
применяются правила (R3):
MoveParticle(
Parameters(ThreadNum),
THEN(InitRandom,
THEN(
FOR(Parameters(iteration_counter, 1, IterationAmount),
CriticalSection(Admixture_CS,
THEN(
Assignment(nextx, CalculateNewPosition( minus(CrystalLen,1), x,
ProbabilityLimit, ThreadNum)),
THEN(
IF(
logical_not(eq(nextx, x)),
THEN(
THEN(
Decrement(ArrayElement(Crystal, x)),
THEN(
Increment(ArrayElement(Crystal, nextx)), NIL)),
THEN(
Assignment(x, nextx), NIL))), NIL)))), NIL))).
1. CriticalSection($name, THEN($x, $y)) →
THEN(CriticalSection1(TODO_Name($name, 0),$x),
CriticalSection1(TODO_Name($name, 1), $y)).
2. CriticalSection1(TODO_Name($name, $n),THEN($x, $y)) →
THEN(CriticalSection1(TODO_Name($name, $n), $x),
CriticalSection1(TODO_Name($name,$n+1),$y)).
3. CriticalSection1($name, NIL) → NIL.
Паралельне програмування
51
Первые два правила определяют
конкретные названия критических секций.
Правило 3 переводит терм со специальным
названием CriticalSection1 в стан-
дартный терм CriticalSection.
Заметим, что в общем случае эти
преобразования скорее ухудшают свойства
программы. Расширение критических сек-
ций (программа BigLockThread) умень-
шает количество кода, который может вы-
полняться параллельно (хотя упрощение
структуры программы может привести к
использованию оптимизаций компилятора,
что улучшает производительность). Раз-
биение критической секции (программа
SeparatedLockThread) повышает накладные
расходы на синхронизацию; кроме того,
полученная программа оказывается не
полностью эквивалентной исходной. При
разбиении критической секции отдельные
операторы выполняются атомарным обра-
зом, но между двумя последовательными
операторами одного потока могут выпол-
няться операторы другого (хотя в данной
задаче это несущественно). Однако приме-
нение таких трансформаций позволяет
вводить дополнительные средства синхро-
низации, которые могут быть более эф-
фективными. Например, программа
SeparatedLockThread содержит только опе-
раторы увеличения и уменьшения пере-
менной, поэтому критические секции в ней
можно заменить функциями Interlock-
edDecrement и InterlockedIncrement.
Эта программа (InterlockedThread) явля-
ется более эффективной, чем исходная
(хотя и не строго эквивалентна ей, как и
SeparatedLockThread).
Программа BigLockThread также
может использоваться в качестве исходной
при введении новых средств синхрониза-
ции. Однако при этом используются не
стандартные средства синхронизации, а
специально разработанный класс
LoopManipulation. Этот класс
предоставляет один метод RunSafeLoop,
который принимает в качестве параметра
тело цикла и количество итераций, и
выполняет необходимое количество
итераций в пределах критической области
(фактически этод метод заменяет цикл for
с вложенной критической секцией). При
этом количество блокировок не равняется
количеству итераций, а определяется
специальным параметром класса (т.е.
несколько итераций выполняются в
пределах одной критической секции). За
счет уменьшения количества критических
секций существенно снижаются накладные
расходы на синхронизацию, поэтому такая
программа (LoopManipulationThread) явля-
ется более эффективной. Заметим, что
фактически данный класс является альтер-
нативной реализацией алгебраической
конструкции – цикла. Это значит, что хоть
исходный код двух вариантов отличается
достаточно существенно, но их алгебраи-
ческое представление оказывается практи-
чески одинаковым.
Также возможен переход к исполь-
зованию специализированных библиотек
синхронизации, таких как Concurrency and
Coordination Runtime (CCR) [12, 13] и C#
Software Transactional Memory (SXM) [14,
15]. Библиотека CCR представляет собой
набор программных конструкций для ко-
ординации взаимодействий между пото-
ками в C# [12]. Данные конструкции могут
комбинироваться для представления
сложных и гибких шаблонов взаимодейст-
вия (communication patterns). Библиотека
CCR базируется на программирования на
основе портов (port-based programming) и
передачи сообщений, как механизме
структурирования программного обеспе-
чения и средстве обеспечения изолирован-
ности между различными компонентами
для надежности и повышения степени па-
раллелизма программы. Основным досто-
инством библиотеки CCR является воз-
можность высокоуровневой координации
задач, что исключает необходимость ис-
пользования низкоуровневых конструкций
синхронизации, таких как блокировки.
Software Transactional Memory
(SXM) [14, 15] представляет собой API для
1. TODO_Name(Admixture_CS, 0) → ArrayElement(Admixture_CS, x).
2. TODO_Name(Admixture_CS, 1) → ArrayElement(Admixture_CS, nextx).
3. CriticalSection1($x, $y) → CriticalSection($x, $y).
Паралельне програмування
52
многопоточных вычислений, в которых
разделяемые потоками данные синхрони-
зируются без использования блокировок.
Потоки синхронизируются с помощью
транзакций памяти (memory transactions) –
кратковременных вычислений, которые
либо выполняются полностью (оказывают
воздействие на данные) либо терпят не-
удачу и прерываются (не оказывают воз-
действия). С помощью SXM в программах
указываются атомарные (atomic) блоки,
упрощающие написание параллельных
программ. Блок кода обозначается как
атомарный, после чего компилятор и сис-
тема поддержки выполнения гарантируют,
что операции в пределах блока, включая
вызовы функций, будут атомарными.
Для перехода к использованию спе-
циализированных библиотек координации
возможно использование простых и доста-
точно общих алгебраических равенств
(правил TermWare). При этом определен-
ные конструкции синхронизации преобра-
зуются в их аналоги в этих библиотеках;
далее с помощью генератора кода созда-
ются программы, использующие данные
библиотеки (HandleCCR и
SXMTransactional). Как и в случае про-
граммы LoopManipulationThread, несмотря
на значительное различие кода на языке
C#, алгебраические представления про-
грамм оказываются весьма близкими, и
отражают существенное изменение – пе-
реход к новой реализации определенных
операторов, а не детали реализации. Осо-
бенно это заметно для SXM, поскольку в
этой системе вместо простого блока
atomic{} используются довольно сложные
правила вызова API (поскольку эта биб-
лиотека разрабатывалась в расчете на
обычный компилятор C#, в ней не было
возможности непосредственной реализа-
ции новых конструкций языка). Итак, ал-
гебраическая запись позволяет скрыть
технические детали реализации таких биб-
лиотек, показывая только существенные
отличия. Кроме того, использование авто-
матически применяемых правил позволяет
осуществить быстрый переход к использо-
ванию подобных библиотек, при этом нет
необходимости вручную переписывать
существующий код.
Полученные до настоящего времени
программы использовали общие правила,
что позволяло применять их к широкому
классу задач. Однако при этом производи-
тельность таких программ оказывалась не-
высокой. Для того чтобы получить более
существенный прирост производительно-
сти, необходимо использовать особенно-
сти задачи. Основной проблемой при соз-
дании эффективной параллельной реали-
зации задачи моделирования броуновского
движения является необходимость выпол-
нения большого количества простых ите-
раций. Для повышения производительно-
сти необходимо уменьшить количество
синхронизаций (аналогично LoopManipu-
lationThread), при этом не расширяя
критическую область. Один из вариантов
реализации данного подхода заключается в
сохранении состояния каждой итерации в
пределах соответствующего потока, с
записью этого состояния в общую память
после определенного количества итераций.
Такая программа (InvisibleMovesThread)
может быть получена с использованием
системы правил, реализующей общую
схему такого преобразования; при этом
конкретные особенности (например, как
происходит сохранение и обновление
состояния) реализуются с помощью
специальной системы правил, разра-
ботанной для данной задачи. При этом
получается очень эффективная программа,
производительность которой на двух-
ядерной системе почти в 2 раза выше, чем
у последовательной программы.
На рис. 4 и 5 показаны графики за-
висимости времени работы от количества
итераций и количества частиц (потоков).
Как видно из приведенных графи-
ков, большинство средств синхронизации
оказывается не очень эффективным для
данного класса задач. Существенное
улучшение по сравнению с последова-
тельной программой достигается только на
программе InvisibleMovesThread. Про-
грамма LoopManipulationThread выполня-
ется со скоростью, близкой к последова-
тельной программе; все остальные про-
граммы оказываются неэффективными. За-
метим, что программа на основе транзак
Паралельне програмування
53
ционной памяти не показана на рис. 4 и 5,
поскольку время исполнения в этом случае
существенно выше (например, для 2
частиц и 500000 итераций последова-
тельная программа выполняется 0,09 с,
худшая из приведенных программ –
SeparatedLockThread – выполняется 0,39 с,
а программа на основе транзакционной
памяти – 8,31 с). Таким образом, подходы
к синхронизации, претендующие на уни-
Time(iterations)
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
1 2 3 4 5 6 7 8 9 10
Iterations,*100000
Ti
m
e,
s
Sequential
SmallLockThreads
SeparatedLockThread
LoopManipulationThread
BigLockThread
HandleCCR
InterlockedThread
InvisibleMovesThread
Рис. 4. Зависимость времени исполнения от количества итераций (2 частицы)
TIme(threads)
0
0,05
0,1
0,15
0,2
0,25
0,3
1 2 3 4 5 6 7 8
Threads
Ti
m
e,
s
Sequential
SmallLockThreads
SeparatedLockThread
LoopManipulationThread
BigLockThread
HandleCCR
InterlockedThread
InvisibleMovesThread
Рис. 5. Зависимость времени исполнения от количества частиц (100000 итераций)
Паралельне програмування
54
версальность, могут оказаться неэффек-
тивными для конкретных классов задач.
Заключение
В работе исследован вопрос полу-
чения оценок вычислительной сложности
алгоритмов на основе алгебраического
подхода. Предложена методика совмест-
ного использования интегрированного
инструментария и системы TermWare для
автоматизации применения преобразова-
ний к алгоритмам (в частности, направле-
нных на оптимизацию программ). Приве-
денные примеры (Primes и Brown)
демонстрируют возможности TermWare
для перехода между различными сред-
ствами координации вычислений в
многопоточных программах. Результаты
экспериментов по выполнению получен-
ных оптимизированных программ (Inter-
leavedTaskThread, InterlockedThread и Invi-
sibleMovesThread) на микропроцессоре с
многоядерной архитектурой демонстри-
руют хорошую степень распараллеливае-
мости и масштабируемости вычислений.
Дальнейшее развитие разрабаты-
ваемых инструментальных средств будет
также включать создание:
• трансформатора алгоритмов, ин-
тегрирующего TermWare и «ИПС», и
предназначенного для конструирования и
применения правил;
• средств облегченной синхрони-
зации в многопоточных программах, улуч-
шающих существующие методы и позво-
ляющих достичь высокого качества много-
ядерных программ, интенсивно использу-
ющих синхронизацию.
1. Дорошенко А.Е., Жереб К.А., Яценко Е.А.
Формализованное проектирование эффек-
тивных многопоточных программ // Про-
блемы программирования. – 2007. – № 1. –
С. 17–30.
2. Shameem Akhter, Jason Roberts. Multi-Core
Programming. Increasing Performance
through Software Multi-threading. – Intel
Press, 2006. – 336 p.
3. Дорошенко А.Ю., Фінін Г.С., Цейтлін Г.О.
Алгеброалгоритмічні основи програму-
вання. – К.: Наук. думка, 2004. – 458 c.
4. Яценко Е.А., Мохница А.С. Инструменталь-
ные средства конструирования синтакси-
чески правильных параллельных алгорит-
мов и программ // Проблемы программи-
рования. – 2004. – № 2–3. – С. 444–450.
5. Ахо А., Хопкрофт Дж., Ульман Дж. По-
строение и анализ вычислительных алго-
ритмов. – М.: Мир, 1979. – 536 с.
6. Структуры и алгоритмы. Оценка про-
грамм. – http://www.structur.h1.ru/ocen-
ka.htm
7. Цейтлин Г.Е. Введение в алгоритмику. −
Киев: Сфера, 1998. − 310 с.
8. Эффективные алгоритмы. Теория и прак-
тика применения. Этапы полного построе-
ния алгоритма. – http://www.tspu.tula.ru/
ivt/umr/ealg/docs/doc02/doc02.htm
9. TermWare. – http://www.gradsoft.com.ua/
products/termware_rus.html
10. Shevchenko R. TermWare: Semantics
Description, GradSoft Ltd, Kiev, Ukraine. –
http://www.gradsoft.com.ua/rus/Products/term
ware/docs/Semantics_rus/index.html
11. Doroshenko A., Shevchenko R. A Rewriting
Framework for Rule-Based Programming
Dynamic Applications, Fundamenta Informa-
ticae, 2006. – Vol. 72, N 1–3. – P. 95–108.
12. Chrysanthakopoulos G., Singh S. An
Asynchronous Messaging Library for C#. –
http://research.microsoft.com/~tharris/scool/
papers/sing.pdf
13. An Asynchronous Messaging Library for C#
2.0. – http://channel9.msdn.com/wiki/defa-
ult.aspx/Channel9.ConcurrencyRuntime
14. C# Software Transactional Memory. –
http://research.microsoft.com/research/downl
oads/Details/6cfc842d-1c16-4739-afaf-
edb35f544384/Details.aspx?CategoryID=
15. Harris T., Jones S.P. Transactional memory
with data invariants. –
http://research.microsoft.com/~tharris/papers/
2006-transact.pdf
Получено 05.04.2007
Паралельне програмування
55
Об авторах:
Дорошенко Анатолий Ефимович,
доктор физико-математических наук,
профессор,заведующий отделом теории
компьютерных вычислений,
Яценко Елена Анатольевна,
кандидат физико-математических наук,
научный сотрудник,
Жереб Константин Анатольевич,
аспирант Физико-технического учебно-на-
учного центра НАН Украины.
Место работы авторов:
Институт программных систем
НАН Украины, 03680, Киев-187,
проспект Академика Глушкова, 40.
тел. (044) 526 1538,
e-mail: dor@isofts.kiev.ua, aiyat@i.com.ua
Физико-технический учебно-научный
центр НАН Украины, 03142, Киев-142,
бульвар Вернадского, 36.
тел. (044) 424 3025,
e-mail: zhereb@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-286 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-07T16:00:48Z |
| publishDate | 2007 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Дорошенко, А.Ю. Жереб, К.А. Яценко, Е.А. 2008-02-22T18:25:01Z 2008-02-22T18:25:01Z 2007 Об оценке сложности и координации вычислений в многопоточных программах / А.Е. Дорошенко, К.А. Жереб, Е.А. Яценко // Пробл. програмув. — 2007. — N 2. — С. 41-55. — Библиогр.: 15 назв. — рус. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/286 Предложен метод оценки вычислительной сложности алгоритмов на основе алгебраического подхода. Разработана методика применения системы переписывания правил для преобразования конструкций координации вычислений в многопоточных программах. Приведены примеры трансформаций параллельных программ и результаты их выполнения на многоядерной архитектуре. 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/286 |
| work_keys_str_mv | AT dorošenkoaû obocenkesložnostiikoordinaciivyčisleniivmnogopotočnyhprogrammah AT žerebka obocenkesložnostiikoordinaciivyčisleniivmnogopotočnyhprogrammah AT âcenkoea obocenkesložnostiikoordinaciivyčisleniivmnogopotočnyhprogrammah |