мне кажется фотка из топика из-за склеивания разных версий карт. Откуда такое прикольное еще может получиться?! ТАм даже не хребет по линии смены цвета.
если не сложно - можете набросать маленькую программку на фортране (чтобы еще время считала), я её скомпилирую на своем компе и посмотрю время. Действительно интересно.
для некомпилируемых языков мне кажется совсем другая история. Там же код наверняка даже не оптимизируется как в компиляторе, хотя точно не могу сказать.
ну естественно потом оставшиеся 0-3 числа прогнать если останутся.
В большинстве случаев не стоят конечно. И даже противопоказано если там будет 5-10%. Но все-таки этот пример с матрицами чем хорош - прирост больше чем в 10 раз, ради такого уже и можно запариться
ну так без ужасного кода ускорить иногда не получается. Тут не просто избавление от циклов, а их разворачивание, т.е. если вы пишете
for (i=0; i<n; i++){
s+=какие-то вычисления с участием a[i];
}
то иногда можно ускорить вроде бы ничего не меняющим:
for (i=0; i<n; i+=4){
s+=какие-то вычисления с участием a[i];
s+=какие-то вычисления с участием a[i+1];
s+=какие-то вычисления с участием a[i+2];
s+=какие-то вычисления с участием a[i+3];
}
Ускорение будет если все переменные внутри цикла поместятся в регистры процессора.
Заметьте - в теле цикла банальный копипаст..
нет, тут обычное перемножение влоб с n^3 операций, просто организовано так, чтобы данные чаще всего брались их кэша.
Суть алгоритма: делим матрицу на маленькие подматрицы и перемножаем наши матрицы из подматриц как будто это матрицы из чисел. Вместо чисел перемножаются маленькие матрицы по обычному перемножению матриц.
Возможно Штрассена тоже можно так оптимизировать и он будет работать еще быстрее, чем этот блочный алгоритм.
ну если расписать все формулы при умножении с подматрицами для одного ij-го элемента, то как раз получится формула для обычного умножения матриц. Тут просто неудобно это расписывать, но это 100% верно
такая оптимизация из-за жестких требований в ВУЗе ))
А применение - думаю в вычислениях, например как у Умпутуна, (ежедневная обработка огромного количества данных с вычислением каких-то коэффициентов причем за наименьшее время) можно использовать подобную технику оптимизации
А остальные картинки чудо как хороши!
и из его книги http://www.book.ru/69565 Основы параллельного программирования
В большинстве случаев не стоят конечно. И даже противопоказано если там будет 5-10%. Но все-таки этот пример с матрицами чем хорош - прирост больше чем в 10 раз, ради такого уже и можно запариться
matrix_test.cpp(285): (col. 2) remark: LOOP WAS VECTORIZED.
matrix_test.cpp(276): (col. 2) remark: LOOP WAS VECTORIZED.
imac-gleb:Desktop gleb$ ./a.out 2000 200 3
multMatrixSqBad: 74.2494
multMatrixSq: 26.1671
multMatrixBlock: 6.08273
imac-gleb:Desktop gleb$ ./a.out 2000 200 3
multMatrixSqBad: 74.2678
multMatrixSq: 25.3441
multMatrixBlock: 6.04398
imac-gleb:Desktop gleb$
Еще быстрее! Жалко что его только на месяц бесплатно дают :(
for (i=0; i<n; i++){
s+=какие-то вычисления с участием a[i];
}
то иногда можно ускорить вроде бы ничего не меняющим:
for (i=0; i<n; i+=4){
s+=какие-то вычисления с участием a[i];
s+=какие-то вычисления с участием a[i+1];
s+=какие-то вычисления с участием a[i+2];
s+=какие-то вычисления с участием a[i+3];
}
Ускорение будет если все переменные внутри цикла поместятся в регистры процессора.
Заметьте - в теле цикла банальный копипаст..
http://habrahabr.ru/blog/i_am_clever/368…
возможно это еще ускорит, правда может будет больше конфликтов по памяти и из-за этого ускорения не получится, хз, надо пробовать
Суть алгоритма: делим матрицу на маленькие подматрицы и перемножаем наши матрицы из подматриц как будто это матрицы из чисел. Вместо чисел перемножаются маленькие матрицы по обычному перемножению матриц.
Возможно Штрассена тоже можно так оптимизировать и он будет работать еще быстрее, чем этот блочный алгоритм.
да, алгоритмы, для которых нужно меньше чем n^3 я просмотрел, перед тем как писать топик, но понял, что это жесть)
А применение - думаю в вычислениях, например как у Умпутуна, (ежедневная обработка огромного количества данных с вычислением каких-то коэффициентов причем за наименьшее время) можно использовать подобную технику оптимизации
http://blog.lexa.ru/2007/10/16/umnozheni…
вот тут про это есть, и про сабж тоже есть, правда в другом ключе