Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 195 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

Рассмотрим решение задачи о генерации простых чисел (ре-
шето Эратосфена) с помощью портфеля задач, используя C-Linda
(эта задача уже рассматривалась ранее на языке CSP).
Числа-кандидаты на простое число хранятся в пространстве
кортежей. Управляющий процесс собирает результаты и помещает
числа-кандидаты в портфель.
Каждый процесс удаляет число-кандидат из портфеля и прове-
ряет, является ли оно простым, деля его на м´еньшие простые числа.
Для реализации этой схемы (т. е. для того, чтобы проверить, что все
м´еньшие простые числа уже имелись) проверять числа-кандидаты
нужно в возрастающем порядке. Возможна приостановка рабоче-
го процесса в ожидании, что другой процесс сгенерирует м´еньшее
простое число, но взаимная блокировка двух и более процессов ис-
ключается.
Пример. (Генерация простых чисел на языке C-Linda).
РАБОЧИЙ ПРОЦЕСС
# include "linda.h"
# define LIMIT 1000
/* верхняя граница числа простых чисел */
void worker() { /* функция без параметров */
int primes[LIMIT]={2,3} /* таблица простых чисел */
int numPrimes=1, i, candidate, isprime;
/* numPrimes - номер очередного простого числа */
/* циклическое получение кандидатов и их проверка */
while(true) {
if(RDP("stop"))
/* проверка завершения: появился ли
в пространстве кортежей "stop" */
return; /* выход из функции */
IN("candidate", ?candidate); /* получить кандидата */
OUT("candidate", candidate+2);
/* вывод следующего нечетного в качестве
кандидата погружаем в ПК */
i=0; isprime=1;
while(primes[i]*primes[i]<=candidate) {
/* далее нет необходимости проверять
ибо на остальные числа делится не может */
if(candidate%primes[i]==0){
196

Страницы