비트 트위 틀링으로 라운드 로빈 스케줄링에서 다음을 찾습니다
https://stackoverflow.com/questions/480405
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
다음 문제를 고려하십시오. 한 번의 인코딩에서 현재 예정된 슬레이브를 나타내는 비트 스트링이 있습니다. 예를 들어, "00000100"(가장 왼쪽 비트가 #7이고 가장 오른쪽 #0)은 슬레이브 #2가 예정되어 있음을 의미합니다.
이제 나는 라운드 로빈 스케줄링 체계에서 다음 예정된 슬레이브를 트위스트로 선택하고 싶습니다. 나는 어떤 노예들이 실제로 예약을 원한다고 말하는 "요청 마스크"가 있습니다. 다음 노예는 원하는 사람들 에게서만 선택됩니다.
일부 예제 (라운드 로빈 스케줄링이 왼쪽으로 회전하여 수행된다고 가정). 예제 1 : 예제 1 : 예제 1 : 예제 1 : : 예제 1 : : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제 1 : 예제.
- 현재 : "00000100"
- 마스크 : "01100000"
- 다음 일정 : "00100000" - 정상적인 라운드 로빈에서 #3과 #4는 #2 이후에 와야하지만 요청하지 않으므로 #5를 선택합니다.
2 : 예제 2 : 예제 2 : 예제 2 : : 예를 2 : 예를 실시 예제 2 : : : : : : : 예제 2 : : : 예제 2 : : : 예제 2 : : 예제 2 : 예제 2 : 예제 2 : 예제 2 : 예제.
- 현재 : "01000000"
- 마스크 : "00001010"
- 다음 : "00000010" - 스케줄링은 사이클링 왼쪽으로 이루어지고 #1은 그 순서대로 첫 번째 요청 노예이기 때문입니다.
이제 이것은 루프로 쉽게 코딩 할 수 있습니다. 그러나 나는 실제로 루프없이 약간의 widdling 작업으로 결과를 얻고 싶습니다. 동기 부여 : vhdl/verilog의 하드웨어 (FPGA)에서 이것을 구현하고 싶습니다.
보너스는 모든 노예 N에 대해 일반적인 알고리즘을 구성하는 것입니다.
그건 그렇고, 이것은 숙제가 아닙니다. 어떤 방식으로 노예를 예약하고 싶을 때마다, 노예의 요청에 따라 일정을 조정할 때마다 중요한 문제입니다. 내 현재 솔루션은 다소 "무겁다"고 분명한 것을 놓치고 있는지 알고 싶었습니다.
해결책 2
Altera Advanced Synthesis Cookbook에서 작업을 구현하기위한 다음 Verilog 코드를 찾았습니다.
// 'base' is a one hot signal indicating the first request
// that should be considered for a grant. Followed by higher
// indexed requests, then wrapping around.
//
module arbiter (
req, grant, base
);
parameter WIDTH = 16;
input [WIDTH-1:0] req;
output [WIDTH-1:0] grant;
input [WIDTH-1:0] base;
wire [2*WIDTH-1:0] double_req = {req,req};
wire [2*WIDTH-1:0] double_grant = double_req & ~(double_req-base);
assign grant = double_grant[WIDTH-1:0] | double_grant[2*WIDTH-1:WIDTH];
endmodule
그것은 뺄셈을 사용하지만 (한 번만) 개념적으로 Doug의 솔루션과 매우 유사합니다.
다른 팁
루프는 나쁘지 않아도됩니다.
나는 단순히 할 것이다
current[i] = current[i-1] & mask[i] | // normal shift logic
mask[i] & current[i-2] & !mask[i-1] | // here build logic
... // expression for
// remaining
그런 다음 생성 루프에 넣습니다 (즉, 하드웨어로 풀려날 것입니다). 이는 표현식에 병렬 하드웨어를 생성합니다.
여기에서 언급 된 다른 솔루션은 여러 "-"를 사용합니다. 나는 당신에게 정말로 비싼 작업을 할 수 있기 때문에 그들을 낙담시킬 수 있습니다. ESP. 하나의 뜨거운 경우, 당신은> 32 비트 이상을 쉽게 얻을 수 있습니다. 32 비트는 HW에서 쉽게 구현할 수 없습니다. 차용은 모든 비트를 통과해야하기 때문에 (특정 FPGA의 죽은 캐리 로직으로 인해 적은 수의 비트에 접근 할 수 있습니다).
다음 솔루션은 모든 노예 (k)에 대해 작동하며 FPGA의 O (N)입니다. 현장의 각 비트마다 3 개의 논리 게이트와 2 개의 인버터가 필요합니다. 기본 논리 시뮬레이터로 개념을 테스트했으며 작동합니다.
논리 게이트의 체인 현재의 그리고 마스크 본질적으로 체인에서 "아래쪽 아래로"비트를 선호하는 우선 순위 시스템을 만듭니다. 이 체인은 끝에서 반복되어 있지만 현재의 비트는 체인을 깨는 데 사용됩니다.
작업을 시각화하려면 비트를 상상해보십시오 3 에 설정되어 있습니다 현재의 필드와 다이어그램의 신호를 아래쪽으로 따라갑니다. 논리적 인 것 3 입력에 첫 번째 및 게이트에 논리 0을 배치하여 해당 및 게이트의 출력도 0이 될 것입니다 (여기 또는 게이트 체인이 깨진 곳). 첫 번째와 게이트의 출력에서의 0은 하나를 두 번째와 게이트로 입력에 배치합니다. 이것은 조금 만듭니다 2 의 다음 비트에 직접 의존합니다 2 의 마스크.
이제 또는 게이트의 체인이 작용합니다.
비트 2 의 마스크 정해진 곳에서 OR 게이트의 논리적 출력은 왼쪽으로 직접 출력되며, 논리적 인 출력은 논리적 인 입력에 입력 및 비트 아래의 게이트에 배치됩니다. 2 의 현재의 (단 한 번만 현재의 한 번에 설정할 수 있습니다). 상단과 게이트의 출력에있는 논리적 인 것은 하단과 게이트의 입력에 논리적 0을 배치하므로 비트를 설정합니다. 1 의 다음 0과 같습니다.
비트 2 의 마스크 설정되지 않았으며, 또는 게이트에 대한 입력은 모두 0이므로 비트 아래의 게이트의 출력 2 의 현재의 입력에 하나를 하단과 게이트에 넣고 비트를 만드는 0입니다. 1 의 다음 비트에 의존합니다 1 의 마스크.
이 논리는 왼쪽에서 오른쪽으로 돌아 오는 비트를 "위로"또는 게이트의 체인을 따릅니다. 다음 하나로 설정할 수 있습니다. 루프가 비트로 되돌아 가면 루프가 중지됩니다. 3 의 현재의, 그 비트가 설정된 결과. 이렇게하면 회로가 영구적 인 루프로 유지되는 것을 방지합니다.
Verilog 또는 VHDL에 대한 경험이 없으므로 실제 코드를 귀하에게 맡길 게요 그리고 나머지 stackoverflow.
대체 텍스트 http://img145.imageshack.us/img145/5125/bithifterlogicdiagramkn7.jpg
메모:
- 이 솔루션은 부분적입니다. 비트 필드를 유지하려면 여전히 일종의 래칭 메커니즘이 필요합니다.
- 비트 수를 늘리면 게이트 전압에 필요한 시간도 증가 할 것입니다.
- 사건을 처리하려면 몇 가지 논리가 있어야합니다. 현재의 필드는 0입니다. 보다 이 stackoverflow 질문.
흥미로운 문제! 스케줄러 작동을 단순화 할 수 없는지 궁금해 할 수는 없지만 이런 종류의 작업이 필요합니다.
VHDL을 알고 있다는 점을 감안할 때 자세히 설명하지는 않지만 내 제안은 다음과 같습니다.
3 비트 인코더를 사용하여 현재 예정된 작업을 숫자로 전환하십시오.
01000000 --> 6
그런 다음 배럴 시프터를 사용하여 마스크를 해당 숫자 + 1 (현재 작업을 건너 뛰기 위해)을 회전시킵니다.
00001010 --> 00010100
그런 다음 우선 순위 인코더를 사용하여 첫 번째 사용 가능한 "다음"작업을 찾으십시오.
00010100 --> 00000100 --> 2
그런 다음 추가로 배럴 이동을 뒤집습니다.
(2+7) % 8 = 1
다시 인코딩되면 다음 예정된 작업이 제공됩니다.
00000010
배럴 시프터는 부동산 측면에서 '비싸지 않지만'매우 빠르고 간단해야하지만, 현재는 쉽게 돌아 다닐 수있는 방법을 보지 못합니다.
편집 : Doug의 솔루션은 훨씬 더 우아합니다 ...
-아담
하위 팩트 1은 여기서 필수 아이디어입니다. Cascade는 다음 과제를 찾기 위해 비트를 통해 빌린 데 사용됩니다.
bits_before_current = ~(current-1) & ~current
bits_after_current = current-1
todo = (mask & bits_before_current)
if todo==0: todo = (mask & bits_after_current) // second part is if we have to wrap around
next = last_bit_of_todo = todo & -todo
그래도 내부적으로 루프를 사용합니다 ...
TWOS 보완 표현을 가정하면 두 단어를 호출하십시오 mask 그리고 current, C :
mask_lo = (current << 1) - 1; // the bits to the right and including current
mask_hi = ~mask_lo; // the bits to the left of current
// the left bits, otherwise right:
next = (mask & mask_hi) ? (mask & mask_hi) : (mask & mask_lo);
return (next & -next); // the least significant bit set
이것은 당신이 원하는 것을해야합니다.
number_of_tasks= <number of tasks, in the example this is 8>
next_mask= current | (current - 1);
next_barrel= next | (next << number_of_tasks);
next_barrel&= ~number_of_tasks;
next_barrel&= -next_barrel;
next_barrel|= next_barrel >> number_of_tasks;
next_task_mask= next_barrel & -next_barrel;
기본적으로, 다음 작업 마스크의 비트를 복제하고, 고려하고 싶지 않은 비트를 마스크하고, 가장 낮은 세트 비트를 찾고, 높은 비트를 다시 접은 다음 가장 낮은 비트 세트를 가져갑니다. 이것은 일정한 시간에 실행됩니다.
편집 : 현재 == 00010000 및 next_mask == 00111000을 고려하도록 업데이트
테스트되지 않았지만 내 머리 꼭대기에서, 이것이 MA 합리적인 합성을 생성하지 않았다면 놀랄 것입니다 ... 일반적인 비트 틀린 해킹과 달리 상대적으로 읽을 수 있다는 장점이 있습니다.
for i in current'range loop
current := rotate_left(current, 1);
if or_reduce(mask and current) = '1' then
current:= mask and current;
end if;
end loop;
라운드 로빈 또는 우선 순위 중재에 대해 구성 할 수있는 완전한 매개 변수 중재자 구현 :
https://github.com/alexforencich/verilog-axis/blob/master/rtl/arbiter.v
이 디자인은 우선 순위 인코더 쌍을 사용하여 순서대로 다음 출력을 선택합니다. 사용 된 우선 순위 인코더는 나무로 효율적으로 구현됩니다.
