Явный параллелизм кода в C++
Неупорядоченное выполнение в ЦП означает, что ЦП может переупорядочивать инструкции для повышения производительности, и это означает, что ЦП должен выполнять очень изящную бухгалтерию и тому подобное. Есть и другие подходы к процессору, например, гиперпоточность.
Некоторые навороченные компиляторы понимают (не) взаимосвязь инструкций в ограниченной степени и будут автоматически чередовать потоки инструкций (вероятно, в течение более длительного окна, чем видит ЦП), чтобы лучше использовать процессор. Преднамеренное чередование во время компиляции инструкций с плавающей запятой и целочисленных инструкций - еще один пример этого.
Теперь у меня высокопараллельная задача. И у меня обычно есть устаревший одноядерный процессор 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 - о выполнении операций в регистрах и последующей записи результатов обратно. Каждый шаг состоит из нескольких тысяч инструкций. Итак, если я смогу объединить два шага для двух итераций одновременно, мы надеемся, что процессору будет чем заняться, пока происходят промахи в кэше на этапе синтаксического анализа ...
Есть ли какое-то безумие шаблонов С ++ для создания такого явного параллелизма?
Конечно, я могу делать чередование - и даже потрясающее - сам в коде, но это делает код гораздо менее читаемым. А если мне очень хочется нечитаемого, я могу пойти дальше ассемблера! Но, конечно же, для такого рода вещей есть какая-то закономерность?
Я убежден, что идея смешения «синтаксического анализа» и «выполнения операций в регистре» вообще не приведет к ускорению, поскольку это то, что поставщики процессоров делают сами по себе, используя такие методы, как переименование регистров, переадресация хранилищ.
Сочетание синтаксического анализа и выполнения для двух виртуальных машин в одном потоке - с тех пор, как задан этот вопрос - привело к улучшению на 16%. Но мое смешение - это метод проб и ошибок, поэтому весьма вероятно, что я еще не приближаюсь к возможному улучшению. Я все еще ищу способ организовать код без спагетти
Большой. Измерения всегда правильные, и поэтому я искренне признаю, что ошибался. Я попытаюсь подумать о некоторой магии шаблонов, которая могла бы вам помочь сейчас (не то чтобы я очень рассчитывал на то, что приду с чем-нибудь, но кто знает, возможно, что-то придет на мою сторону)
Ответы 8
Возможно, вам лучше всего заглянуть в OpenMP. По сути, он позволяет вам вставлять в код «прагмы», которые сообщают компилятору, как он может распределяться между процессорами.
Гиперпоточность - это система гораздо более высокого уровня, чем переупорядочение инструкций. Это делает процессор похожим на два процессора для операционной системы, поэтому вам нужно будет использовать реальную библиотеку потоков, чтобы воспользоваться этим. То же самое, естественно, относится и к многоядерным процессорам.
Если вы не хотите использовать низкоуровневые библиотеки потоков и вместо этого хотите использовать параллельную систему на основе задач (и похоже, что это то, что вам нужно), я бы посоветовал взглянуть на OpenMP или Intel Заправка строительных блоков.
TBB - это библиотека, поэтому ее можно использовать с любым современным компилятором C++. OpenMP - это набор расширений компилятора, поэтому вам нужен компилятор, который его поддерживает. GCC / G ++ будет начиная с версии 4.2 и новее. Последние версии компиляторов Intel и Microsoft также поддерживают его. Хотя я не знаю ни о каких других.
Обновлено: еще одно примечание. Использование таких систем, как TBB или OpenMP, максимально масштабирует обработку - то есть, если у вас есть 100 объектов для работы, они будут разделены примерно 50/50 в двухъядерной системе, 25/25/25/. 25 в четырехъядерной системе и т. д.
Компилятор Microsoft на самом деле поддерживает OpenMP.
Исправлено, спасибо. Если вы знаете версию, в которой была добавлена поддержка, я тоже добавлю ее. То же самое и с версией ICC.
«И у меня обычно есть устаревший одноядерный процессор x86 без гиперпоточности». Он не хочет многопоточности. Это совсем другой вопрос.
Современные процессоры, такие как Core 2, имеют буфер переупорядочения инструкций громадный порядка 100 инструкций; даже если компилятор довольно тупой, процессор все равно может это исправить.
Основная проблема была бы в том, если бы код использовал много регистров, и в этом случае давление регистра могло бы заставить код выполняться последовательно, даже если теоретически это могло быть выполнено параллельно.
Текущий стандарт C++ не поддерживает параллельное выполнение. Это изменится в следующей версии стандарта, которая должна выйти в следующем году или около того.
Однако я не понимаю, чего вы пытаетесь достичь. Вы имеете в виду один одноядерный процессор или несколько процессоров или ядер? Если у вас только одно ядро, вы должны делать то, что дает наименьшее количество промахов в кеше, что означает, что любой подход использует наименьший рабочий набор памяти. Вероятно, это будет либо выполнение всего синтаксического анализа с последующей всей оценкой, либо выполнение синтаксического анализа и оценки поочередно.
Если у вас есть два ядра и вы хотите использовать их эффективно, вам придется либо использовать особенно умный компилятор, либо языковые расширения. Есть ли одна операционная система, для которой вы разрабатываете, или это должно быть для нескольких систем?
Похоже, вы столкнулись с той же проблемой, с которой сталкиваются разработчики микросхем: выполнение одной инструкции требует больших усилий, но включает в себя набор различных шагов, которые можно связать вместе в конвейер исполнения. (Легче выполнять задачи параллельно, если вы можете построить их из отдельных блоков оборудования.)
Самый очевидный способ - разделить каждую задачу на разные потоки. Вы можете создать один поток для выполнения каждой инструкции до завершения или создать по одному потоку для каждого из двух этапов выполнения и передавать данные между ними. В любом случае вам нужно быть очень осторожным с тем, как вы делитесь данными между потоками, и обязательно обработать случай, когда одна инструкция влияет на результат следующей инструкции. Даже если у вас есть только одно ядро и только один поток может быть запущен в любой момент времени, ваша операционная система должна иметь возможность планировать потоки с интенсивными вычислениями, в то время как другие потоки ожидают промахов в кэше.
(Несколько часов вашего времени, вероятно, потратят на один очень быстрый компьютер, но если вы пытаетесь широко развернуть его на дешевом оборудовании, возможно, имеет смысл рассмотреть проблему так, как вы на нее смотрите. интересная проблема для рассмотрения.)
Учитывая оптимизацию компиляторов и конвейерных процессоров, я бы посоветовал вам просто написать четкий, читаемый код.
Я тоже хотел сказать это. Линейный поток кода с сегодняшним процессором - это фикция. Это просто КАЖЕТСЯ работать таким образом, в то время как реальное выполнение кода конвейерно, за гранью воображения, с предсказанием ветвлений и всем остальным.
Ни один компилятор C++, который я видел до сих пор, не может самостоятельно создавать многоядерный код. Для этого вам нужно использовать некоторые явные конструкции.
@Suma: если вы проголосовали против моего ответа, пожалуйста, перечитайте вопрос и ответьте на него: какая польза от многоядерного кода, когда «А у меня обычно устаревший одноядерный процессор x86 без гиперпоточности». Сохраняйте контекст, люди!
В ПОРЯДКЕ. Тогда я буду отрицать этот вопрос. Вы правы, бесполезно распараллеливать вычисления, если у вас нет ресурсов для распараллеливания.
Взгляните на шелк. Это расширение для ANSI C, которое имеет несколько хороших конструкций для написания распараллеленного кода на C. Однако, поскольку это расширение C, оно имеет очень ограниченную поддержку компилятора, и с ним может быть сложно работать.
Этот ответ был написан, предполагая, что вопросы не содержат части «И у меня обычно устаревающий одноядерный процессор x86 без гиперпоточности.». Я надеюсь, что это поможет другим людям, которые хотят распараллеливать высокопараллельные задачи, но нацелены на двух- и многоядерные процессоры.
Как уже сообщалось в другой ответ, OpenMP - это переносимый способ сделать это. Однако мой опыт показывает, что накладные расходы OpenMP довольно высоки, и их очень легко победить. прокатка реализации DIY (Сделай сам). Надеюсь, OpenMP со временем улучшится, но в настоящее время я бы не рекомендовал использовать его ни для чего другого, кроме прототипирования.
Учитывая характер вашей задачи, вы, скорее всего, захотите использовать параллелизм на основе данных, что, по моему опыту, довольно просто - стиль программирования может быть очень похож на одноядерный код, потому что вы знаете, что делают другие потоки. , что значительно упрощает поддержание безопасности потоков - подход, который сработал для меня: избегать зависимостей и вызывать только поточно-безопасные функции из цикла.
Чтобы создать параллельный цикл DYI OpenMP, вам необходимо:
- в качестве подготовки создайте серийный шаблон цикла для и измените свой код, чтобы использовать функторы для реализации тел цикла. Это может быть утомительно, так как вам нужно передать все ссылки через объект-функтор.
- создать виртуальный интерфейс JobItem для функтора и унаследовать свои функторы от этого интерфейса
- создать функцию потока, которая может обрабатывать отдельные объекты JobItems
- создать пул потоков потока, используя эту функцию потока
- поэкспериментируйте с различными примитивами синхронизации, чтобы выбрать наиболее подходящий для вас. Хотя семафор очень прост в использовании, его накладные расходы весьма значительны, и если тело вашего цикла очень короткое, вы не хотите оплачивать эти накладные расходы за каждую итерацию цикла. Для меня отлично сработала комбинация ручного сброса событий + атомарный (заблокированный) счетчик в качестве гораздо более быстрой альтернативы.
- поэкспериментируйте с различными стратегиями планирования JobItem. Если у вас достаточно длинный цикл, лучше, если каждый поток будет обрабатывать несколько последовательных объектов JobItem за раз. Это снижает накладные расходы на синхронизацию и в то же время делает потоки более удобными для кеширования. Вы также можете сделать это каким-то динамическим способом, уменьшив длину запланированной последовательности по мере того, как вы исчерпываете свои задачи, или позволив отдельным потокам красть элементы из расписаний других потоков.
Я считаю этот вопрос очень интересным и важным, однако то, что делает его плохим, на мой взгляд, - это часть: «Теперь у меня высокопараллельная задача. И у меня обычно устаревающий одноядерный процессор x86 без гиперпоточности». Если у вас нет процессоров для распараллеливания, тогда зачем это делать?