2022-10-27 21:45:59 +02:00
|
|
|
#include<stdio.h>
|
|
|
|
#include <pthread.h>
|
2022-11-07 18:27:27 +01:00
|
|
|
#include <omp.h>
|
|
|
|
#include <stdlib.h>
|
|
|
|
#include <unistd.h>
|
2022-10-27 21:45:59 +02:00
|
|
|
|
|
|
|
#define N_THREADS 1
|
2022-11-07 18:27:27 +01:00
|
|
|
#define N_STEPS 200
|
|
|
|
#define N_NUMBERS_CALCULATED 100000
|
2022-10-27 21:45:59 +02:00
|
|
|
|
2022-11-07 18:27:27 +01:00
|
|
|
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
|
|
|
|
pthread_spinlock_t alive_threads_lock;
|
|
|
|
pthread_spinlock_t produced_numbers_lock;
|
2022-10-27 21:45:59 +02:00
|
|
|
|
2022-11-07 18:27:27 +01:00
|
|
|
int amicable_numbers[N_NUMBERS_CALCULATED];
|
2022-10-27 21:45:59 +02:00
|
|
|
long produced = 0;
|
2022-11-07 18:27:27 +01:00
|
|
|
int threads_alive = 0;
|
2022-10-27 21:45:59 +02:00
|
|
|
|
|
|
|
int calculate_amicable_number(int number) {
|
|
|
|
for(int i=1; i< number; i++){
|
|
|
|
if(number % i == 0){
|
|
|
|
number = number + i;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
return number;
|
|
|
|
}
|
|
|
|
|
|
|
|
void *calculate_amicable_number_invterval(void * arg) {
|
2022-11-07 18:27:27 +01:00
|
|
|
int *myrank = (int *)arg;
|
|
|
|
long mystart = (int)(N_NUMBERS_CALCULATED/ (double)N_THREADS * *myrank);
|
|
|
|
long myend = (int)(N_NUMBERS_CALCULATED / (double)N_THREADS * (*myrank + 1));
|
|
|
|
|
|
|
|
for(int i = mystart; i < myend; i++) {
|
|
|
|
amicable_numbers[i] = calculate_amicable_number(i);
|
|
|
|
}
|
|
|
|
|
2022-10-27 21:45:59 +02:00
|
|
|
return NULL;
|
|
|
|
}
|
|
|
|
|
2022-11-07 18:27:27 +01:00
|
|
|
int not_all_numbers_calculated() {
|
|
|
|
int ret = 0;
|
|
|
|
pthread_spin_lock(&produced_numbers_lock);
|
|
|
|
if(produced < N_NUMBERS_CALCULATED)
|
|
|
|
ret = 1;
|
|
|
|
pthread_spin_unlock(&produced_numbers_lock);
|
|
|
|
return ret;
|
|
|
|
}
|
|
|
|
|
|
|
|
int is_there_space_for_new_thread() {
|
|
|
|
int ret = 0;
|
|
|
|
pthread_spin_lock(&alive_threads_lock);
|
|
|
|
if (threads_alive < N_THREADS)
|
|
|
|
ret = 1;
|
|
|
|
pthread_spin_unlock(&alive_threads_lock);
|
|
|
|
return ret;
|
|
|
|
}
|
|
|
|
|
2022-10-27 21:45:59 +02:00
|
|
|
int main() {
|
2022-11-07 18:27:27 +01:00
|
|
|
pthread_spin_init(&alive_threads_lock, PTHREAD_PROCESS_PRIVATE);
|
|
|
|
pthread_spin_init(&produced_numbers_lock, PTHREAD_PROCESS_PRIVATE);
|
|
|
|
pthread_t t[N_THREADS];
|
|
|
|
int p[N_THREADS];
|
|
|
|
|
|
|
|
double dt = omp_get_wtime();
|
|
|
|
|
|
|
|
for (int i = 0; i<N_THREADS; i++)
|
|
|
|
{
|
|
|
|
p[i] = i;
|
|
|
|
pthread_create(&t[i], NULL, calculate_amicable_number_invterval, (void *)&p[i]);
|
|
|
|
}
|
|
|
|
|
|
|
|
for (int i = 0; i<N_THREADS; i++)
|
|
|
|
pthread_join(t[i], NULL);
|
|
|
|
|
|
|
|
dt = omp_get_wtime() - dt;
|
2022-10-27 21:45:59 +02:00
|
|
|
|
2022-11-07 18:27:27 +01:00
|
|
|
for(int i = 0; i < N_NUMBERS_CALCULATED; i++){
|
|
|
|
printf("%d, ", amicable_numbers[i]);
|
2022-10-27 21:45:59 +02:00
|
|
|
}
|
|
|
|
|
2022-11-07 18:27:27 +01:00
|
|
|
printf("\nExecution time: %lf\n", dt);
|
2022-10-27 21:45:59 +02:00
|
|
|
return 0;
|
2022-11-07 18:27:27 +01:00
|
|
|
|
|
|
|
/// 10 000 korakov
|
|
|
|
/// 1 THREAD: 14.173247
|
2022-11-07 21:42:44 +01:00
|
|
|
/// 2 THREADS: 10.877419, speedup: 1.3029972459459362
|
|
|
|
/// 4 THREADS: 6.838137, speedup: 2.0726766661738423
|
|
|
|
/// 8 THREADS: 5.327306, speedup: 2.66049049932555
|
|
|
|
/// 16 THREADS: 3.964736, speedup: 3.5748274286106314
|
2022-10-27 21:45:59 +02:00
|
|
|
}
|