Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 29
Так что же такое loop fracking?
Здесь достаточно естественного параллелизма чтобы прибегать к особым усилиям.Как раз для БПФ в библиотеке FFTW применяется поход похожий на то что вы предлагаете. Там есть набор из множества функций, вычисляющих кусочки БПФ-графа разных размеров, и из них составляется целое преобразование (при этом ещё и выбирается оптимальная для данной машины комбинация, с помощью замеров производительности). Сами кирпичики генерируются с помощью скриптов перед компиляцией.
Вот тут статья, которая описывает, как это работает www.fftw.org/fftw-paper-ieee.pdf
Примитивизация компилятора до 1-2-3 пунктов (синтаксический анализ — генерация промежуточного кода — кодогенерация) вводит в заблуждение как читателя, так и самого автора, ибо сводит всё к проблеме распределения регистров. А это категорически не так. Между пунктами 2 и 3 ещё присутствует огромный кусок, которые по своему размеру превышает эти 1-2-3 в разы. А именно, оптимизатор, который включает в себя скалярные машинно-независимые оптимизации, межпроцедурный анализ и оптимизации, высокоуровневый оптимизатор циклов и цикловых гнёзд и непосредственно векторизатор.
В приведённом примере с частичными суммами, компилятор отлично видит все возможности для оптимизации и всё отлично оптимизирует, если позволяет семантика (в данном случае fp-model) и попытки оптимизировать это вручную не могут привести ни к чему, кроме как к тому, чтобы помешать компилятору сгенерировать оптимальный код. И делается это на уровне высокоуровневой оптимизации циклов и векторизатора, а не распределителя регистров, как создаётся впечатление из статьи.
В приведённом примере с частичными суммами, компилятор отлично видит все возможности для оптимизации и всё отлично оптимизирует, если позволяет семантика (в данном случае fp-model) и попытки оптимизировать это вручную не могут привести ни к чему, кроме как к тому, чтобы помешать компилятору сгенерировать оптимальный код. И делается это на уровне высокоуровневой оптимизации циклов и векторизатора, а не распределителя регистров, как создаётся впечатление из статьи.
Проблема, как она мне видится, не в том, что компилятор не умеет выдавать оптимальный код.
В конкретном описанном случае переплюнуть векторное суммирование принципиально невозможно.
А теперь представим, что программа скомпилирована под avx2, а исполняться будет на avx512 или avx1024.
Изначально вопрос был: а можно ли, скомпилировать один раз, а потом использовать на более новых процессорах максимально эффективно.
Похоже, что можно, пусть практическая ценность вот прямо сейчас минимальна, но важна ведь идея.
В конкретном описанном случае переплюнуть векторное суммирование принципиально невозможно.
А теперь представим, что программа скомпилирована под avx2, а исполняться будет на avx512 или avx1024.
Изначально вопрос был: а можно ли, скомпилировать один раз, а потом использовать на более новых процессорах максимально эффективно.
Похоже, что можно, пусть практическая ценность вот прямо сейчас минимальна, но важна ведь идея.
Поздравляю, вы придумали идею Java :)
А что если код скомпилирован для ARM, а хочется исполнять на SPARC? Как быть?
> Изначально вопрос был: а можно ли, скомпилировать один раз, а потом использовать на более новых процессорах максимально эффективно.
Лично я этого вопроса в статье не увидел.
Единственный способ в современном мире писать переносимые программы — это писать их в максимально понятном компилятору виде и рассчитывать на то, что он их хорошо оптимизирует. Если хочется убедиться, что у компилятора не возникло проблем с анализом зависимостей по данным и прочими неожиданными нюансами — надо добавить прагму ivdep или ещё кое-какие. Или писать на явно параллельных языках (ispc) или расширениях (Cilk+, OpenMP, OpenCL).
Или можно скомпилоровать для нескольких архитектур одновременно (для icc это -ax<список архитектур> — аля -axSSE4.1,AVX,MIC-AVX512)
Что пытались сказать на эту тему статье — не понял, честно. Для будущих архитектур можно или перекомпилировать, или полагаться бинарную трансляцию / рантайм поддержку (виртуальную машину).
А что если код скомпилирован для ARM, а хочется исполнять на SPARC? Как быть?
> Изначально вопрос был: а можно ли, скомпилировать один раз, а потом использовать на более новых процессорах максимально эффективно.
Лично я этого вопроса в статье не увидел.
Единственный способ в современном мире писать переносимые программы — это писать их в максимально понятном компилятору виде и рассчитывать на то, что он их хорошо оптимизирует. Если хочется убедиться, что у компилятора не возникло проблем с анализом зависимостей по данным и прочими неожиданными нюансами — надо добавить прагму ivdep или ещё кое-какие. Или писать на явно параллельных языках (ispc) или расширениях (Cilk+, OpenMP, OpenCL).
Или можно скомпилоровать для нескольких архитектур одновременно (для icc это -ax<список архитектур> — аля -axSSE4.1,AVX,MIC-AVX512)
Что пытались сказать на эту тему статье — не понял, честно. Для будущих архитектур можно или перекомпилировать, или полагаться бинарную трансляцию / рантайм поддержку (виртуальную машину).
Я бы еще добавил вариант использовать LLVM и компилировать код в IR, но да, это уже ближе к подходу джавы.
Ну да, но это вариация на тему. Apple сейчас как раз пользуется этим подходом — требует сабмитить приложения в LLVM IR в их стор.
Правда не стоит забывать, что LLVM IR строго говоря является платформенно-зависимым, так как все ABI ловеренги происходят во фронтенде и все оптимизации происходят со знанием таргет-архитектуры (я про класс DataLayout).
Правда не стоит забывать, что LLVM IR строго говоря является платформенно-зависимым, так как все ABI ловеренги происходят во фронтенде и все оптимизации происходят со знанием таргет-архитектуры (я про класс DataLayout).
Ну тут уже видимо или шашечки или ехать. Можно задавать все типы с фиксированным размером и выравниванием, можно выбирать оптимизации не полагающиеся на DataLayout, можно тупо не оптимизировать наконец, но смысл тогда вообще во всей затее? :)
>но смысл тогда вообще во всей затее?
Смотря в какой затее. Если вообще смысл этой «платформо-независимости» LLVM IR — то тут понятно, один оптимизатор работает для всех архитектур и все счастливы.
Если речь про то, зачем распространять приложения в LLVM IR — оптимизация под конкретную микроархитектуру (но это тоже кажется что не главное) и гораздо более простой анализ кода (что для аппстора куда более важно).
Смотря в какой затее. Если вообще смысл этой «платформо-независимости» LLVM IR — то тут понятно, один оптимизатор работает для всех архитектур и все счастливы.
Если речь про то, зачем распространять приложения в LLVM IR — оптимизация под конкретную микроархитектуру (но это тоже кажется что не главное) и гораздо более простой анализ кода (что для аппстора куда более важно).
Моя вина — не донес основную мысль
Эта статья не о том, как улучшить кодогенерацию под конкретный процессор еще на 1%.
А скорее интерес пощупать возможную синергию между (абстрактными) компилятором и процессором.
Вот спарк — замечательны процессор, у него масштабируемое к-во регистров, в определенных (и нетривиальных) случаях код может обходиться без обращения к памяти. Но довеском идет и ряд проблем.
В epic в добавок еще пытаются масштабировать функциональные устройства. Результат тоже пока не очень.
Регистровая архитектура — замечательная концепция, позволяющая компилятору быстро выдавать почти идеальный код.
Суперскалярный процессор — отличная идея, увы, производительность упирается во внутреннюю сложность.
Технологические возможности производителей процессоров выше способности их (возможности) переварить, что странно.
Возможности компиляторов упираются в особенности архитектур и их сложность тоже начинает расти непропорционально полезному результату.
Я утрирую, конечно, и тем не менее.
Вот у меня есть мысль и я её думаю :)
Мысль о том, как подать суперскалярному ядру уже частично размеченный зависимостями код.
Так что я пишу потихоньку простой компилятор, виртуальную машину к нему.
А данная статья побочный эффект, что-ли. Еще раз извиняюсь, что не выделил основной вопрос.
Он в том, можно ли на суперскалярном ядре написать такой код для простого суммирования массива, что
при любом (масштабируемом) числе независимых функциональных устройств они будут использованы по максимуму.
Эта статья не о том, как улучшить кодогенерацию под конкретный процессор еще на 1%.
А скорее интерес пощупать возможную синергию между (абстрактными) компилятором и процессором.
Вот спарк — замечательны процессор, у него масштабируемое к-во регистров, в определенных (и нетривиальных) случаях код может обходиться без обращения к памяти. Но довеском идет и ряд проблем.
В epic в добавок еще пытаются масштабировать функциональные устройства. Результат тоже пока не очень.
Регистровая архитектура — замечательная концепция, позволяющая компилятору быстро выдавать почти идеальный код.
Суперскалярный процессор — отличная идея, увы, производительность упирается во внутреннюю сложность.
Технологические возможности производителей процессоров выше способности их (возможности) переварить, что странно.
Возможности компиляторов упираются в особенности архитектур и их сложность тоже начинает расти непропорционально полезному результату.
Я утрирую, конечно, и тем не менее.
Вот у меня есть мысль и я её думаю :)
Мысль о том, как подать суперскалярному ядру уже частично размеченный зависимостями код.
Так что я пишу потихоньку простой компилятор, виртуальную машину к нему.
А данная статья побочный эффект, что-ли. Еще раз извиняюсь, что не выделил основной вопрос.
Он в том, можно ли на суперскалярном ядре написать такой код для простого суммирования массива, что
при любом (масштабируемом) числе независимых функциональных устройств они будут использованы по максимуму.
> можно ли на суперскалярном ядре…
Нельзя. Нельзя в современной парадигме, когда есть программный уровень, который полностью контролируется программистом и хардварный, который просто исполняет (пусть и с некоторыми железячными оптимизациями, как то внеочередное исполнение). В этой парадигме код обязан быть сгенерирован для данной конкретной архитектуры для максимальной производительности (банальное знание о количестве исполняющих устройств в конкретной микроархритектуре может заметно повлиять на качество кода).
Для решения вашей задачи нужен промежуточный уровень — это или бинарная трансляция (не важно встроена она в чип или находится в ОС), или виртуальная машина.
Нельзя. Нельзя в современной парадигме, когда есть программный уровень, который полностью контролируется программистом и хардварный, который просто исполняет (пусть и с некоторыми железячными оптимизациями, как то внеочередное исполнение). В этой парадигме код обязан быть сгенерирован для данной конкретной архитектуры для максимальной производительности (банальное знание о количестве исполняющих устройств в конкретной микроархритектуре может заметно повлиять на качество кода).
Для решения вашей задачи нужен промежуточный уровень — это или бинарная трансляция (не важно встроена она в чип или находится в ОС), или виртуальная машина.
«Единственный способ в современном мире» избавиться от парадигм — не использовать парадигмы :)
Вот конкретно описанный метод вычисления суммы пирамидкой даёт такую формальную возможность.
Вот конкретно описанный метод вычисления суммы пирамидкой даёт такую формальную возможность.
Вычисление пирамидкой — это переход к другой парадигме :)) Это другой алгоритм, с другими свойствами, а не некоторое универсальное представление, которое годится для всех. Вообще, мне кажется это очень плохой пример, который абсолютно не описывает то, что вы хотели продемонстрировать.
Я нигде не говорил об универсальности,
локальная задача, локальное решение.
С одной стороны. А с другой — весьма распространенный вид зависимостей по данным.
Сумма да произведение — вот и вся арифметика :)
локальная задача, локальное решение.
С одной стороны. А с другой — весьма распространенный вид зависимостей по данным.
Сумма да произведение — вот и вся арифметика :)
Я так понял идея была как раз в некотором универсально представлении, которое легко можно положить на любую архитектуру за счёт знания о структуре и свойстве алгоритма.
А так, любой высокоуровневый оптимизатор циклов и векторизатор делает всё, о чём вы рассказали, и даже намного больше (именно в плане выяснения свойств алгоритма и анализа возможных путей оптимизации).
А так, любой высокоуровневый оптимизатор циклов и векторизатор делает всё, о чём вы рассказали, и даже намного больше (именно в плане выяснения свойств алгоритма и анализа возможных путей оптимизации).
Про любую архитектуру я тоже не говорил :)
А так да.
Но в данной статье рассматривается лишь вопрос об устранении зависимостей при суммировании.
Зависимость в данных такая штука, что если она есть, её не объедешь ни на одной архитектуре.
А за счет алгебраических преобразований кое что сделать можно.
Да, я знаю, современные компиляторы умеют пользоваться алгебраическими преобразованиями.
Но в рамках целевой архитектуры.
А хочется универсальности.
SIMD не предлагать :)
А так да.
Но в данной статье рассматривается лишь вопрос об устранении зависимостей при суммировании.
Зависимость в данных такая штука, что если она есть, её не объедешь ни на одной архитектуре.
А за счет алгебраических преобразований кое что сделать можно.
Да, я знаю, современные компиляторы умеют пользоваться алгебраическими преобразованиями.
Но в рамках целевой архитектуры.
А хочется универсальности.
SIMD не предлагать :)
У вас опять всё в кучу. Анализ зависимостей проводится вне зависимости от архитектуры, как и изменение структуры циклов/вычислений. Архитектура имеет значение только при принятии решения об целесообразности преобразования.
Если вы хотите универсальности — надо думать о представлении алгоритма, в котором максимально представлены все свойства необходимые для оптимизации под конкретную (произвольную) архитектуру. И это интересный вопрос.
Если вы хотите максимальной агрессивности оптимизации — надо наращивать аналитически мускулы конкретного оптимизатора.
Если вы хотите универсальности — надо думать о представлении алгоритма, в котором максимально представлены все свойства необходимые для оптимизации под конкретную (произвольную) архитектуру. И это интересный вопрос.
Если вы хотите максимальной агрессивности оптимизации — надо наращивать аналитически мускулы конкретного оптимизатора.
Изначально вопрос был: а можно ли, скомпилировать один раз, а потом использовать на более новых процессорах максимально эффективно.
Похожая задача в значительно более острой форме стоит для GPGPU вычислений, т.к. вариабельность GPU намного выше чем вариабельность CPU. И ничего лучшего чем тупо хранить исходный код и компилировать его на месте под нужный GPU там пока не придумали. Потихоньку правда есть движение в сторону того чтобы хранить не прямо сырцы а уже распарсенное фронт-эндом синтаксическое дерево.
Ну и Java там где производительность менее критична, да :)
Clang (3.7 с -O4) сгенерировал оптимизированный код уже сразу из первого варианта (где без подсказок).
Тогда вопрос: и зачем? Don't help the compiler.
Тогда вопрос: и зачем? Don't help the compiler.
Уважаемый сэр, обращаю Ваше внимание на один простой факт: изменение порядка суммирования float-ов меняет конечный результат.
Режим /fp:precise гарантирует что компилятор сумму посчитает именно так как написано в коде — последовательно. Ваш «код с подсказкой для компилятора» дает другой результат и если компилятор подобное сам забабахает в режиме /fp:precise то это будет ошибкой. Отсюда и наблюдается драматическая разница. Для интереса можете повторить эксперимент на сумме int-ов :)
Подобные ньюансы кажутся мелочами ровно до первого случая когда влетаешь в проблему связанную с мааааленькими ошибочками округления из-за которых программа при включении /fp:fast внезапно начинает крэшиться из-за возникнования отрицательного числа в выражении которое ну никак казалось бы отрицательным быть не может :)
Режим /fp:precise гарантирует что компилятор сумму посчитает именно так как написано в коде — последовательно. Ваш «код с подсказкой для компилятора» дает другой результат и если компилятор подобное сам забабахает в режиме /fp:precise то это будет ошибкой. Отсюда и наблюдается драматическая разница. Для интереса можете повторить эксперимент на сумме int-ов :)
Подобные ньюансы кажутся мелочами ровно до первого случая когда влетаешь в проблему связанную с мааааленькими ошибочками округления из-за которых программа при включении /fp:fast внезапно начинает крэшиться из-за возникнования отрицательного числа в выражении которое ну никак казалось бы отрицательным быть не может :)
Я об этом честно написал, разе нет?
Ну у меня статья оставила впечатление разбора «как улучшить код чтобы помочь тупому компилятору который не может обойти зависимости по данным». А компилятор-то как раз здесь отнюдь не туп. Если Вы разрешаете изменять порядок суммирования — то нафига разбирать варианты с /fp:precise? Стоило бы написать в другом ключе: разобрать что такое /fp:fast vs /fp:precise, показать насколько драматичный выигрыш дает fp:fast и как можно получить тот же результат модификацией кода если по каким-то причинам fp:fast при компиляции использовать вдруг не получается (хотя мне сложно представить почему). Это то что касается первой, содержательной части статьи.
Что касается второй части — то это просто очень сырая идея и вдобавок велосипед, т.к. задача суммирования «деревом» на массивно-параллельной архитектуре является классикой программирования для GPU и очень давно подробно иследована и разобрана. Было бы любопытно увидеть результаты подобной оптимизации на суперскалярах, но как раз ее-то у Вас в статье и нет
Что касается второй части — то это просто очень сырая идея и вдобавок велосипед, т.к. задача суммирования «деревом» на массивно-параллельной архитектуре является классикой программирования для GPU и очень давно подробно иследована и разобрана. Было бы любопытно увидеть результаты подобной оптимизации на суперскалярах, но как раз ее-то у Вас в статье и нет
Видимо, мне следовало более внятно написать о цели статьи,
а именно (уже писал выше), ответить на вопрос можно ли на суперскалярном ядре написать такой код для простого суммирования массива, что при любом (масштабируемом) числе независимых функциональных устройств они будут использованы по максимуму.
а именно (уже писал выше), ответить на вопрос можно ли на суперскалярном ядре написать такой код для простого суммирования массива, что при любом (масштабируемом) числе независимых функциональных устройств они будут использованы по максимуму.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Знакомьтесь, loop fracking