Предпосылки методов
Задачи линейной и нелинейной оптимизации, сетевые транспортные задачи — задачи высокой сложности, подверженные "проклятию размерности". Ориентация на применение многопроцессорных симметричных вычислительных систем в составе персональных компьютеров или рабочих станций (параллельные вычисления) и на применение сетевых технологий (распределенные вычисления) требует разработки новых параллельных методов их решения. Эти методы должны быть лишены недостатков "традиционных" методов: последовательного характера вычислений и введения дополнительных переменных (для задач линейного программирования). Анализ способов распараллеливания показывает эффективность распараллеливания "по информации". Весьма перспективной поэтому становится SPMD-технология программирования (Single Program — Multiple Data). При этой технологии вычислительный процесс строится на основе единственной программы, запускаемой на всех процессорах вычислительной системы или на многих станциях локальной сети. Копии программы могут выполняться по разным ветвям алгоритма, обрабатывая подмножества данных. Неизбежна синхронизация во времени и при обработке общих данных.
Такая технология параллельного программирования и обусловила разработку рассмотренных ниже методов. В то же время не отрицаются известные традиционные методы, сокращающие общее число операций и исключающие перебор. Иной методологический подход открывает дорогу решению задач большой размерности и эффективной параллельной работе многих процессоров. Для ряда задач этот подход еще нуждается в исследовании, уточнении области применения и развитии — проведении тщательной математической экспертизы. Поэтому мы посчитали необходимым осветить его подробно — для лучшего представления "физического смысла", ощутимости пространственной модели задач и следующих из этого планов их параллельного решения.
