LINUX.ORG.RU
ФорумTalks

как в процессорах чаще всего реализована команда деления?


1

1

Чтобы разгрузить мозг после трудного понедельника, вот вам задачка для специалистов по всему: Как бы вы реализовали операцию целочисленного деления в самодельном процессоре? Как сэмулировали бы эту операцию на процессоре не поддерживаемом её? Какие бы шаги предприняли для оптимизации этой операции?

★★★
Ответ на: комментарий от andreyu

Так ROM же, прямо в чипе. Здоровенный, конечно, нужен.
Можно ещё забить в ROM таблицу только для первых k×k и считать в 2^k-ичной системе счисления.

Q3164
()
Ответ на: комментарий от Q3164

Можно ещё забить в ROM таблицу только для первых k×k и считать в 2^k-ичной системе счисления.

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

drBatty ★★
()
Ответ на: комментарий от drBatty

Про деление я ничего не знаю (и на вопрос из ОП-поста «Как бы...» ответил бы «Софтово»), а умножение можно так сделать, хотя я и не знаю, каким способом будет быстрее.

Q3164
()
Ответ на: комментарий от andreyu

Но почему? Вроде везде сказано, что ROM медленне, но почему, я понять не могу, вроде же в нём от одного конца до другого совсем немного элементов.

Q3164
()
Ответ на: комментарий от Q3164

Но почему? Вроде везде сказано, что ROM медленне, но почему, я понять не могу, вроде же в нём от одного конца до другого совсем немного элементов.

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

andreyu ★★★★★
()
Ответ на: комментарий от Q3164

Когда то давно, на ZX-Spectrum было правильнее заранее расчитать таблицу синусов, чем считать их в рилтайме. Поскольку работа с памятью не была узким местом (относительно скорости работы процессора).

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Когда то давно, на ZX-Spectrum было правильнее заранее расчитать таблицу синусов, чем считать их в рилтайме.

Когда-то давно, на 8086 было правильнее заранее рассчитать таблицу умножения на 80 (такой код в Norton Commander есть, если не ошибаюсь), чем использовать умножение. Умножение! А ты о синусах.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

Когда-то давно, на 8086 было правильнее заранее рассчитать таблицу умножения на 80 (такой код в Norton Commander есть, если не ошибаюсь), чем использовать умножение. Умножение! А ты о синусах.

Но это не отменяет того факта, что таблицу синусов на speccy, было выгоднее расчитать предварительно. Верно? :)

andreyu ★★★★★
()
Ответ на: комментарий от Q3164

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

умножители ещё в 70х годах прошлого века делали 2х, и даже 4х битными. Естественно они намного быстрее однобитного («однобитный умножитель» — это простой сумматор удвоенного размера). Например двухбитный умножитель одновременно (не)складывает два числа с частичной суммой.

Но вот двухбитных делителей, AFAIK не делают до сих пор.

drBatty ★★
()
Ответ на: комментарий от Q3164

Даже если память такая https://ece.uwaterloo.ca/~cgebotys/NEW/romdec.gif ?

если такая — всё отлично. Но представь себе матрицу 30000×30000 китайцев (миллиард). Скорость работы такой матрицы равна скорости работы одного китайца, ибо в каждый момент мы выбираем только одного из матрицы. А вот кормить тебе придётся весь миллиард. Сейчас в процессоре в умножителе тоже 100500 транзисторов, и они тоже составляют матрицу, например умножитель 32x32 умножает за один такт два числа из 32х бит, и имеет в своём составе 1024 однобитных сумматоров. Но работают они ВСЕ сразу, а не по одному. Единственное, что сейчас ограничивает число транзисторов — TDP, потому вопрос кормления стоит ребром.

drBatty ★★
()
Ответ на: комментарий от i-rinat

Когда-то давно, на 8086 было правильнее заранее рассчитать таблицу умножения на 80 (такой код в Norton Commander есть, если не ошибаюсь), чем использовать умножение. Умножение!

умножение на константу — частный случай. И да, 80 == 2⁴+2²+2⁰, т.е. всего три сложения/сдвига. Что-то я сильно сомневаюсь, что выборка из памяти будет быстрее.

drBatty ★★
()
Ответ на: комментарий от i-rinat

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

А теперь посчитай в тактах.

в тактах уже считал: сам подумай, что выгоднее: иметь n конвейеров из n ступеней, в которых ВСЕ n×n элементов задействованы, или иметь n×n элементов, из которых работает лишь ОДИН? Ответ очевиден.

ну вот ещё один пример: для деления двух чисел 0..65535 тебе понадобится 32 матрицы 65536×65536 (по 512Mb каждая, всего 4Гб). Куда как проще создать конвейер из 16х сумматоров на 16 бит каждый (всего 256 однобитных сумматоров), которые За ОДИН такт и будут делить два 16и битных числа с остатком. Матрица таких сумматоров может не только умножать два числа за такт, но складывать по 16 чисел за такт.

drBatty ★★
()
Ответ на: комментарий от drBatty

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

А теперь посчитай в тактах.

в тактах уже считал: сам подумай, что выгоднее: иметь n конвейеров из n ступеней, в которых ВСЕ n×n элементов задействованы, или иметь n×n элементов, из которых работает лишь ОДИН? Ответ очевиден.

Ну вот опять эталонная шизофазия. Для 8086 доступны таблицы с числом тактов на инструкцию. А вместо того, чтобы посчитать, ты несёшь какой-то бред. Ну так и быть, я посчитаю за тебя: чтение из памяти занимает 4 такта. Логические операции, сдвиги и просто mov'ы занимают минимум 4 такта каждое. Итого — чтение из памяти (на 8086) в разы быстрее. Да и на 8088 оно в разы быстрее.

ну вот ещё один пример: для деления двух чисел 0..65535 тебе понадобится 32 матрицы 65536×65536 (по 512Mb каждая, всего 4Гб). Куда как проще создать конвейер из 16х сумматоров на 16 бит каждый (всего 256 однобитных сумматоров), которые За ОДИН такт и будут делить два 16и битных числа с остатком. Матрица таких сумматоров может не только умножать два числа за такт, но складывать по 16 чисел за такт.

О чём ты? Речь шла исключительно об умножении на константу на 8086. Что это за поток сознания?!

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

Ну вот опять эталонная шизофазия. Для 8086 доступны таблицы с числом тактов на инструкцию. А вместо того, чтобы посчитать, ты несёшь какой-то бред. Ну так и быть, я посчитаю за тебя: чтение из памяти занимает 4 такта. Логические операции, сдвиги и просто mov'ы занимают минимум 4 такта каждое. Итого — чтение из памяти (на 8086) в разы быстрее. Да и на 8088 оно в разы быстрее.

это не у меня шизофазия, а у тебя эталонная безграмотность: 4 такта это МИНИМАЛЬНОЕ время, которое возникает только в случае идеально-сферической памяти, время доступа к которой ВСЕГДА равно нулю. У реальной памяти так, к сожалению, не бывает. Латентность есть всегда, но её нет в твоих таблицах.

И да, для деления 16и битных чисел нужно 4Гб памяти с нулевой латентностью. Да даже и не с нулевой — покажи мне 16и битный компьютер с 4Гб памяти? Жду с нетерпением (кстати, 8086 мог максимум 1048576 байт адресовать, если ты забыл).

ну вот ещё один пример: для деления двух чисел 0..65535 тебе понадобится 32 матрицы 65536×65536 (по 512Mb каждая, всего 4Гб). Куда как проще создать конвейер из 16х сумматоров на 16 бит каждый (всего 256 однобитных сумматоров), которые За ОДИН такт и будут делить два 16и битных числа с остатком. Матрица таких сумматоров может не только умножать два числа за такт, но складывать по 16 чисел за такт.

О чём ты? Речь шла исключительно об умножении на константу на 8086. Что это за поток сознания?!

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

drBatty ★★
()
Ответ на: комментарий от drBatty

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

Опять-таки, ты просто не знаешь, о чём говоришь. Во времена 8086 зазор между скоростями CPU и латентностью памяти не был таким большим, как сейчас.

это не у меня шизофазия

Да ну?

И да, для деления

Какого деления?

а зачем ты приплёл к вопросу о делении какое-то умножение, да ещё и на константу

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

Ты приплёл другую тему.

i-rinat ★★★★★
()
Последнее исправление: i-rinat (всего исправлений: 1)
Ответ на: комментарий от i-rinat

Опять-таки, ты просто не знаешь, о чём говоришь. Во времена 8086 зазор между скоростями CPU и латентностью памяти не был таким большим, как сейчас.

это ты не знаешь, о чём говоришь: во времена 8086 не было огромных кешей на кристалле, и латентность играла огромную роль. Сейчас она важна только в некоторых приложениях, в частности таких, как ты предлагаешь — рандомно читать одно слово из 4х гигабайт. Ну а в те времена, проблема была даже с маленькими табличками. В отличие от памяти, в ALU никакой латентности не было, и вычисления завершались точно в срок, что намного важнее НЁХ, которую даёт RAM в виде латентности.

Какого деления?

ты сабж читаешь?

А теперь проследи нить разговора. Знаешь, такие ссылочки, указывающие на предыдущий комментарий в нити. Прочитай мой первый комментарий в текущей нити. Ты приплёл другую тему.

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

Ну и в целых числах экстраполяция вообще плохо работает, ибо ошибку округления очень сложно контролировать.

По всем этим причинам, табличные вычисления применялись и применяются только в _очень_ специальных случаях (вроде графики в ZX, но вы видели ЭТУ «графику»??).

drBatty ★★
()
Ответ на: комментарий от andreyu

таблицу синусов на speccy, было выгоднее расчитать предварительно

Да ладно там спекки, он родом из 70х, так и Вольф3Д образца 1992го этим не брезговал.

redgremlin ★★★★★
()
Ответ на: комментарий от drBatty

это ты не знаешь, о чём говоришь: во времена 8086 не было огромных кешей на кристалле

Потому что не было необходимости в кеше.

в частности таких, как ты предлагаешь — рандомно читать одно слово из 4х гигабайт

Не приписывай мне то, чего я не говорил.

ты сабж читаешь?

Читаю. Внимательно. Но как ты не заметил, отвечал я на конкретное сообщение, а не на оригинальное.

это ты приплёл другую тему

То есть ты так и не проследил нить? Хотя, кто бы сомневался.

Да и в ней тоже слил,

Если ты повторишь это сто раз, то даже сам поверишь. Аутотренинг — великая сила.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

это ты не знаешь, о чём говоришь: во времена 8086 не было огромных кешей на кристалле

Потому что не было необходимости в кеше.

гениальный аргумент! Вот и у Александра Невского не было никакой необходимости в танках-амфибиях. ☺

Действительно: подумаешь, Over9000 бойцов на Чудском Озере утонуло? Мы же всё равно победили!

drBatty ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.