Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Обойти математический сопроцессор


Автор: liliputochka 21.12.2010, 10:46
Добрый день,
  у меня программа, написанна на С, выполняет простые математические операции с плавающей точкой с помощью математического сопроцессора. Нужно реализовать эти же операции, но так чтобы математический сопроцессор в вычислениях не участвовал. Пробовала перевести числа в формат с фиксированной точкой. К сожалению, функции выполняющие перевод тоже используют математический сопроцессор.
 Подскажите что делать?

Автор: Akina 21.12.2010, 11:22
Взять библиотеку эмуляции сопроцессора из какого-нить древнего языка и выдрать оттуда нужные функции...
А какой смысл НЕ использовать сопр?

Автор: liliputochka 21.12.2010, 13:22
Есть такое мнение, что работа с числами с плавающей точкой занимает больше тактов работы процессора, чем с числами с фиксированной точкой. Надо это мнение проверить.
Не подскажете библиотеку эмуляции сопроцессора? И какой язык можно взять для поиска этой библиотеки?

Автор: W4FhLF 21.12.2010, 15:07
Если вы работаете на обычных современных процессорах, то это мнение просто бред.

Автор: Severyanin 21.12.2010, 16:14
Нет, это не совсем бред. По-идее, так оно и есть. Просто я не вижу смысла в такой оптимизации на современных процессорах. Опишите задачу, пожалуйста. Наверняка есть более простое и логичное ее решение

Автор: liliputochka 21.12.2010, 20:20
Задача проста:
 дана функция, ее надо оптимизировать. При профилировке было замечано, что код использующий математические операции с плавающей точкой работает особенно медленно. Соответсвтвенно было решено оптимизировать эти выражения. Код был заменен на ассемблерный аналог, но выигрыша во времени это не дало. Вот теперь оптимизация добралась до перевода чисел в формат фиксированной точки (8.24).

Автор: maxim1000 21.12.2010, 20:28
если уж дошло до деталей настолько близких к конкретному процессору, то, возможно, есть смысл почитать его сравнительные скорости различных операций на нём

если рассматривать абстрактный процессор, боюсь, на таком уровне оптимизации уже бессмысленны

Автор: liliputochka 21.12.2010, 20:42
Как узнать какой у меня процесссор?

Автор: Pavia 21.12.2010, 20:57
liliputochka, 
Тогда вопрос о компетентности ассемблерной оптимизации встаёт ребром.

CPU_Z возьми и посмотри. 
А когда будешь оптимизировать используй CPUID .

Что оптимизировали? Какую задачу решали? 

Какая операция самая медленная?

Какие оптимизационные методики использовали? Алгоритм уже оптимизирован? Надеюсь что код уже рассчитан на неравномерный доступ к памяти? Число обращений к памяти уменьшено? А парализация данных уже задействована?  

Автор: W4FhLF 21.12.2010, 22:34
Цитата(liliputochka @  21.12.2010,  20:20 Найти цитируемый пост)
При профилировке было замечано, что код использующий математические операции с плавающей точкой работает особенно медленно.


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

Автор: liliputochka 22.12.2010, 10:40
Первоначальная функция:
Код

Void SinGen_S_gen_t_sin(ALG_Handle h, float frame[restrict], int size)
{
    SinGen_S_Obj * gen = (Void *)h;

    Uint32 phase, aphase;
    Uint32 reg, kv, sig;
    float S, C, St, Ct, d, cosd, d1, a=0.5, one=1.0, kk=K;
    Uint32 K1;
    Uint32 step;

    reg=  gen->reg;
    step= gen->step;

//    #pragma MUST_ITERATE (1, 256)

    while(size--)
    {        
        sig= (Uint32)((Int32)(reg) >> 31);
        kv= (Uint32)((Int32)(reg << 1) >> 31);

            phase = ((kv ^ (reg << 2)) >> 2) + (kv >> 31);
        aphase = phase >> (32 - 2 - lengchTbl);

        phase = _clr(phase, 32 - 2 - lengchTbl, 31);


        St= gSin_tabl[aphase];
        Ct= gSin_tabl[(1 << lengchTbl) - aphase];

        d = K * phase;

        cosd= 1. - 0.5f*d*d;


        C = Ct * cosd - St * d;
        S = St * cosd + Ct * d;


        S = SET_SIGN_F(S, sig);        // ++--
        C = SET_SIGN_F(C,  sig ^ kv);    // +--+

        S = exp2(-24) * S;
        C = exp2(-24) * C;

        *frame++ = C;
        *frame++ = S;

        reg += step; // mod 32

    }
    gen->reg= reg;
}

Код, который оптимизировали с помощью ассемблера выделен жирным шрифтом.
Ассемблерный код:
Код

        asm("finit");
        asm("flds %0"::"g"(kk));
        asm("fmul %0":"=g"(d):"g"(phase));

        asm("flds %0"::"g"(d));
        asm("fmul %0"::"g"(a));
        asm("fmul %0"::"g"(d));
        asm("fld1");
        asm("fsubrp");
        asm("fstps %0":"=g"(cosd));
    
         asm("flds %0"::"g"(Ct));
        asm("fmul %0"::"g"(cosd));
        asm("flds %0"::"g"(St));
        asm("fmul %0"::"g"(d));
        asm("fsubp");
        asm("fstps %0":"=g"(C));
         asm("flds %0"::"g"(St));
        asm("fmul %0"::"g"(cosd));
        asm("flds %0"::"g"(Ct));
        asm("fmul %0"::"g"(d));
        asm("faddp");
        asm("fsts %0"::"g"(S));

Функция на С уже оптимизированна.

Добавлено через 6 минут и 32 секунды
Вот этот код тратил особенно много процессорного времени:
Код

        d = K * phase;
        cosd= 1. - 0.5f*d*d;
        C = Ct * cosd - St * d;
        S = St * cosd + Ct * d;

Автор: W4FhLF 22.12.2010, 13:42
Вот то о чём я и говорил.

Цитата(liliputochka @  22.12.2010,  10:40 Найти цитируемый пост)
Вот этот код тратил особенно много процессорного времени:


И чего вы хотели добиться простым переписыванием этого кода на ассемблер? Любой современный компилятор лучше вас оптимизирует код. Забудьте про ассемблер.

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

У вас тормозит НЕ этот код. А тот, что идёт перед ним:

Код

        St= gSin_tabl[aphase];  \\ <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        Ct= gSin_tabl[(1 << lengchTbl) - aphase]; \\ <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
        d = K * phase;
        cosd= 1. - 0.5f*d*d;
        C = Ct * cosd - St * d;
        S = St * cosd + Ct * d;


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

На современных процессорах любое чтение из памяти эквивалентно тысяче сложений/умножений/вычитаний. Вот и подумайте какой смысл оптимизировать арифметику если всего-лишь одно обращение к памяти съест любой прирост производительности вычислений. Вам нужно оптимизировать работу с памятью, вычислить паттерн обращений к таблице gSin_tabl и организовать доступ таким образом, чтобы был эффективно задействован кеш процессора. В идеале следует стремиться к тому, чтобы доступ был последовательным. 

Следует почитать литературу по оптимизации прежде, чем тратить время на всякую ерунду типа переписывания кода на ассемблер или обход сопроцессора. 

Автор: liliputochka 22.12.2010, 15:31
W4FhLF те строки что вы указали в качестве ресурсоемких являются массивом. На сколько я представляю, массив хранится в кеше или оперативке, доступ к которой занимает 1 такт процессорного времени. К тому же стоки, которые я указала как ресурсоемкие были выявлены эмпирически, а не профайлером. Профайлер указал саму функцию.

Автор: W4FhLF 22.12.2010, 17:00
Цитата(liliputochka @  22.12.2010,  15:31 Найти цитируемый пост)
На сколько я представляю, массив хранится в кеше или оперативке, доступ к которой занимает 1 такт процессорного времени.


Вы неправильно представляете. 

Какой у вас размер массива?

Автор: Pavia 22.12.2010, 19:13
Цитата(W4FhLF @  22.12.2010,  13:42 Найти цитируемый пост)
На современных процессорах любое чтение из памяти эквивалентно тысяче сложений/умножений/вычитаний.

1 так чтение из кэша 14 при кэш промахке+частота процессора/частоту памяти(1-5 такта). Но это не на самых последних. В самых последних видимо уже всё по другому так как частоту памяти уж практически дотянули до частоты процессора.
Умножение выполняется быстро, но не так как хочется. 

Пока в коде еще не разбирался но по первому взгляду скажу тормазят вычисления. Но от таблице лучше отказаться. Рекомендации дам чуть по позже.

Автор: Pavia 22.12.2010, 22:18
liliputochka, 
Совет простой выкинуть всё и переписать код заново. А ещё я так и не понял что он там у тебя считает. Можно математическую формулу увидеть? А то за всеми этими хитро трюками для "оптимизации" сути не видно.

Автор: VictorTsaregorodtsev 22.12.2010, 22:20
Поддерживаю - в данном сишном коде все операции простейшие. Плавучую математику современный проц выполняет почти так же быстро, как и целочисленку, поэтому в разы ускорить вычисления можно только переходом к SIMD-командам ака MMX, SSEx - но я в исходном С-коде места им не вижу.
В сишном коде увидел еще вот такую непонятку: exp2(-24) - это ведь константа, зачем её на каждом вызове функции дважды считать?

По поводу растактовки разных команд проца на разных процессорах и оптимизации кода хоть на С, хоть на асме - см. http://www.agner.org.

Ну и алгоритм может стоит переделать или компилятор поменять на оптимизирующий (сейчас, кстати, какой компилятор?)

Автор: liliputochka 23.12.2010, 09:36
Цитата(VictorTsaregorodtsev @  22.12.2010,  22:20 Найти цитируемый пост)
exp2(-24) - это ведь константа, зачем её на каждом вызове функции дважды считать?

Я использую функцию exp2(a)*a = число с фиксированной точкой. Так вроде реализую оптимизацию.

Цитата(VictorTsaregorodtsev @  22.12.2010,  22:20 Найти цитируемый пост)
сейчас, кстати, какой компилятор?

gcc 4.0

Цитата(Pavia @  22.12.2010,  22:18 Найти цитируемый пост)
Можно математическую формулу увидеть?

Постараюсь:
Код

St= gSin_tabl[aphase];
Ct= gSin_tabl[(1 << lengchTbl) - aphase];

Выбираем из массива значения табличных синусов
Код

C = Ct * cosd - St * d;
S = St * cosd + Ct * d;

cos(a+b) = cos(a)*cos(b)-sin(a)*sin(b)
sin(a+b) = sin(a)*cos(b)+cos(a)*sin(b)

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

Автор: maxim1000 23.12.2010, 10:00
а сравнивали вообще с нормальным вычисление косинуса угла?
(я имею в виду - не разбивать число, не приводить его к фиксированному виду, просто посчитать косинус)

а то не удивлюсь, если в современных процессорах есть отдельная команда для это, и переплюнуть её по скорости не так-то и просто

Автор: liliputochka 23.12.2010, 10:30
Цитата(maxim1000 @  23.12.2010,  10:00 Найти цитируемый пост)
а сравнивали вообще с нормальным вычисление косинуса угла?

Нет, не сравнивала.

Добавлено через 3 минуты и 56 секунд
Цитата(W4FhLF @  22.12.2010,  17:00 Найти цитируемый пост)
Какой у вас размер массива?

Может это подскажет:
Код

#define lengchTbl 8
Void SinGen_S_init(Void)
{
    double step= M_PI_2/(1 << lengchTbl);
    double phasa=0;
    int i;
    int b;
    
    for(i= 0; i<=((1 << lengchTbl)); i++)
    {
        b = exp2(24) * sin(phasa);
        gSin_tabl[i] = b;
        phasa += step;
    };
}

Автор: W4FhLF 23.12.2010, 11:42
Цитата(maxim1000 @  23.12.2010,  10:00 Найти цитируемый пост)
а то не удивлюсь, если в современных процессорах есть отдельная команда для это, и переплюнуть её по скорости не так-то и просто 


FSIN, FCOS, FTAN...


Цитата(liliputochka @  23.12.2010,  10:30 Найти цитируемый пост)
Может это подскажет:


8 чтоли? 
Тогда массив кеширован конечно. 

В связи с этим становится вообще непонятно чего вы хотите от вашего кода и процессора в целом. smile 

Автор: liliputochka 23.12.2010, 16:21
Цитата(W4FhLF @  23.12.2010,  11:42 Найти цитируемый пост)
чего вы хотите от вашего кода и процессора в целом

А можно попонятнее?

Автор: VictorTsaregorodtsev 23.12.2010, 22:26
Цитата(W4FhLF @  23.12.2010,  11:42 Найти цитируемый пост)
FSIN, FCOS
 и даже fsincos появился (уже почти 10 лет назад, на четвертом пне, ЕМНИП), чтобы считать сразу и синус, и косинус быстрее, чем за 2 вызова разных команд. Но, тем не менее, и эта одна команда требует нескольких десятков тактов - поэтому быстрое вычисление приближенными алгоритмами или через табличные значения остается актуальным.

Автор: W4FhLF 23.12.2010, 22:40
Цитата(VictorTsaregorodtsev @  23.12.2010,  22:26 Найти цитируемый пост)
поэтому быстрое вычисление приближенными алгоритмами


Это например какие? В смысле я знаю какие есть алгоритмы в целом, но мне просто интересно соотнести точность приближённого  вычисления, чтобы оно было быстрее машинной инструкции.

Цитата(VictorTsaregorodtsev @  23.12.2010,  22:26 Найти цитируемый пост)
через табличные значения остается актуальным


Согласен. Но при условии, что паттерн доступна к таблице или размер позволяют её кешировать.

Автор: liliputochka 24.12.2010, 10:53
Извените что прерываю ваш спор, но вопрос так и остался "под вопросом".

Автор: Pavia 24.12.2010, 19:19
liliputochka, 
Ваш код  http://forum.vingrad.ru/index.php?showtopic=318431&view=findpost&p=2272153 считается за 400-1000 тактов процессора он не может тормозить.  И он считается быстрее чем в 1 посте.  Следовательно проблема в неправильном его применении.

Автор: liliputochka 24.12.2010, 20:23
Цитата(Pavia @  24.12.2010,  19:19 Найти цитируемый пост)
проблема в неправильном его применении

Подскажите хотя бы что делать? Может что-то прочесть или куда-то еще посмотреть? Я не сильна в оптимизации.

Автор: VictorTsaregorodtsev 24.12.2010, 22:33
Цитата(W4FhLF @  23.12.2010,  22:40 Найти цитируемый пост)
Это например какие? В смысле я знаю какие есть алгоритмы в целом, но мне просто интересно соотнести точность приближённого  вычисления, чтобы оно было быстрее машинной инструкции.

Может, я был не совсем точен в том посте... Если не привязываться именно к единичным машинным командам... Не знаю, как насчет синуса-косинуса, но вот для вычисления exp() приближенный алгоритм есть и работает он в разы быстрее, чем реализованная в математической библиотеке компилятора функция exp(). Точность аппроксимации была математически исследована и опубликована в научной статье 99 года, ссылку могу дать.

Автор: liliputochka 25.12.2010, 10:22
Цитата(VictorTsaregorodtsev @  24.12.2010,  22:33 Найти цитируемый пост)
ссылку могу дать

Давайте

Автор: VictorTsaregorodtsev 27.12.2010, 17:47
liliputochka написал в личку

Остальным: сорри, что не выдаю ссылку на всеобщее обозрение - но алгоритм вошёл в разряд ноу-хау, благодаря которым мои программы работают в 10-20-... раз быстрее чужих и позволяют обучать нейросети на десятках гигабайт данных. Конкурентное преимущество, как никак ;) Девушке ссылку дал, остальные пусть предлагают мне что-нибудь интересное взамен ;)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)