Jump to content

    

Подсчитать кол-во единиц в слове

Вот проект :) . Компилировался в 9.1 без SP.

 

Взял только исходник. Quartus 10.0 - 117 МГц.  :)

Такой же результат (117 МГц) получил еще тремя реализациями. А больше - никак.  :laughing:

 

 

UPD:

Собрал Quartus 9.1 - действительно, 126 МГц.

 

Но 9.1 показывает такой же результат (даже 127 МГц :) ) и для такого "банального" варианта, как:

module sum64(
  input         clk,
  input  [63:0] data_i,
  output [6:0]  sum_o
);

logic [63:0] data;
logic [6:0]  sum;

logic [1:0][5:0]  sum_32bit;
logic [3:0][4:0]  sum_16bit;
logic [7:0][3:0]  sum_8bit;
logic [15:0][2:0] sum_4bit;
logic [31:0][1:0] sum_2bit;

always_ff @(posedge clk)
  begin
    data  <= data_i;
    sum_o <= sum;     
  end


always_comb
  for(int i=0; i<32; i++)
    sum_2bit[i] = data[2*i+1] + data[2*i];
  
always_comb
  for(int i=0; i<16; i++)
    sum_4bit[i] = sum_2bit[2*i+1] + sum_2bit[2*i];

always_comb
  for(int i=0; i<8; i++)
    sum_8bit[i] = sum_4bit[2*i+1] + sum_4bit[2*i];
    
always_comb
  for(int i=0; i<4; i++)
    sum_16bit[i] = sum_8bit[2*i+1] + sum_8bit[2*i];    
    
always_comb
  for(int i=0; i<2; i++)
    sum_32bit[i] = sum_16bit[2*i+1] + sum_16bit[2*i];    
    

assign sum = sum_32bit[1] + sum_32bit[0];  

  
endmodule

 

А также для варианта, предложенного уважаемым SM в теме, ссылку на которую уже давали выше.

Для Quartus 10.0 же все эти варианты дают 117 МГц.

 

 

Значит теперь стоят два равнозначных вопроса:

1) Добиться 125 МГц при сборке Quartus 10.0 :)

2) Найти реализацию лучше, чем данные.

Share this post


Link to post
Share on other sites

Если я не снес в гневе Q10, посмотрю, так как это очень интересно.

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

 

Share this post


Link to post
Share on other sites
Либо они накосячили в синтезе (это уже перебор), либо скорректировали временные модели (что довольно странно для вполне зрелого семейства).

 

Это действительно интересно, но, несмотря на причину отличия в результатах, можно сделать вывод, что все предложенные реализации одинаковы по быстродействию.

 

И, либо реализации быстрее этих нет, и нужно это доказать, либо она есть, и нужно ее найти.  :)

 

 

 

Share this post


Link to post
Share on other sites
Взял только исходник. Quartus 10.0 - 117 МГц.  :)

Такой же результат (117 МГц) получил еще тремя реализациями. А больше - никак.  :laughing:

Открыл проект в QII 10.0 со всеми настройками целиком. :) Сразу 123.76МГц. Замечу, что разница 123.76 и 125.38 достаточно мала. И раньше были изменения в быстродействии от версии к версии, причем более значительные.

 

Но все же решил посмотреть. Выводы. Синтез не изменился. Размещение не изменилось, причем при смене зерен разводки оно остается одинаковым у обоих версий. Изменилась разводка и критические пути.

 

Более подробное рассмотрение в Таймквесте (см. рис) показывает, что во всех путях, которые стали выпадать из ограничений, одна из задержек изменилась с примерно с 0.6 на 0.9нс. Приемник и источник по этому участку находятся в соседних LAB. Могу лишь предположить, что эти пути QII 10.0 развел не по DirectLink, а по R4. В подтверждение статистика использования ресурсов межсоединений ниже. DirectLink в проекте используется меньше.

 

	                QII 9.1 SP2	        QII 10.0
Block interconnects	175 / 32,401 ( < 1 % )	166 / 32,401 ( < 1 % )
C4 interconnects	71 / 21,816 ( < 1 % )	70 / 21,816 ( < 1 % )
C16 interconnects	53 / 1,326 ( 4 % )	51 / 1,326 ( 4 % )
Direct links	        73 / 32,401 ( < 1 % )	62 / 32,401 ( < 1 % )
Global clocks	        2 / 10 ( 20 % )	        2 / 10 ( 20 % )
Local interconnects	85 / 10,320 ( < 1 % )	86 / 10,320 ( < 1 % )
R4 interconnects	88 / 28,186 ( < 1 % )	83 / 28,186 ( < 1 % )
R24 interconnects	35 / 1,289 ( 3 % )	36 / 1,289 ( 3 % )

 

Это действительно интересно, но, несмотря на причину отличия в результатах, можно сделать вывод, что все предложенные реализации одинаковы по быстродействию.

Не совсем равны. Разный синтез, разные реализации. Но в любом случае, каждая из них лучше, чем в лоб писать цикл на 64 разряда.

 

P.S. В процессе работы QII 10.0 один раз упал. :smile3046:

post-8660-1284214577_thumb.png

post-8660-1284214586_thumb.png

Share this post


Link to post
Share on other sites
Не совсем равны. Разный синтез, разные реализации.
Естественно, разные. Я писал лишь, что полученная Fmax одинакова.  :)

 

 

Но в любом случае, каждая из них лучше, чем в лоб писать цикл на 64 разряда.

Хотелось бы все-таки найти более быстродействующую реализацию.

Share this post


Link to post
Share on other sites

Обнаружил комбинацию (3+3+1)+4+1, которая позволяет в одном LAB-е обработать 12 входных сигналов.

Я имею в виду, что сначала две тройки сигналов четырьмя LUT-ами суммируются, далее складываются между собой и еще одним входным сигналом, а затем 4 сигнала сложенные тройкой LUT-ов добавляются вместе с последним сигналом. Есть надежда, что это существенно улучшит ситуацию.

Не смог заставить Quartus разместить эти элементы правильно, а когда они разбросаны где попало, пользы быть не может.

Нужно генерировать netlist и с помощью LogicLock фиксировать. Не нашел в себе силы заново изучить как это делается.

Ни к чему попытки вручную указать как реализовывать мою схему, если инструмент не слушается.

"Зачем тебе телефон, если ты не можешь говорить?" ©агент из матрицы.

Это была тоска по RLOC атрибутам, которых нет у Альтеры.

 

Переписал на VHDL своими словами дерево сумматоров Sergey'F. Вместо 125MHz получил около 100MHz.

Подсмотрел netlist. Он почти целиком на LUT-ах, никаких CARRY нет. А у меня сумматоры с CARRY.

Пляски со спекулятивными сумматорами результата не дали, как и ожидалось при столь небольших размерах.

Убрал буфер CARRY_SUM. Получил больше 144MHz, хотя просил 125.

Если просить 144, то дадут 138. Можно еще разное просить, но давать будут что угодно.

Сделал чистый проект, чтобы заслать интересующимся. Q10.0 начал вываливаться.

Важные параметры: synthesis SPEED, IGNORE CARRY BUFFERS ON; fitter STANDARD

В Q91 тоже около 144MHz.

 

Попробовал установить такие же параметры и посмотреть, сколько даст верилоговый вариант Sergey'F.

С отключенными Carry buffers 134MHz. Вероятно, можно еще поиграть с размещением через LogicLock для всего проекта и получить 146 или больше. Ведь исходная структура идентичная, а прижав поплотнее дизайн мне удавалось поднять мегагерц на 10 скорость.

 

Испортила Альтера настроение. Нет ощущения контроля над ситуацией.

Политика "скажи что хочешь, а quartus позаботится" не всегда хороша.

Я бы согласился с Альтерой, если бы quartus синтезировал простую сумму в цикле до таких же частот,

что дерево изготовленное Sergey'F.

 

В аттаче проекты Q10.0 и Q9.1 с исходными текстами. Верификацию не делал.

sum64_144.rar

Share this post


Link to post
Share on other sites
Важные параметры: synthesis SPEED, IGNORE CARRY BUFFERS ON; fitter STANDARD

Как раз хочется получить RTL-описание, которое будет давать >125 МГц, а не играться с параметрами, чтобы этого достичь.

И если поменять значение тех параметров, что Вы указали, на дефолтные, то частота сразу падает до 125 МГц.

А есть изменить параметр DEVICE с EP3C5E144C8 на EP3C5F256C8, то частота падает до 123 МГц (я просто под него предыдущие реализации проверял).

 

 

 

Но, несмотря на это, у Вас наилучшая реализация по быстродействию. Только при ней частота поднялась до 123 МГц, кроме того, использование указанных Вами выше параметров позволяет увеличить частоту еще на 23 МГц - до 146 МГц. В моей реализации эффект от этих параметров был более незначительным - частота увеличивалась до 137 МГц, то есть на 20 МГц.  :)

 

Я, правда, проверкой функциональности Вашего варианта пока тоже не занимался и даже вообще не смотрел код, но думаю, что там все нормально.

Share this post


Link to post
Share on other sites
Как раз хочется получить RTL-описание, которое будет давать >125 МГц, а не играться с параметрами, чтобы этого достичь.

Пробовал сделать на основе вот такой ячейки. 

 

 

c79fd646d14at.jpg

 

Дальше по традиционной схеме 3+3,4+4... Но увы выиграша не увидел. Делал в ISE для 3-го спартана.

 

если кому интересно, или хочет поиграться то пожалуйста.

 


`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Engineer:       Gusev M.E.
// Create Date:    21:15:47 09/20/2010 
// Module Name:    proba1 
// Project Name:   64bit_in1_for_electronix.ru
// Target Devices: sp3e
// Tool versions:  Xilinx 11.1
// Revision: 
// Revision 0.01 - File Created
//////////////////////////////////////////////////////////////////////////////////
module celll(
   input [3:0] in4bit,
 output [2:0] out3bit);

wire aa=in4bit[0]^in4bit[1];
wire bb=in4bit[0]&in4bit[1];
wire cc=in4bit[2]^in4bit[3];
wire dd=in4bit[2]&in4bit[3];

wire a=aa^cc;
wire b=aa&cc;

wire c=bb^dd;
wire d=bb&dd;

wire e=b|c;

assign out3bit[2]=d;
assign out3bit[1]=e;
assign out3bit[0]=a;

endmodule


module prob1(
   input clk,
   input [63:0] word64,
   output reg [5:0] out);

reg [63:0] bit64;
 wire [2:0] tha;
 wire [2:0] thb;
 wire [2:0] thc;
 wire [2:0] thd;
 wire [2:0] the;
 wire [2:0] thf;
 wire [2:0] thg;
 wire [2:0] thk;
 wire [2:0] thaa;
 wire [2:0] thbb;
 wire [2:0] thcc;
 wire [2:0] thdd;
 wire [2:0] thee;
 wire [2:0] thff;
 wire [2:0] thgg;
 wire [2:0] thkk;	
   wire [3:0] foura;
   wire [3:0] fourb;
   wire [3:0] fourc;
   wire [3:0] fourd;
   wire [3:0] foure;
   wire [3:0] fourf;
   wire [3:0] fourg;
   wire [3:0] fourk;
   wire [4:0] fivea;
   wire [4:0]	fiveb;
   wire [4:0] fivec;
   wire [4:0] fived;
   wire [5:0] sixa;
   wire [5:0]	sixb;	 
 wire [5:0] sixFind;

 wire [3:0] aaa=bit64[3:0];
   wire [3:0] bbb=bit64[7:4]; 
   wire [3:0] ccc=bit64[11:8];	
 wire [3:0] ddd=bit64[15:12];
 wire [3:0] eee=bit64[19:16];
 wire [3:0] fff=bit64[23:20];
 wire [3:0] ggg=bit64[27:24];
 wire [3:0] kkk=bit64[31:28];
 wire [3:0] aaaa=bit64[35:32];
 wire [3:0] bbbb=bit64[39:36];
 wire [3:0] cccc=bit64[43:40];
 wire [3:0] dddd=bit64[47:44];
 wire [3:0] eeee=bit64[51:48];
 wire [3:0] ffff=bit64[55:52];
 wire [3:0] gggg=bit64[59:56];
 wire [3:0] kkkk=bit64[63:60];	 



celll U1 (.in4bit(aaa),.out3bit(tha));
celll U2 (.in4bit(bbb),.out3bit(thb));
celll U3 (.in4bit(ccc),.out3bit(thc));
celll U4 (.in4bit(ddd),.out3bit(thd));
celll U5 (.in4bit(eee),.out3bit(the));
celll U6 (.in4bit(fff),.out3bit(thf));
celll U7 (.in4bit(ggg),.out3bit(thg));
celll U8 (.in4bit(kkk),.out3bit(thk));
celll U9 (.in4bit(aaaa),.out3bit(thaa));
celll U10 (.in4bit(bbbb),.out3bit(thbb));
celll U11 (.in4bit(cccc),.out3bit(thcc));
celll U12 (.in4bit(dddd),.out3bit(thdd));
celll U13 (.in4bit(eeee),.out3bit(thee));
celll U14 (.in4bit(ffff),.out3bit(thff));
celll U15 (.in4bit(gggg),.out3bit(thgg));
celll U16 (.in4bit(kkkk),.out3bit(thkk));

assign foura=tha+thb;
assign fourb=thc+thd;
assign fourc=the+thf;
assign fourd=thg+thk;
assign foure=thaa+thbb;
assign fourf=thcc+thdd;
assign fourg=thee+thff;
assign fourk=thgg+thkk;

assign fivea=foura+fourb;
assign fiveb=fourc+fourd;
assign fivec=foure+fourf;
assign fived=fourg+fourk;

assign sixa=fivea+fiveb;
assign sixb=fivec+fived;

assign sixFind=sixa+sixb;

always @ (posedge clk) begin
bit64=word64;
out=sixFind;
end
endmodule

 

 

Share this post


Link to post
Share on other sites

Господа и товарищи! Попробуйте этот код. Вчера были результаты быстродействия чуть лучше, чем у приведенных выше образцов. А сегодня почему-то намного хуже. Весь в недоумении. Компилировал в Quartus 9.1 SP2.

module  CountOnes64
(input  wire  clk,
  input  wire [63:0] d,
  output logic [6:0] sum);

  bit  [63:0] dc;
  bit  [6:0] sumc;  
  always @(posedge clk)  begin
    dc <= d;
    sum = sumc;
  end

  bit [0:15][2:0] s0;
  bit [0:7][3:0] s1;
  bit [0:3][4:0] s2;
  bit [0:1][5:0] s3;
  always_comb  begin
    for (int i=0; i<16; i++)
      s0[i] = dc[4*i] + dc[4*i +1] + dc[4*i +2] + dc[4*i +3];
    for (int j=0; j<8; j++)  begin
      s1[j][2:0] = s0[2*j] + s0[2*j +1];
      s1[j][3] = s0[2*j][2] & s0[2*j +1][2];
    end
    for (int k=0; k<4; k++)  begin
      s2[k][3:0] = s1[2*k] + s1[2*k +1];
      s2[k][4] = s1[2*k][3] & s1[2*k +1][3];
    end
    for (int m=0; m<2; m++)  begin
      s3[m][4:0] = s2[2*m] + s2[2*m +1];
      s3[m][5] = s2[2*m][4] & s2[2*m +1][4];
    end
    sumc[5:0] = s3[0] + s3[1];
    sumc[6] = s3[0][5] & s3[1][5];
  end
endmodule

 

Upd. Ох, ексель-моксель! Выбрал не ту микросхему. Вместо EP3C5F256C8 была выбрана EP2C5... А с EP3C5 дает частоты 123 MHz и 158 MHz при Ignore Carry Buffers Off и On, соответственно.

Есть еще мысли, продолжу...

Share this post


Link to post
Share on other sites

Кое-что удалось :) ...

Идея: минимизировать число уровней логики; метод - вручную кодировать переносы на основе суммирования 4 бит на одном LUT. При этом задача каждый раз сводится к предыдущей То есть результат первого сложения (16 3-битовых чисел) представляется снова как 3 16-битных вектора, в кажом из которых надо снова найти число единиц, и сложить их, но уже с уётом сдвига на 1 и 2 разряда. Вместо нахождения напрямую снова вычисляются переносы, они группируются поразрядно в вкатора, в которых снова нужно найти число единиц, и т. д.

 

Код УЖАСЕН, знаю, извините :), повышением удобочитаемости не занимался (если кому-то нужно - скажите, допилю). Функциональный тест и .do-файл для него прилагаются.

Проект - на основе выкладывавшегося выше (где архив больше 3 Мб).

EP3C5E144C8, 85 С; Quartus 8.0 SP1

Результаты: 128.98 МГц - оптимизация Speed, "Ignore Carry Buffers" отключено.

132.43 МГц оптимизация "Balanced", по-моему, и на "Area" то же самое, "Ignore Carry Buffers" отключено. то есть те самые желанные настройки по умолчанию

Включение "Ignore Carry Buffers" прибавляет где-то 1 МГц.

Если изменить функцию sum4 на закомментированный вариант - частота резко падает до 86 МГц.

Похоже, при сложении множества чисел желание Quartus уложиться в обычную структуру сумматров только портит дело.

 

P. S. Интересно, как тот же код снитезят более новые Quartus'ы - а то в 8.0 временные параметры CIII указаны как подлежащие уточнению.

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

sum64_intekus.zip

Share this post


Link to post
Share on other sites
Идея: минимизировать число уровней логики; метод - вручную кодировать переносы на основе суммирования 4 бит на одном LUT

... при игнорировании цепочек переноса; то есть, ИМХО, если это же логику расписать руками, должен получиться примерно настолько же быстрый вариант при настройках по умолчанию.

Для начала скажу, что я сделал в приведенном коде. Нулевая ступень - суммируем группы по 4 бита, каждому такому сумматору должно потребоваться 3 LUT и никаких переносов. Дальше суммируем обычным деревом сумматоров. Но - старшие биты в каждом из сумматоров обладают свойством, назовем, "исключительности". То есть, если этот бит в 1, то все остальные младшие биты в 0 (максимальные числа в ступенях s0, s1, s2, s3 будут 4, 8, 16 и 32). Поэтому для вычисления старшего бита не нужны переносы из младших. Вот на этих переносах задержки и экономятся.

Дальше - нужно применить схемы параллельных переносов, когда для их формирования используются только входные сигналы. Только нужно еще определить, в каком случае параллельные переносы будут эффективнее последовательных. Надеюсь, если правильно все написать, то быстродействие будет не меньше, чем при игнорировании carry.

P.S. Частоты у меня снова слегка упали - 121 MHz и 158 MHz, устал подкручивать в настройках.

Share this post


Link to post
Share on other sites
Для начала скажу, что я сделал в приведенном коде. (...)

Спасибо, мне он и без комментариев показался довольно ясным :)

Дальше суммируем обычным деревом сумматоров. Но - старшие биты в каждом из сумматоров обладают свойством, назовем, "исключительности"

Интуитивно чувствуется, что использование этого свойства при каждом сложении (как это сделано у Вас) - и даст карйнюю степень оптимизации.

Надеюсь, если правильно все написать, то быстродействие будет не меньше, чем при игнорировании carry.

Для начала можно попробовать заменить суммирование на явно расписанные логические функции (например:

function [2:0] sum4(input [3:0] n);
  sum4[0] = ^n;
  sum4[1] = ~(n == 4'h0 | n == 4'h1 | n == 4'h2 | n == 4'h4 | n == 4'h8  | n == 4'hF);
  sum4[2] = &n;
endfunction

); а где там дальше применять последовательные и параллельные переносы - да, надо разбираться; для начала, наверное, среверсить TechMap даваемый Quartus в том самом варианте "за 150".

Share this post


Link to post
Share on other sites
заменить суммирование на явно расписанные логические функции

Нечто подобное я уже пробовал, лучше не становилось. Наверное, Quartus сам до этого додумался.

среверсить TechMap даваемый Quartus в том самом варианте "за 150"

Там 6 листов. Как а анекдоте - "проще нового родить, чем этого отмыть".

Share this post


Link to post
Share on other sites
Нечто подобное я уже пробовал, лучше не становилось. Наверное, Quartus сам до этого додумался.

Там 6 листов. Как а анекдоте - "проще нового родить, чем этого отмыть".

В общем, если кто-то ещё (например, начавший тред alexPec) подтвердит интерес - на досуге поэкспериментирую, а так пока тему оставляю - много текущих задач.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this