@Ромуальд_7

Всем доброго времени суток!
Прошу прощения, если пишу не совсем в ту ветку, но такой вопрос только начинающий задать и может
Смотрите, есть некоторый алгоритм, совершающий кучу тригонометрических операций, который, упростив, можно представить так:
Здесь упрощено очень многое, но суть осталась — на вход подаётся четыре переменные, с ними производится туча операций, в результате которых находится две других, и, после их проверки, вырабатывается сигнальное значение, сообщающее о пригодности этих двух значений. Дело в том, что в теле этого алгоритма производится такая туча тригонометрических операций, что пятигигагерцовому ядру процессора становится плохо, и он успевает рассчитать всего тысячу входных «квадриплетов» за секунду. (Алгоритм оптимизирован донельзя, но это не суть.)

В чём, собственно, вопрос — не могли бы вы дать какую-нибудь наводку (или помочь иначе) на материалы, которые нужно изучить, чтобы «ручками» собрать аналогово-цифровую схему, реализующую приведённый выше алгоритм, например? Как известно, аудиокодек, видеокарта и математический сопроцессор (ну, и ещё куча вещей) появились именно ввиду неэффективности универсальных вычислителей в некотором спектре задач, следовательно, можно любой алгоритм переложить на «железку», которая только его инструкции и будет выполнять; скажите, пожалуйста, если я не прав
Я думаю, что это должна быть не ПЛИС, ведь целью я ставлю предельное увеличение скорости расчётов за счёт именно фиксированного функционала (микро)схемы, но я просто-напросто не знаю, что именно искать в интернете (есть ли какой-то модуль «синус», например, и так далее).
Ну, и, конечно, есть у меня подозрения, что точность double удержать может не получиться, и все расчёты пойдут насмарку по причине физики (помехи, наводки, отклонения номиналов компонентов схемы). Если всё то, что я описываю, сомнительно хотя бы поэтому, то стоит ли экспериментировать вообще?

Большое спасибо за любые разъяснения и помощь!

Добавлено через 2 минуты
P.S. Как я вообще вижу работу с этой «железкой» — на вход поступают цифровые данные, которые ЦАПом приводятся к виду напряжений на входных контактах, схема эти напряжения преобразует, компаратор реализует условный оператор, схема формирует напряжения на выходных контактах, и АЦП возвращает это счастье обратно в цифровое представление.

0

@qbfan

Сопоставить a,b,c,d целые значения в диапазоне от 0 до 255, и для всех этих значений
просчитать таблицу результатов. Правда таблица получается 4 мерной, но современные
компьютеры вполне должны потянуть. В любом случае аналоговая схема не даст точность
выше 3 значащих цифр (т е никак не double).

Добавлено через 8 минут
Упрощённый способ: заменить обращение к sin cos asin acos предвычисленными таблицами -
тоже должно хорошо работать.

0

@VTsaregorodtsev

Как минимум тут - косинусы считать не нужно.

sin(a)*cos(b) = (sin(a-b)+sin(a+b))/2

sin^2(c)*cos^2(d) = (sin(c-d)+sin(c+d))^2 /4

Т.е. получаем atan( 2(sin(a-b)+sin(a+b)) / (sin(c-d)+sin(c+d))^2 )

Вроде бы не ошибся.
Пробуй преобразовывать дальше/иначе - вдруг таки получится из пяти (2 тригонометрических и 3 обратных тригонометрических) функций оставить меньшее их число. А то пока косинус ещё возникает в дальнейшем, при вычислении игрека.
Но это м.б. полезно только для упрощения аппаратной реализации, если железяка будет способна выдать нужную точность. В точность аналоговой железяки я не верю - только в цифровую.

0

@Ромуальд_7

qbfan, понял Вас, спасибо!
Но тут дело-то в чём - предвычисленные таблицы работают очень плохо в смысле соотношения "точность/размер хранимых данных". Взять ту же таблицу Брадиса - классно, но не достичь точности double даже с невероятно большой таблицей. Хочу сказать, что я пробовал этот подход, но в месте, где результаты этого алгоритма используются, регулярно происходили ложные срабатывания (и несрабатывания); жёстко требуется точность, как минимум, 12 знаков (отладка показала).
Хорошо, аналоговый способ не пройдёт. А что скажете по поводу цифрового подхода?
Благодарю Вас за труды, но, как я упоминал, это прикидочный алгоритм, который я писал почти что "от балды"; настоящие методы предельно оптимизированы (ещё 30 лет назад), но, и с этим ничего не поделать, подразумевают кучу тригонометрических неприводимы/несокращаемых операций. Геодезия это, одним словом.
Ну вот а я вообще слабо понимаю, о чём говорю А что по поводу цифрового пути можете сказать?

0

@Aledveu

пока очень сомнительно выглядят требования к точности и производительности.
а вот это ещё более сомнительно. вы на интерпретаторе это делаете ? или эмулируете плавающую точку ?
или у вас специальная математическая библиотека для тригонометрии ?

0

@Ромуальд_7

Так я ж и говорю, что в целом плохо понимаю, о чём спрашиваю. Мне бы понять, что вообще можно и как, а там уж и с требованиями разберёмся.
Нет, я использую православный Си-крест-крест со стандартной библиотекой математики. Как я и писал, я всё сильно упростил в описании, поскольку разбор стоящей над этим вопросом задачи - не цель самого вопроса. Я предлагаю вообще не думать в этом направлении. Я хочу поэкспериментировать, совместив приятное (некоторое увлечение электроникой) и полезное ("разработка железки", решающей проблемную часть большого алгоритма), поэтому и прошу, по большому счёту, какую-нибудь теорию по теме предмета обсуждения (вот что это вообще за тема? "Разработка ИС"?).

0

@u235

Это вообще-то кусочно-линейная функция..

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

1

@Aledveu

мы поскольку не знаем что у вас за задача то и посоветовать что-то адекватное трудно.
может у вас там всё так плохо с оптимизацией кода что так медленно - кто же знает.
вот вы говорите что вам надо double, а где расчёты деградации точности при сложной обработке?

могу поделиться своим опытом - понадобилась мне как-то сделать прецизионный датчик и там надо было оцифровывать аналоговый сигнал (16 бит ацп на большой скорости) а потом ещё несколько цифровых фильтров и потом матричные преобразования. так вот мат ан сильно помог упростить задачу и так же всё сделать на целочисленной арифметике а не в плавающей точке. в результате небольшая cpld и stm32 прекрасно справились с задачей.

не хотите (или не можете) сказать что за задача - ну так начните разрабатывать ис.
скорее всего начнёте с того чтобы сделать всё сначала на плис, (сколько бюджет? сколько сейчас комплект разработчика - 100-200 т)
потом когда отладите на плисине можно делать асик (ещё бюджет + ещё 2-4 нолика)

1

@Ромуальд_7

u235, спасибо Вам большое, но
Я же написал, что это просто абстрактная "модель" другого большого неоптимизируемого (физически и математически там уже некуда) кода, и я хотел бы чтобы сообщество не помогло мне сократить число операций, а показало бы, как вот прям это можно в железку запихнуть.

Добавлено через 21 минуту
Я Вас уверяю - там всё отлично. Правда отлично. Просто есть задачи, для которых быстрее не получится. Как, например, интегрирование - у Вас может быть хоть стоядерный процессор, но это ускорит интегрирование ровно в 1 раз. Расчётов нет, но есть фактические данные. В C++-реализации в момент финальной проверки выполняемости условия равенства нулю некоторой переменной оказывается, что в ряде случаев там не ноль уже в пятом знаке, и это при double'ах-то. И всё бы не так страшно, но есть ситуации, когда "не ноль в пятом знаке" - не ошибка, и такое нужно пропустить, а не отбросить.
Звучит здорово. Я сылшал про целочисленное интегрирование, которое в ряде случаев работает лучше "обычного". Однако я мало представляю, как именно это применить к тригонометрии.
Так вот а что значит-то это словосочетание?) С чего начать-то?)
А зачем? Чем ЦП - не ПЛИС? Если говорить о программируемых микросхемах, то, по-моему, ничего лучше уже существующей программы я не получу (с точки зрения производительности).
Исходя из сумм, которые Вы упомянули, не хотите ли Вы сказать, что моя задумка - развлечение для богатых? Я-то думал, что есть какие-то стандартные подходы (а-ля конструктор), которые могут позволить относительно быстро и недорого накидать на большой макетке прототип - "макро"схему. Я очень сильно заблуждаюсь?

0

@Aledveu

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

Сейчас плис как раз и применяют когда надо сделать устройство которое перемалывает данные - не надо тратиться на заказные ИС и можно все отладить. если надо устройство - то можно взять готовый комплект разработчика и на нём сделать прототип прежде чем что-то паять.

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

1

@u235

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

1

@Ромуальд_7

Интерееееесно. Я всегда ассоциировал ПЛИС с теми же Arduino или STM. Внимательно изучу вопрос, спасибо!

Исключительно в целях заботы о Вас же Там 600 (+/-) строк кода (это без комментариев к нему; с ними - под 1000) - только людей мучить.
А задача там звучит просто - обработка спецданных на геоиде. Все алгоритмы хорошо изучены и оптимизированы довольно давно. Мой алгоритм берёт всё это счастье и производит проверку с последующей обработкой. Вот эту проверку я и хотел попытаться ускорить аппаратно. Здесь ситуация как в компьютерной графике - нарисовать ВСЮ сцену бывает быстрее, чем вычислять, что нужно рисовать, а что - нет; вот у меня такая же условно-нерешаемая иначе задача.

0

@Aledveu

вот что непонятно - в той функции которую вы прдставили в 1 посте - там есть состояние?
что мешает параллелить вычисления ?

0

@Ромуальд_7

Не совсем понимаю вопрос; перефразируйте, пожалуйста.
Да ничего, наверное, если Вы имеете в виду то, что можно было бы подавать массивы a,b,c,d и получать результирующие массивы. Так я и предполагал использовать эту штуку, в целом.

0

@Aledveu

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

0

@Ромуальд_7

Так это не решает проблемы-то Это всё-равно огромное число операций на процессоре, к тому же, компилятор (и его платформа, соответственно) тоже вносит смуту в происходящее (но это другая история).
Мне просто интересно, как именно происходит проектирование и создание "железки", невероятно быстро выполняющей один-единственный алгоритм. Всё остальное, я считаю, обсуждать бессмысленно

0

@Aledveu

для начала выбирается принципиальная компоновка системы :
1)эта железка вставляется в компьютер как плата расшширения в pci-e ? -
минимальное масштабирование системы и максимальная сложность.
Даже если взять готовую плату, то придётся самому писать программу драйвера ОС ибо операционка вас не допустит к железу )) , самому писать программу управления для ПК, самому писать что будет делать плисина - а это код ускорителя на HDL, скорее всего микроконтроллер для управления, и к нему код. Итого три совершенно разные софтины + разработка аппаратной части.
2)эта железка подключается через USB ? - допускается некоторое масштабирование, немного легче чем 1
3)Эта железка подключается через ethernet ? - масштабируется легко, немного легче чем 1

для 2 и 3 - уже можно обойтись без драйвера для ОС ))

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

но я бы сказал так что если вы ранее не делали ничего подобного, но очень хотите туда полезть - придётся начинать с чего пороще, делать кучу прототипов чтобы просто работало. и это потребует много времени и сил и средств.
судя по вашим вопросам, отсутствию внятного ТЗ и отсутствию описания ваших попыток посчитать на GPU - вы в начале пути.

2

@Ромуальд_7

Точно так, да. Скорость обмена данными критична, я полагаю.
Это я понимал с самого начала, да Не знаю, готов ли я к этому, но ..
А USB и Ethernet - это не наш метод
А они были и закончились успехом, кстати говоря. Но мне мало
В целом, я же поэтому и написал в ветку "электроника для начинающих".
Большое спасибо Вам за помощь! Теперь у меня хотя бы есть представление о том, куда копать.

0