Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 10 лет назад пользователемКирилл Сутырин
3 Параллельные алгоритмы Последовательные алгоритмы Алгоритмы, в которых определены подпоследовательности действий, предназначенные для независимого параллельного исполнения Алгоритмы, действия которых определены для строго последовательного их исполнения
4 Временной алгоритм множество объектов (данных), над которыми должны выполняться действия множество действий (операторов), которые должны выполняться над объектами множество статических связей, задающих отношения упорядоченност и операторов выполнена временная параметризация, определяющая упорядоченност ь операций над объектами в динамике вычислительно го процесса
5 # 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
6 Интервал активности оператора. Определим для произвольного одновыходного (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
7 Временная параметризация множества операторов алгоритма. Примем, что задано множество Р = {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.
8 Определим параллельный алгоритм как временной алгоритм, в котором имеется хотя бы одна пара операторов Р j (t j н, t j к ) и Р i (t i н, t i к ) c частично или полностью перекрывающимися интервалами активности dt j и dt i, для которых выполняется условие dt j dt i Параллельный алгоритм Определим последовательный алгоритм как временной алгоритм, имеющий единичное значение ширины h = 1. Последовательный алгоритм
9 ПРОИЗВОЛЬНЫЙ ВРЕМЕННОЙ ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ Си-программы, представляющих текстовую и графическую спецификации статического алгоритма Множество Т н = {t j н }, j = 0,1,2,…,p, определяющего для каждого временного оператора параметр t j н начала его выполнения
11 Временная Параллельная Граф - Схема для временного алгоритма А -конструкция Г (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
12 если вершине 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
13 Ранг временного оператора Для произвольного временного оператора Р 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)).
14 Частный приоритет 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 δ.
15 Си – программа циклического алгоритма void main(void) { int s, r ; int i, p, q, t, k ; scanf ( %d %d\n, &s, &r ) ; for (i=1; i
16 Файлы, задающие граф задачи на уровне операторов
17 ВПГС циклической Си-программы
18 1. Поляков Г.А., Умрихин Ю.Д. Автоматизация проектирования сложных цифровых систем коммутации и управления. - М.: Радио и связь, с. 2. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. – СПб.: БХВ-Петербург, – 608 с. 3. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд.- СПб.: Питер, с. ЛИТЕРАТУРА
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.