Floating and fixed point arithmetic in FPGA Опции

[des333]

Подскажите, кто знает, литературу по сабжу.

А то, все что пока удалось найти, это основные мат. сведения + простые показательные примеры.

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

Не верю, что нет серьезных изданий по сабжу.




Заранее спасибо!




P.S. Лучше, если на английском языке.

Сообщение отредактировал des333 - Aug 30 2009, 14:05

[Methane]

P.S. Лучше, если на английском языке.

Попробуйте подумать головой.

[des333]

Попробуйте подумать головой.

Я думаю, если не хочется советовать по теме, писать никто не заставляет...

Сообщение отредактировал des333 - Aug 30 2009, 14:11

[DmitryR]

А зачем вам, скажите, литература? На opencores есть готовые реализации, скачайте и изучите.

[des333]

А зачем вам, скажите, литература? На opencores есть готовые реализации, скачайте и изучите.

Реализации уже скачал - изучаю.

Просто хочется рассмотреть не только конкретный практический подход, но и теоритическую часть.

Алгоритмы, оптимизацию, рассчеты, сравнительный анализ и т.д. 

[Самурай]

Подскажите, кто знает, литературу по сабжу.
А то, все что пока удалось найти, это основные мат. сведения + простые показательные примеры.
Интересует более подробный, доскональный и глубокий анализ данной темы.
Не верю, что нет серьезных изданий по сабжу.

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

1. Арифметика цифровых машин (М.А.Карцев)
2. Основы машинной арифметики (А.М.Шауман)
3. Arithmetic and Logic in Computer Systems (Mi Lu)
4. SYNTHESIS OF ARITHMETIC CIRCUITS: FPGA, ASIC, and Embedded Systems

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

[des333]

Самурай:

Большое спасибо!

[des00]

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

раскажите для повышения образованности, а какую теорию и алгоритмы вы имели в виду ? правила всех арифметических операций однозначно вытекают из определения форматов чисел. И какой именно сравнительный анализ вы имели в виду? Сравнивать что лучше плавучка или фиксированная точка в общем смысле? но на этот вопрос можно дать однозначный ответ %)

[des333]

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

Неужели эта область настолько простая, что не затронута ни в какой литературе?

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

Просто я про обычные счетчики видел больше информации, чем про вычесления с плавающей запятой.

И какой именно сравнительный анализ вы имели в виду? Сравнивать что лучше плавучка или фиксированная точка в общем смысле? но на этот вопрос можно дать однозначный ответ %)

Если Вас не затруднит, дайте 

И скажите, в каких областях тогда используется оставшийся, явно худший в общем смысле, вариант?

[des00]

Неужели эта область настолько простая, что не затронута ни в какой литературе?

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

как видно с точки зрения вычислений, ничем не отличается от целочисленой арифметики.

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

Просто я про обычные счетчики видел больше информации, чем про вычесления с плавающей запятой.

насколько я знаю, на это есть отдельный стандарт, в нем все написано как и что делать с плавающей запятой. На счетчики такого стандарта нет %)

Если Вас не затруднит, дайте
И скажите, в каких областях тогда используется оставшийся, явно худший в общем смысле, вариант?

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

Преимущество использования представления чисел в формате с плавающей запятой над представлением в формате с фиксированной запятой (и целыми числами) состоит в том, что можно использовать существенно больший диапазон значений при неизменной относительной точности. Например, в форме с фиксированной запятой число, занимающее 8 разрядов в целой части и 2 разряда после запятой, может быть представлено в виде 123456,78; 8765,43; 123,00 и так далее. В свою очередь, в формате с плавающей запятой (в тех же 8 разрядах) можно записать числа 1,2345678; 1234567,8; 0,000012345678; 12345678000000000 и так далее.

[yes]

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

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

но за последние время вышла DW для флоат поинта, ну и опенкорес на месте не стоит...

еще можно порекомендовать изучить реализацию libm (GNU) там написан эмулятор плавучки для целочисленных процессоров - можно получить представление

[Гвоздик]

Некоторое время назад я тоже столкнулся с задачей вычисления алгоритма с дробными числами на ПЛИСине. По моим практическим наблюдениям опенкоресные и закрытые от копирования умножители, сумматоры и делители чисел с плавающей запятой работали слишком медленно, чтобы их можно было серьезно применять. Решением оказалось применение Матлаба в связке с зайлинксовским "AccelEDA". Все исходные данные и результат автоматически приводились Матлабом к целым числам соотвествующей разрядности. Точность вычислений терялась, но в пределах ТЗ. Зато написать все и отмоделировать можно очень быстро.

[petrov]

Книжка по теме:
http://www.telesys.ru/wwwboards/dsp/307/me...es/164673.shtml

[Rst7]

Я бы не стал так огульно хаять плавающую точку Хотя бы только потому, что если абстрагироваться от конкретного IEEE-шного формата (и не использовать его во внутреннем представлении, а носить на шинах все в распакованном виде), то не так уж и много аппаратуры надо наворотить рядом - для умножителя/делителя нужно сделать рядом вычисление суммы/разностей порядков плюс некоторые костыли для нормализации, а для суммы/разности - такой себе barrel-shift'ер, управляемый разностью порядков для приведения мантисс к одному порядку.

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

Я это к тому, что если очень надо, то можно и реализовать плавающую запятую. Конечно, если вообще хочется IEEE-формата, тогда да - там железа надо наворотить некисло.

[zverek]

Я бы не стал так огульно хаять плавающую точку Хотя бы только потому, что если абстрагироваться от конкретного IEEE-шного формата (и не использовать его во внутреннем представлении, а носить на шинах все в распакованном виде), то не так уж и много аппаратуры надо наворотить рядом

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

Некоторое время назад я тоже столкнулся с задачей вычисления алгоритма с дробными числами на ПЛИСине. По моим практическим наблюдениям опенкоресные и закрытые от копирования умножители, сумматоры и делители чисел с плавающей запятой работали слишком медленно, чтобы их можно было серьезно применять. Решением оказалось применение Матлаба в связке с зайлинксовским "AccelEDA". Все исходные данные и результат автоматически приводились Матлабом к целым числам соотвествующей разрядности. Точность вычислений терялась, но в пределах ТЗ. Зато написать все и отмоделировать можно очень быстро.

ИМХО, только как вариант "вставил и забыл", что-то "расширяемое" так сделать не получится.

Хотя, посмотреть на то, как будет считать матлаб, интересно (а может даже пригодится)

[Rst7]

Но для этого нужно как минимум вникнуть во все детали и хорошо во всем разбираться.

Не могу сказать, что уж очень там с "деталями" сложно. Хотя, опять же... Ну вот допустим, простейшие вещи - умножение и деление с плавающей запятой.

Умножение: Вроде все хорошо, допустим, числа нормализованы и всегда есть единичный старший бит. Тогда, по результатам умножения для нормализации надо проверить старший бит произведения, и, если он равен 0, то сдвинуть результат влево с увеличением результирующего порядка на 1. Типа перенос учесть в сумматоре порядков.

Деление: а тут таких простых результатов не получается - количество нулей в частном может быть произвольным. Т.к. выполнять после деления поиск первой единицы в частном и сдвиг результата до нормализованного очень уж тоскливо, есть смысл вкрутить автонормализацию в само деление. Допустим, если деление выполняется в столбик, то наличие каждого ведущего нулевого бита в частном должно приводить к уменьшению величины порядка результата на единичку. Как только встречается 1, то деление продолжается обычным образом.

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

[zverek]

Не могу сказать, что уж очень там с "деталями" сложно.

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

Сорри, я по старой доброй институтской памяти...

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

А как, например, косинус считают с плавающей точкой? Через ряды? (Я не про синус нуля, пи и прочее из школьных учебников). То есть я понимаю, что можно через "сложение" все сделать. Акцент на производительность (как это не в теории делается)? Или опять все сводится к реализации умножения/деления + конвейер?

Дополнение: наткнулся на интересную статейку чувствую, что в разных современных GPU таких уловок масса. Наткнулся на нее здесь, значит "в лоб" даже сопроцессор не считает.
Сорри за глупый вопрос, математику подзабыл, а до каких пор надо складывать, когда считаем синус, понимаю, что все вычисления приближенные, или в этом IEEE какраз это и описано?

[Methane]

Я думаю, если не хочется советовать по теме, писать никто не заставляет...

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

[des00]

Некоторое время назад я тоже столкнулся с задачей вычисления алгоритма с дробными числами на ПЛИСине. По моим практическим наблюдениям опенкоресные и закрытые от копирования умножители, сумматоры и делители чисел с плавающей запятой работали слишком медленно, чтобы их можно было серьезно применять. Решением оказалось применение Матлаба в связке с зайлинксовским "AccelEDA". Все исходные данные и результат автоматически приводились Матлабом к целым числам соотвествующей разрядности. Точность вычислений терялась, но в пределах ТЗ. Зато написать все и отмоделировать можно очень быстро.

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

Я бы не стал так огульно хаять плавающую точку

дык ее никто и не хает, но согласитесь что реализация плавающей точки весит больше чем фиксированной/целочисленной ?

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

последнее что я читал про GPU подводило к мысли что современные GPU как раз ушли с фиксированной точки на плавающую и все вычисления внутри строятся как раз на ней.

А как, например, косинус считают с плавающей точкой? Через ряды? (Я не про синус нуля, пи и прочее из школьных учебников). То есть я понимаю, что можно через "сложение" все сделать. Акцент на производительность (как это не в теории делается)? Или опять все сводится к реализации умножения/деления + конвейер?

Дополнение: наткнулся на интересную статейку чувствую, что в разных современных GPU таких уловок масса. Наткнулся на нее здесь, значит "в лоб" даже сопроцессор не считает.

ну это был достаточно старый сопроцессор, с современными GPU не сравнить. А алгоритм расчета синуса зависит от требуемой вам точности.

[Methane]

Алгоритмы, оптимизацию, рассчеты, сравнительный анализ и т.д. 

Простой пример. Астрономы, когда считают расстояния до звезд, часто считают то синус (x) = x. И работает! Расстояние до какой-то там звезды, у черта на куличках такое, что диаметр орбиты нашего глобуса такой что плакать хочется. От этого углы крохотные, а вблизи нуля, синус это просто палка под углом в 45 градусов.

А в функциях что дает TI, синус вообще имеет период 65535, и амплитуду 32768 и тоже работает. И методов расчета его в ТИ предлагает три: через ряд (ну очень не длинный), через таблицу (ну очень не большую) и кажись через таблицу с интерполированием. И тоже работает! Асинхронные и синхронные двигатели + всякие УПСы, прекрасно работают на таком урезанном синусе. А астрономам не подходит: диаметр орбиты нашего глобуса, делёное на расстояние до какой-то там звезды стабильно дает 0, для почти всех звезд.

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

Это так, на пальцах.

[des00]

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

да и проще им, собрал один раз качественный FPU на кремнии и размножил N раз, все же не фпга %)

[Methane]

дык ее никто и не хает, но согласитесь что реализация плавающей точки весит больше чем фиксированной/целочисленной ?

Я не соглашусь. Сравните умножение какогонить урезанного эмулятора плавающей точки, где под float пару байт отведено и умножение с фиксированной точкой типа 64.64. Все хорошо на своем месте.

да и проще им, собрал один раз качественный FPU на кремнии и размножил N раз, все же не фпга %)

А на кремнии собрать несколько качественных FPU и запхать их в FPGA?

[des00]

Я не соглашусь. Сравните умножение какогонить урезанного эмулятора плавающей точки, где под float пару байт отведено и умножение с фиксированной точкой типа 64.64. Все хорошо на своем месте.

задачи конечно бывают разные, но на 64-х битном проце с умножителем 64х64 не вижу никаких проблем. На фпга для моих задач(модемная связь), максимум что потребовалось это ss10.24(36 бит). И то, это было взято с большим запасом

А на кремнии собрать несколько качественных FPU и запхать их в FPGA?

ИМХО не имеет смысла, это как идея, которая витала у хилых %) аппаратные элементы видео декодеров на фпга, даешь h.264 за 2 доллара (на спартан 3), которая быстра загнулась. Подобное (FPU) нужно небольшому количеству людей, а место на кристале будет занимать много (ведь надо делать честный IEEE, а не в тапки с...ь).

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

[Methane]

задачи конечно бывают разные, но на 64-х битном проце с умножителем 64х64 не вижу никаких проблем.

Я и на 8 битовом проблем не нахожу.

ИМХО не имеет смысла, это как идея, которая витала у хилых %) аппаратные элементы видео декодеров на фпга, даешь h.264 за 2 доллара (на спартан 3), которая быстра загнулась. Подобное (FPU) нужно небольшому количеству людей, а место на кристале будет занимать много (ведь надо делать честный IEEE, а не в тапки с...ь).

Не понял, это идея корейцев была? Вопли "h.264" в FPGA c их стороны шли?

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

То ихних маркетологов увольнять нада. Они могли эту самую блочную плавающую точку и в FIR фильтрах применять и вообще везде подряд. Работы на пол часа, толку ноль, зато кричать "мы круче ксилинкса" можно на всех сайтах типа edn.

[des00]

Я и на 8 битовом проблем не нахожу.

у нас разный взгляд на проблему %)

Не понял, это идея корейцев была? Вопли "h.264" в FPGA c их стороны шли?

мне ее озвучивал начальник, после встречи с манагерами хилых в америке, хотели аппаратный CABAC/CAVLC, Deblock и ME в фпга класса спартан3е Потом как я понял к нему микроба, ДДР2, интерфейсы и вуаля транскодер почти за 2 бакса %)

То ихних маркетологов увольнять нада. Они могли эту самую блочную плавающую точку и в FIR фильтрах применять и вообще везде подряд. Работы на пол часа, толку ноль, зато кричать "мы круче ксилинкса" можно на всех сайтах типа edn.

вам виднее, я подробно не разбирался что они там предлагают

[Methane]

мне ее озвучивал начальник, после встречи с манагерами хилых в америке, хотели аппаратный CABAC/CAVLC, Deblock и ME в фпга класса спартан3е Потом как я понял к нему микроба, ДДР2, интерфейсы и вуаля транскодер почти за 2 бакса %)

А, закон постоянства интеллекта в действии.

[des333]

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

Да я ничего сравнивать не хотел 
Хотел просто нарыть литературу.

....

Это так, на пальцах.

Так вот мне, как раз, нужно не на пальцах, а много-много сложной теории. 

Сообщение отредактировал des333 - Sep 1 2009, 10:55

[zverek]

А нет ли какого-то математического САПРа, который покажет разные способы вычисления, например, синуса в зависимости от того, что мы хотим получить (погрешность, точность, и т.д.)? Имел дело только с Matlab'ом, но мельком (очень не понравился его суконный язык, ощущение такое, что работаешь с БолшойЭВМ и перфокартами и он вот вот обзовет тебя нехорошим словом) и с Mathemati'кой (строил графики). Интересно посмотреть, как он будет считать.

А алгоритм расчета синуса зависит от требуемой вам точности.

А какая там, у них, в FPU/GPU? Неужели про это нет книг и разбирать приходится на "живых" примерах. Так не охото идти в "Библиотеку имени Ленина" за книгой 1964 года "Вычислительная математика ЭВМ". У нас что с того времени книг не писали?

[Methane]

А нет ли какого-то математического САПРа, который покажет разные способы вычисления, например, синуса в зависимости от того, что мы хотим получить (погрешность, точность, и т.д.)? Имел дело только с Matlab'ом, но мельком (очень не понравился его суконный язык, ощущение такое, что работаешь с БолшойЭВМ и перфокартами и он вот вот обзовет тебя нехорошим словом) и с Mathemati'кой (строил графики). Интересно посмотреть, как он будет считать.

Вот лучше матлаба я лично не знаю.

А какая там, у них, в FPU/GPU? Неужели про это нет книг и разбирать приходится на "живых" примерах. Так не охото идти в "Библиотеку имени Ленина" за книгой 1964 года "Вычислительная математика ЭВМ". У нас что с того времени книг не писали?

Есть. К примеру посмотрите в хелпе матлаба.

[zverek]

Вот лучше матлаба я лично не знаю.

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

[Methane]

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

Просто серьезно подойдите. Это все же язык программирования. Причем специфический.
Это не
x=x+1;
Это гораздо более высокий уровень.
x=0:0.001:pi*10;
Просто создали вектор. От 0 до pi*10 c шагом 0.001
y=sin(x);
сказали сделай вектор y члены которого будут синусами вектора х
z=tan(x.^9);
сделай вектор z, члены которого будут тангенсами в членов вектора x в девятой степени.
plot3 (x,y,z);
нарисуй все это (фигня получилась)
А можно использовать и фурье и фильтры и вообще что угодно. Короче кол-во ДИКОГО ГЕМОРРОЯ, матлаб сокращает просто грандиозно, где есть хоть какие-то расчёты.

[Гвоздик]

Спешу поправить на верное название зайлинксовской программы стыковки с "Матлабом", которую я использовал - "AccelDSP".

[Sergey'F]

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

1. Арифметика цифровых машин (М.А.Карцев)
2. Основы машинной арифметики (А.М.Шауман)
3. Arithmetic and Logic in Computer Systems (Mi Lu)
4. SYNTHESIS OF ARITHMETIC CIRCUITS: FPGA, ASIC, and Embedded Systems

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

И еще одна книга в духе 3 и 4:
Ergovac, Lang. Digital Arithmetic.

[Maverick]

Попытаюсь вставить свои пять копеек
У Xilinx есть CoreGenerator, который может сгенерировать готовый блок для работы с плавающей запятой по стандарту IEEE 754

[Methane]

Попытаюсь вставить свои пять копеек
У Xilinx есть CoreGenerator, который может сгенерировать готовый блок для работы с плавающей запятой по стандарту IEEE 754

Во--во. И этот мегакоребилдер скажет сколько тактов ему нужно с каким пайплайном, и вопрос про недостатки плавучки отпадет сам собой.

[Sergey'F]

Еще в тему. Мой студент на курсовом реализовал плавучку + и * практически в полном соответствии с IEEE-754, включая обработку субнормальных чисел и формирование всех флагов.

Результат для 32 бит в сравнении с Альтеровскими + и * для Cyclone III:

Altera:
+ :
183МГц, 11тактов, 950ЛЭ
* :
181МГц, 5 тактов, 279ЛЭ

Свой:
+ и * выполнены как один модуль, использующий некоторые совместные части:
105МГц, 5 тактов, 1643ЛЭ.

Целью было понизить число тактов сумматора за счет частоты, подогнав частоту под реально достижимую в процессоре Nios II для используемой платформы.

Самые ресурсоемкие блоки - сдвигатели для денормализации и нормализации.

Из 5 тактов последние 3 - это нормализация, денормализация, округление результата с формированием флагов. Это цена полной поддержки формата IEEE-754.

[Little_boo]

Попытаюсь вставить свои пять копеек
У Xilinx есть CoreGenerator, который может сгенерировать готовый блок для работы с плавающей запятой по стандарту IEEE 754

Floating-point 3.0?