Path Trace
Hello,
I am posting an old program here that was written by me to trace different paths in a circuit. It is written in Perl and works for verilog (.v) files.
The program recursively iterates through every path in the circuit and it prints out the gates encountered en-route. It is useful if you are calculating a metric for each gate/wire
This is a way to NOT write a program. The program, as I found out later, is very slow because
Sample data structure
struct gate{
char name[];
int num_in;
int num_out;
int in[];
int out[];
.
.
}
You need to traverse the netlist once to fill in the data structures and you are good to go.
I cannot post the better program here because it was not written by me. So I post my old version of path trace here.
I am posting an old program here that was written by me to trace different paths in a circuit. It is written in Perl and works for verilog (.v) files.
The program recursively iterates through every path in the circuit and it prints out the gates encountered en-route. It is useful if you are calculating a metric for each gate/wire
This is a way to NOT write a program. The program, as I found out later, is very slow because
- It does not build the data structure for gates that makes traversing easier
- It works with gate names instead of numeric abstractions which are easier to deal with.
Sample data structure
struct gate{
char name[];
int num_in;
int num_out;
int in[];
int out[];
.
.
}
You need to traverse the netlist once to fill in the data structures and you are good to go.
I cannot post the better program here because it was not written by me. So I post my old version of path trace here.
#!/usr/bin/perl
#Path_Trace.plx
use warnings;
use Data::Dumper;
use strict;
use List::Util qw(min);
my $bench_file = $ARGV[0];
my $file_name;
my $circuit_name;
my $element;
my @input_array;
my @output_array;
my @wire_array;
my @gates;
my @sorted_gates;
my @wire_struct;
my @input_list_struct;
my @input_list_struct_2;
my @output_list_struct;
my @gate_queue;
#my @fanout_test;
my $num_inputs=0;
my $num_outputs=0;
my $num_wires=0;
my $num_gates=0;
my $gate_name_temp;
my $gate;
my $line;
my $role;
my $inp;
my $inp_test;
#Test netlist file
if($bench_file =~ /(.*).v/)
{
$file_name = $1;
}
else
{
print "Format of bench file name: circuit_name.v \n example : s1423.v\n";
}
#Read Netlist File
while(<>)
{
my $INPUT_DATA = $_;
chomp($INPUT_DATA);
{
#MODULE NAME
if($INPUT_DATA =~ /module (.*) (.*);/)
{
$circuit_name = $1;
print "circuit name = $circuit_name\n";
}
#INPUT OUTPUT WIRES
if($INPUT_DATA =~ m/^\s*input (.*);/)
{
@input_array = split /,/, $1;
}
if($INPUT_DATA =~ m/^\s*output (.*);/)
{
@output_array = split /,/, $1;
}
if($INPUT_DATA =~ m/^\s*wire (.*);/)
{
@wire_array = split /,/, $1;
}
my @wire1;
my @wire2;
my @wire3;
my $gate_name_temp;
my $gate;
my $line;
my $role;
#AND, OR, NAND, NOR, XOR
if($INPUT_DATA =~ m/^\s*(NAND2X1)\s*(.*)\s*\(\.Y\((.*)\),\.A\((.*)\),\.B\((.*)\)\);$/)
{
push @gates,
{
element => "gate",
num_inputs => 2,
gate_type => "$1",
gate_name => "$2",
output =>
{
element => "wire",
wire_name => "$3",
sa0 => 1,
sa1 => 1,
level => 0,
wire_delay =>0,
},
input_1 =>
{
element => "wire",
wire_name => "$2_$4",
sa0 => 1,
sa1 => 1,
level => 0,
wire_delay => 0,
},
input_2 =>
{
element => "wire",
wire_name => "$2_$5",
sa0 => 1,
sa1 => 1,
level => 0,
wire_delay => 0,
},
processed => 0,
gate_delay => 2,
gate_level => -1
};
}
#INV, BUF
#DE - Doesnt Exist
#renaming the gates at inputs of the gates for fanouts
if($INPUT_DATA =~ m/^\s*(INVX1|BUFX1) (.*) \(\.Y\((.*)\),\.A\((.*)\)\);$/)
{
$gate_name_temp = $2;
push @gates,
{
element => "gate",
num_inputs => 1,
gate_type => "$1",
gate_name => "$2",
output =>
{
element => "wire",
wire_name => "$3",
sa0 => 1,
sa1 => 1,
level => 0,
wire_delay => 0,
},
input_1 =>
{
element => "wire",
wire_name => "$2_$4",
sa0 => 1,
sa1 => 1,
level => 0,
wire_delay => 0,
},
processed => 0,
gate_delay => 1,
gate_level => -1
};
}
}
}
#File Read complete
#wire struct holds fault data for all wires
#input_list_struct is used for levelization
for $element (@input_array){
push @wire_struct, {element => "wire",wire_name => "$element", sa0 => 1, sa1 =>1, level => 0,wire_delay=>0};
push @input_list_struct, {element => "wire",wire_name => "$element", sa0 => 1, sa1 => 1, level => 0,wire_delay=>0};
push @input_list_struct_2, {element => "wire",wire_name => "$element", sa0 => 1, sa1 => 1, level => 0,wire_delay=>0};
}
for $element (@wire_array){
push @wire_struct, { element => "wire",wire_name => "$element", sa0 => 1, sa1 =>1, level => -1,wire_delay=>0};
}
for $element (@output_array){
push @wire_struct, { element => "wire",wire_name => "$element", sa0 => 1, sa1 =>1, level => -1,wire_delay=>0};
push @output_list_struct, {element => "wire",wire_name => "$element", sa0 => 1, sa1 => 1, level => 0,wire_delay=>0};
}
$num_gates = scalar @gates;
my $index=0;
#gate_processed = 2 then all inputs are processed
#shift gate into the queue if even one of the inputs processed
while($num_gates != 0)
{
for my $gate(@gates){
for my $inp (@input_list_struct){
my $inp_test = $inp->{wire_name};
if(($gate->{input_1})->{wire_name} =~ m/$inp_test$/){
$gate->{processed}++;
if($gate->{processed}==1){
unshift(@gate_queue,$gate);
}
if($gate->{processed}>1){
$gate->{processed}=$gate->{num_inputs};
}
}
if(($gate->{num_inputs}!=1)){
if(($gate->{input_2})->{wire_name} =~ m/$inp_test$/){
$gate->{processed}++;
if($gate->{processed}==1){
unshift(@gate_queue,$gate);
}
}
if($gate->{processed}>1){
$gate->{processed}=$gate->{num_inputs};
}
}
}
}
#if both inputs of the gates are processed, then calculate the level of the gate
#if only one of the inputs are processed, then add the gate to the end
my $num_gate_queue = scalar @gate_queue;
while ($num_gate_queue != 0)
{
$gate = pop(@gate_queue);
if($gate->{processed}==$gate->{num_inputs}){
if($gate->{num_inputs}==2){
if(($gate->{input_1}->{level})>($gate->{input_2}->{level})){
$gate->{gate_level} = ($gate->{input_1}->{level});
}
else{
$gate->{gate_level} = ($gate->{input_2}->{level});
}
$gate->{gate_level}++;
$gate->{output}->{level}=$gate->{gate_level};
unshift(@input_list_struct,$gate->{output});
$num_gate_queue--;
$num_gates--;
}
elsif($gate->{num_inputs}==1){
$gate->{gate_level} = $gate->{input_1}->{level};
$gate->{gate_level}++;
$gate->{output}->{level}=$gate->{gate_level};
unshift(@input_list_struct,$gate->{output});
$num_gate_queue--;
$num_gates--;
}
}
else{
unshift(@gate_queue,$gate);
$num_gate_queue--;
}
}
#the updated levels of the wires are present in input_list_struct
#update the fanouts of the gate with the levels from this struct
for $gate(@gates){
for $inp (@input_list_struct){
$inp_test = $inp->{wire_name};
if(($gate->{input_1})->{wire_name} =~ m/$inp_test$/){
$gate->{input_1}->{level} = $inp->{level};
}
if($gate->{num_inputs}!=1){
if(($gate->{input_2})->{wire_name} =~ m/$inp_test$/){
$gate->{input_2}->{level} = $inp->{level};
}
}
}
}
}
print "gate: level\n";
for $gate (@gates){
print "$gate->{gate_name}: $gate->{gate_level}\n";
}
print "\n\nPaths and Delays\n";
#Path Trace Variable Decl
my $wire;
my $inp_count = scalar @input_list_struct_2;
my $path_count;
my @fanout_array;
my $path_complete=0;
my @path_array;
my @tmp_current_path;
my $depth=-1;
my $tmp_num_fanouts=0;
my @num_fanouts;
my $num_paths=0;
my @saved_restore;
my @path_delay;
# End path trace variable decl
while($inp_count !=0){
my @current_path;
$wire = pop @input_list_struct_2;
$inp_count--;
$depth = 0;
$num_fanouts[$depth]=1;
push @current_path,$wire;
$tmp_num_fanouts=0;
for $gate (@gates){
if(($gate->{input_1})->{wire_name} =~ m/$wire->{wire_name}/){
$tmp_num_fanouts++;
push @fanout_array,$gate;
}
elsif($gate->{num_inputs}!=1){
if(($gate->{input_2})->{wire_name} =~ m/$wire->{wire_name}/){
$tmp_num_fanouts++;
push @fanout_array,$gate;
}
}
} #all fanouts are in the fanout array now pop the fanout array and continue the process
#more than 1 fanout need to save the values for future use
if($tmp_num_fanouts>1){
$depth++;
$num_fanouts[$depth] = $tmp_num_fanouts;
#save current path for the future
my $i=0;
for $element (@current_path){
$tmp_current_path[$depth][$i]=$element;
$i++;
}
$saved_restore[$depth]=$i;
}
while((scalar @fanout_array)!=0){
$path_complete=0;
#pop the next gate in the stack
$gate = pop @fanout_array;
#when the number of fanouts in the depth is over, reduce the depth
#push the new gate in the current path
push @current_path,$gate;
#trace the wire
$wire = $gate->{output};
my $flag=0;
for my $element2 (@output_list_struct){
if($wire->{wire_name} =~ m/$element2->{wire_name}/){
$flag = 1;
}
}
if($flag == 0){
push @current_path,$wire;
}
while(!$path_complete){
#reached output? path completed
for $element (@output_list_struct){
if($wire->{wire_name} =~ m/$element->{wire_name}/){
$path_complete=1;
$num_paths++;
push @current_path,$wire;
my $j=0;
my $i=$num_paths-1;
for $element (@current_path){
$path_array[$i][$j]=$element;
$j++;
}
#check iteratively if all the previous depth paths are exhausted
if($num_fanouts[$depth]>1){
$num_fanouts[$depth]--;
#resotring current path for a new path
my $i=0;
splice(@current_path,0);
while($i<$saved_restore[$depth]){
for $element ($tmp_current_path[$depth][$i]){
$current_path[$i]=$element;
$i++;
}
}
}
elsif($depth!=0){
$depth--;
#if the number of fanouts at this depth is greater than 1 then restore else continue with the next cycle
while($depth!=0){
if($num_fanouts[$depth]>1){
#remove if wrong
$num_fanouts[$depth]--;
my $i=0;
splice(@current_path,0);
while($i<$saved_restore[$depth]){
for $element ($tmp_current_path[$depth][$i]){
$current_path[$i]=$element;
$i++;
}
}
last;
}
else{
$depth--;
}
}
}
last;
}
}
#if path is not completed find fanouts
$tmp_num_fanouts=0;
if(!$path_complete){
for $gate (@gates){
if(($gate->{input_1})->{wire_name} =~ m/$wire->{wire_name}/){
push @fanout_array,$gate;
$tmp_num_fanouts++;
}
elsif($gate->{num_inputs}!=1){
if(($gate->{input_2})->{wire_name} =~ m/$wire->{wire_name}/){
push @fanout_array,$gate;
$tmp_num_fanouts++;
}
}
}#all fanouts are in the fanout array now pop the fanout array and continue the process
if($tmp_num_fanouts > 1){
$depth++;
my $i=0;
for $element (@current_path){
$tmp_current_path[$depth][$i]=$element;
$i++;
}
$saved_restore[$depth]=$i;
$num_fanouts[$depth] = $tmp_num_fanouts;
}
$gate = pop(@fanout_array);
$wire = $gate->{output};
# push @current_path,$wire;
push @current_path,$gate;
}
}
}
}
for(my $i=0;$i<$num_paths;$i++){
$path_delay[$i] = 0;
for(my $j=0;$j<$#{$path_array[$i]}+1;$j++){
if($path_array[$i][$j]->{element} =~ m/gate/){
print $path_array[$i][$j]->{gate_name}."->";
$path_delay[$i] = $path_delay[$i]+$path_array[$i][$j]->{gate_delay};
}
elsif($path_array[$i][$j]->{element} =~ m/wire/){
print $path_array[$i][$j]->{wire_name}."->";
$path_delay[$i] = $path_delay[$i]+$path_array[$i][$j]->{wire_delay};
}
}
print "\t\t delay: ".$path_delay[$i]."\n";
}
Comments
Post a Comment