Intel® Software Network

Необходимо четко представлять, какие алгоритмы подлежат распараллеливанию, а какие - нет в моделях с общей памятью (к которым относятся большинство современных десктопных компов с многоядерными процессорами). Например, львиную долю времени при трехдиагонализации симметричных матриц занимает BLAS Level 2 и для него безразлично, сколько ядер у Вашего процессора. Все упирается в пропускную способность оперативной памяти и дело можно поправить, только увеличив частоту этой памяти. Иное дело - грамотный алгоритм перемножения м-ц : здесь можно добиться прекрасного распараллеливания (см. мою страницу http://www.thesa-store.com/products/ , где описаны новые алгоритмы диагонализации матриц и их перемножения (например, разработан новый алгоритм быстрого перемножения м-ц, который не требует выделения дополнительной оперативной памяти) и их сравнение с соответствующими алгоритмами, реализованными в Intel MKL). С полученными результатами также можно ознакомиться по статьям, которые опубликованы на моей странице.

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

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

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

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

---

Дмитрий Оганезов
Intel® Software Network

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

.

Несколько лет назад переписывался с 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 и вашего алгоритма. Это возможно? Я почитал у вас на сайте, вы описываете методику сравнения. Вы можете предоставить исполняемый файл для сравнения на нашей стороне? Если разработчики подтвердят ваши данные - я буду думать, что мы можем сделать дальше.

Удачи!

---

Дмитрий Оганезов
Intel® Software Network

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

---

Дмитрий Оганезов
Intel® Software Network

MAD\doganezo:

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

Дмитрий,

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

Юрий

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

 

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

 

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

 

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

 

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

---

Дмитрий Оганезов
Intel® Software Network

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, т.к. на время расчета велико влияние квадратичных операций. При распараллеливании моего алгоритма результаты должны быть значительно лучше. Появится свободное время - займусь распараллеливанием.