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

Question

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

У меня есть программа, которая берет большой трехмерный массив (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. Основные данные, благодаря тому, как они были построены, имеют странную систему адресации, но вам не нужно об этом беспокоиться. Существует также другой код для выполнения проекций других сторон куба, но они делают совершенно разные вещи.

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

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

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

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

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

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

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

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

Answer 5

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

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

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

Answer 6

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

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)

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

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

Answer 7

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

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

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

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

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

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

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

Answer 8

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

Answer 9

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