Накладные расходы из -за использования событий

Question

У меня есть пользовательский класс пула потоков, который создает некоторые потоки, которые каждый ожидает своего собственного события (сигнал). Когда новое задание добавляется в пул потоков, она разбудит первый бесплатный поток, чтобы выполнить задание.

Проблема заключается в следующей: у меня есть около 1000 петлей каждого около 10 000 итераций. Эти петли должны быть выполнены последовательно, но у меня есть 4 процессора. То, что я пытаюсь сделать, это разделить петли итерации 10 000 итерации на петли 4 2'500 итераций, то есть по одному на нить. Но я должен ждать, пока 4 маленьких петли закончится, прежде чем перейти к следующей «большой» итерации. Это означает, что я не могу объединить работу.

Моя проблема заключается в том, что использование пула потоков и 4 потока намного медленнее, чем выполнение заданий последовательно (наличие одного цикла, выполненного отдельным потоком, намного медленнее, чем выполнение непосредственно в основном потоке последовательно).

Я в Windows, поэтому я создаю события с CreateEvent() А потом подождите одного из них, используя WaitForMultipleObjects(2, handles, false, INFINITE) Пока главная нить не вызовет SetEvent().

Похоже, что все это событие (наряду с синхронизацией между потоками с использованием критических разделов) довольно дорого!

Мой вопрос: нормально ли, что использование событий занимает «много времени? Если это так, есть ли другой механизм, который я мог бы использовать, и это было бы менее дорогим по времени?

Вот какой -то код для иллюстрации (некоторые соответствующие детали, скопированные из моего класса пула потоков):

// thread function
unsigned __stdcall ThreadPool::threadFunction(void* params) {
    // some housekeeping
    HANDLE signals[2];
    signals[0] = waitSignal;
    signals[1] = endSignal;

    do {
        // wait for one of the signals
        waitResult = WaitForMultipleObjects(2, signals, false, INFINITE);

        // try to get the next job parameters;
        if (tp->getNextJob(threadId, data)) {
            // execute job
            void* output = jobFunc(data.params);

            // tell thread pool that we're done and collect output
            tp->collectOutput(data.ID, output);
        }

        tp->threadDone(threadId);
    }
    while (waitResult - WAIT_OBJECT_0 == 0);

    // if we reach this point, endSignal was sent, so we are done !

    return 0;
}

// create all threads
for (int i = 0; i < nbThreads; ++i) {
    threadData data;
    unsigned int threadId = 0;
    char eventName[20];

    sprintf_s(eventName, 20, "WaitSignal_%d", i);

    data.handle = (HANDLE) _beginthreadex(NULL, 0, ThreadPool::threadFunction,
        this, CREATE_SUSPENDED, &threadId);
    data.threadId = threadId;
    data.busy = false;
    data.waitSignal = CreateEvent(NULL, true, false, eventName);

    this->threads[threadId] = data;

    // start thread
    ResumeThread(data.handle);
}

// add job
void ThreadPool::addJob(int jobId, void* params) {
    // housekeeping
    EnterCriticalSection(&(this->mutex));

    // first, insert parameters in the list
    this->jobs.push_back(job);

    // then, find the first free thread and wake it
    for (it = this->threads.begin(); it != this->threads.end(); ++it) {
        thread = (threadData) it->second;

        if (!thread.busy) {
            this->threads[thread.threadId].busy = true;

            ++(this->nbActiveThreads);

            // wake thread such that it gets the next params and runs them
            SetEvent(thread.waitSignal);
            break;
        }
    }

    LeaveCriticalSection(&(this->mutex));
}

Answer 1

Если вы просто параллелизируют петли и используете VS 2008, я бы посоветовал посмотреть на OpenMP. Если вы используете Beta 1 Visual Studio 2010, я бы предложил посмотреть на Библиотека параллельных шаблонов, особенно "Параллель для" / "параллель для каждого" APIS или "Занятная группа Класс, потому что они, вероятно, будут делать то, что вы пытаетесь сделать, только с меньшим кодом.

Что касается вашего вопроса о производительности, здесь это действительно зависит. Вам нужно будет посмотреть, сколько работы вы планируете во время итераций и каковы затраты. Watformultipleobjects может быть довольно дорогим, если вы сильно его попадаете, и ваша работа невелика, поэтому я предлагаю использовать уже созданную реализацию. Вы также должны убедиться, что вы не работаете в режиме отладки, в рамках отладчика и что сами задачи не блокируют блокировку, ввод/вывод или распределение памяти, и вы не достигаете ложного обмена. Каждый из них имеет потенциал для разрушения масштабируемости.

Я бы посоветовал посмотреть на это под таким xperf F1 Profiler в Visual Studio 2010 Beta 1 (у него есть 2 новых режима параллелизма, которые помогают увидеть раздор) или Vtune Intel.

Вы также можете поделиться кодом, который вы выполняете в задачах, чтобы люди могли получить лучшее представление о том, что вы делаете, потому что ответ, который я всегда получаю с проблемами с производительностью, является первым «это зависит», а во -вторых, «Есть ли у вас профилировал это ".

Удачи

-Рик

Answer 2

Это выглядит для меня как модели потребительского производителя, который можно использовать с помощью двух семафоров, один охраняющий переполнение очереди, а другая - пустая очередь.

Вы можете найти некоторые детали здесь.

Answer 3

Да, WaitForMultipleObjects довольно дорого. Если ваша работа невелика, накладные расходы синхронизации начнут ошеломлять стоимость фактического выполнения работы, как вы видите.

Один из способов исправить это-объединить несколько рабочих мест в одну: если вы получаете «небольшую» работу (как бы вы оценивали такие вещи), храните ее где-нибудь, пока у вас не будет достаточно небольших рабочих мест, чтобы сделать одну работу разумного размера. Затем отправьте их все в рабочую ветку для обработки.

Альтернативно, вместо использования сигналов вы можете использовать очередь с одним чиновником с одной авторитетом для хранения ваших заданий. В этой модели каждая рабочая нить пытается снять задание из очереди. Когда он находит один, он выполняет работу; Если это не так, он спит в течение короткого периода времени, затем просыпается и снова пытается. Это снизит вашу задачу на накладные расходы, но ваши потоки займут процессор, даже если работы не предстоит сделать. Все зависит от точной природы проблемы.

Answer 4

Остерегайтесь, вы все еще просите следующую работу после того, как Endignal испускается.

for( ;; ) {
    // wait for one of the signals
    waitResult = WaitForMultipleObjects(2, signals, false, INFINITE);
    if( waitResult - WAIT_OBJECT_0 != 0 )
        return;
    //....
}

Answer 5

Это не должно быть таким дорогим, но если ваша работа практически не займет время, то накладные расходы потоков и синхронизации станут значительными. Такие пулы потоков, как этот, работают намного лучше для более длительных заданий или для тех, кто использует много IO вместо ресурсов процессора. Если вы связаны с процессором при обработке работы, убедитесь, что у вас есть только 1 потока на процессор.

Могут быть и другие проблемы, как GetNextJob получает свои данные для обработки? Если есть большое количество копирования данных, то вы снова значительно увеличили накладные расходы.

Я бы оптимизировал его, позволяя каждой потоке продолжать снимать задания с очереди, пока очередь не станет пустой. Таким образом, вы можете передать стопот заданий в пул потоков, и объекты Sync будут использоваться только один раз, чтобы начать поток. Я также храню задания в очереди и передал указатель, ссылку или итератор в поток вместо копирования данных.

Answer 6

Переключение контекста между потоками также может быть дорогостоящим. В некоторых случаях интересно разработать структуру, которую вы можете использовать для последовательного обработки заданий с одним потоком или с несколькими потоками. Таким образом, вы можете получить лучшее из двух миров.

Кстати, в чем именно ваш вопрос? Я смогу ответить более точно с более точным вопросом :)

РЕДАКТИРОВАТЬ:

Часть событий может потреблять больше, чем ваша обработка в некоторых случаях, но не должна быть такой дорогой, если только ваша обработка не будет очень быстрой. В этом случае переключение между Thredas тоже дорого, отсюда и мой ответ первой частью о том, как делать вещи последовательно ...

Вы должны искать узкие места для синхронизации. Вы можете отслеживать время ожидания потоков с ...

РЕДАКТИРОВАТЬ: После дополнительных намеков ...

Если я предполагаю правильно, ваша проблема состоит в том, чтобы эффективно использовать все ваши компьютерные ядра/процессоры для перепаризации некоторых Essencialy Sequential.

Примите это, у вас есть 4 ядра и 10000 петли, чтобы вычислить, как в вашем примере (в комментарии). Вы сказали, что вам нужно дождаться завершения 4 потоков, прежде чем продолжить. Затем вы можете упростить процесс синхронизации. Вам просто нужно дать свои четыре потока Thr Nth, nth+1, nth+2, nth+3 петли, дождитесь завершения четырех потоков, а затем продолжат. Вы должны использовать рейсвис или барьер (механизм синхронизации, который ожидает завершения n потоков). Способствовать росту имеет такой механизм. Вы можете посмотреть реализацию Windows для эффективности. Ваш пул потоков не совсем подходит для этой задачи. Поиск доступного потока в критическом разделе - это то, что убивает ваше время процессора. Не часть события.

Answer 7

Похоже, что все это событие (наряду с синхронизацией между потоками с использованием критических разделов) довольно дорого!

«Дорогой» - относительный термин. Jets дороги? Автомобили? Или велосипеды ... обувь ...?

В этом случае вопрос: «дорогими» событиями относительно времени, необходимого для выполнения JobFunction? Это помогло бы опубликовать некоторые абсолютные цифры: сколько времени занимает процесс, когда «нетребился»? Это месяцы или несколько фемтосекунд?

Что происходит со временем, когда вы увеличиваете размер тренажера? Попробуйте размер бассейна 1, затем 2 затем 4 и т. Д.

Кроме того, поскольку у вас были некоторые проблемы с тем, что здесь в прошлом, я бы посоветовал отладку подсчитать количество раз, когда ваша функция потока фактически вызывается ... это соответствует тому, что вы ожидаете?

Выбирая выступление из воздуха (ничего не зная о вашей целевой системе, и предполагая, что вы не делаете ничего «огромного» в коде, который вы не показали), я ожидаю «накладных расходов на событие» каждой «работы» быть измеренным в микросекундах. Может быть, сто или около того. Если время, необходимое для выполнения алгоритма в функции Job, не значительно больше, чем в этот раз, то ваши потоки, вероятно, будут стоить вам времени, а не сэкономить.

Answer 8

Since you say that it is much slower in parallel than sequential execution, I assume that your processing time for your internal 2500 loop iterations is tiny (in the few micro seconds range). Then there is not much you can do except review your algorithm to split larger chunks of precessing; OpenMP won't help and every other synchronization techniques won't help either because they fundamentally all rely on events (spin loops do not qualify).

On the other hand, if your processing time of the 2500 loop iterations is larger than 100 micro seconds (on current PCs), you might be running into limitations of the hardware. If your processing uses a lot of memory bandwidth, splitting it to four processors will not give you more bandwidth, it will actually give you less because of collisions. You could also be running into problems of cache cycling where each of your top 1000 iteration will flush and reload the cache of the 4 cores. Then there is no one solution, and depending on your target hardware, there may be none.

Answer 9

As mentioned previously, the amount of overhead added by threading depends on the relative amount of time taken to do the "jobs" that you defined. So it is important to find a balance in the size of the work chunks that minimizes the number of pieces but does not leave processors idle waiting for the last group of computations to complete.

Your coding approach has increased the amount of overhead work by actively looking for an idle thread to supply with new work. The operating system is already keeping track of that and doing it a lot more efficiently. Also, your function ThreadPool::addJob() may find that all of the threads are in use and be unable to delegate the work. But it does not provide any return code related to that issue. If you are not checking for this condition in some way and are not noticing errors in the results, it means that there are idle processors always. I would suggest reorganizing the code so that addJob() does what it is named -- adds a job ONLY (without finding or even caring who does the job) while each worker thread actively gets new work when it is done with its existing work.