Основы параллельного программирования

Организация параллельных программ как системы потоков

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

Существование нескольких одновременно выполняемых потоков приводит к появлению дополнительных соотношений, которые должны выполняться для величин временных траекторий потоков. Согласно [7], возможные типовые варианты таких соотношений на примере двух потоков p и q состоят в следующем (см. рисунок 1):

• — выполнение потоков осуществляется строго последовательно, т. е. поток начинает свое выполнение только после полного завершения потока (однопрограммный режим работы ЭВМ — см. рисунок 1 пункт а);
• — выполнение потоков может осуществляться одновременно, но в каждый момент времени могут исполняться команды только какого-либо одного потока (режим разделения времени или многопрограммный режим работы ЭВМ — см. рисунок 1 пункт б);
• — параллельное выполнение потоков, когда одновременно могут выполняться команды нескольких потоков (данный режим исполнения потоков осуществим только при наличии в вычислительной системе нескольких процессоров — см. рисунок 1 пункт в).

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

Согласно [7], результат одновременного выполнения нескольких потоков, если не предпринимать специальных мер, может зависеть от порядка исполнения команд. Ситуация, когда два или более потоков используют разделяемый ресурс и конечный результат зависит от соотношения скоростей потоков, называется состязанием или гонками.

Выполним анализ возможных командных последовательностей, которые могут получаться для программ, образованных в виде набора потоков. Рассмотрим для простоты два потока.

Командная последовательность программы образуется чередованием команд отдельных потоков и тем самым имеет вид:

Фиксация способа образования последовательности из команд отдельных потоков может быть обеспечена при помощи характеристического вектора.

В котором следует положить, если команда получена из потока (иначе). Порядок следования команд потоков в должен соответствовать порядку расположения этих команд в исходных потоках.

где есть команда потока, соответствующая команде в .

С учетом введённых обозначений, под программой, образованной из потоков и, можно понимать множество всех возможных командных последовательностей.

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

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

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

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

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