Много поточная обработка обеспечит какое-либо повышение производительности?

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

Это проблема матрицы?

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

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

Try this code:

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)

I changed the order of loops to make the code cache friendly... С его помощью вы получите прирост производительности на порядок ... Будьте уверены.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

1. Вам нужно ровно столько потоков, сколько соответствует количеству доступных вам ядер. Это операция с интенсивным использованием ЦП, и потоки вряд ли будут ждать ввода-вывода.

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

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

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

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

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

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

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

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 сумме за раз (что, следовательно, могло быть в реестре).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Устранение ложного совместного использования

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

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

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

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

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

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

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

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

Редактировать: Комментарий был правильным, и я ошибаюсь - он полностью имеет смысл.

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