Уважаемый
Nick Kovalyov, конвейеризация дело сложное и трудное, но интересное. Это почти что распараллеливание, даже нет не так - это именно распараллеливание задачи во времени (в отличие от распараллеливания в пространстве). Попробуем разобраться в поставленной Вами задачи. Итак, что мы имеем: некий алгоритм программы, содержащий цикл. Для начала предположим, что цикл у нас будет одиночный и простой. Примерно такой, какой показан на следующем рисунке:
Этот алгоритм представляет собой несколько операторов, возможно не связанных между собой, которые должны выполниться
i раз. Для перехода от блок-схемы алгоритма к граф-схеме воспользуемся одной из методик, описанной в следующей книге Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. – М.: Радио и связь, 1990. – 256 с. Или сразу построим граф программы по правилам, изложенным в Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуа-лизация и применение. – СПб.: БВХ-Петербург, 2003. – 1104 с. При этом зависимость по данным между операторами может быть очень сильная или наоборот - слабая. Имеется два крайних случая, изображённых на рисунке:
Для простоты примем, что у нас в цикле есть всего три оператора (не считая счётчика итераций, но он как правило не представляет интереса и говорить о нём мы не будем) -
a,
b и
c. Если связь между операторами сильная т.е. например, оператор
b использует в своём теле оператор
a, вычисленный только что (в этом же цикле итерации), а оператор
c использует оператор
b, то данный алгоритм является полностью последовательным и его никак нельзя распараллелить ни во времени, ни в пространстве. Так как невозможно посчитать
c не посчитав при этом
b и т.д. Этому случаю соответствует первая граф-схема. Второй крайний случай - слабая информационная связь или вообще отсутствие оной. Это означает, что все три оператора могут быть выполнены параллельно (пространственное распараллеливание). Этот случай показан на второй граф-схеме. В нашем случае интерес представляют промежуточные варианты, т.е. когда зависимость между переменными есть, но значения берутся из результатов предыдущих итераций. Пусть, например, оператор
b использует своё собственное значение, вычисленное на предыдущей итерации (или ещё раньше), значение оператора
a, также вычисленное не позже предыдущей итерации и значение оператора
c, вычисленное двумя итерациями ранее. Тогда оператор
b можно конвейеризовать с оператором
a и
c. Пример конвейеризации для описанных случаев приведён на следующем рисунке:
Ситуация I соответствует сильно связанным операторам - все они выполняются строго последовательно и, соответственно, работает только одна ступень нашего импровизированного конвейера. Второй случай (II) в наибольшей степени подходит нам. Работа здесь осуществляется следующим образом:
1. В первую ступень конвейера загружаем оператор
a и производим вычисление (здесь следует заметить, что оператор
a является неделимой атомарной частицей алгоритма т.е. он представляет собой элементарную операцию, если это не так и оператор
a можно разбить на несколько операторов, то нетрудно обобщить всё вышесказанное и на этот случай). Для этого используем начальное значение оператора
a (
a(0)).
2. Производим загрузку оператора
a во вторую ступень конвейера, а в первую загружаем оператор
b. Вычисляем новые значения этих операторов.
3. Сдвигаем оператор
a в третью ступень, во вторую помещаем оператор
b, а в первую загружаем оператор
c. Производим вычисление.
Не трудно увидеть, что теперь мы каждый такт будем получать значения всех операторов цикла.
Случай III соответствует полностью распараллеливаемой структуре, которую можно выполнять как на конвейере, так и на нескольких функциональных устройствах.
Таким образом проблема распараллеливания циклов, а как частный случай - конвейеризация, зависит от внутренней структуры этого самого цикла, точнее от зависимости операторов между собой по данным. Вообще распараллеливание циклов довольно трудная задача, если сразу не видно как он будет выполняться, то приходится выполнять сложный анализ, привлекая довольно непростой математический аппарат. В некоторых случаях помогают разные программы, например, в упомянутой мною книге Касьянова и Евстигнеева приводятся несколько примеров графических редакторов для работы с графами и библиотек для соответствующей обработки и анализа. Но как правило они тоже не эффективны.
Подробнее почитать о распараллеливании можно в следующей литературе:
1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БВХ–Петербург, 2002. – 608 с.
2. Распараллеливание алгоритмов обработки информации. Том 1 / Под ред. А.Н. Свенсона. – Киев: Наук. думка, 1985. – 280 с.
3. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. – М.: Радио и связь, 1989. – 176 с., ил.
4. Штейнберг Б.Я. Распараллеливание рекуррентных программных циклов. // Ин-формационные технологии, №4, 2004.
5. Барбан А.П., Игнатущенко В.В. Распараллеливание структурированных про-грамм. // Электронное моделирование, №2, 1982.
6. Ортега Дж. Введение в параллельные и векторные методы решения линейных сис-тем: Пер. с англ. – М.: Мир, 1991. – 367 с.
7. Воеводин В.В. Информационная структура алгоритмов. - М.: Изд-во МГУ, 1997.- 139 с.
8. Евстигнеев В.А., Спрогис С.В. Векторизация программ: анализ зависимостей. 1989.
9. Шнитман В.З. Современные высокопроизводительные компьютеры. Учебное пособие, 1996 // Аналитические материалы Центра информационных технологий.
http://www.citforum.ru/hardware/svk/contents.shtml.
10. Шпаковский Г.И. Организация параллельных ЭВМ и суперскалярных процес-соров: Учебное пособие. – Мн.: Белгосуниверситет, 1996. – 296 с.
11. Ну и конечно сайт
http://www.parallel.ruУспешной работы!
"О наслажденье ходить по краю.
Замрите, ангелы, смотрите: я играю.
Разбор грехов моих оставьте до поры,
Вы оцените красоту игры!"
Конвейеризация циклов вычислений?
Dec 16 2005, 06:30
)
