Russian Qt Forum

Есть алгоритм, считает корреляционные моменты. Если кратко, то представляет собой:

Проблема в том, что размер vector может быть 4-5 млн., а tau от 0 до 100-200 тыс. В итоге через полчаса работы я вырубил программу. Можно ли как-то ускорить этот алгоритм до вменяемых времен расчета?

Навскидку, попробуйте в начале циклов для result сделать reserve(int size);

Краткий и банальный ответ "никак". А чисто практически

1) *(it + tau) вылазит за границы массива

2) предраспределить result. Это не решит проблему но нужно для 3

3) очевидно распараллелить. С OpenMP дело сводится к добавлению одной строки

4) Если такие расчеты неизбежны - нужно делать их адаптивно и отображать в UI - напр через каждые 1000 точек. Еще лучше считать не подряд, а "решеткой". При наличии обновляемого графика юзверь занят наблюдением и время для него течет куда быстрее. Хороший способ "превратить отходы в доходы"

Действительно, *(it + tau) вылазит за границы массива.

1. Распараллелить, OpenMP как нельзя к месту.

2. Использовать SIMD инструкции современных процессоров.

Если допустимо, double заменить на float, - это даст ускорение в два раза. Если допустимо, перейти к арифметике с фиксированной точкой на int16, - это даст ускорение еще в два раза (относительно float).

С-либы для работы с SIMD - Intel IPP/MKL, у AMD - свои. Можно и на асме/интринсиках сделать, тем более, что алгоритм простой.

Чтобы вам лучше представить, что даст SIMD для вашей задачи, приведу пример: AVX инструкция DPPS оперирует 2-мя исходными 256-битными операндами (например, в каждом по 8 float'ов) и производит попарное умножение, т.е. за раз получается 8 вот таких результатов (правда без сложения, но это мелочь):

Ввиду того, что АЛУ конвейеризовано, и имеется несколько исполнительных портов, то будет еще ускорение при последовательном исполнении однотипных инструкций (с независимыми операндами), например, упомянутая выше одна dpps занимает 12 тактов, а две - только 14. Ваш алгоритм хорош для этой возможности.

3. GPGPU (OpenCL, CUDA, ...). Ввиду того, что объем данных большой, возможно, будет лучше SIMD. Но здесь я не специалист, пока.

Моя практика этого не подтверждает, скорость остается примерно одинаковой. Возможно Вы имели ввиду "меньше объем данных для чтения".

В первый раз слышу о такой - хранить флоты 16 бит (half) да, но об арифметике мне ничего не известно. Сообщите что/откуда. Спасибо

Имею эту радость в одном из проектов. Да, прирост скорости впечатляет. Но Вы забыли о др стороне медали - никто не обещал наличие AVХ на целевой машине. Там может быть по минимуму SSE3 а может и вообще ничего (хоть и редко). В результате приходится иметь 4 либы (для всех вариантов) и притыкивать их при старте. Не смертельно, но кол-во забот нарастает (особенно c учетом кросс-платформ)

Вы занимаетесь 3d и никогда не слышали про арифметику с фиксированной запятой?  Впечатляет. Для реалтайма в далекие времена использовали его во все поля.
http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%BE_%D1%81_%D1%84%D0%B8%D0%BA%D1%81%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%B9_%D0%B7%D0%B0%D0%BF%D1%8F%D1%82%D0%BE%D0%B9

Но врядли это здесь поможет, только если использовать 64битные числа для хранения.

Ускорение за счет большего количества опреандов на регистр. Кол-во операндов обратно пропорционально размеру операнда. т.е. 4 double = 8 float. 

Да, так и есть. Например, AVX начинается только с SandyBridge. Упомянутые либы от Intel имеют набор всех реализаций и выбирают оптимальный в рантайме.

Выглядит как-то наивно - что я сохраню в 16 битах, по 1 цифре на целую/дробную?  :) А хоть бы и 64 - как тогда их складывать, "эмулировать" что ли  ???

Если уж разговор от том "кто чего слышал" - то вот есть формат 4 байта на точку (32-бита), который хранит RGB как 3 float значения (может быть напр тысячи, миллионы). Довольно популярен. Ну как он называется - можете и не знать, а вот как он хранит - догадаетесь?  :)

Уже больше 10 лет ассемблером не занимался (к сожалению). И продолжаю по старинке думать что регистры FPU 64-битные. Команда загрузки float из памяти в регистр сама  конвертирует  в double и наоборот. Или это уже не так? Спасибо

Хммм... сомневаюсь. Я использую embree от того же Intel и ничего она не выбирает - под что откомпилил - то и будет. На всякий случай спросил у авторов - да, компилите под каждый набор. А если "выбирает" то интересно как она это делает. Напр
Переменные должны быть обычными float или блоками по 4 float или даже по 8. И инструкции сложения тоже разные. И что, откомпилятся все варианты и в runtime код прыгнет на нужную ветку?  Хорошо бы конечно, но слабо верится, более реалистично есть какая-то директива указывающая компилятору под что делать код, ну или переменная окружения. Но "все в одном" так не выходит.

http://habrahabr.ru/post/131171/

Что имеется ввиду: каждая компонента может хранить число от 0 и до "тысячи, миллионы"?

Регистры FPU 80-битные и соответствуют типу long double. У SIMD расширений свое АЛУ (и свои регистры, за исключением MMX, которое использует регистры сопроцессора), к сопроцессору не имеющее никакого отношения.

Выбор в рантайме делается так:
- имеются реализации под все наборы инструкций в виде отдельных ДЛЛ;
- в рантайме на основании инструкции CPUID определяется набор поддерживаемых инструкций, ну и выбирается максимально функциональная (загружается соответствующая ДЛЛ).
Интерфейсные функции едины, просто внутри идет диспетчеризация в конкретную реализацию.

Не думаю что сами Вы дочитали эту тягомотину до конца :) Да и к Вашей предыдущей ссылке это никакого отношения не имеет.

Да

По ходу дела заметим что прямолинейная попытка обрезать float (ну просто возьмем меньше бит на х-ку и мантиссу) ничего хорошего не приносит, half делает хитрее. Да, ну и все варианты скорость не повышают, а наоборот

С этим я никак не спорю, т.к. сам делаю так же. Но я могу подгрузить достаточно большую/представительную единицу (напр ф-цию, класс), свободно писать арифметику и надеяться что "в runtime разберутся" возможности нет. Поэтому для задачи ТС все равно придется заводить неск компилируемых вариантов (что впрочем не смертельно)

Конечно нет, я стараюсь не читаю хабр. Но это ваш уровень, там элементарные вещи на пальцах. Я бы порекомендовал faq фидо-эхи demo.design, но боюсь что для вас это будет сложновато. Судя по перлу ниже... :)

Да вы что правда? Вы и читать уже не умеете? Или это сложная тема для вас? Брысь учить арифметику и не позориться. :)

Old, Вы пожалуйста дома так разговаривайте со своим котом, а здесь ведите себя прилично и не кичитесь тем что Вы считаете "знаниями".

Мне не нужно читать такие сомнительные (мягко говоря) статьи, т.к. эти вещи мне известны еще по моей первой работе. Помню не работала команда "сложение без нормализации" - ну починил, правда долго сидел. Хотел я или нет - пришлось запомнить как равняются мантиссы. А тут какой-то сынок расписывает "с пятого на десятое". А другой дурачок, прочитавший это, возомнил себя умным и знающим, дает советы направо и налево. Право, несерьезно  :) 

Это лучше рассказывать благодарной публике, которая будет верить этой лапше. Пока все говорит об обратном. :)

Зря вы так про Akon, он предложил эту арифметику как вариант, который имеет право на жизнь. ;)
И да, не все дурочки, которые знают больше вас, скорее наоборот. :)

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

Вы правда до сих пор не понимаете разницу между цифрами и числами? Вы не знаете, что можно хранить в 16 битах? По какой одной цифре, о чем вы говорите?

Я вам хотел сначала привести ссылку на википедию, что бы вы наконец узнали, что же можно хранить в 16 битах, но решил, что такие простые вещи вы должны знать. Но нет, видно я ошибся.
Почитайте: http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BB%D1%8B%D0%B9_%D1%82%D0%B8%D0%BF и не позорьтесь.

А если будет интерес узнать, что же это за арифметика, то пишите, я вам постараюсь на пальцах рассказать, а то "труды из интернета" для вас сложноваты. ;)
На самом деле там все просто и при некоторых условиях точность 64 битного числа с фиксированной запятой будет выше double. Хотя в повседневной работе эта арифметика скорее всего будет не нужна, точности double хватает, особенно для 3d.
Расцвет фиксированной точки был во времена, когда математический сопроцессор был отдельной дорогой микросхемой и ставился не во все машины. А использовать софтовые библиотеки для расчетов плавающей арифметики в реалтайме было невозможно из-за производительности тех компьютеров.  

ОФФТОПИК:

Парни, призываю к конструктивному подходу! Время - деньги. А "переход на личности" в любых ипостасях - это обычный прием демагогов, пользы от которого - ровно нуль.

АНТИОФФТОПИК:

Предлагаю сперва концептуально обозначить решения, а потом уже копать дальше. Методы которые мне видятся:

1) Уменьшение количества повторений в цикле за счет изменения алгоритма (если возможно)
2) Минимизация обращений к памяти, оптимизация использование процессорного кэша
3) Выбор команд просчета с меньшим количеством процессорных тактов на одно вычисление
4) Выбор команд просчета с пакетным способом вычислений (несколько обсчетов блочно)
5) Использование возможностей GPU
6) Распараллеливание вычислений

Дополняйте.

ИМХО, безусловно, все виды оптимизации скомбинировать не всегда получится (например распараллеливание и использование GPU может вообще ничего не дать, по сравнению с одно-поточным использованием GPU). Естественно, заманчиво использовать оптимизацию комплексно.

В таком ключе побеседуем?  ;)

Дык нужен топикстартер. :)
Интересно сколько же в среднем по времени происходит расчет и на сколько ему хотелось бы его ускорить.
Самое простое, это распараллелить вычисления (руками или с использованием того же OpenMP). Больше ядер - меньше время.
Но я бы сразу смотрел на OpenCL/CUDA. Сейчас видеокарты дешевая масштабируемая мощя. :)

Есть простое выражение "в одном байте можно сохранить 2 шестнадцатиричные (или десятичные) цифры", и это никак не противоречит др утверждению - 256 возможных значений. Так что ничего безграмотного я не сказал. Да и вообще - зачем тратить свое время на док-во типа "смотрите, он этого не знает!!!!!" ?  Даже если это Вам удастся (предположим) Вы от этого ничего не выиграете, а только потеряете.

Согласен  :)

Да наверное ни в каком пока не обозначена "цена вопроса". У меня впечатление что ТС ожидал чего-то простого/бытового, а здесь этого нет. Тот же OpenMP - да, одна строка, но ведь либу тащить и не на одной платформе, изучать опции компилятора и.т.п. Др варианты имеют свои минусы и также требуют времени. Конечно все это решаемо, но имеет смысл если ТС хочет (или условия позволяют) делать это ощутимой работой.

Вообще насколько целочисленная арифметика обгоняет флоты? Я когда-то создавал такую тему, мой простой тест показал что всего в полтора раза. Один человек проверял, вроде у него в 2 раза (тоже не бог весть что). Учитывая что работать с float куда приятнее...

Про это тока краем уха слышал - в теме про обсчеты хэшей (майнинг биткоинов) :) , но совершенно не представляю, кто занимается балансом загруки GPUs, ОС или энд-программер.


Если честно, без понятия. Лично мои увлечения asm закончились еще до появления пентиумов )