Попробуйте еще Metis, если он компиллируется и дает хотя бы разумную производительность, это вам сильно расширяет класс применений. Это код на C (правда, не интересовался, какой версии С), надеюсь возни минимум.
Ага, википедия говорит, только в самсунговских Exynos 5 есть Mali T6xx. А эти самсунги вроде как не добры к линуксу.
То что вы рассказываете звучит здорово, в перспективе. Я сейчас купил андроидную приставку к телевизору на RK3066, с целью погонять на нем линукс и проверить производительность в расчетах. Ну и думал, что может есть способ граф. процессор завести. Похоже, не судьба — там только Mali 400 (OpenVG, OpenGL). А вот ява на таком маленьком устройстве меня совсем не радует.
Я вот пытаюсь найти какую-то информацию об этом, может у вас понимание есть: у ARM'ов их графпроцессоры в принципе возможно нагрузить GPGPU? Ведь в отличие от Nvidia etc у них графпроцессор живет в том же адресном пространстве, что и сам CPU, за счет чего нет необходимости долго и мучительно копировать данные туда-сюда? Если я что-то путаю, поправьте плиз. Если на этом Mali можно запустить GPGPU счет — это будет нечто.
Ну вот я бы на этот процессор стал бы смотреть, если доступны тесты следующего (в порядке важности):
— плотные матричные умножения, выполненные в технике Libsmm по ссылке выше (классический Atlas, OpenBLAS etc чхать на малые матрицы хотели, а Libsmm дает до 50-кратного прироста против OpenBLAS). Интересуют матрично-матричные и матрично-векторные.
— разреженные матричные умножения (CSR), блочно-разреженные форматы (посмотрите, например OSKI) — последние часто сводят к очереди умножений плотных блоков, а их можно выполнять вызовами к аналогу Libsmm.
— preconditioned conjugate gradient: достаточно хотя бы диагонального прекондишинера. Интересуют матрицы (в порядке приоритета): плотные, разреженные, блочно-диагональные с плотными и разреженными блоками.
— Lanczos algorithm
— факторизация холеского для плотных и разреженных матриц.
— решение треугольных систем (результат матричной факторизации): плотные, разреженные.
— очень хорошо, если оказывается, что железяка быстро в железе вычисляет корни, синусы и прочее трансцендентное (будут очень рады спец-функциям). Без хотя бы корня в железе вас сразу классифицируют в общий ряд с arduino. Вот еще типичное обсуждение (http://software.intel.com/en-us/forums/topic/277543).
— очень хорошо, если понятно как процессор справляется с относительно случайным доступом в память, например когда бежит по графу. Непрямо на это будет указывать производительность в разреженной алгебре, но спецов по графам это не очень устроит. Если у вас получится скомпиллировать Metis, это будет прорыв.
— ньютоновский градиентный спуск, с разреженной и плотной матрицей. Тот же interior point method формирует блочную матрицу, где есть много нулевых блоков, просто плотной матрицей не обойдетесь.
Для всего этого зоопарка — шкалируемость производительности с числом клеток, оценка GFLOPS и memory bandwidth как функция размера задачи. Ведь ваша главная продажная ценность — «оно само распараллеливает, программисту на С ничего делать не надо». Никакого OpenMP, MPI… Так же очень хорошо, если доступна статистика внутренних счетчиков по классификации PAPI.
Разреженный BLAS нельзя тестировать на случайных матрицах, все на этом обжигаются. Разница в производительности (!) простого матрично-векторного умножения может отличаться в разы в зависимости от структуры разреженности. Всегда берите несколько матриц из реальных задач, часто берут из matrixmarket'а.
Спасибо за развернутый и очень полезный ответ. Крайне поучительно узнать, с какими задачами сталкиваются в параллельной реальности :) Еще ваш ответ мне напомнил деятельность хабраюзера TheShade, который таким способом искал (а может и продолжает искать) оптимальные настройки Java-машин.
Конкретно про регрессию — лично для меня выстрелил ваш ответ про то, что тригонометрические функции аппроксимируют приближенно там, где можно точно.
И еще очень поучительно про катастрофу ошибок.
А вы не встречали случаем сравнений ГП (в широком смысле) с монте-карлой с марковскими цепями, алгоритм Метрополиса? Интуитивно кажется, что это все про одно и то же, только язык разный. И в отличие от ГП, для марковских цепей тут недавно некая группа исследователей продвигала идею настраивать вероятности перехода в цепи маркова так, чтобы в итоге монте-карла сходилась не просто так, а бежала по геодезической (!) в соответствующем многообразии вероятностной меры. До конца я их идею не понял, но общего образования хватает, чтоб понять: вместо поиска, направленного как-то, они предлагают выбирать преимущественное направление следущего шага так, что он в среднем бежал к оптимуму по кратчайшему пути. Если интересно, попробую вспомнить/найти ключевые слова для поиска.
Вы все правильно говорите, когда разговор заходит о широком классе задач с неизвестной структурой предметной области. Тут и правда, остается только закодировать широкий набор эволюционных стратегий и молиться на теорему Пуанкаре о возвращении. Благо, оно работает лучше, чем просто случайное блуждание, и, в общем, неясно почему. (Рассуждения об эффективности эволюции меня не очень устраивают, пока нет доказательных исследований, какие конкретно эволюционные стратегии приводят к каким результатам — с цифрами в руках на больших выборках для специфических задач. А судя по каментам выше, общей теории нет и неясно, возможна ли она.)
Другое дело, когда речь идет о конкретной задаче регрессии, где структура предметной области известна и неплохо изучена. В этом частном случае применение ГП по меньшей мере заставляет задавать вопросы, ибо, казалось бы, можно взять аппроксиманд Паде, из априорной оценки точности определить требуемые степени полиномов числителя и знаменателя, а затем решить банальную систему линейных уравнений. Вычислительно это должно быть в разы, если не в десятки раз эффективнее. Другое дело, будет ли результат обладать интересующими вас свойствами, которые вы не закодировали набором точек. Но ведь, кажется, вы в данном топике даете пример только регрессии?
Да, есть класс вычислительных задач (например, методы конечных элементов, у химиков DFT) где плотные матрицы небольшого размера. Для универсальности представьте себе разреженно-блочную матрицу с относительно небольшими плотными блоками. Разреженная матрица будет большая, но очередь умножений ее плотных блоков можно разрезать на куски небольшого размера. Если есть техническая возможность такой кусок данных быстро закачать в память мультиклета, там быстро умножить и быстро же вернуть обратно, то да, может быть актуально. Еще лучше, если мультиклет будет жить в одном адресном пространстве с основной памятью, тогда не придется копировать данные туда-сюда, как в современных GPU.
А вот пример реального кода, где используют маленькие матрицы, даже специальный аналог атласа написали для очень маленьких матриц: www.hector.ac.uk/cse/distributedcse/reports/cp2k03/cp2k03/node9.html
Фактически этот код — месиво из bash'евских скриптов и фортранного кода. Они автоматически генерят кучу версий фортранных матричных умножателей для всех комбинаций размеров двух матриц с разными способами развернуть циклы — и проверяют, какая версия работает быстрее. В конечном итоге их аналог dgemm'а выглядит так:
— если надо умножить матрицы [1 x 3] * [3 x 4], вызываем multiply1x3x3x4
— если надо умножить матрицы [2 x 3] * [3 x 4], вызываем multiply2x3x3x4
…
В моем текущем проекте (Nektar++) маленькие матрицы тоже актуальны.
Спасибо за достаточно развернутый и популярный комментарий начинки этого мультиклета. Осталось непонятным: у него один коммутатор (тогда никакой надежности, увы) или одноранговое кольцо коммутаторов?
И еще, раз у вас есть компиллятор C, вы уже дошли до стадии, когда можно запустить Atlas и проверить производительность матричных умножений?
Крайне контр-интуитивно то, что, по вашим словам, чем больше эквивалентных представлений мы допускаем, тем больше вероятность сойтись быстрее. И кажется, вы слегка себе противоречите, добавляя про ухудшение сходимости при добавлении дополнительных функций. Ведь дополнительные функции только расширяют класс эквивалентности? :)
Не могли бы вы дать пример, когда вы в реальной задаче использовали ГП? У меня таких задач не было, вот и пытаюсь отделить мух от котлет.
о том, что дубликаты генов полезны я уже много раз слышал, но сам я с генетическим программированием не игрался (в отличие от компьютерной алгебры), поэтому мне трудно в это поверить на слово. Потому всем и всегда задаю вопрос: откуда следует, что эти дубликаты полезнее, чем альтернативные способы организации поиска? Примеры альтернатив: часто добавлять случайные поддеревья (может быть эквивалентно мутациям в «мертвом коде»), забить на формулировки генетического программирования и искать рациальных аппроксимаций. Кто-нибудь этот вопрос исследовал? Спрашиваю не чтоб подколоть, мне правда интересен ответ. Потому что априори генетическое программирование в применении к математическим выражениям для меня (математика по образованию, плотно работавшему с компьютерной алгеброй) выглядит псевдонаучной магией.
сюда же вопрос: вы сами пишете об оптимизациях, фактически — частичных упрощениях формул. Ваши оптимизации могут значительно изменять синтаксическое дерево формулы. Как быть с предполагаемой гладкостью пространства поиска? Наивно рассуждая, тут либо нужно бороться за гладкость, либо решительно все упрощать. Но во втором случае может есть смысл пойти еще дальше и ограничить класс функций-приближений, например, рациональными.
ОК, значит мертвые участки кода помогают. Но как часто? Можно ли построить какую-то статистику, доказывающую на (пусть игрушечном) примере, что допускать мертвый код выгоднее (быстрее сойдемся), чем добавлять случайные ветки к формулам без мертвых участков?
Всякий раз, когда я вижу попытки применять генетическое программирование к поиску математических формул, у меня возникают вопросы, на которые пока не нашел ответа, а докладчики мялись и не телились (может, не повезло пока):
— часто применяющие генетическое программирование не догадываются о существовании функции simplify() в почти каждой системе компьютерной алгебры. Один такой персонаж на докладе как-то сокрушался, что у него случается code bloat очевидно сокращаемых выражений, но технологии сокращения у него не было.
— всякую формулу можно переписать в эквивалентном символьном представлении: например, добавить и тут же вычесть некое выражение, а потом скобки переставить. Это наверняка заспамливает пространство случайного поиска, нет? Иными словами, у меня есть сильное подозрение, что генетическое программирование себя хуже ведет в применении к символьным математическим выражениям, чем к иным областям, где «классы эквивалентности» (как угодно определенные) меньше. Вы с этим как-то явно боретесь?
— отдельный случай предыдущего вопроса. Если разрешать вычислять аналитические функции только от мономов, а связывать их арифметическими операциями (чтоб исключить случай вроде \sqrt{x+y}), то цепочку последовательных делений (подходящую дробь) можно привести к нормальному виду (отношению двух выражений полиномиального вида). Таким образом поиск всякого выражения с делением в алфавите можно свести к поиску рациональной функции с заранее неизвестными степенями полиномов в числителе и знаменателе. С точки зрения качества приближения, искать рациональную функцию определенной степени числителя и знаменателя заведомо выгоднее, чем априори произвольное выражение, которое уже затем эквивалентно некоторой рациональной функции. И уж раз вы решаете задачу регрессии, то вычислительно дешевле рациональное приближение, аппроксимирующее тот же корень. Что на этот счет говорит мега-теория генетического программирования?
То что вы рассказываете звучит здорово, в перспективе. Я сейчас купил андроидную приставку к телевизору на RK3066, с целью погонять на нем линукс и проверить производительность в расчетах. Ну и думал, что может есть способ граф. процессор завести. Похоже, не судьба — там только Mali 400 (OpenVG, OpenGL). А вот ява на таком маленьком устройстве меня совсем не радует.
— плотные матричные умножения, выполненные в технике Libsmm по ссылке выше (классический Atlas, OpenBLAS etc чхать на малые матрицы хотели, а Libsmm дает до 50-кратного прироста против OpenBLAS). Интересуют матрично-матричные и матрично-векторные.
— разреженные матричные умножения (CSR), блочно-разреженные форматы (посмотрите, например OSKI) — последние часто сводят к очереди умножений плотных блоков, а их можно выполнять вызовами к аналогу Libsmm.
— preconditioned conjugate gradient: достаточно хотя бы диагонального прекондишинера. Интересуют матрицы (в порядке приоритета): плотные, разреженные, блочно-диагональные с плотными и разреженными блоками.
— Lanczos algorithm
— факторизация холеского для плотных и разреженных матриц.
— решение треугольных систем (результат матричной факторизации): плотные, разреженные.
— очень хорошо, если оказывается, что железяка быстро в железе вычисляет корни, синусы и прочее трансцендентное (будут очень рады спец-функциям). Без хотя бы корня в железе вас сразу классифицируют в общий ряд с arduino. Вот еще типичное обсуждение (http://software.intel.com/en-us/forums/topic/277543).
— очень хорошо, если понятно как процессор справляется с относительно случайным доступом в память, например когда бежит по графу. Непрямо на это будет указывать производительность в разреженной алгебре, но спецов по графам это не очень устроит. Если у вас получится скомпиллировать Metis, это будет прорыв.
— ньютоновский градиентный спуск, с разреженной и плотной матрицей. Тот же interior point method формирует блочную матрицу, где есть много нулевых блоков, просто плотной матрицей не обойдетесь.
Для всего этого зоопарка — шкалируемость производительности с числом клеток, оценка GFLOPS и memory bandwidth как функция размера задачи. Ведь ваша главная продажная ценность — «оно само распараллеливает, программисту на С ничего делать не надо». Никакого OpenMP, MPI… Так же очень хорошо, если доступна статистика внутренних счетчиков по классификации PAPI.
Разреженный BLAS нельзя тестировать на случайных матрицах, все на этом обжигаются. Разница в производительности (!) простого матрично-векторного умножения может отличаться в разы в зависимости от структуры разреженности. Всегда берите несколько матриц из реальных задач, часто берут из matrixmarket'а.
Конкретно про регрессию — лично для меня выстрелил ваш ответ про то, что тригонометрические функции аппроксимируют приближенно там, где можно точно.
И еще очень поучительно про катастрофу ошибок.
А вы не встречали случаем сравнений ГП (в широком смысле) с монте-карлой с марковскими цепями, алгоритм Метрополиса? Интуитивно кажется, что это все про одно и то же, только язык разный. И в отличие от ГП, для марковских цепей тут недавно некая группа исследователей продвигала идею настраивать вероятности перехода в цепи маркова так, чтобы в итоге монте-карла сходилась не просто так, а бежала по геодезической (!) в соответствующем многообразии вероятностной меры. До конца я их идею не понял, но общего образования хватает, чтоб понять: вместо поиска, направленного как-то, они предлагают выбирать преимущественное направление следущего шага так, что он в среднем бежал к оптимуму по кратчайшему пути. Если интересно, попробую вспомнить/найти ключевые слова для поиска.
Другое дело, когда речь идет о конкретной задаче регрессии, где структура предметной области известна и неплохо изучена. В этом частном случае применение ГП по меньшей мере заставляет задавать вопросы, ибо, казалось бы, можно взять аппроксиманд Паде, из априорной оценки точности определить требуемые степени полиномов числителя и знаменателя, а затем решить банальную систему линейных уравнений. Вычислительно это должно быть в разы, если не в десятки раз эффективнее. Другое дело, будет ли результат обладать интересующими вас свойствами, которые вы не закодировали набором точек. Но ведь, кажется, вы в данном топике даете пример только регрессии?
А вот пример реального кода, где используют маленькие матрицы, даже специальный аналог атласа написали для очень маленьких матриц:
www.hector.ac.uk/cse/distributedcse/reports/cp2k03/cp2k03/node9.html
Фактически этот код — месиво из bash'евских скриптов и фортранного кода. Они автоматически генерят кучу версий фортранных матричных умножателей для всех комбинаций размеров двух матриц с разными способами развернуть циклы — и проверяют, какая версия работает быстрее. В конечном итоге их аналог dgemm'а выглядит так:
— если надо умножить матрицы [1 x 3] * [3 x 4], вызываем multiply1x3x3x4
— если надо умножить матрицы [2 x 3] * [3 x 4], вызываем multiply2x3x3x4
…
В моем текущем проекте (Nektar++) маленькие матрицы тоже актуальны.
И еще, раз у вас есть компиллятор C, вы уже дошли до стадии, когда можно запустить Atlas и проверить производительность матричных умножений?
Крайне контр-интуитивно то, что, по вашим словам, чем больше эквивалентных представлений мы допускаем, тем больше вероятность сойтись быстрее. И кажется, вы слегка себе противоречите, добавляя про ухудшение сходимости при добавлении дополнительных функций. Ведь дополнительные функции только расширяют класс эквивалентности? :)
Не могли бы вы дать пример, когда вы в реальной задаче использовали ГП? У меня таких задач не было, вот и пытаюсь отделить мух от котлет.
— часто применяющие генетическое программирование не догадываются о существовании функции simplify() в почти каждой системе компьютерной алгебры. Один такой персонаж на докладе как-то сокрушался, что у него случается code bloat очевидно сокращаемых выражений, но технологии сокращения у него не было.
— всякую формулу можно переписать в эквивалентном символьном представлении: например, добавить и тут же вычесть некое выражение, а потом скобки переставить. Это наверняка заспамливает пространство случайного поиска, нет? Иными словами, у меня есть сильное подозрение, что генетическое программирование себя хуже ведет в применении к символьным математическим выражениям, чем к иным областям, где «классы эквивалентности» (как угодно определенные) меньше. Вы с этим как-то явно боретесь?
— отдельный случай предыдущего вопроса. Если разрешать вычислять аналитические функции только от мономов, а связывать их арифметическими операциями (чтоб исключить случай вроде \sqrt{x+y}), то цепочку последовательных делений (подходящую дробь) можно привести к нормальному виду (отношению двух выражений полиномиального вида). Таким образом поиск всякого выражения с делением в алфавите можно свести к поиску рациональной функции с заранее неизвестными степенями полиномов в числителе и знаменателе. С точки зрения качества приближения, искать рациональную функцию определенной степени числителя и знаменателя заведомо выгоднее, чем априори произвольное выражение, которое уже затем эквивалентно некоторой рациональной функции. И уж раз вы решаете задачу регрессии, то вычислительно дешевле рациональное приближение, аппроксимирующее тот же корень. Что на этот счет говорит мега-теория генетического программирования?