Перейти к содержанию
    

поиск нескольких максимумов в массиве на FPGA

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

 

Могу подсказать где искать.

 

В 3-м томе Кнута есть раздел "сети сортировки".

 

И вот здесь вот глава 28

http://www.rsdn.ru/res/book/prog/basic_algorithms.xml

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Только циклов будет 3 * 5.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Реализация примерно та, что рассказывал ранее в этой ветке iosifk

Реализация на VHDL

Посмотри вложение. Там папка README, в которой найдешь описание и sreenshot работы, а файл test_shema.vhd - это TESTBENCH. Единственное замечание там описания для нахождения 16 максимальных значений и их координат в потоке, но думаю переделать для 3 максимальных значений не будет проблемой.

Надеюсь подойдет.

sortr.rar

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

если не сложно расскажите в 2-х словах, а в чем разница и преимущества.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

если не сложно расскажите в 2-х словах, а в чем разница и преимущества.

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

вот пример сортировки 16 значений за 9 тактов. вертикальная линия - компаратор (устройство с 2-мя входами и 2-мя выходами, переставляющее входные данные, если они не в заданном порядке)

sortn.jpg

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

вот пример сортировки 16 значений за 9 тактов.

Алгоритм - супер, но разве вам надо упорядочить все элементы массива? Если нет, то - бесполезная трата ресурсов.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Алгоритм - супер, но разве вам надо упорядочить все элементы массива?

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Да, можно удалить ненужные сравнения, которые не ведут к первым трем уровням. Кое-то упростится. Но перестановка каждой пары регистров - тоже отнимет немало ресурсов. Зато - быстро!

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

vadimuzzz, хотелось бы узнать, на чем Вы остановили свой выбор.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

vadimuzzz, хотелось бы узнать, на чем Вы остановили свой выбор.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

как успехи?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

как успехи?

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
К сожалению, ваш контент содержит запрещённые слова. Пожалуйста, отредактируйте контент, чтобы удалить выделенные ниже слова.
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...