Вопрос по c++, cpu, multithreading, ram, performance – Будет ли многопоточность повышать производительность?

15

Я новичок в программировании в целом, поэтому, пожалуйста, имейте это в виду, когда отвечаете на мой вопрос.

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

Вопрос в том, получу ли я какое-либо увеличение производительности, если буду использовать многопоточность программы, или я столкнусь с узким местом доступа к ОЗУ? Когда я говорю многопоточность, я имею в виду многопоточность только для 2 или 4 ядер, не более.

Если это помогает, моя текущая конфигурация компьютера - 2,4 ГГц Core2 Quad, 1033 FSB, 4 ГБ оперативной памяти на 667 МГц.

Заранее спасибо,

-Faken

Редактировать:

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

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

Вот код:

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

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

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

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

подделать от мм? = О John T
Это зависит от реализации потоков & amp; ОС вы используете. В некоторых ситуациях потоки не обязательно будут должным образом делегированы различным ядрам. С другой стороны, я не уверен, что оптимизация компилятора могла бы позаботиться об этом, но есть стратегии для доступа к памяти, чтобы обеспечить оптимальное использование кэша ЦП и усилителя; сократить время выборки, что дает вам большие преимущества в производительности. Эти стратегии часто используются при программировании низкого уровня для микроконтроллеров и усилителей. небольшие процессоры. dborba
Ну, у вас есть очень уникальный ник. фейк пост на ММ прямо сейчас :) John T
Если это поможет, я сейчас использую компилятор VC ++. Что касается выделения ресурсов специально для кэша ЦП, это было бы намного выше моих возможностей на данный момент. Хотя я был вынужден пройти курс обучения электронике в университете, который имел дело с внутренней работой микроконтроллера, поэтому я понимаю многие его внутренние функции (хотя я до сих пор не понимаю, почему меня заставили его ... чувак Я машиностроение! Не компьютер!) Faken
Ух ты, не ожидал увидеть тебя здесь, не говоря уже о том, что ты выбрал меня из толпы из почти сотен тысяч! Да, это Факен из ММ! Faken

Ваш Ответ

19   ответов
2

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

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

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

В-третьих, вы связаны с памятью? & quot; Объем ОЗУ. & quot; не то же самое, что «привязанный к памяти». Если вы в настоящее время связаны с процессором, то многопоточность ускорит процесс. Если вы в настоящее время связаны с памятью, тогда многопоточность может даже замедлить работу (если один поток слишком быстр для памяти, что произойдет с несколькими потоками?).

В-четвертых, вы медлительны по какой-то другой причине? Если выnewилиmallocИз-за большого объема памяти в вашем алгоритме вы можете видеть издержки только от этого.И на многих платформах обаnew and malloc don't handle multithreading wellтак что, если вы медлите прямо сейчас, потому чтоmalloc плохо, многопоточная программа будет еще медленнее, потому чтоmalloc будет хуже

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

+1 за закон Амдала.
2

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

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

1

Устранить ложный обмен

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

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

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

как бы это ни было многопоточным, не было бы никаких блокировок, поскольку каждый поток не мог читать или записывать что-то, к чему другой поток имеет доступ. Faken
Извините за задержку с ответом. Я знаю, что вы не могли бы использовать блокировки в своем коде, однако кэш процессора имеет блокировку, которая предотвращает одновременную запись нескольких ядер в одну и ту же область кэша. Проблема в том, что у вас нет контроля над этими замками или размером их области. Таким образом, если ваши данные расположены близко друг к другу, ваши потоки могут в конечном итоге конкурировать за эти блокировки кеша, что приведет к дополнительным потокам, что приведет к снижению производительности. Одним из способов смягчения этого является использование стека, а затем копирование результатов в кучу в конце.
-1

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

11

выяснить, что вы делаете, это медленно, и делать меньше. Особый случай "делать меньше этого" вместо этого делать что-то еще, что быстрее.

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

#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;
}

(Изменить: только что заметил, что «проекция» должен быть массивом 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 в этом примере он довольно мал, поэтому мы выполняем много ненужной работы с «счетчиками»; массив. Даже без профилирования я предполагаю, что подсчет до 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

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

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

Итак, давайте сделаем однострочное изменение, переключив циклы i и 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 (я думаю, что разница между «пользовательским» и «реальным» временем в приведенном выше описании в основном объясняется тем фактом, что мой вирус Сканер работает, что раньше не было. «Пользователь» - это то, сколько времени программа занимала ЦП, «реальное» включает время, затраченное на приостановку, либо ожидание ввода-вывода, либо предоставление времени другому процессу для запуска).

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

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

Наконец, большая часть моего прироста производительности была получена за счет оптимизации того факта, что «шаги» маленький. С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 секунд, хотя я не собираюсь его запускать, чтобы доказать это. Но стоит помнить, что я полностью не убрал зависимость от времени от «шагов», просто сделал ее сублинейной.

Спасибо за этот комментарий - в будущем я буду иметь в виду, что новым программистам на C ++ понадобятся объяснения, более близкие к основным принципам.
Ха-ха! Спустя 1 месяц, но я никогда не забывал о вашем посте. Я наконец понял. Только когда я получил гораздо больший опыт программирования и знания о современных процессорах, я смог это понять. Я реализую свою собственную версию того, что у вас есть, когда у меня будет время. Вся проблема не в многопоточности, а в получении попаданий в кеш! Мне не нужно больше тактов, мне нужно больше пропускной способности памяти, единственный способ получить это - использовать кеш! Faken
Я перечитал это быстро и не совсем понял. Дайте мне день или около того, и я сяду и очень внимательно его изучу. Я не буду использовать какой-либо код, который я до конца не понимаю, и даже тогда я не буду копировать и вставлять код в свои программы. Ваш фактор сокращения времени 5 интересен. Мне нужно провести некоторое исследование структуры компьютера и тому подобных вещей. Если я в конечном итоге воспользуюсь концепциями, которые вы мне объяснили, я демонстративно дам вам кредит. Спасибо за потраченное время и усилия, это очень ценится. Faken
2

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

EDIT

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

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

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

и эта проблема
Я согласен: определенные задачи подходят для многопоточности, некоторые не подходят
Потоки не являются независимыми, поэтому они могут мешать друг другу из-за совместного использования структуры данных. Я предполагаю, что данные находятся в общей куче или другой глобальной области потока, а не в том, что у каждого потока есть копия данных, которые ему нужны, например, строка или столбец данных, что было бы неразумно для такого изолированного использования данных. Просто сказать, что многопоточность не может быть подходом к решению проблемы.
Мое приложение вызывающе многопоточное, на самом деле, я думаю, оно будет считаться «смущающе параллельным». поскольку каждая операция может выполняться независимо друг от друга, и, кроме того, чтение и запись могут выполняться одновременно, не взаимодействуя друг с другом, поскольку каждая «операция» моего кода работает с отдельным набором данных и записывает что-то, что больше ничего не коснется. Вопрос не в том, является ли он взаимно читаемым, а в том, удастся ли мне попасть в узкое место доступа к оперативной памяти. Faken
1

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

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

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

@Faken - Не так. 100% -ное потребление ресурсов процессора означает, что в течение измеренного интервала цикл простоя вообще не работает. ОС не может планировать остановку из-за ОЗУ, поэтому любые задержки из-за памяти не поддаются измерению. Я считаю, что vTune может дать вам информацию о задержках из-за оперативной памяти.
Да, я думаю, что понял. Да, 1 ядро загружено на 100%, а остальные просто сидят там. Я предполагаю, что это означает, что пропускная способность моей оперативной памяти не используется полностью, в противном случае мое одно ядро на ЦП будет менее 100%, пока оно ожидает данные от оперативной памяти. Так что в основном моя производительность будет увеличена в зависимости от того, сколько у меня осталось накладных расходов на доступ к оперативной памяти. Faken
0

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

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

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

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

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

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

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

При таком простом задании, как добавление, программа часто вообще не ограничена ALU («CPU»), скорее ограничена шина памяти. Это очень важно для этого вопроса. Лучшие ответы на эти вопросы отражают это, а те, за которые я проголосовал, - нет.
Я не делаю тонны многопоточного программирования, но я немного поработал, и мне кажется, что это правильно. Кто-то спамил, как 5 отрицательных ответов на разумные ответы в этой теме, не указав «Почему» на одного. Я хочу узнать, имеет ли мой ответ огромный недостаток (наиболее вероятен мой ввод-вывод данных, но в вопросе не указана система хранения!). Во всяком случае, кто-то может рассказать немного? Это разница между тем, чтобы быть полезным и быть членом. Благодарю.
31

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

You only need as many threads to match the number of cores available to you. This is a CPU intensive operation, and threads are unlikely to be waiting for I/O.

The above assumption might not hold if the entire array does not fit in RAM. If portions of the array are paged in and out, some threads will be waiting for paging operations to complete. In that case, the program might benefit from having more threads than cores. Too many, however, and performance will drop due to the cost of context switching. You might have to experiment with the thread count. The general rule is to minimize the number of context switches between ready threads.

If the entire array does not fit in RAM, you want to minimize paging! The order in which each thread accesses memory matters, as does the memory access pattern of all the running threads. To the extent possible, you would want to finish up with one part of the array before moving to the next, never to return to a covered area.

Each core would benefit from having to access a completely separate region of memory. You want to avoid memory access delays caused by locks and bus contention. At least for one dimension of the cube, that should be straightforward: set each thread with its own portion of the cube.

Each core would also benefit from accessing more data from its cache(s), as opposed to fetching from RAM. That would mean ordering the loops such that inner loops access nearby words, rather than skipping across rows.

Finally, depending on the data types in the array, the SIMD instructions of Intel/AMD processors (SSE, at their various generations) can help accelerate single core performance by summing multiple cells at once. VC++ has some built in support.

If you have to prioritize your work, you might want to first minimize disk paging, then concentrate on optimizing memory access to make use of the CPU caches, and only then deal with multithreading.

Это оно! Большое спасибо, это именно то, что я искал! Faken
С точки зрения пространственной локализации я также рассмотрюen.wikipedia.org/wiki/Hilbert_curve - это алгоритм перемещения по пространству при максимизации пространственной локализации - он должен помочь вашему кешу и ускорить ваш доступ.
Извините, Дейв, то, что вы говорите, не имеет для меня никакого смысла. В этом случае трехмерный массив на самом деле представляет собой гигантский одномерный массив с 1 миллиардным элементом, выделенный для HEAP ... который является линейным, с точки зрения пространственного местоположения, который будет действителен только вдоль одномерного пути, который затем будет действителен только мои проекции только по одной оси (что я мог бы перетасовать данные, чтобы они применились к другой оси, но вычислительное время и головная боль не стоят того). Faken
& quot; Вы хотите избежать задержек доступа к памяти, вызванных блокировками и конфликтом шины. & quot; Один из способов избежать конфликтов при записи в других измерениях - это «осколок»; итоги. Это означает, что каждый поток записывает в свой собственный массив итогов, и вы добавляете их все однопоточными в конце. Только с четырьмя ядрами дублирование представляет собой значительную, но не огромную нагрузку на память, и код почти наверняка проще, чем обеспечение того, чтобы одновременные участки работы были «диагональными». (то есть проекции на грани куба не пересекаются).
@Faken: Ах да, извините, я неправильно понял вашу структуру данных. Сказав это, вы будете перебивать кэш ЦП, поскольку вы будете получать доступ к элементам массива, которые находятся рядом в трехмерном пространстве (то есть один столбец), которые будут очень распространены в одномерном массиве. Ответ одного пользователя ниже хорошо описывает это.
2

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

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

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

2

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

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

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

2

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

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

Я могу проверить это. Я знаю глубже, в моем проекте может быть необходимость или даже необходимость. Faken
0

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

3

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

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

Многопоточность - это довольно важная вещь, чтобы «получить» ее, и сейчас нет времени изучать ее. :)
Хех, если бы я знал, что я делаю :) Причина, по которой я спрашиваю, состоит в том, чтобы узнать, стоит ли мне потратить время на то, чтобы начать понимать, как начать работу. Если большинство людей скажут, что я не вижу реального улучшения, то я не должен тратить на это свое время, в конце концов, я начинающий программист, новые концепции приходят медленно, если у вас нет опыта. Faken
5

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 КБ для 1000 итогов стека). В отличие от этого, вы делаете больше магазинов, чем вы, концентрируясь на 1 общем количестве за раз (что, следовательно, может быть в реестре).

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

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

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

У меня только 1033 МГц FSB, это ядро Core2 первого поколения, компьютеру уже более 2 лет. Ребята, вы, кажется, гораздо больше в этом вопросе, который я впервые ожидал ... Я думаю, выложите реальный код, ребята, вы, кажется, довольно заинтересованы. Faken
0

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)

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

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

Разница проста: вы читаете память в последовательном порядке, каждый современный процессор имеет функцию «prefetch». способность, таким образом, чтение и запись памяти последовательно намного быстрее, чем произвольный доступ, что делает кэш-промах на каждом шагу. (Пропуск кэша состоит из сотен циклов). Просто выполните простой тестовый прогон, и вы увидите, что скорость вашей программы улучшается на порядок mangintude.
Но с этим методом я не столкнусь с проблемами использования еще большей пропускной способности ОЗУ, чем раньше? прежде чем я столкнулся с 1 миллиардом операций чтения из ОЗУ (чтение из partMap) и 1 миллионом операций записи в оперативную память (записанных в проекцию). Но с этим новым методом я бы столкнулся с 2 миллиардами операций чтения (одна операция чтения из partMap, затем другая из проекции) и 1 миллиард операций записи (в проекцию), я не понимаю, как это может быть лучше. Faken
1

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

Disk I/O bandwidth: In most enterprise applications the sheer size of data processed requires it to be stored in some database. Acessing this data may be slowed down by both: the maximum transfer speed, but very often the biggest impact will be caused by a big number of small disk accesses reading some blocks here and there. The you will see the latency time of the heads of the disks moving around and even the time the disk requires for a full rotation may limit your application. Long times ago i had a real problem using some expansive SUN E430 installation that was outperformed by my small NeXTstation... It was the constant fsync()ing of my database which was slowed down by disks not caching write accesses (for good reason). Normally you can speed up your system by adding additional disks to get more I/O per second. Dedicating your drives to specific tasks may even do better in some cases.

Network Latency: nearly everything that affects application speed said for disks is equivalent for Network I/O.

RAM: If your RAM is not big enough to store your complete application image you need to store it on an external disks. Therefore the Disk I/O slowdown bites you again.

CPU processing speed (either Integer or floating point): CPU processing power is the next factor that is a limit for CPU intensive tasks. A CPU has a physical speed limit that cannot be outreached. The only way to speed up is to add more CPU.

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

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

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

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

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

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

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

4

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

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

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

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

это не матричная проблема. На самом деле это моя попытка работать с трехмерными данными в форме, которую я могу понять. У меня всего лишь около 1 месяца опыта программирования на C ++ и, кроме того, я инженер-механик, а не специалист по компьютерам. У меня появилась идея обрабатывать 3D-данные в моей программе, работая с программами FEA и CFD, в зависимости от настроек и программы, они делают что-то очень похожее. Faken

Похожие вопросы