Почему в современных процессорах нет инструкции `nand`?

Почему разработчики x86 (или другие архитектуры ЦП) решили не включать его? Это логический элемент, который можно использовать для создания других логических элементов, поэтому он быстр как одна инструкция. Вместо цепочки notи andинструкций (оба созданы из nand), почему нет nandинструкции?

http://www.ibm.com/support/knowledgecenter/ssw_aix_61/com.ibm.aix.alangref/idalangref_nand_nd_instrs.htm : POWER имеет NAND.

Но, как правило, современные процессоры построены так, чтобы соответствовать автоматической генерации кода компиляторами, и побитовый NAND очень редко требуется. Побитовое И и ИЛИ чаще используются для манипулирования битовыми полями в структурах данных. На самом деле, в SSE есть AND-NOT, но нет NAND.

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

Стоимость таких функций АЛУ составляет

1) логика, выполняющая саму функцию

2) селектор, который выбирает этот результат функции вместо других из всех функций АЛУ

3) стоимость наличия этой опции в наборе команд (и отсутствие какой-либо другой полезной функции)

Я согласен с вами, что 1) стоимость очень мала. Однако стоимость 2) и 3) практически не зависит от функции. Я думаю, что в этом случае 3) стоимость (биты, занятые в инструкции) были причиной отсутствия этой конкретной инструкции. Биты в инструкции - очень скудный ресурс для разработчика процессора / архитектуры.

Переверните его - сначала посмотрите, почему Nand был популярен в разработке аппаратной логики - у него есть несколько полезных свойств. Затем спросите, применяются ли эти свойства в инструкции процессора ...

TL / DR - нет, поэтому нет недостатка в использовании вместо них «И», «Или» или «Нет».

Самым большим преимуществом для проводной логики Nand была скорость, полученная за счет уменьшения количества логических уровней (ступеней транзистора) между входами и выходами схемы. В CPU тактовая частота определяется скоростью гораздо более сложных операций, таких как сложение, поэтому ускорение операции AND не позволит вам увеличить тактовую частоту.

И количество раз, когда вам нужно объединить другие инструкции, исчезающе мало - достаточно, чтобы Нанд действительно не заработал свое место в наборе инструкций.

Я хотел бы согласиться с Брайаном здесь, и Wouter и pjc50.

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

Рассмотрим X86: AND(это операция «и»), вероятно, очень быстрая. То же самое и для NOT. Давайте посмотрим на небольшую разборку:

Введите код:

#include <immintrin.h>
#include <stdint.h>

__m512i nand512(__m512i a, __m512i b){return ~(a&b);}
__m256i nand256(__m256i a, __m256i b){return ~(a&b);}
__m128i nand128(__m128i a, __m128i b){return ~(a&b);}
uint64_t nand64(uint64_t a, uint64_t b){return ~(a&b);}
uint32_t nand32(uint32_t a, uint32_t b){return ~(a&b);}
uint16_t nand16(uint16_t a, uint16_t b){return ~(a&b);}
uint8_t nand8(uint8_t a, uint8_t b){return ~(a&b);}

Команда произвести сборку:

gcc -O3 -c -S  -mavx512f test.c

Выходная сборка (укороченная):

    .file   "test.c"
nand512:
.LFB4591:
    .cfi_startproc
    vpandq  %zmm1, %zmm0, %zmm0
    vpternlogd  $0xFF, %zmm1, %zmm1, %zmm1
    vpxorq  %zmm1, %zmm0, %zmm0
    ret
    .cfi_endproc
nand256:
.LFB4592:
    .cfi_startproc
    vpand   %ymm1, %ymm0, %ymm0
    vpcmpeqd    %ymm1, %ymm1, %ymm1
    vpxor   %ymm1, %ymm0, %ymm0
    ret
    .cfi_endproc
nand128:
.LFB4593:
    .cfi_startproc
    vpand   %xmm1, %xmm0, %xmm0
    vpcmpeqd    %xmm1, %xmm1, %xmm1
    vpxor   %xmm1, %xmm0, %xmm0
    ret
    .cfi_endproc
nand64:
.LFB4594:
    .cfi_startproc
    movq    %rdi, %rax
    andq    %rsi, %rax
    notq    %rax
    ret
    .cfi_endproc
nand32:
.LFB4595:
    .cfi_startproc
    movl    %edi, %eax
    andl    %esi, %eax
    notl    %eax
    ret
    .cfi_endproc
nand16:
.LFB4596:
    .cfi_startproc
    andl    %esi, %edi
    movl    %edi, %eax
    notl    %eax
    ret
    .cfi_endproc
nand8:
.LFB4597:
    .cfi_startproc
    andl    %esi, %edi
    movl    %edi, %eax
    notl    %eax
    ret
    .cfi_endproc

Как вы можете видеть, для типов данных размером менее 64 все просто обрабатывается как long (отсюда и l, а не l ), так как это, как кажется, «родная» битовая пропускная способность моего компилятора.

Тот факт, что между ними есть movs, объясняется только тем фактом, что eaxэто регистр, содержащий возвращаемое значение функции. Обычно вы просто рассчитываете в ediрегистре общего назначения, чтобы рассчитать результат.

Для 64 битов это то же самое - только с "четырьмя" (следовательно, конечными q) словами и rax/ rsiвместо eax/ edi.

Похоже, что для 128-битных операндов и больше Intel не задумывался о реализации операции «не»; вместо этого компилятор создает 1регистр « все регистры» (самосравнение регистра с самим собой, результат, сохраненный в регистре с vdcmpeqdинструкцией), и получает его xor.

Вкратце: реализуя сложную операцию с несколькими элементарными инструкциями, вы не обязательно замедляете операцию - просто нет преимущества иметь одну инструкцию, которая выполняет работу с несколькими инструкциями, если она не быстрее.

Во-первых, не путайте побитовые и логические операции.

Побитовые операции обычно используются для установки / очистки / переключения / проверки битов в битовых полях. Ни одна из этих операций не требует nand («и не», также известный как «немного ясный» более полезен).

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

NAND часто не реализуется напрямую, потому что наличие инструкции AND неявно дает вам возможность перейти в состояние NAND.

Выполнение логической операции в CPU часто устанавливает биты в регистре флага.

Большинство регистров флагов имеют флаг ZERO. Флаг нуля устанавливается, если результат логической операции равен нулю, и очищается в противном случае.

Большинство современных процессоров имеют команду перехода, которая переходит, если установлен нулевой флаг. У них также есть istruction, который прыгает, если нулевой флаг не установлен.

И и NAND являются дополнениями. Если результат операции AND равен нулю, то результат операции NAND равен 1, и наоборот.

Поэтому, если вы хотите не переходить, если NAND из двух значений имеет значение true, просто выполните операцию AND и перейдите, если установлен нулевой флаг.

Поэтому, если вы хотите не переходить, если NAND из двух значений имеет значение false, просто выполните операцию AND, и переходите, если нулевой флаг сброшен.

То, что что-то дешево , не означает, что оно рентабельно .

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

Или сравните его с финансовыми инструментами: вы бы купили облигацию на 1 доллар с доходностью 0,01% только потому, что можете? Нет, вы предпочитаете экономить эти доллары, пока у вас не будет достаточно, чтобы купить облигацию за 10 долларов с лучшей доходностью. То же самое относится и к силиконовому бюджету на ЦП: это эффективно, чтобы уменьшить количество дешевых, но бесполезных операций, таких как NAND, и сделать сохраненные транзисторы более дорогими, но действительно полезными.

Нет такой расы, чтобы иметь как можно больше операций. Поскольку RISC vs CISC доказали то, что Тьюринг знал с самого начала: меньше значит больше. На самом деле лучше иметь как можно меньше операций.

На аппаратном уровне ни nand, ни no - это элементарная логическая операция. В зависимости от технологии (или от того, что вы произвольно называете 1 и что вы называете 0), nand или no могут быть реализованы очень простым, элементарным способом.

Если мы игнорируем случай «ни», вся другая логика строится из nand. Но не потому, что есть какое-то компьютерное доказательство, доказывающее, что все логические операции могут быть созданы из - и причина в том, что просто нет какого-либо элементарного метода для создания xor, или, и т. Д., Который лучше, чем создание его из nand.

Для компьютерных инструкций ситуация иная. Может быть реализована инструкция nand, и она будет немного дешевле, чем, например, реализация xor. Но только малость, потому что логика, которая вычисляет результат, крошечная по сравнению с логикой, которая декодирует инструкцию, перемещает операнды, проверяет, что вычисляется только одна операция, и получает результат и доставляет его в нужное место. Для выполнения каждой инструкции требуется один цикл, аналогично сложению, которое в десять раз сложнее с точки зрения логики. Экономия nand против xor будет незначительной.

Затем учитывается, сколько инструкций необходимо для операций , которые фактически выполняются типичным кодом . Нанд находится далеко не на вершине списка часто запрашиваемых операций. Гораздо более распространено, что и, или, не требуется. Разработчики процессоров и наборов команд изучат множество существующего кода и определят, как различные инструкции будут влиять на этот код. Скорее всего, они обнаружили, что добавление команды nand приведет к очень небольшому сокращению числа инструкций процессора, выполняемых для выполнения типичного кода, а замена некоторых существующих команд на nand увеличит количество выполняемых инструкций.

Тот факт, что NAND (или NOR) может реализовывать все логические элементы в комбинационной логике, не превращается в эффективный побитовый оператор таким же образом. Чтобы реализовать AND с использованием только операций NAND, где c = a AND b, вам нужно иметь c = a NAND b, затем b = -1, затем c = c NAND b (для NOT). Основными побитовыми логическими операциями являются AND, OR, EOR, NOT, NAND и NEOR. Это не много, чтобы покрыть, и первые четыре, как правило, встроены в любом случае. В комбинационной логике основные логические схемы ограничены только количеством доступных ворот, что является совершенно другой игрой в мяч. Количество возможных взаимосвязей в программируемом массиве гейтов, которое звучит так, как вам нужно, действительно будет очень большим числом. Некоторые процессоры действительно имеют встроенные массивы гейтов.

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

NAND, NOR и XNOR очень редко нужны. Помимо классических побитовых операторов AND, OR и XOR, только ANDN ( ~a & b) - который не является NAND ( ~(a & b)) - будет иметь практическую полезность. Если таковые имеются, ЦП должен реализовать это (и действительно, некоторые ЦП действительно реализуют ANDN).

Для объяснения практической полезности ANDN представьте, что у вас есть битовая маска, которая использует много битов, но вас интересуют только некоторые из них, а именно:

enum my_flags {
    IT_IS_FRIDAY = 1,
    ...
    IT_IS_WARM = 8,
    ...
    THE_SUN_SHINES = 64,
    ...
};

Обычно вы хотите проверить свои биты в битовой маске

1. Они все установлены
2. Хотя бы один установлен
3. По крайней мере, один не установлен
4. Ни один не установлен

Давайте начнем с того, что соберем ваши биты интереса:

#define BITS_OF_INTEREST (IT_IS_FRIDAY | IT_IS_WARM | THE_SUN_SHINES)

1. Все интересующие вас биты установлены: побитовое ANDN + логическое NOT

Допустим, вы хотите знать, все ли ваши биты интересов установлены. Вы можете видеть это как (my_bitmask & IT_IS_FRIDAY) && (my_bitmask & IT_IS_WARM) && (my_bitmask & THE_SUN_SHINES). Однако, как правило, вы свернули бы это в

unsigned int life_is_beautiful = !(~my_bitmask & BITS_OF_INTEREST);

2. Установлен хотя бы один интересующий бит: побитовое И

Теперь давайте скажем, что вы хотите знать, установлен ли хотя бы один интерес. Вы можете видеть это как (my_bitmask & IT_IS_FRIDAY) || (my_bitmask & IT_IS_WARM) || (my_bitmask & THE_SUN_SHINES). Однако, как правило, вы свернули бы это в

unsigned int life_is_not_bad = my_bitmask & BITS_OF_INTEREST;

3. По крайней мере , один бит интереса не установлен: побитовое ANDN

Теперь предположим, что вы хотите знать, если хотя бы один бит интереса не установлен. Вы можете видеть это как !(my_bitmask & IT_IS_FRIDAY) || !(my_bitmask & IT_IS_WARM) || !(my_bitmask & THE_SUN_SHINES). Однако, как правило, вы свернули бы это в

unsigned int life_is_imperfect = ~my_bitmask & BITS_OF_INTEREST;

4. Бит интереса не установлен: побитовое И + логическое НЕ

Теперь предположим, что вы хотите знать, не установлены ли все интересующие вас биты . Вы можете видеть это как !(my_bitmask & IT_IS_FRIDAY) && !(my_bitmask & IT_IS_WARM) && !(my_bitmask & THE_SUN_SHINES). Однако, как правило, вы свернули бы это в

unsigned int life_is_horrible = !(my_bitmask & BITS_OF_INTEREST);

Это обычные операции, выполняемые над битовой маской, плюс классическое побитовое ИЛИ и XOR. Я думаю , однако , что язык (который не является центральным процессором ) должен включать в себя побитовое NAND, NOR и операторы XNOR (символы которых были бы ~&, ~|а ~^), несмотря на редко. Я бы не стал включать оператор ANDN в язык, так как он не коммутативный ( a ANDN bне то же самое, что b ANDN a) - лучше писать ~a & bвместо a ANDN b, первый показывает более четко асимметрию операции.