Encontrar el siguiente en el round robin de la programación de a poco cambiando

StackOverflow https://stackoverflow.com/questions/480405

Pregunta

Considere el siguiente problema.Usted tiene un poco de cadena que representa la actual programada esclavo en una bañera de codificación.Por ejemplo, "00000100" (con la izquierda bits, #7 y el de más a la derecha #0) significa que el esclavo #2 está programado.

Ahora, quiero elegir la fecha de la siguiente esclavo en un round-robin esquema de planificación, con una vuelta de tuerca.Tengo una "solicitud de máscara", que dice que los esclavos en realidad quieren estar programado.El siguiente esclavo será recogido sólo de aquellos que quieren.

Algunos ejemplos (asumir la planificación round robin se realiza mediante la rotación hacia la izquierda).Ejemplo1:

  • Actual:"00000100"
  • Máscara:"01100000"
  • La siguiente programación:"00100000" - en condiciones normales de round-robin, #3 y, a continuación, #4 debe venir después de #2, pero no la solicitud, así que #5 es recogido.

Ejemplo2:

  • Actual:"01000000"
  • Máscara:"00001010"
  • Siguiente:"00000010" - debido a que la programación se realiza por el ciclismo a la izquierda, y el #1 es el primer solicitando esclavo en ese orden.

Ahora, esto puede ser fácilmente codificado en un bucle, lo sé.Pero quiero obtener mi resultado un poco-con la operación, sin bucles.La motivación:Quiero implementar esto en hardware (en un FPGA) en VHDL/Verilog.

Un bono es hacer un algoritmo que es genérico para cualquier cantidad de esclavos N.

Por cierto, esta no es una tarea cuestión.Es un problema importante cuando uno quiere programar esclavos de alguna manera, y la condición de la programación por los esclavos de las solicitudes.Mi solución actual es un poco "pesado" y quería saber si me estoy perdiendo algo que es obvio.

¿Fue útil?

Solución 2

He encontrado el siguiente código de Verilog para implementar la tarea en el libro de cocina de síntesis avanzada de Altera. 

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

Utiliza la resta (aunque solo una vez), por lo que conceptualmente es bastante similar a la solución de Doug.

Otros consejos

Un bucle no tiene que ser malo.

Simplemente haría 

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

Y luego póngalo en un bucle de generación (es decir, se desenrollará en hardware), lo que producirá hardware paralelo para las expresiones.

Otras soluciones aquí mencionadas usan múltiples " - " ;. Solo puedo desalentarlos, ya que esto te dará una operación realmente costosa. Esp. en un hot puedes obtener fácilmente más de > 32 bits, que no serán fácilmente implementables en HW, ya que el préstamo tiene que pasar por todos los bits (la lógica de acarreo en ciertos fpgas lo hace accesible para un pequeño número de bits).

La siguiente solución funciona para cualquier número de esclavos (K), y es O (n) en su FPGA. Para cada bit en el campo, necesitará tres puertas lógicas y dos inversores. Probé el concepto con un simulador lógico básico y funciona.

La cadena de compuertas lógicas entre actual y máscara esencialmente crea un sistema de prioridad que favorece los bits & "; más abajo &"; en la cadena Esta cadena se enrolla en los extremos, pero los bits actuales se usan para romper la cadena.

Para visualizar la operación, imagine que el bit 3 se establece en el campo actual y siga la señal hacia abajo en el diagrama. El lógico en el bit 3 coloca un cero lógico en la entrada de la primera puerta AND, lo que garantiza que la salida de esa puerta AND también será cero (aquí es donde se rompe la cadena de la puerta OR ) El cero en la salida de la primera puerta AND coloca un uno en la entrada a la segunda puerta AND. Esto hace que el bit 2 de siguiente dependa directamente del bit 2 de máscara .

Ahora, la cadena de puertas OR entra en juego.

Si se configuró el bit 2 de máscara , la salida lógica de la compuerta OR directamente a la izquierda también será una, que colocará una lógica. en la entrada a la puerta AND debajo del bit 2 de current (que será cero, ya que solo un bit en current puede establecerse en un hora). El lógico en la salida de la compuerta AND superior coloca un cero lógico en la entrada de la compuerta AND inferior, estableciendo así el bit 1 de next igual a cero.

Si no se estableció el bit 2 de máscara , ambas entradas a la puerta OR serían cero, por lo que la salida de la puerta AND debajo del bit 2 de actual sería un cero, colocando uno en la entrada de la puerta Y inferior y, por lo tanto, haciendo el bit 1 de siguiente depende del bit 1 de máscara .

Esta lógica sigue la cadena de compuertas OR " up " los bits, girando desde el lado izquierdo hacia la derecha, asegurando que solo un bit en siguiente pueda establecerse en uno. El bucle se detiene una vez que vuelve al bit 3 de current , como resultado de que se haya establecido ese bit. Esto evita que el circuito permanezca en un ciclo perpetuo.

No tengo experiencia con Verilog o VHDL, por lo que le dejaré el código real a usted y el resto del stackoverflow .

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

notas :

  1. Esta solución es solo parcial. Todavía requerirá algún tipo de mecanismo de retención para mantener los campos de bits.
  2. Tenga en cuenta que a medida que aumenta el número de bits, también aumentará el tiempo requerido para que los voltajes de la puerta se asienten.
  3. Tendrá que haber algo de lógica para manejar el caso en el que el campo actual sea igual a cero. Consulte esta pregunta de stackoverflow .

¡Interesante problema! No puedo evitar preguntarme si no puede simplificar la operación de su planificador, por lo que este tipo de operación sería necesaria.

Dado que conoce VHDL, no entraré en detalles, pero mi sugerencia sería la siguiente:

Use un codificador de 3 bits para convertir la tarea programada actualmente en un número:

01000000 - > 6

Luego use una palanca de barril para rotar la máscara en ese número + 1 (para omitir la tarea actual):

00001010 - > 00010100

Luego use un codificador de prioridad para encontrar el primer " next " tarea:

00010100 - > 00000100 - & Gt; 2

Luego invierta el cambio de barril mediante la adición:

(2 + 7)% 8 = 1

Que cuando se vuelve a codificar dará la siguiente tarea programada:

00000010

Debería ser muy rápido y sencillo, aunque la palanca de cambios de barril es "cara" en términos de bienes inmuebles, pero no veo una manera fácil de evitar eso en este momento.

Editar: la solución de Doug es significativamente más elegante ...

-Adam

Subtratar 1 es la idea esencial aquí. Se utiliza para tomar prestados en cascada a través de los bits para encontrar la siguiente tarea. 

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

Esto usará un bucle internamente aunque ...

Suponiendo dos complementar la representación, llame a su dos palabras mask y current, en 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

Esto debería hacer lo que quieras: 

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;

Básicamente, duplique los bits de la siguiente máscara de tareas, enmascare los bits que no queremos considerar, encuentre el bit de conjunto más bajo, doble los bits altos nuevamente y luego tome el conjunto de bits más bajo. Esto se ejecuta en tiempo constante.

Editar: Actualización para tener en cuenta current == 00010000 y next_mask == 00111000

Sin probar, pero fuera de mi cabeza, me sorprendería si esto no produjera una síntesis razonable ... Tiene la ventaja de ser relativamente legible (para mí de todos modos) a diferencia de los típicos trucos de bit-twiddling. 

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;

Implementación completa de árbitro parametrizable que se puede configurar para round-robin o arbitraje prioritario:

https://github.com/alexforencich/verilog- axis / blob / master / rtl / arbiter.v

Este diseño utiliza un par de codificadores de prioridad para seleccionar la siguiente salida en la secuencia. Los codificadores de prioridad utilizados se implementan eficientemente como árboles.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top