Форум программистов, компьютерный форум, киберфорум
Наши страницы
Assembler: Linux
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.70/10: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
#1

Программирование SIMD библиотек на Fasm в x86-64 Linux

23.08.2012, 22:09. Просмотров 1856. Ответов 19
Метки нет (Все метки)

Начал недавно проект по разработке SIMD бибилиотек для С++ на Fasm под 64-bit Linux.
Интересно услышать мнение матерых программеров как о самом проекте, так и качестве кода.
Вот вебсайт, где можно качнуть исходники и посмотреть документацию, которая уже есть.

Сайт проекта на sourceforge.net
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2012, 22:09
Ответы с готовыми решениями:

Fasm + linux + ide
Господа! В данный момент приходится кодить на fasm под Linux (Debian). Хотелось...

Вывод числа: Linux и FASM
Решил поупражняться в ассемблере, и (наверное, почти как и все) столкнулся с...

Программирование на языке Assembler в FASM
Программирование на языке Assembler в FASM автор pas взято здесь Введение...

Как собрать wine под Linux x86-64 ?
Подскажите, пожалуйста... как собрать wine для 64-битного линукса? Я пробую на...

Подключение библиотек [Linux]
Вообщем избитая тема, но что то я не догоняю, ситуация такая: в pro файл...

19
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
03.09.2012, 08:39 #2
Строки тоже можно на SSE обрабатывать
1) Для вычисления длины попробуй pcmpeqb->pmovmskb->bsf, но это только для однобайтовых кодировок
2) Для сравнения строк либо pxor либо экзотическая pcmpestri
3) Потом здесь
Assembler
1
2
add             ptr, bytes            ; ptr++
add             target, bytes         ; target++
можно использовать один регистр для адресации и сэкономить одну инструкцию.

Теперь Math
1) Могу ошибаться, но кажется rol ax,8 быстрее чем xchg al,ah
2) Вариант для SIGN_INT
Assembler
1
2
3
4
5
mov   flag1,tmp
test  tmp,tmp
setnz flag2
sar   flag1
or    flag1,flag2
3) ABS_INT. Если negative - это непосредственный операнд, который принимает значения 0 и 1, тогда можно избавиться от if-else
Assembler
1
2
3
4
5
mov  temp, value
xor  value, negative shl (bytes*8-1)
sar  value, bytes*8-1
xor  temp, value
sub  temp, value
0
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
03.09.2012, 13:06  [ТС] #3
>Строки тоже можно на SSE обрабатывать
Это была первая мысль, которая мне пришла, когда я писал тот модуль. К сожалению это не получится из за их внутреннего представления.
У строки гранулярность 1, 2, 4 байта. При том признак конца строки находится в самой строке. Если нам нужно найти конец вот в такой строке 'a','b','c',0 (длина 3 символа)
То нам нужно чтобы проверить символ конца, обрабатывать ее блоками по 16 байт. Если мы загрузим весь блок (16 байт), то вместе со строкой, в регистр попадут соседние байты памяти.
Если они за пределами адресного пространства процесса, то мы вылетим по Segmentation Fault. Строки и ее куски ведь необязаны быть выровнены на границу 16 байт. Мы ведь можем и подстроку в строке искать с произвольной позиции.
Так что можем попробовать читать и за пределами памяти процесса. И тут придет северный пушной зверь.
Вариант второй. Перед сравнением строк, попытаться заранее узнать их длины. Тогда можно будет знать, что читать можно большим куском и мы не залезем в соседние байты, или за пределы адресного пространства.
Но чтобы это узнать, нужно сначала пройтись по строке и найти символ ее конца, а значит опять последовательное чтение и снова проблема что наш блок может хапнуть соседние за строкой байты и выйти за адресное пространсво процесса.
Снова та же дилема. Поэтому приходится читать поэлементно, проверяя, а не кончилась ли строка, вместо того чтобы смотреть ее большими блоками.
Если заранее как-то знать не заглядывая в саму строку ее длниу, то sse операции над строкой - то что надо. К сожалению это подойдет только для массивов символов, где их длина известна заранее.
А так рискуем или затереть соседние данные или выйти за пределы адресного пространсва процесса. Вот такой вот облом меня постиг, но идея твоя хорошая и правильная.

>1) Для вычисления длины попробуй pcmpeqb->pmovmskb->bsf, но это только для однобайтовых кодировок
Не только для них. Есть еще для 2 байтных PCMPEQW и 4 байтых PCMPEQD и т.д. К сожалению они тут не помогут, из-за тех сложностей, что я написал выше.
Если есть идеи, как это обойти: читать большими блоками и не тереть соседние данные и не выйти за пределы памяти процесса, тут я готов просто руки целовать, тому кто знает как это можно хитро сделать, не сваливаясь в поэлементный просмотр строки на предмет, где ее конец.
>2) Для сравнения строк либо pxor либо экзотическая pcmpestri
Тут все та же проблема, не знаем где кончилась строка и не начали ли мы уже сравнивать данные за строкой. Т.е. нужно сначала внутри вектора найти конец строки и понять после какого элемента мусор. Ну и не поймать бы Segmentation fault, если читаем вместе с последними байтами и кусок адресов за пределами памяти.

>3) Потом здесь
Замечание правильное. Мы можем съэкономить одну операцию если сделам так
Assembler
1
2
3
@@:     add     index, bytes
        mov     temp, [ptr + index]
        mov     [target + index], temp
Правда за это мы расплатимся, как не парадоксально снижением скорости работы. Индексная адресация вроде этого [ptr + index] работет медленее чем простое ображение к памяти по адресу в регистре.
Этот прикол мало где упоминается в советах по оптимизации, но посуди сам. Для того чтобы посчитать адрес, нам нужно сложить два регистра, и потом прочитать по тому адресу, чтобы записать снова сложить два других регистра. И конечно сначала мы увеличиваем index. Итого 3 микросложения против 2 в моем коде.
Соблазн конечно велик сократить код на одну операцию, но на самом деле, мы увеличим вычисления на 1 операцию. Поэтому лучше не сокращать этот кусок.

>Теперь Math
>1) Могу ошибаться, но кажется rol ax,8 быстрее чем xchg al,ah
Все правильно. Быстрее. Дельное замечание. Изменил у себя в коде. В следующий релиз пойдет с rol

>2) Вариант для SIGN_INT
Спасибо что обратил внимание на эту функцию. Я там оставил кусок рудиментарного кода (писал его очень давно)
Твой вариант, тоже интересный. Скорость та же что у моего куска.
Сейчас я выкинул инструкцию обнуляющую регистр, и сравниваю напрямую с 0. Скорости это правда не прибавило. Зато код стал чище.
Assembler
1
2
3
4
5
        cmp     value, 0                    ; compare value with 0
        setg    flag1                       ; set flag1 if value > 0
        setl    flag2                       ; set flag2 if value < 0
        sub     flag1, flag2                ; return (flag1 - flag2)
        ret
>3) ABS_INT. Если negative - это непосредственный операнд, который принимает значения 0 и 1, тогда можно избавиться от if-else
negative в вычислениях не участвует. Это просто флаг который говорит макросу какую функцию генерировать: ABS или NEGABS.
Короче это просто флаг, который определяет как превратить макрос в код. Ветвлений в самом коде нет.

Вообще, я приятно удивлен, что кто-то стал внимательно изучать мой код. В основном, все махнули рукой и пошли обсуждать свои дела, ну или сраться на Linux.org.ru
То что ты, не просто его посмотрел, а даже предложил дельные улучшения, это просто супер.
Побольше бы таких программистов, которые разбираются в предметной области, а не просто пишут, а нафига ты это вообще написал, или спрашивают, как на ассемблере закодить програмку для сайта, чтобы она делала мне хорошо :-).
0
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
03.09.2012, 13:40 #4
Индексная адресация вроде этого [ptr + index] работет медленее чем простое ображение к памяти по адресу в регистре.
Ты тестировал скорость? Дело в том, что в AMD Optimization manual советуют делать именно так (смотри пункт 8.5 Pointer Arithmetic in Loops). Вроде бы адрес вычисляется в одельном ALU за один такт (может быть вычислено выражение вида [<регистр>+<регистр>*<20-3>+<константа>]). Однако инструкция будет занимать больше байт и это скажется на скорости декодирования.
0
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
03.09.2012, 13:49  [ТС] #5
У меня Pentium4, и тут эта операция работает медленее. Я это не раз тестировал. И поэтому всегда избавляюсь от сложных инструкций вычисления адреса. Особенно во внутренних циклах. Зато два независимых по данным сложения, могут быть сделаны параллельно и будут быстре чем индексная адресация.
AMD Optimization manual хорош для оптимизации под их процессоры. Его нельзя использовать как руководсвто по оптимизации общего плана. Потому что даже процессоры одного производителя, но разных поколений, будут по разному выполнять этот код. И разброс скорости тоже будет везде свой.
0
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
04.09.2012, 11:01 #6
Поэксперементировал с BIN_TO_NUM - кажется есть прирост в производительности (но не исключено, что могут быть ошибки). ИЧСХ реализация на Delphi не сильно уступает в скорости.
0
Вложения
Тип файла: rar BIN_TO_NUM.rar (10.4 Кб, 9 просмотров)
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
04.09.2012, 11:02 #7
Тестировал на Celeron 430.
0
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
05.09.2012, 10:48  [ТС] #8
>Поэксперементировал с BIN_TO_NUM - кажется есть прирост в производительности (но не исключено, что могут быть ошибки).
Очень дельное замечание. Тут это улучшение как раз и просилось. Прирост в скорости +5% на Pentium4. Кстати то же самое сделал и с OctToNum. Жаль что нет lea [rax + rsi * 16]. Тогда можно было бы и преобразование 16-ричных чисел ускорить.

Спасибо за внимание к проекту и участие в его улучшении.

>ИЧСХ реализация на Delphi не сильно уступает в скорости.
Интересно было бы еще сравнить DecToNum для floating-point numbers, с тем что есть в Delphi.
Я делал сравнения с glibc (тесты вот тут http://linasm.sourceforge.net/about/performance.php), прирост для целочисленных преобразований, тоже был не очень, а когда дошло время до floating-point, то тут glibc немного спасовал.
0
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
05.09.2012, 10:57 #9
Попробуй написать на сях и скомпилировать при помощи ICC. Особенно интересно посмотреть какой код будет сгенерирован для разных процессоров.
0
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
05.09.2012, 11:27  [ТС] #10
Не думаю что по своей интелектуальности ICC сильно обгонит тот же GCC. Без сомнения код будет быстрее для их процессоров, правда не настолько как может показаться из их рекламных проспектов.

Я просто смотрел asm выхлоп от GCC с включенной оптимизаций O2 и O3, и он меня честно не порадовал.
Куча пересылок - стек регистры, регистр - регистр. Компилятор похоже гоняет данные туда-сюда, что -то сохраняет, зачем то опять их выковыривает, хотя можно было хранить все на регистрах и не парится.

> Попробуй написать на сях и скомпилировать при помощи ICC. Особенно интересно посмотреть какой код будет сгенерирован для разных процессоров.
Честно говоря не хочется парится и писать то что уже сделано снова на С. Я на С пишу когда разрабатываю алгоритм, Когда он отлажен, то переношу в асм код (ручками с оптимизацией). Так что я на такое уже насмотрелся. Мне кажется ICC, не будет радикально умнее чем gcc. То что он сделает код компактнее и быстрее - даже не спорю. Но не на несколько порядков. Попробовать можно, но идея мне кажется сомнительной.
0
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
05.09.2012, 12:16 #11
Вот ещё один вариант BIN_TO_NUM. Всё сводится к 2 инструкциям pcmpeqb и pmovmskb. Однако для твоей задачи код нужно будет дорабатывать напильником и не факт, что получится быстрее.
http://www.cyberforum.ru/post3214375.html
0
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
05.09.2012, 19:18  [ТС] #12
Ёжки кошки. Ну там и таблицы. Идея прикольная извлекать символы блоками. Вот вопрос для размышлений.
Дано: Есть строка из 5 символов + 6-ой символ - конец строки.
"0b101"
Сразу за строкой идут еще какие-то данные в притык. Или строка стоит на границе страницы памяти, причем нулевой символ (конец строки) - это последний байт страницы. Прямо за ней, границы адресного пространства процесса.
Вопрос: Как на этот случай отреагирует блочный извлекатель строк, который смотрит сразу 8 байт? Что в этом случае произойдет? Как избежать этого?
0
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
07.09.2012, 09:44 #13
Например можно копировать во временный буффер. Ещё вариант: развернуть цикл и использовать pinsrb.

Переделал на скорую руку под SSE2 - работает с той же скоростью.

Вот этот кусок должно быть очень тормозной - сплошные зависимости
Assembler
1
2
3
mov bl,[eax]
sub bl,'0'
cmp bl,1
0
Вложения
Тип файла: rar BIN_TO_NUM_SSE2.rar (10.9 Кб, 9 просмотров)
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
07.09.2012, 11:46  [ТС] #14
Цитата Сообщение от murderer Посмотреть сообщение
mov bl,[eax]
sub bl,'0'
cmp bl,1
Правильно. Там не только зависимости по данным будут тормозить код. Значение полинома считается по схеме горнера. Это также значит что все следующие вычисления зависят от предыдущих. Так что оптимизировать там просто нечего. К тому же мы должны для каждого символа, что мы считали из строки проверить что он в пределах [0..1].

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

>Например можно копировать во временный буффер. Ещё вариант: развернуть цикл и использовать pinsrb.
Копировать во временный буфер плохая идея - потеряешь всю произодительность из-за копирования туда-сюда. Лучше за первый проход по строке определить где кончаются цифры, а потом повторно, уже зная длину числа в байтах, использовать векторный алгоритм. Так съэкономишь время на латентности памяти на запись.

Еще бы интерсно взглянуть на тот кусок, где в твоем алгоритме проверяется переполнение типа. Оно необходимо, потому что кто-то может скинуть в строку 0b100000000 (для типа char). И алгоритм без проверки переполнения даст в результате 0 и промолчит о том что было передано слишком большое число. Т.е. программа, которая считает такое число будет думать что человек, не ошибся при вводе, а ввел именно ноль. Такой случай нужно обрабатывать и как-то извещать программу, что у нас неверные данные или неправильный ввод.

Еще по поводу movaps. Руководство по оптимизации программ, очень красноречиво говорит о том, что не стоит смешивать вещественные и целочисленные SIMD инструкции, для одних и тех же данных, поскольку они выполняются на разных АЛУ процессора. И для внутреннего планировщика процессора, такое смешивание будет приводить к неправильной планировке загрузки вычислительных устройств. Как награда за это - снижение быстродействия.
Если тебе нужно загрзить сразу 16 байт целочисленных данных в регист XMM, используй MOVDQA. Она как раз для этого случая и нужна.

Вот тебе ссылка по SIMD (sse, sse2, ...) инструкциям процессора
http://linasm.sourceforge.net/docs/instructions/simd.php#data
Там сгруппированы эти инструкции по их назначению и типам данных, с которыми они работают. Это поможет тебе выбирать соответсвующие команды для векторных расширений процессора.

Если будет интересно и будет желание и время - попробуй сделать то же самое для шестнадцатеричных чисел.
0
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
07.09.2012, 12:53 #15
Переполнение можно проверить при помощи bsr уже после конвертирования - избавимся от условного перехода в цикле.
Assembler
1
2
3
bsr temp,value
cmp temp,1 shl max_value
jae ovrfl
Добавлено через 6 минут
Лучше за первый проход по строке определить где кончаются цифры, а потом повторно, уже зная длину числа в байтах, использовать векторный алгоритм.
Не могу придумать как это сделать.

Добавлено через 15 минут
Что-то я напутал скорее так
Assembler
1
2
3
4
5
bsr ecx,value
mov eax,1
shl eax,cl 
cmp eax,max_value
jae ovrfl
0
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
07.09.2012, 12:57  [ТС] #16
Ну это достаточно тривальная задача. Вот набросок на С

C
1
2
3
4
5
6
7
8
9
10
11
12
13
// Сначала пропускаем префикс "ob"
// Теперь string указавыает на начало, где идут цифры
 
// Потом определяем кол-во цифр в строке
char *ptr = string;
char symbol;
while (symbol = ptr[0] - '0', symbol <= 1)
{
    ptr++;
}
 
// Теперь мы знаем кол-во цифр в строке
size_t digits = ptr - string;
На ассемблере будет не сложнее. Но писать не охота. Идея думаю и так понятна.
0
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
07.09.2012, 13:13 #17
Проблема в том, что длина строки ничего не даёт IMHO.

Добавлено через 2 минуты
Как загрузить в xmm-регистр данные, размером меньше 16 байт? Видимо только через временный буффер.
0
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
07.09.2012, 13:37  [ТС] #18
Хорошо, вот тебе код похитрее

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Сначала пропускаем префикс "ob"
// Теперь string указавыает на начало, где идут цифры
 
// Теперь обрабатываем нашу строку
char symbol;
uint64_t charvector = 0;
size_t counter = 0;
while (symbol = string[0] - '0', symbol <= 1)
{
    charvector <<= 8;       // Сдвигаем наш вектор на позицию одного символа
    charvector += symbol;   // Добавляем очередной символ в вектор
    counter++;
    if (counter == 8)       // Если вектор полностью заполнен, то проводим преобразование
    {
        value += DigitsToNumber (charvector)
        charvector = 0;
        counter = 0;
    }
    string++;
}
value += DigitsToNumber (charvector)
Плюсы: Ни каких временных буферов и можно даже использовать регистры CPU (64 битные). Обрабатываем блоки произвольной длины, а не только 16 байт.
Минусы: Каждые 8 символов - сбрасывается конвеер процессора, поскольку происходит неправильно предсказанный переход.
0
murderer
3318 / 1465 / 133
Регистрация: 06.10.2010
Сообщений: 3,217
07.09.2012, 14:16 #19
Это получится даже медленнее чем через память.

Добавлено через 4 минуты
Кажется переконвертировать число в 16-ричную систему можно очень быстро через VPSHUFB.
0
Jack Black
0 / 0 / 0
Регистрация: 23.08.2012
Сообщений: 10
07.09.2012, 14:40  [ТС] #20
Цитата Сообщение от murderer Посмотреть сообщение
Это получится даже медленнее чем через память.
Это утверждение стоит проверить. Ибо обращение в память на запись будет медленее чем запись в регистр. Латентность памяти на запись выше чем на чтение, там нужны совсем другие напряжения и токи подать на ячейки, плюс физически процесс зарядки конденсатора идет медленее чем его разрядка. Поэтому в процессор и встраивают кеши различных уровней, чтобы сгладить медленную работу памяти.

Допустим даже что процессор не вытолкнет твой временный буффер для символов в память, а будет хранить в кеше. Скорость работы кеша, даже первого уровня тоже меньше скорости работы регистров. Так что вопрос что быстрее: записать во временный буфер или регистр, даже не стоит.

Кроме того если твой код будет работать только со строками кратными 16 символов. И не сможет обработать строку где к примеру всего 3 символа, то это существенно огриничит его применение.
В первую очередь при програмировании должна быть выполнена главная задача: Написанный код должен решать поставленную перед ним задачу. На втором месте идет скорость и на третьем - переносимость. Поскольку переносимость нам не нужна. То стоит сосредоточится на первых 2. Сначала, правильный алгоритм, потом оптимизация его по скорости выполнения.

Добавлено через 9 минут
Вот небольшие данные по латентности памяти. Данные немного староваты, но хорошо отражают стоимость записи в память и регистр.

Finally, we should at least give an impression of the costs associated with cache hits and misses. These are the numbers Intel lists for a Pentium M:
Assembler
1
2
3
4
5
6
To Where    | Cycles
============+=============
Register    | 1
L1          | 3
L2          | 14
Main Memory | 240
Добавлено через 4 минуты
Если интересно откуда взяты эти данные, то есть хорошая книга на английском языке по оптимизации программ работающих с памятью.
www.akkadia.org/drepper/cpumemory.pdf
0
07.09.2012, 14:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2012, 14:40

интеграция библиотек Qt в eclipse (Linux)
Помогите подключить Qt библиотеки к IDE eclipse. Операционка Ubuntu 11.10

Перенос разделяемых библиотек на другой ПК Linux
Доброго времени суток. Решил попробовать перенести приложение с одного Linux...

компилирование/установка библиотек под Linux
Здравствуйте! Столкнулся с проблемой: скачал с сайта разработчика пакет...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru