WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 ||

Внутри цикла интегрирования одного интервала осуществляется контроль числа отрезков, размещенных в локальном стеке процесса. Если оно превышает наперед заданную величину SPK и в глобальном стеке нет отрезков, то осуществляется перенос части отрезков из локального стека в глобальный. Перенос осуществляется в пределах критической секции. Следует обратить внимание на то, что проверка if((sp>SPK) && (!sdat.ntask)) выполняется вне критической секции, следовательно, возможна ситуация, в которой в момент доступа процесса внутрь критического интервала переменная sdat.ntask уже не будет иметь нулевое значение – то есть в глобальном стеке другим процессом уже будут размещены некоторые отрезки. Именно поэтому семафор наличия в стеке отрезков устанавливается только в том случае, если стек реально пуст (мы договорились, что выполнять операцию sem_post над открытым семафором нельзя):

if(!sdat.ntask) sem_post(sdat.sem_task_present) По окончании цикла обработки очередного отрезка выполняется проверка наличия заданий в глобальном стеке отрезков и наличия активных процессов:

if( (!sdat.nactive) && (!sdat.ntask) ) Эти действия выполняются внутри критической секции, таким образом, если обе проверки дали отрицательный результат, можно быть уверенным в том, что все фрагменты заданного интервала интегрирования уже обработаны, можно переходить к суммированию частичных сумм. Однако только один процесс «владеет» информацией о том, что интегрирование фрагментов полностью завершено, следует сообщить б этом остальным процессам, напомним, что они находятся в состоянии ожидания открытия «семафора наличия отрезков в глобальном стеке». Таким образом, единственным легальным способом завершить их работу, является размещение в глобальном стеке терминальных отрезков и открытие соответствующего семафора:

- 26 for(i=0;i

} sem_post(sdat.sem_task_present) Процесс, получивший терминальный отрезок, добавляет внутри критической секции найденную им частичную сумму к общему значению интеграла и заканчивает свою работу.

sem_wait(&(sdat.sem_sum)) sdat.s_all+=s sem_post(&(sdat.sem_sum)) Рассмотренный алгоритм демонстрирует достаточно высокую эффективность при выполнении на 2, 3 и 4х процессорах, что подтверждают приведенные ниже результаты определения интеграла 1 J = sin2 с точностью = 10-5.

x2 x 10-Время выполнения Np 1 2 3 tiger.jscc.ru 31.39 15.61 10.29 7.ga03.imamod.ru 37.48 19.00 - Ускорение Np 1 2 3 tiger.jscc.ru 1 2.01 3.05 4.ga03.imamod.ru 1 1.Эффективность np 1 2 3 tiger.jscc.ru 100% 101% 102% 100% ga03.imamod.ru 100% 99% В приложениях приведен перечень использованных в примерах функций работы с нитями, семафорами и подпрограмма измерения времени.

В листинге Алг. 7 запуск параллельных процессов упрощенно описан строками:

StartThrTask(np, slave_thr);

WaitThrTask();

В листинге Алг. 13 приведен подробный пример, иллюстрирующий последовательность запуска параллельных процессов, каж - 27 дый из которых выполняет процедуру, указанную параметром tsub. В рассматриваемом примере запускается процедура slave_thr.

typedef int ThrSub(void);

pthread_t *tid_procs;

StartThrTask(int np, ThrSub *tsub) { int i;

// --- распределить массив дескрипторов запускаемых процессов -- tid_procs = (pthread_t *)malloc(np*sizeof(pthread_t));

// --- запустить np процессов -- for (i = 0; i < np; i++) pthread_create(&(tid_procs[i]), NULL, tsub, NULL);

#ifdef HAVE_THR_SETCONCURRENCY_PROTO int thr_setconcurrency(int);

thr_setconcurrency(np);

#endif } WaitThrTask(void) { int i;

for(i = 0; i < np; i++) pthread_join(tid_procs[i], NULL);

} Алг. 13. Процедуры запуска и завершения параллельных нитей - 28 Приложения Перечень использованных в примерах функций Posix Семафоры Для использования функций управления семафорами следует включить в текст программы заголовочный файл semaphore.h:

#include int sem_init(sem_t *sem, int pshared, unsigned int value);

Обращение к функции sem_init приводит к инициализации семафора и установке его в закрытое состояние, если value =0, и в открытое, если value =1. Семафоры sem_t являются семафорами общего вида, поэтому при инициализации могут быть указаны и другие значения value, но в рамках рассмотренных примеров используются только 0 или 1. В простейшем случае pshared = 0.

Пример вызова:

sem_t sem;

sem_init(&sem, 0, 0);

int sem_wait(sem_t * sem);

Обращение к функции sem_wait приводит к остановке процесса, вплоть до изменения состояния семафора sem на не нулевое, если его значение в момент обращения равно 0. В противном случае значение семафора sem уменьшается на 1 и выполнение процесса продолжается.

Пример вызова:

sem_wait(&sem);

int sem_post(sem_t * sem);

Обращение к функции sem_post приводит к увеличению значения семафора sem на 1.

Пример вызова:

sem_post(&sem);

Процессы Для использования функций порождения нитей следует включить в текст программы заголовочный файл pthread.h:

#include - 29 int pthread_create(pthread_t * tid, pthread_attr_t * attr, void * (*start_routine)(void *), void * arg);

Обращение к функции pthread_create приводит к запуску процесса выполняющего функцию start_routine. В качестве первого параметра необходимо задать адрес дескриптора порождаемого процесса tid. В простейшем случае остальные параметры могут быть установлен в NULL.

Пример вызова:

pthread_t tid;

pthread_create(&tid, NULL, ThreadProcess, NULL);

int pthread_join(pthread_t tid, void **thread_return);

Обращение к функции pthread_join приводит к приостановке вызвавшего ее процесса до тех пор, пока нить, указанная дескриптором tid, не закончит свое выполнение. Через параметр thread_return передается значение, возвращаемое исполняемой нитью процедурой.

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

Пример вызова:

pthread_join(tid, NULL);

int thr_setconcurrency(int p);

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

Пример вызова:

#ifdef HAVE_THR_SETCONCURRENCY_PROTO thr_setconcurrency(p);

#endif Компиляция и сборка программы При создании исполняемого кода программы, возможно, потребуется указать две стандартные библиотеки, содержащие функции работы с нитями и семафорами. Например, компиляцию и сборку программы, исходный текст которой расположен в файле prog.c, можно выполнить следующим образом:

gcc prog.c -lpthread –lrt -o prog.x - 30 Измерение времени Для измерения интервалов времени удобно использовать функцию vmtime, текст которой приведен в листинге Алг. 14. Она возвращает значение времени истекшего с некоторого, неизменного в ходе выполнения программы, момента в прошлом, выраженное в секундах.

double vmtime(void) { double z;

struct timeval tst;

struct timezone tz;

gettimeofday(&tst,&tz);

z = (double)tst.tv_sec+1e-6*tst.tv_usec;

return z;

} Алг. 14. Процедуры запуска и завершения параллельных нитей Библиографический список 1. Языки программирования. Под ред. Ф.Женуи, Пер. с англ.

В.П.Кузнецова, Под ред. В.М.Курочкина. - М.: Мир, 1972, 406 стр.

2. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Пер. с англ. - Мир, 1981, 368 с.

3. Стивенс. У. Unix: взаимодействие процессов. Мастер-класс./ Пер.

с англ.Д.Солнышков. – Спб: Питер, 2002.-576 с. ISBN 5-31800534-9.

4. Якобовский М.В. Распределенные системы и сети. Учебное пособие. – М.: МГТУ “Станкин”, 2000, 118 с, ил 5. Транспьютеры. Архитектура и программное обеспечение. Пер. с англ. / Под ред. Г. Харпа. - М.: Радио и связь, 1993, 304 с., ил.

- 31 Содержание Введение.......................................................................................................Интегрирование одномерной функции на многопроцессорной системе с общей памятью..........................................................................................Последовательные алгоритмы................................................................Метод трапеций.....................................................................................Метод рекурсивного деления...............................................................Метод локального стека........................................................................Параллельные алгоритмы.......................................................................Метод геометрического параллелизма................................................Метод коллективного решения..........................................................Метод глобального стека....................................................................Приложения................................................................................................Перечень использованных в примерах функций Posix......................Семафоры.............................................................................................Процессы..............................................................................................Компиляция и сборка программы........................................................Измерение времени................................................................................Библиографический список......................................................................

Pages:     | 1 | 2 ||










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.