우선 순위 큐 구현을 위해 Verilog를 사용하여 숫자 배열로 찾기

Question

저는 Verilog의 초심자입니다. 그러나 16 개 요소의 배열을 가지고 있으며 (각 요소는 16 비트 길이입니다) 최소 항목을 찾고 싶습니다. 배열을 반환하고, 최소값을 반환하고, 배열이 하나의 인접한 항목 블록이되도록 최소 이후의 배열에있는 모든 항목을 다시 배열합니다. 비교기를 사용해야한다는 것을 알고 있지만 많은 수의 그룹을 비교하고 최소값을 결정하는 것과 관련하여 어디에서 시작해야할지 모릅니다.

편집 : 내가 실제로 만들고있는 것은 우선 순위 대기열입니다. 구현 된 큐 기능이 있지만 큐의 머리 부분에있는 값을 반환하는 대신 가장 작은 값으로 항목을 반환하고 저장소를 연속적으로 유지하려고합니다. 당신이 문 또는 LUT를의 수를 줄이기 위해 압력이없는 경우

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,-,-,-} 

Answer 1

간단한 방법은, 트리 형 구조를 구현하는 것입니다.

큐의 엔트리는 A0, A1, ... A7이 경우 수행 다음 단계

1. 계산 B0 = 분 (A0, A1), B1 = 분 (A2, A3) D0 = min (C0, C1) 계산 : C0 = min (B0, B1), C1 = min (B2, B3)
2. 계산 D = min (C0, C1)

각 단계마다 작은 항목의 색인을 따라 전달하십시오.

이렇게하려면 모든 데이터에 동시에 액세스해야하므로 전체 저장소가 RAM이 아닌 플립 플롭에 있음을 의미합니다.

모든 데이터가 플립 플롭에 있다고 가정하면 재 포장은 너무 어렵지 않고 저장소의 다음 상위 항목의 각 항목을 조건부로로드하기위한 논리를 만들고 제거되는 요소의 색인을 디코딩합니다 제거되는 요소 위의 각 항목에 대해 shift-down을 활성화하는 벡터.

비교할 때 대기열 또는 대기열에서 대기하는지 비교할 것인지를 결정할 수 있습니다. 각 dequeue 이후에 repacking이 실제로 필요한지 여부를 고려할 수도 있습니다.

Answer 2

SystemVerilog는 배열에 대해 sort 메서드를 제공합니다. IEEE Std 1800-2009의 "Array ordering methods"섹션 7.12.2를 참조하십시오.