[Oldring 0]

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

 

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

 

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

 

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

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

[ViKo 1]

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

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

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

[Maverick_ 15]

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

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

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

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

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

sortr.rar

[vadimuzzz 0]

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

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

[Maverick_ 15]

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

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

[sazh 3]

сильно понравилось

 

и пример наверно уже набросали.

[vadimuzzz 0]

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

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

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

[ViKo 1]

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

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

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

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

[vadimuzzz 0]

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

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

[ViKo 1]

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

[ViKo 1]

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

[vadimuzzz 0]

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

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

[Maverick_ 15]

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

как успехи?

[vadimuzzz 0]

как успехи?

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