junrushao1994 commented on a change in pull request #8817:
URL: https://github.com/apache/tvm/pull/8817#discussion_r694983321
##########
File path: src/tir/schedule/concrete_schedule.cc
##########
@@ -208,6 +211,25 @@ Schedule ConcreteScheduleNode::Copy() const {
}
/******** Schedule: Schedule: Sampling ********/
+
+void ConcreteScheduleNode::Seed(support::LinearCongruentialEngine::TRandState
seed) {
+ support::LinearCongruentialEngine(&rand_state_).Seed(seed == -1 ?
std::random_device()() : seed);
+}
+support::LinearCongruentialEngine::TRandState ConcreteScheduleNode::ForkSeed()
{
+ // In order for reproducibility, we computer the new seed using RNG's random
state and a different
+ // set of parameters. Note that both 32767 and 1999999973 are prime numbers.
+ return (support::LinearCongruentialEngine(&rand_state_)() * 32767) %
1999999973;
+}
Review comment:
@tqchen I happened to implement a BSGS discrete logarithm this morning.
This is a simple but effective algorithm (but not effective enough for crypto)
we use in high school competitive programming:
https://gist.github.com/junrushao1994/d32f265f5b4815d4b346d6022e95f394.
I use this script to find out what the minimal number of trials is required
for a first repeat to happen given `num_threads` threads, and here is the
outcome when I set `num_threads=1000`.
```
k = 0, forked_seed = 1, repeat = 0
k = 1, forked_seed = 32767, repeat = 477805293
k = 2, forked_seed = 1073676289, repeat = 955610586
k = 3, forked_seed = 1151436593, repeat = 792763173
k = 4, forked_seed = 1123352159, repeat = 1465074278
k = 5, forked_seed = 880690861, repeat = 1324276493
k = 6, forked_seed = 1597831943, repeat = 1242547212
k = 7, forked_seed = 159983087, repeat = 1577951775
k = 8, forked_seed = 165882496, repeat = 12097717
k = 9, forked_seed = 1471819791, repeat = 670441922
k = 10, forked_seed = 1119742748, repeat = 130415288
k = 11, forked_seed = 611119031, repeat = 268696235
k = 12, forked_seed = 537559101, repeat = 53491731
k = 13, forked_seed = 199300256, repeat = 1422308282
k = 14, forked_seed = 471576507, repeat = 535435921
k = 15, forked_seed = 147613471, repeat = 482454183
k = 16, forked_seed = 850669543, repeat = 1171123831
k = 17, forked_seed = 1889291753, repeat = 1518153595
k = 18, forked_seed = 423706282, repeat = 325709943
k = 19, forked_seed = 1583929701, repeat = 1523336904
k = 20, forked_seed = 625213317, repeat = 2097645560
...
k = 990, forked_seed = 465632523, repeat = 1395274874
k = 991, forked_seed = 1381087097, repeat = 1524683345
k = 992, forked_seed = 81518328, repeat = 874365972
k = 993, forked_seed = 1111089621, repeat = 464689348
k = 994, forked_seed = 1074102788, repeat = 1779776079
k = 995, forked_seed = 1126529515, repeat = 113162479
k = 996, forked_seed = 993116317, repeat = 711897275
k = 997, forked_seed = 1442798429, repeat = 285912163
k = 998, forked_seed = 176761269, repeat = 918045815
k = 999, forked_seed = 1936579488, repeat = 43150205
min repeat: 1407035
```
In a word, in practice the repeat won't happen after 1407035 trials given
the `forked_seed` within 1000 threads.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
