[Arranje 0]

Не подскажите как можно в Verilog Hdl работать с дробями или вещественными числами? Мне нужно реализовать СЛАУ методом Гаусса, только вот как я понял без этих вещей там не обойтись, или как то можно?))

 

Если тебе нужно 4 знака пояле запятой, то можно воспльзоваться числами с фиксированной точкой. Написать отдельный модуль - "Делитель", которому на вход подаются 2 32х разрядные и на выходе 1 32 разрядное(как его реализовать, можно поискать в гугле по ключевым словам "ALU деление" или "АЛУ деление" (тебе выдадут ссылки на рзличные реффераты + книги, этого должно хватить) а также вот http://electronix.ru/forum/index.php?showtopic=58400 (тут преведенны отдельные ссылки на другие темы + книги). Работать такой делитель возможно будет несколько тактов. Реализовать подобный делитель, всё равно что реализовать деление для 2х целых. Деление можно проводить стандартно - столбиком.

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

 

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

 

В целом по задаче, хотел бы посоветовать реализовывай модифицированный метод Гаусса - дели не на первый аргумент, а на максимальный в строке. Такой подход (если не изменяет память) 100% обеспечит сходимость.

100 на 100 -вобще говоря небольшая матрица (Гаусс должен осилить). 100 переменных - это приблизительно 100 элементов электрической схемы. Для решения нужно проделать 5000 операций деления, бОльшая часть из которых может быть проделанна в параллель - для первый строки 99, для второй 98 и т.п. Всего 100 циклов деления, если влезет 100 "делителей".

 

мне нужно чтобы синтезировалось с очень хорошей частотой

Какова максимально возможная глубина комбинационной логики?

Изменено 6 февраля, 2009 пользователем Arranje

[cdg 4]

Не подскажите как можно в Verilog Hdl работать с дробями или вещественными числами? Мне нужно реализовать СЛАУ методом Гаусса, только вот как я понял без этих вещей там не обойтись, или как то можно?))

А чисто академический интерес - почему именно Гаусс ? не самый оптимальный с точки зрения быстродействия метод, особенно для матриц большого размера.

[Kadaj 0]

Всем спасибо за ответы, буду пробовать.

 

2Arranje что касается логики, то я расчитываю уложиться в 90000 логических эелементов(работаю на альтере), можно наверно и больше. Смотря какие у них есть устройства. Или я не правильно понял вопрос?)

 

2cdg Мне сказали Гаусса поэтому делаю Гаусса. А какие методы более эффективны для больших размерностей? Если они будут и эффективней и проще, то я возможно стану делать его)

[Arranje 0]

Всем спасибо за ответы, буду пробовать.

 

2Arranje что касается логики, то я расчитываю уложиться в 90000 логических эелементов(работаю на альтере), можно наверно и больше. Смотря какие у них есть устройства. Или я не правильно понял вопрос?)

 

2cdg Мне сказали Гаусса поэтому делаю Гаусса. А какие методы более эффективны для больших размерностей? Если они будут и эффективней и проще, то я возможно стану делать его)

 

Нет, меня скорее интересует глубина логики - то есть максимально возможное число подряд идущих вентилей, расположенных между 2мя регистрами (глубина асинхронной части,) - поясню к чему этот вопрос. Вы сказали, что хотели бы развести свою схему на "хорошую чатсоту". Для каждой ПЛИС такая "хорошая" частота может быть своей, а то что вы понимаете под "хорошей" может быть недостежимо на той ПЛИС на которую вы будете разводить. Вот эта тактовая частота и определяется глубиной асинхронной части - чем больше последовательно соединённых вентилей, тем больше задержка, тем больше должен быть период тактового сигнала и тем ниже частота.

Сейчас Альтера анонсировала Stratix IV и уже доступны образцы определённой модели, в которой 228 тыс эквивалентных логических вентилей (91 тыс "попугаев" ALM).

 

Помимо точных методов (коим является метод Гаусса), есть итерационные метода, такие как метод Гаусса-Зейделя, если не ошибаюсь, Ньютона и прочие(можно легко взять любой учебник по Численным методам или вычислительной математике - и посмотреть часть про СЛАУ).

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

Среди точных методов ещё есть метод Краута (Краммера).

 

Повторюсь ещё раз, вроде бы матрица 100 на 100 считается "маленькой" и должны быть по силам Гауссу. Однако если потом от вас потребуют 10^5 x 10^5 вот тут Гаусс начнёт загибаться.

 

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

Изменено 6 февраля, 2009 пользователем Arranje

[yes 5]

Задача не совсем академическая, скорее научная, так что real не подходит, мне нужно чтобы синтезировалось с очень хорошей частотой, потом придется еще конвейер делать. А можно по подробней насчет векторов. Там же при домножении дроби получаются, как с ними быть?)

 

ну так работайте с плавающей точкой - математические сопроцессоры на верилоге описываются.

представление вещественных чисел в виде битов описано в IEEE-754 (как вариант, можно взять)

 

 

 

 

В целом по задаче, хотел бы посоветовать реализовывай модифицированный метод Гаусса - дели не на первый аргумент, а на максимальный в строке. Такой подход (если не изменяет память) 100% обеспечит сходимость.

 

100% только в сбербанке :)

если матрица вырожденая, то есть ее ранг меньше количества неизвестных - никакая оптимизация не поможет.

ну и термин "сходимость" по-моему не применим к алгоритму Гаусса, так как алгоритм требует конечное число операций независимо от значений коэффициентов (время зависит только от размера матрицы)

[Arranje 0]

Задача не совсем академическая, скорее научная, так что real не подходит, мне нужно чтобы синтезировалось с очень хорошей частотой, потом придется еще конвейер делать. А можно по подробней насчет векторов. Там же при домножении дроби получаются, как с ними быть?)

Как сформулирована задача. Какова постановка?

 

"Исследовать принципиальную возможность реализации решения СЛАУ методом Гаусса в ПЛИС" или "исследовать принципиальную возможность ускорения решения СЛАУ методом Гаусса в ПЛИС".

 

100% только в сбербанке

если матрица вырожденая, то есть ее ранг меньше количества неизвестных - никакая оптимизация не поможет.

ну и термин "сходимость" по-моему не применим к алгоритму Гаусса, так как алгоритм требует конечное число операций независимо от значений коэффициентов (время зависит только от размера матрицы)

 

Да, как-то вырожденные случай мне в голову не пришёл. Но в этом случае вам не поможет ни один из методов решения СЛАУ. Подходя к задаче я имел ввиду, что система по умолчанию совместная и определенная. Но в целом согласен с поправкой.

 

термин "сходимость" по-моему не применим к алгоритму Гаусса

Так оно и есть. Наверно нужно говорить об устойчивости, но наверное лучше говорить про точноть и погрешность)

Изменено 6 февраля, 2009 пользователем Arranje

[Kadaj 0]

Как сформулирована задача. Какова постановка?

 

"Исследовать принципиальную возможность реализации решения СЛАУ методом Гаусса в ПЛИС" или "исследовать принципиальную возможность ускорения решения СЛАУ методом Гаусса в ПЛИС".

Скорее второй вариант, мне нужно реализовать Гаусс, с частотой не менее 100мгц, чтобы одна итерация выполнялась за 1 такт. Под итерацией подразумевается умножение и сложение ведущей строки с ведомой. Т.е итерация это зануление элемента который находится под ведущим. Хотя если честно даже не знаю, может лучше сделать 1 итерация - зануление всех элементов которые находятся под ведущим. Вобщем есть над чем подумать. Вобщем мне нужно реализовать как можно более быструю схему. Чем быстрей тем лучше)

Изменено 6 февраля, 2009 пользователем Kadaj

[Jools 0]

А почему методом Гаусса?

 

В аппаратуре лучше использовать алгоритмы основанные на QR- LU- и т. д. разложениях матриц. Смотрите Голуба "Матричные вычисления".

 

 

А это:

"Исследовать принципиальную возможность реализации решения СЛАУ методом Гаусса в ПЛИС" или "исследовать принципиальную возможность ускорения решения СЛАУ методом Гаусса в ПЛИС".

 

хотя бы переформулировать так:

"Проблемы (или Экономическая целесообразность) проектирования системы решения СЛАУ методом Гаусса в современных ПЛИС."

 

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

 

Ваши требования (хоть с floating point, хоть и с fixed point) невыполнимы на современных ПЛИС. Даже не просто невыполнимы - это просто фантастика.

[alexr22b 0]

Мда, матрица 100х100 на 90000 LE и 100 mhz и 4 (десятичных ?) знака после запятой это тяжко. Интуиция подсказывает что вы ошиблись на пару порядков либо в LE либо в Mhz.

Для ПЛИС как вам уже сказали нужно QR/LU, смотрите также Givens Rotation. http://en.wikipedia.org/wiki/Givens_rotation

[Kadaj 0]

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

[Jools 0]

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

 

Если Вам нужна тактовая частота 100 MHz - то ваш однотактовый делитель чисел с плавающей точкой из области научной фантастики в ближайшие лет 10 точно. :rolleyes:

 

Если Вы хотите придумать что-то стоящее по решению уравнений матричным способом на ПЛИС или DSP, то смотрите в сторону целочисленной арифметики и операций умножения и сложения. На сегодня не существует решений для реализации в аппаратуре лучше основанных на QR- (и подобных) разложениях матриц.

 

Метод Гаусса (если мне не изменяет память) имеет вычислительную сложность O^3, основанные на разложениях матриц алгоритмы O^2.

Сложности O^1 вроде еще никто не предложил - может есть смысл исследовать эту нишу ? Подумаете - Вращения Гивенса, Отражения Хаусхолдера, разложения Холецкого и, наконец, разложения Kadaj'a :)

Звучит !!!

[Kadaj 0]

Если Вам нужна тактовая частота 100 MHz - то ваш однотактовый делитель чисел с плавающей точкой из области научной фантастики в ближайшие лет 10 точно. :rolleyes:

Ясно, получается эта статья полный бред?) Там видимо обычные теоретические выводы человека которые лишь в теории знаком с Плис. Вообще получается что самая быстрая реализация получится на 4 ядерном универсальном процессоре?)

[Jools 0]

Ясно, получается эта статья полный бред?) Там видимо обычные теоретические выводы человека которые лишь в теории знаком с Плис.

 

Нет, возможно не бред, но выкладки теоретические. Насколько я понял (смотрел бегло) здесь они как- то хитро ( я не математик) ушли от операции деления и не используют плавающую точку. Вообщем становиться не "чистый" Гаусс, а какой-то иной алгоритм, преобразованный к сложности O^2 и использующий в основе операции умножения и сложения. Суть я не разбирал, было бы стоящее - уже опубликовали бы в IEEE или запатентовали.

 

 

По-моему, главным в этой работе было бы сравнение полученного ими результата с результатами полученными с помощью уже известных алгоритмов сложности O^2. Чего в этой статье не наблюдается. Делайте выводы сами.

 

Вообще получается что самая быстрая реализация получится на 4 ядерном универсальном процессоре?)

Немогу сказать. Но при использовании алгоритмов основанных на разложении матрицы разгон тоже получается большим - попробуйте погуглить QR decomposition systolic array

[cdg 4]

Всем спасибо за ответы, буду пробовать.

 

2Arranje что касается логики, то я расчитываю уложиться в 90000 логических эелементов(работаю на альтере), можно наверно и больше. Смотря какие у них есть устройства. Или я не правильно понял вопрос?)

 

2cdg Мне сказали Гаусса поэтому делаю Гаусса. А какие методы более эффективны для больших размерностей? Если они будут и эффективней и проще, то я возможно стану делать его)

Если не изменяет память (давненько это было....) есть алгоритмы для матриц большой размерности, так называемые блочные методы, используются различные способы приведения матрицы к блочно-диагональному виду, эффективно применялись для матриц размерности 100x100 и больше, в киевском политехе в свое время усиленно муссировали эту тему, там обращали матрицы порядка 10_000x10_000, что было необходимо при моделировании аналоговых процессов в кристале, конечно если исходная матрица совсем общего вида, то прийдется туго.... В любом случае необходимо посчитать количество операций умножения, деления для разных методов, уже подзабыл, но нет уверенности что Гаусс окажется проще, чем нахождение обратной матрицы. Успехов.