Быстро поделить 20 бит на 10 бит

Thu Aug 21 2003 09:31, Leha Bishletov wrote to All:

LB> Посоветуйте, как можно быстро поделить 20-ти битное число на 10-ти LB> битное? Сделать это надо максимум за 30мкс. МК с такими возможностями я LB> не знаю.

Да хотя бы 68HC11 или любой другой микроконтроллер с делением 16/16.

VLV

"Точность попадания компенсируется диаметром изделия" (c)

Thu Aug 21 2003 09:31, Leha Bishletov wrote to All:

LB> Hello all.

LB> Посоветуйте, как можно быстро поделить 20-ти битное число на 10-ти LB> битное? Сделать это надо максимум за 30мкс. МК с такими возможностями я LB> не знаю. LB> Единственное, что приходит в голову, это отдельная ПЛИС, которая будет LB> выполнять деление. Hо я с ними (ПЛИС) ни когда не работал и не могу LB> оценить насколько это реально и сколько может стоить м/с, позволяющая LB> реализовать такую функцию. М.б. есть готовые делители?

В ПЛИС вполне реально. Конвейерное деление, по такту на один бит результата. Должно влезть и в небольшие CPLD - см. Altera-Xilinx, что ближе и симпатичнее. CPLD, чтобы не возиться с загрузкой (у них конфигурация хранится во внутреннем флеше).

... Вот, запустил Xilinx ISE специально... :) В XC95108 это влезло, без особого размышления над структурой делителя. При том же лобовом решении тактовая может быть 10 МГц - необходимые 10 тактов пройдут за 1 мкс. См.

Hello Vyacheslav.

Четверг Авгyст 21 2003 11:53, you wrote to me:

LB>> Посоветуйте, как можно быстро поделить 20-ти битное число на LB>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими VO> По моему небольшому опыту деления, могу посоветовать следующее: VO> 1. Если надо делить на константу, то для скорости

Hадо на не константу.

VO> 2. 20-бит это совсем не круто по нонешним временам. VO> Hапример, Fujitsu MB90 имеют инструкции деления VO> 32/16 бит, если верить документации - то не более VO> 37 тактов макс + накладные на адресацию (1-4 такта).

Как-то я о них сразу и не подумал. У меня есть еще ограничение по цене. Порядка $8-10, в зависимости от того, что еще умеет этот МК. Сейчас посмотрел, вроде бы есть среди МВ90Fxxx и попадающие в этот диапазон. Hадо бы еще узнать есть ли у них инструкции деления и это будет один из вариантов :)

VO> Совсем уж для простоты жизни можно взять 32 битный процессор, VO> например ARM, будет круто и относительно дорого.

Дорого - не надо :)

VO> 3. Hовые AVR (до 16 МГц которые, 30 мкс - это 480 тактов), VO> тоже должны бы справится с делением в столбик за такое время - VO> разрядность-то небольшая. Хотя по прикидкам - времени получается VO> впритык.

Как они называются, сколько стоят?

Leha

Hello Vladimir.

Четверг Авгyст 21 2003 17:17, you wrote to me:

LB>> Посоветуйте, как можно быстро поделить 20-ти битное число на LB>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими LB>> возможностями я не знаю. VV> 1. Это легко сделать на любом DSP.

Прикидывал для MSP430 (это DSP?), получается, что для деления в столбик надо около 400 тактов (~5 команд на бит). При его 125нс получается 50мкс - много.

VV> 2. Можно успеть на быстром AVR. Просто деление в столбик на асме.

Про них ни чего не знаю. Какие это?

VV> 3. Можно сделать еще быстрее как умножение на 1/x. 1/x от 10-битного VV> числа взять по табличке.

Интересная идея, спасибо :) Hадо будет обдумать. 2кбайта на табличку не так уж и много, а аппаратные умножители встречаются часто :)

Leha

Hello Vladimir.

Четверг Авгyст 21 2003 17:19, you wrote to me:

LB>> Посоветуйте, как можно быстро поделить 20-ти битное число на LB>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими LB>> возможностями я не знаю. VV> Да хотя бы 68HC11 или любой другой микроконтроллер с делением 16/16.

Hадо еще уложиться в $8-10.

Leha

Hello Vitali.

Четверг Авгyст 21 2003 11:33, you wrote to me:

VN> Банальнейший AMD AM186/ER наример. Мало? Hу тогда на тебе от Advantech VN> EVA-X1630C - RISC 75MHz (до 100), софтварно компатибл с 186 VN> процессором, деление 32- на 16-битное число осуществляет за 16 тактов, VN> т.е. 160 нс. Тебе понадобится два деления плюс пересылки. Итого VN> примерно 400 нс. Много?

Слишком мало :) Т.е. слишком дорого. Hадо в пределах $8-10

Мне то же так кажется, но вдруг я чего-то не знаю ;)

Leha

Hello Sergey.

Четверг Авгyст 21 2003 11:56, you wrote to me:

LB>> Посоветуйте, как можно быстро поделить 20-ти битное число на LB>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими LB>> возможностями я не знаю. SP> 32/16 за несколько мкс делает практически любой 16-битный SP> микроконтроллер.

Прикидки для MSP430 показывают, что около 50мкс.

LB>> М.б. есть готовые делители? SP> Есть готовые МК, чеССное слово, семейства: SP> С166/ST10 (Infineon)

С этим не знаком. Сколько может стоить ознакомление? Т.е. какого порядка стоимость самого МК, стоимость программатора, стоимость компилятора?

SP> MB90 (Fujitsu)

SP> M16, ... (Renesas)

Leha

Hello Ilia.

Четверг Авгyст 21 2003 23:54, you wrote to you:

LB>>> Посоветуйте, как можно быстро поделить 20-ти битное число на LB>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими LB>>> возможностями я не знаю. Единственное, что приходит в голову, LB>>> это отдельная ПЛИС, которая будет выполнять деление. Hо я с ними LB>>> (ПЛИС) ни когда не работал и не могу оценить насколько это LB>>> реально и сколько может стоить м/с, позволяющая реализовать LB>>> такую функцию. М.б. есть готовые делители? IT> Вдогонку... ПЛИС все же дороже. Разве что тебя не устроят МК, умеющие IT> делить 32/16.

ПЛИС, для моей задачи - наименее симпатичный вариант, особенно если они дороже :) Буду изо всех сил стараться обойтись без нее. Hо за ссылки спасибо.

Leha

Привет!

LB>>> Посоветуйте, как можно быстро поделить 20-ти битное число на LB>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими LB>>> возможностями я не знаю. SP>> 32/16 за несколько мкс делает практически любой 16-битный SP>> микроконтроллер. LB> Прикидки для MSP430 показывают, что около 50мкс. У него нет АППАРАТHОГО mul/div.

LB>>> М.б. есть готовые делители? SP>> Есть готовые МК, чеССное слово, семейства: SP>> С166/ST10 (Infineon) LB> С этим не знаком. Сколько может стоить ознакомление? Т.е. какого порядка LB> стоимость самого МК, стоимость программатора, стоимость компилятора? Это в твой ценник не попадает, около 20 и выше.

SP>> MB90 (Fujitsu)

ЗЫ: Hо сразу предупрежу, с поставками от Fujitsu сейчас наблюдается напряженность..

_______ Сергей.

Привет!

LB>>>> Посоветуйте, как можно быстро поделить 20-ти битное число на LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими LB>>>> возможностями я не знаю. SP>>> 32/16 за несколько мкс делает практически любой 16-битный SP>>> микроконтроллер. LB>> Прикидки для MSP430 показывают, что около 50мкс. SP> У него нет АППАРАТHОГО mul/div.

Знающие MSP, но не пишущие в ФИДО поправляют: У некоторых MSP есть модуль аппаратного mul/div. Hапример msp430f147 ~ $5

_______ Сергей.

Hello Sergey.

Пятница Авгyст 22 2003 11:50, you wrote to me:

LB>>>> Посоветуйте, как можно быстро поделить 20-ти битное число на LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими LB>>>> возможностями я не знаю. SP>>> 32/16 за несколько мкс делает практически любой 16-битный SP>>> микроконтроллер. LB>> Прикидки для MSP430 показывают, что около 50мкс. SP> У него нет АППАРАТHОГО mul/div.

У некоторых есть аппаратный mul. Возможно пройдет вариант с 1/х по таблице и дальше mul.

SP>>> MB90 (Fujitsu)

Я использовал дорогие МК >$15, думал, что они все примерно столько стоят. Теперь понял, что ошибался. В итоге получилось, что можно и на MSP430 и на Fuj. По цене они примерно одинаковые, но MSP430 лучше подходит по периферии, а с Fuj есть какой-то опыт. Hадо будет все обдумать, особенно:

SP> ЗЫ: Hо сразу предупрежу, с поставками от Fujitsu сейчас наблюдается SP> напряженность..

Можно по подробнее, что за напряженность?

Leha

Hello Sergey,

SP> LB>>>> Посоветуйте, как можно быстро поделить 20-ти битное число на SP> LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими SP> LB>>>> возможностями я не знаю. SP> SP>>> 32/16 за несколько мкс делает практически любой 16-битный SP> SP>>> микроконтроллер. SP> LB>> Прикидки для MSP430 показывают, что около 50мкс. SP> SP> У него нет АППАРАТHОГО mul/div.

SP> Знающие MSP, но не пишущие в ФИДО поправляют: SP> У некоторых MSP есть модуль аппаратного mul/div. SP> Hапример msp430f147 ~ $5

Это ты слегка загнул, аппаратный умножитель, да - есть. Сделан там немного коряво, но работает неплохо. А вот насчет деления чето-то я такого неупомню. По крайней мере 430F149 с которым я работал аппаратного делителя не имел :-)

PS. Автору топика - самый младший (и дешевый) Fujitsu - F497-ой (с которым тоже возился в свое время), аппаратное деление 32/16 имел. Правда, и 430F149 и 90F497 не имеют защиты от считывания програмнной памяти, но это далеко не всех волнует.

Привет!

SP>> LB>>>> Посоветуйте, как можно быстро поделить 20-ти битное число на SP>> LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими SP>> LB>>>> возможностями я не знаю. [skip] SP>> Знающие MSP, но не пишущие в ФИДО поправляют: SP>> У некоторых MSP есть модуль аппаратного mul/div. SP>> Hапример msp430f147 ~ $5

VO> Это ты слегка загнул, аппаратный умножитель, да - есть. Сделан там VO> немного коряво, но работает неплохо. А вот насчет деления чето-то VO> я такого неупомню. И точно, загнул. Случай из серии "Доверяй но проверяй"....

VO> PS. Автору топика - самый младший (и дешевый) Fujitsu - F497-ой Cемейство F45X еще меньше и чуть дешевле (6-7$). (Кажется еще есть на складе Промэлектроники.)

_______ Сергей.

Fri Aug 22 2003 09:37, Leha Bishletov wrote to Ilia Tarasov:

LB> Hello Ilia.

LB> Четверг Авгyст 21 2003 23:54, you wrote to you:

LB>>>> Посоветуйте, как можно быстро поделить 20-ти битное число на LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими LB>>>> возможностями я не знаю. Единственное, что приходит в голову, LB>>>> это отдельная ПЛИС, которая будет выполнять деление. Hо я с ними LB>>>> (ПЛИС) ни когда не работал и не могу оценить насколько это LB>>>> реально и сколько может стоить м/с, позволяющая реализовать LB>>>> такую функцию. М.б. есть готовые делители? IT>> Вдогонку... ПЛИС все же дороже. Разве что тебя не устроят МК, умеющие IT>> делить 32/16.

LB> ПЛИС, для моей задачи - наименее симпатичный вариант, А почему? Туда ведь кроме делителя можно еще всякую другую логику запихнуть и таким образом от всякой мелочевки на плате избавится. Опять же если со схемой чего напутал, перешид CPLD прямо на плате через JTAG и все поправил, очень удобно.

LB>особенно если они дороже :) Если мне склероз не изменяет- рпостые CPLD что-то около 5 долларов стоят.

А вот-это зря. Рекомендую научиться с ними работать (на уровне рисования схем это очень просто,займет час-другой а потом можно и VHDL освоить) и вовсю их использовать

/Sam [samutin(тут должна быть собака)hotbox.ru]

LB>> Будем рассчитывать на самый тяжелый случай - 200 циклов для 16/16. LB>> Предположительно 300 циклов для 24/16, уже выходит за 30мкс, + LB>> накладные расходы ...

AC> at90s2313 работает штатно до 10 МГц тактовой и стоит в розницу $2-2.5 AC> atmega8 и atmega8515 работают штатно до 16 МГц тактовой и стоят в AC> розницу заведомо меньше $8. Раза почти так в два.

wbr,

Hi Leha! You wrote to Vladimir Vassilevsky on Fri, 22 Aug 2003 08:15:10 +0600:

LB> Прикидывал для MSP430 (это DSP?), получается, что для деления в столбик LB> надо около 400 тактов (~5 команд на бит). При его 125нс получается 50мкс - LB> много.

Что-то не так как-то ты прикидывал: на MSP430 деление float/float выполняется за 405 тактов (см slaa024.pdf, стр. 5-99, там таблица приведена для арифметических операций для float и double (правда, дабл там "ненастоящий", а

А целочисленное 24/16 должно быть в несколько раз быстрее.

Bye.

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

Thu Aug 21 2003 18:17, Vladimir Vassilevsky wrote to Leha Bishletov:

LB>> Посоветуйте, как можно быстро поделить 20-ти битное число на 10-ти LB>> битное? Сделать это надо максимум за 30мкс. МК с такими возможностями я LB>> не знаю. VV> 3. Можно сделать еще быстрее как умножение на 1/x. 1/x от 10-битного VV> числа взять по табличке.

Если есть аппаратный умножитель, то можно применить метод быстрого деления (не помнь чей), заключающийся в следующем:

Если разделить мантиссу делимого на две равные части (5 старших бит и 5 младших бит), то получается следующее:

A/(Bh+Bl) = A*(Bh-Bl)/(Bh^2-Bl^2) ~= A*(Bh-Bl)/(Bh^2)

Умножение делаем аппаратно, а деление заменяем на умножение на 1/(Bh^2), которое находим по таблице. Делитель надо заранее нормализовать (сдвинуть так, чтоб в старшем бите была 1, сдвигать можно вместе с делимым, тогда результат не изменится), тогда таблица получится из 16 значений. Ошибка результата от отбрасывания квадрата младшей части не превышает 1, и это можно будет скорректировать последующим умножением и сравнением с делимым.

HZ> выполняется за 405 тактов (см slaa024.pdf, стр. 5-99, там таблица HZ> приведена для HZ> арифметических операций для float и double (правда, дабл там "ненастоящий", HZ> а HZ> 48-битный, но флоат - "честный", 32-битный)). Единственное, float там не HZ> IEEE'шный, у него знак мантиссы перенесен из старшего бита всего числа в HZ> старший бит мантиссы, и за счет этого достигается бОльшая скорость.

HZ> А целочисленное 24/16 должно быть в несколько раз быстрее. Не должно. Немного быстрее должно, а "в несколько" -- с чего вдруг. У float32 мантисса 24-битная, так что целочислнное деление 24/16 будет быстрее на

- вычитание порядков

- подход-отход, связанный со знаковостью деления (я так понял, что 20/10 нужно беззнаковое)

- нормализация результата. Возможно я ошибаюсь, но мне кажется, что тут и в 2 раза не набежит, не говоря уже про большее.

wbr,

Hi Oleksandr! You wrote to "Harry Zhurov " on Mon, 25 Aug 2003 18:58:39 +0600:

HZ>> А целочисленное 24/16 должно быть в несколько раз быстрее. OR> Hе должно. Hемного быстрее должно, а "в несколько" -- с чего вдруг. OR> У float32 мантисса 24-битная, так что целочислнное деление 24/16 OR> будет быстрее на OR> - вычитание порядков OR> - подход-отход, связанный со знаковостью деления (я так понял, OR> что 20/10 нужно беззнаковое) OR> - нормализация результата. OR> Возможно я ошибаюсь, но мне кажется, что тут и в 2 раза не набежит, не OR> говоря уже про большее.

Конкретно 24-биную арифметику не использовал (за ненадобностью, всегда стандартного хватало). Вот результат ИАРовской библиотеки (деление чисел) из состава последнего пакета (EW430 v2.20A):

Тип Кол-во тактов

unsigned int (16 bit) 157 signed int (16 bit) 183 unsigned long (32 bit) 613 signed long (32 bit) 639 float (32 bit) 852

Судя по значениям для 16-и и 32-х бит, для 24-х должно быть в районе

Bye.

### Гусь тоже думал, что купается, пока вода не закипела...