You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tvm.apache.org by GitBox <gi...@apache.org> on 2021/01/08 20:12:52 UTC
[GitHub] [tvm] electriclilies commented on a change in pull request #7083: [RELAY,TOPI] Threefry PRNG: splittable and stateless
electriclilies commented on a change in pull request #7083:
URL: https://github.com/apache/tvm/pull/7083#discussion_r553580601
##########
File path: python/tvm/relay/op/random/kernel.py
##########
@@ -0,0 +1,134 @@
+# 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.
+"""Splittable and parallelizable PRNG kernels."""
+# pylint: disable=invalid-name,unused-argument
+from __future__ import absolute_import
+
+import sys
+import numpy as np
+
+from ...expr import Constant
+from .... import nd
+from . import _make
+
+
+def threefry_key(seed):
+ """Create a new Threefry random number generator key.
+
+ Example
+ -------
+
+ .. code-block:: python
+
+ gen = threefry_key(0)
+ _, random_number = threefry_generate(gen, (4,))
+
+ Parameters
+ ----------
+ seed : int
+ Starting seed for the key
+
+ Returns
+ -------
+ key : relay.Expr
+ New key to pass to future uses of :py:func:`threefry_split` or
+ :py:func:`threefry_generate`.
+ """
+ s = np.frombuffer(seed.to_bytes(32, sys.byteorder), dtype="uint64")
+ a = np.concatenate((s, np.array([0, 0, 0, 0, 1 << 63, 0], dtype="uint64")))
+ return Constant(nd.array(a))
+
+
+def threefry_generate(key, shape):
+ """Generate an array of random bits (`uint64`) using the Threefry algorithm
+
+ Example
+ -------
+
+ .. code-block:: python
+
+ key = threefry_key(0)
+ new_key, random1 = threefry_generate(key, (4,))
+ _, random2 = threefry_generate(new_key, (4,))
+ # random1 and random2 are different random numbers
+
+ Parameters
+ ----------
+ key : relay.Expr
+ key that uniquely determines the random values. Multiple uses with the
+ same key will generate the same random values. This key should be
+ treated as an opaque pointer. You can create one from calling
+ :py:func:`threefry_key`, :py:func:`threefry_split`, or
+ :py:func:`threefry_generate`. **Do not use this key again after calling
+ this function.**
+
+ shape : Sequence[int]
+ Desired outputs shape of random numbers. **Currently the total
+ number of elements must be a multiple of 4.**
+
+ Returns
+ -------
+ new_key : relay.Expr
+ New key to pass to future uses of :py:func:`threefry_split` or
+ :py:func:`threefry_generate`.
+
+ random_array : relay.Expr
+ Array of random numbers. Has shape `shape`.
+ """
+ return _make.threefry_generate(key, shape)
+
+
+def threefry_split(key):
+ """Split an existing Threefry key into two new ones.
+
+ This is useful if you have to subsequent calls which each need their own
Review comment:
Why wouldn't someone just create two separate three fry keys using different seeds, and use them?
##########
File path: python/tvm/relay/op/random/kernel.py
##########
@@ -0,0 +1,134 @@
+# 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.
+"""Splittable and parallelizable PRNG kernels."""
+# pylint: disable=invalid-name,unused-argument
+from __future__ import absolute_import
+
+import sys
+import numpy as np
+
+from ...expr import Constant
+from .... import nd
+from . import _make
+
+
+def threefry_key(seed):
+ """Create a new Threefry random number generator key.
+
+ Example
+ -------
+
+ .. code-block:: python
+
+ gen = threefry_key(0)
+ _, random_number = threefry_generate(gen, (4,))
+
+ Parameters
+ ----------
+ seed : int
+ Starting seed for the key
+
+ Returns
+ -------
+ key : relay.Expr
+ New key to pass to future uses of :py:func:`threefry_split` or
+ :py:func:`threefry_generate`.
+ """
+ s = np.frombuffer(seed.to_bytes(32, sys.byteorder), dtype="uint64")
+ a = np.concatenate((s, np.array([0, 0, 0, 0, 1 << 63, 0], dtype="uint64")))
+ return Constant(nd.array(a))
+
+
+def threefry_generate(key, shape):
+ """Generate an array of random bits (`uint64`) using the Threefry algorithm
+
+ Example
+ -------
+
+ .. code-block:: python
+
+ key = threefry_key(0)
+ new_key, random1 = threefry_generate(key, (4,))
+ _, random2 = threefry_generate(new_key, (4,))
+ # random1 and random2 are different random numbers
+
+ Parameters
+ ----------
+ key : relay.Expr
+ key that uniquely determines the random values. Multiple uses with the
+ same key will generate the same random values. This key should be
+ treated as an opaque pointer. You can create one from calling
+ :py:func:`threefry_key`, :py:func:`threefry_split`, or
+ :py:func:`threefry_generate`. **Do not use this key again after calling
+ this function.**
+
+ shape : Sequence[int]
Review comment:
Why does the total number of outputs need to be a multiple of four?
##########
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:
Can you elaborate on how path and key are used in number generation? You don't explain what the key is, either.
##########
File path: tests/python/relay/test_prng.py
##########
@@ -0,0 +1,108 @@
+# 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.
+import pytest
+import tvm
+import tvm.relay
+import tvm.testing
+from tvm.relay.testing import run_infer_type
+
+
+@tvm.testing.parametrize_targets
+def test_threefry_repeatability(target, ctx):
+ target, ctx = "llvm", tvm.cpu(0)
+ key1 = tvm.relay.random.threefry_key(1)
+ rand1 = tvm.relay.random.threefry_generate(key1, (12,))
+ out_key1, out1 = tvm.relay.create_executor(
+ "vm", tvm.IRModule.from_expr(tvm.relay.Function([], rand1)), target=target, ctx=ctx
+ ).evaluate()()
+
+ key2 = tvm.relay.random.threefry_key(1)
+ rand2 = tvm.relay.random.threefry_generate(key2, (12,))
Review comment:
It might be a good idea to add some tests with shapes other than (12, ), especially in the type test.
----------------------------------------------------------------
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:
users@infra.apache.org