Файл: Сумматор, компаратор, устройство сдвига и алу. Повышение скорости арифметических операций.pdf

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ
«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»
Московский институт электроники и математики им. А.Н.Тихонова
«Сумматор, компаратор, устройство сдвига и АЛУ.
Повышение скорости арифметических операций»
Практическая работа №5
по направлению 09.03.01 Информатика и вычислительная техника студента образовательной программы бакалавриата
«Информатика и вычислительная техника»
Проверил:
Лежнев Евгений Владимирович
Выполнил:
Степченко Александр Сергеевич
Корчагин Илья Александрович
БИВ196

Москва 2022 г.
Содержание
Задание......................................................................................................................................................3
Выполнение работы..............................................................................................................................3
Дополнительное задание 1...........................................................................................................3
Дополнительное задание 2...........................................................................................................7
Дополнительное задание 3.........................................................................................................14
Дополнительное задание 4.........................................................................................................18
Дополнительное задание 5.........................................................................................................24
Задание для самостоятельной работы...................................................................................29
Выводы.....................................................................................................................................................34
Контрольные вопросы.......................................................................................................................35 2

Задание
Выполните дополнительные задания для разделов 5.1.2, 5.1.5, 5.2.3, 5.3.1 и
5.3.4.
Выполнение работы
Дополнительное задание 1
Используя статический временной анализ, получите оценку максимальной тактовой частоты для сумматоров различной разрядности (8, 16, 32, 64, 128, 256
бит). На основе указанных оценок опишите зависимость роста данного параметра от разрядности сумматора в виде функции.
// adder.v module adder
#(
parameter WIDTH = 8
)
(
input [WIDTH - 1:0] x, y,
input carry_in,
output [WIDTH - 1:0] z,
output carry_out
);
assign {carry_out, z} = x + y + carry_in;
endmodule
// unit_delay.v module unit_delay
#(
parameter WIDTH = 1
)
(
3

input clock,
input [ WIDTH - 1:0 ] data_in,
output reg [ WIDTH - 1:0 ] data_out
);
always @(posedge clock)
data_out <= data_in;
endmodule
// register.v module register
#(
parameter WIDTH = 8
)
(
input clock,
input reset,
input load,
input [ WIDTH - 1:0 ] data_in,
output reg [ WIDTH - 1:0 ] data_out
);
always @(posedge clock, negedge reset)
if (reset)
data_out <= { WIDTH { 1'b0 } };
else if (load)
data_out <= data_in;
endmodule
// lab_05.v module lab_05(
input MAX10_CLK1_50,
input [1:0] KEY,
input [9:0] SW,
output [9:0] LEDR
);
parameter WIDTH = 8;
//wires
4

wire [WIDTH - 1:0] x_bus, y_bus, z_bus;
wire load_x, load_y;
wire carry_in_wire;
wire carry_out_wire;
wire clock;
wire reset;
assign clock = MAX10_CLK1_50;
assign reset = KEY[1];
//register for the arguments register #(.WIDTH(WIDTH)) x_register(
.clock(clock),
.reset(reset),
.load(load_x),
.data_in(SW[WIDTH:1]),
.data_out(x_bus)
);
register #(.WIDTH(WIDTH)) y_register(
.clock(clock),
.reset(reset),
.load(load_y),
.data_in(SW[WIDTH:1]),
.data_out(y_bus)
);
//carry_in synchronization unit_delay #(.WIDTH(1)) carry_in_register(
.clock(clock),
.data_in(SW[0]),
.data_out(carry_in_wire)
);
//argument selector assign load_x = SW[0] & KEY[0] ? 1'b1 : 1'b0;
assign load_y = SW[0] & KEY[0] ? 1'b1 : 1'b0;
//adder adder #(.WIDTH(WIDTH)) i_adder(
5

.carry_in(carry_in_wire),
.x(x_bus),
.y(y_bus),
.z(z_bus),
.carry_out(carry_out_wire)
);
//output synchronization unit_delay #(.WIDTH(WIDTH)) z_register(
.clock(clock),
.data_in(z_bus),
.data_out(LEDR[WIDTH - 1:0])
);
unit_delay #(.WIDTH(1)) carry_out_register(
.clock(clock),
.data_in(carry_out_wire),
.data_out(LEDR[9])
);
assign LEDR[8:WIDTH] = 0;
endmodule
Таблица 1
Максимальная тактовая частота для сумматоров разной разрядности
Разрядность, бит
Максимальная тактовая чистота, МГц
8 393.08 16 319.28 32 243.13 64 158.83 128 101.24 256 69.13 6

Рис. 1: Зависимость максимальной тактовой частоты от разрядности сумматора
Дополнительное задание 2
Модифицируйте АЛУ, приведенное в листинге 5.12, таким образом, чтобы оно поддерживало четыре новые операции и имело ряд дополнительных выходов, которые реализуют флаги переполнения для арифметических операций.
Создайте соответствующую структурную реализацию модифицированного АЛУ.
// alu.v
//ALU commands
`define ALU_AND 3'b000
`define ALU_OR 3'b001
`define ALU_ADD 3'b010
`define ALU_SUB 3'b011
`define ALU_SLL 3'b100
`define ALU_SRL 3'b101
`define ALU_SLT 3'b110
`define ALU_SGT 3'b111
module alu
7

#(
parameter WIDTH = 4,
parameter SHIFT = 2
)
(
input [WIDTH - 1:0] x, y,
input [SHIFT - 1:0] shamt,
input [2:0] operation,
output zero,
output reg overflow,
output reg [WIDTH - 1:0] result
);
always @(*) begin case (operation)
`ALU_AND: begin result = x & y;
overflow = 0;
end
`ALU_OR: begin result = x | y;
overflow = 0;
end
`ALU_ADD: begin
{overflow, result} = x + y;
end
`ALU_SUB: begin result = x - y;
overflow = 0;
end
`ALU_SLL: begin result = y << shamt;
overflow = 0;
end
`ALU_SRL: begin result = y >> shamt;
overflow = 0;
end
`ALU_SLT: begin result = (x < y) ? 1 : 0;
8

overflow = 0;
end
`ALU_SGT: begin result = (x > y) ? 1 : 0;
overflow = 0;
end endcase end
//Flags assign zero = (result == 0);
endmodule
Рис. 2: RTL-представление АЛУ с реализованными 4 дополнительными операциями
9

// bitwise_or.v module bitwise_or
#(
parameter WIDTH = 8
)
(
input [WIDTH - 1:0] x, y,
output [WIDTH - 1:0] z
);
assign z = x | y;
endmodule
// subtractor.v module subtractor
#(
parameter WIDTH = 8
)
(
input [WIDTH - 1:0] x, y,
output [WIDTH - 1:0] z
);
assign z = x - y;
endmodule
// right_shifter.v module right_shifter
#(
parameter WIDTH = 8,
// SHIFT specifies the number of bits for shamt argument parameter SHIFT = 3
)
(
input [WIDTH - 1:0] x,
input [SHIFT - 1:0] shamt,
output [WIDTH - 1:0] z
10

);
assign z = x >> shamt;
endmodule
// sgt.v module sgt
#(
parameter WIDTH = 8
)
(
input [WIDTH - 1:0] x, y,
output [WIDTH - 1:0] z
);
assign z = (x > y) ? 1 : 0;
endmodule
// alu_stractural.v module alu_structural
#(
parameter WIDTH = 4,
parameter SHIFT = 2
)
(
input [WIDTH - 1:0] x, y,
input [SHIFT - 1:0] shamt,
input [2:0] operation,
input carry_in,
output zero,
output overflow,
output [WIDTH - 1:0] result
);
wire [8 * WIDTH - 1:0] t; // This ALU supports 8 operations
// Bitwise AND
bitwise_and #(.WIDTH(WIDTH)) i_and(
.x(x),
.y(y),
11

.z(t[WIDTH - 1:0])
);
// Bitwise OR
bitwise_or #(.WIDTH(WIDTH)) i_or(
.x(x),
.y(y),
.z(t[2 * WIDTH - 1:WIDTH])
);
// Adder adder #(.WIDTH(WIDTH)) i_adder(
.x(x),
.y(y),
.carry_in(carry_in),
.z(t[3 * WIDTH - 1:2 * WIDTH]),
.carry_out(overflow)
);
// Subtractor subtractor #(.WIDTH(WIDTH)) i_subtractor(
.x(x),
.y(y),
.z(t[4 * WIDTH - 1:3 * WIDTH])
);
// Left shifter left_shifter #(
.WIDTH(WIDTH),
.SHIFT(SHIFT)
)
i_left_shifter(
.x(x),
.shamt(shamt),
.z(t[5 * WIDTH - 1:4 * WIDTH])
);
// Right shifter right_shifter #(
12

.WIDTH(WIDTH),
.SHIFT(SHIFT)
)
i_right_shifter(
.x(x),
.shamt(shamt),
.z(t[6 * WIDTH - 1:5 * WIDTH])
);
// SLT
slt #(.WIDTH( WIDTH)) i_slt(
.x(x),
.y(y),
.z(t[7 * WIDTH - 1:6 * WIDTH ] )
);
// SGT
sgt #(.WIDTH( WIDTH)) i_sgt(
.x(x),
.y(y),
.z(t[8 * WIDTH - 1:7 * WIDTH ] )
);
// Multiplexer bn_mux_n_1_generate #(
.DATA_WIDTH(WIDTH),
.SEL_WIDTH(3)
)
i_mux(
.data(t),
.sel(operation),
.y(result)
);
// Flags assign zero = (result == 0);
endmodule
13

Рис. 3: RTL-представление структурной реализации АЛУ
Дополнительное задание 3
Реализуйте блочный сумматор с каскадным переносом разрядности 16, 32,
64 и 128 бит. Варьируя значения параметров разрядности блока (WIDTH) и количества блоков (BLOCK_COUNT), найдите их оптимальное соотношение с точки зрения задержки реализуемого блока, то есть такое соотношение, на котором достигается максимальная тактовая частота. Объясните полученные результаты.
// lab_05.v module lab_05
(
input MAX10_CLK1_50,
14

input [1:0] KEY,
input [9:0] SW,
output [9:0] LEDR
);
parameter GROUP_COUNT = 2;
parameter GROUP_WIDTH = 2;
parameter WIDTH = GROUP_COUNT * GROUP_WIDTH;
//WIDTH should be no more than 8
wire [WIDTH - 1:0] x_bus, y_bus, z_bus; wire carry_in_wire, carry_out_wire;
assign reset = KEY[1];
assign clock = MAX10_CLK1_50;
//argument selector assign load_x = SW[9] & KEY[0] ? 1'b1 : 1'b0;
assign load_y = SW[9] & KEY[0] ? 1'b1 : 1'b0;
//x synchronization register #(.WIDTH(WIDTH)) x_register
(
.clock (clock ),
.reset (reset ),
.load (load_x ),
.data_in (SW[WIDTH:1]),
.data_out(x_bus )
);
//y synchronization register #(.WIDTH(WIDTH)) y_register
(
.clock (clock ),
.reset (reset ),
.load (load_y ),
.data_in (SW[WIDTH:1]),
.data_out(y_bus )
);
15

//carry in synchronization unit_delay #(.WIDTH(1)) carry_in_register
(
.clock (clock ),
.data_in (SW[ 0 ] ),
.data_out(carry_in_wire)
);
//adder group_ripple_carry_adder
#(
.BLOCK_COUNT(GROUP_COUNT),
.WIDTH (GROUP_WIDTH)
)
i_RCA
(
.carry_in (carry_in_wire ),
.x (x_bus ),
.y (y_bus ),
.z (z_bus ),
.carry_out(carry_out_wire)
);
//adder result synchronization unit_delay #(.WIDTH(WIDTH)) z_register
(
.clock (clock ),
.data_in (z_bus ),
.data_out(LEDR[WIDTH - 1:0])
);
//carry out synchronization unit_delay #(.WIDTH(1)) carry_out_register
(
.clock (clock ),
.data_in (carry_out_wire),
.data_out(LEDR[9] )
);
16

assign LEDR[8] = 0;
endmodule
Рис. 4: RTL-представление модуля верхнего уровня для блочного сумматора с каскадным переносом
Таблица 2
Максимальная тактовая частота для блочного сумматора разрядности 16
GROUP_WIDTH
GROUP_COUNT
Максимальная тактовая частота, МГц
16 1
295.42 8
2 186.15 4
4 98.4 2
8 312.23 1
16 44.55
Таблица 3
Максимальная тактовая частота для блочного сумматора разрядности 32 17

GROUP_WIDTH
GROUP_COUNT
Максимальная тактовая частота, МГц
32 1
240.81 16 2
163.82 8
4 99.85 4
8 65.49 2
16 235.71 1
32 18.14
Таблица 4
Максимальная тактовая частота для блочного сумматора разрядности 64
GROUP_WIDTH
GROUP_COUNT
Максимальная тактовая частота, МГц
64 1
223.07 32 2
135.43 16 4
92.68 8
8 69.96 4
16 31.15 2
32 161.75 1
64 8.99
Из таблиц 2-4 видно, что наибольшая максимальная частота достигается при параметрах GROUP_WIDTH=k, GROUP_COUNT=1 и GROUP_WIDTH=2,
GROUP_COUNT=k/2, где k – разрядность сумматора.
Дополнительное задание 4
Используя статический временной анализ, получите оценку максимальной тактовой частоты сумматора с предварительным вычислением переноса для разных значений разрядности (8, 16, 32, 64 и 128 бит). Опишите зависимость изменения данного параметра как функцию от разрядности исследуемого сумматора.
18

// carry_lookahead_adder.v module carry_lookahead_adder
#(
parameter WIDTH = 8
)
(
input carry_in,
input [WIDTH - 1:0] x,
input [WIDTH - 1:0] y,
output [WIDTH - 1:0] z,
output carry_out,
output group_generate,
output group_propagate
);
wire [WIDTH:0] carry;
wire [WIDTH - 1:0] generate_wire, propagate_wire;
assign carry[0] = carry_in;
carry_lookahead_generator #(.WIDTH(WIDTH)) i_CLG(
.carry_in(carry_in),
.generate_in(generate_wire),
.propagate_in(propagate_wire),
.carry(carry[WIDTH:1]),
.group_generate(group_generate),
.group_propagate(group_propagate)
);
generate genvar i;
for (i = 0; i <= WIDTH - 1; i = i + 1)
begin: stage
// Create generate and propagate signals assign generate_wire [i] = x[i] & y[i];
assign propagate_wire[i] = x[i] ^ y[i];
// Calculate sum (z bus)
assign z[i] = carry[i] ^ propagate_wire[i];
19

end endgenerate assign carry_out = carry[WIDTH];
endmodule
// carry_lookahead_generator.v module carry_lookahead_generator
#(
parameter WIDTH = 8
)
(
input carry_in,
input [WIDTH - 1:0] generate_in, propagate_in,
output [WIDTH:1] carry,
output group_generate, group_propagate
);
// Temporary wires for the carry calculation wire [((WIDTH + 1) * WIDTH) / 2 - 1:0] p_temp, g_temp;
wire [WIDTH - 1:0] c_temp, pg_temp;
generate genvar i, j;
for (i = 0; i <= WIDTH - 1; i = i + 1)
begin: stage
// Calculate carry for (j = 0; j <= i; j = j + 1)
begin: block assign p_temp[((i + 1) * i) / 2 + j] = & propagate_in[i : j];
case(j)
0: assign g_temp[((i + 1) * i) / 2 + j] = generate_in[i];
default: assign g_temp[((i + 1) * i) / 2 + j] = p_temp[((i + 1) * i) / 2 + j] &
generate_in[j - 1];
endcase end assign c_temp [i] = p_temp[((i + 1) * i) / 2] & carry_in;
assign pg_temp[i] = | g_temp[(( i + 2) * (i + 1)) / 2 - 1:((i + 1) * i) / 2];
20

assign carry [i + 1] = pg_temp[i] | c_temp[i];
end endgenerate assign group_propagate = p_temp [(WIDTH * (WIDTH - 1)) / 2];
assign group_generate = pg_temp[WIDTH - 1];
endmodule
// lab_05_carry_lookahead.v module lab_05_carry_lookahead
(
input MAX10_CLK1_50,
input [1:0] KEY,
input [9:0] SW,
output [9:0] LEDR
);
// WIDTH should be no more than 9
parameter WIDTH = 4;
wire [WIDTH - 1:0] x_bus, y_bus, z_bus;
wire carry_in_wire, carry_out_wire;
assign reset = KEY[1];
assign clock = MAX10_CLK1_50;
// argument selector assign load_x = SW[9] & KEY[0] ? 1'b1 : 1'b0;
assign load_y = SW[9] & KEY[0] ? 1'b1 : 1'b0;
// x synchronization register #(.WIDTH(WIDTH)) x_register(
.clock(clock),
.reset(reset),
.load(load_x),
.data_in(SW[WIDTH:1]),
.data_out(x_bus)
);
21

// y synchronization register #(.WIDTH(WIDTH)) y_register(
.clock(clock),
.reset(reset),
.load(load_y),
.data_in(SW[WIDTH:1]),
.data_out(y_bus)
);
// carry in synchronization unit_delay #(.WIDTH(1)) carry_in_register(
.clock(clock),
.data_in(SW[0]),
.data_out(carry_in_wire)
);
// adder carry_lookahead_adder #(.WIDTH(WIDTH)) i_CLA(
.carry_in(carry_in_wire),
.x(x_bus),
.y(y_bus),
.z(z_bus),
.carry_out(carry_out_wire)
);
// adder result synchronization unit_delay #(.WIDTH(WIDTH)) z_register(
.clock(clock),
.data_in(z_bus),
.data_out(LEDR[WIDTH - 1:0])
);
// carry out synchronization unit_delay #(.WIDTH(1)) carry_out_register(
.clock(clock),
.data_in(carry_out_wire),
.data_out(LEDR[9])
);
22

endmodule
Рис. 5: RTL-представление сумматора с вычислением переносов по явным формулам
Таблица 5
Максимальная тактовая частота сумматора различной разрядности
Разрядность, бит
Максимальная тактовая частота, МГц
8 263.09 16 238,18 32 208.38 64 133.05 128 111.12 23

Рис. 6: Зависимость максимальной тактовой частоты от разрядности сумматора
Дополнительное задание 5
Используя статический временной анализ, опишите зависимость максимальной тактовой частоты префиксного сумматора как функцию от разрядности исследуемого устройства. Сравните это поведение с поведением аналогичных функций для сумматора с последовательным вычислением переноса и для блочного сумматора с предварительным вычислением переноса.
// gp_cell.v module gp_cell(
input wire g_left, g_right, p_left, p_right,
output wire g_out, p_out
);
assign g_out = g_left | p_left & g_right;
assign p_out = p_left & p_right;
endmodule
// prefix_carry_generator.v
24

module prefix_carry_generator
# (
parameter LEVELS = 3,
parameter WIDTH = 2 ** LEVELS
)
(
input carry_in,
input [WIDTH - 1:0] generate_in, propagate_in,
output [WIDTH - 1:0] carry,
output carry_out
);
// Sklansky adder wire [WIDTH:0] g_temp [LEVELS:0];
wire [WIDTH:0] p_temp [LEVELS:0];
assign g_temp[0] = {generate_in, carry_in};
assign p_temp[0] = {propagate_in, carry_in};
generate genvar i, j;
for (i = 0; i <= LEVELS - 1; i = i + 1)
begin : stage for (j = 0; j <= WIDTH; j = j + 1)
begin : block if( (j / 2 ** i) % 2 == 1 )
gp_cell i_gp_cell(
.g_left (g_temp[i][j]),
.g_right(g_temp[i][(j / (2**i)) * (2**i) - 1]),
.p_left (p_temp[i][j]),
.p_right(p_temp[i][(j / (2**i)) * (2**i) - 1]),
.g_out (g_temp[i+1][j]),
.p_out (p_temp[i+1][j])
);
else begin assign g_temp[i+1][j] = g_temp[i][j];
assign p_temp[i+1][j] = p_temp[i][j];
end end
25

end endgenerate assign carry = g_temp[LEVELS][WIDTH-1:0];
assign carry_out = g_temp[LEVELS][WIDTH]|p_temp[LEVELS][WIDTH]&g_temp[LEVELS][WIDTH-1];
endmodule
// prefix_adder.v module prefix_adder
# (
parameter LEVELS = 3,
parameter WIDTH = 2 ** LEVELS
)
(
input carry_in,
input [WIDTH - 1:0] x,
input [WIDTH - 1:0] y,
output [WIDTH - 1:0] z,
output carry_out
);
wire [WIDTH - 1:0] carry;
wire [WIDTH - 1:0] generate_wire, propagate_wire;
prefix_carry_generator
#(.LEVELS(LEVELS),.WIDTH(WIDTH))
i_PCG
(
.carry_in(carry_in),
.generate_in(generate_wire),
.propagate_in(propagate_wire),
.carry(carry),
.carry_out(carry_out)
);
generate genvar i;
for (i = 0; i <= WIDTH - 1; i = i + 1)
26

begin: stage
// Create generate and propagate signals assign generate_wire[i] = x[i] & y[i];
assign propagate_wire[i] = x[i] ^ y[i];
// Calculate sum (z bus)
assign z[i] = carry[i] ^ propagate_wire[i];
end endgenerate endmodule
// lab_05_prefix.v module lab_05_prefix
(
input MAX10_CLK1_50,
input [1:0] KEY,
input [9:0] SW,
output [9:0] LEDR
);
// LEVELS should be no more than 3
parameter LEVELS = 2;
parameter WIDTH = 2 ** LEVELS;
wire [WIDTH - 1:0] x_bus, y_bus, z_bus;
wire carry_in_wire, carry_out_wire;
assign reset = KEY[1];
assign clock = MAX10_CLK1_50;
// argument selector assign load_x = SW[9] & KEY[0] ? 1'b1 : 1'b0;
assign load_y = SW[9] & KEY[0] ? 1'b1 : 1'b0;
// x synchronization register #(.WIDTH(WIDTH)) x_register(
.clock(clock),
.reset(reset),
.load(load_x),
.data_in(SW[WIDTH:1]),
27

.data_out(x_bus)
);
// y synchronization register #(.WIDTH(WIDTH)) y_register(
.clock(clock),
.reset(reset),
.load(load_y),
.data_in(SW[WIDTH:1]),
.data_out(y_bus)
);
// carry in synchronization unit_delay #(.WIDTH(1)) carry_in_register(
.clock(clock),
.data_in(SW[0]),
.data_out(carry_in_wire)
);
// adder prefix_adder #(.LEVELS(LEVELS)) i_prefix(
.carry_in(carry_in_wire),
.x(x_bus),
.y(y_bus),
.z(z_bus),
.carry_out(carry_out_wire)
);
// adder result synchronization unit_delay #(.WIDTH(WIDTH)) z_register(
.clock(clock),
.data_in(z_bus),
.data_out(LEDR[WIDTH - 1:0])
);
// carry out synchronization unit_delay #(.WIDTH(1)) carry_out_register(
.clock(clock),
.data_in(carry_out_wire),
28

.data_out(LEDR[9])
); endmodule
Рис. 7: RTL-представление префиксного сумматора
Таблица 6
Максимальная тактовая частота сумматора для различных разрядностей
Разрядность, бит
Максимальная тактовая частота, МГц
8 324.44 16 298.27 32 257.67 64 201.54 128 144.65
Из таблиц 1-6 видно, что при различных разрядностях большую максимальную тактовую частоту имеют различные реализации сумматоров.
Задание для самостоятельной работы
Используя примеры кода из данного пособия, реализуйте следующие комбинационные блоки.
29

10. Параллельный префиксный сумматор Брента–Кунга, имеющий настраиваемое число уровней префиксной сети при помощи параметра LEVELS.
// gp_cell.v module gp_cell(
input wire g_left, g_right, p_left, p_right,
output wire g_out, p_out
);
assign g_out = g_left | p_left & g_right;
assign p_out = p_left & p_right;
endmodule
// prefix_carry_generator.v module prefix_carry_generator
# (
parameter LEVELS = 3,
parameter WIDTH = 2 ** LEVELS
)
(
input carry_in,
input [WIDTH - 1:0] generate_in, propagate_in,
output [WIDTH - 1:0] carry,
output carry_out
);
// Sklansky adder wire [WIDTH:0] g_temp [LEVELS:0];
wire [WIDTH:0] p_temp [LEVELS:0];
assign g_temp[0] = {generate_in, carry_in};
assign p_temp[0] = {propagate_in, carry_in};
generate genvar i, j;
for (i = 0; i <= LEVELS - 1; i = i + 1)
begin : stage
30

for (j = 0; j <= WIDTH; j = j + 1)
begin : block if( (j / 2 ** i) % 2 == 1 )
gp_cell i_gp_cell(
.g_left (g_temp[i][j]),
.g_right(g_temp[i][(j / (2**i)) * (2**i) - 1]),
.p_left (p_temp[i][j]),
.p_right(p_temp[i][(j / (2**i)) * (2**i) - 1]),
.g_out (g_temp[i+1][j]),
.p_out (p_temp[i+1][j])
);
else begin assign g_temp[i+1][j] = g_temp[i][j];
assign p_temp[i+1][j] = p_temp[i][j];
end end end endgenerate assign carry = g_temp[LEVELS][WIDTH-1:0];
assign carry_out = g_temp[LEVELS][WIDTH]|p_temp[LEVELS][WIDTH]&g_temp[LEVELS][WIDTH-1];
endmodule
// prefix_adder.v module prefix_adder
# (
parameter LEVELS = 3,
parameter WIDTH = 2 ** LEVELS
)
(
input carry_in,
input [WIDTH - 1:0] x,
input [WIDTH - 1:0] y,
output [WIDTH - 1:0] z,
output carry_out
);
wire [WIDTH - 1:0] carry;
31

wire [WIDTH - 1:0] generate_wire, propagate_wire;
prefix_carry_generator
#(.LEVELS(LEVELS),.WIDTH(WIDTH))
i_PCG
(
.carry_in(carry_in),
.generate_in(generate_wire),
.propagate_in(propagate_wire),
.carry(carry),
.carry_out(carry_out)
);
generate genvar i;
for (i = 0; i <= WIDTH - 1; i = i + 1)
begin: stage
// Create generate and propagate signals assign generate_wire[i] = x[i] & y[i];
assign propagate_wire[i] = x[i] ^ y[i];
// Calculate sum (z bus)
assign z[i] = carry[i] ^ propagate_wire[i];
end endgenerate endmodule
// lab_05_prefix.v module lab_05_prefix
(
input MAX10_CLK1_50,
input [1:0] KEY,
input [9:0] SW,
output [9:0] LEDR
);
// LEVELS should be no more than 3
parameter LEVELS = 2;
parameter WIDTH = 2 ** LEVELS;
32

wire [WIDTH - 1:0] x_bus, y_bus, z_bus;
wire carry_in_wire, carry_out_wire;
assign reset = KEY[1];
assign clock = MAX10_CLK1_50;
// argument selector assign load_x = SW[9] & KEY[0] ? 1'b1 : 1'b0;
assign load_y = SW[9] & KEY[0] ? 1'b1 : 1'b0;
// x synchronization register #(.WIDTH(WIDTH)) x_register(
.clock(clock),
.reset(reset),
.load(load_x),
.data_in(SW[WIDTH:1]),
.data_out(x_bus)
);
// y synchronization register #(.WIDTH(WIDTH)) y_register(
.clock(clock),
.reset(reset),
.load(load_y),
.data_in(SW[WIDTH:1]),
.data_out(y_bus)
);
// carry in synchronization unit_delay #(.WIDTH(1)) carry_in_register(
.clock(clock),
.data_in(SW[0]),
.data_out(carry_in_wire)
);
// adder prefix_adder #(.LEVELS(LEVELS)) i_prefix(
.carry_in(carry_in_wire),
33

.x(x_bus),
.y(y_bus),
.z(z_bus),
.carry_out(carry_out_wire)
);
// adder result synchronization unit_delay #(.WIDTH(WIDTH)) z_register(
.clock(clock),
.data_in(z_bus),
.data_out(LEDR[WIDTH - 1:0])
);
// carry out synchronization unit_delay #(.WIDTH(1)) carry_out_register(
.clock(clock),
.data_in(carry_out_wire),
.data_out(LEDR[9])
); endmodule
Рис. 8: RTL-представление параллельного префиксного сумматора Брента-Кунга
Выводы
После выполнения данной лабораторной работы были приобретены навыки создания Verilog модулей, описывающих работу сумматоров, компараторов,
устройств сдвига и АЛУ. Были изучены различные реализации двоичных
34

сумматоров, в том числе неполный, полны, а также с вычислением переносом по рекурентным и явным формулам.
Контрольные вопросы
1. Что такое комбинационный сумматор? Приведите примеры реализаций.
Ответ: Сумматором (Adder) называют вычислительный блок, реализующий сложение двух n-разрядных двоичных чисел x = (xn-1, ..., x0 ) и y = (yn-1, ..., y0).
Результат сложения часто представляют в виде n-разрядного двоичного числа z =
(zn-1, ..., z0) и дополнительного однобитного двоичного числа cout, которое сигнализирует о возникновении бита переноса (переполнения), то есть ситуации,
когда результирующая сумма является (n + 1)-битным числом.
2. С помощью каких средств Quartus Prime можно проанализировать технологически зависимую и структурную реализацию блоков проекта?
Ответ: С помощью RTL-Viewer и Technology Map Viewer.
3. Опишите пример сумматора с синхронизированными входами и выходами. Для чего он использовался в данной главе?
Ответ: Код в листинге 5.6 представляет модуль сумматора, все входы и выходы которого синхронизированы при помощи элементов единичной
35

задержки и регистров. Данный сумматор использовался для проведения статического временного анализа.
4. Опишите, для чего нужен статический временной анализ. Как осуществляется статический временной анализ в Quartus Prime?
Ответ: Статический временной анализ нужен для аналиа быстродействия комбинационной схемы. Во-первых, комбинационную схему нужно превратить в последовательностную, добавив синхронизацию всех входных и выходных сигналов. Во-вторых, требуется указать файл, который будет содержать основные характеристики синхронизирующего сигнала и другие параметры, необходимые для проведения статического временного анализа.
5. Опишите назначение компаратора и приведите примеры его реализации.
Ответ: Компараторами (comparator) называют различные логические устройства, предназначенные для сравнения чисел между собой. Чаще всего входами компаратора являются две n-разрядные шины, а выходом – сигнальный однобитный выход, который содержит единицу, если входные аргументы удовлетворяют выбранному соотношению сравнения, и ноль в ином случае. При этом входные аргументы трактуются как целые числа со знаком или без знака, а в качестве отношения сравнения выступает сравнение на равенство, строгое неравенство или нестрогое неравенство аргументов.
Пример поведенческого описания компаратора на языке Verilog, реализующего различные типы отношения сравнения, представлен в листинге ниже:
36

6. Опишите назначение устройства сдвига и приведите пример его реализации. Каких типов бывают устройства сдвига?
Ответ: Устройствами сдвига (shifter) и устройствами циклического сдвига
(barrel shif ters, rotators) являются логические блоки, представляющие собой сдвиг в адресации элементов некоторой шины данных на заданное число позиций.
В свою очередь, устройства циклического сдвига интерпретируют индексы шины данных как замкнутые в кольцо, то есть следующим индексом после (n 1)
−
является индекс 0. Таким образом, сдвиг индексов происходит по модулю длины шины данных.
37

7. АЛУ – назначение и пример реализации. Почему АЛУ обычно реализуют как комбинационное устройство?
Ответ: Арифметико-логическое устройство (АЛУ) представляет собой блок,
позволяющий выполнять ряд арифметических и логических операций над заданным количеством аргументов. Конкретный набор операций, количество операндов и разрядность у поддерживаемых операций могут очень сильно варьироваться в зависимости от типа устройства, для которого разрабатывается
АЛУ. Кроме того, очень часто АЛУ имеет ряд дополнительных выходов, которые передают специальные сигналы-индикаторы (флаги), которые обращаются в единицу при наступлении определенного события (например, при переполнении результата или обращении результата в ноль).
Следующий листинг представляет описание упрощенного АЛУ,
поддерживающего всего четыре операции:
38

АЛУ представляет комбинационное устройство, и его сложность равна сумме сложностей блоков, реализующих поддерживаемые операции, и мультиплексора. В свою очередь, задержка такого АЛУ равна сумме задержки мультиплексора и максимальной задержки среди блоков, которые реализуют поддерживаемые операции. В силу модульности представленного описания любой блок может быть заменен на аналогичный по функциональности блок, но имеющий более оптимальные параметры задержки или сложности.
8. Иерархический подход к проектированию сумматоров различной размерности. Как осуществляется перенос и каскадное соединение сумматоров при иерархическом подходе?
Ответ: Оптимизировать реализацию сумматора с каскадным переносом можно за счет использования более крупных блоков, которые осуществляют сложение сразу нескольких битов исходных аргументов вместо однобитных блоков полного сумматора. Соответствующее описание блочного сумматора с каскадным переносом представлено в листинге 5.21.
Для переноса и каскадного соединения сумматоров при иерархическом подходе carry_out одного блока подается на carry_in другого блока и т.д.
9. Как осуществляется построение сумматоров с ускоренным групповым переносом?
Ответ: Основная идея, позволяющая существенно снизить задержку срабатывания сумматора, заключается в том, что вместо последовательной схемы расчета сигналов переноса (carry) используются специальные схемы, которые позволяют ускорить процесс вычисления этих сигналов и сделать его независимым от вычисления выходных значений сумматора. Для указанных целей введем ряд вспомогательных сигналов, которые характеризуют состояние сигналов переноса.
10. Опишите, как выполняется двухуровневая реализация сумматора с ускоренным групповым переносом.
Ответ: Задержку схемы и ее сложность можно сбалансировать при помощи формирования многоуровневой структуры из сумматоров и блоков
39

предварительного вычисления переноса. Такая структура предполагает наличие множества сумматоров, вычисляющих вспомогательные сигналы генерации и передачи переноса для группы аргументов. Данные сигналы впоследствии используются блоками предварительного вычисления переноса для вычисления сигналов переноса, которые подаются на соответствующие входы рассматриваемого множества сумматоров.
11. Опишите, как реализуется префиксный сумматор, в чем его отличие от других типов сумматоров.
Ответ:
40

41