Блог

Главная - Вопросы по программированию - Найти минимум в массиве чисел, используя Verilog для реализации приоритетной очереди

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

#arrays #comparison #verilog #priority-queue #system-verilog

#массивы #сравнение #verilog #приоритет-очередь #система-verilog

Вопрос:

Я довольно новичок в 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,-,-,-}

Ответ №1:

Простой подход, если у вас нет необходимости уменьшать количество вентилей или 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)

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

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

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

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

Комментарии:

1. Спасибо. Я обязательно прислушаюсь ко всем вашим предложениям. Я все еще не уверен в проблеме переупаковки очереди. Причина, по которой я играл с этой идеей, заключается в том, что это кажется «потраченным впустую пространством», если я не переупаковываю его в непрерывное хранилище.

2. будет ли это потрачено впустую, зависит от вашей политики перераспределения. Если вам не нужно отслеживать порядок, в котором объекты были поставлены в очередь, вы можете сохранить вектор допустимых / пустых битов для массива и выполнить поиск по нему, чтобы найти свободную запись. Это требует определенных затрат, но это намного дешевле, чем логика поиска минимального значения.

3. Массив пустых / полных записей звучит как действительно хорошая идея на самом деле. Возможно, я рассмотрю возможность реализации этого. На самом деле, все, о чем я забочусь, это удаление минимальной записи из очереди, поэтому на самом деле не имеет значения, где она расположена. Спасибо за помощь. Я действительно ценю это.

Ответ №2:

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

Комментарии:

1. sort метод используется для изменения массива с минимального на максимальный. Но я думаю, что здесь, в этом контексте, min метод более полезен для нахождения минимального числа.