После того, как мы воплотим в "железе" кластерную архитектуру, придется задуматься над вопросом а как же ее использовать. Старые линейные методы программирования уже не подходят для написания программ, эффективно использующих многопроцессорную технологию. Необходимо поменять стиль программирования задач. Но для этого надо иметь минимальное представление о том, какими способами можно превратить линейную программу в параллельную. Хотя существуют специальные трансляторы, которые автоматически, без участия програмиста, могут найти в программе куски параллельного кода и дать на выходе исполняемую на кластере задачу, добиться максимальных результатов с помощью таких трансляторов нельзя. О некоторых подобных трансляторах мы поговорим позже, когда будем обсуждать программное обеспечение кластера. Теперь же рассмотрим некоторые теоретические вопросы построения параллельных вычислений.

Распараллеливание программ - это процесс адаптации алгоритмов, записанных в виде программ, для их эффективного исполнения на вычислительной системе параллельной архитектуры. Заключается либо в переписывании программ на специальный язык, описывающий параллелизм и понятный трансляторам целевой вычислительной системы, либо к вставке специальной разметки (например, инструкций MPICH/MPI).

Распараллеливание может быть ручным, автоматизированным и полуавтоматизированным. При распараллеливании важно учитывать не только формальный параллелизм структуры алгоритма, но и то, что обменные операции в параллельных ЭВМ происходят, как правило, значительно медленнее арифметических. С этим связано существование львиной доли накладных расходов на организацию параллелизма.

Целью программиста не должно быть получение правильного результата вычислений любой ценой, но получение правильного результата наибыстрейшим, оптимальным способом. Если программа предназначена для однократного использования, то лучше написать ее как можно проще, не оптимизируя ее быстродействие и используемую память, чтобы потратить минимум усилий на тестирование и отладку. Если программа предназначена для частого использования или время ее работы будет гораздо больше времени ее написания и отладки, то не следует жалеть труда на оптимизацию ее быстродействия.

Для начала разберемся, что мы хотим получить от кластера. Как уже было сказано, использовать параллельные компьютеры имеет смысл только для "тяжелых" задач, которые требуют или большого времени счета или большого объема памяти.

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

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