Constraints for a queue/array: Need help to understand how to implement this #3 condition

vickydhudashia · January 30, 2022, 7:47pm

create a list of instructions (size=20) from ADD, MUL, SUB and NOP instructions.

Such that No add instruction is repeated in 3 clock cycles and
MUL is not repeated in 4 clock cycles and
SUB is not repeated in the last 3 valid instructions.
(I don’t understand how to implement this #3)

Valid instruction = any other instruction except “nop” . “nop” is considered empty cycle do nothing instruction.

instruction cycle #

ADD 1
MUL 2
SUB 3
ADD 4
NOP 4
NOP 4
ADD 5
MUL 6
SUB 7



// assuming "1" = add instruction. Later can define as enum
// assuming "2" = mul inst.
// assuming "3" = sub inst.
// assuming "4" = nop inst.

class A;
  rand int q[$];
  
  
  constraint q_c {
        q.size == 21;
        foreach (q[i]) {
				q[i] inside {[1:4]};
				//q[i] == 1 -> q[i+1] != 1 -> q[i+2] != 1;
	            if (q[i] == 1) {
	              q[i+1] != 1;
	              q[i+2] != 1;
	            }
				//q[i] == 2 -> q[i+1] != 2 -> q[i+2] != 2 -> q[i+3] != 2;
                  
                  if (q[i] == 2) {
                    q[i+1] != 2;
                    q[i+2] != 2;
                    q[i+3] != 2;
	            }
			}
  }
  
endclass

module top;
	
   A a_h;
	initial begin
      repeat (5) begin
          a_h = new();
          a_h.randomize();
          $display("***************************** q =  %0p ****************************************", a_h.q);
		end
  	end 
endmodule

EDIT: Gives correct output for scenario 1 and scenario 2.
But need help with #3 implementation


***************************** q =  '{3, 2, 3, 3, 4, 4, 4, 3, 1, 4, 3, 4, 3, 2, 4, 4, 1, 2, 3, 4, 4}  ****************************************
***************************** q =  '{1, 4, 4, 2, 4, 1, 3, 2, 1, 4, 4, 2, 4, 3, 1, 4, 4, 2, 3, 1, 3}  ****************************************
***************************** q =  '{2, 3, 4, 4, 4, 4, 3, 3, 4, 4, 3, 4, 2, 1, 4, 4, 1, 2, 4, 1, 3}  ****************************************
***************************** q =  '{3, 3, 3, 3, 2, 4, 1, 3, 3, 2, 3, 1, 4, 2, 4, 3, 4, 4, 3, 3, 1}  ****************************************
***************************** q =  '{4, 1, 4, 4, 3, 3, 1, 3, 3, 3, 4, 1, 2, 4, 3, 4, 3, 1, 2, 4, 3}  ****************************************

ABD_91 · January 31, 2022, 4:49am

In reply to vickydhudashia:

The issue is the Max index of the queue is 20 .
So q[21] , q[22] , q[23] don’t exist

The Error arises since your constraint tries to access such invalid indexes .


Constraint  Guard  is helpful such  cases  (  Refer  LRM  for  more  info  )


 constraint q_c {
            q.size == 21;

          foreach (q[i])
          {
 	     q[i] inside {[1:4]};
           //q[i] == 1 -> q[i+1] != 1 -> q[i+2] != 1;
            if (q[i] == 1) 
           {  
              if( i <  19 )    //  Constraint  Guard
              {
                q[i+1] != 1;
                q[i+2] != 1;
              }  
           }
		
          //q[i] == 2 -> q[i+1] != 2 -> q[i+2] != 2 -> q[i+3] != 2;
 
              if (q[i] == 2) 
             {  if( i < 18 )   //  Constraint  Guard
               {
                  q[i+1] != 2;
                  q[i+2] != 2;
                  q[i+3] != 2;
                }
             }  
         }
  }

vickydhudashia · January 31, 2022, 7:25pm

In reply to ABD_91:

Hi ABD_91, Thanks, Yes I thought about it, But still real problem is with #3 implementation. I still can’t figure out a way to implement that constraint or any other way like in post-randomization/ late-randomization.
Let me edit Title & Post to avoid confusion.

dave_59 · January 31, 2022, 8:19pm

In reply to vickydhudashia:

It would help if you actually did use an enumerated type to begin with. It would make your code much easier to read. Another piece of advice: do not use queues unless you plan to push/pop elements, they are not as efficient as dynamic arrays.

It’s hard to know from your question how programmable the constraints needs to be. There is always the brute force hardcoded constraint.

module top;
typedef enum { ADD=1,MUL,SUB,NOP} instruction_e;
class A;
  rand instruction_e list[] = new[20];
  constraint q_c {

    foreach (list[i]) {
      if (i< 17 && list[i] == ADD) {
        list[i+1] != ADD;
        list[i+2] != ADD;
      }
      if (i< 16 && list[i] == MUL) {
        list[i+1] != MUL;
        list[i+2] != MUL;
        list[i+3] != MUL;
      }
    }
    (list[17]!=SUB || list[18]!=SUB) &&
    (list[18]!=SUB || list[19]!=SUB) &&
    (list[17]!=SUB || list[19]!=SUB);
  }
 
endclass
 
   A a_h;
	initial begin
      repeat (5) begin
          a_h = new();
        assert(a_h.randomize());
        $display("***************************** list =  %0p ****************************************", a_h.list);
		end
  	end 
endmodule

vickydhudashia · January 31, 2022, 11:12pm

In reply to dave_59:

Hi Dave, Thanks for reply, I will keep in mind for next timess…
I think I was not clear on my 3rd requirenment.
Anywhere in my instruction list, I can have SUB operation only if there wasn’t SUB instruction in previous 3 valid instructions.
If there is NOP instruction, consider it as you did’t have any operation/ that place in list is empty

So question is how do i create constraint/ do any post randomization check/edit for sub operations ? NOP can come any number of times. But I need to keep track of last 3 valid instructions and if SUB was not one of them, then only I can have SUB operation.


***************************** list =  '{MUL, ADD, NOP, SUB,  SUB, ADD, MUL, SUB, SUB, SUB, SUB, ADD, SUB, SUB, MUL, SUB, NOP, ADD, ADD, NOP}  ****************************************
                                         V    V        V,1st V,2nd   
                                                             X - Should not come here since before this SUB instruction, last 3 valid instructions were MUL, ADD, SUB
                                                             
Ex (invalid case):                                                              
ADD, MUL, SUB, NOP, NOP, NOP, NOP, NOP, NOP, SUB, NOP . . . . 
 V    V   V,1st                              V,2nd  
                                              X - Should not come here since last 3 valid instructions were ADD, MUL, SUB
                                              
Ex (valid case):                                                              
ADD, MUL, SUB, NOP, ADD, NOP, MUL, NOP, ADD, SUB, NOP . . . . 
 V    V   V,1st      V         V         V   V,2nd  
                                              Correct - since last 3 valid instructions were ADD, MUL, ADD

dave_59 · February 1, 2022, 5:39am

In reply to vickydhudashia:

OK, those examples really help. Try this

module top;
typedef enum { ADD=1,MUL,SUB,NOP} instruction_e;
class A;
  rand instruction_e list[] = new[20];
  constraint q_c {
    foreach (list[i]) {
     if (i< 17 && list[i] == ADD) {
        list[i+1] != ADD;
        list[i+2] != ADD;
      }
      if (i< 16 && list[i] == MUL) {
        list[i+1] != MUL;
        list[i+2] != MUL;
        list[i+3] != MUL;
      }
      foreach (list[j])
        if(i<j && list[i]==SUB && list[j]==SUB)
          list.sum() with (int'(item.index inside {[i+1:j-1]} && item != NOP)) >= 3;
    }
  }
endclass
   A a_h;
	initial begin
      repeat (10) begin
          a_h = new();
        assert(a_h.randomize() );
        $display("***************************** list =  %0p ****************************************", a_h.list);
		end
  	end 
endmodule

vickydhudashia · February 1, 2022, 8:36am

In reply to dave_59:

Thank you Dave! Knowing this way of using array method makes me feel a little wiser !!
I did slight modification to first 2 conditions and here is the complete code that generates expected output.


module top;
typedef enum { ADD=1,MUL,SUB,NOP} instruction_e;
class A;
  rand instruction_e list[] = new[20];
  constraint q_c {
    foreach (list[i]) {
      if (i< 18 && list[i] == ADD) {
         list[i+1] != ADD;
         list[i+2] != ADD;
      }
      else 
      if (i< 19 && list[i] == ADD) {
         list[i+1] != ADD;
      }
      
      if (i< 17 && list[i] == MUL) {
        list[i+1] != MUL;
        list[i+2] != MUL;
        list[i+3] != MUL;
      } else 
      if (i< 18 && list[i] == MUL) {
        list[i+1] != MUL;
        list[i+2] != MUL;
      } else 
      if (i< 19 && list[i] == MUL) {
        list[i+1] != MUL;
      }
          
      foreach (list[j])
        if(i<j && list[i]==SUB && list[j]==SUB)
          list.sum() with (int'(item.index inside {[i+1:j-1]} && item != NOP)) >= 3;
    }
  }
endclass
   A a_h;
	initial begin
      repeat (10) begin
          a_h = new();
        assert(a_h.randomize() );
        $display("***************************** list =  %0p ****************************************", a_h.list);
		end
  	end 
endmodule

dave_59 · February 1, 2022, 7:12pm

In reply to vickydhudashia:

BTW, since we are now using a nested foreach loop, it’s easer to write the other constraints that way as well. No need for out of bounds checking.

class A;
  rand instruction_e list[] = new[20];
  constraint q_c {
    foreach (list[i]) {
      foreach (list[j])
        if(i<j) {
          if (list[i]==ADD && list[j]==ADD) j-i >= 3;
          if (list[i]==MUL && list[j]==MUL) j-i >= 4;
          if (list[i]==SUB && list[j]==SUB)
            list.sum() with (int'(item.index inside {[i+1:j-1]} && item != NOP)) >= 3;
        }
    }
  }
endclass

vickydhudashia · February 3, 2022, 2:31am

In reply to dave_59:

Thanks Dave. That’s even better and cleaner !!

Atresh · February 23, 2022, 4:46pm

In reply to vickydhudashia:

Why do we need else in the below? the if its self will ensure element element+1 and element+2 up to element 17,18,19 arent ADD. correct?
if (i< 18 && list[i] == ADD) {
list[i+1] != ADD;
list[i+2] != ADD;
}
else
if (i< 19 && list[i] == ADD) {
list[i+1] != ADD;
}

imajeeth · July 22, 2023, 6:18pm

Might not be as optimized a solution like Dave provided. But this works for me.

class instr;
  typedef enum {
    ADD,
    MUL,
    SUB,
    NOP
  } instr_t;
  
  rand instr_t ins;
  instr_t      last3_valid_instr_q[$];
  instr_t      last4_instr_q[$];
  instr_t      last3_instr_q[$];
  
  
  //No add instruction is repeated in 3 clock cycles
  constraint c1 {
    ADD inside {last3_instr_q} -> ins != ADD;
  }
  //MUL is not repeated in 4 clock cycles
  constraint c2 {
    MUL inside {last4_instr_q} -> ins != MUL;
  }
  //SUB is not repeated in the last 3 valid instructions.
  constraint c3 {
    SUB inside {last3_valid_instr_q} -> ins != SUB;
  }
  function void post_randomize();
    //Populating last3_valid_instr_q
    if(ins != NOP) begin
    	if(last3_valid_instr_q.size == 3) 
      		last3_valid_instr_q.pop_front;
      	last3_valid_instr_q.push_back(ins);
    end 
    //populating last4_instr_q
    if(last4_instr_q.size == 4)
      last4_instr_q.pop_front;
    last4_instr_q.push_back(ins);
    
    //populating last3_instr_q
    if(last3_instr_q.size == 3)
      last3_instr_q.pop_front;
    last3_instr_q.push_back(ins);
    
  endfunction
  
  
endclass

module top;
  initial begin 
    instr in;
    in = new;
    repeat(100) begin 
      in.randomize();
      $display("%p",in.ins);
    end
  end 
endmodule

GeetikaAilawadi · August 11, 2023, 9:47am

In reply to imajeeth:
Could you please let me know why you added “if else” only in case of last3_valid_instr_q in post_randomize

imajeeth · August 11, 2023, 12:51pm

In reply to Grace90:

Thank you for the catch. I updated the code. I think that else is not needed there.

cecil · February 11, 2024, 10:22pm

Hi Dave,
To satisfy the 3rd condition, shouldn’t the last ‘if’ statement be something like this?

list.sum() with (int'(item.index inside {[i+1:j-1]} && item != NOP && item != SUB)) >= 3;

dave_59 · February 12, 2024, 1:31am

That check is unnecessary because the constraint only needs to check the minimum distance between i and k.

cecil · February 28, 2024, 2:16pm

Thanks for the clarification.