Skip to content

[Pack] Random Number Generator in Packer is Non-Deterministic #2858

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
AlexandreSinger opened this issue Jan 14, 2025 · 0 comments
Closed

[Pack] Random Number Generator in Packer is Non-Deterministic #2858

AlexandreSinger opened this issue Jan 14, 2025 · 0 comments
Assignees

Comments

@AlexandreSinger
Copy link
Contributor

Within the GreedyCandidateSelector used in the packer, there is code which adds cluster molecule candidates by attraction groups. In this code, when the number of available atoms in the attraction group is larger than some threshold (currently 500), it randomly selects candidates from this group:

for (int j = 0; j < attraction_group_num_atoms_threshold_; j++) {
// FIXME: This is a non-deterministic random number generator and it is
// overkill to what this needs to be. Should use vtr::irand which
// would be faster.
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distr(min, max);
int selected_atom = distr(gen);
AtomBlockId blk_id = available_atoms[selected_atom];
//Only consider molecules that are unpacked and of the correct type
t_pack_molecule* molecule = prepacker.get_atom_molecule(blk_id);
if (!cluster_legalizer.is_mol_clustered(molecule) &&
cluster_legalizer.is_molecule_compatible(molecule, legalization_cluster_id)) {
add_molecule_to_pb_stats_candidates(molecule,
cluster_gain_stats,
packer_opts_.feasible_block_array_size,
attraction_groups,
atom_netlist_);
}
}
}

The issue is that the random number generator used here is way overkill for this application and is non-deterministic. We should be using vtr::irand instead which would be faster.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants