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

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

где V – количество операций, которые необходимо выполнить при решении задачи на ВС; n – число параллельных ветвей или число вычислителей, на которых решается задача, n≥2;

t(V,n) – время, затрачиваемое на:

• синхронизацию параллельных ветвей алгоритма,
• настройку (программирование структуры) системы,
• реализацию обменов информацией между ветвями (вычислителями);

T(V,n) – время, расходуемое системой собственно на счет.

На основе анализа задач и опыта их решения (с использованием методики крупноблочного распараллеливания) на вычислительных системах установлено, что при n = const показатель ε(V,n) асимптотически стремится к нулю с ростом объема операций в задаче, т.е. имеет место: ε(V,n) → 0 при V → ∞. Значения ε(V,n) будут практически удовлетворительными при выполнении неравенства

V ≥n*10^k

где k – эмпирический коэффициент, k≥1. Очевидно, что имеет место зависимость k от быстродействия ν каналов связей между вычислителями: k→ 1 при ν → ν*, где 1/ν* – время обращения к локальной памяти в вычислителе. При удовлетворении неравенства достигается адекватное размещение параллельной программы на системе из n вычислителей (при произвольной структуре сети связей) и обеспечивается эффективное использование этих вычислителей.

Таким образом, если объем операций V, связанных с решением задачи, на несколько порядков превышает число вычислителей n, на которых должно осуществляться её решение, то достигается эффективное функционирование системы.

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