1 of 34

Конечные автоматы, многотактные вычисления

Введение в проектирование на языке Verilog

Прутьянов В. В.

2 of 34

Умножитель 18x18: Verilog

module mul #(

parameter N = 18

) (

input wire clk,

input wire [N-1:0] i_a,

input wire [N-1:0] i_b,

output reg [2*N-1:0] o_res

);

reg [N-1:0] a, b;

always @(posedge clk) begin

a <= i_a;

b <= i_b;

o_res <= a * b;

end

endmodule

3 of 34

Умножитель 18x18: RTL Viewer

RTL Viewer

module mul #(

parameter N = 18

) (

input wire clk,

input wire [N-1:0] i_a,

input wire [N-1:0] i_b,

output reg [2*N-1:0] o_res

);

reg [N-1:0] a, b;

always @(posedge clk) begin

a <= i_a;

b <= i_b;

o_res <= a * b;

end

endmodule

4 of 34

Умножитель 18x18: Technology Map Viewer

Technology Map Viewer (Post-Fitting)

module mul #(

parameter N = 18

) (

input wire clk,

input wire [N-1:0] i_a,

input wire [N-1:0] i_b,

output reg [2*N-1:0] o_res

);

reg [N-1:0] a, b;

always @(posedge clk) begin

a <= i_a;

b <= i_b;

o_res <= a * b;

end

endmodule

5 of 34

Ресурсы Altera Cyclone IV E

Ресурсы:

Логические элементы
Порты ввода-вывода
Умножители
Блоки PLL (ФАПЧ)
Блоки памяти

5

Источник: Cyclone IV FPGA Device Family Overview, Cyclone IV Device Handbook, Volume 1, Chapter 1. Table 1-1.

6 of 34

Умножитель 18x18: Flow Summary

+-------------------------------------------------------------------------------------+

; Flow Summary ;

+------------------------------------+------------------------------------------------+

; Top-level Entity Name ; mul ;

; Family ; Cyclone IV E ;

; Device ; EP4CE15F23C8 ;

; Timing Models ; Final ;

; Total logic elements ; 0 / 15,408 ( 0 % ) ;

; Total combinational functions ; 0 / 15,408 ( 0 % ) ;

; Dedicated logic registers ; 0 / 15,408 ( 0 % ) ;

; Total registers ; 0 ;

; Total pins ; 73 / 344 ( 8 % ) ;

; Total virtual pins ; 0 ;

; Total memory bits ; 0 / 516,096 ( 0 % ) ;

; Embedded Multiplier 9-bit elements ; 2 / 112 ( 2 % ) ;

; Total PLLs ; 0 / 4 ( 0 % ) ;

+------------------------------------+------------------------------------------------+

7 of 34

Умножитель 18x18: Resource Property Editor

8 of 34

Умножитель 18x18: Chip Planner

9 of 34

Умножитель на основе сумматора: алгоритм

uint32_t mul(uint32_t a, uint32_t b) {

uint32_t res = 0;

for (int i = 0; i < 32; i++) {

res += (a & 0x1) ? 0 : b;

a >> 1;

b << 1;

}

return res;

}

res = 0

i = 0

res += (a & 0x1) ? 0 : b

a >> 1

b << 1

i++

?

i == 32

return res

10 of 34

Умножитель на основе сумматора: алгоритм

uint32_t mul(uint32_t a, uint32_t b) {

uint32_t res = 0;

while ((a != 0) && (b != 0)) {

res += (a & 0x1) ? 0 : b;

a >> 1;

b << 1;

}

return res;

}

res = 0

res += (a & 0x1) ? 0 : b

a >> 1

b << 1

empty = (a != 0) && (b != 0)

?

empty

return res

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

11 of 34

Конечные автоматы

Синхронная логика

N бит регистров кодируют 2^Nсостояний системы

12 of 34

Конечные автоматы

Конечный автомат Мура

Синхронная логика

N бит регистров кодируют 2^Nсостояний системы

13 of 34

Конечные автоматы

Конечный автомат Мура

Конечный автомат Мили

Синхронная логика

N бит регистров кодируют 2^Nсостояний системы

14 of 34

Конечные автоматы

Конечный автомат Мура

Конечный автомат Мили

Конечный автомат (finite state machine, FSM) – дискретное устройство, имеющее входы и выходы, в каждый момент времени находящееся в одном состоянии из множества возможных

Конечный автомат определяется через:

Набор состояний
Начальное состояние
Диаграмма переходов между состояниями
Таблица выходов
Таблица выходов

Диаграмма состояний 2-битного счетчика со входом разрешения

15 of 34

Конечные автоматы

Диаграмма состояний 2-битного счетчика со входом разрешения

module fsm_cnt(

input wire clk,

input wire rst_n,

input wire en,

output wire out

); // Moore's FSM

reg [1:0] state, state_next;

localparam [1:0] S0 = 0, S1 = 1, S2 = 2, S3 = 3;

always @(posedge clk or negedge rst_n)

state <= !rst_n ? S0 : state_next;

always @(*) // Next state logic

case (state)

S0: state_next = en ? S1 : state;

S1: state_next = en ? S2 : state;

S2: state_next = en ? S3 : state;

S3: state_next = en ? S0 : state;

endcase

assign out = (state == S3); // Output logic

endmodule

Конечный автомат (finite state machine, FSM) – дискретное устройство, имеющее входы и выходы, в каждый момент времени находящееся в одном состоянии из множества возможных

Конечный автомат определяется через:

Набор состояний
Начальное состояние
Диаграмма переходов между состояниями
Таблица выходов

16 of 34

fsm_mul: Datapath

a = i_a; b = i_b; res = 0;

while ((a != 0) && (b != 0)) {

res += a[0] ? 0 : b;

a >> 1;

b << 1;

}

return res;

17 of 34

fsm_mul: Datapath

a = i_a; b = i_b; res = 0;

while ((a != 0) && (b != 0)) {

res += a[0] ? 0 : b;

a >> 1;

b << 1;

}

return res;

18 of 34

fsm_mul: Datapath

a = i_a; b = i_b; res = 0;

while ((a != 0) && (b != 0)) {

res += a[0] ? 0 : b;

a >> 1;

b << 1;

}

return res;

19 of 34

fsm_mul: Datapath

a = i_a; b = i_b; res = 0;

while ((a != 0) && (b != 0)) {

res += a[0] ? 0 : b;

a >> 1;

b << 1;

}

return res;

20 of 34

fsm_mul: Datapath

a = i_a; b = i_b; res = 0;

while ((a != 0) && (b != 0)) {

res += a[0] ? 0 : b;

a >> 1;

b << 1;

}

return res;

21 of 34

fsm_mul: Datapath

a = i_a; b = i_b; res = 0;

while ((a != 0) && (b != 0)) {

res += a[0] ? 0 : b;

a >> 1;

b << 1;

}

return res;

22 of 34

fsm_mul: RTL

reg [N-1:0] a, b;

reg sel;

always @(posedge clk) begin

a <= sel ? i_a : (a >> 1);

b <= sel ? i_b : (b << 1);

o_res <= sel ? {N{1'b0}} : (o_res + (a[0] ? b : {N{1'b0}}));

end

wire empty = (a == {N{1'b0}}) || (b == {N{1'b0}});

23 of 34

fsm_mul: IDLE

reg [N-1:0] a, b;

reg sel;

always @(posedge clk) begin

a <= sel ? i_a : (a >> 1);

b <= sel ? i_b : (b << 1);

o_res <= sel ? {N{1'b0}} : (o_res + (a[0] ? b : {N{1'b0}}));

end

wire empty = (a == {N{1'b0}}) || (b == {N{1'b0}});

reg [1:0] state, state_next;

localparam [1:0] IDLE=0, STEP=1, DONE=2;

always @(posedge clk or negedge rst_n)

state <= !rst_n ? IDLE : state_next;

always @(*) begin

case (state)

IDLE: begin

sel = 1'b1;

o_vld = 1'b0;

state_next = i_vld ? STEP : state;

end

STEP: begin

sel = 1'b0;

o_vld = 1'b0;

state_next = empty ? DONE : state;

end

DONE: begin

sel = 1'b0;

o_vld = 1'b1;

state_next = IDLE;

end

endcase

end

24 of 34

fsm_mul: STEP

reg [N-1:0] a, b;

reg sel;

always @(posedge clk) begin

a <= sel ? i_a : (a >> 1);

b <= sel ? i_b : (b << 1);

o_res <= sel ? {N{1'b0}} : (o_res + (a[0] ? b : {N{1'b0}}));

end

wire empty = (a == {N{1'b0}}) || (b == {N{1'b0}});

reg [1:0] state, state_next;

localparam [1:0] IDLE=0, STEP=1, DONE=2;

always @(posedge clk or negedge rst_n)

state <= !rst_n ? IDLE : state_next;

always @(*)

case (state)

IDLE: begin

sel = 1'b1;

o_vld = 1'b0;

state_next = i_vld ? STEP : state;

end

STEP: begin

sel = 1'b0;

o_vld = 1'b0;

state_next = empty ? DONE : state;

end

DONE: begin

sel = 1'b0;

o_vld = 1'b1;

state_next = IDLE;

end

endcase

25 of 34

fsm_mul: DONE

reg [N-1:0] a, b;

reg sel;

always @(posedge clk) begin

a <= sel ? i_a : (a >> 1);

b <= sel ? i_b : (b << 1);

o_res <= sel ? {N{1'b0}} : (o_res + (a[0] ? b : {N{1'b0}}));

end

wire empty = (a == {N{1'b0}}) || (b == {N{1'b0}});

reg [1:0] state, state_next;

localparam [1:0] IDLE=0, STEP=1, DONE=2;

always @(posedge clk or negedge rst_n)

state <= !rst_n ? IDLE : state_next;

always @(*)

case (state)

IDLE: begin

sel = 1'b1;

o_vld = 1'b0;

state_next = i_vld ? STEP : state;

end

STEP: begin

sel = 1'b0;

o_vld = 1'b0;

state_next = empty ? DONE : state;

end

DONE: begin

sel = 1'b0;

o_vld = 1'b1;

state_next = IDLE;

end

endcase

26 of 34

fsm_mul: RTL

reg [N-1:0] a, b;

reg sel;

always @(posedge clk) begin

a <= sel ? i_a : (a >> 1);

b <= sel ? i_b : (b << 1);

o_res <= sel ? {N{1'b0}} : (o_res + (a[0] ? b : {N{1'b0}}));

end

wire empty = (a == {N{1'b0}}) || (b == {N{1'b0}});

reg [1:0] state, state_next;

localparam [1:0] IDLE=0, STEP=1, DONE=2;

always @(posedge clk or negedge rst_n)

state <= !rst_n ? IDLE : state_next;

always @(*)

case (state)

IDLE: begin

sel = 1'b1;

o_vld = 1'b0;

state_next = i_vld ? STEP : state;

end

STEP: begin

sel = 1'b0;

o_vld = 1'b0;

state_next = empty ? DONE : state;

end

DONE: begin

sel = 1'b0;

o_vld = 1'b1;

state_next = IDLE;

end

endcase

27 of 34

Verilog: операторы @ и wait

При симуляции синхронной логики управлять временем бывает удобнее с помощью операторов @ и wait вместо #
Конструкция @(expression) внутри блоков always или initial задерживает дальнейшее выполнение, пока выражение expression не изменит значение
Конструкция wait(expression) внутри блоков always или initial задерживает дальнейшее выполнение, пока выражение expression не станет истинным

reg clk = 1'b0;

reg rst_n = 1'b0;

always

#1 clk <= ~clk;

initial begin

@(posedge clk);

rst_n <= 1'b1;

end

reg [3:0] a = 4'h0;

initial begin

wait (rst_n);

@(posedge clk);

a <= 4'hA;

@(posedge clk);

a <= 4'hB;

end

28 of 34

Verilog: операторы repeat, while, for

Оператор repeat внутри always или initial выполняет тело цикла константное число раз
Цикл while внутри always или initial выполняет тело цикла, пока условие истинно
Цикл for внутри always или initial позволяет выполнять однотипные действия

В отличии от compile-time цикла generate for, такой for выполняется в ходе симуляции
Как и generate for, может использоваться в синтезируемом коде, если количество итераций известно в момент компиляции, а тело цикла – синтезируемый код

initial begin

repeat (5)

@(posedge clk);

rst_n <= 1'b1;

end

initial begin

while (!rst_n)

@(posedge clk);

a <= 1'b1;

end

integer i;

reg [W-1:0] idx;

wire [N-1:0] dat;

always @(*) begin

idx = 0;

for (i = 0; i < N; i = i + 1)

if (dat[i])

idx = i[W-1:0];

end

29 of 34

Verilog: task

Переиспользовать несинтезируемый код на Verilog можно с помощью задач (task)
Как и функции, задачи могут иметь входы (input), локальные переменные, использовать конструкции if, case, for для описания поведения, а также вызовы других задач и функций
В отличии от function, в task разрешено управлять временем через операторы #, @, wait

30 of 34

Verilog: system tasks

Verilog предусматривает стандартный набор системных задач (system tasks):

$display – печатает отформатированную аргументами строку в консоль
$finish – останавливает симуляцию
$time, $stime, $realtime – получает текущее время в целом/действительном формате
$signed, $unsigned – конвертирует в знаковый/беззнаковый тип
$random, $urandom, $urandom_range – генерирует знаковое/беззнаковое случайное число
$readmemh, $readmemb – инициализирует массив из текстового файла в hex/bin формате
$value$plusargs – получает значение аргументов командной строки
и др.

31 of 34

fsm_mul: Симуляция

task rnd_mul();

reg [N-1:0] res; // static local variable

begin

i_vld <= 1'b1;

i_a <= $urandom_range(0, 2**(N/2)-1);

i_b <= $urandom_range(0, 2**(N/2)-1);

@(posedge clk);

res <= i_a * i_b;

i_vld <= 1'b0; i_a <= {N{1'bX}}; i_b <= {N{1'bX}};

wait (o_vld == 1'b1);

if (res != o_res)

$display("[FAIL]");

@(posedge clk);

end

endtask

integer i;

initial begin

repeat (3) @(posedge clk);

rst_n <= 1'b1;

end

initial begin

wait (rst_n == 1'b1);

@(posedge clk);

for (i = 0; i < 10; i = i + 1)

rnd_mul();

end

32 of 34

fsm_mul: RTL Viewer

33 of 34

fsm_mul: State Machine Viewer

34 of 34

Заключение

Конечные автоматы – удобный инструмент для

проектирования синхронных блоков по микроархитектурной спецификации

Этапы проектирования FSM:

Определить входы и выходы
Определить состояния
Составить диаграмму переходов
Составить таблицу выходов

Применения FSM:

Выполнение последовательных действий
Управление логикой многотактных вычислений
Управление передачей данных по протоколу

Источник изображения: Micron MT41J256M16 DDR3 SDRAM Datasheet