Levelization of circuits

Hello,

When working with benchmark circuits, it is convenient to levelize the gates and work with levels. This is useful when you want to calculate some metric for all gates or wires. It is efficient than recursively traversing through all wires, gates, and fanouts. 

Here I upload a program that levelizes the iscas bench marks.  It is written in perl. Use it the way you see fit and edit it if you find mistakes.

Levelization
1. Assign level number 0 to all primary inputs
2. For each PI fanout
  • Label that circuit line with level number of the PI 
  • Queue the logic gate driven by that fanout line (I need a queue)
3. While queue is not empty
  • dequeue the next logic gate in the queue 
  • If all of the gate fanins are labeled with level numbers, then label the logic gate and its fanouts with maximum of input levels + 1. Queue all fanouts of the logic gate. Otherwise requeue the logic gate. 

Algorithm - Levelization
loop
inputlist - list of primary inputs
for all gates
    if either of input of gates is present in the inputlist,
       add the gate to the queue

for the gates in the queue
    dequeue the gate
    if all the inputs of the gates have levels assigned (level is not -1) then
         level(gate)=max(level of inputs)+1, level(output wire) = max(level of inputs)+1
         push outputwire into input list
    if all inputs of gate do not have levels assigned
         push the gate to the end of the queue.
goto loop 

How to run: perl levelization.plx test_3.v 

Sample: test_3.v 
module test_3 (A1,B1,C1,D1,O1,O2,O3); 
input A1,B1,C1,D1; 
output O1,O2,O3; 
wire Z1,Z2,Z3,Z4; 
NAND2X1 NAND2_1 (.Y(Z1),.A(C1),.B(D1)); 
NAND2X1 NAND2_2 (.Y(Z2),.A(B1),.B(Z1)); 
NAND2X1 NAND2_3 (.Y(Z3),.A(A1),.B(Z2)); 
NAND2X1 NAND2_4 (.Y(Z4),.A(Z2),.B(Z1)); 
NAND2X1 NAND2_5 (.Y(O3),.A(C1),.B(D1)); 
NAND2X1 NAND2_6 (.Y(O1),.A(Z3),.B(Z4)); 
BUFX1 BUF1_1 (.Y(O2),.A(Z4)); 
endmodule 



Output 
gate: level 
NAND2_1: 1 
NAND2_2: 2 
NAND2_3: 3 
NAND2_4: 3 
NAND2_5: 1 
NAND2_6: 4 
BUF1_1: 4 



 #!/usr/bin/perl  
 #levelization.plx  
 use warnings;  
 use Data::Dumper;  
 use strict;  
 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 @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 =~ /input (.*);/)  
 {  
   @input_array = split /,/, $1;  
 }  
 if($INPUT_DATA =~ /output (.*);/)  
 {  
   @output_array = split /,/, $1;  
 }  
 if($INPUT_DATA =~ /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 =~ /(.*) (.*) \(\.Y\((.*)\),\.A\((.*)\),\.B\((.*)\)\);/)  
 {  
   push @gates,   
   {   
      num_inputs => 2,  
      gate_type => "$1",   
      gate_name => "$2",   
      output =>   
      {  
        wire_name => "$3",  
        sa0 => 1,  
        sa1 => 1,  
        level => 0,  
      },  
      input_1 =>   
      {  
        wire_name => "$2_$4",   
        sa0 => 1,  
        sa1 => 1,  
        level => 0,  
      },  
      input_2 =>   
      {  
        wire_name => "$2_$5",   
        sa0 => 1,  
        sa1 => 1,  
        level => 0,  
      },  
      processed => 0,   
      processed_ip1 => 0,  
      processed_ip2 => 0,  
      gate_level => -1,  
      shifted => 0  
   };  
 }  
 #INV, BUF  
 #DE - Doesnt Exist  
 #renaming the gates at inputs of the gates for fanouts  
 if($INPUT_DATA =~ /(INVX1|BUFX1) (.*) \(\.Y\((.*)\),\.A\((.*)\)\);$/)  
 {  
   $gate_name_temp = $2;  
   push @gates,   
   {   
      num_inputs => 1,  
      gate_type => "$1",   
      gate_name => "$2",   
      output =>   
      {  
        wire_name => "$3",  
        sa0 => 1,  
        sa1 => 1,  
        level => 0,  
      },  
      input_1 =>   
      {  
        wire_name => "$2_$4",   
        sa0 => 1,  
        sa1 => 1,  
        level => 0,  
      },  
      processed => 0,   
      processed_ip1 => 0,  
      gate_level => -1,  
      shifted => 0  
   };  
 }  
 }  
 }  
 #File Read complete  
 #wire struct holds fault data for all wires  
 #input_list_struct is used for levelization  
 for $element (@input_array){  
   print "input: $element\n";  
   push @wire_struct, { wire_name => "$element", sa0 => 1, sa1 =>1, level => 0};  
   push @input_list_struct, {wire_name => "$element", sa0 => 1, sa1 => 1, level => 0};  
 }  
 for $element (@wire_array){  
   push @wire_struct, { wire_name => "$element", sa0 => 1, sa1 =>1, level => -1};  
 }  
 for $element (@output_array){  
   push @wire_struct, { wire_name => "$element", sa0 => 1, sa1 =>1, level => -1};  
 }  
 print "Initial inputs\n";  
 for my $href ( @input_list_struct ) {  
   print "{ ";  
   for my $role ( keys %$href ) {  
   print "$role=$href->{$role} ";  
 }  
 print "}\n";  
 }  
 $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_ip1} = 1;  
           if($gate->{num_inputs}==1){  
             print "NOTE: $gate->{gate_name}:$gate->{processed}\n";  
             getc();  
             if($gate->{processed}!=$gate->{num_inputs}){  
                unshift(@gate_queue,$gate);  
             }  
           }  
           elsif($gate->{processed_ip2}==1){  
             $gate->{processed}=$gate->{num_inputs};  
           }  
           elsif($gate->{processed}!=$gate->{num_inputs}){  
             if($gate->{shifted}==0){  
                print "1. shifting $gate->{gate_name} to gate queue\n";  
                getc();  
                unshift(@gate_queue,$gate);       
             }  
           }  
        }  
        if(($gate->{num_inputs}!=1)){  
           if(($gate->{input_2})->{wire_name} =~ m/$inp_test$/){  
             $gate->{processed_ip2} = 1;    
             if($gate->{processed_ip1}==1){  
                $gate->{processed}=$gate->{num_inputs};  
             }  
             if($gate->{processed}!=$gate->{num_inputs}){  
                if($gate->{shifted}==0){  
                  print "2. shifting $gate->{gate_name} to gate queue\n";  
                  getc();  
                  unshift(@gate_queue,$gate);  
                }  
             }  
           }  
        }  
      }  
   }    
   print "Gates in gate queue\n";  
   for my $line (@gate_queue)   
   {  
      for my $role (keys %$line)  
      {  
        if($role =~ m/^input_1$/)  
        {  
           print "$role: $line->{$role}->{wire_name},";  
           print "lvl: $line->{$role}->{level},";  
        }  
        elsif($role =~ m/^input_2$/)  
        {  
           print "$role: $line->{$role}->{wire_name},";  
           print "lvl: $line->{$role}->{level},";  
        }  
        elsif($role =~ m/^output$/)  
        {  
           print "$role: $line->{$role}->{wire_name},";  
           print "lvl: $line->{$role}->{level},";  
        }  
        else  
        {  
           print "$role:$line->{$role},";  
        }  
      }  
      print "\n";  
   }  
   getc();  
 #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->{num_inputs}==1){  
        print "Number of gates in queue: $num_gate_queue";  
        if($gate->{processed_ip1}==1){  
           $gate->{processed}=$gate->{num_inputs};  
        }  
      }  
      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--;  
           print "Number of gates left $num_gates";  
           getc();    
        }  
        elsif($gate->{num_inputs}==1){  
           print "input level: $gate->{input_1}->{level}\n";  
           getc();  
           $gate->{gate_level} = $gate->{input_1}->{level};  
           $gate->{gate_level}++;  
           $gate->{output}->{level}=$gate->{gate_level};  
           print "$gate->{gate_name}: $gate->{gate_level}";  
           unshift(@input_list_struct,$gate->{output});  
           $num_gate_queue--;  
           $num_gates--;  
           print "Number of gates left $num_gates";  
           getc();    
        }  
      }  
      else{  
 #       if($gate->{shifted}==0){  
        print "3. shifting $gate->{gate_name} to gate queue\n";  
        getc();  
        unshift(@gate_queue,$gate);  
        $num_gate_queue--;  
 #gates that are not processed because of lack of second input being processed are shifted in here, they need not be shifted again  
        $gate->{shifted}=1;  
 #       }         
      }  
   }  
   print "updated input list\n";  
   for my $href ( @input_list_struct ) {  
      print "{ ";  
      for my $role ( keys %$href ) {  
        print "$role=$href->{$role} ";  
      }  
      print "}\n";  
   }  
 #the updated levels of the wires are present in input_list_struct  
 #update the fanouts of the gate with the levels from this struct  
   print "modifying gate: level input of gate\n";  
   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};  
           print "$gate->{gate_name}: $gate->{input_1}->{wire_name} - $gate->{input_1}->{level}\n";  
        }  
        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";  
 }


Comments

Post a Comment

Popular posts from this blog

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

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