Intel® Software Network

Приветствую, Юрий!

За этими праздниками я чуть не "проморгал" ваш пост. Очень интересные работы у вас на сайте! Данные по SDIAG vs. DSPTRD впечатляют. Насколько я понял, вы уже контактировали с кем-то из Интел? На всякий случай, я послал ссылки на этот пост и на ваш сайт ребятам из MKL, посмотрим что они скажут. От себя добавлю что последний официальный релиз MKL на данный момент (насколько я знаю) 10.0.020. Любопытно было бы посмотреть, насколько ситуация изменилась.

Юрий, ваши алгоритмы - предмет IP? Вы участник программы ISPP? А еще я не понял (вероятно, просмотрел) - есть ли на сайте детальное описание алгоритмов? В любом случае, если у вас будет желание/возможность рассказать подробнее о предложенных решениях - мы готовы сотрудничать.

Удачи, и ждем комментариев от наших инженеров.

Здравствуйте, Дмитрий.

.

Несколько лет назад переписывался с Intel, но к общему знаменателю мы не пришли. После этого в 2006 году был открыт новый (более быстрый) алгоритм перехода от собственных векторов трехдиагональной матрицы к собственным векторам исходной матрицы, а в 2007 году разработан алгорим быстрого умножения м-ц, который не требует выделения дополнительной памяти (алгорим Штрассена и его модификации очень "прожорливы"). Моя страница несколько устарела (в том смысле, что результаты для IA32 сейчас у меня значительно лучше как для диагонализации, так и для перемножения м-ц). В феврале этого года Intel MKL значительно улучшила результаты для dgemm IA32. А история вопроса такова. Мало кто верил моим россказням про то, что dgemm Intel MKL не эффективна. Одним из немногих, кто мне поверил, был проф. Грановский (создатель известной квантовохимической программы PC GAMESS), который в конце прошлого года разработал алгорим умножения матриц для IA32 значительно быстрей dgemm Intel MKL. Он был подарен им Intel'у, которая, как показывет сравнительный анализ результатов и кода, и воспользовалась алгоритмом Грановского. Следует отметить, что он годится только для Core 2 Duo и не вписывается в концепцию блочной обработки пакета LAPACK (да еще и медленней моего алгоритма). Мой алгоритм перемножения матриц однотипен для всех прцессоров. Для 45 нм. процессора q9450 скорость перемножения матриц на одном ядре достигает 96.2%  для IA32 и 97.7% для EM64T от теоретически возможной. Что касается доступности моих алгоритмов, то мои материальные возможности не позволяют мне передать разработки бесплатно. Я хотел бы их передать на коммерческой основе.

.

Юрий Сиголаев.

YuriiSig:

Мой алгоритм перемножения матриц однотипен для всех прцессоров (с поправкой на кэш). Для 45 нм. процессоров скорость перемножения матриц на одном ядре для IA32 достигает 94% от теоретически возможной. Что касается доступности моих алгоритмов, то мои материальные возможности не позволяют мне передать разработки бесплатно. Я хотел бы их передать на коммерческой основе.

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

Предлагаю начать с объективных тестов. Я связался с разработчиками MKL (они, кстати, вас помнят). Их пожелание - каким-то образом провести сравнение результатов последней версии MKL и вашего алгоритма. Это возможно? Я почитал у вас на сайте, вы описываете методику сравнения. Вы можете предоставить исполняемый файл для сравнения на нашей стороне? Если разработчики подтвердят ваши данные - я буду думать, что мы можем сделать дальше.

Удачи!

Небольшая поправка - для сравнительных тестов, было бы здорово получить вашу библиотеку. Это позволит провести детальное сравнение в "равных" условиях (один компилятор, одинаковые ключи компиляции и т.п.).
Это возможно?

MAD\doganezo:

Небольшая поправка - для сравнительных тестов, было бы здорово получить вашу библиотеку. Это позволит провести детальное сравнение в "равных" условиях (один компилятор, одинаковые ключи компиляции и т.п.).
Это возможно?

Дмитрий,

мои разногласия с Intel в свое время возникли как раз по этому поводу. Я, например, без труда просматриваю код библиотек Intel MKL. И мой код, также без труда может быть раскрыт. Я не боялся раскрытия кода (Intel наверняка реализуеет мои идеи лучше, чем я), но не хотел раскрытия моих алгоритмов. Мы договорились в свое время, что тестирование будет проводиться на моем компе, но после тестирования они дали задний ход  (сославшись на то, что у них нет моих библиотек???). Возможно, есть еще какой-то выход.

Юрий

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

 

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

 

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

 

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

 

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

MAD\doganezo:

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

Т.к. все практически реализовано на ассемблере, то все тесты можно провести на моем компе (т.к. настройки транслятора на быстродействии не сказываются, а все остальное можно проверить на моем компе). Благо, в Питере есть представители Intel и если их устроят результаты тестов, то они смогут их повторить прямо на моем компе (процессор q9450) сами.

MAD\doganezo:

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

В свое время я и договаривался с Intel о передаче  алгоритмов. Все идеи уместятся на одной страничке. С патентами я связывться не буду: у нас это сплошной обман, а у них это дорого стоит и мне не по карману. Поэтому я и не хочу предоставлять свои библиотеки, т.к. алгоритмы могут быть раскрыты.

YuriiSig:

... Иное дело - грамотный алгоритм перемножения м-ц : здесь можно добиться прекрасного распараллеливания (см. мою страницу http://www.thesa-store.com/products/ , где описаны новые алгоритмы диагонализации матриц и их перемножения (например, разработан новый алгоритм быстрого перемножения м-ц, который не требует выделения дополнительной оперативной памяти) ...

Доработан алгоритм быстрого умножения м-ц, описанный на странице, посвященной Core 2 Duo для IA32. Он требует относительно небольшого объема дополнительной оперативной памяти и позволяет перемножать м-цы вплоть до размера 11500*11500 при 4 GB оперативной памяти. Для процессора q9450 на одном ядре под EM64T получены следующие интересные результаты:  для м-ц 480*480 скорость равна 4.21 ops/cycle (dgemm Interl MKL - 3.70 ops/cycle), для м-ц 960*960 скорость равна 4.25 ops/cycle (dgemm Interl MKL - 3.75 ops/cycle), а для м-ц 11264*11264 скорость равна 5.98 ops/cycle (dgemm Interl MKL - 3.80 ops/cycle). Особенно хочется отметить результаты для малых матриц - даже близких к ним результатов я еще не встречал и в помине, а м-цы такого размера важны в некоторых приложениях. Дело в том, что когда я занялся небольшими матрицами, я сразу понял, где находится узкое место. Поэтому мне и удалось продвинуться. Алгоритм получился весьма сложным (ведь кроме значительного увеличения скорости был минимизирован и объем используемой дополнительной памяти, что позволяет перемножать м-цы очень большого порядка, т.е. я убил сразу двух зайцев !) и я им горжусь.Но общий недостаток всех алгоритмов быстрого умножения (и в этом смысле мой алгоритм не является исключением, хотя по остальным показателям превосходит все остальные) - это их худшее распараллеливание по сравнению с каноническим dgemm в моделях с общей памятью из-за наличия большого числа квадратичных операций, что неминуемо влечет интенсивное использование оперативной памяти. Впрочем я не расспараллеливал алгоритм, а получил оценку сверху, пропустив один экземпляр программы одновременно на 4-х ядрах (например, для м-ц 480*480 я получил 3.65 ops/cycle), что является очень грубой оценкой для неканонических dgemm, т.к. на время расчета велико влияние квадратичных операций. При распараллеливании моего алгоритма результаты должны быть значительно лучше. Появится свободное время - займусь распараллеливанием.

YuriiSig:

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

Я бы так однозначно не утверждал. Тут есть несколько моментов.

Во-первых, будущее много-ядерных систем достаточно однозначно видится в области ссNUMA систем, в основном как раз из-за таких алгоритмов, которые упираются в пропускную способность памяти. А на NUMA системе производительность алгоритма, упирающегося в пропускную способность памяти, всё ещё может расти линейно при распараллеливании. У AMD 2-ух процессорные системы уже NUMA. У Intel это предвидится в ближайшем будущем, с выходом QuickPath Interconnect.

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

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

randomizer:

YuriiSig:

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

Я бы так однозначно не утверждал. Тут есть несколько моментов.

Во-первых, будущее много-ядерных систем достаточно однозначно видится в области ссNUMA систем, в основном как раз из-за таких алгоритмов, которые упираются в пропускную способность памяти. А на NUMA системе производительность алгоритма, упирающегося в пропускную способность памяти, всё ещё может расти линейно при распараллеливании. У AMD 2-ух процессорные системы уже NUMA. У Intel это предвидится в ближайшем будущем, с выходом QuickPath Interconnect.

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

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

По поводу "во-первых и в-третьих" - я имел в виду настоящее, а не будущее. По поводу "во-вторых": могу лишь сказать,что мой подход (при неизменной частоте памяти) позволил увеличить скорость алгоритма, отвечающего за Blas Level 2 при трехдиагонализации матриц на 35% по сравнению с аналогичным алгоритмом в Intel MKL, но этот разрыв в скоростях не связан с многоядерностью. Ребята из Intel MKL знают об этом уже более 3-х лет.

YuriiSig:

По поводу "во-первых и в-третьих" - я имел в виду настоящее, а не будущее. По поводу "во-вторых": могу лишь сказать,что мой подход (при неизменной частоте памяти) позволил увеличить скорость алгоритма, отвечающего за Blas Level 2 при трехдиагонализации матриц на 35% по сравнению с аналогичным алгоритмом в Intel MKL, но этот разрыв в скоростях не связан с многоядерностью. Ребята из Intel MKL знают об этом уже более 3-х лет.

Первый пункт про NUMA - это не будущее, это настоящее. 2/4-процессорные системы от AMD - NUMA. Последние 2/4-процессорные системы от Intel, те которые содержат QPI вместо разделяемой шины - тоже NUMA. Многопроцессорные сервера от IBM на основе процессоров Intel Xeon - очень сильно NUMA, например некоторые конфигурации выглядят так: 8 NUMA узлов, на каждом узле по 8 Гб "приватной" памяти, 4 процессора на узле.
Упускать эти тенденуции из вида нельзя. Уже сегодня приложение может терять часть пропускной способности с памятью, если не учитывает NUMA А в завтра эти тенденции будут только усиливаться.

По поводу третьего пункта - да, пока это не сегодняшний день. Однако время идёт очень быстро...

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

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

 То, о чем Вы пишете, уже не является моделью с общей памятью в чистом виде. Думаю, что здесь необходимо уже другое название. В любом случае на первом месте остается грамотный алгоритимический подход к реализации алгоритмов. Например, для некоторых важных случаев перемножения неквадратных матриц, мой алгоритм более чем на порядок превосходит скорость алгоритма dgemm Intel MKL. Что касается AMD, то у меня к этой фирме стойкий иммунитет, основанный на личной практике. Пользуюсь только интеловскими процессорами.

Здравствуйте,
Продвинулась ли как-нибудь ситуация с ознакомлением Интела с вашими алгоритмами?
А то скорость в 32-битных системах по прежнему очень низка - например на Pentium E2140 интеловский Linpack 10.2 достигает лишь 40% от теоретического максимума (в 64-битах ситуация заметно лучше).
А ведь Linpack в основном зависит от dgemm.

Уважаемый maa1, дело в том, что не ребята из Интела разрабатывают алгоритмы - они их только реализуют (конечно, очень грамотно - они дураков не держат. Например, алгоритм перемножения м-ц (вернее, его ядро) реализован на ассемблере и содержит не одну тысячу строк кода). А так как они в этом практически не кумекают, то с ними разговор об этом, что глухого с немым. Те, кому они подчиняются, слабо в этом разбираются - вот они им лапшу на уши и вешают (ведь основная продукция Intel'а - это железо). А в нашей стране это никому не нужно (правда, встречаются исключения типа профессора Грановского). Я в свое время с ними переписывался и они присылали мне тестовые задачи: по их характеру я сразу понял, что они пытаются понять смысл моих алгоритмов. Но кое-что понял только проф. Грановский, который разработал алгоритм перемножения матриц для x86 под 65 нм. проц. Core (Intel его алгоритм и использует) и который стал не актуален для 45 нм. процессоров из-за другой реализации одной из команд. А ведь мои разработки не ограничиваются только алгоритмом перемножения матриц.

Интересная ситуация! и очень знакомая - я сейчас как раз готовлю статью об одном своем алгоритме, над которым работаю с 2003 г. Причем с 2006 г. мне за эту работу никто не платит - независимое исследование, так сказать ;)

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

1) Патентовать алгорим - все равно что патентовать такие вещи, как колесо. Не хочу тормозить прогресс ;)
2) Это не имеет смысла - всегда можно придумать косметические исправления - и будет новый алгоритм.
3) Алгоритм должен быть опубликован, доказан, обсужден в широких кругах и признан ими - только тогда он может стать популярным, ограничение на использование (вроде патента) отпугнет широкие круги, и алгоритм, даже если он потенциально и очень хороший, будут просто игнорировать.

Что же делать? Думаю, прежде всего не надо валить все в одну кучу: естественное желание получить достойную компенсацию за свой труд и естественное опасение, что Вас могут обокрасть.

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

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

И пользуясь случаем, еще раз повторю вопрос, который уже задавал ранее: чем Интел хуже Дж.Сороса? Почему бы не поддерживать грантами исследования и разработки сторонних исследователей, в которых Интел заинтересован? Какие-то гранты Интел дает, но механизм получения такого гранта настолько засекречен, что сами сотрудники, которых я спрашивал, не знают, как это делается и к кому обращаться ;)

Почему никому не показывая? Во-первых, Intel присылал мне тесты и по их результатам можно было делать определенные выводы. Во-вторых я брался за эту работу не ради Intel'а, а для решения определенных задач с последующими публикациями. Задним числом я узнал о пакете Intel MKL и увидел, что их разработки (вернее алгоритмы, которые они реализовывают) в определенной части весьма слабы. А т.к. это коммерческий продукт, то я думал, что мои разработки их заинтересуют, вернее, конкуренция заставит их это сделать. В-третьих, я ознакомил  своих коллег с моими результатами в режиме реального времени (а им лапшу на уши не навешаешь). И мой предыдущий пост был ответом на заданный мне вопрос и не более. А с Intel'ом мне все ясно и кроме замечательных процессоров (у меня сейчвс 2 компа: с q9450 и c i7 860) мне от них ничего не нужно.

А как же чипсеты? Чипсеты у вас какие стоят?

Интеловские.

Прогнал трехдиагонализацию под x64 последней версии Intel MKL на проце i7 860 на предмет возможных улучшений алгоритма: воз и ныне там - на матрице 5000*5000 Inel MKL на одном ядре дает 26.4 с, а у меня 21.1 с (при этом оптимизации алгоритма под новый проц. не проводил).

Век живи — век учись... На 2-х ядрах результат Intel MKL 16.3 с против 26.4 с на одном ядре (см. мое предыдущее сообщение). Т.е. ихний алгоритм распараллеливает и код, связанный с частью алгоритма трехдиагонализации, отвечающего за интенсивный обмен с памятью! Я сначала обалдел от мастерства ребят из Интела и хотел уже было написать хвалебную сагу об их гениальности. Но потом немного поостыл и начал анализировать возникшую ситуацию, т.к. в чудеса не очень верилось. А ларчик открывался просто: т.к. их алгоритм на одном ядре запрограммирован халтурно, то естественно, что он довольно неплохо распараллеливается на 2-х ядрах. Но их алгоритм не настолько плох, чтобы распараллеливаться и на 4-х ядрах: 14.9 с - здесь выигрыш определяется распараллеливанием части кода, который сродни перемножению матриц, т.е. хорошо распараллеливается. Да, HT я не подключал. Чему учит сей урок: c появлением многоядерности качество продукции может быть второй свежести и это сойдет вам с рук, хотя это не относится к алгоритмам, слабо зависящим от скорости памяти.

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

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

Так просветите, чтобы и остальные понимали о чем речь,
а не только "ребята из Интел" ...

Я им и писал: для широких масс не имеет смысл вдаваться в подробности, т.к. это высший пилотаж, реализованный на ассемблере да еще под конкретные процессоры (например, новая реализация команды pshufd на 45 нм. процессорах повлекла за собой пересмотр многих алгоритмов). Если не верите, разберите (например, с помощью Ida Pro) простешую процедуру dgemm - перемножение матриц: ее ядро требует использования не одной тысячи строк ассемблерного кода. А написание "коленного" кода занимет пару минут (а то и менее) и вмещается в несколько строчек. Но и работать будет на порядок медленней.

Глубокоуважаемые коллеги,

не могу, к сожалению, утверждать строго в отношении Ваших алгоритмов, т.к. принадлежу, по-видимому, к тем самым "широким массам", которым не хотят раскрывать подробностей высшего ассм. пилотажа (так что даже усомлюсь, что действительно "высший" - иногда кажется раз ассемблер - значит Пилотаж ;), однако предположу, что Вы, как это ни прискорбно, повторяете распространную ошибку, оценивая деловую целесообразность единственным фактором - эффективностью алгоритма. Действительно, с теоретической точки зрения, чем алгоритм эффективнее - тем лучше. Однако серьезный бизнес неохотно идет на внедрения новых алгоритмов - поскольку в бизнесе второй раз наступать на грабли очень накладно, а кто только не обжигался на самых новых алгоритмах/технологиях? Разве что новички. Так что солидные компании как Интел, кроме прочих, руководствуются принципом "старый конь борозды не испортит". И Вам, коллеги, придется долго доказывать (не Интелу, а самым широким массам) со всем "пилотажем", что Ваш алгоритм действительно не только быстрее, но и корректен, надежен, полон, прежде чем такая компания как Интел решится его реализовать в свой пакет. Так что учитывайте все факторы, значительные не только для теории, но и для делового мира ;)