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

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

Заметим, что применение закона дистрибутивности при эквивалентных преобразованиях требует большой осторожности, поскольку при этом возможно, например, переполнение. Например, если в выражении величины , – большие положительные числа, то умножение может быть выполнено без осложнений, но умножения в эквивалентном выражении могут вызвать переполнение.

Покажем на примере как может меняться высота ЯПФ при изменении порядка действий в выражении.

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