Главная       Библиотека      Перечень ссылок

ВЫПУСКНАЯ РАБОТА МАГИСТРА

Тема: "Исследование способов распараллеливания программ в процессе трансляции"

Руководитель: кандидат физико-математических наук, доцент Дацун Н. Н.

АВТОРЕФЕРАТ

СОДЕРЖАНИЕ

Общие сведения

Основная часть

Выводы

Используемая литература

ОБЩИЕ СВЕДЕНИЯ

Относительно недавно в связи с бурным развитием многопроцессорных вычислительных систем перед программистами встала задача распараллеливания вычислительного процесса, что в свою очередь наложило свои требования на построение трансляторов. Потребовалось распараллелить как сам процесс трансляции, так и работу программы, полученной в результате трансляции. В связи с этим за последние годы были проведены теоретические исследования по параллельной трансляции, являющиеся естественным развитием традиционных последовательных методов. Началась активная работа по теории параллельных вычислений. В результате были разработаны методы распараллеливания выходной программы в процессе трансляции, созданы алгоритмы параллельного счета некоторых типов арифметических выражений и систем уравнений и получены некоторые оценки эффективности распараллеливания. Однако методы, основанные на результатах теории параллельных вычислений, пока еще используются на практике довольно слабо.

Актуальность работы

Проблема распараллеливания выходных программ в вычислительном процессе является актуальной с развитием многопроцессорных систем.

Цель и задачи исследования

Целью выпускной работы является исследование методов распараллеливания программ в процессе трансляции, то есть исследование и модификация алгоритмов распараллеливания арифметических выражений.

Методы исследования

В работе используется теория вычислитильных процессов, теория моделирования.

Научная новизна полученных результатов

Научная новизна состоит в модификации существующих алгоритмов распараллеливания арифметических выражений для более широкого спектра задач.

Практическая новизна полученных результатов

Практическая новизна состоит в программной реализации алгоритмов распараллеливания арифметических выражений.

Апробация работы

Тестирование алгоритмов будет произведено при помощи моделирования многопроцессорной вычислительной системы.

Заключение и перспективы исследования

В работе проведено исследование и модификация существующих алгоритмов распараллеливания арифметических выражений.

ОСНОВНАЯ ЧАСТЬ

На данный момент разработано много алгоритмов распараллеливания и преобразования арифметических выражений [1 – 4]. Большая часть алгоритмов являются многопроходными. После каждого прохода формируется выходное выражение, которое является входным на следующем проходе алгоритма. Одним из самых простых является алгоритм [3], работающий с входным выражением в форме инверсной польской записи (ПОЛИЗ).

Преобразование арифметического выражения общего вида

В ПОЛИЗе операнды появляются в том же порядке, что и в исходном выражении, но символы операций должны быть переупорядочены так, чтобы учитывался приоритет операций. Скобки в ПОЛИЗе всегда отсутствуют и выражение записывается так, чтобы любой операции предшествовали ее операнды.

Первый алгоритм распараллеливания арифметического выражения

Считывается входная строка слева направо, при чем каждая пара операндов со знаком операции, стоящим за ними, заменяется промежуточной переменной. Эти промежуточные переменные являются входными операндами на следующем проходе алгоритма. Промежуточные переменные генерируются на одном проходе и принадлежат одному уровню дерева свертывания, поэтому их можно вычислять параллельно [3]. Алгоритм простой и быстрый, но не применим к арифметическим выражениям, содержащим некоммутативные операции.


Дерево свертывания выражения b • c • d + a + e + f
(в формате Flash Movie 5.0)

Второй алгоритм распараллеливания арифметического выражения

Этот алгоритм также является многопроходным. Каждый проход алгоритма соответствует шагу вычислений (уровню дерева свертывания). Все промежуточные переменные, которые можно получить на данном проходе, сформировываются и вставляются в выходное выражение данного прохода. Затем выходное выражение становится входным выражением следующего прохода и так до того, пока свертывание выражения не будет закончено [4]. Данный алгоритм использует два стека: один – для операндов, другой – для операций. В стеках используется обычное правило приоритета операций. Сначала создаются промежуточные переменные для вычисления операций более высокого приоритета. Благодаря этому и происходит преобразование арифметического выражения.


Дерево свертывания выражения a + b • c • d + e + f
(в формате Flash Movie 5.0)

Третий алгоритм распараллеливания арифметического выражения

  1. Входное выражение преобразуется в ПОЛИЗ и эта последняя записывается в обратном порядке.
  2. Начиная с самого правого символа, каждому символу входного выражения присваивается некоторый вес в соответствии с нижеописанными правилами. Присвоить каждому символу Si вес Vi = Vi + Ri, i = 1,…,n, где Ri = 1 – ∆(Si). ∆(Si) = 0, если Si – операнд. ∆(Si) = 1, если Si – унарная операция. ∆(Si) = 2, если Si – бинарная операция, Vi-1 = Vi-2 + Ri-1, Vi-2 = Vi-3 + Ri-2 ..., V1 = R1. Отметим, что если выражение из n символов правильное, то Vn = 1.
  3. Разбиваем входное выражение на два независимых следующим образом. Просматривая выражение слева направо, находим символ с максимальным весом Vm и отмечаем его. Слева от отмеченного символа ищем символ с весом 1 и слева от него проводим черту. Эта черта разделяет анализируемое выражение на два подвыражения. Отмечаем корень дерева. Корнем дерева является самый левый символ входного выражения.
  4. Поиск параллелизма внутри правого подвыражения. Сформировать новое подвыражение, состоящее из символов, ограниченных первыми символами справа и слева от символа Vm, чьи веса Vi = 1. Символы с весом Vi = 1 не входят в это вновь сформированное подвыражение. Переставляем это подвыражение вправо, соединив оставшиеся части правого подвыражения. Анализ подвыражения и разбиения его на подвыражения продолжается до тех пор, пока начальный символ Vm не станет в подвыражении на вторую позицию.
  5. Пункт 4 повторяем применительно к самому левому подвыражению [5].


Дерево свертывания выражения a + b + c + d • e • f + g + h
(в формате Flash Movie 5.0)

ВЫВОДЫ

В рамках работы были получены результаты:

1. Проведен анализ программ для автоматического распараллеливания и рассмотрены типичные элементы распараллеливания.
2. Рассмотрены известные представители классов матричных и векторных процессоров с учетом их особенностей работы и экономической выгоды.
3. Были получены оценки эффективности параллельных вычислений.
4. Приведены алгоритмы распараллеливания программ в процессе трансляции, которые позволяют распараллелить арифметические выражения за счет уменьшения количество шагов вычисления, как с оставлением числа операций, так и с увеличением числа операций.

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА

  1. Сборник трудов магистрантов 2003 Донецкого национального технического университета. Выпуск 2. - Донецк, ДонНТУ Министерства образования и науки Украины, 2003.


  2. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. – М.: Наука, 1981. - 256 с.


  3. Hellerman H. Parallel Processing of Algebraic Expressions. – iEEE Trans. Electron. Comput. EC. 15, 1966. – pages 82 – 91.


  4. Baer J.L., Bovet D.P. Compilation of Arithmetic Expressions for Parallel Computations. – North Holland, Amsterdam: Proc. IFIP Congress, 1968. – pages 340 – 346.


  5. Ramamoorthy C.V., Gonzalez M.J. A Survey of Techniques for Recognizing Parallel Processable Streams in Computer Programs. – In Conf. Proc. 1969 FJCC, AFIPS Press, 1972. – pages 1 – 15.
В начало      Главная       Библиотека      Перечень ссылок