Найти минимум в массиве чисел, используя Verilog для реализации Priority Queue - PullRequest
Новая
       24

Найти минимум в массиве чисел, используя Verilog для реализации Priority Queue

1 голос
/ 26 апреля 2011

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

РЕДАКТИРОВАТЬ: На самом деле я делаю приоритетную очередь. У меня реализована функциональность очереди, но вместо того, чтобы возвращать то, что находится в начале очереди, я хочу вернуть запись с наименьшим значением и сохранить непрерывное хранилище. 

e.g. {2,3,4,1,5,6,-,-} 
min is 1 --> {2,3,4,-,5,6,-,-} 
Rearrange so everything following the returned min is moved to the index preceding it-->
{2,3,4,5,6,-,-,-}

Ответы [ 2 ]

1 голос
/ 26 апреля 2011

Простой подход, если у вас нет необходимости сокращать количество вентилей или LUT, состоит в реализации древовидной структуры.

Если в очереди есть записи A0, A1, ... A7, выполните следующие действия:

  1. вычислить B0 = min (A0, A1), B1 = min (A2, A3), B2 = min (A4, A5), B3 = min (A6, A7)
  2. вычислить C0 = min (B0, B1), C1 = min (B2, B3)
  3. вычислить D = min (C0, C1)

На каждом шаге также передавайте индекс любой записи, которая меньше.

Для этого требуется доступ ко всем данным одновременно, поэтому подразумевается, что все хранилище находится в триггерах, а не в ОЗУ.

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

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

0 голосов
/ 26 апреля 2011

SystemVerilog предоставляет метод sort для массивов. См. «Методы упорядочения массивов», раздел 7.12.2 в стандарте IEEE 1800-2009.

...