14,16,17. Задача распараллеливания выражений. Общая характеристика.

Методы построения дерева свертки, основанные на анализе старшинства операций.

Методы анализа обратной польской записи.

Распараллеливание выражений.

Задача: требуется разработать алгоритм, ставящий в соответствие исходному выражению новое выражение, эквивалентное исходному и обладающее минимальным временем реализации.

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

Все алгоритмы распараллеливания выражений делят на две большие группы:

• Методы, основанные на сравнении старшинства операции.

• Методы, использующие обратную польскую запись.

Сравнение старшинства операций.

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

ПРИМЕР: Пусть требуется вычистить следующее выражение: E = a + b + c * d * e * f + g.

Входная строка	« a+b+c*d*e*f+g »
Результат первого прохода	T1+T2*T3+g, где T1 = (a+b), T2 = (c*d), T3 = (e*f)
Результат второго прохода	« T4+T5 », где T4 = (T2 * T3), T5 = (T1 + g)
Результат третьего прохода	« T6 », где T6 = (T4 + T5)
Выходная строка	(((c*d)*(e*f))+((a+b)+g)))

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

\

Стек пентад:

Уровень	Операция	1операнд	2операнд	Результат
1	+	a	b	T1
1	*	c	d	T2
1	*	e	f	T3
2	*	T2	T3	T4
2	+	T1	g	T5
3	+	T4	T5	T6

Полученный стек пентад может быть эффективно использован в ВС со стековой организацией.

Метода анализа обратной польской записи.

• Инфиксная запись «a+b»

• Префиксная запись «+ab»

• Постфиксная запись «ab+», она же обратная польская

В этом методе продвигаются по входной строке слева на право до тех пор пока не встречается триада типа: <операнд1><операнд2><операция>. После нахождения такой триады генерируется пентада: <уровень><операция><операнд1><операнд2><результат>, причем уровень равен номеру прохода. Дойдя до конца строки, начинают новый проход, где в качестве операндов используются операнды, незатронутые на предыдущих проходах, а так же промежуточные результаты.

Этот метод не дает в общем случае параллельной формы минимальной высоты.

ПРИМЕР: Пусть требуется вычистить следующее выражение: E = a + b + c * d * e * f + g.

Входная строка:	ab+cd*e*f*g++
Результат первого прохода:	T1T2e*f*g++, где T1=ab+, T2=cd*
Результат второго прохода:	T1T3f*g++, где T3=T2l*
Результат третьего прохода:	T1T4g++, где T4=T3f*
Результат четвертого прохода:	T1T5+, где T5=T4g+
Результат пятого прохода:	T6, где T6=T1T5+
Выходная строка:	(a+b)+((((c*d)*e)*f)+g)

Данный метод часто используется.