c - ハイパーキューブ構造を使用した C の単純な並列マージソート

Question

ハイパーキューブ通信の概念を理解するのに役立つ単純な並列マージソート アルゴリズムを作成しようとしています。ランダムな整数の配列を生成し、スレッドを割り当ててデータをソートする C プログラムがあります。各スレッドは、データのサブリストを順次ソートし、他のスレッドと比較交換操作を実行してサブリストをマージします。以下はスレッド関数です。

void *th_fun(void* args)
{
    int i, j;
    int my_id             = *((int*)args);

    int chunk_size        = N_DATA/N_THREADS;
    int start_index       = my_id*chunk_size;

    //set up the memory this thread will use
    th_mem[my_id].my_data = &data[start_index];
    th_mem[my_id].partner_data = malloc(sizeof(int)*chunk_size);
    for(i = 0; i < chunk_size; i++)
        th_mem[my_id].partner_data [i] = 0;

    //sort my data serially, should use a mergesort
    qsort((void*)th_mem[my_id].my_data, chunk_size, sizeof(int), compare);

    //wait for all threads to finish sorting
    barrier_simple();

    //compare-exchange accross hypercube
    int partner_id, op;
    int logth = log(N_THREADS)/log(2);
    for(i = 0; i < logth; i++)
    {
        partner_id = my_id ^ (int)pow(2,logth-i-1);

        //send my data to partner
        for(j = 0; j < chunk_size; j++)
        {
            th_mem[partner_id].partner_data[j] = th_mem[my_id].my_data[j];
        }

        //wait for all data to be sent
        barrier_simple();

        //get the lowest or highest elements between my_data, partner_data
        int x = my_id & (int)pow(2,logth-i-1);
        op = (x > 0 ? 1:-1);
        int* output = merge(th_mem[my_id].my_data, th_mem[my_id].partner_data, 
                            chunk_size, op);

        //save results
        for(j = 0; j < chunk_size; j++)
        {
            th_mem[my_id].my_data[j] = output[j];
        }
        free(output);

        //wait for all data to be merged
        barrier_simple();
    }

    free(th_mem[my_id].partner_data);
    pthread_exit(args);
}

4 つのスレッドでソートされた 12 のデータ要素を使用したサンプル実行 (出力はチャンク化され、どのスレッドがそのデータを担当しているかを示します):

./parallel_merge 12 4
Unsorted:
0:924 674 704 
1:495 554 645 
2:979 285 119 
3:878 80 620 

Serial sort: 
0:80 119 285 
1:495 554 620 
2:645 674 704 
3:878 924 979 

Parallel sort: 
0:80 119 285 
1:495 554 674 
2:620 645 704 
3:878 924 979 

ご覧のとおり、並列ソートは完全に正しいわけではありません (パフォーマンスの考慮事項を除けば、ofc)。多くの gdb を実行しましたが、ハイパーキューブ交換がうまくいかない理由を特定できません。どんな助けでも大歓迎です。私の参照は、ハイパーキューブテンプレートとマージソートでした