20150420_msu08_Integr (Лекции), страница 2

Таким образом, требование "всеотрезки интервала интегрирования полностью обработаны" означает,что:- функция проинтегрирована на всех отрезках, покрывающих исходный интервалинтегрирования;- полученные на отрезках интегрирования значения интегралов добавлены кчастичным суммам соответствующих процессов.Москва, 2015 г.Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.29 из 40Необходимые данныеsdat.sem_listsdat.s_allsdat.sem_task_presentsdat.list_of_taskssdat.ntasksdat.nactivesdat.s_allМосква, 2015 г.семафоры доступа:семафор доступа к глобальному стеку отрезковсемафор доступа к значению интеграласемафоры состояния:семафор наличия записей в глобальном стекеотрезковпеременные:глобальный стек отрезковчисло записей в глобальном стеке отрезков указатель глобального стека отрезковчисло активных процессовзначение интегралаПараллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.30 из 40Параллельный алгоритм: метод глобального стекаint{//////slave_thr()все переменные, начинающиеся с sdat.

являются глобальными,к ним имеет доступ каждый из запущенных процессов slave_thrи запускающая программа main// sp, s - локальные переменные процессов slave_thrsp=0 // указатель локального стека - локальный стек пустs=0 // частичная сумма интегралов, вычисленных на отрезках,// обработанных данной копией процесса// начало цикла обработки стека интерваловwhile(1){// ожидание появления в глобальном стеке интервалов для обработкиsem_wait(sdat.sem_task_present)// чтение одного интервала из списка интервалов// Начало критической секции чтения из глобального// стека очередного интервала интегрирования//sem_wait(sdat.sem_list)sdat.ntask-- // указатель глобального стекаGET_OF_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab)if(sdat.ntask)sem_post(&sdat.sem_task_present)if(a<=b) // очередной отрезок не является терминальнымsdat.nactive++ // увеличить число процессов, имеющих// интервал для интегрированияsem_post(sdat.sem_list)//// Конец критической секции чтения из глобального// стека очередного интервала интегрированияif(a>b) // отрезок является терминальнымbreak // выйти из цикла обработки стека интервалов// начало цикла интегрирования одного интервалаwhile(1){c=(a+b)/2fc=fun(c)sac=(fa+fc)*(c-a)/2scb=(fc+fb)*(b-c)/2sacb=sac+scbif(!BreakCond(sacb,sab)){s+=sacbif(!sp) // локальный стек пустbreak // выход из цикла интегрирования// одного интервалаsp-GET_FROM_LOCAL_STACK[sp]( a, b, fa, fb, sab)}else{PUT_TO_LOCAL_STACK[sp]( a, c, fa, fc, sac)sp++a=cfa=fcsab=scb}Москва, 2015 г.// перемещение части локального стека// в общий список интерваловif((sp>SPK) && (!sdat.ntask))Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.31 из 40Инициализацияint{//////slave_thr()все переменные, начинающиеся с sdat.

являются глобальными,к ним имеет доступ каждый из запущенных процессов slave_thrи запускающая программа main// sp, s - локальные переменные процессов slave_thrsp=0 // указатель локального стека - локальный стек пустs=0// частичная сумма интегралов, вычисленных на отрезках,// обработанных данной копией процессаМосква, 2015 г.Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.32 из 40Доступ процесса IntTrap04p к глобальному стеку// начало цикла обработки глобального стекаwhile(1){// ожидание появления в глобальном стеке интервалов для обработкиsem_wait(sdat.sem_task_present)// чтение одного интервала из списка интерваловsem_wait(sdat.sem_list)sdat.ntask-- // указатель глобального стекаGET_OF_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab)if(sdat.ntask) // в глобальном стеке остались заданияsem_post(&sdat.sem_task_present)if(a<=b) // очередной отрезок не является терминальнымsdat.nactive++ // увеличить число процессов, имеющих интервал для интегрированияsem_post(sdat.sem_list)if(a>b) // отрезок является терминальнымbreak // выйти из цикла обработки стека интерваловМосква, 2015 г.Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.33 из 40Запись терминальных отрезков// Начало критической секции заполнения глобального// стека терминальными отрезками (a>b)sem_wait(&sdat.sem_list)sdat.nactive--if( (!sdat.nactive) && (!sdat.ntask) ){// запись в глобальный стек списка терминальных отрезковfor(i=0;i<nproc;i++){PUT_TO_GLOBAL_STACK[sdat.ntask](2,1,-,-,-)sdat.ntask++;}// в глобальном стеке есть записиsem_post(sdat.sem_task_present)}sem_post(sdat.sem_list)//// Конец критической секции заполнения глобального// стека терминальными отрезкамиМосква, 2015 г.Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.34 из 40Результаты тестирования1J10512 1 sin x2 xВремя выполненияNptiger.jscc.ruga03.imamod.ru131.3937.48215.6119.00310.29-47.83-22.011.9733.0544.013102%4100%УскорениеNptiger.jscc.ruga03.imamod.ru111Эффективностьnptiger.jscc.ruga03.imamod.ruМосква, 2015 г.1100%100%2101%99%Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.35 из 40Вопросыкакую часть отрезков следует перемещать излокального стека в глобальный стек?- в какой момент интеграл вычислен?- что должен делать процесс у которого пустлокальный стек, если глобальный стек тоже пуст?-- должен ли процесс закончить работу, если в еголокальном и в глобальном стеке отрезков нет?-На сколько отрезков изначально разбить отрезок?Москва, 2015 г.Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.36 из 40ЗаключениеРассмотрен ряд методов вычисления интеграловна многопроцессорных системах,проанализированы их преимущества инедостатки Показано, что методы геометрическогопараллелизма и коллективного решениянеприменимы для эффективного численногоинтегрирования функций общего вида Показано, что идея децентрализованногоуправления расчетом эффективно решает задачуМосква, 2015 г.Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.37 из 40ЛитератураЯкобовский М.В.

Введение в параллельные методырешения задач: Учебное пособие / Предисл.: В. А.Садовничий. – М.: Издательство Московскогоуниверситета, 2013. – 328 с., илл. – (Серия«Суперкомпьютерное образование») ISBN 978-5-21106382-2Якобовский М.В., Кулькова Е.Ю. Решение задач намногопроцессорных вычислительных системах сразделяемой памятью. - М.: СТАНКИН, 2004.

– 30 c.http://www.imamod.ru/~serge/arc/stud/Jackob_2.pdfМосква, 2015 г.Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.38 из 40КонтактыЯкобовский М.В.проф., д.ф.-м.н.,зав. сектором«Программного обеспечения многопроцессорныхсистем и вычислительных сетей»Института прикладной математики им.М.В.Келдыша Российской академии наукmail: lira@imamod.ruweb: http://lira.imamod.ruМосква, 2015 г.Параллельные алгоритмы: Параллельные алгоритмы численногоинтегрирования © Якобовский М.В.39 из 40.