Параллельные алгоритмы Последовательные алгоритмы Алгоритмы, в которых определены подпоследовательности действий, предназначенные для независимого параллельного исполнения Алгоритмы, действия которых определены для строго последовательного их исполнения

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

# include void main(void) { double x,y,z; double z1,z2 ; scanf(%e 5e\n,&x,&y) ; z1=sin(x); z2=cos(y); z=z1+z2 ; printf(%e\n,z); } Параметр начала t j н оператора Р j - это значение дискретного времени, соответствующее моменту начала выполнения оператора Р j Р. Временная глубина t j 0 оператора Р j - характеризует временную задержку между началом выполнения оператора Р j Р и моментом t j к получения результатов выполняемого преобразования Тип = + sin cos var sto p vx vix tj0 tj

Интервал активности оператора. Определим для произвольного одновыходного (k jвых = 1) оператора Р j Р с параметрами t j н и t j к интервал активности dt j как временной интервал, началом которого является момент времени t j н и концом которого является момент времени t j к завершения выполнения оператора Р j dt j = ( t j н, t j н +td, t j н +2td,..., t j к ), где td – выбранное значение приращения дискретного модельного времени. В последующем будем называть произвольный оператор Р j временным оператором (ВО) и обозначать Р j (t), если для него определены ( t j н, t j к ), либо (t j н,T0(Р j )) или интервал активности dt j

Временная параметризация множества операторов алгоритма. Примем, что задано множество Р = {P j }, j =0,1,2,..., р ( р =| P |) операторов некоторого алгоритма. Формирование для множества Р = {P j } соответствующего множества Р (t) временных операторов P j (t j н, t j к ) Р (t) = {P j ( t j н, t j к )}, где j = 0,1,2,...,p, назовем временной параметризацией исходного множества Р = {P j }. Введем множество NT = { t j н } параметров начала выполнения операторов алгоритма. Будем называть исходное множество Р = {P j } абстрактным множеством операторов, а множество Р (t) временных операторов P j ( t j н, t j к ) – параметризованным во времени множеством операторов. Множественный временной оператор. Примем, что имеются множества Р (t) = {Р j (t j н, t j к )} и/или Р (t) = {Р ( t j н, T 0 (Р j )}. Назовем множественным временным оператором (МВО) подмножество Р (t jr ) Р (t ) операторов Р j (t j н ), имеющих одно и то же значение t j н = t jr (t jr NT) и, следовательно, начинающих выполняться одновременно в момент времени t jr.

Определим параллельный алгоритм как временной алгоритм, в котором имеется хотя бы одна пара операторов Р j (t j н, t j к ) и Р i (t i н, t i к ) c частично или полностью перекрывающимися интервалами активности dt j и dt i, для которых выполняется условие dt j dt i Параллельный алгоритм Определим последовательный алгоритм как временной алгоритм, имеющий единичное значение ширины h = 1. Последовательный алгоритм

ПРОИЗВОЛЬНЫЙ ВРЕМЕННОЙ ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ Си-программы, представляющих текстовую и графическую спецификации статического алгоритма Множество Т н = {t j н }, j = 0,1,2,…,p, определяющего для каждого временного оператора параметр t j н начала его выполнения

Временная Параллельная Граф - Схема для временного алгоритма А -конструкция Г (t) = (D,U, C,Y), содержащая множество U = {Uj} вершин, множество С = {Ci} стрелок (связей), множество прямых – временных ярусов Y = {Yt}, отмеченных значениями дискретного времени t, удовлетворяющую следующим условиям: имеется взаимно однозначное соответствие между вершинами Uj и операторами Pj Uj Pj, ( j = 0,1,2,..., p ; р = | P |) ; если вершине Uj поставлен во взаимно однозначное соответствие оператор Рj функционального, временного, пространственного или комбинированного преобразования, то из данной вершины Uj исходят kjвых стрелок (kjвых - число выходов оператора Рj) и в данную вершину Uj входят kjвх стрелок ( kjвх - число входов оператора Рj); K j вхK j вых U j P j

если вершине U j поставлен во взаимно однозначное соответствие условный управляющий оператор L j, проверяющий (в общем случае) выполнение одного из m логических условий, то из данной вершины U j исходят m стрелок и в данную вершину U j входят kjвх стрелок ( kjвх-число входов оператора L j ); связи между вершинами конструкции Г (t) = (D,U, C,Y), определяются заданными для множества Р = {P j } операторов алгоритма А = ( D, Р(t ), S,W, DТ )) сопряженным S и внешним W множествами; все вершины U j ВПГС Г (t) = (D,U, C,Y), поставленные во взаимно однозначное соответствие временным операторам Рj (t j н,t j к ) Р(t ) алгоритма А = ( D, Р(t), S,W, DТ )), имеющим значение параметра начала t j н = t н и образующим множественный временной оператор (МВО) Р (t н ), расположены на временном ярусе Y со значением дискретного времени t = t н и образуют МВО U (t н ) ВПГС Г (t) = (D,U, C,Y ). K j вхK j вых LjLj if SjSj WjWj PjPj Y U(t H ) MBO tHtH

Ранг временного оператора Для произвольного временного оператора Р j ВПГС Г(t) понятие ранга r j определяется следующим образом: а) ранг r j = t j 0 при W j = (случай оператора Р j, являющегося выходным оператором алгоритма); б) r j = max (r λ + t j 0 ),если W j (случай, когда оператор Р j представляет собой P λ W j внутренний оператор алгоритма, обеспечивающий формирование промежуточного результата, используемого другими, внешними по отношению к Р j, операторами Р λ алгоритма). С содержательной точки зрения ранг r j оператора Р j задает максимальное значение времени от момента начала t j н выполнения оператора Р j до завершения решения задачи (то есть временную длину соответствующего маршрута в ВПГС Г (t)).

Частный приоритет b j временного оператора Р j (в рамках отдельного алгоритма) [1,2 ]: а) b j δ = 1 при r j = max r i и r i < r j при i j ; P i P δ б) b j δ < b i δ при r j = r i и t j 0 < t i 0 ; в) b j δ |W i | ; г) b j δ < b i δ при r j = r i, t j 0 = t i 0 и |W j | = |W i |, но i < j. Общие приоритеты d j операторов Р j различных алгоритмов будем определять следующим образом d j = b j δ + max (bi ν ), если j δ > min j ν, ν M δ P i P δ ν=1...κα d j = b j δ, если j δ = min j ν. В последнем соотношении М δ - множество номеров ν (ν 1...κ) алгоритмов, имеющих более высокие приоритеты ba ν по сравнению с приоритетом ba δ рассматриваемого алгоритма, Р δ - множество операторов, относящихся к алгоритму с номером δ, имеющему приоритет f δ.

Си – программа циклического алгоритма void main(void) { int s, r ; int i, p, q, t, k ; scanf ( %d %d\n, &s, &r ) ; for (i=1; i

Файлы, задающие граф задачи на уровне операторов

ВПГС циклической Си-программы

1. Поляков Г.А., Умрихин Ю.Д. Автоматизация проектирования сложных цифровых систем коммутации и управления. - М.: Радио и связь, с. 2. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. – СПб.: БХВ-Петербург, – 608 с. 3. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд.- СПб.: Питер, с. ЛИТЕРАТУРА