strange behavior with array in function

[pater]

Hello All,

I noticed strange behavior with my splitSequence function in my program. I am writing parallel bubble search program with openMP. Everything is working ok in my laptop ( i5 ubuntu distro 64 bit ,paralleled for 4 or more threads ) but when i compile it and run on my university machine ( 16 cores with architecture x86-64, fedora distro) it assign different values to array spliSeqLen.

splitSequence function

void splitSequence (int thNums, int seqLen, int *seq, int *splitSeqLen, int **splitSeq)
{
    int i, j;
    int singleSeqLen = seqLen / thNums;
    int seqMod = seqLen % thNums;
    
    for (i = 0; i < thNums; i++)
        splitSeqLen[i] = singleSeqLen;
    
    for (i = thNums - 1; i >= thNums - seqMod; i--)
        splitSeqLen[i]++;
        
    printf("\n 1 \n");    
    for (i = 0; i < thNums; i++)
        printf("\nsplitSeqLen %d \n", splitSeqLen[i]);
        
    for (i = 0, j = 0; j < thNums; i+=splitSeqLen[j], j++)
        splitSeq[j] = &seq[i];
    
    printf("\n 2 \n");
    for (i = 0; i < thNums; i++)
        printf("\nsplitSeqLen %d \n", splitSeqLen[i]);
}

this code run on my laptop gives below results (sequence length 10, thread numbers 4)

1
splitSeqLen 2
splitSeqLen 2
splitSeqLen 3
splitSeqLen 3

2
splitSeqLen 2
splitSeqLen 2
splitSeqLen 3
splitSeqLen 3

code run on university machine (sequence length 10 , thread numbers 5) gives following results

1
splitSeqLen 2
splitSeqLen 2
splitSeqLen 2
splitSeqLen 2
splitSeqLen 2

2
splitSeqLen 33447984  <-- every run is different
splitSeqLen 0             <-- always 0
splitSeqLen 2
splitSeqLen 2
splitSeqLen 2

This array is not changed between these two dispays so i don't know why these two valuse are incorrect. The funniest thing is that on university machine this code runs ok for thread numbers < 4, above 4 it gives wrong results.

Below you will find all program

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <omp.h>


int compare (int *, int , int *);
void splitSequence (int , int, int *,int *, int **);
void mergeSequences (int , int , int *, int *, int **);
void displaySequence (int *, int);
void saveResult (int *, int, int, double, FILE*);


int main()
{
    int i, j, k, seqLen, seed, thNums, temp;
    int *seq;                                                            // array of sequence numbers
    int *sortedSeq;                                                        // array of sorted numbers
    int **splitSeq;                                                        // array of pointers of splitted sequences
    int *splitSeqLen;                                                    // array of splitted sequences' length                                    
    clock_t start, stop;
    FILE *fp;
    double execTime;
    char c;
    
    printf("Please enter sequence length : ");
    scanf("%i", &seqLen);
    printf("Please enter number of threads (max 16) : ");
    scanf("%i", &thNums);
    
    seq = (int *)malloc(seqLen * sizeof(*seq));                            // dynamically allocate memory for sequance array
    sortedSeq = (int *)malloc(seqLen * sizeof(*seq));                    // dynamically allocate memory for sorted numbers array
    splitSeq = (int **)malloc(thNums * sizeof(**splitSeq));                // dynamically allocate memory for splitted seq array
    splitSeqLen = (int *)malloc(thNums * sizeof(*splitSeqLen));            // dynamically allocate memory for splitted seq length array
    
    if (seq == NULL || splitSeq == NULL || splitSeqLen == NULL)
    {
        printf("Memory allocation error");
        return -1;        
    }  
     
    seed = time(NULL);                                                    // set randomization
    srand(seed);
    
    for (i = 0; i < seqLen; i++)                                        // get random numbers
        seq[i] = rand();
    
    //printf("\nDisplay randomized numbers ? (y\\n) : ");
    //scanf("%s", &c);
    
    //if (c == 'y')
    //    displaySequence(seq, seqLen);
    
    omp_set_num_threads(thNums);
    splitSequence(thNums, seqLen, seq, splitSeqLen, splitSeq);
    start = clock();
    printf("\nStart mp\n");
    
#pragma omp parallel private(i, j, k, temp) \
            firstprivate(splitSeqLen, thNums, splitSeq)        
    {    
#pragma omp for schedule(static)
        for (i = 0; i < thNums; i++)
        {
            printf("Thread number %d has stared sorting...\n",
                    omp_get_thread_num());
            for (j = 0; j < splitSeqLen[i] - 1; j++)
            {
                for (k = 0; k < splitSeqLen[i] - 1 - j; k++)
                {
                    if(splitSeq[i][k] > splitSeq[i][k+1])
                    {
                        temp =  splitSeq[i][k];
                        splitSeq[i][k] = splitSeq[i][k+1];
                        splitSeq[i][k+1] = temp;       
                    } 
                }
            }
            printf("Thread number %d has finished sorting...\n",
                    omp_get_thread_num());
        }
    }
    stop = clock();
    execTime = ((double) stop-start) / CLOCKS_PER_SEC;
    printf("\nSorting time - ");
    printf("%f", execTime);
    
    start = clock();
    mergeSequences(thNums, seqLen, sortedSeq, splitSeqLen, splitSeq);
    stop = clock();
    execTime = ((double) stop-start) / CLOCKS_PER_SEC;
    
    printf("\nMerging time - ");
    printf("%f", execTime);
    printf("\n\nWhat do you want ? :\n");
    printf("- Press 1 for saving results.\n");
    printf("- Press 2 for displaying results.\n");
    printf("- Press any other key for exit.\n");
    scanf("%s", &c);
    
    switch (c)
    {
        case '1':
            saveResult(sortedSeq, seqLen, thNums, execTime, fp);
            break;
        case '2':
            displaySequence(sortedSeq, seqLen);
            break;
        default :
            break;
    }
    
    free(seq);
    free(sortedSeq);
    free(splitSeq);
    free(splitSeqLen);
    
    return 0;
}


void splitSequence (int thNums, int seqLen, int *seq, int *splitSeqLen, int **splitSeq)
{
    int i, j;
    int singleSeqLen = seqLen / thNums;
    int seqMod = seqLen % thNums;
    
    for (i = 0; i < thNums; i++)
        splitSeqLen[i] = singleSeqLen;
    
    for (i = thNums - 1; i >= thNums - seqMod; i--)
        splitSeqLen[i]++;
        
    printf("\n 1 \n");    
    for (i = 0; i < thNums; i++)
        printf("\nsplitSeqLen %d \n", splitSeqLen[i]);
        
    for (i = 0, j = 0; j < thNums; i+=splitSeqLen[j], j++)
        splitSeq[j] = &seq[i];
    
    printf("\n 2 \n");
    for (i = 0; i < thNums; i++)
        printf("\nsplitSeqLen %d \n", splitSeqLen[i]);
}


void mergeSequences (int thNums, int seqLen, int *sortedSeq, int *splitSeqLen, int **splitSeq)
{
    int i, j, index;
    int indexes[thNums];
    int *comparedNums = (int *)malloc(thNums * sizeof(*comparedNums));
    
    for (i = 0; i < thNums; i++)
        indexes[i] = 0;
        
    for (i = 0; i < seqLen; i++)
    {
        
        for (j = 0; j < thNums; j++)
            comparedNums[j] = splitSeq[j][indexes[j]];
            
        index = compare(comparedNums, thNums, &sortedSeq[i]);
        
        if (indexes[index] < splitSeqLen[index]-1)
            indexes[index]++;
        else
            splitSeq[index][indexes[index]] = -1;    
    }
    
    free(comparedNums);
}


int compare (int *comparedNums, int thNums, int *min)
{
    int i, index;
    for (i = 0; i < thNums; i++)
    {
        if (comparedNums[i] >= 0)
        {
            *min = comparedNums[i];
            index = i;
            break;
        }
    }
            
    for (i = 0; i < thNums; i++)
    {
        if (comparedNums[i] <= *min && comparedNums[i] >= 0)
        {
            *min = comparedNums[i];
            index = i;
        }
    }
    
    return index;
}


void displaySequence (int *seq, int seqLen)
{
    int i;
    printf("\n");
    for (i = 0; i < seqLen; i++)
    {
        printf("%d", seq[i]);
        printf("\n");
    } 
}


void saveResult (int *seq, int seqLen, int thNums, double execTime, FILE *fp)
{
    int i;
    struct tm *ptr;
    char str[100];
    time_t timeValue;
    timeValue = time(NULL);
    ptr = localtime(&timeValue);
    strftime(str, 100, "%c", ptr);
    fp=fopen(str,"w");
    fprintf(fp,"<<<<< STATISTICS >>>>> \n");
    fprintf(fp,"Sequence length : %d\n", seqLen);
    fprintf(fp,"Used threads : %d\n", thNums);
    fprintf(fp,"Sorting time : %f\n", execTime);
    fprintf(fp,"<<<<< SEQUENCE >>>>> \n");
    
    for (i = 0; i < seqLen; i++)
        fprintf(fp,"%d\n", seq[i]);
}

i would be grateful for any help because i can not manage with it for fives days.

Thanks and regards,
Patryk

[grumpy]

Try editing the code samples so they are not rendered in your post as a single line. As is, the code is virtually impossible to read.

The most likely explanation is that you are running off the end of an array. For example, the caller supplies an array of 4 elements, but your code is accessing past the end (indices 0-3).

The other possibility, if you are using system threads, is that you have a synchronisation issue. If any thread is modifying some data, you need to ensure that it can't be preempted or interrupted by any other thread that modifies or reads the same data.

[pater]

i edited my code sorry for that. splitSequences is triggered before openMP directive so it runs as a singe thread and imo it doesn't run off the end of an array.

[msh]

splitSeq = (int **)malloc(thNums * sizeof(**splitSeq));

This looks suspicious to me. `sizeof(**splitSeq)` is equal to `sizeof(int)`, not `sizeof(*int)`, which is what you're assigning to the elements of `splitSeq` inside of `splitSequence()`.

[pater]

yes you are right. Wrong memory allocation of pointer table caused this behavior. Thanks a lot !! You saved me a lot of time.

Patryk