честно говоря, я мало что понял. Не могли бы вы чуть подробнее рассказать, что происходит с разделением доступа к ячейкам памяти одной команды скалярного произведения между параграфами?
а сколько тактов занимает одна операция умножения? Fused multiply-add есть? Как себя ведут клетки, когда пытаются читать/записать в одну ячейку памяти?
Соглашусь, что мой стиль предвзят. Это продиктовано тем, что
— конкретно в случае задачи регрессии есть более эффективные решения, и я уже встречался с крайне необдуманными применениями ГП как технологии (я не имею ввиду вас). Что, разумеется, говорит не столько о технологии, сколько о применяющих. С другой стороны, у каждой технологии, кроме собственно технологии, есть свой «маркетинг», и не всегда он приносит пользу тем, кто готов бездумно таковую технологию применить. Под маркетингом я имею ввиду вещи вроде «ТеХом пользоваться очень просто!», «ГП это универсальная технология». Это разумные утверждения, которые как правило не идут против истины, но в конечно счете могут приводить к не самому адекватному расположению рекламируего «товара» в системе представлений.
Может показаться, что я вцепился в ваш пример именно символьной регрессии и упускаю все прочие более удачные применения ГП как технологии. Да, наверное так. Но именно потому, что этот конкретный пример правда считаю крайне неудачным, по описанным выше причинам. Что, еще раз, не говорит, что мне не симпатичен ваш опыт в крайне разнообразных задачах. Мне было интересно посмотреть ваши демки и я вполне согласен, что в ситуации, когда модели нет, ГП поставляет неплохой инструмент для ее поиска.
— чтобы более осознанно выбирать технологию, следует знать об альтернативах и — тут ключевое — иметь возможность сравнивать эффективность этих технологий и отдельных их составляющих. Хотя бы как-нибудь, поэтому академически точными понятиями увы, не всегда можно оперировать. А раз так, я осознанно выбрал стиль беседы «научная курилка», где легко переходят от интуитивных ощущений к формальным определениям и обратно, но все понимают, что задача не теорему доказать, а понимания достичь.
— вы мне исходно показались ГП-евангелистом без кругозора. Тут я признаю свою ошибку. Поэтому я и не отвечал на ваши каменты. Все ваши ответа на мои вопросы о сравнительной эффективности отдельных составляющих ГП даны с точки зрения универсальности ГП и правильности ее применения так, словно альтернатив нет. К тому же, некоторые ваши ответы, на мой взгляд, не несут цели разобраться в содержании, а только добавить формализма. Например, на вопрос о гладкости пространства поиска в свете применения различных оптимизаций, которые фактически являются достаточно значимыми интервенциями в исходную модель, вы лишь отвечаете классификацией собственных оптимизаций. При всем уважении к проделанной вами работе, отвечает ли такая классификация задаче разобраться о гладкости пространства поиска? На мой взгляд нет, но добавляет формализма и наукообразия, и будь я неуверенный студент, меня бы ваш ответ отпугнул вообще любые вопросы задавать. Заметьте, это добавляет наукообразия там, где я как раз стараюсь его избежать. Таким образом, нового понимания ГП у меня в разговоре не возникло. А жаль, могло возникнуть, если б беседа обернулась ссылкой на исследования, где терминология ГП транслируется в модели, напрямую допускающие оценку качества сходимости.
Теперь, спасибо что поймали на терминологических неточностях. Разумеется, физический смысл у точек пространства никуда не исчезает. Имел ввиду следующее: когда нужно посчитать некоторую статсумму, значимый вклад может дать суммирование по достаточно малому подмножеству индексов, и вот каких — заранее может быть неясно. И уже из необходимости как-то выбрать подмножество суммирования вводят распределение вероятностей. Так точнее?
Ваше замечание о моих задачах странное, потому что я никаких своих задач не упоминал.
Не дописал. Ключевое в этой идее — вместо того, чтоб притягивать за уши биологическую аналогию и уже потом вставлять туда костыли типа «а мы придумали новое правило мутации так, чтоб у нас вот тут лучше сходилось, мы проверили», люди рассуждают в терминах чистой теории вероятности: нам надо бежать по пространству, как не знаем, но пусть пробные точки вынимаются из некоторого распределения вероятностей — вот это распределение мы подкручивать и будем. а уже за это отвечает цепь маркова, веса перехода из состояний в состояние у которой можно на ходу прокручивать, так что она «учится», а в немаркетинговых терминах — мы имеем последовательность распределение вероятности таких, что они в конце концов сходятся к правильному (но заранее не известному). Мне моя интуиция говорит, что такая модель более или менее эквивалентна ГП, но «честнее» ее, не приносит лишней мишуры и сразу обнажает объект, над которым работаем.
Те гаврики, о которых я писал чуть выше, придумали как работать не просто с последовательностями распределение вероятности, про которые ничего не известно, а обнаружили там богатую дифференциальную геометрию и сказали, как можно сходиться к правильному (но заранее неизвестному) распределению по кратчайшему пути в неком пространстве всяких распределений.
Ну, тут вопрос в определении того, что такое монте-карло. Если просто лепим много случайных нескоррелированных вариантов и проверяем какой лучше, то да, все как вы и говорите. Сам никуда не сходится, но по теореме Пуанкаре, рано или поздно пройдет рядом с нужной точкой.
Но так называемые Markov Chain Monte Carlo алгоритмы лепят случайные значения не с равной вероятностью. У них марковская цепь отвечает за выбор преимущественного направления так, чтоб процесс при этом оставался случайным. Ключевые слова — алгоритм метрополиса. Исходно оно было придумано в стат. физике — там все пространство состояний не обойдешь, но физический смысл несут только некоторые точки пространства состояний, причем заранее неясно, какие.
из вот этого комментария: "«сравним» для меня это разница в один порядок: 0.4 GFLOPS (multiclet, float32) vs 4 GFLOPS (i7, float64) — ну, по крайней мере есть что сравнивать, особенно учитывая разницу в частотах и несравнимый уровень вылизанности технологии у Intel."
Собственно, ради подобного сравнения, но с реальными чиселками, я исходный вопрос и задавал. Надежду, кроме разницы в частотах, питает то, что у мультиклета (точнее, качества вашего компиллятора) может оказаться лучшая шкалируемость на клетки по сравнению со шкалируемостью на различные x86 ядра. Тут для оценок вообще никаких данных не хватает: что с кэшем, насколько эффективно клетки обращаются к близко расположенным данным и так далее. Так что пока — гадание на кофейной гуще. Пока вы с коллегой тесты не прогоните ну или хотя бы детально модель внутренностей не расскажете, в терминах задержек каждой операции в числе тактов, длинне конвейеров и т.п.
снимаю шляпу перед мастером. И часто вам попадаются машины на VAX? Во время своего студенчества на кафедре теории функций стоял к тому времени уже устаревший сановский спарк, уже не помню какой номер. Все хотелось его попробовать, но не дали доступа. А сейчас его уже наверное и нет там.
Несколько десятков минут на современном железе? Это быстро :)
Как вы на старом железе решаете проблему тестов, кушающих память не в себя?
как раз поэтому я говорил «что вряд ли, но кто знает» :)
насчет памяти не совсем так. На небольших размерах матриц (например: 4х4) все укладывается в кэш и значит мы сравниваем чистую производительность i7 с его кэшем (а то и регистровым файлом) против мультиклета и его кэшем. Или что у него там — я не очень понял, есть ли кэш, как далеко расположена внешняя память (см. задержку) и какая разница в частотах между памятью и процессором.
В предыдущем каменте я скорее ставил задачу рассказать, что на разреженной (разреженно-блочной) алгебре и маленьких матрицах пиковая достижимая производительность в разы ниже таковой для плотной алгебры, по крайней мере для i7. Который не может взять и на ходу распараллелить вычисление. Ну и «сравним» для меня это разница в один порядок: 0.4 GFLOPS (multiclet, float32) vs 4 GFLOPS (i7, float64) — ну, по крайней мере есть что сравнивать, особенно учитывая разницу в частотах и несравнимый уровень вылизанности технологии у Intel.
В тему, недавно сидел на докладе, парень рассказывал о малоточных вычислениях на встроенных устройствах. Утверждение: считать с малой точностью возможно и очевидно быстрее/энергоэффективнее. Но что принципиально, точность (overflow/underflow) в итеративных алгоритмах типа Lanzcos можно контролировать с помощью очень несложного preconditioner'а. В качестве примера он там приводил эффективную производительность расчета, достигнутую на FPGA — она превышала теоретический предел Nvidia Fermi на порядок или два (правда как сравнивать попугаев разной точности тоже вопрос — число итераций ведь от точности небось зависит). Так что если вам актуально — вот.
Судя по беседе, вам приходится работать с большим зоопарком железа? Значит, скорее всего у вас не расчеты. Скажите хоть ваш класс задач.
Дык и крутизна ведь разная в разных задачах. Возьмете задачи, где данные лежат плотно и подряд (плотная линейная алгебра, dgemm-constraint), там нужно чтоб числомолотилка побыстрее. Возьмете задачи, где данные разреженные (разреженная алгебра, графы etc), там доступ к памяти и производительность подсистемы кэша становится важнее.
Вот например мой лаптоп на i7 выдает в максимуме на dgemm (OpenBLAS, одна нить) около 20 гигафлоп, но производительность аналога dgemv от Libsmm (выше упоминал) на маленьких матрицах от 2 до 6-7 гигафлоп в зависимости от размера. Отсюда, производительность разреженной алгебры этими 2-7 гигафлопами и ограничена. Мультиклет вон там в каких-то задачах в одинарной точности выдает чуть больше 2 гигафлопов. Получается, мультиклет сравним с i7? Если окажется, что разреженная алгебра на нем считается на полной скорости, то да, сравним (что вряд ли, но кто знает). А учитывая проблемы распараллеливания, OpenMP, false sharing etc на всех нынешних CPU, может быть и круче (что опять же вряд ли, но кто знает).
Так что линпак прекрасен, но только для плотной алгебры, а это очень узкая ниша. В Dhrystone не вглядывался, надо будет посмотреть что там.
Ну дык зависит от того, производительность чего вы хотите узнать. Какая у вас задача?
Возможно я не умею такие бенчмаркинги готовить (да и никогда не пытался, пока), но доверия им априори никакого. Вот скажет мне Linpack конкретную циферку в гигафлопсах — и как мне ее натягивать на мою задачу? Только если бенчмаркинг указывает на производительность того самого вычислительного фрагмента, на который моя задача села.
К тому же, железо без компиллятора вы все-равно ж не протестируете? Так что увы, в общем случае мой ответ — магия поиска оптимальных настроек у наилучших компилляторов для каждой платформы для конкретного микробенчмаркинга.
— конкретно в случае задачи регрессии есть более эффективные решения, и я уже встречался с крайне необдуманными применениями ГП как технологии (я не имею ввиду вас). Что, разумеется, говорит не столько о технологии, сколько о применяющих. С другой стороны, у каждой технологии, кроме собственно технологии, есть свой «маркетинг», и не всегда он приносит пользу тем, кто готов бездумно таковую технологию применить. Под маркетингом я имею ввиду вещи вроде «ТеХом пользоваться очень просто!», «ГП это универсальная технология». Это разумные утверждения, которые как правило не идут против истины, но в конечно счете могут приводить к не самому адекватному расположению рекламируего «товара» в системе представлений.
Может показаться, что я вцепился в ваш пример именно символьной регрессии и упускаю все прочие более удачные применения ГП как технологии. Да, наверное так. Но именно потому, что этот конкретный пример правда считаю крайне неудачным, по описанным выше причинам. Что, еще раз, не говорит, что мне не симпатичен ваш опыт в крайне разнообразных задачах. Мне было интересно посмотреть ваши демки и я вполне согласен, что в ситуации, когда модели нет, ГП поставляет неплохой инструмент для ее поиска.
— чтобы более осознанно выбирать технологию, следует знать об альтернативах и — тут ключевое — иметь возможность сравнивать эффективность этих технологий и отдельных их составляющих. Хотя бы как-нибудь, поэтому академически точными понятиями увы, не всегда можно оперировать. А раз так, я осознанно выбрал стиль беседы «научная курилка», где легко переходят от интуитивных ощущений к формальным определениям и обратно, но все понимают, что задача не теорему доказать, а понимания достичь.
— вы мне исходно показались ГП-евангелистом без кругозора. Тут я признаю свою ошибку. Поэтому я и не отвечал на ваши каменты. Все ваши ответа на мои вопросы о сравнительной эффективности отдельных составляющих ГП даны с точки зрения универсальности ГП и правильности ее применения так, словно альтернатив нет. К тому же, некоторые ваши ответы, на мой взгляд, не несут цели разобраться в содержании, а только добавить формализма. Например, на вопрос о гладкости пространства поиска в свете применения различных оптимизаций, которые фактически являются достаточно значимыми интервенциями в исходную модель, вы лишь отвечаете классификацией собственных оптимизаций. При всем уважении к проделанной вами работе, отвечает ли такая классификация задаче разобраться о гладкости пространства поиска? На мой взгляд нет, но добавляет формализма и наукообразия, и будь я неуверенный студент, меня бы ваш ответ отпугнул вообще любые вопросы задавать. Заметьте, это добавляет наукообразия там, где я как раз стараюсь его избежать. Таким образом, нового понимания ГП у меня в разговоре не возникло. А жаль, могло возникнуть, если б беседа обернулась ссылкой на исследования, где терминология ГП транслируется в модели, напрямую допускающие оценку качества сходимости.
Теперь, спасибо что поймали на терминологических неточностях. Разумеется, физический смысл у точек пространства никуда не исчезает. Имел ввиду следующее: когда нужно посчитать некоторую статсумму, значимый вклад может дать суммирование по достаточно малому подмножеству индексов, и вот каких — заранее может быть неясно. И уже из необходимости как-то выбрать подмножество суммирования вводят распределение вероятностей. Так точнее?
Ваше замечание о моих задачах странное, потому что я никаких своих задач не упоминал.
Те гаврики, о которых я писал чуть выше, придумали как работать не просто с последовательностями распределение вероятности, про которые ничего не известно, а обнаружили там богатую дифференциальную геометрию и сказали, как можно сходиться к правильному (но заранее неизвестному) распределению по кратчайшему пути в неком пространстве всяких распределений.
Но так называемые Markov Chain Monte Carlo алгоритмы лепят случайные значения не с равной вероятностью. У них марковская цепь отвечает за выбор преимущественного направления так, чтоб процесс при этом оставался случайным. Ключевые слова — алгоритм метрополиса. Исходно оно было придумано в стат. физике — там все пространство состояний не обойдешь, но физический смысл несут только некоторые точки пространства состояний, причем заранее неясно, какие.
Собственно, ради подобного сравнения, но с реальными чиселками, я исходный вопрос и задавал. Надежду, кроме разницы в частотах, питает то, что у мультиклета (точнее, качества вашего компиллятора) может оказаться лучшая шкалируемость на клетки по сравнению со шкалируемостью на различные x86 ядра. Тут для оценок вообще никаких данных не хватает: что с кэшем, насколько эффективно клетки обращаются к близко расположенным данным и так далее. Так что пока — гадание на кофейной гуще. Пока вы с коллегой тесты не прогоните ну или хотя бы детально модель внутренностей не расскажете, в терминах задержек каждой операции в числе тактов, длинне конвейеров и т.п.
Несколько десятков минут на современном железе? Это быстро :)
Как вы на старом железе решаете проблему тестов, кушающих память не в себя?
насчет памяти не совсем так. На небольших размерах матриц (например: 4х4) все укладывается в кэш и значит мы сравниваем чистую производительность i7 с его кэшем (а то и регистровым файлом) против мультиклета и его кэшем. Или что у него там — я не очень понял, есть ли кэш, как далеко расположена внешняя память (см. задержку) и какая разница в частотах между памятью и процессором.
В предыдущем каменте я скорее ставил задачу рассказать, что на разреженной (разреженно-блочной) алгебре и маленьких матрицах пиковая достижимая производительность в разы ниже таковой для плотной алгебры, по крайней мере для i7. Который не может взять и на ходу распараллелить вычисление. Ну и «сравним» для меня это разница в один порядок: 0.4 GFLOPS (multiclet, float32) vs 4 GFLOPS (i7, float64) — ну, по крайней мере есть что сравнивать, особенно учитывая разницу в частотах и несравнимый уровень вылизанности технологии у Intel.
В тему, недавно сидел на докладе, парень рассказывал о малоточных вычислениях на встроенных устройствах. Утверждение: считать с малой точностью возможно и очевидно быстрее/энергоэффективнее. Но что принципиально, точность (overflow/underflow) в итеративных алгоритмах типа Lanzcos можно контролировать с помощью очень несложного preconditioner'а. В качестве примера он там приводил эффективную производительность расчета, достигнутую на FPGA — она превышала теоретический предел Nvidia Fermi на порядок или два (правда как сравнивать попугаев разной точности тоже вопрос — число итераций ведь от точности небось зависит). Так что если вам актуально — вот.
Дык и крутизна ведь разная в разных задачах. Возьмете задачи, где данные лежат плотно и подряд (плотная линейная алгебра, dgemm-constraint), там нужно чтоб числомолотилка побыстрее. Возьмете задачи, где данные разреженные (разреженная алгебра, графы etc), там доступ к памяти и производительность подсистемы кэша становится важнее.
Вот например мой лаптоп на i7 выдает в максимуме на dgemm (OpenBLAS, одна нить) около 20 гигафлоп, но производительность аналога dgemv от Libsmm (выше упоминал) на маленьких матрицах от 2 до 6-7 гигафлоп в зависимости от размера. Отсюда, производительность разреженной алгебры этими 2-7 гигафлопами и ограничена. Мультиклет вон там в каких-то задачах в одинарной точности выдает чуть больше 2 гигафлопов. Получается, мультиклет сравним с i7? Если окажется, что разреженная алгебра на нем считается на полной скорости, то да, сравним (что вряд ли, но кто знает). А учитывая проблемы распараллеливания, OpenMP, false sharing etc на всех нынешних CPU, может быть и круче (что опять же вряд ли, но кто знает).
Так что линпак прекрасен, но только для плотной алгебры, а это очень узкая ниша. В Dhrystone не вглядывался, надо будет посмотреть что там.
Возможно я не умею такие бенчмаркинги готовить (да и никогда не пытался, пока), но доверия им априори никакого. Вот скажет мне Linpack конкретную циферку в гигафлопсах — и как мне ее натягивать на мою задачу? Только если бенчмаркинг указывает на производительность того самого вычислительного фрагмента, на который моя задача села.
К тому же, железо без компиллятора вы все-равно ж не протестируете? Так что увы, в общем случае мой ответ — магия поиска оптимальных настроек у наилучших компилляторов для каждой платформы для конкретного микробенчмаркинга.