tkonolige commented on a change in pull request #7083: URL: https://github.com/apache/tvm/pull/7083#discussion_r554185452
########## File path: python/tvm/topi/random/kernel.py ########## @@ -0,0 +1,408 @@ +# Licensed to the Apache Software Foundation (ASF) under one +# or more contributor license agreements. See the NOTICE file +# distributed with this work for additional information +# regarding copyright ownership. The ASF licenses this file +# to you under the Apache License, Version 2.0 (the +# "License"); you may not use this file except in compliance +# with the License. You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, +# software distributed under the License is distributed on an +# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +# KIND, either express or implied. See the License for the +# specific language governing permissions and limitations +# under the License. +"""Pseudorandom number kernels.""" +import tvm +import tvm.topi +from ... import tir +from ...tir import ir_builder + + +# Threefry PRNG with splitting based on +# - J. K. Salmon, M. A. Moraes, R. O. Dror and D. E. Shaw, "Parallel random numbers: As easy as 1, +# 2, 3," SC '11: Proceedings of 2011 International Conference for High Performance Computing, +# Networking, Storage and Analysis, Seattle, WA, 2011, pp. 1-12, doi: 10.1145/2063384.2063405. +# - Claessen, K. ; Palka, M. (2013) "Splittable Pseudorandom Number Generators using Cryptographic +# Hashing". Proceedings of Haskell Symposium 2013 pp. 47-58. MLA +# - Ferguson, Niels, et al. "The Skein hash function family." Submission to NIST (round 3) 7.7.5 +# (2010): 3. + + +# Threefry is a counter based PRNG: given a unique input, it generates a unique random number. As +# there is no state to maintain, we can apply it to a sequence of numbers (0..N) to generate a +# sequence of random numbers in parallel. In order to make the PRNG splittable (that is we can +# generate a sequence of random numbers in one place, and another sequence in another), we add a +# path and key in addition to the counter. The path allows us to encode a sequence of splits (a 0 in Review comment: The last sentence explains what the key is: "To avoid continuously growing the path, we can compress an existing path into the key portion of the generator by hashing the current key, path, and counter to create the new key (this same technique is used if we run out of room for the counter)." I've added a comment on how it is initialized. I've also added an explanation of how random numbers are generated (we apply the hash to key, path, and counter). ---------------------------------------------------------------- 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. For queries about this service, please contact Infrastructure at: [email protected]
