Последние потоки выполняются медленнее, чем первые потоки при записи в массив
Я пытаюсь оптимизировать генератор множеств Мандельброта, проблема в том, что я пытаюсь сделать его многопоточным с помощью функции _beginthread (). Компьютерная проблема, которую я решаю, заключается в запуске функции на 2D-плоскости, я пытаюсь запустить около 8 потоков одновременно, каждый из которых вычисляет часть (строку) 2D-массива, но я замечаю, что первые потоки что закончить, закончить намного быстрее, чем последние темы, которые заканчиваются. это вывод:
Starting thread 0
Starting thread 1
Starting thread 2
Starting thread 3
Starting thread 4
Starting thread 5
Starting thread 6
Starting thread 7
Ending thread 0 - Time taken: 1062ms
Ending thread 7 - Time taken: 1031ms
Ending thread 1 - Time taken: 1610ms
Ending thread 6 - Time taken: 1563ms
Ending thread 2 - Time taken: 10265ms
Ending thread 5 - Time taken: 10219ms
Ending thread 4 - Time taken: 31609ms
Ending thread 3 - Time taken: 31641ms
Каждый поток имеет одно и то же, но с разными номерами, я не понимаю, почему я получаю такие времена
Вот как я многопоточный это:
#define HEIGHT 4000
#define WIDTH 4000
#define MAX_THREADS 8
int const maxIterations = 150;
int bitmap[HEIGHT][WIDTH];
bool finishedThreads[MAX_THREADS];
void renderRow(void * arg) {
int startTime = GetTickCount();
int * threadNumPinter = (int*)arg;
int threadNum = *threadNumPinter;
int startRow = threadNum * (HEIGHT / MAX_THREADS);
for (int y = startRow; y <= startRow+(HEIGHT / MAX_THREADS); y++) {
for (int x = 0; x <= WIDTH; x++) {
double xx = (((double)x / (double)WIDTH) * 4.0) - 2.0;
double yy = (((double)y / (double)HEIGHT) * 4.0) - 2.0;
bitmap[x][y] = isPartOfSet(xx, yy) * 10;
}
}
threadNum = startRow / (HEIGHT / MAX_THREADS);
finishedThreads[threadNum] = true;
cout << "Ending thread " << threadNum << " - Time: " << GetTickCount() - startTime << "ms" << endl;
_endthread();
}int main() {
int startTime = GetTickCount();
HANDLE hThread;
HANDLE ghEvents[2];
DWORD dwThreadID;
int rowsPerThread = HEIGHT / MAX_THREADS;
int arg;
int threadIds[MAX_THREADS];
for (int i = 0; i < MAX_THREADS; i ++) {
threadIds[i] = i;
cout << "Starting thread " << i << endl;
arg = i;
_beginthread(renderRow, 0, &threadIds[i]);
Sleep(10);
}
bool done = true;//Wait for all threads to finish
while (1) {
for (int i = 0; i < MAX_THREADS; i++){
if (finishedThreads[i] == false)done = false;
}
if (done == true) break;
else done = true;
Sleep(20);
}
saveBitmap(WIDTH, HEIGHT);
cout << endl << "Rendered in " << double(GetTickCount() - startTime) / 1000.0 << " seconds" << endl;
cin.get();
main();
}
Очевидно, что кода больше, чем это, но я не думаю, что это повлияет на проблему. Что я здесь не так делаю? У меня была та же проблема с CUDA, поэтому я считаю, что именно так я реализую многопоточность. Благодарю.
Решение
В своем ответе я не буду затрагивать вопросы потоков / синхронизации или соображения по поводу кэширования — см. Другие ответы / комментарии для этого.
Моя точка зрения другая: ты пишешь, что «Каждый поток имеет то же самое, но с разными номерами». Если моя память о наборе Мандельброта мне не помешает, определение того, является ли точка членом набора (IOW, реализация вашей isPartOfSet функция, которую вы не предоставили) является итеративным процессом. Некоторые точки «выручают» быстро, некоторые — нет, и вам нужно продолжать итерацию до тех пор, пока вы не определите максимальное число элементов.
Итак, я говорю следующее: с вашим распараллеливанием «один большой блок на поток», вероятно, естественно, что ваши потоки занимают значительно различное количество времени.
Решение этой проблемы состоит в том, чтобы разделить проблему (то есть изображение) на более мелкие части, размер которых составляет не зависит от количества потоков, но должен быть выбран эмпирически, чтобы быть: а) не слишком большим, чтобы предотвратить неравное распределение работы (как в вашем примере с огромными блоками) и б) не настолько маленьким, чтобы вызвать чрезмерные организационные издержки.
Итак, теперь у вас есть M потоков и N блоков работы (с N >> M), и вам нужна реализация, которая позволяет каждому потоку работать в цикле, как
while (worktodo) fetch_a_chunk_of_work_and_do_it ()
Как реализован этот тип модели «производитель / потребитель» — я оставлю это для описания других (или для вас, чтобы гуглить :-))
Другие решения
Классический пример некорректного одновременного использования глобальной переменной.
bool finishedThreads[MAX_THREADS];
является глобальным и доступен из нескольких потоков (записано / прочитано). Вы не можете ожидать, что это сработает. В вашем случае вы даже не должны использовать эту переменную. Вместо этого вам следует ожидать события завершения потока.
Жесткое кодирование до 8 потоков ужасно, а как насчет двухъядерного ноутбука какого-то пользователя? std::thread::hardware_concurrency.
Сон ужасен. Ваша спин-петля — абсолютно НЕ правильный способ сделать это. Извините, просто честно.
использование std::thread и использовать join ждать их завершения. Еще лучше: делайте все, кроме одного рабочего элемента в других потоках, делайте один в главном потоке, затем присоединяйтесь к другим. Если имеется N процессоров, то вы должны создать N-1 потоки и сделать один элемент в главном потоке.
Зачем использовать API-интерфейсы только для Windows, когда классы библиотек C ++ существенно лучше?
Предлагаемый способ избежать Sleep
Если простого ожидания выхода из потока недостаточно (с помощью объединения, упомянутого выше), в более сложном сценарии следует использовать std::mutex, std::unique_lock, а также std::condition_variable.
У вас должна быть переменная, которая имеет значение true, когда происходит уведомление. В коде, который ждет, вы получаете мьютекс, проверяете этот флаг, и если он не установлен, вы вызываете wait на условной переменной.
В потоке, который уведомляет другой поток, вы получаете мьютекс, устанавливаете переменную flag, которую я упомянул, используете notify_one или же notify_all метод на условной переменной.
Посмотрите на это ссылка на cppreference. Основные, которые вы используете, это те, о которых я уже упоминал.