В настоящее время я создаю распараллеленный код, используя MPI, чтобы узнать, сколько треугольников в любом данном графике. Пока мой код может успешно получить правильное количество треугольников (я знаю, потому что у меня есть сериализованная версия того же самого кода, который работает намного медленнее) до определенного момента. Я бы сказал, что после примерно 6000 узлов мои потоки больше не читаются внутри функции (я обнаружил это, посмотрев на потоки в основной функции по сравнению с подсчетом, превратился ли поток в функцию).
Для справки, сам код принимает число узлов, ребер, начальное число и степень.
Для этой цели мы будем игнорировать семя и степень, поскольку они прекрасно работают, когда все работает.
Редактировать: Я быстро объясню соглашение о присвоении имен для потерянных. По сути, нам дан график из нескольких узлов вместе с ребрами, соединяющими их (подумайте о смежности) Теперь задача программы - пройти каждую вершину u и взять другую вершину v в графе, чтобы определить, есть ли у них соответствующая вершина w, соединяющая их. В этой ситуации, поскольку в C нет никаких bools, мы будем использовать int для ребер uv, uw и vw. Таким образом, если есть соединительное ребро, мы можем превратить их в 1. Если они все равны 1, то мы нашли треугольник и теперь можем добавить его в глобальную переменную. Пусть будет известно, что код здесь в циклах for для вычисления треугольников является на 100% правильным и не является вопросом вопроса. Скорее вопрос касается проблемы использования pthreads на более высоких узлах.
Вот код ниже:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "graph.h"
#define MAX_N 1000000
#define MAX_E 2*MAX_N // must be at least twice MAX_N
GRAPH_t * G;
#define MAX_THREADS 65536
#include <pthread.h>
int thread_id[MAX_THREADS]; // User defined id for thread
pthread_t p_threads[MAX_THREADS];// Threads
pthread_attr_t attr; // Thread attributes
pthread_mutex_t lock_count; // Protects minimum, count
unsigned int parallelCount = 0;
unsigned int threadCount = 0;
void *count_ParallelTriangles(void *threadID) {
int u = *((int *)threadID);
int counter = 0;
unsigned int v, w, e, uv, uw, vw;
for (v = u + 1; v < G->n; v++) {
uv = 0;
for (e = G->V_ptr[v]; e < G->V_ptr[v + 1]; e++) {
if (G->E_v[e] == u) {
uv = 1; // Edge (u,v) exists
}
}
if (uv == 1) {
for (w = v + 1; w < G->n; w++) {
uw = 0; vw = 0;
for (e = G->V_ptr[w]; e < G->V_ptr[w + 1]; e++) {
if (G->E_v[e] == u) uw = 1; // Edge (u,w) exists
if (G->E_v[e] == v) vw = 1; // Edge (v,w) exists
}
if ((uv == 1) && (vw == 1) && (uw == 1)) {
counter += 1;
}
}
}
}
//if (counter > 0) {
pthread_mutex_lock(&lock_count);
threadCount += 1;
parallelCount += counter;
pthread_mutex_unlock(&lock_count);
//}
pthread_exit(NULL);
}
и ниже, где он вызывается в основном
int main(int argc, char *argv[]) {
struct timespec start, stop;
float time_serial;
unsigned int num_nodes, num_edges, seed, num_triangles, max_degree;
if (argc != 5) {
printf("Use: <executable_name> <num_nodes> <num_edges> <seed>
<max_degree>\n");
exit(0);
}
if ((num_nodes = atoi(argv[argc-4])) > MAX_N) {
printf("Maximum number of nodes allowed: %u\n", MAX_N);
exit(0);
};
if ((num_edges = atoi(argv[argc-3])) > MAX_E) {
printf("Maximum number of edges allowed: %u\n", MAX_E);
exit(0);
};
if (num_edges < 2*num_nodes) {
num_edges = 2*num_nodes;
printf("Number of edges must be at least twice the number of nodes: changing
num_edges to %u\n", num_edges);
exit(0);
};
seed = atoi(argv[argc-2]);
max_degree = atoi(argv[argc-1]);
// Initialize graph
G = init_graph ( num_nodes, num_edges, seed, max_degree );
float time_parallel;
//Initialize Pthread
pthread_mutex_init(&lock_count, NULL);
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
clock_gettime(CLOCK_REALTIME, &start);
for (int u = 0; u < num_nodes; u++) {
thread_id[u] = u;
pthread_create(&p_threads[u], &attr, count_ParallelTriangles, (void
*)&thread_id[u]);
}
for (int u = 0; u < num_nodes; u++) {
pthread_join(p_threads[u], NULL);
}
clock_gettime(CLOCK_REALTIME, &stop);
time_parallel = (stop.tv_sec - start.tv_sec)
+ 0.000000001*(stop.tv_nsec - start.tv_nsec);
printf("Thread active: %d\n", threadCount);
printf("Parallel execution time = %f s\n", time_parallel);
// Print results
printf("G: Nodes = %u, Edges = %u, Triangles = %u\n", G->n, G->m, parallelCount);
pthread_attr_destroy(&attr);
pthread_mutex_destroy(&lock_count);
return 0;
}
И, наконец, вот мой вывод, когда он работает правильно. Максимальное значение ребер равно 1000000, поэтому оно рассчитывает максимальное количество ребер, которое может поместиться в пределах его средней степени, которая в данном случае составляет 234110.
./triangles.exe 4096 1000000 0 0
Serial execution time = 16.181034 s
G: Nodes = 4096, Edges = 234110, Triangles = 651015
Thread active: 4096
Parallel execution time = 0.843587 s
G: Nodes = 4096, Edges = 234110, Triangles = 651015
Мы видим, что вышесказанное работает правильно, так как количество потоков равно количеству объявленных узлов. Однако, если мы увеличим узлы всего на несколько тысяч, мы увидим, что вывод больше не работает правильно, несмотря на то, что все еще идет довольно быстро:
./triangles.exe 6000 1000000 0 0
Serial execution time = 48.326824 s
G: Nodes = 6000, Edges = 413845, Triangles = 1207058
Thread active: 2061
Parallel execution time = 1.471421 s
G: Nodes = 6000, Edges = 413845, Triangles = 1079834
В приведенном выше случае, если бы мы запустили этот пример еще несколько раз, количество потоков будет изменяться между каждым вызовом, и вычисляемые им треугольники будут изменяться в результате (так как каждый счетчик треугольников зависит от потока, правильно его пропускающего глобальная переменная). Серийный счет и время останутся относительно непротиворечивыми, поскольку это уже правильно.
EDIT:
Добавлен дополнительный код для основного файла.
Ниже приведен заголовочный файл для создания графика
typedef struct _graph {
unsigned int n; // Number of vertices in the graph
unsigned int m; // Number of edges in the graph
unsigned int * E_u; // Edge i = (E_u[i],E_v[i])
unsigned int * E_v; //
unsigned int * V_ptr; // Edges incident on vertex u
// have ids V_ptr[u] ... V_ptr[u+1]-1
} GRAPH_t;
GRAPH_t * init_graph ( unsigned int n, unsigned int m, unsigned int seed,
unsigned int max_degree ) {
GRAPH_t * G = (GRAPH_t *) calloc(1, sizeof(GRAPH_t));
unsigned u, v, e, nbrs, first, lastplus1, maxvalue;
double fraction;
G->n = n;
G->E_u = (unsigned int *) calloc(m, sizeof(unsigned int));
G->E_v = (unsigned int *) calloc(m, sizeof(unsigned int));
G->V_ptr = (unsigned int *) calloc((G->n+1), sizeof(unsigned int));
srand48(seed);
unsigned int count = 0;
// Generate edges
G->V_ptr[0] = count;
for (u = 1; u < G->n; u++) {
G->V_ptr[u] = count;
switch (max_degree) {
case 0: // max_degree = 0 => max_degree = sqrt(n)
nbrs = sqrt(G->n); if (nbrs > u) nbrs = u;
break;
default:
nbrs = max_degree; if (nbrs > u) nbrs = u;
break;
}
first = G->V_ptr[u];
lastplus1 = first + nbrs; if (lastplus1 > m) lastplus1 = m;
if (first < lastplus1) {
for (e = first; e < lastplus1; e++)
G->E_v[e] = ((unsigned int) lrand48()) % G->n;
maxvalue = G->E_v[first];
for (e = first+1; e < lastplus1; e++) {
G->E_v[e] += G->E_v[e-1];
maxvalue = G->E_v[e];
}
for (e = first; e < lastplus1; e++) {
fraction = ((double) G->E_v[e])/(maxvalue+1+(lrand48()%G->n));
G->E_v[e] = (unsigned int) (fraction * u);
}
// Generate edges incident at u
G->E_u[count] = u;
G->E_v[count] = G->E_v[count];
count++;
for (e = first+1; e < lastplus1; e++) {
if (G->E_v[count-1] < G->E_v[e]) {
G->E_u[count] = u;
G->E_v[count] = G->E_v[e];
count++;
}
}
}
}
G->V_ptr[n] = count;
G->m = count-1; // Initialize number of edges
// Check graph
for (u = 0; u < G->n; u++) {
if (G->V_ptr[u] > G->V_ptr[u+1]) {
printf("Graph generation problem - 1!!!\n");
exit(0);
}
for (e = G->V_ptr[u]; e < G->V_ptr[u+1]; e++) {
if (G->E_u[e] != u) {
printf("Graph generation problem - 2!!!\n");
exit(0);
}
if (G->E_v[e] >= u) {
printf("Graph generation problem - 3!!!\n");
exit(0);
}
if ((e > G->V_ptr[u]) && (G->E_v[e] <= G->E_v[e-1])) {
printf("Graph generation problem - 4!!!\n");
exit(0);
}
}
}
return G;
}