подсчитывать начальные нули в пути данных за один цикл

Как вы все, возможно, знаете, набор инструкций MIPS поддерживает clz (счет с начальным нулем) следующим образом:

clz $t0,$t1 подсчитывает начальные нули t0 = # начальных нулей в t1

Я пишу путь данных с одним циклом в verilog, и мне просто интересно, что ALU должен поддерживать, чтобы я мог это сделать ... есть идеи ??


assembly verilog mips
person aherlambang    schedule 03.03.2010    source источник

Ответы (3)


arrow_upward
4
arrow_downward

Вот возможный подход (я игнорирую случай ввода 0, который, вероятно, лучше всего рассматривать как особый случай):

  • The number of leading zeros in a 32-bit number is either:
    • the number of leading zeros in the top 16 bits, if any of the top 16 bits are non-zero; or
    • 16 плюс количество начальных нулей в младших 16 битах, если все верхние 16 битов равны нулю
  • Это дает верхний бит 5-битного результата (игнорируя особый случай ввода 0...).
  • Теперь вам нужно найти количество ведущих нулей в 16-битном числе, поэтому снова примените тот же принцип.
  • и Т. Д.

В Verilog это может выглядеть примерно так:

result[4] = (value[31:16] == 16'b0);
val16     = result[4] ? value[15:0] : value[31:16];
result[3] = (val16[15:8] == 8'b0);
val8      = result[3] ? val16[7:0] : val16[15:8];
result[2] = (val8[7:4] == 4'b0);
val4      = result[2] ? val8[3:0] : val8[7:4];
result[1] = (val4[3:2] == 2'b0);
result[0] = result[1] ? ~val4[1] : ~val4[3];
person Matthew Slattery    schedule 04.03.2010

arrow_upward
0
arrow_downward

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

Что-то вроде (псевдокод):

if word == 0: return 32
elsif (word & 1) == 0: return 31
elsif (word & 3) == 0: return 30

и Т. Д.

person Eli Bendersky    schedule 03.03.2010
comment
@Alexander: да, это может быть еще одна операция, которую выполняет ALU. имейте в виду, однако, что это удлинит ваш тактовый цикл, потому что это сложная операция. Я полагаю, что настоящие процессоры делают что-то более сложное - person Eli Bendersky; 03.03.2010
comment
Я ищу что-то более сложное... более эффективное и простое - person aherlambang; 04.03.2010
comment
@ Александр, это определенно просто, хотя, возможно, и не слишком эффективно. - person Eli Bendersky; 04.03.2010
comment
Гораздо проще работать с другого конца, просматривая бит за раз: word[31]? 0: слово[30]? 1 : слово[29] ? 2 ... word[0]?31:32 (но имеет длинную цепочку пульсаций). Обратите внимание: у вас может быть «быстрый» и «маленький», но не оба. Если у вас есть доступный блок, называемый «приоритетным кодировщиком», вы можете использовать его, который является «простым» в том смысле, что вам не нужно его кодировать. Ответ Мэтью - хороший быстрый подход, я могу опубликовать более крупный и немного более быстрый ответ. - person greggo; 11.10.2012
comment
Arg, я имею в виду, что у вас может быть "быстрый" или "маленький", но не оба - person greggo; 12.10.2012

arrow_upward
0
arrow_downward

Создайте модуль clz16, который просматривает 16 бит и имеет 4-битный результат (0..15) и вывод «allzero». Соедините два из них вместе, чтобы сделать clz32, вам нужен мультиплексор, чтобы выбрать, какие 4 младших бита и немного логики для верхних 2 выходных битов.

clz16 состоит из двух clz8 таким же образом. clz8 состоит из двух clz4. clz4 — это всего лишь три логические функции с ‹= 4 входами, так что не имеет большого значения, как вы это сделаете, синтезатор сведет это к нескольким гейтам.

Этот иерархический подход больше, чем решение Мэтью Слэттери с каскадными мультиплексорами, но, вероятно, не настолько сильно (для переключения мультиплексоров не нужны широкие ворота), и я считаю, что он допускает более низкую опору. задерживать. Оба подхода хорошо масштабируются до больших размеров (например, 64, 128 бит) с задержкой. в log2(n).

person greggo    schedule 12.10.2012