Automatic Data Path Extraction in Large-Scale
Register-Transfer Level Designs
Wei Song, Jim Garside and Doug Edwards
School of Computer Science, the University of Manchester
Manchester M13 9PL United Kingdom
02/06/2014
Advanced Processor Technologies Group
The School of Computer Science
Motivation
• Data path extraction is important
– Hardware verification
– Synthesis for asynchronous circuits
– System partition
• Methodology
– State-space analysis
• actuate but slow and not scalable
– Pattern matching
• Fast, scalable but inaccurate
• Accuracy depends on accurate type recognition
Advanced Processor Technologies Group School of
Computer Science
02/06/2014
2
Tool Flow
Verilog RTL
Verilog RTL
Bison+Flex, support
synthesizable Verilog
2001.
Parser
A new graphic abstraction
to reveal relations between
Verilog signals.
Abstract
Syntax Tree
Signal-level
DFG
Verilog RTL
Data Path Extraction
Data Path Only
Signal-level DFG
Still directly mapped with
the AST. Possible for code
extraction.
Advanced Processor Technologies Group School of
Computer Science
Graphic
Trimming
Remove control
related signals.
02/06/2014
Remove
Control Arcs
Remove control
relations.
3
Signal-Level Data Flow Graph (DFG)
module GCD (Clock,Reset,Load,A,B,Done,Y);
input Clock,Reset,Load;
input [7:0] A,B;
output Done;
output [7:0] Y;
reg A_lessthan_B, Done;
reg [7:0] A_New, A_Hold, B_Hold, Y;
always @(posedge Clock)
if(Reset) begin
A_Hold = 0; B_Hold = 0;
end else if(Load) begin
A_Hold = A; B_Hold = B;
end else if(A_lessthan_B) begin
A_Hold = B_Hold;
B_Hold = A_New;
end else
A_Hold = A_New;
always @(A_Hold or B_Hold)
if(A_Hold >= B_Hold) begin
A_lessthan_B = 0;
A_New = A_Hold - B_Hold;
end else begin
A_lessthan_B = 1;
A_New = A_Hold;
end
always @(A_Hold or B_Hold)
if(B_Hold == 0) begin
Done = 1; Y = A_Hold;
end else begin
Done = 0; Y = 0;
end
endmodule
Advanced Processor Technologies Group School of
Computer Science
A Greatest Common Divider (GCD) Calculator
A_P
Reset_P
I
I
Reset
Load_P
I
A
B_P
Clock_P
I
Load
I
Clock
B
A_lessthan_B
A_Hold
FF
FF
B_Hold
A_New
I
i_port
O
o_port
wire
Done
Y
FF
MODULE
register
module
clock
Y_P
O
02/06/2014
Done_P
O
control
data
4
Definition of a Signal-Level DFG
A_P
Reset_P
I
I
Reset
Load_P
I
A
B_P
Clock_P
I
Load
I
Clock
B
A signal-level DFG is a directed multi-graph denoted by a six-tuple:
A_lessthan_B
A_Hold
FF
FF
B_Hold
A_New
I
i_port
O
o_port
wire
FF
Done
Y
MODULE
register
DFG (V , A,TV ,FV ,T A ,FA )
V
a finite set of nodes
representing Verilog components (signal and module)
A V V
a finite set of arcs connecting nodes
TV
a set of node types { reg ,wire ,in ,out , module }
FV :V TV map types to nodes
TA
a set of arc types {control , data ,clock ,reset }
FA : A T A map types to arcs
module
clock
Y_P
O
Done_P
O
Advanced Processor Technologies Group School of
Computer Science
control
data
02/06/2014
5
Node insertion
input Clock,Reset,Load;
input [7:0] A,B;
output Done;
output [7:0] Y;
reg A_lessthan_B, Done;
reg [7:0] A_New, A_Hold, B_Hold, Y;
I
Advanced Processor Technologies Group School of
Computer Science
I
Reset
always @(posedge Clock)
if(Reset) begin
A_Hold = 0; B_Hold = 0;
end else if(Load) begin
A_Hold = A; B_Hold = B;
end else if(A_lessthan_B) begin
A_Hold = B_Hold;
B_Hold = A_New;
end else
A_Hold = A_New;
always @(A_Hold or B_Hold)
if(B_Hold == 0) begin
Done = 1; Y = A_Hold;
end else begin
Done = 0; Y = 0;
end
A_P
Reset_P
Load_P
I
A
B_P
Clock_P
I
Load
I
Clock
B
A_lessthan_B
A_Hold
FF
FF
B_Hold
A_New
Done
Y
Latch will be detected
by case analysis.
02/06/2014
Y_P
O
Done_P
O
6
Type Estimation of Arcs
Relation Tree
always @(posedge Clock)
if(Reset) begin
A_Hold = 0; B_Hold = 0;
end else if(Load) begin
A_Hold = A; B_Hold = B;
end else if(A_lessthan_B) begin
A_Hold = B_Hold;
B_Hold = A_New;
end else
A_Hold = A_New;
Reset
A
A_New
B_Hold
A_Hold = A_New
A
A_lessthan_B
If(A_lessthan_B)
Load
0
Clock
Clock
Load
Reset
A_Hold = 0
If(Reset)
(posedge Clock)
A_Hold
A_lessthan_B
A_Hold
FF
A_New
Arc connection
in DFG
Advanced Processor Technologies Group School of
Computer Science
02/06/2014
control recognition:
if(sig)
case(sig)
C = sig?A:B
D = mem[addr]
7
Remove Control Arcs
A_P
Reset_P
I
I
Reset
Load_P
I
A
B_P
Load
I
I
Clock
B
A_P
Reset_P
Clock_P
I
I
Reset
A
A_lessthan_B
A_Hold
FF
B_P
Clock_P
I
Load
I
Clock
B
A_lessthan_B
FF
B_Hold
A_Hold
FF
FF
A_New
B_Hold
A_New
Done
Y
Y_P
O
Load_P
I
Done
Y
Done_P
Y_P
O
Advanced Processor Technologies Group School of
Computer Science
O
02/06/2014
Done_P
O
8
Recursively Remove Dangling Components
A_P
Reset_P
I
I
Reset
Load_P
I
A
B_P
Clock_P
I
Load
A_P
I
Clock
B
B_P
I
I
A
Nodes to be
recursively removed
B
A_lessthan_B
A_Hold
FF
FF
B_Hold
A_Hold
FF
FF
A_New
A_New
Done
Y
Y_P
O
dangling
wire
B_Hold
Y
Done_P
O
Advanced Processor Technologies Group School of
Computer Science
Y_P
FF
dangling
FF
O
dangling
output
I
dangling
input
module
dangling
module
O
02/06/2014
9
Hierarchical Designs (SHA-3 Encoder)
in
out
data path
in the manual
automatic
generated
DFG
FF
in_P
counter
round
const
out_P
I
one
round
O
out
in
FF
extracted
data path
i
FF
rconst
MODULE
Advanced Processor Technologies Group School of
Computer Science
round_in
rc
round
round_out
MODULE
02/06/2014
10
Large-Scale Test Cases
I/O
Module
Signal
I/O
Module
Signal
Time
(s)
OR1200
52
37
2074
40
33
1142
1
RSD
7
24
1063
3
23
659
<1
NOVA
19
140
7043
9
103
4279
10
Designs
OR1200:
RSD:
NOVA:
Signal-level DFG
Data path DFG
A 5-stage OpenRISC processor.
An industrial standard Reed-Solomon decoder.
An FPGA proven H.264/AVC baseline decoder.
Intel CoreTM2 Due 3.00 GHz with 2GB memory
Advanced Processor Technologies Group School of
Computer Science
02/06/2014
11
Possible Usages
• Signal-level DFG
– Code extraction
– Controller detection*
– Interface recognition (Memory, bus, handshake)
• Data path extraction
– Data-flow analysis by switching back-annotation
– System partition
* Wei Song and Jim Garside. Automatic controller detection for large scale RTL designs. In
Proc. of EUROMICRO Conference on Digital System Design (DSD), Santander, Spain, pp.
884–851, September 2013
Advanced Processor Technologies Group School of
Computer Science
02/06/2014
12
Conclusion
• Signal-level DFG
– A graphic representation of signal relations in RTL.
– A typed and hierarchical multi-graph.
• Data path extraction
– Trim all control related arcs and nodes.
– Automatic control/data recognition.
– Able to process large-scale designs.
Advanced Processor Technologies Group School of
Computer Science
02/06/2014
13
Implementation and Test Environment
•
Verilog parser
•
Signal-level DFG
– Bison, Flex and Vpreprocessor (Verilog Perl tool)[1]
– C++ STL based abstract syntax tree
–
–
–
–
•
Boost Graphic Library (data structure)
Open Graph Drawing Framework (automatic layout)[2]
PugiXML (file format)
Qt (diagram drawer)
User interface
– Asynchronous Verilog Synthesiser[3]
– Command line UI: embedded Tcl with self-defined commands
[1] http://www.veripool.org/verilog-perl
[2] http://www.ogdf.net
[3] https://github.com/wsong83/Asynchronous-Verilog-Synthesiser
Advanced Processor Technologies Group School of
Computer Science
02/06/2014
14
© Copyright 2024 ExpyDoc
