[ANT 0]

Разрядность слова - порядка 300 бит. Как такая функция называется: модуль? Как реализовать в Верилоге?

[Sergei_Ilchenko 0]

Разрядность слова - порядка 300 бит. Как такая функция называется: модуль? Как реализовать в Верилоге?

 

1. Если время не поджимает, то с минимумом ресурсов - это счетчик и регистр сдвига. Считаем выдвинувшиеся единички.

 

2. Если нужно "сразу" - то сумматоры.

 

Первый ряд сумматоров суммирует соседние пары битов входного регистра.

 

Второй ряд сумматоров результаты предыдущих... и т.д. до получения 9-ти разрядного результата для Вашего случая.

 

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

 

Самое интересное, что несколько дней назад обдумывал решение этой задачи :)

 

Готовой функции в veriolog наверное не найдете. И это не суммирование по модулю. Хотя сумматоры в себя включают сумматоры по модулю 2.

 

Кажись так.

[SM 0]

Первый ряд сумматоров суммирует соседние пары битов входного регистра.

Сумматоры суммируют по три бита, а по два бита суммируют полусумматоры. То есть первый ряд суммирует тройки входных битов.

Второй ряд - суммирует попарно выходы первого ряда, и каждый из них принимает на свой перенос еще по одному входному биту.

Третий ряд - попарно выходы второго ряда, и опять на перенос принимает по одному входному биту.

 

Итого:

- последний ряд принимает один входной бит.

- предпоследний - 2 бита

- предпредпоследний - 4 бита

...

- второй - 2^(N-2) бит

- первый - 3*2^(N-1) бит.

 

Окончательно итого - если есть 16 бит, то это три ряда (1+2+12=15 бит) + лишний четвертый инкрементор. Если есть 300... сами считайте :)

[Artem_Petrik 0]

Сумматоры это конечно хорошо, но на верилоге треуемое описывается тремя строчками при помощи for...generate.

синтезатор уже расставит сумматоры на свой вкус.

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

[SM 0]

Сумматоры это конечно хорошо, но на верилоге треуемое описывается тремя строчками при помощи for...generate. синтезатор уже расставит сумматоры на свой вкус.

Щаз :) :) От того, какую конструкцию для этого написать, площадь, так сказать, этого произведения искусства, меняется в разы, если не на порядки. Это уже пройдено.

И, докучи, для писания "влоб" generate не нужен. Простого for хватит. Но синтезатор с результатом такого for очень неоптимально справляется.

 

Более менее оптимально синтезаторы съедают такую конструкцию (эта опять 16-битная):

 

assign temp1 = (in & 16'h5555) + ((in & 16'hAAAA) >> 1);
assign temp2 = (temp1 & 16'h3333) + ((temp1 & 16'hCCCC) >> 2);
assign temp3 = (temp2 & 16'h0707) + ((temp2 & 16'h7070) >> 4);
assign temp4 = (temp3 & 16'h000F) + ((temp3 & 16'h0F00) >> 8);
assign out = temp4[4:0];

 

но и то не получается той площади, что расставление сумматоров деревом. Ошибочно думать, что синтезатор это бог, и он минимизирует все так, что меньше уже не минимизировать.

[sazh 8]

Разрядность слова - порядка 300 бит. Как такая функция называется: модуль? Как реализовать в Верилоге?

 

// MAX+plus II Verilog Example
// Combinatorial Always Statement 
// Copyright (c) 1994 Altera Corporation

module proc (d, q);

    input  [2:0] d;
    output [1:0] q;

    integer num_bits;

    always @(d)
    begin: block
        integer i;

        num_bits = 0;
        for (i = 0; i < 3; i = i + 1)
           if (d[i] == 1)
               num_bits = num_bits + 1;
    end

    assign q = num_bits;

endmodule

[Artem_Petrik 0]

Щаз :) :) От того, какую конструкцию для этого написать, площадь, так сказать, этого произведения искусства, меняется в разы, если не на порядки. Это уже пройдено.

И, докучи, для писания "влоб" generate не нужен. Простого for хватит. Но синтезатор с результатом такого for очень неоптимально справляется.

Хм, доберусь до квартуса, попробую синтезировать. Мне почему-то кажется, что прооптимизировать дерево сумматоров - достаточно простая задача, чтобы с ней справился оптимизатор. Впрочем я могу ошибаться. Практика покажет.

Просто расставлять сумматоры вручную в данной задаче - мартышкин труд. Человек должен стратегией заниматься, а не низкоуровневой оптимизацией. Это так, лирическое отступление :)

ЗЫ: караз sazh и код подогнал :)

[SM 0]

Просто расставлять сумматоры вручную в данной задаче - мартышкин труд. Человек должен стратегией заниматься, а не низкоуровневой оптимизацией. Это так, лирическое отступление :)

Ну зачем же вручную - для этого как раз for...generate придуман.

[Leka 1]

http://forum.ixbt.com/topic.cgi?id=48:1629:2575#2575 (и в соседних постах)

[SM 0]

Хм, доберусь до квартуса, попробую синтезировать.

Ну вот я добрался.

Первый код - 208 LE

Второй код (дерево сумматоров, но не оптимальное) - 160 LE

 

Оптимальное дерево сумматоров строить лениво :) Но уверен, еще меньше места займет.

 

module test (in, out);

input [63:0] in;
output reg [6:0] out;


reg [6:0] i;

always @*
begin
  out=0;
  for (i=0; i<64; i=i+1)
    out = out + in[i];
end

/*
wire [63:0] temp [5:0];

assign temp[0] = (in      & 64'h5555555555555555) + ((in >> 1)       & 64'h5555555555555555);
assign temp[1] = (temp[0] & 64'h3333333333333333) + ((temp[0] >> 2)  & 64'h3333333333333333);
assign temp[2] = (temp[1] & 64'h0707070707070707) + ((temp[1] >> 4)  & 64'h0707070707070707);
assign temp[3] = (temp[2] & 64'h000f000f000f000f) + ((temp[2] >> 8)  & 64'h000f000f000f000f);
assign temp[4] = (temp[3] & 64'h0000001f0000001f) + ((temp[3] >> 16) & 64'h0000001f0000001f);
assign temp[5] = (temp[4] & 64'h000000000000003f) + ((temp[4] >> 32) & 64'h000000000000003f);

always @*
  out <= temp[5][6:0];
*/

endmodule

 

квартус 8.0 SP1, компилировано под ACEX1K, все настройки по дефолту

[Postoroniy_V 0]

так же как и у SM "квартус 8.0 SP1, компилировано под ACEX1K, все настройки по дефолту"

module one(
input[63:0]    i,
output [6:0] o);

function[5:0] count_one;
input[31:0]    i;
bit[31:0] temp[5:0];
    temp[0] = (i       & 32'h55555555) + ((i >> 1)       & 32'h55555555);
    temp[1] = (temp[0] & 32'h33333333) + ((temp[0] >> 2)  & 32'h33333333);
    temp[2] = (temp[1] & 32'h07070707) + ((temp[1] >> 4)  & 32'h07070707);
    temp[3] = (temp[2] & 32'h000f000f) + ((temp[2] >> 8)  & 32'h000f000f);
    temp[4] = (temp[3] & 32'h0000001f) + ((temp[3] >> 16) & 32'h0000001f);
    temp[5] = (temp[4] & 32'h0000003f) + ((temp[4] >> 32) & 32'h0000003f);
    count_one = temp[5][5:0];                                 
endfunction

function[5:0] count_one1;
input[31:0]    i;
integer x;
    count_one1=i[0];
    for(x=1;x<32;x=x+1)
        count_one1 = count_one1+i[x];
endfunction

function[2:0] count4;
input[3:0]    i;
    case(i)
    4'b0000:count4=0;
    4'b0001:count4=1;
    4'b0010:count4=1;
    4'b0011:count4=2;
    4'b0100:count4=1;
    4'b0101:count4=2;
    4'b0110:count4=2;
    4'b0111:count4=3;
    4'b1000:count4=1;
    4'b1001:count4=2;
    4'b1010:count4=2;
    4'b1011:count4=3;
    4'b1100:count4=2;
    4'b1101:count4=3;
    4'b1110:count4=3;
    4'b1111:count4=4;
    endcase
endfunction

function[3:0] count8;
input[7:0]    i;
    count8 = count4(i[7:4])+count4(i[3:0]);
endfunction

function[5:0] count_4_32;
input[31:0] i;
    count_4_32=count4(i[3:0]);
    count_4_32=count_4_32+count4(i[7:4]);
    count_4_32=count_4_32+count4(i[11:8]);
    count_4_32=count_4_32+count4(i[15:12]);
    count_4_32=count_4_32+count4(i[19:16]);
    count_4_32=count_4_32+count4(i[23:20]);
    count_4_32=count_4_32+count4(i[27:24]);
    count_4_32=count_4_32+count4(i[31:28]);

endfunction

function[5:0] count_8_32;
input[31:0] i;

    count_8_32=count8(i[7:0]);
    count_8_32=count_8_32+count8(i[15:8]);
    count_8_32=count_8_32+count8(i[23:16]);
    count_8_32=count_8_32+count8(i[31:24]);

endfunction

//assign o=count_one1(i[63:32])+count_one1(i[31:0]);//200 LC in acex1k
//assign o=count_4_32(i[63:32])+count_4_32(i[31:0]);//165 LC in acex1k
assign o=count_one(i[63:32])+count_one(i[31:0]);//160 LC in acex1x
//assign o=count_8_32(i[63:32])+count_8_32(i[31:0]);//159 LC in acex1k

endmodule

[Sergei_Ilchenko 0]

Фига народ цепануло :)

 

Согласен - интересно!!!!

[des00 25]

module add_1bits (input a, b, icarry, output sum, ocarry);
  assign {ocarry, sum} = a + b + icarry;
endmodule

module ones(input[63:0]i, output [6:0] o);


  genvar g0;
  genvar g1;
  genvar g2;
  genvar g3;
  genvar g4;


  wire [65:0] i_scaled;

  logic [1:0] stage0 [21 : 0];  // 22
  logic [2:0] stage1 [10 : 0];  // 11
  logic [3:0] stage2 [ 5 : 0];  // 6
  logic [4:0] stage3 [ 2 : 0];  // 3
  logic [5:0] stage4 [ 1 : 0];  // 2

  generate

    assign i_scaled = i;

    for (g0 = 0; g0 < 22; g0++) begin : stage0_gen
      add_1bits
      add_1bits
      (
        .a     ( i_scaled [3*g0 + 0] ),
        .b     ( i_scaled [3*g0 + 1] ),
        .icarry( i_scaled [3*g0 + 2] ),
        .sum   ( stage0   [g0][0]    ),
        .ocarry( stage0   [g0][1]    )
      );
    end

    for (g1 = 0; g1 < 11; g1++) begin : stage1_gen
      assign stage1[g1] = stage0[2*g1 + 0] + stage0[2*g1 + 1];
    end

    for (g2 = 0; g2 < 6; g2++) begin : stage2_gen
      assign stage2[g2] = (g2 != 5) ? (stage1[2*g2 + 0] + stage1[2*g2 + 1]) : (stage1[2*g2 + 0]);
    end

    for (g3 = 0; g3 < 3; g3++) begin : stage3_gen
      assign stage3[g3] = stage2[2*g3 + 0] + stage2[2*g3 + 1];
    end

    for (g4 = 0; g4 < 2; g4++) begin : stage4_gen
      assign stage4[g4] = (g4 != 1) ? (stage3[2*g4 + 0] + stage3[2*g4 + 1]) : (stage3[2*g4]);
    end

  endgenerate

  assign o = stage4[0] + stage4[1];

endmodule

 

149 LC для acex1k, но думаю можно еще немного выжать %)

[Artem_Petrik 0]

149 LC для acex1k, но думаю можно еще немного выжать %)

Я сегодня дома, поэтому все еще без квартуса, все на бумажке :)

Так вот: выжать можно не немножко!

Я исходил из 63х разрядного исходного, потому что красивее всего выглядят деревья для (2^n)-1 исходных узлов. в этом случае получается:

1-й уровень: 16шт 1-битных сумматоров (2 однобитных входа + 1 перенос)

2-й: 8шт 2-битных (2 двухбитных входа + перенос)

3-й: 4шт 3-битных

4-й: 2шт 4-битных

5-й: один 5-битный.

по идее после синтеза должно выйти 16 + 8*2 + 4*3 + 2*4 + 1*5 = 57 LC.

для того, чтобы сделать 64-й вход, как в примерах выше - нужно добавить еще один 6разрядный сумматор.

тогда получится 63LC. Это, по идее, теоретический предел.

 

зы: странно, если таким же образом посчитать исходник des00 то должно было получиться

22 + 11*2 + 6*3 + 3*4 +2*5 +1*6 = 90 LC. а не 149.

Кто-то из нас с квартусом глючит :).

[Leka 1]

по идее после синтеза должно выйти 16 + 8*2 + 4*3 + 2*4 + 1*5 = 57 LC

16*2+8*3+4*4+2*5+1*6=88 LUT. ISE дает 93.