Наиболее распространенным типом параллелизма задач, реализуемых на вычислительных системах, является параллелизм независимых ветвей. Суть этого типа параллелизма состоит в том, что в алгоритме решения задачи на различных этапах могут быть выделены независимые модули - ветви, которые в вычислительных системах могут выполняться одновременно, т.е. параллельно, по независимым программам.
Удобной графической моделью представления параллелизма независимых ветвей является ярусно-параллельная форма. Все ветви в ЯПФ разбиваются по N+1 ярусам; в ярус 0 входят ветви, каждая из которых не зависит (в вышеуказанном смысле) от другой ветви; в первый - ветви, зависящие только от ветвей нулевого яруса;... в i-й ярус - ветви, зависящие от ветвей (i-1)-го яруса и, возможно, от ветвей ярусов с номерами, меньшими (i-1); и т.д.
Обычно графически ветви обозначаются кружками с соответствующими номерами (вместо номеров могут быть другие идентификаторы). Функциональные связи между ветвями показываются отрезками, причем если отрезок не выходит ни из какого кружка, то, он соответствует входной переменной программы; если отрезок соединяет два кружка, то этот отрезок соответствует выходной переменной для ветви а и входной - для b; если отрезок не входит ни в какой кружок, то он соответствует выходной переменной программы. Возможные «расщепления» отрезка означают, что одни и те же переменные являются входными для двух или более ветвей.
Каждую ветвь для удобства идентификации можно пронумеровать двойным индексом вида (i,j), где i -номер яруса, j - номер ветви в этом ярусе.
Важнейшая характеристика ветви (i, j) -это ее «длина», которая в зависимости от ситуации интерпретируется либо как трудоемкость реализации ветви, либо как время реализации на конкретном вычислительном устройстве.
Формирование ярусно-параллельной формы и оценка I- довольно трудоемкий процесс, зависящий от сложности задачи и от квалификации системного программиста. В современных вычислительных системах построением ЯПФ или подобного ей объекта занимается специальный блок ОС либо специальная программа-диспетчер. Однако для простых задач ЯПФ можно построить вручную.
Компания bsd.su оказывает услугу ит аутсорсинг москва.