Рихвицкий
В.С. 
Несколько априорных замечаний.
Имея N процессоров,
можно получить ускорение не более, чем в N раз. Сравним: быстрая сортировка
массива длиной N имеет трудоемкость N*ln(N) умноженное на некоторую
константу, но оценка будет вестись по скорости роста) против самой
простой и самой медленной - методом пузырька, трудоемкость которой (N-1)*(N-2)/2.
Выигрыш, таким образом порядка в N/ln(N) раз. Конечно, для малых N опущенный
коэффициент может быть существеннее. То же самое, сравнивая обычное и быстрое
преобразование Фурье.
Идеальный
вариант распараллеливания - изначально независимые одинаковые вычисления
по нескольким ветвям, например, умножение матриц. Быстрое преобразование
Фурье можно еще более убыстрить за счет параллельной обработки.
Распараллеливание
на самом нижнем уровне - команд - используя массивы регистров называется
векторизацией.
Распараллеливание
на уровне совместимых подпрограмм требует более сложного (а может быть
более простого - свойства подпрограмм быть зависимыми, с одной стороны
и совместимыми с другой создает отношение частичного порядка по используемым
и создаваемым параметрам) и специальных указаний для динамической синхронизации
разнородных процессов (впрочем, векоризация тоже требует специальных).
Надо быть
осторожными - трудоемкость усилий по синхронизации слишком малых блоков
может перекрыть выигрыш от совмещения.
Можно
только надеяться, что совместное использование общих ресурсов - памяти,
например - не приведет к коллизиям. Впрочем, если память требуется большая,
проблему может создать свопинг.
Препятствия
к распараллеливанию. Уже в быстрой сортировке, также как и в быстром преобразовании
Фурье, массив разбивается на подмассивы динамически. Транслятор не может
до выполнения создать оптимальный алгоритм, если только в нем нет эвристики,
предлагающей разделить цикл по разбиениям (надо же догадаться!) на две
части: для разбиений на малые подмассивы, которых много и на большие, которых
мало. На каждом из них свой способ распараллеливания.
Существует
класс задач, называемых NP-полными, для точного решения которых которых
не существует более экономичного алгоритма, чем полный перебор вариантов.
К ним относится, например, известная задача о коммивояжере (из класса задач
на нахождение экстремума). Хотя, конечно, существуют алгоритмы, доставляющие
"почти оптимальное решение" почти всегда, но даже практически никогда нет
гарантий этого "почти". Очевидно, требуется сразу внести разумное сокращение
перебора всех путей отсечением повтора анализа остатка пути, если он уже
встречался и оценен или ясно, что стоимость тестируемого пути (точнее,
это уже целое подсемейство) не может быть ниже достигнутого минимума.
Эти оценки
эффективнее распараллеливания на немногих (скажем, 10) процссорах. Но тогда
как связать эти отсечения в мультипроцессорном алгоритме? Скажем, пока
один процесс идет по своему пути, другой получает заключение о бесполезности
этого. И надо еще идентифицировать такую ситуацию! Она же не формальная,
т.е. скрыта в значениях и транслятор до выполнения программы ничего не
знает. Конечно, и на этот случай могут быть эвристики, но сколько же можно?!
Начало практической работы.
Эта машина
не имеет никакого доступа, кроме сетевого. Поэтому вхожу в нее, конечно,
с помощью telnet. Как выясняется, текстового редактора, приятного для незнакомца,
тоже нет. Поэтому подготавливаю файл своей первой программы на PC (Norton'овским
редактором). Файл называю достаточно оригинально: hello.f. Кажется, другого
расширения, кроме .f писать нельзя. Содержимое оригинальностью ему соответствует:
print *,"Hello!"
stop
end
Пересылаю
на SPP посредством ftp (обязательно в режиме ascii!). Затем вхожу telnet'ом
в эту машину и выполняю команду
f77 -o hello hello.f
В результате
появляются два файла: hello.o и hello. Последний из них - выполняемый.
Запускаю его написав команду
hello
Срабатывает.
Рихвицкий
В.С.