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

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

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

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

Ускорение параллельной программы (алгоритма), получаемое при запуске программы на системе с p процессорами – это отношение

  (1)

где T1 – время выполнения программы на одном процессоре; Tp –время выполнения программы на системе из p процессоров.