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

ЛЕКЦИЯ 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
		a	+	▬	+			a	+
	b	+	+	+	▬ +
	c	*	+	*	▬ +		c	*
	d	*	*	*	▬ + *
	l	*	*	*	▬ + *		l	*
	f	*	*	*	▬ + * +
	g	▬	*	▬	▬ + * +g▬
			+	▬	+	▬ +			+
		*	+	*	▬ + *			+ *
		+	*	+	▬ + +	= *		+
	g	▬	+	▬	▬ +	= +g
			+	▬	+	▬ +			+
		▬	+	▬	▬ ▬

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

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

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

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

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

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

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

12
• Далее ⇒