Jump to content

    
Sign in to follow this  

Recommended Posts

Добрый день!

 

Мне дали задание реализовать на ПЛИС алгоритм нахождения обратного числа по модулю с использованием расширенного алгоритма Евклида. С ПЛИС я раньше особо не сталкивался. Прошу палками не бить, а подтолкнуть в нужную сторону. Кое-что на verilog писал, собственно прилагаю.

 

Алгоритм:

 

image.jpg

 

image.jpg

 

Код:

 

module inversea (input wire [63:0]a, 
input wire clk,
input wire [63:0]p, 
output reg [64:0]res);

reg [63:0]u;
reg [63:0]v;
reg [63:0]r;
reg [63:0]s;
reg [63:0]x;
reg [8:0]k;

initial
begin
r = 0;
s = 1;
k = 0;
end	

initial 
@(a or p) begin
u = p;
v =a;
end

always @(posedge clk) begin

while (v > 0) begin
	if ((u >> 1) == 0)
		if ((r >> 1) == 0) begin
			u = u >> 1;
			r = r >> 1;
			k = k + 1;
		end
		else begin
		u = u >> 1;
		r = (r+p) >> 1;
		k = k + 1;
		end
	else if ((v >> 1) == 0) 
		if ((s >> 1) == 0) begin
			k = k >> 1;
			s = s >> 1;
			k = k + 1;
		end
		else begin
			v = v >> 1;
			s = (s+p) >> 1;
			k = k + 1;
		end
	else begin
		x = u-v;
	end
	if (x > 0) begin
		u = x;
		r = r - s;
		if (r < 0)
			r <= r + p;
		else begin
			v = -x;
			s = s - r;
			if (s < 0)
				s = s + r;
		end
	end
end

if (r > p)
	r = r - p;
if (r < 0)
	r = r + p;

	res = r; 

end

endmodule

 

Тестбенч:

 

module test();
// constants                                           
// general purpose registers
reg eachvec;
// test vector input registers
reg [63:0]a;

reg [63:0]p;
// wires                                               
reg clk;

wire [64:0]res;

always
#50 clk = ~clk;

// assign statements (if any)                          
inversea inv1 (
// port map - connection between master ports and signals/registers   
.a(a),
.clk(clk),
.p(p),
.res(res)
);
initial                                                
begin                                                  
// code that executes only once                        
// insert code here --> begin                          

// --> end    
clk = 0;                                         
$display("Testbench running");                       
end       

always                                           
// optional sensitivity list                           
// @(event1 or event2 or .... eventn)                  
begin                                                  
// code executes for every evenst on sensitivity list   
// insert code here --> begin                          
a = 'd4;
p = 'd26;                                                                                        
#10;
// --> end                                             
end

initial
begin                                                  
// code that executes only once                        
// insert code here --> begin                          

// --> end                                             
$display("a = %d",a);
$display("p = %d",p);
#51 $display("out = %d",res);                         
end  

initial
begin
 $dumpfile("out1.vcd");
 $dumpvars(0,test);
end

initial
begin
#400 $finish;
end 

endmodule

 

Заранее благодарю.

inversea.v

inverseatest.v

Edited by kereokerekeke

Share this post


Link to post
Share on other sites
Добрый день!

 

Мне дали задание реализовать на ПЛИС алгоритм нахождения обратного числа по модулю с использованием расширенного алгоритма Евклида. С ПЛИС я раньше особо не сталкивался. Прошу палками не бить, а подтолкнуть в нужную сторону. Кое-что на verilog писал, собственно прилагаю.

...

Заранее благодарю.

Я больше в VHDL шарю, но ИМХО ПЛИС это не процессор.

Соответственно, если взять код на С++, и в лоб переделать на Verilog - работать не будет.

Особенно аккуратннее с циклами надо - циклы в микропроцессорах и в HDL для ПЛИС - полная противоположность.

Share this post


Link to post
Share on other sites
Мне дали задание реализовать на ПЛИС алгоритм нахождения обратного числа по модулю с использованием расширенного алгоритма Евклида. С ПЛИС я раньше особо не сталкивался. Прошу палками не бить, а подтолкнуть в нужную сторону. Кое-что на verilog писал, собственно прилагаю.

В нужную сторону - первоначальное обучение надо начинать с более простых задач. Разработка для ПЛИС слишком сильно отличается от традиционного программирования, чтобы так с наскока взять и сразу всё получилось.

Share this post


Link to post
Share on other sites

Вам надо обработать массив данных - считайте что данные приходят последовательно и обрабатываются тоже последовательно - pipeline.

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

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

Share this post


Link to post
Share on other sites
Соответственно, если взять код на С++, и в лоб переделать на Verilog - работать не будет.

Взять Vivado, в нем есть HLS - это автоматическое преобразование из С++ в HDL... И произвести все в нем все оптимизации... И это будет круто...

 

Share this post


Link to post
Share on other sites
Взять Vivado, в нем есть HLS - это автоматическое преобразование из С++ в HDL... И произвести все в нем все оптимизации... И это будет круто...

К сожалению не оптимально по ресурсам

обзор

и еще обзор

тогда может лучше через Python

Share this post


Link to post
Share on other sites

Этот алгоритм можно переписать на верилог почти в лоб, но, чтобы получить синтезируемую комбинаторную функцию нужно заменить while с неопределённым числом итераций на for с фиксированным числом итераций(так что синтезатор сможет развернуть цикл) и флагом прекращения цикла(синтезатор добавит пути обхода старших ступеней тела цикла по этому флагу).

То есть вместо

while(<loop_condition>){<loop body>}

следует писать

loop_enabled = 1'b1;
for(i=0; i<n_max_iterations; i=i+1)begin
  if(!<loop_condition>)loop_enabled = 1'b0;
  if(loop_enabled) begin
    <loop body>
  end
end

И придётся математически доказать значение константы с максимально возможным числом итераций.

Сам я никогда не пробовал так, может синтез и не пройдёт, хотя теоретически должен.

UPD: А если loop_condition не зависит от счётчика цикла, то loop_enabled тут не нужен, поскольку loop_condition не будет меняться при пропуске циклов.

Edited by Timmy

Share this post


Link to post
Share on other sites
К сожалению не оптимально по ресурсам

обзор

и еще обзор

тогда может лучше через Python

Ну, мы же не знаем какая плата у ТС, какие требования по ресурсам/частоте/времени на разработку :)

Если под руками Stratix/Arria и задача большие массивы обрабатывать, то OpenCL/HLS - почему бы и нет?

Share this post


Link to post
Share on other sites

Небольшой оффтоп, OpenCL альтеры не совсем то же самое что Vivado HLS. Когда речь об OpenCL, у хилых есть SDAccel. Сам по себе HLS плохо приспособлен для создания неких законченных устройств, в нем разрабатываются отдельные блоки для проекта верхнего уровня. Как то так...

Share this post


Link to post
Share on other sites
Ну, мы же не знаем какая плата у ТС, какие требования по ресурсам/частоте/времени на разработку :)

Если под руками Stratix/Arria и задача большие массивы обрабатывать, то OpenCL/HLS - почему бы и нет?

 

Спасибо за ответы. Есть плата terasic de2-115. Требования - чтобы работало. Время особой роли не играет.

Edited by kereokerekeke

Share this post


Link to post
Share on other sites
Этот алгоритм можно переписать на верилог почти в лоб, но, чтобы получить синтезируемую комбинаторную функцию нужно заменить while с неопределённым числом итераций на for с фиксированным числом итераций(так что синтезатор сможет развернуть цикл)

...

При таком подходе и задаче ТС есть очень большая вероятность, что полученная схема не влезет в FPGA, а если влезет, то разведется на частоте менее мегагерца :(

 

 

Share this post


Link to post
Share on other sites
Спасибо за ответы. Есть плата terasic de2-115. Требования - чтобы работало. Время особой роли не играет.

А Вам не рассказали, как данные будут попадать в "плату" и из нее извлекаться...

К примеру на тумблерах задаете данные, нажимаете кнопочку и на светодиодах читаете ответ... Так?

 

Share this post


Link to post
Share on other sites
А Вам не рассказали, как данные будут попадать в "плату" и из нее извлекаться...

К примеру на тумблерах задаете данные, нажимаете кнопочку и на светодиодах читаете ответ... Так?

 

Как вариант. Единственное, что числа должны быть 64 бита. С ПЛИС я и работал на данный момент на уровне поморгать светодиодами, что сильно осложняет задачу...

Edited by kereokerekeke

Share this post


Link to post
Share on other sites
Как вариант. Единственное, что числа должны быть 64 бита. С ПЛИС я и работал на данный момент на уровне поморгать светодиодами, что сильно осложняет задачу...

Параметризацию никто не отменял. Можно сделать например для 4 или 8 бит проверить работоспособность, а потом поменять цифру в VHDL описании в generick/package 4 или 8 на 64 и всех делов ...

В верилоге аналогично - parameter/define ...

 

Любопытство почему 64 бита, а не 32/16/8 бит?

Share this post


Link to post
Share on other sites
А Вам не рассказали, как данные будут попадать в "плату" и из нее извлекаться...

К примеру на тумблерах задаете данные, нажимаете кнопочку и на светодиодах читаете ответ... Так?

 

Как вариант. Единственное, что числа должны быть 64 бита.

..[офф]

помню, когда в технаре учился - стажировался в одном НИИ, мне сказали сделать платку для программирования синтезатора - моего тёзки.

На плате были тумблер 1 - 0 , кнопки - клоков и записи + антидребезговые тригера.

Так вот - через месяц работы я код из нескольких десятков бит набивал на память и с приличной скоростью!

Аля - человеческий SPI.

В те же времена, инженеры меня посылали принести ведро меандра (свежего).

p.s.

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this