masabahmad / crono Goto Github PK

It seems to me in this file CRONO/apps/triangle_counting/sorted_neighbors_tri_lock.cc, line 103-110

              int counter = 0;
              //printf("\n %d %d %d", neighbor, edges[neighbor], it);
              while(counter < edges[neighbor])
              {
                counter++;
              }
              if(edges[neighbor] == counter)
                Total_tid[tid]++;

is just doing Toal_tid[tid]++;

What's the point to write a while loop to increment the counter? Or am I missing something?

Hi Masab,

I have a couple of questions :)

1. Here https://github.com/masabahmad/CRONO/blob/master/apps/community/community_lock.cc#L165 W_f[v][i] is protected with a mutex, could you explain why it is needed since it seems that each thread has their own partition over vertices and they don't overlap?
2. Here https://github.com/masabahmad/CRONO/blob/master/apps/community/community_lock.cc#L182 each comm[i] in all of the threads would be set to the same value since the right hand side contains only constants. Is there smth missing or smth I don't understand?

Thanks,

Yunduz

I was running some tests with 'bc' benchmark but kept running into "Corrupted double-linked list" errors. Upon further investigation I noticed this part in the code responsible for memory allocation for sigma matrix in main.

//Memory allocations for the input graph
int** W = (int**) malloc(N*sizeof(int*));
int** W_index = (int**) malloc(N*sizeof(int*));
int** sigma = (int**) malloc(P*sizeof(int*));
for(int i = 0; i < N; i++)
{
     //W[i] = (int *)malloc(sizeof(int)*N);
     delta[i]=0;
     avg[i]=0;
     int ret = posix_memalign((void**) &W[i], 64, DEG*sizeof(int));
     int re1 = posix_memalign((void**) &W_index[i], 64, DEG*sizeof(int));
     int re2 = posix_memalign((void**) &sigma[i], 64, N*sizeof(int));
     if (ret != 0 || re1!=0 || re2!=0)
     {
         fprintf(stderr, "Could not allocate memory\n");
         exit(EXIT_FAILURE);
     }
}

If I understand correctly, sigma is supposed to be a 2D matrix (PxN) where P in the number of threads and N is the number of vertices. However, the for loop goes for N iterations and in each iteration allocates memory for a row in sigma. But sigma has P rows and not N!!!.

I separated the sigma memory allocation in another loop and the problem I was having seems to have gone away. Here are my modified memory allocation loops.

for(int i = 0; i < N; i++)
{
     //W[i] = (int *)malloc(sizeof(int)*N);
     delta[i]=0;
     avg[i]=0;
     int ret = posix_memalign((void**) &W[i], 64, DEG*sizeof(int));
     int re1 = posix_memalign((void**) &W_index[i], 64, DEG*sizeof(int));
     //int re2 = posix_memalign((void**) &sigma[i], 64, N*sizeof(int));
     //if (ret != 0 || re1!=0 || re2!=0)
     if (ret != 0 || re1!=0)
     {
         fprintf(stderr, "Could not allocate memory\n");
         exit(EXIT_FAILURE);
     }
}

// The new sigma memory allocation loop
for(int i = 0; i < P; i++)
{
    int re2 = posix_memalign((void**) &sigma[i], 64, N*sizeof(int));
    if (re2!=0)
    {
        fprintf(stderr, "Could not allocate memory\n");
        exit(EXIT_FAILURE);
    }
}

Is my understanding and fix correct or did I misinterpret something in the code?

Hi, as the title suggests, I think there's an out of bound error in apsp (although possibly on other benchmarks too, I haven't actually looked there yet).

Here's the details:

• In do_work there's a posix_memalign((void**) &D, 64, N * sizeof(int)) and a similar one for Q. This clearly allocates an N sized array.
• In initialize_single_source there's a for (int i = 0; i < N + 1; i++) which obviously works on an N+1 sized array.
• In initialize_single_source there's also a D[source] = 0; where in the last iteration source is N rather than N-1. So also an N+1 sized array.
• In do_work, the way next_source is defined and incremented also makes the while loop go from 0 to N+1, which is what actually causes the previous issue to arise.

Now, there's only one thing I am not clear on, basically what is the proper fix? Is the allocation supposed to allocate an N+1 sized array? Or are the indices wrong and should only go from 0 to N?

PS: for help debugging this, compile with -fsanitize=address and these errors will be detected as you run.

Thanks

Hello,

For triangle counting I've tried to provide a file with a simple, 3 nodes graph which makes one triangle like this:
0 1
1 2
2 0

However, the output says:
.gr graph with parameters: Vertices:1 Degree:1

File Read, Largest Vertex:1
Threads Joined!
Time Taken:
0.000009 seconds
Triangles=0

This seems to be incorrect. Could you let me know if my file format is wrong or it's something else?

Thanks,

Yunduz

Hi Masab,

In your paper it says: "The final loop is statically divided amongst threads, with each thread reading shortest path values and updating the centralities via atomic locks." I noticed that in the implementation there is no part where threads use atomic locks. I am wondering if you had an earlier version that did and if you could post it?

Thanks,

Yunduz