Member 14764665 Ответов: 2

Как изменить программу для использования нескольких потоков потребительского уровня


У меня есть проблемы, которые мне нужна помощь в решении. 1-я проблема состоит в том, чтобы иметь несколько потребительских потоков, работающих вместе, чтобы найти все простые числа в заданном диапазоне и измерить, сколько времени потребуется программе, чтобы найти все простые числа, используя 2, 3 и 4 потребительских потока. 2-я проблема состоит в том, чтобы иметь буфер из 2 элементов вместо буфера из 1 элемента и измерить, сколько времени потребуется программе для поиска и печати всех простых чисел с использованием 2, 3 и 4 потребительских потоков. Вот мой код. Я попробовал поискать в интернете и ничего не нашел. Не могли бы вы мне помочь? Мой код приведен ниже.

Что я уже пробовал:

#include <stdio.h>
#include <pthread.h>
#define MAX 1234568500

pthread_mutex_t the_mutex;
pthread_cond_t condc, condp;
int buffer = 0;

unsigned long long int isPrime(unsigned long long int x)
{
	int i;
	
	for(i=2;i<=x/2;++i)
	{
		if(x % i == 0)
		{
			return -1;
		}
	}
	
	return x;
}

void *producer(void *ptr)
{
	unsigned long long int i;
	for(i=1234567800;i<=MAX;i++)
	{
		pthread_mutex_lock(&the_mutex);
		
		while(buffer!=0)
			pthread_cond_wait(&condp,&the_mutex);
		
		buffer = i;
		pthread_cond_signal(&condc);
		pthread_mutex_unlock(&the_mutex);
	}
	
	pthread_exit(0);
}

void *consumer(void *ptr)
{
	unsigned long long int i;
	for(i=1234567800;i<=MAX;i++)
	{
		pthread_mutex_lock(&the_mutex);
		
		while(buffer==0)
			pthread_cond_wait(&condc,&the_mutex);
		
		if(isPrime(buffer)!=-1)
			printf("%d\n",isPrime(buffer));
			
		buffer = 0;
		pthread_cond_signal(&condp);
		pthread_mutex_unlock(&the_mutex);
	}
	pthread_exit(0);
}

int main(int argc, char **argv)
{
	int num_args = argc - 1
	pthread_t pro,con;
	
	pthread_mutex_init(&the_mutex,0);
	
	pthread_cond_init(&condc,0);
	pthread_cond_init(&condp,0);
	
	pthread_create(&con,0,consumer,0);
	pthread_create(&pro,0,producer,0);
	
	pthread_join(pro,0);
	pthread_join(con,0);
	
	pthread_cond_destroy(&condc);
	pthread_cond_destroy(&condp);
	
	pthread_mutex_destroy(&the_mutex);
	
	return 0;
}

2 Ответов

Рейтинг:
2

Rick York

I have been thinking about your first problem for a while and I think I have an algorithm in mind. It has to do with dividing the work between the threads. The thing is, you probably won't see much improvement over a single-threaded version until you get to really big numbers. What ever. You wanted a multi-threaded version so here is one possibility. The first thing to do is what most prime finders do : test the value for divisibility by 2. If it is then it's not a prime number so get that out of the way first because then you eliminate half of the possibilities. Then you always start at 3 and check every odd number after it since the even ones are already ruled out.

Вот тут-то и возникает разделение рабочей части. Каждому потоку присваивается значение шага. С одной нитью шаг равен 2. С двумя нитями шаг равен 4. Это приводит к тому, что значение шага в два раза превышает количество потоков. Соответственно, отправной точкой будет :

startingPoint = 3 + ( ( threadIndex - 1 ) * 2 );
Это означает, что начальные точки с четырьмя нитями будут равны 3 для нити 1, 5 для нити 2, 7 для нити 3 и 9 для нити 4.

С этими значениями вы можете записать свою тестовую функцию в виде :
typedef unsigned long long  ULL;

int IsPrime( ULL value, int threadIndex, int threadCount )
{
    ULL strideValue = 2 * (ULL) threadCount;
    ULL lastValue = value / 2;                              // stop testing here
    ULL testValue = 3 + ( ( (ULL) threadIndex - 1 ) * 2 );  // start testing here
    while( testValue <= lastValue )
    {
        if( ( value % testValue ) == 0 )
            return 0;                       // nope, we found a factor
        testValue += strideValue;
    }
    return 1;   // yes, it is a prime
}
Следующее, что нужно сделать, это выяснить, как потоки будут сообщать о своих результатах. Существует большое разнообразие способов сделать это. Одним из них было бы иметь одно результирующее значение и счетчик, который сообщает вам, сколько потоков отчиталось. Доступ к переменным будет контролироваться мьютексом. Когда поток завершает работу, он получает мьютекс, устанавливает значение результата в true только в том случае, если его результат равен true (если false, то оставьте его в покое), а затем увеличивает счетчик. Если поток обнаруживает, что он был последним (счетчик == количество потоков), он подает сигнал, указывающий на то, что тест завершен. После всего этого он освобождает мьютекс.

Следующий шаг - запустить и подать сигнал потокам. Эту часть я оставлю вам, так как, похоже, вы используете библиотеку pthread, и я не могу вам в этом помочь. Я знаю, как работают потоки и сигналы в целом, но не эту библиотеку.

Существуют различные способы использования этого алгоритма, в зависимости от того, как вы хотите проверить. Алгоритм IsPrime был написан при условии, что потоки тестируют одно значение. Еще один способ сделать подобное тестирование - построить список простых чисел. Для этого вы будете использовать универсальную функцию IsPrime, написанную для одного потока, но вы будете распределять значения для тестирования, как это делается в этой функции IsPrime, с различными значениями начала и шага, в зависимости от количества потоков и индекса. Тогда вам понадобится массив результатов со счетчиком, управляемым мьютексом.


Rick York

Кстати, в последнее время я работаю с CUDA, и именно так в ней распараллеливается код. Я могу себе представить, что эта программа распараллелена для работы с графическими процессорами, и она будет очень быстрой на больших числах.

Рейтинг:
1

Patrice T

Цитата:
Как изменить программу для использования нескольких потоков потребительского уровня

Прежде чем прибегать к многопоточности, первое, что нужно сделать,-это убедиться, что тестируемый алгоритм оптимизирован.
Ваш код-это очень неэффективный вариант "пробного подразделения", бывает, что простая оптимизация кода намного превосходит любую многопоточную вариацию вашего кода.
Смотрите мою статью, чтобы получить представление о том, как оптимизировать алгоритм пробного деления: Целочисленная Факторизация: Алгоритм Пробного Деления[^]

Ваш алгоритм определяет, является ли число простым, находя фактор, возвращая фактор вместо -1, имеет гораздо больше применений, чем просто говорит, является ли оно простым или нет.


Member 14764665

Спасибо, я очень ценю этот ответ. Нам дали этот код в классе и просто изменили код, чтобы добавить эти функции