Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 114
научите плиз нормальные таблицы делать!
Писал так: <table cellspacing=3 cellpadding=3 border=1>
Писал так: <table cellspacing=3 cellpadding=3 border=1>
да, как обычно: важен подход, а не метод реализации. А подходу долго и муторно учат в техническим ВУЗах...
Увы, часто все сводится к "сидите, и разбирайтесь сами, а я потом проверю"
Про подход говорилось много. Скажем тут. Взять код из статьи и сравнить с тем, что породили вы. Поучительно.
Опять-таки подход-подходом, но и результат тоже бывает важен, так сравнить это дело с Blitz++, uBlasом и ATLASом было бы неплохо.
Вообще статья получилась странная в результате: если мы хотим иллюстрировать технику, то зачем нам все эти ухищрения с неполными блоками, усложняющие код, если мы хотим получить результат - то почему нет сравниения с уже полученными результатами???
Опять-таки подход-подходом, но и результат тоже бывает важен, так сравнить это дело с Blitz++, uBlasом и ATLASом было бы неплохо.
Вообще статья получилась странная в результате: если мы хотим иллюстрировать технику, то зачем нам все эти ухищрения с неполными блоками, усложняющие код, если мы хотим получить результат - то почему нет сравниения с уже полученными результатами???
Копипаст должен умереть раз и на всегда.
это вы к чему?
Взгляните на этот код - он ужасен.
А то, что избавление от циклов дает прирост производительности всем и так понятно.
А то, что избавление от циклов дает прирост производительности всем и так понятно.
Это не топик для обсуждения красоты кода.
Если присмотритесь внимательнее - увидите, что повторяющиеся с виду блоки кода не идентичны.
Если присмотритесь внимательнее - увидите, что повторяющиеся с виду блоки кода не идентичны.
ну так без ужасного кода ускорить иногда не получается. Тут не просто избавление от циклов, а их разворачивание, т.е. если вы пишете
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];
}
Ускорение будет если все переменные внутри цикла поместятся в регистры процессора.
Заметьте - в теле цикла банальный копипаст..
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];
}
Ускорение будет если все переменные внутри цикла поместятся в регистры процессора.
Заметьте - в теле цикла банальный копипаст..
еще a обязательно должно быть кратно 4 - иначе за пределы выйдем
а эти крохи производительности стоят ухудшения поддержки кода?
а эти крохи производительности стоят ухудшения поддержки кода?
ну естественно потом оставшиеся 0-3 числа прогнать если останутся.
В большинстве случаев не стоят конечно. И даже противопоказано если там будет 5-10%. Но все-таки этот пример с матрицами чем хорош - прирост больше чем в 10 раз, ради такого уже и можно запариться
В большинстве случаев не стоят конечно. И даже противопоказано если там будет 5-10%. Но все-таки этот пример с матрицами чем хорош - прирост больше чем в 10 раз, ради такого уже и можно запариться
если эти несколько десятков строк кода будут отнимать 80% времени вычислений для задачи, выполнение которой рассчитанной на год — безусловно, стоит
и во многих других случаях тоже
и во многих других случаях тоже
это две стороны одной монеты - скорость исполнения в очень общем случае обратно пропорциональна объему кода. так что спорить что тут лучше что хуже мне кажется неверно.
угу
осталось ещё в 6 семестре mpi-версию написать :)
осталось ещё в 6 семестре mpi-версию написать :)
А на ассемблере кода будет еще больше, но и работать то будет сверх-быстро!
это еще почему?
неа, на данный момент компиляторы оптимизируют код намного лучше человека, они ведь учитывают размер кэша, количество регистров и т.п. Так что разворачивать циклы и расчитывать, чтобы то что надо попало в кэш когда надо - единственное что остается делать программисту. Остальное сделает gcc
У gcc кстати довольно плохой оптимизатор по сравнению с VC и Intel.
Про VC просто лучше промолчать - он никогда особенно хорош не был, а Intel... Intel делает использует опасные оптимизации, что приводит к тому, что результат невозможно использовать: да вы что-то такое насчитаете быстро, но вот что - большой вопрос... Вот тут ребята, которые занимаются разработкой скоростных библиотек как раз вещей типа перемножения матриц об этом пишут. Inter Fortran - да, тот получше, чем gfortran...
> неа, на данный момент компиляторы оптимизируют код намного лучше человека, они ведь учитывают размер кэша
Вряд ли они учитывают *размер* кэша. Скорее L2 cache *line size*
Вряд ли они учитывают *размер* кэша. Скорее L2 cache *line size*
на данный момент компиляторы оптимизируют код намного лучше человека
Ерунда
Ерунда
К сожалению или к счастью правда. Человек любую программу мало-мальски ненулевого размера будет доводить до уровня, который обгонит компилятор пару лет - это как раз хватит для того, чтобы вышел новый процессор и пришлось всё начинать с начала...
Другое дело что компилятор строго следит за буквой программы, а не за её логикой, а так как операторы сложения, умножения и прочего в компьютерах ведут себя не так как в математике (скажем с транзитивностью полный швах), то многие оптимизации, которые может сделать человек компилятор сделать либо вообще не может (нормальные компиляторы), либо может - но с непредсказуемыми результами (ICC).
Другое дело что компилятор строго следит за буквой программы, а не за её логикой, а так как операторы сложения, умножения и прочего в компьютерах ведут себя не так как в математике (скажем с транзитивностью полный швах), то многие оптимизации, которые может сделать человек компилятор сделать либо вообще не может (нормальные компиляторы), либо может - но с непредсказуемыми результами (ICC).
Правило 90/10 Вам, очевидно, не знакомо? Тем более что сейчас это скорее 95/5.
Я умею оптимизить C++ код и работаю в геймдеве.
Про то что компиляторы оптимизируют лучше человека смешно читать.
Компилятор "смотрит" на программу через призму языка. К тому же трансформации/оптимизации которые может делать человек ему не под силу, либо их нельзя заставить работать так, как нужно программисту.
Язык, который не позволяет мне получить в точности то, что я задумал - отстоен по определению.
С++ весь такой убого скалярный и нормально векторизовать программы можно только вручную на intrinsics или asm. Проблема, как ни парадоксально в том, что C++ _недостаточно_ высокоуровневый язык чтобы писать на нём _быстродействующий_ код. Функциональные языки имеют более высокий потенциал к высокопроизводительному коду.
х86 процессоры научились быстро жрать то, что им подсовывают.
Однако существуют ещё и другие процессоры, более требовательные к качеству компиляции. Я в своё время оптимизил GSM декодер под ARM тупо переписав его на асм без особых оптимизаций и получил 10X ускорение.
Асмовая программа не скована ABI и может использовать удобное распределение регистров, которое снизит стековый онанизм.
А то, что генерит PPC-gcc или XLC, вообще, мягко говоря, отвратительно.
Я умею оптимизить C++ код и работаю в геймдеве.
Про то что компиляторы оптимизируют лучше человека смешно читать.
Компилятор "смотрит" на программу через призму языка. К тому же трансформации/оптимизации которые может делать человек ему не под силу, либо их нельзя заставить работать так, как нужно программисту.
Язык, который не позволяет мне получить в точности то, что я задумал - отстоен по определению.
С++ весь такой убого скалярный и нормально векторизовать программы можно только вручную на intrinsics или asm. Проблема, как ни парадоксально в том, что C++ _недостаточно_ высокоуровневый язык чтобы писать на нём _быстродействующий_ код. Функциональные языки имеют более высокий потенциал к высокопроизводительному коду.
х86 процессоры научились быстро жрать то, что им подсовывают.
Однако существуют ещё и другие процессоры, более требовательные к качеству компиляции. Я в своё время оптимизил GSM декодер под ARM тупо переписав его на асм без особых оптимизаций и получил 10X ускорение.
Асмовая программа не скована ABI и может использовать удобное распределение регистров, которое снизит стековый онанизм.
А то, что генерит PPC-gcc или XLC, вообще, мягко говоря, отвратительно.
это неправда
А стоимость разработки на ассемблере будет на порядок выше стоимости разработки на С, а работать будет врядли быстрее, если программист на С возьмет в руки VTune.
вот это можно назвать программированием — математика на Си :)
а всякие пыхыпы и жаваскрипт — это так, скриптование :)
а всякие пыхыпы и жаваскрипт — это так, скриптование :)
глупости. посмотрите значение слова "программирование" ...
;) :)
Толковый словарь русского языка:
Часть прикладной математики и вычислительной техники, разрабатывающая методы составления программ
Большой Энциклопедический словарь:
ПРОГРАММИРОВАНИЕ, процесс подготовки задач для решения их на ЭВМ, состоящий из следующих этапов: составление ''плана решения'' задачи в виде набора операций (алгоритмическое описание задачи); описание ''плана решения'' на языке программирования (составление программы); трансляция программы с языка программирования на машинный язык (в виде последовательности команд, реализация которых техническими средствами ЭВМ и есть процесс решения задачи). Программированием называют также раздел прикладной математики, изучающий и разрабатывающий методы и средства составления, проверки и улучшения программ для ЭВМ.
Математика нужна в Х% всех задач, решаемых компьютером и программированием (в смысле, что знать математику и т.п.).
ПРОГРАММИРОВАНИЕ, процесс подготовки задач для решения их на ЭВМ, состоящий из следующих этапов: составление ''плана решения'' задачи в виде набора операций (алгоритмическое описание задачи); описание ''плана решения'' на языке программирования (составление программы); трансляция программы с языка программирования на машинный язык (в виде последовательности команд, реализация которых техническими средствами ЭВМ и есть процесс решения задачи). Программированием называют также раздел прикладной математики, изучающий и разрабатывающий методы и средства составления, проверки и улучшения программ для ЭВМ.
Математика нужна в Х% всех задач, решаемых компьютером и программированием (в смысле, что знать математику и т.п.).
ПХП для своей области применения хорош, а то,то это скриптовый язык - никто и не скрывает. Скриптам тоже оптимизация нужна. Тут все от программиста зависит.
Лично я считаю что ряд функционала ПХП скриптов лучше вынести в отдельные программы на компилируемом языке (например, шаблонизатор + кэширование шаблонов, синхронизация и агрегация данных нескольких сайтов). Кроме того, считаю использование ПХП + cron считаю ересью, для таких задач польше подойдет bash. Хотя это мое мнение.
Лично я считаю что ряд функционала ПХП скриптов лучше вынести в отдельные программы на компилируемом языке (например, шаблонизатор + кэширование шаблонов, синхронизация и агрегация данных нескольких сайтов). Кроме того, считаю использование ПХП + cron считаю ересью, для таких задач польше подойдет bash. Хотя это мое мнение.
плин -) это алгоритмизация если что. а алгоритмы это самая что ни на есть математика.
непонятно, какой смысл вы вкладываете в слово "скриптование", противопоставляя его "программированию"
Кстати, было бы интересно увидеть результаты работы после сборки Intel C++ Compiler"ом - он умеет векторизировать циклы.
SSE инструкции появились девять лет назад, и продолжать их упорно неиспользовать это глупо.
SSE инструкции появились девять лет назад, и продолжать их упорно неиспользовать это глупо.
попробую скачать и скомпилировать, первый раз про него слышу, думал у gcc нет конкурентов
Разве использование этих инструкций в результирующем коде нельзя включить опциями компилятора Intel?
а если матриц много, то, возможно, будет выгоднее поручить расчёты видеокарте?
тоже интересный вариант. где-то мелькал open source sdk для видеокарт nvidia
http://blog.lexa.ru/2007/01/04/o_peremno…
http://blog.lexa.ru/2007/10/16/umnozheni…
вот тут про это есть, и про сабж тоже есть, правда в другом ключе
http://blog.lexa.ru/2007/10/16/umnozheni…
вот тут про это есть, и про сабж тоже есть, правда в другом ключе
Правильно. Но все же векторизацию вычислений нужно (правильнее) делать с головой (алгоритмом), а не компилятором.
Параллелизация и оптимизация под N-CPU SMP сильно зависит от алгоритма в плане, например, работы с памятью и кэшем. Чтобы не было тормозов необходимо, чтобы изменения не делались одновремнно в участках памяти менее cpu cache line size. Ну и для более высокого уровня кэша тоже оптимизироваться можно, если объем данных большой.
Даже при работе с NVIDIA CUDA необходимо думать о размерах кэшей, а Intel под свои CPU это прямым текстом рекомендует в своим материалах для разработки.
Какой бы ни был офигенный алгоритм с распарралеливанием компилятором - это не панацея и может не давать прироста в производительности из-за ошибок связанных с незнанием принципов работы CPU и кэшей.
Подобные алгоритмы не заточенные под SMP - это не то, чтобы "детский сад, вторая группа", но уже явно "вчерашний день".
Параллелизация и оптимизация под N-CPU SMP сильно зависит от алгоритма в плане, например, работы с памятью и кэшем. Чтобы не было тормозов необходимо, чтобы изменения не делались одновремнно в участках памяти менее cpu cache line size. Ну и для более высокого уровня кэша тоже оптимизироваться можно, если объем данных большой.
Даже при работе с NVIDIA CUDA необходимо думать о размерах кэшей, а Intel под свои CPU это прямым текстом рекомендует в своим материалах для разработки.
Какой бы ни был офигенный алгоритм с распарралеливанием компилятором - это не панацея и может не давать прироста в производительности из-за ошибок связанных с незнанием принципов работы CPU и кэшей.
Подобные алгоритмы не заточенные под SMP - это не то, чтобы "детский сад, вторая группа", но уже явно "вчерашний день".
а он есть в свободном доступе?
imac-gleb:Desktop gleb$ icc matrix_test.cpp -O3
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$
Еще быстрее! Жалко что его только на месяц бесплатно дают :(
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$
Еще быстрее! Жалко что его только на месяц бесплатно дают :(
"И будем перемножать матрицу из подматриц по обычному правилу. Не сложно математически доказать, что ответ получится такой же как и при обычном перемножении"
Раскажи-ка тут поподробнее.
Раскажи-ка тут поподробнее.
ну если расписать все формулы при умножении с подматрицами для одного ij-го элемента, то как раз получится формула для обычного умножения матриц. Тут просто неудобно это расписывать, но это 100% верно
Хорошо, я сейчас обьясню в чём у меня была проблема.
Дело в том, что алгоритм Штрассена (в котором мы разбиваем матрицу на 4 подматрицы а затем обходимся перемножением 7 матриц размером n/2) действует рекурсивно. В результате чего мой код на си под юникс для матрицы 2000x2000 дал результат по времени в 75% процентов по сравнению с подсчётом в лоб. Теоретически же он должен был дать 23%. Но я не оптимизировал его иначе как алгоритмически. Потери времени у меня как раз были на этапе выделения памяти. Так вот вы использовали этот алгоритм, я правильно понял?
Дело в том, что алгоритм Штрассена (в котором мы разбиваем матрицу на 4 подматрицы а затем обходимся перемножением 7 матриц размером n/2) действует рекурсивно. В результате чего мой код на си под юникс для матрицы 2000x2000 дал результат по времени в 75% процентов по сравнению с подсчётом в лоб. Теоретически же он должен был дать 23%. Но я не оптимизировал его иначе как алгоритмически. Потери времени у меня как раз были на этапе выделения памяти. Так вот вы использовали этот алгоритм, я правильно понял?
нет, тут обычное перемножение влоб с n^3 операций, просто организовано так, чтобы данные чаще всего брались их кэша.
Суть алгоритма: делим матрицу на маленькие подматрицы и перемножаем наши матрицы из подматриц как будто это матрицы из чисел. Вместо чисел перемножаются маленькие матрицы по обычному перемножению матриц.
Возможно Штрассена тоже можно так оптимизировать и он будет работать еще быстрее, чем этот блочный алгоритм.
Суть алгоритма: делим матрицу на маленькие подматрицы и перемножаем наши матрицы из подматриц как будто это матрицы из чисел. Вместо чисел перемножаются маленькие матрицы по обычному перемножению матриц.
Возможно Штрассена тоже можно так оптимизировать и он будет работать еще быстрее, чем этот блочный алгоритм.
Ага, всё понятно. Если сделаешь подобную оптимизацию для алгоритма Штрассена - выложи, мне очень интересен результат. Там явно надо грамотно обращаться с памятью :)
И если интересно будет, попробуй ещё поработать с алгоритмом Винограда (именно Винограда, а не Копперсмита—Винограда), там совсем ничего сложного нет, но мне кажется подобная оптимизация заставит его работать лучше, чем просто блочное перемножение. У меня на тех же матрицах он дал результат в 50% от времени перебора в лоб.
И если интересно будет, попробуй ещё поработать с алгоритмом Винограда (именно Винограда, а не Копперсмита—Винограда), там совсем ничего сложного нет, но мне кажется подобная оптимизация заставит его работать лучше, чем просто блочное перемножение. У меня на тех же матрицах он дал результат в 50% от времени перебора в лоб.
Вообще я стараюсь пользоваться scilab, но там пока-что очень неудобно реализовывать сложные алгоритмы - иногда приходится писать на c# (мне он просто нравится).
В своих, исследовательских задачах, я так с оптимизацией не заморачиваюсь. Главное - результат расчёта. С теми же матрицами, если начнёшь оптимизировать, то сдохнуть можно (во всяком случае времени на это обычно нет). Ведь видов матриц тьма, оптимизировать под каждый встречающийся вид - жалко себя и своё свободное время.
Вот стало интересно, а вам зачем такая оптимизация, получить моральное удовлетворение от успеха или, для дела?
Оговорюсь, правда, что если, вдруг появится действительно большая задача (на день-два счёта) - тогда пооптимизирую... хотя, можно сходить на концерт, а компьютер пусть посчитает, на то он и железка. )
В своих, исследовательских задачах, я так с оптимизацией не заморачиваюсь. Главное - результат расчёта. С теми же матрицами, если начнёшь оптимизировать, то сдохнуть можно (во всяком случае времени на это обычно нет). Ведь видов матриц тьма, оптимизировать под каждый встречающийся вид - жалко себя и своё свободное время.
Вот стало интересно, а вам зачем такая оптимизация, получить моральное удовлетворение от успеха или, для дела?
Оговорюсь, правда, что если, вдруг появится действительно большая задача (на день-два счёта) - тогда пооптимизирую... хотя, можно сходить на концерт, а компьютер пусть посчитает, на то он и железка. )
такая оптимизация из-за жестких требований в ВУЗе ))
А применение - думаю в вычислениях, например как у Умпутуна, (ежедневная обработка огромного количества данных с вычислением каких-то коэффициентов причем за наименьшее время) можно использовать подобную технику оптимизации
А применение - думаю в вычислениях, например как у Умпутуна, (ежедневная обработка огромного количества данных с вычислением каких-то коэффициентов причем за наименьшее время) можно использовать подобную технику оптимизации
)
кто такой Умпутун, правда, не знаю ) но, да, когда ежедневно много считается - не грех и пооптимизировать.
Есть ещё алгоритм штрассена - при заполненных (плотных) матрицах даёт хороший выигрыш.
кто такой Умпутун, правда, не знаю ) но, да, когда ежедневно много считается - не грех и пооптимизировать.
Есть ещё алгоритм штрассена - при заполненных (плотных) матрицах даёт хороший выигрыш.
http://umputun.habrahabr.ru/ - грех не знать =)
да, алгоритмы, для которых нужно меньше чем n^3 я просмотрел, перед тем как писать топик, но понял, что это жесть)
да, алгоритмы, для которых нужно меньше чем n^3 я просмотрел, перед тем как писать топик, но понял, что это жесть)
Да, зачем в formula() параметр n?
double formula(int i, int j, int n){
return 1/(double(i+j+1));
}
double formula(int i, int j, int n){
return 1/(double(i+j+1));
}
Заметка хорошая с точки зрения того на что стоит обратить внимание.
А вообще-то быстрое перемножение матриц для начала надо реализовать на блоках 2х2. Как Вы думаете, сколько для этого надо операций умножения? 8? А вот и нет, 7. :) А это существенная экономия.
А вообще-то быстрое перемножение матриц для начала надо реализовать на блоках 2х2. Как Вы думаете, сколько для этого надо операций умножения? 8? А вот и нет, 7. :) А это существенная экономия.
ага, алгоритм Штрассена, про него уже тут написали
http://habrahabr.ru/blog/i_am_clever/368…
возможно это еще ускорит, правда может будет больше конфликтов по памяти и из-за этого ускорения не получится, хз, надо пробовать
http://habrahabr.ru/blog/i_am_clever/368…
возможно это еще ускорит, правда может будет больше конфликтов по памяти и из-за этого ускорения не получится, хз, надо пробовать
Ну... такая хорошая оптимизация алгоритма - это конечно курто (да и редко в наше время). Но если это критичсекий код, то как говорилось, лучше вручную переписать с SSE (а может и на GPU :) ). Или попытаться реализовать другие алгоритмы умножения, типа алгоритма Штрассена (если конечно его погрешности допустимы). Википедия говорит, что тогда есть шансы некубически выиграть производительность на размерах >128. К тому же он производит впечатление алгоритма неплохо забивающего кеш.
Неплохо было бы если камрад автор присоветовал теорию для скуривания.
Тоже хочешь "быстрее хранить одномерные массивы"? :)
Имею ввиду теорию по оптимизации, не только к операциям над матрицами. Ну чтобы с тонкостями.
А как это - "быстрее хранить"? =)
А как это - "быстрее хранить"? =)
я всё это извлек из семинаров К.Ю. Богачева
и из его книги http://www.book.ru/69565 Основы параллельного программирования
и из его книги http://www.book.ru/69565 Основы параллельного программирования
А для перла что посоветуете ?
а на перле посоветуем не заморачиваться оптимизированием перемножения матриц - все равно тормозз
для некомпилируемых языков мне кажется совсем другая история. Там же код наверняка даже не оптимизируется как в компиляторе, хотя точно не могу сказать.
для перла советую использовать как можно чаще его внутренние функции
Это же цирк. Если нужна математическая производительность, велкам ту фортран.
A = B * C
главное, чтобы размерность подходила.
A = B * C
главное, чтобы размерность подходила.
если не сложно - можете набросать маленькую программку на фортране (чтобы еще время считала), я её скомпилирую на своем компе и посмотрю время. Действительно интересно.
Фортран традиционно используется для расчётов, поэтому существует огромное количество оптимизированных умножателей матриц для него. Плюс встроенное умножение матриц в некоторых версиях. Поэтому, сейчас никто сам уже не пишет эти умножения, поэтому Фортран, вроде как, удобнее. Однако тот же BLAS и с C/C++ неплохо дружит. Если интересно, возьмите BLAS или MKL, там в комплекте тесты идут, потестируйте... Но вообще, смысла, скорее всего нет. Фортран не так уж и сильно отличается по вычислительной семантике от Си, чтобы чудес от него ждать.
Отличается. В качестве примера цикл:
for (int i=0;i<size;++i) {
a[i]=b[i]+b[i+1];
}
Может ли компилятор развернуть цикл так, чтобы использовать значение b[i+1], загруженное в регистр на предыдущем шаге? Ответ в Fortran: да, разумеется. Ответ в C/C++: вообще говоря нет. Почему? Очень просто: вдруг (b+1)==a ? Если компилятор может как-то напрячься и понять что это не так (скажем и a и b - статические переменные), тогда - пожалуйста, но в общем случае - нет. Правда у Fortran'а есть свой бич: F90-style массивы. Можно делать срезы других массивов, что изредка бывает удобно, но обычно - страшная головная боль для разработчиков компиляторов и больше ничего. Некоторые компиляторы даже имеют ключ, отключаещий это дело. Почему в супер-пупер-скоростной язык попал такой ужас? Очень просто: векротные компьютеры 80х обрабатывали такие вещи на аппаратном уровне и там это не было потерей в производительности. А в 90е - это стало большой проблемой из-за кешей, но стандарт - есть стандарт...
for (int i=0;i<size;++i) {
a[i]=b[i]+b[i+1];
}
Может ли компилятор развернуть цикл так, чтобы использовать значение b[i+1], загруженное в регистр на предыдущем шаге? Ответ в Fortran: да, разумеется. Ответ в C/C++: вообще говоря нет. Почему? Очень просто: вдруг (b+1)==a ? Если компилятор может как-то напрячься и понять что это не так (скажем и a и b - статические переменные), тогда - пожалуйста, но в общем случае - нет. Правда у Fortran'а есть свой бич: F90-style массивы. Можно делать срезы других массивов, что изредка бывает удобно, но обычно - страшная головная боль для разработчиков компиляторов и больше ничего. Некоторые компиляторы даже имеют ключ, отключаещий это дело. Почему в супер-пупер-скоростной язык попал такой ужас? Очень просто: векротные компьютеры 80х обрабатывали такие вещи на аппаратном уровне и там это не было потерей в производительности. А в 90е - это стало большой проблемой из-за кешей, но стандарт - есть стандарт...
Так глобальная же оптимизация проводится. И то, чему реально соответсвуют a и b вычисляется и учитывается. Понятно, конечно, что всё в Си можно написать с указателями и так, что любой оптимизатор загнётся. Но можно так и не писать, использовать статические или автоматические массивы... Вообще, обычно, вроде, их хватает, тем более, что c99 позволяет автоматическим массивам иметь вычисляемый в runtime размер. Тут главное, квоты не забыть поправить : ).
А про срезы можно подробнее? Никогда не сталкивался с проблемой такой.
А про срезы можно подробнее? Никогда не сталкивался с проблемой такой.
Вы много 3D игр на фортране видели ?
А там очень нужна математическая производительность.
А там очень нужна математическая производительность.
Многие системы программирования позволяют компоновать полученные в результате трансляции фортрановской программы объектные файлы с объектными файлами, полученными от компиляторов с других языков, что позволяет создавать более гибкие и многофункциональные приложения.
То есть математические вычисления можно выполнять отдельно на фортране, и адекватно вплетать в C/C++-приложения.
То есть математические вычисления можно выполнять отдельно на фортране, и адекватно вплетать в C/C++-приложения.
А вы много 3D игр не на Фортране видели? Вообще, очень сложно судить о том, какие средства используют программисты для написания игр. Исходники закрыты. При этом известно, что 3D игры пишут (именно, не писали, а пишут) даже на Lisp, и ничего, всё шустро бегает. Так что это... Почему бы и не фортран для некоторых функций, связанных с расчётами?
Эх... Когда-нибудь, в старости, я буду сидеть где-нибудь в кресле-качалке, смотреть на звезды, и читать исходник 3д гамы написанный на смеси хаскелла, си и ассемблерных вставок... А скрипты все в той игре будут на перле...
Эх мечты-мечты >_<
Эх мечты-мечты >_<
Тему только переводить не надо, на Lisp ни один разумный человек частоипользуемое перемножение матриц делать не будет.
А так я всегда "за" чтобы технологии по назначению заюзать. Кодогенерация и все такое.
А так я всегда "за" чтобы технологии по назначению заюзать. Кодогенерация и все такое.
Вопрос в размере матриц. Если это матрицы 4x4 и 4x1, как в играх, то Lisp способен их представлять и умножать достаточно эффективно. Реализовывать умножение, конечно, смысла никакого нет... Но речь и не об этом, речь о том, что в играх разные языки могут использоваться, в том числе и Фортран.
Для кодогенерации с оптимизацией Lisp не очень хорошо подходит. Работа с графами - это не конёк функциональных языков... Постоянно писать set - удовольствие сомнительное. Или вы о метапрограммировании?
Для кодогенерации с оптимизацией Lisp не очень хорошо подходит. Работа с графами - это не конёк функциональных языков... Постоянно писать set - удовольствие сомнительное. Или вы о метапрограммировании?
Спасибо за статью :) Ещё б тот же алгоритм на асме - цены бы вам не было :-D
А не встречал ли кто алгоритма по разложению большой матрицы на произведение двух небольших?
всмысле? если они квадратные, то у всех размеры будут одинаковые
Когда заканчивал универ в 2001 году увлекся немного задачей по поиску алгоритма разложения любой матрицы состоящей из 0 и 1 на произведение двух более мелких. Задача в основном состояла в том, чтобы найти способ минимальных перестановок в матрице, после которых она стала возможна к простому разложению на произведение двух более мелких матриц.
P.S. Это было давно, и после того момента с матрицами вообще не работал, поэтому сорри за каламбур, пост навеял молодость :)
P.S. Это было давно, и после того момента с матрицами вообще не работал, поэтому сорри за каламбур, пост навеял молодость :)
1. исключить многочисленные a[j], a[i], a[k] в теле цикла, надо ходить по указателям ++, а не получать доступ к элементу по индексу.
2. вместо плавающей использовать фиксированную точку + параллельно вычислять за один проход несколько сложений, вычитаний, или умножений, "распараллелить" (в кавычках)
3. кроме этого по настоящему распараллелить вычисления.
2. вместо плавающей использовать фиксированную точку + параллельно вычислять за один проход несколько сложений, вычитаний, или умножений, "распараллелить" (в кавычках)
3. кроме этого по настоящему распараллелить вычисления.
Хехе.. Читаем Code Complete http://www.amazon.com/Code-Complete-Prac…
Там в клаве про оптимизацию есть этот пример (с разворачиванием строчек цикла) и другой.
Во втором примере автор пытался так же оптимизировать умножение матриц. Но его переписывания с лихвой перекрыла оптимизация компилятора..
Вывод: стоит ли оптимизировать, если бутылочное горлышко не в этом месте? ;)
Там в клаве про оптимизацию есть этот пример (с разворачиванием строчек цикла) и другой.
Во втором примере автор пытался так же оптимизировать умножение матриц. Но его переписывания с лихвой перекрыла оптимизация компилятора..
Вывод: стоит ли оптимизировать, если бутылочное горлышко не в этом месте? ;)
Для начала определимся, что матрицы будем хранить в одномерном массиве размера n*n. К элементу A(i, j) будем обращаться как a[i*n+j]. Хранить в одномерном быстрее чем в двумерном массиве, т.к. одно целочисленное умножение и одно обращение к памяти работает быстрее, чем два обращения к памяти.
Спорное утверждение. В release или O3 должно быть одинаково. Потому что это есть одно и тоже.
Спорное утверждение. В release или O3 должно быть одинаково. Потому что это есть одно и тоже.
1. Как с помощью данной функции мне перемножить 1000 матриц 5х5 и 2000 матриц 7х7, или одну 1003х1003?
Алгоритм не универсален, чтобы его применять нужно заранее знать размер матрицы. А если его знать заранее, и в функции прямо указать n - нормальный компилятор сам прекрасно развернет цикл без вашего участия.
2. Если уж лезть дебри, то в проце сравнение целого числа с нулем происходит значительно быстрее сравнения двух целых чисел, поэтому переворачиваем циклы.
3. Если заговорили о многоядерности, тогда бы уж упомянули о варианте разрезания сверхбольших матриц на полоски, и скармливании их разным тредам.
Алгоритм не универсален, чтобы его применять нужно заранее знать размер матрицы. А если его знать заранее, и в функции прямо указать n - нормальный компилятор сам прекрасно развернет цикл без вашего участия.
2. Если уж лезть дебри, то в проце сравнение целого числа с нулем происходит значительно быстрее сравнения двух целых чисел, поэтому переворачиваем циклы.
3. Если заговорили о многоядерности, тогда бы уж упомянули о варианте разрезания сверхбольших матриц на полоски, и скармливании их разным тредам.
1) как видите не развернул, т.к. ускорение получилось более чем в 10 раз
2) да, я думаю такими подобными хитростями можно еще процентов 5-10 выиграть
3) ну я написал:
В дальнейшем конечно правильно будет с помощью multithread или mpi распараллелить программу и получить прирост еще в 1.8-1.9 раза.
2) да, я думаю такими подобными хитростями можно еще процентов 5-10 выиграть
3) ну я написал:
В дальнейшем конечно правильно будет с помощью multithread или mpi распараллелить программу и получить прирост еще в 1.8-1.9 раза.
1) Не развернул, потому, что в коде не была заранее известна размерность, а если бы вы написали for(i=5999;i>0;i--){...} и компилили с соответсвующими настройками компилятора - должен развернуть.
2) может даже и меньше чем 5%, зато это ничего не стоит кодеру и не сказывается на читабельности кода.
3) На скольки ядерном камушке? А если матрица целочисленная, и под рукой видяшка Nvidia со 256 потоковыми процессорами? Если уж решать абстрактную задачу, то почему бы не пофантазировать;)
2) может даже и меньше чем 5%, зато это ничего не стоит кодеру и не сказывается на читабельности кода.
3) На скольки ядерном камушке? А если матрица целочисленная, и под рукой видяшка Nvidia со 256 потоковыми процессорами? Если уж решать абстрактную задачу, то почему бы не пофантазировать;)
а динамическое программирование уже не подходит для данной задачи?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Перемножаем матрицы быстро или простая оптимизация программ