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

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

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

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

VLV

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

Reply to
Vladimir Vassilevsky
Loading thread data ...

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

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

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

VLV

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

Reply to
Vladimir Vassilevsky

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 мкс. См.

formatting link
, в той же фирме (InlineGroup) можешь взять диск с бесплатным софтом (Webpack)

Reply to
Ilia Tarasov

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

Reply to
Leha Bishletov

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

Reply to
Leha Bishletov

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

Reply to
Leha Bishletov

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

Reply to
Leha Bishletov

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)

formatting link
С этим знаком, буду вниательнее изучать те, что подходят по цене.

SP> M16, ... (Renesas)

formatting link
С этим не знаком, да и дороговаты они для моей задачи.

Leha

Reply to
Leha Bishletov

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

Reply to
Leha Bishletov

Привет!

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)

formatting link
LB> С этим знаком, буду вниательнее изучать те, что подходят по цене. Знаком :), а не знаешь что у него все что тебе надо есть... У _ВСЕХ_ без исключения MB90Fxxx есть аппаратное целочисленное умножение/деление. В твой ценник попадают F49X, F45X, F38X.

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

_______ Сергей.

Reply to
Sergey Pinigin

Привет!

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

_______ Сергей.

Reply to
Sergey Pinigin

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)

formatting link
LB>> С этим знаком, буду вниательнее изучать те, что подходят по LB>> цене. SP> Знаком :), а не знаешь что у него все что тебе надо есть... SP> У _ВСЕХ_ без исключения MB90Fxxx есть аппаратное целочисленное SP> умножение/деление. SP> В твой ценник попадают F49X, F45X, F38X.

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

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

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

Leha

Reply to
Leha Bishletov

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 не имеют защиты от считывания програмнной памяти, но это далеко не всех волнует.

Reply to
Vyacheslav Ovsiyenko

Привет!

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$). (Кажется еще есть на складе Промэлектроники.)

_______ Сергей.

Reply to
Sergey Pinigin

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]

Reply to
Alexander Samutin
23-Aug-03 19:16 Andy Chernyshenko wrote to Leha Bishletov:

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

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

wbr,

Reply to
Oleksandr Redchuk

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 (правда, дабл там "ненастоящий", а

48-битный, но флоат - "честный", 32-битный)). Единственное, float там не IEEE'шный, у него знак мантиссы перенесен из старшего бита всего числа в старший бит мантиссы, и за счет этого достигается бОльшая скорость.

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

Bye.

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

Reply to
Harry Zhurov

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, и это можно будет скорректировать последующим умножением и сравнением с делимым.

Reply to
Vovanius Uryvaeff
24-Aug-03 23:43 Harry Zhurov wrote to Leha Bishletov:

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,

Reply to
Oleksandr Redchuk

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-х должно быть в районе

300-400 тактов, т.ч. в два раза по сравнению с флоатом оно может спокойно выйти.

Bye.

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

Reply to
Harry Zhurov

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.