2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 10  След.
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 09:14 


04/02/08
325
Буково
Если вам нужна только скорость, а особая точность не нужна, то лучше всего с поставленной задачей справятся видеокарты nVidia с их CUDA. Нужно лишь распараллелить стандартный алгоритм, хоть из того же GSL, чтобы равномерно нагрузить всю сотню-другую ядер процессоров видеокарты, а т.к. оперативной памяти у современных видеокарт предостаточно, можете перемножать хоть матрицы 10000х10000 :)

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 09:30 


26/01/10
959
Ed_Em в сообщении #287100 писал(а):
Если вам нужна только скорость, а особая точность не нужна, то лучше всего с поставленной задачей справятся видеокарты nVidia с их CUDA. Нужно лишь распараллелить стандартный алгоритм, хоть из того же GSL, чтобы равномерно нагрузить всю сотню-другую ядер процессоров видеокарты, а т.к. оперативной памяти у современных видеокарт предостаточно, можете перемножать хоть матрицы 10000х10000 :)

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

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 10:00 


21/03/06
1545
Москва
Хотелось бы поддержать автора в его начинании. На мой взгляд, идея подобного конкурса - интересная, постановка задачи - корректная, правила "игры" сформулированы четко и логично. Единственное - насчет денежного приза сомнения - а нужен ли он вообще? Тут как раз соревновательный и интеллектуальный эффект являются главным призом ИМХО.

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

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

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 10:31 


04/02/08
325
Буково
Zealint в сообщении #287104 писал(а):
Ed_Em в сообщении #287100 писал(а):
Если вам нужна только скорость, а особая точность не нужна, то лучше всего с поставленной задачей справятся видеокарты nVidia с их CUDA. Нужно лишь распараллелить стандартный алгоритм, хоть из того же GSL, чтобы равномерно нагрузить всю сотню-другую ядер процессоров видеокарты, а т.к. оперативной памяти у современных видеокарт предостаточно, можете перемножать хоть матрицы 10000х10000 :)

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

Тогда хорошей скорости вы никак не добьетесь. Ну а кластерное время довольно дорогое, дешевле пару видеокарт купить.

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 12:16 


26/01/10
959
e2e4 в сообщении #287110 писал(а):
Хотелось бы поддержать автора в его начинании. На мой взгляд, идея подобного конкурса - интересная, постановка задачи - корректная, правила "игры" сформулированы четко и логично. Единственное - насчет денежного приза сомнения - а нужен ли он вообще? Тут как раз соревновательный и интеллектуальный эффект являются главным призом ИМХО.

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

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


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

Цитата:
Тогда хорошей скорости вы никак не добьетесь. Ну а кластерное время довольно дорогое, дешевле пару видеокарт купить.

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

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 15:51 


30/12/09
95
Zealint в сообщении #287097 писал(а):
Понятия не имею что это такое. Был бы вам признателен, если бы вы поучаствовали как раз с этой реализацией. Если знакомы с ней, это отнимет у вас минут 10 да? Зато вы получите полную оценку этой реализации на практике.

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

Zealint в сообщении #287097 писал(а):
Ключевое слово - "адекватном". Где гарантия, что в uBLAS использование адекватное?

boost идет в исходниках да и в документаци они рассказывают ка именно оно у них реализовано.

Zealint в сообщении #287097 писал(а):
Вот мне как раз один товарищ еще прислала программу gotoBLAS2 (понятия не имею о том, что это), но работает все равно не слишком шустро... проигрывает реализации "в лоб", написанной кем-то на Delphi.

BLAS это вообще то порт фортрановсой бибиотеки и реализовать ее можно по разному.
На самом деле шаблоны после их "раскручивания" копилятором дают код эквивалентный тому что называется "в лоб".

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 16:31 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Думаю, BLAS в итоге будет в проигрыше, и вот почему. BLAS работает с числами с плавающей точкой, минимальный размер которых --- 4 байта. Причём 4-мя байтами, скорее всего, не обойтись, т.к. может накапливаться погрешность вычислений. А по условиям задачи, во-первых, значения целые (вычисления должны производиться точно), во-вторых, по модулю они не превышают 600, а значит, влезают в 2 байта. То есть мы можем проиграть по памяти в 4 раза только за счёт выбора плавающей точки. В данной задаче это критично, т.к. 90% матрицы в кэш L3 не влезает, а значит, в основном, мы будем работать со скоростью оперативной памяти, что будет сильно ограничивать быстродействие. Да и аппаратные средства позволяют за одну инструкцию перемножать 4 2-байтных числа (pmaddwd, если вдруг кто интересуется :D ), тогда как для плавающей точки всё не столь радужно (если не параллелить, что опять же запрещено условиями).

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 17:27 


04/02/08
325
Буково
Zealint, честно говоря, не понимаю вашего стремления не использовать сторонние библиотеки.
Приведу "собранный на коленке" пример перемножения матриц 5000x5000:
Код:
#include <stdio.h>
#include <gsl/gsl_matrix.h>
main(){
   int i, j;
   gsl_matrix *m1 = gsl_matrix_alloc(5000,5000);
   gsl_matrix *m2 = gsl_matrix_alloc(5000,5000);
   for(i=0; i<5000; i++)
      for(j=0; j<5000; j++){
         gsl_matrix_set(m1, i, j, i*5000.+j);
         gsl_matrix_set(m2, i, j, i*1000.+j);
      }
   gsl_matrix_mul_elements(m1, m2);
   FILE *f = fopen("matrix_mult", "w");
   for(i=0; i<5000; i++){
      for(j=0; j<5000; j++)
         fprintf(f, "%.0f\t", gsl_matrix_get(m1, i, j));
      fprintf(f, "\n");
   }
   fclose(f);
   gsl_matrix_free(m1);
   gsl_matrix_free(m2);
}

Выполняем:
Код:
gcc 1.c -lgsl -lgslcblas -lm && time ./a.out
48.41user 1.94system 0:58.87elapsed 85%CPU (0avgtext+0avgdata 0maxresident)k
1064inputs+0outputs (14major+97916minor)pagefaults 0swaps

Причем львиную долю времени, естественно, занимает запись в файл. Без нее:
Код:
gcc 1.c -lgsl -lgslcblas -lm && time ./a.out
2.09user 0.40system 0:02.50elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+97868minor)pagefaults 0swaps

Как видите, очень быстро.
Правда, кушает оно 387МБ оперативки, а файл с результатами занял 358МБ!

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 18:52 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Ed_Em, впечатляет!
Однако... Вы ничего не путаете? gsl_matrix_mul_elements действительно перемножает матрицы? А не элементы покомпонентно $c_{ij}=a_{ij}b_{ij}$ ?

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 18:59 


26/01/10
959
worm2 в сообщении #287159 писал(а):
Думаю, BLAS в итоге будет в проигрыше, и вот почему. ....

Не совсем, BLАS проигрывает даже тупой реализации без оптимизации по памяти, о которых вы говорите.

Цитата:
Zealint, честно говоря, не понимаю вашего стремления не использовать сторонние библиотеки.

Еще раз: в моей практике не было случая, когда нужную мне задачу библиотечная функция решала быстрее. Вы привели хороший пример. Почему бы вам не поучаствовать с этой библиотекой? Или она только под Linux? Конкурс для Linux я не могу сейчас провести по техническим причинам. Например, на разных линуксах одна и та же программа редко запускается (у меня так получается). То есть допустим, я мог бы расширить конкурс (добавить Linux), но вот добавлю я Ubuntu, а кто-то под Suse, добавлю Suse, а кто-то под Gentoo и т. д. Буду сидеть сутками и качать Linux, потом у меня диск закончится. Что делать? Кто посоветует?

Кстати, тов. Ed_Em, функция gsl_matrix_mul_elements ( ..., ... ) выполняет произведение Адамара, а не произведение матриц в алгебраическом смысле. То есть ваши 2 секунды - это даже слишком долго для такой программы. У меня полторы получилось : ) Ой, тут тов. worm2 вам уже то же самое сказал, пока я это писал...

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

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 19:06 


30/12/09
95
Zealint в сообщении #287204 писал(а):
Конкурс для Linux я не могу сейчас провести по техническим причинам. Например, на разных линуксах одна и та же программа редко запускается (у меня так получается). То есть допустим, я мог бы расширить конкурс (добавить Linux), но вот добавлю я Ubuntu, а кто-то под Suse, добавлю Suse, а кто-то под Gentoo и т. д. Буду сидеть сутками и качать Linux, потом у меня диск закончится. Что делать? Кто посоветует?

Их бинарники совместимы, т.е. собранные на Ubuntu будут идти под Red Hat и так далее.

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 19:08 


26/01/10
959
Roman Voznyuk в сообщении #287208 писал(а):
Их бинарники совместимы, т.е. собранные на Ubuntu будут идти под Red Hat и так далее.


Так вот к сожалению получается так, что ничего они не совместимы. Я делал программу под Suse, она не пошла под Ubuntu. Наоборот тоже пробовал. Одинаково.

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 19:09 


30/12/09
95
worm2 в сообщении #287159 писал(а):
Думаю, BLAS в итоге будет в проигрыше, и вот почему. BLAS работает с числами с плавающей точкой, минимальный размер которых --- 4 байта. Причём 4-мя байтами, скорее всего, не обойтись, т.к. может накапливаться погрешность вычислений. А по условиям задачи, во-первых, значения целые (вычисления должны производиться точно), во-вторых, по модулю они не превышают 600, а значит, влезают в 2 байта. То есть мы можем проиграть по памяти в 4 раза только за счёт выбора плавающей точки.

А если тип поменять? Он же шаблонный.

Zealint в сообщении #287209 писал(а):
Так вот к сожалению получается так, что ничего они не совместимы. Я делал программу под Suse, она не пошла под Ubuntu. Наоборот тоже пробовал. Одинаково.

И в чем была причина?

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 19:19 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Roman Voznyuk писал(а):
А если тип поменять? Он же шаблонный.
Не всякая реализация BLAS --- на шаблонах, тут ещё покопаться надо. Да и здесь хитрая ситуация: для входных данных нужна матрица short'ов, а для выходных --- матрица long'ов (ибо как раз подходит для матриц 5000x5000). Потянет ли какая-либо шаблонная реализация такую ситуацию, и сумеет ли компилятор после подстановки типов её хорошо соптимизировать?

 Профиль  
                  
 
 Re: Перемножение матриц - конкурс для программистов
Сообщение11.02.2010, 19:19 


26/01/10
959
Zealint в сообщении #287209 писал(а):
И в чем была причина?


Если бы я знал, то не заводил бы разговор. Давайте проведём эксперимент? (если у Вас есть время).
Напишите код и скомпилируйте под своим линуксом. Я протестую под своим. Только уже завтра, не сегодня. Только сделайте все по правилам: ввод из input.txt, вывод в output.txt. Почта моя указана в правилах конкурса.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 143 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 10  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group