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
3156
Уфа
Думаю, 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
3156
Уфа
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
3156
Уфа
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, Супермодераторы



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

Сейчас этот форум просматривают: Dmitriy40


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

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