Мне кажется, что идея двух компьютеров, которые управляют по очереди, немного странная. Это разве не случай "#define true (rand() & 1) //happy debugging"?
А знают ли об этой фиче те, кто проверяют самолёты на исправность?
Судя по описанию, контракты — это просто ещё один вариант assert. Не могу найти информации, чтобы компилятор имел право оптимизировать код на основе знания о том, что предусловия всегда верны. Говорить, что контракты — это аналог assume, это примерно как говорить, что старые throw-описания являются аналогами нового noexcept.
std::assume_aligned выглядит как какой-то крайне частный случай.
Во современных компиляторах есть __assume(condition) или __builtin_unreachable, при помощи которых можно сообщать оптимизатору любую доп. информацию. Вместо того, чтобы вводить специальную функцию только для выравнивания, лучше было стандартизовать функцию assume и дать рекомендации по тому, как с её помощью можно описывать выравнивание.
Да, мне тоже непонятно, зачем писать на чистом C.
Для тех, кому нужна высокая производительность, особенно полезны в C++ именно шаблоны: это абстракция без потери производительности.
Я думаю, это в основном самодисциплина: ограничивая себя в инструменте, люди настраивают себя на определённый стиль программирования.
Очень часто, когда используется C++, люди вовсю используют контейнеры STL, чтобы не думать о работе с памятью, в результате начинаются тормоза из-за огромного количества аллокаций. Если же ограничить себя чистым C, придётся потратить больше времени на продумывание структур данных в памяти, в результате код наверняка будет работать быстрее.
Механизм шаблонов C++ можно частично сэмулировать в чистом C при помощи трюка включения хедера без стража.
Идея довольно простая: есть хедер без стража включения, который содержит шаблонный код. Этот хедер предполагает, что параметры шаблона установлены извне в макросы с именами вроде TYPE, SIZE, и т.п.. Далее можно включать этот хедер много раз, каждый раз устанавливая эти макросы по-разному: получится несколько инстанциирований «шаблона».
Этот механизм никак не мешает MSVC: код можно нормально отлаживать, в нём работает intellisense, и т.п. Естественно, нет никаких проблем с возвращаемыми значениями и указателями на функции. Код безусловно разбухает, но ровно на столько же, насколько разбухает аналогичный код с шаблонами C++.
Упомяну более весёлый аналог: небольшой мод для Crimsonland / Typoshooter, когда-то мной написанный.
Если хочется HEX, могу выслать исходники, там поправить схему генерации вопросов и ответов тривиально =)
Во-первых, можно для начала написать прототип с синхронными запусками ядер и копирований. В большинстве случаев будет прекрасно работать (если ядра делают много вычислений).
Потом можно попробовать что-то типа ленивых вычислений. Достаточно реализовать класс future-буфера, у которого внутри есть cl::Buffer (где будут данные) и cl::Event (когда данные в буфере будут правильными). Ну а дальше сделать обёртку над каждой командой, которая будет сама устанавливать списки ожидания для команд и записывать куда следует cl::Event готовности результата.
В целом кажется, что стоит покурить ключевые слова вроде future/promise/async.
P.S. Писать отдельное декларативное описание ядер и зависимостей между ними в каком-то особом формате — кажется излишним.
SYCL — замечательная задумка. Пока что она сильно молодая, чтобы всерьёз возлагать на неё надежды. Судя по всему, это будет платформенно-независимой версией CUDA runtime.
Должен заметить, что CUDA runtime на порядок удобнее в использовании, чем OpenCL, что затрудняет переход CUDA-поклонников на OpenCL (особенно учёных, которым чихать на кроссплатформенность).
Конечно, SYCL выглядит как-то далековато от простого OpenCL, всюду куча абстракций, на первый взгляд ненужных. Однако какие-то вещи оттуда существенно облегчают работу.
Например, я реализовал в нашем проекте «двойной» типизированный буфер, который существует одновременно на host и device, и синхронизируется автоматически прозрачно для пользователя. Естественно, пользователь должен корректно вызывать функции доступа к сторонам буфера, указывая каждый раз: нужен доступ «только на чтение» или «на чтение и запись».
Чуть позже я узнал о SYCL. В нём sycl::buffer является ровно тем же самым общим типизированным буфером, и для работы с ним надо ровно так же вызывать функцию с указанием типа доступа.
Также в SYCL есть более простой способ использования асинхронной работы.
Короче говоря, лично я надеюсь, что в будущем смогу писать на SYCL =)
но это не избавит от десятков clSetKernelArg подряд
Десяток clSetKernelArg подряд — это C API.
В C++ обёртках ядро принято вызывать примерно как обычную функцию.
Вот пример:
//устанавливаем параметры запуска (кол-во потоков, очередь)
auto launcher = kernel.bind(queue, AlignUp(paramsCnt, 64), 64);
//вызываем ядро, передавая параметры как в обычную функцию
launcher(paramsBuffer, paramsCnt, resultsBuffer);
Здесь аргументы — объекты типа cl::Buffer и примитивные типы.
Хотя должен заметить, что обёртки писались под старый стандарт C++, поэтому количество аргументов ограничено 32 (хотя вроде не сложно это число увеличить). Бывало, в это ограничение я не укладывался =)
Да, C++ обёртка не решает волшебным образом все проблемы именно потому, что она почти полностью соответствует C-шному API.
Чтобы не мучиться постоянно, придётся пописать какие-то классы поверх неё (например типизированный буфер). Будет проще, чем поверх C-шного API.
Мне кажется, API написан на C в первую очередь потому, что его больше не на чем писать. C-шные функции легко использовать из любого языка программирования в любой ситуации. Если делать C++ API первостепенным, то начнётся куча проблем (радости с именованием символов, версии и настройки STL). К тому же, драйверы как-то принято писать на чистом C, а не на C++ со всякими std::vector и std::string=)
Конечно, мне пока что не были необходимы ни синхронизация по событиям, ни тем более разделение буфера на части. Однако мне кажется, что как минимум синхронизация по событиям в C++ обёртках есть, и нет проблем её использовать. В любом случае, такие проблемы уже совсем не для новичков.
К тому же, никто не мешает использовать C++ обёртки почти всюду, а в случае возникновения трудностей перейти на C API в одном конкретном проблемном месте. В этом ещё одно отличиё обёрток от фреймворка: обёртки и исходный API можно легко смешивать (с фреймворкам дело обычно сложнее).
Например, мне пришлось писать извлечение бинарного кода программы на C API из-за бага обёрток. Надо сказать, получилось 25 уродливых строчек с кучей звёздочек, sizeof, и самопальных макросов SAFE_CALL. Если бы не баг в обёртках (который, кстати, никто не мешает исправить самому локально), было бы строчек 2-5.
В спецификации (ссылка выше) об этом написано: «The C++ API corresponds closely to the underlying C API and introduces no additional execution overhead».
Вопрос про производительность вряд ли возникнет у человека, который использует C++ wrappers и мельком видел их внутренности.
Вариант API никак не влияет на код собственно вычислительных программ OpenCL, так что ядра работают абсолютно с одинаковой скоростью. Копирование данных запускает те же самые команды C-шного API, то есть работает столько же времени. Все понятия, такие как асинхронные вызовы например, одинаковы и в C, и в C++.
Чаще всего разница только в том, что вместо прямого вызова C-шной функции вызывается метод класса C++, который внутри вызывает ту же C-шную функцию. Скорее всего он инлайнится, а даже если и нет, overhead от лишнего вызова будет ничтожно мал по сравнению с временем работы самого вызова в драйвере. Ну может быть какой-то overhead есть из-за того, что используется std::vector<cl::device> и std::vector<std::string> вместо вручную выделенных кусков памяти. Но это опять же ничтожно малое время по сравнению с временем инициализации девайса и компиляции программы. Обработка ошибок тоже может отнимать время, но чтобы это стало заметным, надо написать невероятно неэффективную программу с огромным количеством API-вызовов.
По сути C++ обёртка — это просто более удобное использование C-шного API.
Это не фреймворк, это именно обёртки над C API, официальные от Khronos.
Все команды в обёртках являются эквивалентами команд C-шного API, и наоборот, для каждой команды C-шного API есть эквивалент в обёртках. Параметры почти такие же, названия примерно одинаковые. То есть отдёльно «учить» C++ обёртки не нужно: зная C API, можно легко начать пользоваться обёртками.
Среди бонусов:
всюду нормальная типизация вместо void * и размеров в байтах
использование std::vector или cl::vector, cl::string вместо char*
автоматическое отслеживание времени жизни объектов (типа умных указателей)
автоматическая обработка ошибок через исключения (нужно включить)
Я думаю, при освоении OpenCL лучше перейти на официальные C++-обёртки как можно быстрее. Использование C-шного API — лишняя трата ценного времени: тонны параметров, void*, обработка ошибок и пр.
Замечательная статья!
Я конечно не раз пользовался такими хешами, но не подозревал, что можно решать с их помощью столько всяких задач=)
Использовать нечётное число P вместе с модулем M = 2^64 — хорошая идея.
На самом деле можно использовать любой модуль M при вычислениях. Желательно, чтобы M и P были взаимно простыми (например, P=2 и M=10^9 — совсем плохая идея), а P имело большой порядок по модулю M (например, P=10 и M=10^9+1 — не слишком хороший выбор). Можно использовать хеши по нескольким модулям, если коллизии всё-таки возникают.
Совершенно согласен.
Я просто хотел подчеркнуть, что преимущества арифметического кодирования перед кодированием Хаффмана чисто в форме энтропийного кодирования довольно малы. А вот при «кодировании цепочек» арифметическое кодирование действительно существенно лучше. Очень нетривиально адаптировать код Хаффмана к подобной задаче.
Код Хаффмана можно построить за O(KlogK), где K — количество символов алфавита. Также для простоты кодирования можно построить за O(KL) оптимальный код с ограничением L на длину слова сверху (например 31 бит). Для приведенных вами масштабов это ничтожно мало по сравнению с O(N) времени (линейный проход), которое требуется для собственно кодирования. Единственная проблема с использованием традиционного кода Хаффмана — это большие затраты памяти кодера и декодера (ни в какой кеш не влезает). Но и арифметическое кодирование естественным образом эту проблему не решает.
Насколько я понимаю, обратное преобразование BWT можно также выполнить за O(N) времени (например здесь описано).
Move-To-Front, если я не ошибаюсь, можно выполнить за O(N log N) посредством нетривиального использования сбалансированных деревьев. Для алфавита более 256 символов это может быть существенно.
Наконец, мне кажется не совсем правильным делать акцент на том, что арифметическое кодирование сжимает лучше Хаффмана. Дело в том, код Хаффмана невероятно прост (префиксный код), его можно очень быстро кодировать и декодировать. В случае небольшого алфавита можно в кодер Хаффмана подавать блоки по два-три символа — это приблизит коэффициент сжатия к оптимуму (энтропии источника).
В то же время арифметическое кодирование требует умножений и делений, и жутко тормозит по сравнению с Хаффманом. Реальное преимущество арифметического кодирования состоит в возможности варьировать веса символов входного алфавита в процессе кодирования. Вместе с хорошей моделью предсказания последующих символов входного потока арифметическое кодирование может обеспесить коэффициент сжатия лучше, чем арифметическое кодирование само по себе.
Для меня Spectrum тоже был первым компьютером… Мне тогда пять лет было, я ещё в детский садик ходил=)
Игрушки помню очень смутно, зато Basic помню прекрасно! Были познавательные книжки типа «Дядюшка Компьютер»=) Говорят, я скурпулезно перерисовывал латинские буквы из книжки, хотя не умел даже по-русски читать… Помню, в школе меня потом переучивали: писать русскую 'И' вместо латинской 'N', а также не перечёркивать цифру ноль по-диагонали=)
Ну и да, ассемблер мне конечно было тогда рано осваивать.
«Изображение получается таким, каким должно быть в природе» — чересчур пафосное высказывание =)
Насколько я понимаю, рендеринг без допущений означает, что получаемая картинка со временем сходится (как-нибудь там по вероятности) к решению уравнения рендеринга. Так что выглядит оно не в точности как в природе: всё зависит от того, насколько хорошо решаемое уравнение соответсвует реальной физике. Причём уравнение рендеринга не является чем-то незыблемым: например, классическая версия, судя по всему, совсем не учитывает объемные эффекты.
Системная ошибка всегда есть, просто в случае рендереров без допущений она действительно крайне мала.
А знают ли об этой фиче те, кто проверяют самолёты на исправность?
Во современных компиляторах есть __assume(condition) или __builtin_unreachable, при помощи которых можно сообщать оптимизатору любую доп. информацию. Вместо того, чтобы вводить специальную функцию только для выравнивания, лучше было стандартизовать функцию assume и дать рекомендации по тому, как с её помощью можно описывать выравнивание.
Для тех, кому нужна высокая производительность, особенно полезны в C++ именно шаблоны: это абстракция без потери производительности.
Я думаю, это в основном самодисциплина: ограничивая себя в инструменте, люди настраивают себя на определённый стиль программирования.
Очень часто, когда используется C++, люди вовсю используют контейнеры STL, чтобы не думать о работе с памятью, в результате начинаются тормоза из-за огромного количества аллокаций. Если же ограничить себя чистым C, придётся потратить больше времени на продумывание структур данных в памяти, в результате код наверняка будет работать быстрее.
Идея довольно простая: есть хедер без стража включения, который содержит шаблонный код. Этот хедер предполагает, что параметры шаблона установлены извне в макросы с именами вроде TYPE, SIZE, и т.п.. Далее можно включать этот хедер много раз, каждый раз устанавливая эти макросы по-разному: получится несколько инстанциирований «шаблона».
Пример приведён здесь:
http://stackoverflow.com/a/17670232/556899
Этот механизм никак не мешает MSVC: код можно нормально отлаживать, в нём работает intellisense, и т.п. Естественно, нет никаких проблем с возвращаемыми значениями и указателями на функции. Код безусловно разбухает, но ровно на столько же, насколько разбухает аналогичный код с шаблонами C++.
Если хочется HEX, могу выслать исходники, там поправить схему генерации вопросов и ответов тривиально =)
Потом можно попробовать что-то типа ленивых вычислений. Достаточно реализовать класс future-буфера, у которого внутри есть cl::Buffer (где будут данные) и cl::Event (когда данные в буфере будут правильными). Ну а дальше сделать обёртку над каждой командой, которая будет сама устанавливать списки ожидания для команд и записывать куда следует cl::Event готовности результата.
В целом кажется, что стоит покурить ключевые слова вроде future/promise/async.
P.S. Писать отдельное декларативное описание ядер и зависимостей между ними в каком-то особом формате — кажется излишним.
SYCL — замечательная задумка. Пока что она сильно молодая, чтобы всерьёз возлагать на неё надежды. Судя по всему, это будет платформенно-независимой версией CUDA runtime.
Должен заметить, что CUDA runtime на порядок удобнее в использовании, чем OpenCL, что затрудняет переход CUDA-поклонников на OpenCL (особенно учёных, которым чихать на кроссплатформенность).
Конечно, SYCL выглядит как-то далековато от простого OpenCL, всюду куча абстракций, на первый взгляд ненужных. Однако какие-то вещи оттуда существенно облегчают работу.
Например, я реализовал в нашем проекте «двойной» типизированный буфер, который существует одновременно на host и device, и синхронизируется автоматически прозрачно для пользователя. Естественно, пользователь должен корректно вызывать функции доступа к сторонам буфера, указывая каждый раз: нужен доступ «только на чтение» или «на чтение и запись».
Чуть позже я узнал о SYCL. В нём sycl::buffer является ровно тем же самым общим типизированным буфером, и для работы с ним надо ровно так же вызывать функцию с указанием типа доступа.
Также в SYCL есть более простой способ использования асинхронной работы.
Короче говоря, лично я надеюсь, что в будущем смогу писать на SYCL =)
Десяток clSetKernelArg подряд — это C API.
В C++ обёртках ядро принято вызывать примерно как обычную функцию.
Вот пример:
Здесь аргументы — объекты типа cl::Buffer и примитивные типы.
Хотя должен заметить, что обёртки писались под старый стандарт C++, поэтому количество аргументов ограничено 32 (хотя вроде не сложно это число увеличить). Бывало, в это ограничение я не укладывался =)
Чтобы не мучиться постоянно, придётся пописать какие-то классы поверх неё (например типизированный буфер). Будет проще, чем поверх C-шного API.
Конечно, мне пока что не были необходимы ни синхронизация по событиям, ни тем более разделение буфера на части. Однако мне кажется, что как минимум синхронизация по событиям в C++ обёртках есть, и нет проблем её использовать. В любом случае, такие проблемы уже совсем не для новичков.
К тому же, никто не мешает использовать C++ обёртки почти всюду, а в случае возникновения трудностей перейти на C API в одном конкретном проблемном месте. В этом ещё одно отличиё обёрток от фреймворка: обёртки и исходный API можно легко смешивать (с фреймворкам дело обычно сложнее).
Например, мне пришлось писать извлечение бинарного кода программы на C API из-за бага обёрток. Надо сказать, получилось 25 уродливых строчек с кучей звёздочек, sizeof, и самопальных макросов SAFE_CALL. Если бы не баг в обёртках (который, кстати, никто не мешает исправить самому локально), было бы строчек 2-5.
Вопрос про производительность вряд ли возникнет у человека, который использует C++ wrappers и мельком видел их внутренности.
Вариант API никак не влияет на код собственно вычислительных программ OpenCL, так что ядра работают абсолютно с одинаковой скоростью. Копирование данных запускает те же самые команды C-шного API, то есть работает столько же времени. Все понятия, такие как асинхронные вызовы например, одинаковы и в C, и в C++.
Чаще всего разница только в том, что вместо прямого вызова C-шной функции вызывается метод класса C++, который внутри вызывает ту же C-шную функцию. Скорее всего он инлайнится, а даже если и нет, overhead от лишнего вызова будет ничтожно мал по сравнению с временем работы самого вызова в драйвере. Ну может быть какой-то overhead есть из-за того, что используется std::vector<cl::device> и std::vector<std::string> вместо вручную выделенных кусков памяти. Но это опять же ничтожно малое время по сравнению с временем инициализации девайса и компиляции программы. Обработка ошибок тоже может отнимать время, но чтобы это стало заметным, надо написать невероятно неэффективную программу с огромным количеством API-вызовов.
По сути C++ обёртка — это просто более удобное использование C-шного API.
Все команды в обёртках являются эквивалентами команд C-шного API, и наоборот, для каждой команды C-шного API есть эквивалент в обёртках. Параметры почти такие же, названия примерно одинаковые. То есть отдёльно «учить» C++ обёртки не нужно: зная C API, можно легко начать пользоваться обёртками.
Среди бонусов:
Хедер
Спецификация
Пока есть только для OpenCL 1.2, новые версии запаздывают.
P.S. Khronos как-то не так написан…
Я конечно не раз пользовался такими хешами, но не подозревал, что можно решать с их помощью столько всяких задач=)
Использовать нечётное число P вместе с модулем M = 2^64 — хорошая идея.
На самом деле можно использовать любой модуль M при вычислениях. Желательно, чтобы M и P были взаимно простыми (например, P=2 и M=10^9 — совсем плохая идея), а P имело большой порядок по модулю M (например, P=10 и M=10^9+1 — не слишком хороший выбор). Можно использовать хеши по нескольким модулям, если коллизии всё-таки возникают.
Я просто хотел подчеркнуть, что преимущества арифметического кодирования перед кодированием Хаффмана чисто в форме энтропийного кодирования довольно малы. А вот при «кодировании цепочек» арифметическое кодирование действительно существенно лучше. Очень нетривиально адаптировать код Хаффмана к подобной задаче.
Move-To-Front, если я не ошибаюсь, можно выполнить за O(N log N) посредством нетривиального использования сбалансированных деревьев. Для алфавита более 256 символов это может быть существенно.
Наконец, мне кажется не совсем правильным делать акцент на том, что арифметическое кодирование сжимает лучше Хаффмана. Дело в том, код Хаффмана невероятно прост (префиксный код), его можно очень быстро кодировать и декодировать. В случае небольшого алфавита можно в кодер Хаффмана подавать блоки по два-три символа — это приблизит коэффициент сжатия к оптимуму (энтропии источника).
В то же время арифметическое кодирование требует умножений и делений, и жутко тормозит по сравнению с Хаффманом. Реальное преимущество арифметического кодирования состоит в возможности варьировать веса символов входного алфавита в процессе кодирования. Вместе с хорошей моделью предсказания последующих символов входного потока арифметическое кодирование может обеспесить коэффициент сжатия лучше, чем арифметическое кодирование само по себе.
Игрушки помню очень смутно, зато Basic помню прекрасно! Были познавательные книжки типа «Дядюшка Компьютер»=) Говорят, я скурпулезно перерисовывал латинские буквы из книжки, хотя не умел даже по-русски читать… Помню, в школе меня потом переучивали: писать русскую 'И' вместо латинской 'N', а также не перечёркивать цифру ноль по-диагонали=)
Ну и да, ассемблер мне конечно было тогда рано осваивать.
Насколько я понимаю, рендеринг без допущений означает, что получаемая картинка со временем сходится (как-нибудь там по вероятности) к решению уравнения рендеринга. Так что выглядит оно не в точности как в природе: всё зависит от того, насколько хорошо решаемое уравнение соответсвует реальной физике. Причём уравнение рендеринга не является чем-то незыблемым: например, классическая версия, судя по всему, совсем не учитывает объемные эффекты.
Системная ошибка всегда есть, просто в случае рендереров без допущений она действительно крайне мала.