[vadimuzzz 0]

с одним максимумом все вроде понятно: например, n-1 компараторов, если в массиве n элементов, можно конвейерами порезать. а как быть если надо, скажем 3 максимальных значения?

[iosifk 3]

с одним максимумом все вроде понятно: например, n-1 компараторов, если в массиве n элементов, можно конвейерами порезать. а как быть если надо, скажем 3 максимальных значения?

Ну так и в чем же проблема?

Ставим 3 схемы проверки. Если число больше первого, то оно заменяет первое и проходит на следующее сравнение. Если больше второго, то заменяет второе и проходит на третье сравнение. Итого при последовательном переборе чисел добавляются еще пара тактов для "проталкивания числа "вверх"". При этом я понимаю, что проверки идут по одному числу.

[des00 25]

Ну так и в чем же проблема?

Ставим 3 схемы проверки. Если число больше первого, то оно заменяет первое и проходит на следующее сравнение. Если больше второго, то заменяет второе и проходит на третье сравнение. Итого при последовательном переборе чисел добавляются еще пара тактов для "проталкивания числа "вверх"". При этом я понимаю, что проверки идут по одному числу.

кстати простой, однотактный код такой штуки приводился на этом форуме %) в теме про сортировку по возрастанию/убыванию %)

[bogaev_roman 0]

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

Конкретизируйте задачу

[des00 25]

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

отсортировать по возрастанию, за один проход. и не париться %)

[vadimuzzz 0]

посмотрел тему, про которую говорил des00, там как я понял примерно то же, что имел в виду iosifk. у меня немного не то (хотя, м.б. я сам себе проблему создал). данные читаются не последовательно, а сразу есть, скажем 32 отсчета (на портах). требуется за минимальное количество тактов (при этом не в ущерб Fmax) найти 3 максимума. перебирать элементы по одному неохота

[Oldring 0]

посмотрел тему, про которую говорил des00, там как я понял примерно то же, что имел в виду iosifk. у меня немного не то (хотя, м.б. я сам себе проблему создал). данные читаются не последовательно, а сразу есть, скажем 32 отсчета (на портах). требуется за минимальное количество тактов (при этом не в ущерб Fmax) найти 3 максимума. перебирать элементы по одному неохота

 

Написать полную сортирующую схему, взять три старших значения результата и позволить синтезатору самостоятельно выкинуть всё остальное?

[iosifk 3]

а сразу есть, скажем 32 отсчета (на портах).

Это что же более 200 - 400 пинов одновременно сравнивать? А скажем рассогласование приходов сигналов учитывается?

А еще и CDC???

[vadimuzzz 0]

Это что же более 200 - 400 пинов одновременно сравнивать? А скажем рассогласование приходов сигналов учитывается?

А еще и CDC???

нет, сигналы все внутри. собственно я немного наврал, последовательное чтение все-таки будет, но скорее всего в несколько потоков одновременно (несколько банков памяти). вот и не хотелось к контроллеру памяти логику наворачивать.

 

2Oldring:вариант с полной сортировкой может и приемлем, но я не знаю алгоритмов, которые хорошо параллелятся. не просветите?

[Serhiy_UA 1]

...перебирать элементы по одному неохота

Еще в студенчестве был курс "Специализированные вычислительные машины", а там был раздел по ассоциативным вычислителям. А в них работа со всеми данными сразу, правда, по одному биту в такт от каждого данного. Здесь можно высоко поднять тактовую частоту. Возможно, задача в самый раз для такого вычислителя.

Но, как всегда, правильная постановка задачи - половина ее решения, а задача не ясна...

[des00 25]

нет, сигналы все внутри. собственно я немного наврал, последовательное чтение все-таки будет, но скорее всего в несколько потоков одновременно (несколько банков памяти). вот и не хотелось к контроллеру памяти логику наворачивать.

отсортировать потоки, потом составить массив из 3 результатов для каждого потока и еще раз отсортировать %)

[vadimuzzz 0]

отсортировать потоки, потом составить массив из 3 результатов для каждого потока и еще раз отсортировать %)

а где гарантия, что все максимумы в одном потоке не окажутся?

ой, сорри, невнимательно прочитал. да, это пойдет )

[bogaev_roman 0]

В данном варианте смешанное решение будет, где-то потребуется вычислять максимум последовательно, где-то параллельно, кол-во уровней логики можно будет определить эксперементально. Можно вообще же все потоки разделить по 4 и выбрасывать минимальное значение на первых этапах (будут оставаться 3), а потом уже последовательно выбрать максимумы.

[ViKo 1]

данные читаются не последовательно, а сразу есть, скажем 32 отсчета (на портах). требуется за минимальное количество тактов (при этом не в ущерб Fmax) найти 3 максимума. перебирать элементы по одному неохота

Если пытаться сделать схему, параллельно сравнивающую все отсчеты между собой, никакой ПЛИС не хватит. 32 * 31 = 992 (с самим собой сравнивать не нужно).

Или же разбить схему сравнения на несколько ступеней. Сначала - соседние сравнить (16 сравнений) , потом - те, что остались (8), потом ... (4) (2). И это только для одного результата.

Остается - последовательно:

Имеем 3 регистра. В первый заносим первый отсчет. Если следующий отсчет больше первого, заносим новый, а то, что было, передвигаем во второй. Если следующий отсчет больше второго, заносим его вместо второго, а то, что было, передвигаем в третий. И т.д., и т.п.

p.s. первый расчет - неверный, маху дал. Пополам еще поделить.

Изменено 23 марта, 2010 пользователем ViKo

[vadimuzzz 0]

Или же разбить схему сравнения на несколько ступеней. Сначала - соседние сравнить (16 сравнений) , потом - те, что остались (8), потом ... (4) (2). И это только для одного результата.

это я и имел в виду в первом посте, такая схема мне нравится, но не знаю как ее расширить на 3 макс.

Остается - последовательно:

Имеем 3 регистра. В первый заносим первый отсчет. Если следующий отсчет больше первого, заносим новый, а то, что было, передвигаем во второй. Если следующий отсчет больше второго, заносим его вместо второго, а то, что было, передвигаем в третий. И т.д., и т.п.

мне не нравится слово "последовательно". 3-5 тактов - идеал