Будет ли многопоточность обеспечивать любое повышение производительности?

Ответ 1

Существует только один способ оптимизации кода: выяснить, что вы делаете, что медленно, и делать меньше. Частный случай "делать меньше" заключается в том, чтобы быстрее сделать что-то другое.

Итак, в первую очередь, вот что я делаю на основе вашего опубликованного кода:

#include <fstream>
#include <sstream>
using std::ios_base;

template<typename Iterator, typename Value>
void iota(Iterator start, Iterator end, Value val) {
    while (start != end) {
        *(start++) = val++;
    }
}

int main() {

    const int dim = 1000;
    const int cubesize = dim*dim*dim;
    const int squaresize = dim*dim;
    const int steps = 7; //ranges from 1 to  255
    typedef unsigned char uchar;

    uchar *partMap = new uchar[cubesize];
    // dummy data. I timed this separately and it takes about
    // a second, so I won't worry about its effect on overall timings.
    iota(partMap, partMap + cubesize, uchar(7));
    uchar *projection = new uchar[squaresize];

    for (int stage = 1; stage < steps; stage++) {
        for (int j = 0; j < dim; j++) {
                for (int i = 0; i < dim; i++)
                {
                        int sum = 0;
                        for (int k = 0; k < dim; k++)
                            if (partMap[(((i * dim) + k) * dim) + j] >= stage)
                                sum++;

                        projection[(j*dim) + i] = sum;
                }
        }

        std::stringstream filename;
        filename << "results" << stage << ".bin";
        std::ofstream file(filename.str().c_str(), 
            ios_base::out | ios_base::binary | ios_base::trunc);
        file.write((char *)projection, squaresize);
    }

    delete[] projection;
    delete[] partMap;
}

(Edit: просто заметили, что "проекция" должна быть массивом int, а не uchar. Мой плохой. Это будет иметь значение для некоторых таймингов, но, надеюсь, не слишком большой.)

Затем я скопировал result*.bin в gold*.bin, поэтому я могу проверить мои будущие изменения следующим образом:

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    1m41.978s
user    1m39.450s
sys     0m0.451s

ОК, так что на данный момент 100 секунд.

Итак, размышляя, что он шагает по массиву данных миллиарда элементов, который замедляется, попробуйте пройти один раз один раз, а не один раз за этап:

    uchar *projections[steps];
    for (int stage = 1; stage < steps; stage++) {
         projections[stage] = new uchar[squaresize];
    }

    for (int j = 0; j < dim; j++) {
            for (int i = 0; i < dim; i++)
            {
                    int counts[256] = {0};
                    for (int k = 0; k < dim; k++)
                            counts[partMap[(((i * dim) + k) * dim) + j]]++;

                    int sum = 0;
                    for (int idx = 255; idx >= steps; --idx) {
                        sum += counts[idx];
                    }
                    for (int stage = steps-1; stage > 0; --stage) {
                        sum += counts[stage];
                        projections[stage][(j*dim) + i] = sum;
                    }
            }
    }

    for (int stage = 1; stage < steps; stage++) {
        std::stringstream filename;
        filename << "results" << stage << ".bin";
        std::ofstream file(filename.str().c_str(),
            ios_base::out | ios_base::binary | ios_base::trunc);
        file.write((char *)projections[stage], squaresize);
    }

    for (int stage = 1; stage < steps; stage++) delete[] projections[stage];
    delete[] partMap;

Это немного быстрее:

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    1m15.176s
user    1m13.772s
sys     0m0.841s

Теперь steps в этом примере довольно мал, поэтому мы делаем много ненужной работы с массивом "counts". Даже без профилирования я предполагаю, что подсчет до 256 два раза (один раз, чтобы очистить массив и один раз его суммировать) довольно значителен по сравнению с подсчетом до 1000 (для выполнения по нашей колонке). Поэтому давайте изменим, что:

    for (int j = 0; j < dim; j++) {
            for (int i = 0; i < dim; i++)
            {
                    // steps+1, not steps. I got this wrong the first time,
                    // which at least proved that my diffs work as a check
                    // of the answer...
                    int counts[steps+1] = {0};
                    for (int k = 0; k < dim; k++) {
                        uchar val = partMap[(((i * dim) + k) * dim) + j];
                        if (val >= steps) 
                            counts[steps]++;
                        else counts[val]++;
                    }

                    int sum = counts[steps];
                    for (int stage = steps-1; stage > 0; --stage) {
                        sum += counts[stage];
                        projections[stage][(j*dim) + i] = sum;
                    }
            }
    }

Теперь мы используем столько ведер, сколько нам нужно.

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    0m27.643s
user    0m26.551s
sys     0m0.483s

Hurray. Код почти в 4 раза быстрее, чем первая версия, и дает те же результаты. Все, что я сделал, это изменить порядок выполнения математики: мы даже не рассматривали многопоточность или предварительную выборку. И я не пытался оптимизировать технический цикл, просто оставил его компилятору. Так что это можно считать достойным началом.

Однако он по-прежнему занимает порядок больше, чем 1-й, в который входит iota. Таким образом, вероятно, есть большие успехи в поиске. Одно из основных отличий заключается в том, что iota работает по 1-му массиву в последовательном порядке, вместо того, чтобы прыгать по всему месту. Как я сказал в своем первом ответе, вы должны стремиться всегда использовать последовательный порядок на кубе.

Итак, давайте сделаем однострочное изменение, переключив циклы я и j:

            for (int i = 0; i < dim; i++)
    for (int j = 0; j < dim; j++) {

Это все еще не последовательный порядок, но это означает, что мы фокусируемся на миллиметровом куске нашего куба за раз. Современный процессор имеет как минимум 4 МБ кеша, поэтому, немного повезло, мы ударим только основную память для любой части куба один раз во всей программе. С еще лучшей локальностью мы могли бы уменьшить трафик в и из кэша L1, но основная память является самой медленной.

Какая разница?

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    0m8.221s
user    0m4.507s
sys     0m0.514s

Неплохо. Фактически, только это изменение приносит исходный код от 100 до 20 секунд. Таким образом, это отвечает за фактор 5, и все остальное, что я сделал, несет ответственность за другой фактор 5 (я думаю, что разница между "пользователем" и "реальным" временем в приведенном выше в основном объясняется тем фактом, что мой антивирус "user" - это время, в течение которого программа занимала процессор, "реальный" включает приостановленное время, либо ожидая ввода/вывода, либо давая другое время для выполнения).

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

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

Наконец, большая часть моего прироста производительности исходила из оптимизации за то, что "шаги" малы. С steps=100 я получаю:

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    0m22.262s
user    0m10.108s
sys     0m1.029s

Это не так уж плохо. С шагами = 100 исходный код, вероятно, занимает около 1400 секунд, хотя я не собираюсь его запускать, чтобы доказать это. Но стоит помнить, что я не полностью отменил зависимость времени от "шагов", просто сделал ее сублинейной.

Ответ 2

Многопоточность через несколько ядер может сократить время, необходимое для суммирования по осям, но требуется особая осторожность. На самом деле вы можете получить более высокие повышения производительности от некоторых изменений, которые вы можете внести в свой код потока:

• Вам нужно только столько потоков, чтобы соответствовать количеству доступных вам ядер. Это интенсивная работа процессора, и потоки вряд ли будут ждать ввода/вывода.

• Вышеприведенное предположение может не выполняться, если весь массив не подходит в ОЗУ. Если части массива выгружаются и выходят, некоторые потоки ждут завершения операций подкачки. В этом случае программа может выиграть от большего количества потоков, чем ядра. Однако слишком много, и производительность снизится из-за стоимости переключения контекста. Возможно, вам придется поэкспериментировать с количеством потоков. Общее правило состоит в том, чтобы свести к минимуму количество переключателей контекста между готовыми потоками.

• Если весь массив не подходит в ОЗУ, вы хотите свести к минимуму пейджинг! Порядок, в котором каждый поток обращается к памяти, имеет значение, равно как и шаблон доступа к памяти всех запущенных потоков. Насколько это возможно, вы хотели бы закончить работу с одной частью массива, прежде чем переходить к следующему, чтобы никогда не вернуться в закрытую область.

• Каждое ядро ​​выиграет от доступа к совершенно отдельной области памяти. Вы хотите избежать задержек доступа к памяти, вызванных блокировками и конфликтами в шинах. По крайней мере, для одного измерения куба это должно быть простым: установите каждый поток с собственной частью куба.

• Каждое ядро ​​также выиграет от доступа к большему количеству данных из его кеш-памяти, а не к извлечению из ОЗУ. Это означало бы упорядочение циклов таким образом, чтобы внутренние петли приближались к соседним словам, а не пропускали строки.

• Наконец, в зависимости от типов данных в массиве инструкции SIMD процессоров Intel/AMD (SSE в разных поколениях) могут помочь ускорить одноядерную производительность путем суммирования сразу нескольких ячеек. VС++ имеет встроенную поддержку .

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

Ответ 3

Как работает ваш код. Это так?

for each row: add up the values
for each column: add up the values
for each stack: add up the values

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

Я думаю, что вы можете насытить шину памяти (*), и в этом случае многопоточность поможет только в том случае, если core2 quad использует разные шины для разных ядер. Но если вы не насыщаете пропускную способность шины, вы не можете получить лучшую производительность таким образом даже после многопоточности. У вас будет 4 ядра, все время остановившиеся на пропущенных кешах вместо одного.

Если вы привязаны к кешу памяти, ваша цель - посещать каждую страницу/строку памяти как можно раньше. Поэтому я бы попробовал такие вещи, как пробегать данные один раз, добавив каждое значение в три разных итоговых значения. Если это работает быстрее на одном ядре, мы работаем. Следующий шаг заключается в том, что с кубиком 1000x1000x1000 у вас есть 3 миллиона итогов на ходу. Это тоже не подходит для кеша, поэтому вам нужно беспокоиться о том, что проблемы с кешем пропущены, как вы читаете.

Вы хотите удостовериться, что по мере того, как вы выполняете ряд из 1000 смежных значений в ОЗУ, добавляя к общей сумме, которую все они разделяют, вы также добавляете к смежным итогом для столбцов и стеков (которые они не магазин). Таким образом, "квадрат" итогов столбцов должен храниться соответствующим образом, как и "квадрат" стеков. Таким образом, вы имеете дело с 1000 из ваших миллиардов значений, просто потянув около 12 тыс. Памяти в кеш (4 тыс. Для 1000 значений, плюс 4 тыс. Для 1000 столбцов, плюс 4 тыс. Для итоговых сумм в стеке). В отличие от этого, вы делаете больше магазинов, чем если бы вы сосредоточились на 1 сумме за раз (что, следовательно, могло быть в регистре).

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

(*) Задняя часть расчета конверта: в случайных случайных опросах с Интернета самая высокая оценка FSB для процессоров Core2, которые я нашел до сих пор, является Extreme со скоростью 12 ГБ/с, с двумя каналами на частоте 4х199 МГц). Размер строки кэша составляет 64 байта, что меньше вашего шага. Таким образом, суммирование столбца или стека плохой способ, хватающий 64 байта за значение, будет только насыщать шину, если она делает 200 миллионов значений в секунду. Я предполагаю, что это не так быстро (10-15 секунд для всего этого), или вы не будете спрашивать, как ускорить его.

Итак, моя первая догадка, вероятно, была удалена. Если ваш компилятор или процессор не вставили какую-то очень умную предварительную выборку, одно ядро ​​не может использовать 2 канала и 4 одновременных перевода за цикл. В этом случае 4 ядра не могут использовать 2 канала и 4 одновременных передачи. Эффективная пропускная способность шины для серии запросов может быть намного ниже физического предела, и в этом случае вы надеетесь увидеть хорошие улучшения от многопоточности просто потому, что у вас есть 4 ядра, требующих 4 разных строчки кэша, все из которых могут быть загружаемых одновременно, не беспокоя FSB или контроллер кэша. Но латентность по-прежнему является убийцей, и поэтому, если вы можете загрузить меньше одной строки кэша за суммарное значение, вы сделаете гораздо лучше.

Ответ 4

Невозможно сказать, в общем, потому, что вы не указали, насколько быстр ваш процессор и оперативная память. Хорошие шансы на то, что это улучшит ситуацию, потому что я не могу себе представить, как даже 4 потока, суммирующихся параллельно, достаточно насытили бы ОЗУ настолько, что это станет узким местом (а не процессором).

Ответ 5

Моя кишка говорит, что вы увидите скромные улучшения. Однако предсказание результатов оптимизаций - это, как правило, ошибочное дело.

Попробуйте и проверьте результаты.

Ответ 6

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

ИЗМЕНИТЬ

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

Да, он появляется после повторного чтения вашего вопроса и с учетом вашего конкретного случая вы выиграете от многопоточности.

ОЗУ очень быстрая, поэтому я думаю, что было бы очень сложно насытить пропускную способность памяти, если у вас много много потоков.

Ответ 7

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

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

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

Ответ 8

Я думаю, что даже если многопоточность может повысить производительность, это неправильный подход к оптимизации. Множество ядер - все это ярость, потому что они - единственный способ для производителей ЦП обеспечить более быструю скорость процессора по доступной цене - не обязательно потому, что они потрясающий инструмент программирования (все еще много зрелости, которое должно произойти).

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

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

Ответ 9

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

Во-первых, работа параллелизуема? Закон Amdahl даст вам верхнюю оценку того, насколько вы можете ускорить процесс многопоточности.

Во-вторых, будет ли многопоточное решение вводить много накладных расходов? Вы говорите, что программа "RAM интенсивна, поскольку программа постоянно извлекает информацию из ОЗУ, как чтение, так и запись". Поэтому вам нужно определить, будет ли чтение/запись значительным накладными расходами на координацию. Это непросто. Хотя каждый процессор может в любое время получить доступ к компьютеру всей памяти (как для чтения, так и для записи), это может замедлить доступ к памяти - даже без блокировок - потому что различные ЦП хранят свои собственные кеши и должны координировать то, что в их кешах (ЦП 1 имеет значение в кеше, ЦП 2 обновляет это значение в ОЗУ, ЦП 2 должен сказать ЦП 1 аннулировать его кеш). И если вам нужны блокировки (это почти гарантия, так как вы оба "читаете и записываете" память), вам нужно избегать конфликтов как можно больше.

В-третьих, связаны ли вы с памятью? "Оперативная память". это не то же самое, что "память связана". Если вы в настоящее время связаны с ЦП, то многопоточность ускорит процесс. Если вы в настоящее время связаны с памятью, многопоточность может даже замедлить работу (если один поток слишком быстр для памяти, то что будет с несколькими потоками?).

В-четвертых, вы медленны по какой-то другой причине? Если вы используете new ing или malloc, используя много памяти в своем алгоритме, вы можете увидеть накладные расходы только от этого. И на многих платформах new и malloc не работают хорошо многопоточно, поэтому, если вы сейчас медленны, потому что malloc Плохо, многопоточная программа будет еще медленнее, потому что malloc будет хуже.

В целом, однако, не увидев ваш код, я ожидал бы, что он будет привязан к процессору, и я ожидал бы, что многопоточность ускорит работу - почти столько же, сколько закон Амдаля. Возможно, вы захотите посмотреть библиотеку OpenMP или Intel Threading Building Blocks или какую-то очередь потоков, чтобы сделать это.

Ответ 10

Прежде чем вы начнете многопоточность, вы должны запустить профилировщик против вашего кода. Возможно, другой вопрос относительно того, где можно найти хороший (возможно) бесплатный С++-профайлер.

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

Ответ 11

Хотя это, вероятно, будет очень сложно для вас, если вы новичок в программировании, очень мощный способ ускорить работу - это использовать мощь графического процессора. Мало того, что VRAM намного быстрее, чем обычная оперативная память, GPU также может запускать ваш код параллельно на 128 или более ядрах. Конечно, для этого объема данных вам понадобится довольно большой VRAM.

Если вы решите проверить эту возможность, вы должны посмотреть nVidia CUDA. Я сам этого не проверял, но это означало такие проблемы.

Ответ 12

Если вы правильно разбиваете свои данные, то да, у вас будет повышение производительности. Если вы сейчас проверите свое использование процессора, одно ядро ​​будет на 100%, а остальные 3 должны быть близки к 0%

Все зависит от того, насколько хорошо вы структурируете свои потоки и использование памяти.

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

Ответ 13

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

• Ширина дискового ввода-вывода: в большинстве корпоративных приложений чистый размер обрабатываемых данных требует сохранения в некоторой базе данных. Признание этих данных может быть замедлено обоими: максимальная скорость передачи, но очень часто наибольшее воздействие будет вызвано большим количеством небольших дисков, которые читают некоторые блоки здесь и там. Вы увидите время ожидания головок дисков, перемещающихся и даже время, требуемое для полного вращения диска, может ограничить ваше приложение. Долгое время назад у меня была настоящая проблема с использованием какой-то экспансивной установки SUN E430, которая была превзойдена моей небольшой NeXTstation... Это была постоянная fsync() моя база данных, которая была замедленна дисками, не кэширующими доступ к записи (по уважительной причине), Обычно вы можете ускорить работу системы, добавив дополнительные диски, чтобы получить больше ввода-вывода в секунду. Выделение ваших дисков на конкретные задачи может даже улучшить ситуацию в некоторых случаях.

• Задержка сети: почти все, что влияет на скорость приложения, указанное для дисков, эквивалентно для ввода/вывода сети.

• ОЗУ: Если ваша оперативная память недостаточно велика для хранения полного изображения приложения, вам необходимо сохранить его на внешних дисках. Поэтому замедление дискового ввода-вывода снова укусит вас.

• Скорость обработки процессора (целая или плавающая точка): мощность процессора - это следующий фактор, который является предел для задач с интенсивным использованием ЦП. У CPU есть физический предел скорости, который не может быть преодолен. Единственный способ ускорить - добавить больше CPU.

Эти ограничения могут помочь вам найти ответ для вашей конкретной проблемы.

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

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

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

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

Если вы видите время ожидания ввода-вывода, подумайте об умном разделении или кешировании, а затем о потоковой передаче. Существует причина, по которой GNU-make поддерживает параллельную сборку в 90: -)

Проблема, о которой вы описали, приводит меня сначала к умным алгоритмам. По возможности старайтесь как можно больше использовать последовательные операции чтения/записи в основной памяти, чтобы максимально поддерживать подсистемы процессора и памяти. Храните операции "локальные" и datastructures как маленькие и оптимизированные, насколько это возможно, чтобы уменьшить объем памяти, который нужно перетасовать, прежде чем переключиться на второе ядро.

Ответ 14

Устранить ложный доступ

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

У Herb Sutter есть очень хорошая статья о False Sharing, как ее обнаружить и как избежать этого в ваших параллельных алгоритмах.

Очевидно, что он также имеет множество других отличных инструментов для параллельного программирования, см. блог .

Ответ 15

Это матричная проблема?

И у Intel, и у AMD есть супер-оптимизированные библиотеки для всех видов тяжелых математических задач. Эти библиотеки используют потоки, упорядочивают данные для лучшего использования кеша, предварительную выборку кеша, векторные инструкции SSE. Все.

Я считаю, что вы должны платить за библиотеки, но они хорошо стоят денег.

Ответ 16

Если вы можете разделить массив так, чтобы потоки не записывали/не читали в/из тех же позиций в массиве, он должен увеличить вашу скорость.

Ответ 17

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

Если вы не можете загружать все в память сразу, вам нужно быть более конкретным в отношении своего решения - оно должно быть адаптировано для потоковой передачи.

Например: Предположим, вы загрузили свой массив в меньшие блоки (размер может не иметь большого значения). Если бы вы загрузили куб 1000x1000x1000, вы могли бы с этим согласиться. Результаты могут храниться временно на своих трех равнинах, а затем добавляться в ваши 3-дюймовые "конечные результаты", тогда блок 1000 ^ 3 можно выбросить, чтобы его больше не читали.

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

Единственная проблема заключается в том, чтобы обеспечить, чтобы ваши данные находились в таком формате, что вы можете получить доступ к одному кубику 1000 ^ 3 напрямую - без поиска головки жесткого диска повсюду.

Изменить: комментарий был верным, и я ошибаюсь - он имеет смысл.

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

Ответ 18

Попробуйте этот код:

int dim = 1000;
int steps = 7 //ranges from 1 to  255

for (int stage = 1; stage < steps; stage++)
for (int k = 0; k < dim; k++)
    for (int i = 0; i < dim; i++)
    {
            sum = 0;
            for (int j = 0; j < dim; j++)
                    if (partMap[(((i * dim) + k) * dim) + j] >= stage)
                            projection[i*dim + j] ++ ;
                            // changed order of i and j
    }


transponse(projection)

Я изменил порядок циклов, чтобы сделать кеш-код удобным... Вы бы получили с собой порядок увеличения силы... Будьте осторожны.

Это шаг, который вы должны сделать, прежде чем пытаться выполнить многопоточность

Ответ 19

Совершенно верно. По крайней мере, поможет каждое ядро ​​в потоке работать над вашей проблемой одновременно. Неясно, поможет ли больше потоков, но это возможно.