Нахождение следующего в циклическом распределении по битам

Question

Рассмотрим следующую проблему. У вас есть битовая строка, которая представляет текущего запланированного ведомого в однократном кодировании. Например, «00000100» (крайний левый бит №7 и крайний правый №0) означает, что подчиненный №2 запланирован.

Теперь я хочу выбрать следующего запланированного ведомого в схеме циклического планирования с изюминкой. У меня есть «маска запроса», которая говорит, какие рабы действительно хотят быть запланированы. Следующий раб будет выбран только из тех, кто хочет.

Некоторые примеры (предположим, что циклическое планирование выполняется вращением влево). Example1:

• Ток: "00000100"
• Маска: "01100000"
• Следующий график: «00100000» - в обычном циклическом цикле # 3 и затем # 4 должны идти после # 2, но они не запрашивают, поэтому выбирается # 5.

Пример2:

• Ток: "01000000"
• Маска: "00001010"
• Далее: «00000010» - потому что планирование выполняется с помощью циклического поворота влево, а № 1 является первым запрашивающим ведомым устройством в этом порядке.

---

Теперь это можно легко закодировать в цикле, я знаю. Но я на самом деле хочу получить мой результат с помощью операции с небольшим переворотом, без циклов. Мотивация: я хочу реализовать это аппаратно (в FPGA) в VHDL / Verilog.

Бонус состоит в том, чтобы создать алгоритм, который является общим для любого количества рабов N.

Кстати, это не домашнее задание. Это важная проблема, когда кто-то хочет каким-либо образом планировать работу подчиненных и обуславливать планирование по запросам ведомых. Мое текущее решение несколько «тяжелое», и я хотел знать, упускаю ли я что-то очевидное.

Answer 1

Цикл не должен быть плохим.

Я бы просто сделал

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

А затем поместите его в цикл генерации (т. Е. Он будет развернут в аппаратное обеспечение), который будет производить параллельное оборудование для выражений.

Другие упомянутые здесь решения используют несколько «-». Я могу только отговорить их, так как это принесет вам действительно дорогую операцию. Особенно в одном цикле вы можете легко получить более 32 бит, что будет нелегко реализовать в HW, поскольку заимствование должно проходить через все биты (логика переноса с ошибками в определенных fpgas делает его доступным для небольшого количества битов).

Answer 2

Я нашел следующий код Verilog для реализации этой задачи в поваренной книге расширенного синтеза 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

Он использует вычитание (хотя бы один раз), поэтому концептуально он очень похож на решение Дуга.

Answer 3

Следующее решение работает для любого количества ведомых (K) и равно O (n) в вашей FPGA. Для каждого бита в поле вам потребуются три логических элемента и два инвертора. Я проверил концепцию с помощью базового логического симулятора, и он работает.

Цепочка логических элементов между current и mask , по существу, создает систему приоритетов, которая поддерживает биты "ниже" в цепочке. Эта цепь зациклена на концах, но биты current используются для разрыва цепи.

Чтобы визуализировать операцию, представьте, что бит 3 установлен в поле current , и следуйте сигналу вниз на диаграмме. Логическая единица в бите 3 помещает логический ноль на входе первого логического элемента И, что гарантирует, что выход этого логического элемента И также будет нулевым (в этом случае цепь логического элемента ИЛИ разорвана) , Ноль на выходе первого логического элемента И ставит единицу на входе второго логического элемента И. Это делает бит 2 из next прямо зависимым от бита 2 из mask .

Теперь вступает в игру цепь ИЛИ.

Если был установлен бит 2 из mask , логический выход логического элемента ИЛИ, находящийся непосредственно слева от него, также будет один, который поместит логический блок в вход в логический элемент AND ниже бита 2 из current (который будет равен нулю, поскольку одновременно может быть установлен только один бит в current ). Логическая единица на выходе верхнего логического элемента И помещает логический ноль на вход нижнего логического элемента И, таким образом устанавливая бит 1 из next равным нулю.

Если бит 2 из mask не был установлен, оба входа в логический элемент ИЛИ будут равны нулю, поэтому выход логического элемента AND ниже бита 2 current будет равен нулю, помещая единицу на входе в нижний логический элемент И, и, следовательно, делая бит 1 из следующим зависимым от бита 1 из маска .

Эта логика следует цепочке логических элементов ИЛИ "вверх" битов, повторяя цикл с левой стороны обратно вправо, гарантируя, что только один бит в next может быть установлен в единицу. Цикл останавливается, как только он возвращается к биту 3 из current , в результате установки этого бита. Это препятствует тому, чтобы схема оставалась в вечном цикле.

У меня нет опыта работы с Verilog или VHDL, поэтому я оставлю фактический код на ваше усмотрение и остальной части stackoverflow .

альтернативный текст http://img145.imageshack.us/img145/5125/bitshifterlogicdiagramkn7.jpg

Примечания:

1. Это решение только частичное. Это все еще потребует некоторого механизма фиксации, чтобы держать битовые поля.
2. Имейте в виду, что по мере увеличения количества битов время, необходимое для установления напряжения затвора, также будет увеличиваться.
3. Должна быть определенная логика для обработки случая, когда поле current равно нулю. См. этот вопрос о переполнении стека .

Answer 4

Интересная проблема! Я не могу не задаться вопросом, не можете ли вы упростить свою работу планировщика, поэтому такая операция будет необходима.

Учитывая, что вы знаете VHDL, я не буду вдаваться в подробности, но мое предложение будет следующим:

Используйте 3-битный кодер, чтобы превратить текущее запланированное задание в число:

01000000 -> 6

Затем поверните маску на это число + 1 с помощью бочкообразного переключателя (чтобы пропустить текущее задание):

00001010 -> 00010100

Затем используйте приоритетный кодер, чтобы найти первое доступное «следующее» задание:

00010100 -> 00000100 -> 2

Затем измените смещение ствола, добавив:

(2 + 7)% 8 = 1

Который при перекодировании даст следующее запланированное задание:

00000010

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

Редактировать: решение Дуга значительно более элегантно ...

-Adam

Answer 5

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

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

Это будет использовать цикл внутри, хотя ...

Answer 6

Предполагая, что двойное представление дополняет, назовите ваши два слова 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

Answer 7

Непроверенный, но не в голову, я был бы удивлен, если бы это не привело к разумному синтезу ... Имеет преимущество в том, что он является относительно читабельным (для меня в любом случае), в отличие от типичных хитов с переворотами.

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 8

Это должно делать то, что вы хотите:

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

Answer 9

Завершите параметризованную реализацию арбитра, которую можно настроить для циклического или приоритетного арбитража:

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

В этом исполнении используется пара приоритетных кодеров для выбора следующего выхода в последовательности. Используемые кодеры приоритетов эффективно реализованы в виде деревьев.