Ошибка внутри: крошечный шанс огромной ошибки на Pentium

Исходное сообщение Тима Коу от 28 ноября:

Группы новостей: comp.sys.intel

От кого: [email protected] (Тим Коу)

Тема: Re: Вопиющая ошибка FDIV в Pentium!

Отправитель: [email protected] (Тим Коу)

Организация: Vitesse Semiconductor

Дата: пн, 28 ноября 1994 г., 06:33:42 по Гринвичу

Строки: 548

В конце этого сообщения есть модель C аппаратного делителя Pentium, которая точно предсказала многие из заявленных ошибочных делений и точно подтверждает все известные мне ошибочные деления.

Я работал над аппаратным FPU IEEE с 1989 по 1991 год. Как разработчик FPU я, естественно, интересуюсь алгоритмами аппаратной арифметики. В настоящее время я работаю над чем-то совершенно другим, но иногда я все еще поддерживаю связанные задачи разработки.

Я увидел первое сообщение об ошибке Pentium FDIV в comp.sys.intel. Когда я увидел пост Андреаса Грусса (включенный), я увидел шаблон и возможность полностью реконструировать делитель Intel. Я взялся за эту задачу с большим рвением, так как очень редко можно увидеть детали чужого передового дизайна.

Я решил опубликовать свои результаты, когда мне показалось, что Intel не полностью раскрывает характеристики ошибки. Лучшая характеристика и единственная характеристика ошибки, исходящей от Intel, — это ее вероятность 1 из 9 миллиардов случайных операндов. Худшая характеристика ошибки заключается в том, что конкретные операнды, подвергающиеся наибольшему риску, представляют собой целые числа ± очень маленькие дельты. Целые числа 3, 9, 15, 21 и 27 за вычетом очень маленьких дельт являются делителями риска. (В частности, максимально выразимая одинарная точность, двойная точность и числа расширенной точности, меньшие 3, 9…27, серьезно подвержены риску делителей.) Другая плохая характеристика этой ошибки, о которой я не слышал от Intel, заключается в том, что в худшем случае ошибка, вызванная ошибкой, была значительно больше, чем ошибка 4 частей на миллиард, наблюдаемая профессором Найсли.

Мне показалось, что Intel пыталась свести к минимуму свою уязвимость, сосредоточив внимание на вероятности ошибки 1 из 9 миллиардов, о которой она сообщила, и на ошибке 4 частей на миллиард, наблюдаемой профессором

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

Я думаю, что Intel проделала выдающуюся техническую работу. В конце концов, единственная причина, по которой я читал comp.sys.intel, заключалась в том, что я рассматривал возможность покупки системы P90.

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

Я опубликовал дополнительную программу, не включенную сюда, которая сканировала операнды с одинарной точностью на наличие ошибок, превышающих один младший значащий бит одинарной точности. Я получил обратно список из 1738 проблемных делений одинарной точности (из 64 триллионов). Херб Сэвидж предоставил список.

Следующие делители и их двоичные масштабы (под этим я подразумеваю различия только в двоичном показателе степени) объясняют ›95% ошибок деления:

3,0 › делитель ›= 3,0–36*(2^-22)

9,0 › делитель ›= 9,0–36*(2^-20)

15,0 ›делитель ›= 15,0–36*(2^-20)

21,0 › делитель ›= 21,0–36*(2^-19)

27,0 › делитель ›= 27,0–36*(2^-19)

Деление с делителем в одном из указанных выше диапазонов имеет примерно 1 шанс из 200 000 привести к потере точности в операциях с двойной расширенной точностью.

Остальные ‹5% ошибок деления можно учесть, изменив указанное выше число 36 на 2048.

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

дивиденд = интдивиденд + дельтадивиденд

or

дивиденд = интдивиденд — дельтадивиденд

divisor = intdivisor — deltadivisor

intdivisor = 3, 9, 15, 21, 27

и должно выполняться одно из следующих условий, которое зависит от показателя степени в представлении IEEE рассматриваемого дивиденда:

intdividend = intdivisor/3 mod intdivisor

intdividend = 2*intdivisor/3 mod intdivisor

Ограничения на приведенные выше дельта-дивиденд и дельта-делитель несколько сложны, подробности о которых оставлены читателю в качестве упражнения. ;-) Подробно ограничения я не прорабатывал.

Вот предыдущие сообщения для comp.sys.intel. Читайте и наслаждайтесь.

-Тим Коу [email protected]

— Текст первого и второго сообщения — На ПК Packard Bell P90 я выполнил следующее

расчет с помощью Microsoft Windows Desk Calculator:

(4195835 / 3145727) * 3145727 [опечатка исправлена ​​из предыдущих сообщений]

Результат: 4195579.

Это представляет собой ошибку 256 или одну часть из ~16 000.

[email protected] (Андреас Кайзер) пишет

›Обычно деление верное (чего вы ожидали?). Всего несколько

›операнды разделены неправильно. Мои результаты (P90) с ~25 000 000 000

›случайные аргументы (в пределах 1..2⁴⁶), с четными результатами, разделенными на два

›до нечетного, чтобы обеспечить уникальные шаблоны мантиссы (двоичный показатель степени

›все равно, конечно).

>

> 3221224323

> 12884897291

> 206158356633

> 824633702441

> 1443107810341

> 6597069619549

> 9895574626641

> 13194134824767

> 13194134826115

> 13194134827143

> 13194134827457

> 13194138356107

> 13194139238995

> 26388269649885

> 26388269650425

> 26388269651561

> 26388276711601

> 26388276712811

> 52776539295213

> 52776539301125

> 52776539301653

> 52776539307823

> 52776553426399

>

› Грусс, Андреас

>

> — — — — — — — — — —

› — Андреас Кайзер — Интернет: [email protected]

› — — — — — — — — — — фидонет: 2:246/8506.9

Анализ этих чисел показывает, что все они, кроме двух, имеют следующий вид:

3*(2^(K+30)) — 1149*(2^(K-(2*J))) — delta*(2^(K-(2*J)))

где J и K – целые числа, большие или равные 0, а дельта – действительное число, которое имеет различные диапазоны в зависимости от J, но обычно может принимать значения от 0 до 1.

Слагаемые 2*J в приведенном выше уравнении позволяют сделать вывод, что делитель Pentium является итеративным делителем, вычисляющим 2 бита частного за такт. (Это согласуется с указанными 39 циклами на расширенное длинное деление из книги данных Pentium. Техническое название для этого типа делителя - основание 4)

Чрезвычайно низкая вероятность ошибки (1 из 10¹⁰) означает, что оставшаяся часть хранится в формате сохранения при переносе. (Формат сохранения переноса — это когда число представлено в виде суммы двух чисел. Этот формат позволяет выполнять следующее вычисление остатка без распространения переносов. Причина, по которой формат сохранения переноса подразумевается вероятностью ошибки, заключается в том, что это очень сложно, но не невозможно. для создания длинных совпадающих последовательностей единиц как в слове суммы, так и в переносимом слове.)

Я предположил, что набор цифр равен -2, -1, 0, 1 и 2. (Наличие 5 возможных цифр в делителе по основанию 4 обеспечивает необходимую погрешность при выборе следующей цифры. система счисления 10 и 10 возможных цифр не допускают ошибок.)

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

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

Анализ точных ошибочных результатов, возвращаемых при неправильном делении, показывает, что бит (или биты) вычитается из остатка в самом старшем бите или рядом с ним.

Моделирование этого процесса включено в программу.

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

Определение частного из последовательности цифр оставляем читателю в качестве упражнения ;-).

Я хотел бы поблагодарить доктора Найсли за предоставленное окно в архитектуру Pentium.

— Третье сообщение — С тех пор я выполнял следующие расчеты в Microsoft

Калькулятор Windows Desk Calculator на компьютере Pentium со следующим

результаты:

(41.999999/35.9999999)*35.9999999–41.999999 ==> (-0.75)*(2^-13)

(48.999999/41.9999999)*41.9999999–48.999999 ==> (-1.0)*(2^-13)

(55.999999/47.9999999)*47.9999999–55.999999 ==> (-1.0)*(2^-13)

(62.999999/53.9999999)*53.9999999–62.999999 ==> (-1.0)*(2^-13)

(54.999999/59.9999999)*59.9999999–54.999999 ==> (-1.0)*(2^-13)

(5244795/3932159)*3932159–5244795 ==> (-1.0)*(2⁸)

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

Я также выполнил следующие расчеты, которые НЕ дали ошибочных результатов:

(38.499999/32.9999999)*32.9999999–38.499999 ==> 0

(45.499999/38.9999999)*38.9999999–45.499999 ==> 0

Я с большим интересом слежу за этой темой. Одно заблуждение, которое необходимо устранить, состоит в том, что это проблема расширенной точности. Эта ошибка затрагивает от 50 до 2000 пар делителей одинарной точности (из общего числа в 64 триллиона). Еще одно заблуждение связано с величиной относительной ошибки. Я бы предложил следующую таблицу вероятностей получения следующих относительных ошибок при выполнении случайного деления с двойной повышенной точностью:

relerror = (correct_result — Pentium_result)/correct_result

Диапазон ошибок | Вероятность

— 1e-4 ‹ повторная ошибка | 0

1e-5 ‹ повторная ошибка ‹ 1e-4 | 0.3e-11

1e-6 ‹ повторная ошибка ‹ 1e-5 | 0.6e-11

1e-7 ‹ повторная ошибка ‹ 1e-6 | 0.6e-11

1e-8 ‹ повторная ошибка ‹ 1e-7 | 0.6e-11

.

.

1e-18 ‹ повторная ошибка ‹ 1e-17 | 0.6e-11

1e-19 ‹ повторная ошибка ‹ 1e-18 | 0.6e-11

Изучение приведенных выше ошибок деления показывает, что и делимое, и делитель являются целыми числами за вычетом небольших дельт. Также примечательно, что индуцированная ошибка составляет примерно дельта ^ (2/3). Целые числа в делителях фактически ограничены перечисленными и их двоичными масштабами. Целые числа в дивидендах могут быть выбраны гораздо более свободно. Этот тип пары делимых делителей на самом деле встречается довольно часто при прямом интегрировании траекторий вне метастабильных точек. Это связано с тем, что метастабильные точки в системах часто имеют некоторые точно интегральные характеристики, и по мере отклонения пути от метастабильной точки эти характеристики медленно расходятся от своих интегральных значений. Если алгоритм прямого интегрирования разделит эти характеристики, и они окажутся, например, 7 и 3, он не сработает.

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

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

800bf6 bffffc

a00ef6 effffc

a808d2 8fffe

e00bd2 bfffe

a7ffd2 8fffe

c3ffd2 a7ffe

dfffd2 bfffe

fbffd2 d7ffe

f9ffdc7 efffe

b9feab7-b9feabf 8fff

b9ffab0e-b9ffab7f 8fffc

-следующая двойная расширенная пара не удалась 3 раза!!!

c3ffd2eb0d2eb0d2 a7ffe

e00bd229315 bfffe

9fffef5–9ffeffeffffff4

9ffff21–9ffff3f effff8

9ffff4d-9ffff7f effffc

f008e35-f008e3f 8ffff4

f008e6d-f008e7f 8ffff6

f008ea1-f008ebf 8ffff8

f008ed9-f008eff 8ffffa

f008f0d-f008f3f 8ffffc

f008f45-f008f7f 8ffffe

f008f7e 8ffffff1

f0023e 8fffff8

effff0d 8ffffc

a808d1b-a808d3f 8fffe

a808d67-a808d7f 8fffe4

a808db3-a808dbf 8fffe8

a808dff 8fffec

Пример запуска программы (с использованием первой обнаруженной ошибки):

— -Введите мантисса делимого в шестнадцатеричном формате: 8

— -Введите делитель мантисса в шестнадцатеричном формате: bffffffb829

— -следующая цифра 1

— -1111000000000000000000000001000111110101101111111111111111111100

— -0000000000000000000000000000000000000000000000000000000000000100

— -11110000000000000000000000010001 номер итерации 1

— -.

— -.

— -.

— -следующая цифра -1

— -0011111111100100101011110100110000010111010000000000000000000000

— -1101111111111111111110110110010010010000000000000000000000000000

— -00011111111001001010101010110000 номер итерации 14

— -следующая цифра 2

— - Обнаружена ошибка.

— -Введите 0 для правильного результата или 1 для неверного результата: 1

— -0000000001101101010100001000000111110110011111111111111111111100

— -1111111100100101010110100110010010010010000000000000000000000100

— -11111111100100101010101011100101 номер итерации 15

— -следующая цифра 0

— -1111110100100000001010111001010110010001111111111111111111100000

— -0000000100101010100000000000010010010000000000000000000000100000

— -11111110010010101010101110011001 номер итерации 16

— -.

— -.

— -.

-Тим Коу [email protected]

Приложение на языке C:

#include 
main()
{
unsigned r0, r1, r2, r3, r4, r5, r6, s0, s1;
unsigned t0, t1, t2, t3, cycle, f, incorrect, spup;
unsigned thr_m2_m1, thr_m1_0, thr_0_1, thr_1_2, positive, errornum;
char line[30], *linepoint;
r0 = 0x0bffffc0;
r1 = 0;
r2 = 0x0800bf60;
r3 = 0;
printf("First digit of mantissas must be between 8 and f\n");
printf("Enter dividend mantissa in hex: ");
*(line+15) = '0';
scanf("%s", line);
linepoint = line;
while (*linepoint != '\0') linepoint++;
while (linepoint < line + 15) *linepoint++ = '0';
*(line+16) = '\0';
sscanf(line+15, "%x", &spup);
spup = (spup >> 2) | (12 & (spup << 2));
*(line+15) = '\0';
sscanf(line+7, "%x", &r3);
*(line+7) = '\0';
sscanf(line, "%x", &r2);
printf("Enter divisor  mantissa in hex: ");
scanf("%s", line);
linepoint = line;
while (*linepoint != '\0') linepoint++;
while (linepoint < line + 15) *linepoint++ = '0';
*(line+15) = '\0';
sscanf(line+7, "%x", &r1);
*(line+7) = '\0';
sscanf(line, "%x", &r0);
r4 = 0;
r5 = 0;
t0 = r2;
while (!(t0 & 1)) t0 = t0 >> 1;
printf("%d\n", t0);
t0 = r0;
while (!(t0 & 1)) t0 = t0 >> 1;
printf("%d\n", t0);
    /*  These thresholds are VERY tentative. */
    /*  There may be bugs in them.           */
t0 = r0 >> 22;
    /*  Next threshold is strongly indicated */
    /*  by the failure of 1/9895574626641    */
if (t0 < 36) thr_0_1 = 3;
    /*  Next threshold is strongly indicated */
    /*  by the failure of 1/824633702441     */
else if (t0 < 48) thr_0_1 = 4;
    /*  Next threshold is strongly indicated */
    /*  by the failure of 5244795/3932159    */
else if (t0 < 60) thr_0_1 = 5;
else thr_0_1 = 6;
thr_m1_0 = 254 - thr_0_1;
if (t0 < 33) thr_1_2 = 11;
else if (t0 < 34) {
  printf("This model does not correctly handle\n");
  printf("this divisor.  The Pentium divider\n");
  printf("undoubtly handles this divisor correctly\n");
  printf("by some means that I have no evidence\n");
  printf("upon which speculate.\n");
  exit();
  }
    /*  Next threshold is strongly indicated     */
    /*  by the failure of 41.999999/35.9999999   */
else if (t0 < 36) thr_1_2 = 12;
else if (t0 < 39) thr_1_2 = 13;
    /*  Next threshold is strongly indicated     */
    /*  by the failure of 1/1443107810341 and    */
    /*  by the failure of 48.999999/41.9999999   */
else if (t0 < 42) thr_1_2 = 14;
else if (t0 < 44) thr_1_2 = 15;
    /*  Next threshold is strongly indicated     */
    /*  by the failure of 55.999999/47.9999999   */
else if (t0 < 48) thr_1_2 = 16;
    /*  Next threshold is strongly indicated     */
    /*  by the failure of 62.999999/53.9999999   */
else if (t0 < 54) thr_1_2 = 18;
    /*  Next threshold is strongly indicated     */
    /*  by the failure of 54.999999/59.9999999   */
else if (t0 < 60) thr_1_2 = 20;
else thr_1_2 = 23;
thr_m2_m1 = 254 - thr_1_2;
if (t0 == 35) errornum = 22;
else if (t0 == 41) errornum = 26;
else if (t0 == 47) errornum = 30;
else if (t0 == 53) errornum = 34;
else if (t0 == 59) errornum = 38;
else errornum = 128;
incorrect = 0;
cycle = 1;
    /*  The cycle limit would be ~34 instead of  */
    /*  18 for double extended precision.        */
while (cycle < 18) {
  t0 = 255 & ((r2 >> 24) + (r4 >> 24));
  if ((t0 > thr_m1_0) || (t0 < thr_0_1)) {
    s0 = 0;
    s1 = 0;
    positive = 0;
    printf("next digit 0\n");
    }
  else if (t0 > thr_m2_m1) {
    s0 = r0;
    s1 = r1;
    positive = 0;
    printf("next digit -1\n");
    }
  else if (t0 < thr_1_2) {
    s0 = ~r0;
    s1 = ~r1;
    positive = 4;
    printf("next digit 1\n");
    }
  else if (t0 & 128) {
    s0 = (r0 << 1) | (r1 >> 31);
    s1 = r1 << 1;
    positive = 0;
    printf("next digit -2\n");
    }
  else {
    s0 = ~((r0 << 1) | (r1 >> 31));
    s1 = ~(r1 << 1);
    positive = 4;
    printf("next digit 2\n");
    if ((t0 == errornum) && (((r2 >> 21) & 7) == 7) && (((r4 >> 21) 
      & 7) == 7)) {
      printf("A bug condition has been detected.\n");
      printf("Enter 0 for correct result or 1 for incorrect result:");
      scanf("%d", &incorrect);
      if (incorrect) {
            /* These amounts that are subtracted from the    */
            /* remainder have NOT been extensively verified. */
        if (errornum == 22) s0 = s0 - (3 << 25);
        else s0 = s0 - (4 << 25);
        }
      }
    }
  t0 = s0 ^ r2 ^ r4;
  t1 = s1 ^ r3 ^ r5;
  t2 = (s0 & r2) | (s0 & r4) | (r2 & r4);
  t3 = (s1 & r3) | (s1 & r5) | (r3 & r5);
  r2 = (t0 << 2) | (t1 >> 30);
  r3 = t1 << 2;
  r4 = (t2 << 3) | (t3 >> 29);
  r5 = (t3 << 3) | positive | (spup & 3);
  spup = spup >> 2;
  t0 = r2;
  f = 32;
  while (f--) {
    if (t0 & (1 << 31)) putchar('1');
    else putchar('0');
    t0 = t0 << 1;
    }
  t0 = r3;
  f = 32;
  while (f--) {
    if (t0 & (1 << 31)) putchar('1');
    else putchar('0');
    t0 = t0 << 1;
    }
  putchar('\n');
  t0 = r4;
  f = 32;
  while (f--) {
    if (t0 & (1 << 31)) putchar('1');
    else putchar('0');
    t0 = t0 << 1;
    }
  t0 = r5;
  f = 32;
  while (f--) {
    if (t0 & (1 << 31)) putchar('1');
    else putchar('0');
    t0 = t0 << 1;
    }
  putchar('\n');
  t0 = r2 + r4;
  f = 32;
  while (f--) {
    if (t0 & (1 << 31)) putchar('1');
    else putchar('0');
    t0 = t0 << 1;
    }
  printf(" iteration number %d\n", cycle++);
  }
}

Воан Р. Пратт

2.9991523619 декабря1994 г. Вон Р. Пратт из Стэнфордского университета разместил сообщение в группах новостей comp.arch и comp.sys.intel, в котором оспаривал оценку Intel вероятность ошибки один раз в 27 000 лет. Он предложил вполне правдоподобный сценарий, при котором баг будет воспроизводиться каждые 3 миллисекунды. Пратт также показал, что кажущаяся безобидной операция деления 4,999999/14,999999 приведет к ошибке 0,00000407 на неисправных процессорах.

«Эта ошибка максимально коварна: она настолько велика, насколько это возможно, без фактического срабатывания предупреждающих сигналов, когда люди просматривают свои столбцы данных. Таким образом, крошечные ошибки в одну стотысячную часть могут в течение длительного периода времени проникать в триллионы вычислений, выполняемых по всему миру, и нет никакого практического способа обнаружить их, кроме как провести массовый подробный аудит. тип, который должен быть адаптирован к ошибке Pentium FDIV и совершенно не нужен для надежного устройства с плавающей запятой

Исходное сообщение Вона Пратта:

От кого: [email protected] (Вон Р. Пратт)

Группы новостей: comp.arch,comp.sys.intel

Тема: Естественный сценарий с высокой вероятностью ошибки FDIV (было: В защиту Intel…)

Дата: 3 декабря 1994 г., 15:20:17 по Гринвичу

Организация: факультет компьютерных наук Стэнфордского университета.

Строки: 194

Идентификатор сообщения: ❤[email protected]›

Ссылки: ❤[email protected]› ❤[email protected]› ❤[email protected]›

Хост публикации NNTP: sunburn.stanford.edu

Внешняя ссылка: Radon.Stanford.EDU comp.arch:15209 comp.sys.intel:20065

В этом сообщении я описываю сценарий, в котором ошибки FDIV встречаются каждые три миллисекунды или около того, в отличие от сценария Intel по умолчанию, в котором они встречаются каждые 27 000 лет или около того. Кроме того, ни одна из обнаруженных ошибок не связана с неясными числами: все они принимают форму небольших «ушибленных» рациональных чисел, таких как 5/15, которые при искажении как 4,999999/14,999999 дают 0,333329 на Pentium и 0,33333329 в других местах. Кроме того, довольно много обнаруженных ошибок очень велики, как в этом примере. Мы оставляем правдоподобие нашего сценария на суд читателя; мое намерение состоит в том, чтобы это выглядело как нечто вполне возможное.

Мотивация. В статье ❤[email protected]› Джо Бак написал:

›Я действительно поражен всей этой суетой. В одном случае из девяти

›миллиард, вы получаете то, что по сути является делением одинарной точности вместо

›деление двойной точности. Подавляющее большинство пользователей Pentium никогда этого не делают

›все, что требует даже полной одинарной точности: они работают с электронными таблицами,

›пишите документы и играйте в игры. Почему Intel должна платить около 1 миллиарда

›(девять нулей) долларов, чтобы купить всем этим лузерам новый чип?

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

Исправить с точностью до одинарной точности, НЕ. Если, конечно, вы не имели в виду 16-битную длину слова; другие примеры ~16-битных ошибок уже приводились, но форма тех, которые мы приводим здесь, такие как приведенный выше 4.999999/14.999999, делает их особенно драматичными.

В этом сообщении я даю простой и правдоподобный сценарий, не связанный с теорией чисел, криптографией, дифференциальными уравнениями или обращением матриц, а просто делением на целые числа от одной до трех цифр, представленные как действительные числа, которые были слегка «ушиблены». процессом, который все мы видели много раз. В этом сценарии ошибка FDIV проявляется не раз в 27 000 лет, а примерно раз в три миллисекунды — с такой скоростью мой Pentium сталкивался с ними.

Ключевым постулатом здесь является то, что целые числа, встречающиеся в этом сценарии, были очень слегка «ушиблены» из-за другой обработки, а затем усечены по какой-либо причине (например, числа могли быть автоматически получены из десятичного калькулятора) до некоторой степени. заданное количество десятичных цифр, *точность*. Все целые числа подвергаются этой обработке единообразно для фиксированной точности. Таким образом, если точность равна, скажем, 6, а мы делим, скажем, 7 на 18, то 7 фактически равно 6,999999, а 18 равно 17,999999, то есть из обоих операндов вычитается одно и то же число, здесь 10^-6.

Существует миллион пар целых чисел i,j, где 1 ‹= i,j ‹= 1000. В следующей таблице показана функция уменьшения десятичной точности и *допуск* (насколько далеко от деления должно быть считаться неправильным ответом), сколько из миллиона возможных делений i/j являются неправильными. Для этих коэффициентов можно ожидать, что IEEE-правильные ответы будут иметь относительную ошибку лучше, чем 10 ^ -17. В приведенной ниже таблице «неправильно» определяется как имеющая относительную ошибку не менее 10^-15 для первого столбца, не менее 10^-13 для второго и т. д. распознавать меньшее количество частных как неправильные.)

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

Мой фаворит — 5/15, то есть 4,999999/14,999999, оцененный Pentium в 0,33332922, тогда как другие оценщики настаивали бы на 0,33333329 как на более справедливом ответе.

Еще один неверный случай — 7/48 (6,999999/47,999999), для которого Pentium вычисляет 0,14583204, тогда как более обоснованное предположение было бы 0,14583332.

Еще один кандидат: 9/54 (8,999999/53,999999), где Pentium делает ставку на 0,16666439 и раздраженно проигрывает до 0,16666665.

Позвольте мне подчеркнуть три основные особенности подобных примеров. Во-первых, основная арифметика выполняется с довольно маленькими целыми числами (хотя и слегка «ушибленными»), что значительно увеличивает вероятность того, что вы столкнетесь именно с этими ошибками, независимо от того, заметите ли вы их когда-либо. Во-вторых, синяки могут быть любой простой величины, например, миллионной или десятимиллионной, это не обязательно должно быть неясное количество, например 0,000000142883, что значительно увеличивает вероятность того, что синяк, возникающий в вашей ситуации, будет для вас плохим. . В-третьих, ошибка может применяться единообразно к обоим операндам FDIV, нет необходимости настраивать ошибки операндов по отдельности, что дает вам еще больше шансов столкнуться с одной из этих ошибок.

Странная особенность этих трех примеров, которую я не исследовал из-за нехватки времени и которая может иметь или не иметь единообразного объяснения, заключается в том, что в каждом случае ошибку можно приблизительно описать, сказав, что Pentium пропустил два повторяющихся символа. цифры, подчеркнутые ^^ выше. Это дает простую эвристику для имитации Pentium на этих трех примерах: вычислите 4,999999/14,999999 или что-то еще на своем карманном калькуляторе, затем удалите две повторяющиеся цифры; результат подходит для одной цифры за пределами повторяющейся строки (фактически до двух в случае 5/15).

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

Только 26 пар выживают при допуске 10^-5. Вот для записи 14 неправильных значений точности 6: 5/15, 5/30, 5/60, 5/120, 9/54, 9/108, 9/216, 9/432, 9/864, 10/60, 10/120, 10/240, 10/480 и 10/960. (7/48 отличается всего на 0,9 * 10 ^ -5, едва упуская допуск 10 ^ -5.) Для точности 5 10 плохих парней: 18/27, 20/30, 33/144, 36/108. , 40/120, 44/192, 72/432, 72/864, 80/480 и 80/960. А для точности 4 два деления — 82/96 и 120/288; в частности, 81,9999/95,9999 дает 0,854156, когда мы ожидали 0,8541665, а 119,9999/287,9999 дает 0,416656, а мы хотели 0,4166665. (Хм, здесь тоже работает правило «удалить два повтора»; очень интересно…)

Хотя мы использовали десятую систему счисления для определения точности, в ней нет ничего особенного, и любая другая система счисления должна давать аналогичные результаты, хотя и с некоторым другим набором небольших рациональных ошибочных делений. В частности, если бы мы развили тринадцать пальцев вместо десяти, соответствующая таблица, переходящая от 11 цифр к 3 цифрам при допуске 10^-9, была бы 0, 31, 211, 547, 802, 784, 417, 109, 0.

Хотя в этом сценарии ошибка FDIV выглядит, по крайней мере, в довольно плохом свете, я не утверждаю, что это что-то вроде наихудшего сценария. Двумя важными факторами для любого сценария являются скорость, с которой этот сценарий запускает ошибку FDIV, и то, как часто сущность этого сценария возникает в реальном мире. «Индекс ущерба» сценария является произведением этих двух факторов. Сценарий, в котором учитываются тысячи часов фактического времени работы Pentium, но который вызывает ошибку, скажем, каждые десять минут, вполне может иметь более высокий индекс ущерба, чем мой сценарий выше, сила которого в том, что он запускает ошибку каждые несколько миллисекунд, но чьей слабостью является неуверенность в том, насколько это вероятно на практике. Однако вы должны признать, что это не совсем неправдоподобный сценарий.

-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o

Я добавляю сюда код, который печатает приведенную выше таблицу. Для тех, кто думает, если не гармонизировать в C, это где искать точные значения «точность» и «допуск».

#include 
#include 
main(argc, argv)
  char *argv[];
{
  int i, j, cnt, digits;
  double prec, tol, ibruis, jbruis, pent, true;
  for (digits = 15, prec = 1e-15; digits > 2; digits--, prec *= 10) {
    printf("%4.d\t\t", digits);
    for (tol = 1e-15; tol < 1e-4; tol *= 100) {
      cnt = 0;
      for (i = 1; i <= 1000; i++)
        for (j = 1; j <= 1000; j++) {
          ibruis = i - prec, jbruis = j - prec;
          pent = ibruis/jbruis;
          true = (1.11*ibruis)/(1.11*jbruis);
          cnt += (fabs(pent - true) > tol*true);
        }
      printf("%4d  ", cnt);
    }
    printf("\n");
  }
}

Моя эвристика для получения истинного частного, а именно true = (1,11*ibruis)/(1,11*jbruis), представляет собой быстрый и грязный метод рандомизации операндов, достаточный для того, чтобы хотя бы немного изменить вероятность обнаружения ошибки FDIV. ближе к оценке Intel, равной одному разу в 27 000 лет. Когда я заменил 1.11 на 1.01, результаты были идентичными, что вместе с оценкой Intel казалось достаточно хорошим для программы, не предназначенной для построения самолетов.

Вон Пратт

["источник"]

11.9999103517 декабря 1994 г. IBM опубликовала «Pentium Study, IBM Memo», ставя под сомнение заявление Intel.

19.9999973251 декабря 1994 года Intel объявила о полной бесплатной замене всех неисправных процессоров Pentium на основании запроса. Эндрю Гроув принес публичные извинения. Все это дело обошлось Intel в 475 000 000 долларов, что составило более половины их прибыли, полученной в последнем квартале 1994 года.

СМИ бушевали, а публика жаждала фаталити.

Алан Эдельман

18.9999163362 сентября 1995 года Алан Эдельман опубликовал отчет, в котором дал подробный анализ ошибки.

Подробнее по теме

• Статистический анализ уязвимости с плавающей запятой: Технический документ Intel
• Возвращение к ошибке Pentium
• Сказка о двух числах
• ""Вместе мы стоим, раздельно - падаем""
• Википедия: Ошибка Pentium FDIV

P.S.

Топ-10 лозунгов Intel «от фанатов»:

• 9.9999973251 Это НЕДОСТАТОК, черт возьми, а не ошибка
• 8.9999163362 Это достаточно близко, мы так говорим
• 7.9999414610 Почти 300 правильных кодов операций
• 6.9999831538 Вам не нужно знать, что внутри
• 5.9999835137 Новый взгляд на ПК и математику
• 4.9999999021 Мы действительно это исправили
• 3.9998245917 Подразделение считается вредным
• 2,9991523619 Как вы думаете, почему они называют это *плавающей* точкой?
• 1.9999103517 Ищем несколько хороших недостатков
• 0.9999999998 Опечатки внутри