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
  • 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. 
The better way to traverse through a circuit is to build a data structure for each gate encountered. Each gate should be assigned a number and there must be arrays in the data structure that holds information on the gates at its input and output. This makes traversing in both directions easier.

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";  
 }
Good Luck, Abishek

Comments

Post a Comment

Popular posts from this blog

Setting up atalanta ATPG to work on Linux

Atalanta is an ATPG tool that is used to generate test patterns for combinational circuits. atalanta is a windows executable file. I am using Atalanta ATPG tool to generate the test patterns required for generating the Transition fault Test patterns RUNNING ATALANTA (LINUX) You need to have WINE installed to run windows executable binary. Created a symbolic link in the usr/bin to the atalanta.exe, name of the link s atalanta. (not necessary if you do not have root privilages) chmod u+x /place/atalanta/atalanta.exe cd /usr/bin sudo ln -s /place/atalanta/atalanta.exe ./atalanta COMMAND TO RUN ATALANTA atalanta [option] filename //put this in a shell script
Read more

Sparse matrix - 3 tuple representation

//program to 3-tuple representation #include<stdio.h> #include<unistd.h> #define SIZE 3000; void main() { int a[5][5],row,columns,i,j; printf("Enter the order of the matrix(5*5)"); scanf("%d %d",&row,&columns); printf("Enter the element of the matrix\n"); for(i=0;i<row;i++) for(j=0;j<columns;j++) { scanf("%d", &a[i][j]); } printf("3-tuple representation"); for(i=0;i<row;i++) for(j=0;j<columns;j++) { if(a[i][j]!=0) { printf("%d %d %d", (i+1),(j+1),a[i][j]); } } getchar(); }
Read more

Generating 16k ROM using Xilinx IP COREGEN and simulating it in modelsim

The instruction ROM is an IP Core. so before interfacing with the open8, it has to be generated. The method of generating and simulating a ROM Xilinx IP Core is described here. FIND ALL THE FILES HERE 1. app.coe (the initialization file) 2. rom_16k_core.vhd 3. rom_16k_core.vho 4. rom_16k_core.xco 5. top_level.vhd 6. do_memgen.do Creation of the ROM Xilinx 10.1 1. open ISE 2. create a new project 3. tools -> core generator(12.1) (or right click on the device and add a new file 10.1) 4. In the IP catalog -> Memory and storage elements -> RAM and ROM 5. double click on block memory generator, A new window opens 6. In the new window select single port ROM click next, Write first mode 7. Select Read Width = 8 and Read Depth = 16384 for 16K ROM -> next 8. The output ports are unregistered, load initialization COE if required -> next 9. No need to use the Reset pin -> next 10. Generate. (takes a little time then shows successfully generated) This...
Read more