1

I am trying to use system verilog constraint solver to solve the following problem statement :

We have N balls each with unique weight and these balls need to be distributed into groups , such that weight of each group does not exceed a threshold ( MAX_WEIGHT) . Now i want to find all such possible solutions . The code I wrote in SV is as follows :

`define NUM_BALLS 5
`define MAX_WEIGHT_BUCKET 100

class weight_distributor;
int ball_weight [`NUM_BALLS];

	rand int unsigned solution_array[][];

	constraint c_solve_bucket_problem
	{		
		foreach(solution_array[i,j]) {
			solution_array[i][j] inside {ball_weight};
			//unique{solution_array[i][j]};
			foreach(solution_array[ii,jj])
				if(!((ii == i) & (j == jj))) solution_array[ii][jj] != solution_array[i][j];
		}
		foreach(solution_array[i,])
			solution_array[i].sum() < `MAX_WEIGHT_BUCKET;

	}

	function new();
		ball_weight = {10,20,30,40,50};
	endfunction

	function void post_randomize();		
		foreach(solution_array[i,j])
			$display("solution_array[%0d][%0d] = %0d", i,j,solution_array[i][j]);
		$display("solution_array size = %0d",solution_array.size);
	endfunction
   endclass

module top;
	weight_distributor weight_distributor_o;
	initial begin
		weight_distributor_o = new();
		void'(weight_distributor_o.randomize());	
	end
endmodule

The issue i am facing here is that i want the size of both the dimentions of the array to be randomly decided based on the constraint solution_array[i].sum() < `MAX_WEIGHT_BUCKET; . From my understanding of SV constraints i believe that the size of the array will be solved before value assignment to the array .

Moreover i also wanted to know if unique could be used for 2 dimentional dynamic array .

2 Answers 2

0

You can't use the random number generator (RNG) to enumerate all possible solutions of your problem. It's not built for this. An RNG can give you one of these solutions with each call to randomize(). It's not guaranteed, though, that it gives you a different solution with each call. Say you have 3 solutions, S0, S1, S2. The solver could give you S1, then S2, then S1 again, then S1, then S0, etc. If you know how many solutions there are, you can stop once you've seen them all. Generally, though, you don't know this beforehand.

What an RNG can do, however, is check whether a solution you provide is correct. If you loop over all possible solutions, you can filter out only the ones that are correct. In your case, you have N balls and up to N groups. You can start out by putting each ball into one group and trying if this is a correct solution. You can then put 2 balls into one group and all the other N - 2 into a groups of one. You can put two other balls into one group and all the others into groups of one. You can start putting 2 balls into one group, 2 other balls into one group and all the other N - 4 into groups of one. You can continue this until you put all N balls into the same group. I'm not really sure how you can easily enumerate all solutions. Combinatorics can help you here. At each step of the way you can check whether a certain ball arrangement satisfies the constraints:

// Array describing an arrangement of balls
// - the first dimension is the group
// - the second dimension is the index within the group
typedef unsigned int unsigned arrangement_t[][];

// Function that gives you the next arrangement to try out
function arrangement_t get_next_arrangement();
  // ...
endfunction

arrangement = get_next_arrangement();

if (weight_distributor_o.randomize() with {
  solution.size() == arrangement.size();
  foreach (solution[i]) {
    solution[i].size() == arrangement[i].size();
    foreach (solution[i][j])
      solution[i][j] == arrangement[i][j];
  }
})
  all_solutions.push_back(arrangement);

Now, let's look at weight_distributor. I'd recommend you write each requirement in an own constraint as this makes the code much more readable.

You can shorten you uniqueness constraint that you wrote as a double loop to using the unique operator:

class weight_distributor;

  // ...

  constraint unique_balls {
    unique { solution_array };
  }

endclass

You already had a constraint that each group can have at most MAX_WEIGHT in it:

class weight_distributor;

  // ...

  constraint max_weight_per_group {
    foreach (solution_array[i])
      solution_array[i].sum() < `MAX_WEIGHT_BUCKET;
  }

endclass

Because of the way array sizes are solved, it's not possible to write constraints that will ensure that you can compute a valid solution using simple calls randomize(). You don't need this, though, if you want to check whether a solution is valid. This is due to the constraints on array sizes in the between arrangement and solution_array.

Sign up to request clarification or add additional context in comments.

Comments

0

Try this.! class ABC; rand bit[3:0] md_array [][]; // Multidimansional Arrays with unknown size

constraint c_md_array { 
 // First assign the size of the first dimension of md_array
 md_array.size() == 2; 

 // Then for each sub-array in the first dimension do the following:
 foreach (md_array[i]) {

    // Randomize size of the sub-array to a value within the range
    md_array[i].size() inside {[1:5]};

    // Iterate over the second dimension 
    foreach (md_array[i][j]) {

       // Assign constraints for values to the second dimension
       md_array[i][j] inside {[1:10]};
     }
  }
 }

endclass

module tb;

initial begin
  ABC abc = new;
  abc.randomize();
  $display ("md_array = %p", abc.md_array);
end

endmodule

https://www.chipverify.com/systemverilog/systemverilog-foreach-constraint

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.