Инструмент для числодробления

Здравствуйте, господин ставлю диагноз по комменту, элита науки, доктор всех знаний и властитель дум. Мне показалось что более вы уже не хотите общаться. Попробую резюмировать то что вы продемонстрировали. Поправте меня пожалуйста, если я ошибаюсь.

Вы, к моему огромному сожалению, типичный представитель того что когда то было наукой. Конечно в зеркале вам видится как минимум пророк рок-н-ролла в неритмичной стране. На деле вы ходите каждый день работать в обшарпанное здание в комнаты с облупившейся краской, которые некогда были лабораториями. Я прям вижу как вы оттопырив пальчик гнусавым голосом издеваетесь над студентами которые ничего не знают только потому что вы ничего им толком не смогли объяснить.

Поправте меня пожалуйста, если я ошибаюсь.

Вы ошибаетесь. Во всем, кроме облупившейся краски в комнате - до нас просто еще ремонт не дошел. Из Вас телепат такой же как чучоный...

На любом, что умеет MPI.

Как показывает опыт многие коллаборации начинались с разговоров за обедом, в баре или в курилке.

а теперь перечитайте моё исходное сообщение, там как раз говорилось о проблемах начать разговор за обедом и том какая это большая задница

обиженные снобы как AIv

простите, дорогой мой, но я AIv знаю лично, и Ваша оценка не соответствует действительности, это если мягко говорить

Батенька, ви таки бывали в Стенфорде или, прости-господи, в Оксфорде? Вот уж где хватает обшарпанных зданий с облупившейся краской! И ведь умудряются как-то заниматься чем-то отдаленно похожим на науку.

Спасибо на добром слове;-)

Я предупреждал насчет этого анонимуса... причем я это существо себе представляю. Год назад мы такое же чудо выгнали не допустив к защите бакалаврского диплома. В этом году он защищался на соседней специализации... у меня было ощущение, что я нахожусь на защите в урюпинском экономическом техникуме при интернате для альтернативно одаренных. Ему из жалости поставили трояк. Товарищ с таким же подвешенным языком, развитым самомнением, много и связно говорит... и так же бессмысленно.

а теперь перечитайте моё исходное сообщение, там как раз говорилось о проблемах начать разговор за обедом и том какая это большая задница

Читаю:

именно что, причём в настоящее время маразм дошёл до того, что учёные практически перестали обмениваться результатами и опытом, ни с кем ничего обсудить нельзя - иначе он завтра уже статью тиснет или грант получит, вежливо под твои результаты/работу

Это не правда. Люди организуют конференции что бы пообщаться. Тут написано что все украдут. Это кто такое сказал? Знакомый Иванов?

Причем тут проблема поговорить? Я вот по секрету скажу, что коллаборация это не ругательство какое то. Это просто люди что то вместе делают.

Ну даже ежели кто и грант получит, а ты не смог получить. И что это значит? Только то, что кто то смог его получить, а ты нет. Может дело не в том что все такие гады, а в тебе, что ты не смог?

Ваша оценка не соответствует действительности

Мы уже на вы?

Батенька, ви таки бывали в Стенфорде или, прости-господи, в Оксфорде?

Таки да. В Вайцмане покошерней будет?

подвешенным языком, развитым самомнением, много и связно говорит

Огромное спасибо за комплимент!

у меня было ощущение, что я нахожусь на защите в урюпинском экономическом техникуме при интернате для альтернативно одаренных

Вы там тоже преподавали? Вы так прекрасно знакомы с темой, что невольно возникает вопрос: а что вы там не остались?

ни с кем ничего обсудить нельзя - иначе он завтра уже статью тиснет или грант получит, вежливо под твои результаты/работу

Это не правда.

это не просто правда, это я из первых уст Вам докладываю

конечно Ваше право не верить мне, но для меня (и это моё право) это просто свидетельство того, что, простите, Вы либо не представляете себе положение дел (о чём изначально шла речь), либо не имеете никакого отношения к науке

это не просто правда, это я из первых уст Вам докладываю

Это довольно странно. А чем мотивировали отказ? Может этот аспирант какое то соглашение о не распространении подписал. Или просто личная неприязнь к терминаторам.

Вообще говоря всегда есть какое то количество неадекватных людей. Обычно, так поступают те которые просто не понимают или не знают чего то. Потому и темнят. Самое простое — обратится напрямую к профессору. У них, у профессоров, работа такая объяснять людям просто о сложных вещах.

Вчера, после ~10летнего перерыва зарегистрировался на суперкомпе.

Fortran, 3 вида C/C++, cuda, openCL
Из параллельных технологий: mpi, openMP, shmem

типа все.

даже swig-а нет :(

На английском нет ни одной?

У меня первая публикация по этой теме (от 1998г) была как раз таки на английском.

вы думаете что надо всем русский учить дабы узнать о вашем методе?

Считайте это бонусом русскоговорящих. ;)
Но он скоро закончится.

Впрочем, если с русским у Вас туго, читайте о слабом подобии LRnLA ;) на языке Шекспира:
http://en.wikipedia.org/wiki/Cache-oblivious_algorithm
Там далее по ссылкам много статей обнаружится...

Это довольно странно. А чем мотивировали отказ?

да ничем

Самое простое — обратится напрямую к профессору.

это снова нарушение горизонтального взаимодействия

и что будет когда через 10-15 лет нынешние аспиранты станут профессорами?

читал коммент, и никак не думал, что это ты:-)
двачую.

http://en.wikipedia.org/wiki/Cache-oblivious_algorithm
Там далее по ссылкам много статей обнаружится...

Спасибо. Так намного понятней. Я пытался разобраться по тому что привел AIv и мало что понял из того описания. Правильно ли я понимаю что в вашем методе используется рекурсивный обход для интегрирования подобно тому как скажем в quicksort? В профите имеете сильно меньший оверхед на ввод/вывод из памяти или даже с диска, из-за того что данные для собственно операций сложил-умножил-подитожил хранятся в кеше.

Думали ли вы про LRnLA на GPU для вычислений или смысла особого нет из-за дополнительного копирования?

это снова нарушение горизонтального взаимодействия

Ну если доцент не хочет взаимодействовать, что ж тут поделаешь.

и что будет когда через 10-15 лет нынешние аспиранты станут профессорами?

вырастет, повзрослеет и поумнеет, ну или не станет профессором :)

Правильно ли я понимаю...

Судя по написанному далее --- Вы не понять пытаетесь, а найти известные Вам аналогии в своей голове. Боюсь, там ничего похожего на LRnLA пока что нет.

используется рекурсивный обход

используется, но не произвольный рекурсивный, а вполне конкретный. Собственно, именно этот «обход» и является «LRnLA алгоритмом».

для интегрирования

этот термин вообще не из этой области. Если конечно под «интегрированием» не понимать любое решение задачи.

подобно тому как скажем в quicksort

нет. Общего с quicksort, как и с массой других алгоритмов --- лишь общий подход «divide-and-conquer»

В профите имеете сильно меньший оверхед

во многих актуальных ситуациях --- этот «оверхед» удается свести к нулю.

ввод/вывод из памяти

термин «ввод/вывод» относительно «памяти» (если это RAM) не используется. Используется «обмен с», «доступ к», «чтение из» «запись в».
Это я к тому, что причины возникновения и составляющие этих самых «оверхедов» могут быть очень разные. В частности, потому сама по себе дебютная идея «cache-oblivious» алгоритмов изначально ограничена лишь памятью.

ввод/вывод ... с диска

тут --- да.

данные для собственно операций сложил-умножил-подитожил хранятся в кеше

это верно практически для любых алгоритмов, выполняющихся практически на любых процессорах, начиная со времён i486.

Думали ли вы про LRnLA на GPU для вычислений

И думал, и двум студентам уже давал такую задачу на диплом.
Сейчас занимаюсь этим плотно.

смысла особого нет из-за дополнительного копирования?

какого именно копирования?

даже swig-а нет :(

При наличии python-devel он в общем и не нужен (либо все что нужно ставится локально).

Судя по написанному далее --- Вы не понять пытаетесь, а найти известные Вам аналогии в своей голове.

Я и не пытаюсь понять LRnLA. Мне интересно то как вы получили десяти-сто кратный прирост производительности. Вы ответили cache-oblivious, за что вам огромное спасибо.

Боюсь, там ничего похожего на LRnLA пока что нет.

И вряд ли будет. Численным моделированием я не занимаюсь.

во многих актуальных ситуациях --- этот «оверхед» удается свести к нулю.

Вот это совсем круто.

Я и не пытаюсь понять LRnLA. Мне интересно то как вы получили десяти-сто кратный прирост производительности.

взаимоисключающие параграфы :) жги ещё

взаимоисключающие параграфы :) жги ещё

LRnLA это cache-oblivious алгоритм, это не значит что он единственный.

Мне интересно то как вы (!!!) получили [..] прирост производительности

для тебя твою же мысль подчеркнул и выделил, теперь отвечаю на вопрос (хоть и не мне адресованный) - с использованием LRnLA, хочешь понять как, разбираться надо именно с ним

теперь далее:

LRnLA это cache-oblivious алгоритм

автор LRnLA говорит о cache-oblivious как о «слабом подобии LRnLA», рекомендую учитывать этот факт в своих дальнейших рассуждениях

Мне интересно то как вы получили десяти-сто кратный прирост производительности.

Предположу, что прирост должен получаться за счёт уменьшения числа пересылок и увеличения независимости узлов (почти снимается необходимость их синхронизации). При этом рассматривать алгоритм нужно именно с точки зрения физика, а не программиста, поскольку в его основе лежит физический принцип причинности. Пусть меня поправят, если что.

Это один из взглядов, причем несколько устаревший. VLev ушел по пути просветления гораздо дальше, и пытается объясняться на языке теории алгоритмов - если раньше понимали не все, то теперь не понимает никто;-)

Вы не в Москве случайно? А то бы приходили к нам на семинар или просто чайку попить... надо бы как то выкристаллизовать наиболее прозрачное объяснение этого ужаса, но нужны люди со стороны с еще не замутненным сознанием и не вывихнутым мосгом;-)

Вы не в Москве случайно?

Нет, увы, в далёком замкадье.

Ай-яй... хорошо Вам там надеюсь;-)

Ну тогда пишите как чего c хацкелем родится aivanov(собака)keldysh(точка)ru

Я правда уеду до августа в дикие края.

Мне интересно то как вы получили десяти-сто кратный прирост производительности.

Тут куда интереснее как остальные не замечают как получают «десяти-сто», а то и тысячекратное замедление ;)

А я, что?
Когда начинал работать, 20 лет назад, у меня был компьютер на i386 с производительностью 1MFlops.
Теперь в корпусе от того самого i386 стоит компьютер с производительностью 1TFlops, что в миллион раз быстрее.
Ну вот я сейчас и решаю задачи в миллион раз более сложные, чем 20 лет назад.
Что в этом странного?

Вот это совсем круто.

Почему круто, сможете предметно ответить? ;)

LRnLA это cache-oblivious алгоритм, это не значит что он единственный.

Не совсем так.
LRnLA --- это довольно большое семейство алгоритмов.
Мне даже пришлось специальную классификацию вводить, чтобы самому в них не путаться. :)
Свойство «cache-oblivious» есть у части из них, собственно, в дебютной идее, за «cache-oblivious» отвечают первые две буквы из LRnLA.

Ок.

При этом рассматривать алгоритм нужно именно с точки зрения физика, а не программиста, поскольку в его основе лежит физический принцип причинности.

Полный аналог «принципа причинности» лежит и в основе информатики.
Так что и с точки зрения программиста вполне можно рассматривать.
Тут скорее технические трудности есть --- в императивном программировании стандартными являются неподходящие структуры данных, а в функциональном программировании нет оптимизирующих компиляторов.

Тут скорее технические трудности есть --- в императивном программировании стандартными являются неподходящие структуры данных, а в функциональном программировании нет оптимизирующих компиляторов.

это трудность? хм... такую трудность порешать не то чтобы сильно трудно

Да локально-то (в своей группе) мы эту трудность как раз решаем. Технически --- при помощи той же кодогенерации. Ментально --- при помощи пары-другой курсов лекций и семинара. Студенты за год-другой все это осваивают.
Но в масштабе индустрии, даже не программирования в целом, а относительно узкой области высокопроизводительных вычислений, где все друг друга знают --- это реальная трудность. :(

Но в масштабе индустрии, даже не программирования в целом, а относительно узкой области высокопроизводительных вычислений, где все друг друга знают --- это реальная трудность. :(

ну а что останавливает от создания соответствующего ЯП? может вот как раз бы и получился хороший материал для демонстрации концепции

Лично я уже вышел из того возраста, когда пишут свои ЯП;-)

ну а что останавливает...

Если бы мои ресурсы были безграничны --- я бы ещё заставил производителей актуальных процессоров пару нужных мне инструкций аппаратно реализовать ;)

... от создания соответствующего ЯП?

языков программирования и так слишком много.
А история строительства Вавилонской башни как бы намекает...

Если же говорить серьёзно, то все, что нужно для LRnLA --- есть в уже существующих ЯП. Мы используем связку python/C++ (где C++ основной), но это не обязательно. Можно ведущим сделать и какой-нибудь функциональный язык, вероятно.

Проблема, к сожалению, несколько глубже. Например, всем давно очевидны проблемы производительности, связанные с многомерными массивами, начиная с матриц. Как и многие другие в нашей жизни --- они решаются при помощи костылей, не трогая главного принципа --- хранения данных по строкам (в Fortranе по столбцам), который и является первопричиной этих проблем.

В то время как тайлы, числа мортона и проч., решающие проблему коренным образом --- придуманы давным-давно.

языков программирования и так слишком много.

это не показатель, и тут даже дело не в том что «мы напишем наш супер-язык» и все его полюбят и будут счастливы, а в том что написание такого языка есть в своём роде форма исследовательской работы

это своего рода генетический алгоритм - размножаем, смотрим что получилось, берём лучшее и снова размножаем :)

А история строительства Вавилонской башни как бы намекает...

слышал там в процессе строительства вроде бы изобрели пару языков :)

Если бы мои ресурсы были безграничны --- я бы ещё заставил производителей актуальных процессоров пару нужных мне инструкций аппаратно реализовать ;)

про производителей актуальных процессоров можно забыть в этом разрезе, у них бизнес-план, норма прибыли, патенты и просто бюрократия, да и процессоры общего назначения скорее движутся к risc схемам

так что уж коли делать, так специализированный вычислитель какой-нибудь

пора уже отчественную науку двигать (не всё ж из видеокарточек одной известной фирмы кластера мастерить :))

Лично я уже вышел из того возраста, когда пишут свои ЯП;-)

научной работе все возрасты покорны :)

написание такого языка есть в своём роде форма исследовательской работы

да, конечно. Кстати, я беседовал на эту тему с людьми, занимающимися подобным в нашем институте. Но дальше приглашения меня на их семинар (так пока и не состоявшийся к тому же) дело не пошло.

можно забыть в этом разрезе

Я бы не был столь категоричен. ;)
Вот, скажем, Intel-овский MIC - вполне себе исследовательский процессор. И у меня есть вариант LRnLA алгоритма, который должен позволить достичь на нем пика в целевых задачах.
Ну а в GPGPU --- там сам Бог велел эти инструкции завести. Я вообще удивляюсь как они без этого обходятся (впрочем, может, просто не нашёл их пока).

процессоры общего назначения скорее движутся к risc схемам

Не, это был тренд 1990-х годов. Сейчас обратный откат.
Последний широкоизвестный пример --- реализация аппаратной поддержки AES intel-ом.

пора уже отчественную науку двигать

Опять же, говорил с членом команды разработчиков Эльбруса.
«бизнес-план, норма прибыли, патенты и просто бюрократия» --- несравнимо больше, чем у того же Intel-а.

научной работе все возрасты покорны :)

Если говорить про удовлетворение собственного любопытства - то я свои ЯП уже писал, мне хватило. Если с прагматической точки зрения - то ИМНО более перспективно написание библиотеки на каком нить подходящем популярном ЯП. Мы вот для питона пилим некое подобие CAS, заточенное под кодогенерацию, в т.ч. с LRnLA алгоритмами. Дьявол, как обычно, прячется в деталях...

LRnLA --- это довольно большое семейство алгоритмов.

То есть область применения не ограничена решением дифуров сеточным методом? У Прокопа есть пример с фильтром Якоби (шестой раздел по ссылке ниже). Так же есть статьи о cache-oblivious структурах данных, например бинарное дерево. Или FFT и собственно библиотека FFTW от тех же ребят.

Свойство «cache-oblivious» есть у части из них, собственно, в дебютной идее, за «cache-oblivious» отвечают первые две буквы из LRnLA.

Дебютная идея это оно http://supertech.csail.mit.edu/papers/Prokop99.pdf ?

Если судить по названию LRnLA это суть параллельный cache-oblivious. В вашем методе рекурсивный обход строится таким образом, что можно избежать локальных конфликтов и тем самым эффективно распаралелить вычесления. Правильно, или я опять глупость написал?

То есть ...

Я не область применения имел в виду, когда писал «LRnLA --- это довольно большое семейство алгоритмов»
а именно существенно отличающиеся «правила обхода».
Часто одно и то же «правило обхода» (то есть один и тот же алгоритм) можно применить к задачам из совершенно разных предметных областей. В терминологии LRnLA об этом говорится как о разном замыкании алгоритма.
Скажем, для «фильтра Якоби» из примера Прокопа можно использовать ровно тот же алгоритм, что и для явной одномерной трехточечной разностной схемы с простыми граничными условиями.
Собственно, если Вы сравните мои картинки для случая 1D с картинками Прокопа --- найдете много общего.

И наоборот, для решения задач из одной и той же предметной области методами LRnLA часто используются разные правила обхода, то есть разные алгоритмы, в зависимости от того компьютера, на котором она решается, численных параметров и проч. Более того, для достижения лучшего результата, при решении даже одной задачи используются несколько LRnLA алгоритмов на разных уровнях рекурсии (обычно 2-4 разных алгоритмов).

решением дифуров сеточным методом

«сеточные методы» здесь не очень при чем. Скажем, PIC, с которого у меня все начиналось --- не совсем сеточный.
Традиционная область приложения LRnLA --- «явные (с локальным шаблоном) методы эволюционного моделирования».
«фильтр Якоби» под это определение вполне подходит.

Или FFT

У FFT --- не только другие информационные зависимости, чем в явных эволюционных методах, но даже и ассимптотическая сложность другая. Потому про него я ничего путного сказать не могу (пока по крайней мере).
Зато кое-что могу сказать про умножение матриц ;)

Дебютная идея это оно

«Дебютная идея» --- это модель вычислений.
У Прокопа эта самая модель на fig 1-1 показана.
В LRnLA модель вычислений другая, больше похожая на верхнюю часть Fig.1 из ссылки http://www.compgeom.com/co-chap/chap.pdf .

Если судить по названию LRnLA это суть параллельный cache-oblivious

Если судить по названию, то «cache-oblivious» --- это алгоритмы, нечувствительные к организации кэширования. То есть название говорит о результате, ничего не говоря о процессе.
Название LRnLA построено наоборот, исходя из процесса:
то, что локально --- организовано рекурсивно, а то, что нелокально --- асинхронно.
Потому, чтобы свойство нечувствительности к организации кэширования оказалось задействованным --- надо как минимум привлечь еще тезис о том, что все, что локально --- нечувствительно к организации кэширования.

о cache-oblivious структурах данных

В принципе, этот вопрос уже начал обсуждаться чуть выше. Так что я лучше для конкретности приведу (с непринципиальными изъятиями) те базовые структуры, которые мы используем в C++ вместо многомерных массивов.

Локально-рекурсивный куб:

template <int dim, class T, int rank> struct cubeLR {
  cubeLR<dim, T, rank-1> datas[1<<dim];
  T& operator[](size_t i) { return ((T*)datas)[i]; }
};
template <int dim, class T> struct cubeLR<dim, T, 1> {
  T datas[1<<dim];
  T& operator[](size_t i) { return datas[i]; }
};

template <int dim> struct brick_header {
  int netID;
  virtual size_t get_size()=0;
  void operator delete(void* p);
  virtual void init(BrickPos<dim>& pos) = 0;
  virtual void drop(BrickPos<dim>& pos) = 0;
};
template <int dim> struct nLAnet {
  brick_header<dim>* datas[1<<dim];
  int ID, iStep;
  char linkType[dim+1];
  nLAnet<dim>* net[dim+1][2];
  virtual bool check4grow();
  virtual void finish_grow() { iStep++; }
};

Fortan + C

Спасибо. Узнал много нового.

К сожалению для решения моих задач LRnLA ничем помочь не может, хотя могу и ошибаться. К примеру, максимизация правдоподобия частично с использованием expectation maximization (EM) для гистограм. Самое умное что пришло в голову это просто перенести вычисление L и/или Q на GPU с минимизацией на CPU. Прирост получился довольно существенным когда фитируется тысячи-десятки тысяч моделей параллельно.

По поводу нулевого оверхеда на чтение данных. Нужно подумать. Пока у меня довольно грустно с оптимизацией доступа к памяти из-за построения гистограм, и еще смотреть надо что бы в память влезло. В последнее время появились работы где люди пытаются делать EM на списках событий вместо гистограм (в томосинтезе PET, SPECT). Но тогда нужно эти события както сортировать, поскольку у меня модель, функция плотности распределения, эффективно считается итерационно.

К примеру, максимизация правдоподобия частично с использованием expectation maximization (EM) для гистограм

При подобном анализе я обычно иду от задачи, а не от метода её решения. Насколько я понял, это что-то вроде томографии (т.е. восстановление структуры объекта по его изображениям)?

довольно грустно с оптимизацией доступа к памяти из-за построения гистограм, и еще смотреть надо что бы в память влезло

независимо от LRnLA тут ключевым является вопрос параметров --- сколько «событий», какова размерность пространства, в котором они происходят и соответственно --- число интервалов на гистограммах, и их размерность.

Но тогда нужно эти события както сортировать

дык те самые бинарные деревья.

Насколько я понял, это что-то вроде томографии (т.е. восстановление структуры объекта по его изображениям)?

Не совсем так. Это деконволюшн, где меряется сигнал и функция отклика прибора. В качестве модели в общем случае используют сумму экспонент свернутую с функцией отклика. Потом надо подобрать параметры модели которые минимизируют разницу с измеряным сигналом. В самом простом случае описано сдесь: https://juwel.fz-juelich.de:8443/dspace/bitstream/2128/674/1/4434.pdf

Там используется одна экспонента и самый простой способ вычисления свертки. То что надо найти показано сплошной линией между точками (рис 2), функция отклика показана пунктиром. Собственно в этой модели 2 параметра \tau и \gamma (формула 9). Минимизируется 2I* (формула 8).

тут ключевым является вопрос параметров --- сколько «событий», какова размерность пространства, в котором они происходят и соответственно --- число интервалов на гистограммах, и их размерность.

События сдесь это время регистрации фотона. Изменяется в дискретных каналах, которых обычно 2^10 — 2^12. Редко больше 12 бит или 4096 каналов. Количество фотонов от сотен до десятков тысяч. В самом простом случае нужна одна одномерная гистограма. Зачастую на практике используют больше, например спектрально разделенные или 2 поляризации. Тогда гистограм 2 и более. Зависит от задачи.

Это деконволюшн

вроде, ещё Винер этой задачей занимался...

подобрать параметры модели

То есть эти «параметры модели» и являются основным результатом обработки исходного сигнала?
И еще: Отдельные сигналы обрабатываются независимо?

Редко больше 12 бит или 4096 каналов. Количество фотонов от сотен до десятков тысяч...гистограм 2 и более.

Вообще, судя по этим параметрам --- и без всяких «cache-oblivious» ухищрений --- все должно локализоваться в кэше, причём L1, само собой.
Так что если ощущается неэфективность вычислений --- возможно, дело не в доступе в память, а, скажем --- в вычислении экспонент.

Кстати, откуда берется «и еще смотреть надо что бы в память влезло»?