0

私は Linux で作業していますが、マルチスレッドとシングル スレッドの両方で 340 ミリ秒かかります。誰かが私がやっていることの何が悪いのか教えてもらえますか?

これが私のコードです

#include<time.h>
#include<fstream>
#define SIZE_OF_ARRAY 1000000
using namespace std;

struct parameter
{
        int *data;
        int left;
        int right;
};
void readData(int *data)
{
        fstream iFile("Data.txt");
        for(int i = 0; i < SIZE_OF_ARRAY; i++)
                iFile>>data[i];
}

int threadCount = 4;

int Partition(int *data, int left, int right)
{
        int i = left, j = right, temp;
        int pivot = data[(left + right) / 2];
        while(i <= j)
        {
                while(data[i] < pivot)
                        i++;
                while(data[j] > pivot)
                        j--;
                if(i <= j)
                {
                        temp = data[i];
                        data[i] = data[j];
                        data[j] = temp;
                        i++;
                        j--;
                }
        }
        return i;
}

void QuickSort(int *data, int left, int right)
{
        int index = Partition(data, left, right);
        if(left < index - 1)
                QuickSort(data, left, index - 1);
        if(index < right)
                QuickSort(data, index + 1, right);
}

//Multi threading code starts from here
void *Sort(void *param)
{
        parameter *param1 = (parameter *)param;
        QuickSort(param1->data, param1->left, param1->right);
        pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
        clock_t start, diff;
        int *data = new int[SIZE_OF_ARRAY];
        pthread_t threadID, threadID1;
        pthread_attr_t attr;
        pthread_attr_init(&attr);
        pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
        pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
        parameter param, param1;
        readData(data);
        start = clock();
        int index = Partition(data, 0, SIZE_OF_ARRAY - 1);
        if(0 < index - 1)
        {
                param.data = data;
                param.left = 0;
                param.right = index - 1;
                pthread_create(&threadID, NULL, Sort, (void *)&param);
        }
        if(index < SIZE_OF_ARRAY - 1)
        {
                param1.data = data;
                param1.left = index + 1;
                param1.right = SIZE_OF_ARRAY;
                pthread_create(&threadID1, NULL, Sort, (void *)&param1);
        }
        pthread_attr_destroy(&attr);
        pthread_join(threadID, NULL);
        pthread_join(threadID1, NULL);
        diff = clock() - start;
        cout<<"Sorting Time = "<<diff * 1000 / CLOCKS_PER_SEC<<"\n";
        delete []data;
        return 0;
}
//Multithreading Ends here

Single thread main function
int main(int argc, char *argv[])
{
        clock_t start, diff;
        int *data = new int[SIZE_OF_ARRAY];
        readData(data);
        start = clock();
        QuickSort(data, 0, SIZE_OF_ARRAY - 1);
        diff = clock() - start;
        cout<<"Sorting Time = "<<diff * 1000 / CLOCKS_PER_SEC<<"\n";
        delete []data;
        return 0;
}
//Single thread code ends here
some of functions single thread and multi thread use same
4

3 に答える 3

2

clock壁時間ではなく、合計CPU時間を返します。

2つのCPUと2つのスレッドがある場合、両方のスレッドを同時に実行clockすると、2秒のCPU時間(各スレッドのCPU時間の合計)が返されます。

したがって、結果は完全に期待されます。CPUの数に関係なく、すべてのCPUで合計された合計実行時間は同じになります。

于 2012-06-25T10:36:41.097 に答える
1

メインスレッドから Partition を一度呼び出すことに注意してください...

コードは同じメモリ ブロックで動作するため、他の CPU が同じメモリ ブロックにアクセスすると、CPU が動作しなくなります。データが非常に大きい場合を除き、このようなヒットが多数発生する可能性があります。

最後に、アルゴリズムを 1 つのスレッドで実行したときにメモリ速度で動作する場合、スレッドを追加しても役に立ちません。しばらく前に画像データでこのようなテストを行いましたが、複数のスレッドを使用すると合計速度が低下しました。これは、プロセスがメモリを集中的に使用するため、両方のスレッドがメモリにアクセスするために競合していたためです...そして結果は、スレッドをまったく持たないよりも悪いものでした。

今日の非常に高速なコンピューターを本当に高速にしているのは、1 台のコンピューターで多数のスレッド (またはプロセス) を実行するのではなく、コンピューターごとに 1 つの非常に集中的なプロセスを実行することです。

于 2012-06-25T10:23:04.503 に答える
1

24 個のスレッドがぶら下がっているプロデューサー/コンシューマー キューでスレッド プールを構築します。データを 2 つに分割し、マージソート タスク オブジェクトをプールに発行します。マージソート オブジェクトは、さらにマージソートのペアをキューに発行し、マージソート オブジェクトが [L1 キャッシュ-サイズデータ]。次に、オブジェクトはそのデータをクイックソートし、完了を親タスクに通知します。

それが 24 コアで目もくらむほど速くないことが判明した場合は、スレッドについての投稿を停止します..

..そして、複数の並べ替えを並行して処理します。

..そして、プールは他のタスクに使用できます。

.. そして、パフォーマンスを破壊し、デッドロックを生成する join()、synchronize() はありません (オブジェクト ref をプッシュするのに十分な時間だけロックする PC キューを除く場合)、スレッド作成のオーバーヘッドはありません。危険なスレッド停止/終了/破棄コードはありません。床屋のように、待機はありません。スレッドがタスクを終了するとすぐに、別のタスクを取得できます。

スレッドのマイクロ管理もチューニングも必要ありません (次世代のボックスに備えて、現在 64 個のスレッドを作成できます)。スレッド数を調整可能にすることができます-実行時にスレッドを追加するか、ポイズンピルをキューに入れていくつかを削除します。

スレッドへの参照はまったく必要ありません - オフに設定するだけです (パラメーターとしてキューを渡します)。

于 2012-06-25T12:56:21.047 に答える