Явный параллелизм кода в с ++

Question

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

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

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

Есть ли прямой способ получить тело моего цикла for для чередования этой высокопараллельной задачи, чтобы две (или более) итерации выполнялись вместе? (Это немного отличается от «разматывания петли», насколько я понимаю.)

Моя задача - «виртуальная машина», выполняющая набор инструкций, которые я действительно упростил для иллюстрации:

void run(int num) {
  for(int n=0; n<num; n++) {
     vm_t data(n);
     for(int i=0; i<data.len(); i++) {
        data.insn(i).parse();
        data.insn(i).eval();
     }
  }  
}

Так что след выполнения может выглядеть так:

data(1) insn(0) parse
data(1) insn(0) eval
data(1) insn(1) parse
...
data(2) insn(1) eval
data(2) insn(2) parse
data(2) insn(2) eval

Теперь я хотел бы иметь возможность делать две (или более) итерации явно параллельно:

data(1) insn(0) parse
data(2) insn(0) parse  \ processor can do OOO as these two flow in
data(1) insn(0) eval   /
data(2) insn(0) eval   \ OOO opportunity here too
data(1) insn(1) parse  /
data(2) insn(1) parse

Из профилирования я знаю (например, с помощью Callgrind с параметром --simulate-cache = yes), что синтаксический анализ связан со случайным доступом к памяти (отсутствует кэш), а eval - с выполнением операций в регистрах и последующей записью результатов. Каждый шаг состоит из нескольких тысяч инструкций. Так что, если я смогу смешать два шага для двух итераций одновременно, то процессор, мы надеемся, будет что-то делать, пока происходят пропуски кэша шага разбора ...

Есть ли какое-то безумие в шаблонах c ++ для генерации такого явного параллелизма?

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

Answer 1

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

Answer 2

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

Answer 3

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

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

TBB - это библиотека, поэтому ее можно использовать с любым современным компилятором C ++. OpenMP - это набор расширений компилятора, поэтому вам нужен компилятор, который его поддерживает. GCC / G ++ будет от версии 4.2 и новее. Последние версии компиляторов Intel и Microsoft также поддерживают это. Впрочем, я не знаю ни о каких других.

РЕДАКТИРОВАТЬ: еще одно примечание. Использование таких систем, как TBB или OpenMP, максимально увеличит объем обработки - то есть, если у вас есть 100 объектов для работы, они будут разделены примерно на 50/50 в двухъядерной системе 25/25/25 / 25 в четырехъядерной системе и т. Д.

Answer 4

В текущем стандарте C ++ нет поддержки параллельного выполнения. Это изменится для следующей версии стандарта, которая должна выйти в следующем году или около того.

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

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

Answer 5

Современные процессоры, такие как Core 2, имеют огромный буфер переупорядочения команд порядка порядка 100 команд; даже если компилятор довольно тупой, процессор все равно может его восполнить.

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

Answer 6

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

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

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

Answer 7

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

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

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

Чтобы создать параллельный цикл DYI OpenMP, вам необходимо:

• в качестве подготовки создайте серию для шаблона цикла и измените код, чтобы использовать функторы для реализации тел цикла. Это может быть утомительно, так как вам нужно передать все ссылки через объект функтора
• создать виртуальный интерфейс JobItem для функтора и наследовать ваши функторы от этого интерфейса
• создать функцию потока, которая может обрабатывать отдельные объекты JobItems
• создать пул потоков с помощью этой функции потока
• Поэкспериментируйте с различными примитивами синхронизации, чтобы увидеть, какие из них лучше всего подходят для вас. Хотя семафор очень прост в использовании, его издержки довольно значительны, и если ваше тело цикла очень короткое, вы не хотите платить эти издержки за каждую итерацию цикла. Для меня отлично работала комбинация события ручного сброса + атомный (блокированный) счетчик как гораздо более быстрой альтернативы.
• экспериментируйте с различными стратегиями планирования JobItem. Если у вас достаточно длинный цикл, лучше, если каждый поток обрабатывает несколько последовательных JobItems за раз. Это уменьшает накладные расходы синхронизации и в то же время делает потоки более дружественными к кешу. Возможно, вы также захотите сделать это некоторым динамическим способом, сократив длину запланированной последовательности по мере того, как вы исчерпываете свои задачи, или разрешив отдельным потокам украсть элементы из других расписаний потоков.

Answer 8

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