Лекция 6. Алгоритм автоматического распараллеливания арифметических

выражений (по А.В.Вальковскому)

Этот метод, использует отношение старшинства между операциями. Идея метода в том, что в выражении выделяются подвыражения, содержащие самые высокоприоритетные операции. Выделенные подвыражения одинаковой глубины «склеиваются» в более крупное подвыражение, таким образом «вырастает» выражение, все подвыражения которого имеют равномерную глубину.

Обычно в качестве знаков арифметических операций используют: +, -, *, /, !,μ. Две последние операции — возведение в степень и унарный минус. При неформальном изложении знак умножения * иногда опускается. Вводится стар-

шинство, или приоритет, операций:

Pr(μ) = 4; Pr(!) = 3; Pr(*) = Pr(/) =2; Pr(+) = Pr(-) = 1.

Опишем один вариант алгоритма более подробно, используя для наглядности только лишь выражения с операциями +, *.

Для хранения текущей информации нам потребуется следующая память:

ячейки х — для сканируемых операндов, у — для сканируемых операций, L —

для операции, стоящей слева от текущего операнда, R — для аналогичной опе-

рации справа, Out — для выходного выражения, Тi — ячейки для записи про-

межуточных результатов. Кроме того, воспользуемся вектор-стеком: St = (St1,

St2) — компонента St1 для операндов; St2 — для операций; Sc — процедура

сканирования следующего символа входной строки; символ —> обозначает за-

сылку. Считается, что входное выражение слева и справа ограничено пробелами, Рг (▬) = 0. Первоначально в R и Out содержится пробел.

Шаг 1. Sc —> х , Sc—> у, R —> L, у — > R. Сканируется очередной опе-

ранд и знак операции после него. Операция (пробел) слева от операнда х засы-

лается в ячейку L, справа от x — в ячейку R.

Шаг 2. Если (St=O OR Рг (L)< Рг (R) OR Рг (St2)<Рг (L)) AND Рг (R)≠

O, то на шаг 3, иначе на шаг 4.

Шаг 3. х —> St1 , y —> St2 , переход на шаг1. Запоминаем операнд и операцию и переходим к сканированию следующей пары (операнд, операция).

Шаг 4. Если Рг (L) = Рг (St2), то на шаг 5, иначе на шаг 6.

Шаг 5. Out Tk у —> Out. Если Pr (y) = 0, то конец разбора, иначе па шаг 1. Здесь промежуточная ячейка Тk = (St1 St2 x). Таким образом, когда найдены две операции одного старшинства, первая из них с соседними операндами группируется в промежуточный результат Tk, вслед за ним выписывается вторая операция, и все это приписывается к выходной строке. Далее Tk воспринимается алгоритмом как атомный операнд.

Шаг. 6. Out х у —> Out, если у = "_", то конец разбора, иначе на шаг. 1. В

случае если не находится двух операций одного старшинства и приоритеты

пошли на убывание, операнд и операция просто приписываются к выходной

строке.

Приведенный алгоритм описывает один из проходов, после которого неко

торые из подвыражений «свертываются» в промежуточные результаты Т k . По-

сле этого алгоритм повторяется до тех пор, пока все выражение не сведется к

единственному Tk.

Покажем выражение е = а + b + с * d* I* f + g после серии последо-

вательных проходов.

1. Входная строка: ▬а+ b +c*d*l*f+g▬ .

2. Результат 1-го прохода: ▬ T1 + T2 * Т3 + g▬ , где

T1 = (а + b), T2 = (с*d), Т3 = (1 *f).

3. Результат 2-го прохода: ▬ T4 + Т5 ▬ , где

T4 = (T2 * T3 ), T5 = (T1 + g).

4. Результат 3-го прохода: ▬T6 ▬ ; T6 = (T4 + T5).

5. Выходная строка: ▬ (((с * d) * (l * f)) + ((а + b) + g)) ▬

Представим таблицу, подробно описывающую весь процесс преобразования указанного выражения.

Проход	Такт	x	y	L	R	Out
1	1	a	+	▬	+			a	+
	2	b	+	+	+	▬+
	3	c	*	+	*	▬+		c	*
	4	d	*	*	*	▬+*
	5	l	*	*	*	▬+*		l	*
	6	f	*	*	*	▬+*+
	7	g	▬	*	▬	▬+*+g▬
2	8		+	▬	+	▬+			+
	9		*	+	*	▬+*			+ *
	10		+	*	+	▬++	=*		+
	11	g	▬	+	▬	▬+	=+g
3	12		+	▬	+	▬+			+
	13		▬	+	▬	▬▬

Дерево выходного выражения (ЯПФ, полученная на основе сравнения старшинства операций)

Доказано, что описанный алгоритм дает в результате выражение с мини-

мальным временем выполнения. Однако он имеет ряд существенных недостат-

ков, главный из которых—многопроходность: он требует столько проходов, ка-

ково время выполнения сгенерированного выражения. Чтобы избавиться от

многопроходности, нужно в процессе разбора «нести» попутно информацию об

уровне формируемых конструкций. Имеется однопроходная версия метода.

Алгоритм распараллеливания программы базового блока.

Построение ЯПФ для отрезка программы производится путем определения зависимости пар смежных команд при анализе программы сверху вниз согласно алгоритму на рисунке.( l – промежуточная переменная, i – номер команды в программе)