OSDev

для всех
Текущее время: 19 ноя 2017, 15:05

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Арифметический сдвиг
СообщениеДобавлено: 26 май 2016, 16:14 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 938
Откуда: Дагоба
Все разработчики ОС знают, что существуют операции сдвига: логические и арифметические. Назначений у логических сдвигов много, их рассматривать не буду. Но вот задался я вопросом: зачем нужен арифметический сдвиг?
Вопрос отнюдь не простой, попробуем рассмотреть ситуацию. Если мы сдвигаем влево, то арифметический сдвиг ничем не отличается от логического. При сдвиге вправо при нулевом бите знака также нет отличий. Единственная ситуация, где возникает отличие – это сдвиг вправо при единичном бите знака, в таком случае он размножается, сохраняя знак всего числа. Очевидный ответ на вопрос о необходимости такого сдвига – это деление числа со знаком на степени двойки, однако...
Если мы сдвигаем числа, кратные той степени двойки, на которую делим, то нет проблем (для простоты рассмотрим просто деление на два). Так, -4/2 должно быть -2. Проверим (на нибблах для простоты). Для деления на два нужно сдвинуть на один разряд. Было -4 = 1100, стало -2 = 1110. Всё сходится. Теперь поделим -3/2. И здесь возникают первые неприятности. Очевидно, -3 на 2 не делится, необходимо округлять. В какую сторону? У математиков принято так называемое "евклидово деление". При делении числа A на B должны получить частное Q и остаток R. Для всех видов деления результат должен удовлетворять следующему тождеству: A = B*Q+R. В данном случае при делении мы не рассматривали остаток, он виртуален – математически присутствует, но нигде не сохраняется. Однако при различении, куда надо округлять частное, важно рассматривать остаток. Итак, евклидово деление. При нём постулируется, что независимо от знаков делителя и делимого остаток всегда положителен (тривиальности про размер модуля остатка опустим). Что мы должны иметь при делении -3/2? Если мы сочтём, что результат должен быть -1, то остаток равен A-B*Q или -3-2*(-1) = -1. То есть, это не евклидово деление. Правильный результат должен быть -2! То есть, при делении отрицательного числа на положительное для евклидова деления надо округлять в сторону минус бесконечности. Посмотрим, что у нас со сдвигом. -3 = 1101. После сдвига 1110 = -2. Ура, всё сходится? Давайте проверим.
Код:
#include <stdio.h>

int main (void) {
  printf ("%d %d\n", -3/2, -3%2);
}

-1 -1
Оба-на! Выходит, язык С подразумевает не евклидово деление? А какое тогда? Как мы видим из приведённых соотношений, тип деления целиком зависит от знака остатка. Евклидово - это всегда положительный остаток. Маленько поправив код выше узнаём, что знак остатка в С совпадает со знаком делимого. А что другие языки? Оказывается, из сотни языков программирования евклидово деление принято только в 8 языках: ABAP, Algol 68, Dart, Maple, Pascal, Scheme R6RS, Stata и Z3 theorem prover. Более того, даже в математических пакетах Matlab, R, Scheme деление неевклидово! Семь языков толком не определились, в 42 остаток имеет знак делителя и в 67 знак делимого (сумма больше ста т.к. некоторые языки имеют более одного оператора). То есть, почти весь компьютерный код (и даже некоторые математические пакеты) делят неевклидово, и из них большинство придерживается соглашения, принятого в С! Получается, арифметический сдвиг, давая теоретически правильный результат, практически бесполезен? Давайте посмотрим, какой код генерируют компиляторы. Скомпилируем функцию

Код:
int fun (int a) {
  return a/64;
}


Опуская загрузку аргумента в регистр EAX получим следующее.
MS Visual Studio:
Код:
        cdq
        and     edx, 63
        add     eax, edx
        sar     eax, 6

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

Intel Parallel Studio:
Код:
        mov     ecx, eax
        sar     eax, 5
        shr     eax, 26
        add     eax, ecx
        sar     eax, 6

Прелестно! Пять инструкций, вместо одного аж три сдвига и одно сложение!

GCC:
Код:
        lea     edx, [eax+63]
        test    eax, eax
        cmovs   eax, edx
        sar     eax, 6

Ситуация как и в студии, только бит-хак выглядит по-другому.

Итак, выходит, что сам по себе арифметический сдвиг для деления на 2 почти бесполезен. И действительно, ведь при помощи сходных бит-хаков арифметический сдвиг можно эмулировать логическим сдвигом:
Код:
        cdq
        shr     eax, 6
        and     edx, 0FC000000h
        or      eax, edx

Деление же выглядит не сильно сложней.

Для красоты картины покажу, как делит Clang, этот перл достойно повесить на "доску позорачёта":
Код:
        mov     ecx, 64
        mov     [ebp-4], eax
        mov     eax, [ebp-4]
        cdq
        idiv    ecx

Мало того, что он пренебрёг любыми сдвигами, так он даже не стал оптимизировать деление на константу (специалисты знают, что вместо деления на константу лучше умножать на другую константу). Он просто поделил в лоб тяжеловесной инструкцией idiv! К тому же сгенерировал двойную зеркальную пересылку данных – зачем?? Вот вам и хвалёная оптимизация LLVM.

Ну и что мы имеем в итоге? Почти во всех процессорах есть инструкция арифметического сдвига, она довольно просто реализуется аппаратно. Практика показывает, что для реального деления она подходит плохо, фактически, незначительно отличаясь от реализации на логическом сдвиге. А некоторые компиляторы (не будем показывать пальцем), вообще пренебрегают ей для деления. Поэтому возвращаемся к исходно поставленному вопросу: зачем процессоры реализуют арифметический сдвиг? Лично я вижу две возможные причины:
1. Дань традиции и архитекторы не задумываются над связью инструкции с алгоритмом, где она будет использоваться. Логичней было бы, например, сделать специализированную готовую инструкцию деления целого числа со знаком на степень двойки. Возможно даже менять поведение "евклидово/неевклидово" этой инструкции, управляя флагами или используя их для коррекции результата (с приоритетом неевклидового деления).
2. Существует какое-то иное неизвестное мне применение, более часто используемое, чем традиционное деление на степень двойки. Если да, то какое?

Прошу высказать ваше мнение.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Арифметический сдвиг
СообщениеДобавлено: 26 май 2016, 20:27 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1056
Как много текста, ели осилил.

Ради совместимости ошибки приходится сохранять.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Арифметический сдвиг
СообщениеДобавлено: 27 май 2016, 00:14 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1314
Откуда: Зеленоград
1. Если деление сдвигом не соответствует правилам "обычной" математики, это не значит, что оно принципиально неправильно и ни на что не годится -- просто этот факт надо учитывать в случаях, когда он важен. Но он может и не играть роли (например, если деление используется лишь для разбиения некоего диапазона на два более мелких примерно равного размера -- для двоичного поиска с отрицательными числами и т.п.).

2. Арифметический и логический сдвиги влево различаются -- но не самим результатом, а состоянием флагов процессора: арифметический сдвиг даст переполнение, если был выдвинут хотя бы один бит, чьё значение не совпадает со значением знакового разряда, а логический переполнения не даёт.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Арифметический сдвиг
СообщениеДобавлено: 27 май 2016, 02:21 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 938
Откуда: Дагоба
SII писал(а):
1. Если деление сдвигом не соответствует правилам "обычной" математики, это не значит, что оно принципиально неправильно и ни на что не годится

Вот я и хотел понять, на что оно годится.

SII писал(а):
Но он может и не играть роли (например, если деление используется лишь для разбиения некоего диапазона на два более мелких примерно равного размера -- для двоичного поиска с отрицательными числами и т.п.).

Возможно, при ассемблерном кодировании так и есть. Но на ассемблере почти никто не пишет, а компиляторы не сильно выигрывают от наличия арифметического сдвига.

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

Они не могут различаться, у них опкоды одинаковые. Да и переполнение фиксируется только для однобитных сдвигов и только при сдвигах влево. Меня же больше интересует правый сдвиг, а инструкция SAR, как указано в мануале, всегда сбрасывает флаг переполнения при однобитном сдвиге, а при многобитном вообще не трогает. Да и дело тут не именно в процессорах Intel, с ними всё как раз понятно - это вопрос жёсткой совместимости начиная с 8086. Но инструкция арифметического сдвига вправо в неизменной реализации присутствует практически везде: DEC Alpha, ARM, NS32x32, MIPS, SPARC, Motorola 680x0, да вообще весь спектр вычислительных систем от примитивных микроконтроллеров Atmel AVR до монстроидальной IBM zArchitecture. Получается, что архитекторы процессоров несколько бездумно копируют распространённую инструкцию. Или я чего-то не понимаю?

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Арифметический сдвиг
СообщениеДобавлено: 27 май 2016, 14:35 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1314
Откуда: Зеленоград
Yoda писал(а):
Возможно, при ассемблерном кодировании так и есть. Но на ассемблере почти никто не пишет, а компиляторы не сильно выигрывают от наличия арифметического сдвига.


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

SII писал(а):
Они не могут различаться, у них опкоды одинаковые


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

SII писал(а):
Да и переполнение фиксируется только для однобитных сдвигов и только при сдвигах влево


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

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

Цитата:
Меня же больше интересует правый сдвиг, а инструкция SAR, как указано в мануале, всегда сбрасывает флаг переполнения при однобитном сдвиге, а при многобитном вообще не трогает. Да и дело тут не именно в процессорах Intel, с ними всё как раз понятно - это вопрос жёсткой совместимости начиная с 8086. Но инструкция арифметического сдвига вправо в неизменной реализации присутствует практически везде: DEC Alpha, ARM, NS32x32, MIPS, SPARC, Motorola 680x0, да вообще весь спектр вычислительных систем от примитивных микроконтроллеров Atmel AVR до монстроидальной IBM zArchitecture. Получается, что архитекторы процессоров несколько бездумно копируют распространённую инструкцию. Или я чего-то не понимаю?


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Арифметический сдвиг
СообщениеДобавлено: 28 май 2016, 00:24 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 938
Откуда: Дагоба
SII писал(а):
Например, в IBMовских мэйнфреймах коды операций разные

OK, я полагал, речь идёт об интелах.

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

Правильный подход.

SII писал(а):
(ну, не считая циклического сдвига, конечно, но он -- отдельная песня).

Кстати, я всё больше склоняюсь к мысли, что в современных реалиях циклический сдвиг - излишество. Не возникает такого ощущения?

SII писал(а):
И кстати о флаге переполнения. В означенных мэйнфреймах, помимо обычных масок прерываний, доступных только для системы (прерывания программные, ввода-вывода и т.п.), есть так называемая маска программы -- в ней любая программа (а не только ОС) может разрешить/запретить прерывания по конкретным событиям, связанным с выполнением кода. Одним из таких событий и является переполнение. Таким образом, если нужен контроль переполнения в арифметике, достаточно разрешить соответствующее прерывание, никаких лишних команд условных переходов после каждой команды, потенциально способной вызвать переполнение, не требуется. Простой, удобный и надёжный механизм.

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

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Арифметический сдвиг
СообщениеДобавлено: 28 май 2016, 14:05 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1314
Откуда: Зеленоград
Цитата:
Кстати, я всё больше склоняюсь к мысли, что в современных реалиях циклический сдвиг - излишество. Не возникает такого ощущения?


Нет, я на АРМах им время от времени пользуюсь. Нечасто, но бывает нужен. Ну а учитывая крайнюю простоту реализации, отказываться от этих команд смысла не вижу.

Кстати, в АРМах он через задницу сделан. Официально имеется лишь сдвиг вправо, а влево используется команда ADC (сложение с переносом). Естественно, эти сдвиги на 1 бит, в отличие от остальных, которые могут иметь произвольную длину, что весьма и весьма неудобно. Так что я бы предпочёл иметь оба сдвига в нормальном виде, а ещё лучше -- 4 сдвига (с проходом через флаг переноса и без оного, сразу со старшего на младший или наоборот).

Цитата:
Вот тут я как раз полагаю, что это не очень удачный механизм, т.к. затрудняет тонкую настройку (здесь контролируем переполнение, а здесь нет) и создание разделяемых библиотек. Я думаю, что интеловский подход с однобайтовой инструкцией INTO - более грамотное решение (хоть в чём-то интел оказался хорош:)


1) Тонкая настройка -- без всякого труда: где надо, устанавливаешь флаг, где не надо -- сбрасываешь. Это ж делает код самой программы, а не ОС, т.е. никаких потерь времени на смену контекста и т.п.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Арифметический сдвиг
СообщениеДобавлено: 29 май 2016, 01:36 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 938
Откуда: Дагоба
SII писал(а):
Цитата:
Кстати, я всё больше склоняюсь к мысли, что в современных реалиях циклический сдвиг - излишество. Не возникает такого ощущения?

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

Нельзя ли припомнить, зачем именно требовались циклические сдвиги?
У меня вот какие соображения на эту тему. Что касается однобитных сдвигов через перенос, их основное предназначение - увеличение разрядности. Это действительно необходимо на малоразрядных процессорах. Но в 64-битных процессорах нужды в этом уже нет. Однобитные циклические сдвиги без переноса нужны крайне редко и при этом элементарно реализуются на логических сдвигах. Если рассматривать многобитные сдвиги, то через перенос - вообще непонятна сфера применения. А если без переноса, то результат сдвигов обычно расслаивается масками на младшую и старшую части, но в таком случае он также эквивалентно заменяется на логические сдвиги примерно с тем же количеством инструкций. В общем, так и непонятно, есть ли конкретная большая группа алгоритмов, где желательны именно циклические сдвиги.
Что касается "раз просто сделать, то пусть будет до кучи". Если инструкция на практике не нужна, то это будет молчащий силикон и неэффективно занятое кодовое пространство. В этом плане использование инструкции ADC - очень удачное решение.

SII писал(а):
1) Тонкая настройка -- без всякого труда: где надо, устанавливаешь флаг, где не надо -- сбрасываешь. Это ж делает код самой программы, а не ОС, т.е. никаких потерь времени на смену контекста и т.п.

Это понятно. Проблема в том, что скомпилированный код, как правило, забывает контролировать флаги и такую ситуацию очень трудно отследить. Другая проблема в том, что библиотечная функция может установить флаги для себя и забыть вернуть их обратно, подложив мину замедленного действия в вызывающий код. Это совершенно реальная ситуация и мы долго искали ошибку в ПО (иногда непредсказуемо вылетало), а потом выяснилось, что виновата компонента DirectX. Она забывала возвращать флаги сопроцессора в прежнее состояние (в интелах ведь тоже точно такая же схема с флагами).
Что касается раздувания кода - грамотное сохранение, установка и возврат флагов, полагаю, требуют не меньше ресурсов.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Арифметический сдвиг
СообщениеДобавлено: 29 май 2016, 02:07 

Зарегистрирован: 26 мар 2012, 17:32
Сообщения: 208
Yoda писал(а):
В общем, так и непонятно, есть ли конкретная большая группа алгоритмов, где желательны именно циклические сдвиги.
Криптографические функции, очевидно же. Цитата в тему:
Цитата:
Secondly, another difference favoring Bitcoin mining on AMD GPUs instead of Nvidia's is that the mining algorithm is based on SHA-256, which makes heavy use of the 32-bit integer right rotate operation. This operation can be implemented as a single hardware instruction on AMD GPUs (BIT_ALIGN_INT), but requires three separate hardware instructions to be emulated on Nvidia GPUs (2 shifts + 1 add). This alone gives AMD another 1.7x performance advantage (~1900 instructions instead of ~3250 to execute the SHA-256 compression function).

Combined together, these 2 factors make AMD GPUs overall 3x-5x faster when mining Bitcoins.


Yoda писал(а):
Другая проблема в том, что библиотечная функция может установить флаги для себя и забыть вернуть их обратно, подложив мину замедленного действия в вызывающий код.
Казалось бы, такие вещи чётко прописываются в спецификации ABI.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Арифметический сдвиг
СообщениеДобавлено: 29 май 2016, 03:47 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 938
Откуда: Дагоба
Nable писал(а):
Криптографические функции, очевидно же.

Да вот не очевидно. Именно с SHA-256 дела не имел, большинство же крутых шифров основано на сетях Фейстеля, подстановочно-перестановочных сетях или суровой математике (RSA, эллиптические кривые). Все эти категории не пользуются циклическими битовыми сдвигами.

Nable писал(а):
Цитата в тему:...

О! Значит мне не одному так кажется, - такой гигант как NVidia тоже считает, что циклические сдвиги устарели!

Nable писал(а):
Yoda писал(а):
Другая проблема в том, что библиотечная функция может установить флаги для себя и забыть вернуть их обратно, подложив мину замедленного действия в вызывающий код.
Казалось бы, такие вещи чётко прописываются в спецификации ABI.

Может и прописывают, но как видно, их даже Майкрософт забывает, что уж про остальных говорить. А с проверкой по коду такая ситуация просто исключена.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB