Перейти к содержанию
Поиск
    

Сортировка чисел

Ответить

Maverick_    15

Maverick_
Опубликовано · Жалоба
А Oldring видимо имел ввиду, что Ваш код написан не очень компактно(мягко говоря), и, надо сказать, сложновато для понимания. Не говоря уже бешенном количестве закомментированных строк.

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

Я так привык писать и мне он удобен для понимания.

ЗЫ На вкус и цвет товарищей нет

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

AJIEKCEu    0

AJIEKCEu
Опубликовано · Жалоба
смотря какая фпга, на виртексе 2 скорее всего вы правы, но на тех же спартанах 3/виртекс 4 1 блок памяти это 16к х 1 (RAMB18).

Дык вроде и на виртекс 2 память такая же.... НО!

(2^16)!=(16*1024)

ну или

(2**16)/=(16*1024)

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Maverick_    15

Maverick_
Опубликовано · Жалоба
Дык вроде и на виртекс 2 память такая же.... НО!

(2^16)!=(16*1024)

ну или

(2**16)/=(16*1024)

 

Несколько раз перечитав Ваше объяснение, я тоже пришел к этому же выводу, что сохраняется не 16 значений, а более 16 тысяч, и кажется без сортировки

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Shtirlits    0

Shtirlits
Опубликовано · Жалоба

Объясните мне на пальцах, пожалуйста, что нужно получить? Эти 16 чисел должны содержать наибольшие 16 значений от чего? Можно пример?

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

AJIEKCEu    0

AJIEKCEu
Опубликовано · Жалоба

У меня как-то так получилось....

В 4 сравнения уложиться не удалось... Только в 5.

 

Немного кривовато, но работает. Вроде. Сильно глубоко не тестил.

 

library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
entity sorter is
generic (
	width	: integer := 16;--ширина входных/выходных векторов
	num		: integer :=16;	--количество векторов, которые надо запомнить
	log2num	: integer :=4 --это собственно log2(num)
	);
port (
	Datain		: in std_logic_vector(width-1 downto 0);
	Dataout0	: out std_logic_vector(width-1 downto 0);
	Dataout1	: out std_logic_vector(width-1 downto 0);
	Dataout2	: out std_logic_vector(width-1 downto 0);
	Dataout3	: out std_logic_vector(width-1 downto 0);
	Dataout4	: out std_logic_vector(width-1 downto 0);
	Dataout5	: out std_logic_vector(width-1 downto 0);
	Dataout6	: out std_logic_vector(width-1 downto 0);
	Dataout7	: out std_logic_vector(width-1 downto 0);
	Dataout8	: out std_logic_vector(width-1 downto 0);
	Dataout9	: out std_logic_vector(width-1 downto 0);
	DataoutA	: out std_logic_vector(width-1 downto 0);
	DataoutB	: out std_logic_vector(width-1 downto 0);
	DataoutC	: out std_logic_vector(width-1 downto 0);
	DataoutD	: out std_logic_vector(width-1 downto 0);
	DataoutE	: out std_logic_vector(width-1 downto 0);
	DataoutF	: out std_logic_vector(width-1 downto 0);
	clk			: in std_logic;
	datastrobe	: in std_logic
	);
end entity;

architecture behavioral of sorter is
type tDataArray is array (NATURAL RANGE<>) of std_logic_vector(width-1 downto 0); 
signal iteration_ct : integer range 0 to (log2num+1) :=0;
-- в этом "регистре" будут храниться СОРТИРОВАННЫЕ значения. Больше индекс - больше значение.
signal mainreg : tDataArray(num downto 1):=(others=>x"0000");	
signal data : std_logic_vector(width-1 downto 0);
signal strobeint : std_logic;
-- функция "вставки" значения в регистр (в заданную позицию)
function datains(signal data : in std_logic_vector(width-1 downto 0); position : in integer; signal datareg: in tDataArray) return tDataArray is 
	variable tmp : tDataArray(num downto 1);
begin
	tmp := datareg;
	for i in 1 to num-1 loop
		if i<position then
			tmp(i) := tmp(i+1);
		end if;
	end loop;
	tmp(position) := data;
	return tmp;
end function;
begin
process(clk)
	variable curr_max : integer range 0 to num:=num;--максимальный номер места на которое претендует текущее значение
	variable curr_min : integer range 0 to num:=0;	--минимальный номер места на которое претендует текущее значение
begin
	if clk'event and clk = '1' then
		strobeint <= datastrobe;
		if (datastrobe='1') then
			data <= datain;
		end if;
		--Проверяем, что не произошло прихода нового значения до окончания процедуры
		assert (not ((iteration_ct /= 0) and (strobeint='1'))) report "error";
		--Собственно процесс итераций
		if iteration_ct /= 0 or strobeint='1' then
			if mainreg((curr_max+curr_min)/2+1)>data then
				curr_max:=(curr_max+curr_min+1)/2-1;
			else
				curr_min:=(curr_max+curr_min+1)/2;
			end if;
			iteration_ct<=iteration_ct+1;
		end if;
		--Прекращаем процедуру по условиям.
		if ((iteration_ct=log2num) or (curr_max=0)) then
			if curr_max=0 then
			else
				mainreg <= datains(data,curr_min,mainreg);
			end if;
			iteration_ct<=0;
			curr_min := 0;
			curr_max := num;
		end if;
	end if;
end process;
Dataout0<= mainreg(1);
Dataout1<= mainreg(2);
Dataout2<= mainreg(3);
Dataout3<= mainreg(4);
Dataout4<= mainreg(5);
Dataout5<= mainreg(6);
Dataout6<= mainreg(7);
Dataout7<= mainreg(8);
Dataout8<= mainreg(9);
Dataout9<= mainreg(10);
DataoutA<= mainreg(11);
DataoutB<= mainreg(12);
DataoutC<= mainreg(13);
DataoutD<= mainreg(14);
DataoutE<= mainreg(15);
DataoutF<= mainreg(16);

end architecture;

 

А вообще нипанятно зачем мудрить :)

Все делается за такт и тривиально.... По крайней мере для таких параметров.

 

library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
entity sorter2 is
generic (
	width	: integer := 16;--ширина входных/выходных векторов
	num		: integer :=16;	--количество векторов, которые надо запомнить
	log2num	: integer :=4 --это собственно log2(num)
	);
port (
	Datain		: in std_logic_vector(width-1 downto 0);
	Dataout0	: out std_logic_vector(width-1 downto 0);
	Dataout1	: out std_logic_vector(width-1 downto 0);
	Dataout2	: out std_logic_vector(width-1 downto 0);
	Dataout3	: out std_logic_vector(width-1 downto 0);
	Dataout4	: out std_logic_vector(width-1 downto 0);
	Dataout5	: out std_logic_vector(width-1 downto 0);
	Dataout6	: out std_logic_vector(width-1 downto 0);
	Dataout7	: out std_logic_vector(width-1 downto 0);
	Dataout8	: out std_logic_vector(width-1 downto 0);
	Dataout9	: out std_logic_vector(width-1 downto 0);
	DataoutA	: out std_logic_vector(width-1 downto 0);
	DataoutB	: out std_logic_vector(width-1 downto 0);
	DataoutC	: out std_logic_vector(width-1 downto 0);
	DataoutD	: out std_logic_vector(width-1 downto 0);
	DataoutE	: out std_logic_vector(width-1 downto 0);
	DataoutF	: out std_logic_vector(width-1 downto 0);
	clk			: in std_logic;
	datastrobe	: in std_logic
	);
end entity;

architecture behavioral of sorter2 is
type tDataArray is array (NATURAL RANGE<>) of std_logic_vector(width-1 downto 0); 
-- в этом "регистре" будут храниться СОРТИРОВАННЫЕ значения. Больше индекс - больше значение.
signal iteration_ct : integer range 0 to (log2num+1) :=0;
signal mainreg : tDataArray(num downto 1):=(others=>x"0000");	
signal data : std_logic_vector(width-1 downto 0);
--	signal compares : std_logic_vector(num downto 1);
signal strobeint : std_logic;
-- функция "вставки" значения в регистр (в заданную позицию)
function datains(signal data : in std_logic_vector(width-1 downto 0); position : in integer; signal datareg: in tDataArray) return tDataArray is 
	variable tmp : tDataArray(num downto 1);
begin
	tmp := datareg;
	for i in 1 to num-1 loop
		if i<position then
			tmp(i) := tmp(i+1);
		end if;
	end loop;
	tmp(position) := data;
	return tmp;
end function;
begin
process(clk)
variable shifted : boolean;
variable compares : std_logic_vector(num downto 1);
begin
	if clk'event and clk = '1' then
		strobeint <= datastrobe;
		if (datastrobe='1') then
			data <= datain;
		end if;
		if strobeint='1' then
			for i in 1 to num loop
				if mainreg(i)>data then
					compares(i):='0';
				else
					compares(i):='1';
				end if;
			end loop;
			shifted := false;
			for i in num downto 1 loop
				if ((compares(i)='1') and (not shifted)) then
					mainreg<=datains(data,i,mainreg);
					shifted := true;
				end if;
			end loop;
			iteration_ct<=0;
		end if;
	end if;
end process;
Dataout0<= mainreg(1);
Dataout1<= mainreg(2);
Dataout2<= mainreg(3);
Dataout3<= mainreg(4);
Dataout4<= mainreg(5);
Dataout5<= mainreg(6);
Dataout6<= mainreg(7);
Dataout7<= mainreg(8);
Dataout8<= mainreg(9);
Dataout9<= mainreg(10);
DataoutA<= mainreg(11);
DataoutB<= mainreg(12);
DataoutC<= mainreg(13);
DataoutD<= mainreg(14);
DataoutE<= mainreg(15);
DataoutF<= mainreg(16);

end architecture;

 

Объясните мне на пальцах, пожалуйста, что нужно получить? Эти 16 чисел должны содержать наибольшие 16 значений от чего? Можно пример?

Пример. На вход поступает поток - clk, Data(15 downto 0), Strobe. Нужно отслеживать значения в потоке и максимальные 16 значений "на текущий момент" выдавать на выход.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Shtirlits    0

Shtirlits
Опубликовано · Жалоба 
    function log2 (x : positive) return natural is 
        begin
            if x <= 1 then
                return 0;
            else
                return log2 (x / 2) + 1;
            end if;
        end function log2;

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Des333    0

Des333
Опубликовано · Жалоба
... остается только считать 16 старших флагов, работать будет на частотах пока память еще шевелиться  :)

 

Если не сложно, поясните, пожалуйста.

 

 

Просто не совсем понятно, как потом будем определять, где "1", где "0"?

 

Перебором подряд, начиная со старшего адреса, пока 16 чисел не наберем? Или есть нормальный вариант, но я его не вижу?

 

Спасибо!

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Sefo    0

Sefo
Опубликовано · Жалоба
:help::help: :help:

Требуется реализовать сортировку входных данных (допустим 16 bit) по любому алгоритму, и чтобы сохранялись 16 максимальных значений. Главное требование чтобы он заработал на 100 МГц в Virtex II (XC2V1000).

Хотелось бы выслушать предложения и может быть готовые решения.

 

Вот еще один вариант. От предыдущих отличается тем, что требует значительно меньше логич. ячеек. На обработку входного отсчета тратится 16 тактов, но на 300 МГц должно разложиться без проблем. Принцип очень прост. В DA(0) кладем по стробу входной отсчет и начинаем вращать по кругу DA(16 downto 1) и сравнивать DA(0) с DA(1) как только обнаруживается, что DA(0) > DA(1) вращать по кругу начинаем все 17 DA. Количество вращений фиксировано - 16. Таким образом по окончании 16-ти вращений в DA(0) попадает значение "на вылет" - оно будет затерто следующим входным отсчетом. В DA(1) располагается самое большое число, а в DA(16) самое маленькое.

 

library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
entity sorter is
    generic (
        width    : integer := 16 --ширина входных/выходных векторов
        );
    port (
        Datain        : in std_logic_vector(width-1 downto 0);
        Dataout0    : out std_logic_vector(width-1 downto 0);
        Dataout1    : out std_logic_vector(width-1 downto 0);
        Dataout2    : out std_logic_vector(width-1 downto 0);
        Dataout3    : out std_logic_vector(width-1 downto 0);
        Dataout4    : out std_logic_vector(width-1 downto 0);
        Dataout5    : out std_logic_vector(width-1 downto 0);
        Dataout6    : out std_logic_vector(width-1 downto 0);
        Dataout7    : out std_logic_vector(width-1 downto 0);
        Dataout8    : out std_logic_vector(width-1 downto 0);
        Dataout9    : out std_logic_vector(width-1 downto 0);
        DataoutA    : out std_logic_vector(width-1 downto 0);
        DataoutB    : out std_logic_vector(width-1 downto 0);
        DataoutC    : out std_logic_vector(width-1 downto 0);
        DataoutD    : out std_logic_vector(width-1 downto 0);
        DataoutE    : out std_logic_vector(width-1 downto 0);
        DataoutF    : out std_logic_vector(width-1 downto 0);
        clk            : in std_logic;
    RESETsn : in std_logic; 
    
        datastrobe    : in std_logic
        );
end entity;

architecture behavioral of sorter is

    type DataArray is array (NATURAL RANGE<>) of std_logic_vector(width-1 downto 0); 

  constant num        : integer :=16;

    signal DA : DataArray(num downto 0);    
  
  signal cnt_en : std_logic;
  signal cnt    : std_logic_vector(3 downto 0);
  
  signal full_rotate : std_logic;
  
begin

process(clk)
begin
        
    if clk'event and clk = '1' then
--    {    
        if RESETsn = '0' then
--        {      
            DA <= (others => (others => '0'));
            full_rotate <= '0';
--        }
        elsif datastrobe = '1' then
--        {      
            DA(0) <= Datain;
            full_rotate <= '0';
--        }
        elsif cnt_en = '1' then
--        {      
            if DA(0) > DA(1) or full_rotate = '1' then
--            {
                DA <= DA(0) & DA(num downto 1);
                full_rotate <= '1';
--            }
            else  
--            {
                DA(num downto 1) <= DA(1) & DA(num downto 2);
--            }
            end if;
--        }
        end if;
--    }
    end if;
    
end process;
  

process(clk)
begin
        
    if clk'event and clk = '1' then
--    {      
        if datastrobe = '1' then
--        {      
            cnt_en <= '1';
            cnt    <= (others => '0');
--        }
        elsif cnt_en = '1' then
--        {      
            cnt <= cnt + 1;
            
            if cnt = 15 then
              cnt_en <= '0';
            end if;
--        } 
        end if;
--    }
        end if;
    
end process;

  
    Dataout0<= DA(1);
    Dataout1<= DA(2);
    Dataout2<= DA(3);
    Dataout3<= DA(4);
    Dataout4<= DA(5);
    Dataout5<= DA(6);
    Dataout6<= DA(7);
    Dataout7<= DA(8);
    Dataout8<= DA(9);
    Dataout9<= DA(10);
    DataoutA<= DA(11);
    DataoutB<= DA(12);
    DataoutC<= DA(13);
    DataoutD<= DA(14);
    DataoutE<= DA(15);
    DataoutF<= DA(16);
    
end architecture;

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

SergeyF    0

SergeyF
Опубликовано (изменено) · Жалоба

Интересное упражнение на ночь. Извините, на VHDL только читать умею, поэтому на смеси SystemVerilog и Verilog:

 

module sort
#(parameter WIDTH=16)
(
input clk, enable, reset, sclr,
input phase,
output tolow,
input fromhi,
input [WIDTH-1:0] dlo, 
input [WIDTH-1:0] dhi,
output reg [WIDTH-1:0] dout
);

assign tolow = (dlo>dout);

always @ (posedge clk or posedge reset)
begin
if (reset) 
	dout <= 0;
else if (enable)
begin
	if (sclr) dout<=0;
	else 
	begin
		if (!phase)	dout <= tolow?dlo:dout;
		else dout <= fromhi?dhi:dout;
	end
end
end

endmodule

 

И главный модуль, объединяющий модули нижнего уровня в линейку

module sortmax
#(parameter WIDTH=16,
 parameter LENGTH=16)
(
input clk, ena, rst, sclr,
input [WIDTH-1:0] data, 
output [WIDTH-1:0] dout[LENGTH-1:0]
);

genvar i;
wire xchange[LENGTH];
reg divgen;
wire divarr[LENGTH+1];

always @ (posedge clk or posedge rst)
begin
if (rst) 
	divgen <= 0;
else 
	if (ena)
		if (sclr) divgen<=0;
		else divgen<=~divgen;
end

generate for(i = 0; i < LENGTH; i=i+2) 
begin : gen_inv
assign divarr[i]=divgen;
assign divarr[i+1]=~divgen;
end endgenerate

sort #(WIDTH) elem_cin(.clk(clk),.enable(ena),.reset(rst),.sclr(sclr),
				.phase(divarr[0]),.fromhi(xchange[1]),
				.dlo(data),.dhi(dout[1]),.dout(dout[0]));
generate for(i = 1; i < LENGTH-1; i=i+1) 
begin : gen_chain
sort #(WIDTH) elem(.clk(clk),.enable(ena),.reset(rst),.sclr(sclr),
				.phase(divarr[i]),.tolow(xchange[i]),.fromhi(xchange[i+1]),
				.dlo(dout[i-1]),.dhi(dout[i+1]),.dout(dout[i]));
end endgenerate
sort #(WIDTH) elem_out(.clk(clk),.enable(ena),.reset(rst),.sclr(sclr),
				.phase(divarr[LENGTH-1]),.tolow(xchange[LENGTH-1]),.fromhi(1'b0),
				.dlo(dout[LENGTH-2]),.dhi({WIDTH{1'b0}}),.dout(dout[LENGTH-1]));

endmodule

 

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

такт 1 - сравнения и обмены (0,1),(2,3),(4,5),...

такт 2 - сравнения и обмены (1,2),(3,4),...

При этом массив исходно упорядочен (забит минимальными значениями)

Корректность еще не доказывал - такой реализации я не встречал, но вроде бы работает.

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

 

P.S. Если лень разбираться - выбирает из текущего потока 16 максимальных значений, по два такта на входной отсчет. Вот еще временная диаграмма из Quartus.

post-8660-1254255822_thumb.png

post-8660-1254256301_thumb.png

Изменено пользователем Sergey'F

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

kreakozeablik    0

kreakozeablik
Опубликовано · Жалоба

1 такт на один отсчет:

module sort_list_cell(clk, rst, en, din, dprev, cprev, dout, cout);

input clk;
input en;
input rst;

input [15: 0] din;

input [15: 0] dprev; // содержимое регистра предыдущего модуля
input cprev; // значение на входе din больше чем dprev

output [15: 0] dout;
output cout; // значение на входе din больше чем dout

reg [15: 0] dout;

assign cout = din > dout;

always @(posedge clk)
	if(rst)
		dout <= 16'd0;
	else if(en && cout)
		dout <= cprev? dprev: din;
endmodule

module sort_list(clk, rst, en, din, do0, d01, d02, do3);

input clk;
input en;
input rst;
input [15: 0] din;

output [15:0] do0, do1, do2, do3;

wire cprev0, cprev1, cprev2, cprev3;

// Отсортированный список, наибольшее снизу
sort_list_cell cell3 (.clk(clk), .en(en), .rst(rst), .din(din), .dprev(do2), .cprev(cprev2), .dout(do3), .cout(cprev3));
sort_list_cell cell2 (.clk(clk), .en(en), .rst(rst), .din(din), .dprev(do1), .cprev(cprev1), .dout(do2), .cout(cprev2));
sort_list_cell cell1 (.clk(clk), .en(en), .rst(rst), .din(din), .dprev(do0), .cprev(cprev0), .dout(do1), .cout(cprev1));
sort_list_cell cell0 (.clk(clk), .en(en), .rst(rst), .din(din), .dprev(15'd0), .cprev(1'b0), .dout(do0), .cout(cprev0));
endmodule

 

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

 

Значение на входе сохраняется в модуле sort_list_cell, начиная с которого это значение превосходит значение регистра dout (условие позиции вставки: cprev = 0 и cout = 1).

Остальные модули, у которых din > dout, берут новое значение регистра dout с выхода предыдущего модуля.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

des00    25

des00
Опубликовано · Жалоба
Дык вроде и на виртекс 2 память такая же.... НО!

(2^16)!=(16*1024)

ну или

(2**16)/=(16*1024)

 

да ошибся, перепутал что RAMB16 это не 16 бит адреса, а 16 килобит, вы правы потребуется 4 блока памяти %)

 

Несколько раз перечитав Ваше объяснение, я тоже пришел к этому же выводу, что сохраняется не 16 значений, а более 16 тысяч, и кажется без сортировки

 

Перебором подряд, начиная со старшего адреса, пока 16 чисел не наберем? Или есть нормальный вариант, но я его не вижу?

 

я сказал что можно использовать гистограмму распределения чисел в потоке. Но в данном случае нам не важна частота появления числа в потоке, а важен сам факт наличия данного числа. Флаг наличия числа это 1 бит, число имеет разрядность 16 бит. Следовательно нам нужна память на 2^16 однобитных чисел. После интервала наблюдения у вас будет факт появления всех чисел в потоке. В данном случае искать их можно только полным перебором. Правда это будет не совсем тот индикатор который хочет автор, т.к. если в потоке все числа были одинаковые этот индикатор выдаст одно число %)

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

sakol    0

sakol
Опубликовано · Жалоба

Добрый день.

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

помогите новичку :)

заранее благодарен

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
К сожалению, ваш контент содержит запрещённые слова. Пожалуйста, отредактируйте контент, чтобы удалить выделенные ниже слова.
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
×
  • Создать...