Encontrar o próximo agendamento round-robin a pouco twiddling

Question

Considere o seguinte problema. Você tem um bit-string que representa o escravo programada atual em codificação one-quente. Por exemplo, "00000100" (com o bit mais à esquerda sendo # 7 e mais à direita # 0) significa que sofremos # 2 está programado.

Agora, eu quero escolher o próximo escravo programada em um esquema de escalonamento round-robin, com uma torção. Eu tenho uma "máscara pedido", que diz que os escravos realmente quer ser agendada. O próximo escravo será escolhido apenas daqueles que querem.

Alguns exemplos (assumir round-robin agendamento é feito girando-esquerda). Exemplo 1:

• atual: "00000100"
• Máscara: "01100000"
• Em seguida cronograma:. "00100000" - no round-robin normal, # 3 e, em seguida, # 4 deve vir depois # 2, mas não o fazem pedido, então # 5 é escolhido

Exemplo 2:

• atual: "01000000"
• Máscara: "00001010"
• Em seguida:. "00000010" - porque a programação é feita pelo ciclismo esquerda, e # 1 é o escravo primeiro solicitando nessa ordem

---

Agora, isso pode ser facilmente codificado em um loop, eu sei. Mas eu realmente quero pegar o meu resultado por uma operação-girando pouco, sem loops. A motivação:. Eu quero implementar isso em hardware (em uma FPGA) em VHDL / Verilog

Um bônus é tornar-se um algoritmo que é genérico para qualquer quantidade de escravos N.

A propósito, esta não é uma pergunta lição de casa. É um problema importante quando se quer escravos programação de alguma maneira, e condicionar o agendamento por pedidos dos escravos. Minha solução atual é um pouco "pesado" e eu queria saber se eu estou faltando algo óbvio.

Answer 1

Eu encontrei o seguinte código Verilog para a execução da tarefa na Altera síntese avançado livro de receitas.

// '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

Ele usa subtração (apenas uma vez, embora), de modo conceitualmente é bastante semelhante à solução de Doug.

Answer 2

Um loop não tem que ser ruim.

Gostaria apenas de fazer

current[i] = current[i-1] & mask[i] |                         // normal shift logic
                mask[i] & current[i-2] & !mask[i-1] |         // here build logic 
                ...                                          // expression for 
                                                             // remaining 

E, em seguida, colocá-lo em um loop gerar (ou seja, ele vai ficar desenrolou em hardware), que irá produzir hardware paralelo para as expressões.

Outras soluções aqui mencionadas usar múltiplos "-". Eu só pode desencorajá-los, pois isso vai-lhe uma operação realmente caro obter. Esp. em um quente você pode obter facilmente mais de> 32 bits, o que não será facilmente implementável em HW, como o emprestado tem que passar por todos os bits (a lógica carry deadicated em certos FPGAs torná-lo acessível para pequeno número de bits).

Answer 3

A solução a seguir funciona para qualquer número de escravos (K), e é O (n) no seu FPGA. Para cada bit no campo, você vai precisar de três portas lógicas e dois inversores. Eu testei o conceito com um simulador de lógica básica, e ele funciona.

A cadeia de portas lógicas entre atual e mascarar essencialmente cria um sistema de prioridades que favorece pedaços "mais abaixo" na cadeia. Esta cadeia é enrolada nas extremidades, mas o corrente bits são usados ??para quebrar a cadeia.

Para visualizar a operação, imagine que pouco 3 é definido no atual campo, e siga as para baixo de sinal no diagrama. A uma lógica no bit 3 coloca um zero lógico na entrada para a primeira porta E, que garante que a saída da referida porta E também vai ser igual a zero (isto é, onde a cadeia de porta OR é quebrado ). O zero na saída da primeira porta E coloca um uma na entrada para a segunda porta E. Isso faz com que mordeu 2 de próxima diretamente dependente bit 2 de máscara .

Agora, a cadeia de portas OR entra em jogo.

Se bit 2 de máscara foi definido, a saída lógica da porta OR diretamente à esquerda do que também irá ser um, que vai colocar uma lógica na entrada para a porta AND abaixo pouco 2 de corrente (o qual vai ser igual a zero, uma vez que apenas um pouco em corrente pode ser fixado a um Tempo). A única lógica na saída da parte superior e portão coloca um zero lógico na entrada do fundo porta AND, estabelecendo, assim, pouco 1 de próxima igual a zero.

Se bit 2 de máscara não foi definido, ambas as entradas para a porta OR seria zero, então a saída da porta AND abaixo bit 2 de atual seria um zero, colocando um na entrada para o fundo e portão, e, portanto, tornando pouco 1 de próxima dependente de bit 1 de máscara .

Esta lógica segue a cadeia de portas OR "up" os bits, looping em torno do lado esquerdo de volta para a direita, garantindo que apenas um bit em próxima pode ser definido como um. O loop pára uma vez que faz o seu caminho de volta para pouco 3 de atual , como resultado desse conjunto de bits ser. Isso impede que o circuito de ficar em um loop contínuo.

Eu não tenho nenhuma experiência com Verilog ou VHDL, por isso vou deixar o código real até você eo resto do stackoverflow.

alt texto http://img145.imageshack.us/img145/5125/bitshifterlogicdiagramkn7 .jpg

Notas:

1. Esta solução é apenas parcial. Ele ainda vai exigir algum tipo de mecanismo de travamento para manter os campos de bits.
2. Tenha em mente que à medida que aumenta o número de bits, o tempo necessário para as tensões portão para resolver também vai aumentar.
3. Não terá que haver alguma lógica no lugar para lidar com o caso em que o atual campo é igual a zero. Consulte esta pergunta stackoverflow .

Answer 4

problema Interessante! Eu não posso ajudar, mas pergunto se você não pode simplificar o seu funcionamento planejador assim este tipo de operação seria necessária.

Uma vez que você sabe VHDL, eu não vou entrar em detalhes, mas a minha sugestão seria a seguinte:

Use um codificador de 3 bits para transformar a tarefa está programada para um número:

01000000 -> 6

Em seguida, use um shifter barril para rodar a máscara por esse número + 1 (para ignorar a tarefa atual):

00001010 -> 00010100

Em seguida, use um codificador de prioridade para encontrar o primeiro disponível "ao lado" tarefa:

00010100 -> 00000100 -> 2

Em seguida, inverter a mudança de barril por adição:

(2 + 7)% 8 = 1

Que quando re-codificado dará a próxima tarefa agendada:

00000010

Deve ser muito rápido e direto, embora o shifter barril é 'caro' em termos de realestate, mas eu não vejo uma maneira fácil de contornar isso no momento.

Editar: solução de Doug é significativamente mais elegante ...

-Adam

Answer 5

subtraindo 1 é a idéia essencial aqui. É usado para toma emprestado em cascata através dos bits para encontrar a próxima tarefa.

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

Isto irá usar um loop internamente embora ...

Answer 6

Assumindo pares representação complemento, chame seus duas palavras mask e current, em 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

Answer 7

Isso deve fazer o que quiser:

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;

Basicamente, duplicar os bits da próxima máscara tarefa, mascarar os bits que não queremos considerar, encontrar o menor conjunto de bits, dobre os bits altos de volta, em seguida, tomar o menor conjunto de bits. Este é executado em tempo constante.

Edit: Atualizando para levar em conta corrente == 00010000 e next_mask == 00111000

Answer 8

Não testado, mas em cima da minha cabeça, eu ficaria surpreso se isso não produziu ma síntese razoável ... Tem a vantagem de ser relativamente legível (para mim), ao contrário hacks típicos-girando bits.

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;

Answer 9

implementação árbitro parametrizável completa que pode ser configurado para o round-robin ou arbitragem prioridade:

https://github.com/alexforencich/verilog- eixo / blob / master / RTL / arbiter.v

Este projeto usa um par de codificadores de prioridade para selecionar a próxima saída na sequência. Os codificadores de prioridade usados ??são implementadas eficientemente quanto árvores.