时间戳

首页 > 解决方案 > system verilog 二维动态数组随机化

system-verilog - system verilog 二维动态数组随机化

问题描述

我正在尝试使用系统 verilog 约束求解器来解决以下问题陈述：

我们有 N 个球，每个球的重量都是唯一的，这些球需要分成几组，使每组的重量不超过阈值 (MAX_WEIGHT)。现在我想找到所有这些可能的解决方案。我在 SV 中编写的代码如下：

`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

我在这里面临的问题是，我希望根据约束 solution_array[i].sum() < `MAX_WEIGHT_BUCKET; 随机决定数组两个维度的大小。. 根据我对 SV 约束的理解，我相信数组的大小将在对数组赋值之前解决。

此外，我还想知道 unique 是否可以用于二维动态数组。

标签： system-verilog

解决方案

您不能使用随机数生成器 (RNG) 来枚举问题的所有可能解决方案。它不是为此而构建的。RNG 可以在每次调用时为您提供这些解决方案之一randomize()。但是，不能保证每次通话都会为您提供不同的解决方案。假设您有 3 个解决方案，S0, S1, S2. 求解器可以给你S1, then S2, then S1, then S1, thenS0等。如果你知道有多少个解，你可以在看到所有解之后停下来。但是，通常，您事先并不知道这一点。

然而，RNG 可以做的是检查您提供的解决方案是否正确。如果您遍历所有可能的解决方案，您可以只过滤掉正确的解决方案。在您的情况下，您有 N 个球和最多 N 个组。您可以先将每个球分成一组，然后尝试这是否是正确的解决方案。然后，您可以将 2 个球放入一组中，将所有其他 N - 2 个放入一组中。您可以将另外两个球放入一组中，将所有其他球放入一组中。您可以开始将 2 个球放入一组，将其他 2 个球放入一组，然后将所有其他 N - 4 个放入一组。您可以继续此操作，直到将所有 N 个球放入同一组。我不太确定如何轻松枚举所有解决方案。组合学可以在这里为您提供帮助。

// 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);

现在，让我们来看看weight_distributor。我建议您在自己的约束中编写每个要求，因为这会使代码更具可读性。

您可以缩短作为双循环编写的唯一性约束以使用unique运算符：

class weight_distributor;

  // ...

  constraint unique_balls {
    unique { solution_array };
  }

endclass

您已经有一个约束，每个组最多可以有一个约束MAX_WEIGHT：

class weight_distributor;

  // ...

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

endclass

由于解决数组大小的方式，不可能编写约束来确保您可以使用简单的调用计算有效的解决方案randomize()。但是，如果您想检查解决方案是否有效，则不需要这个。这是由于 betweenarrangement和对数组大小的限制solution_array。

推荐阅读