标签: deterministic

浮点计算既不是关联的,也不是处理器上的分配.所以,

(a + b) + c 不等于 a + (b + c)

和a * (b + c)不等于a * b + a * c

有没有办法执行不会给出不同结果的确定性浮点计算.它对于单处理器来说是确定性的,但是如果线程增加一个总和,它在多线程程序中就不是确定性的,因为线程可能有不同的交错.

所以我的问题是,如何在多线程程序中实现浮点计算的确定性结果？

我目前正在使用带有64 KB SRAM的ARM Cortex M3处理器构建嵌入式系统.目前,我正在寻找一种方法来确保使用STL容器确定性能,其中包括确保在运行时不会最终耗尽内存.

我主要关注STL容器如何执行动态内存分配.虽然我可以利用自定义分配器让这些结构从我预留的池中获取内存,但我需要为每个结构设置一个单独的池,以确保结构的一个实例不能占用另一个实例的空间.

我正在与这个项目中的其他人一起工作,他们不想关注内存的原始分配,并且更愿意能够利用"众所周知的"数据结构(堆栈,队列,双端队列等).因此,我正在考虑围绕C阵列构建包装器以提供这些结构.这将支持静态分配支持这些容器所需的内存,并允许其他开发人员根据编译器提供的代码大小信息知道他们在运行时之前实例化的容器的大小.在我看来,这可以保证在运行时不会发生内存中断问题,并大大简化了系统设计.

另一种选择是在系统初始化时分配STL容器.在初始化期之后,不会发生额外的动态内存分配.但是,据我所知,标准C++ STL数据结构不支持这一点 - 它要求堆栈之类的容器能够预先分配(类似于向量).

对于我关于围绕标准C阵列构建类的提议有什么意见,我将不胜感激？另外,是否有更简单的方法在编译时分配静态大小的STL容器,例如静态大小的堆栈或队列？(我知道这可能是矢量,但其他我不确定)

注意:我已经阅读了另一个问题(嵌入式C++是否使用STL),但是这个问题的作者并未明确他们有多少内存(除了他们如何使用ARM7进程)或似乎是考虑类似于我的解决方案.

第二个注意:我知道对于一些开发人员来说,64 KB的SRAM可能看起来像很多内存.事实上,我已经在AVR处理器上进行了大量减少内存的开发,所以我理解这个观点.但是,从我目前的(可能是未知的)视图来看,在谈论STL容器时,64 KB的内存并不多.

它们(幂等函数和确定性函数)只是在给定相同输入的情况下返回相同结果的函数吗？

或者是否有我失踪的区别？(如果有区别,请你帮我理解它是什么)

动机

我刚刚重写了大约30个琐碎的解析器,我需要新版本的行为与旧版本完全一样.因此,我存储了他们的示例输入文件和旧解析器生成的输出的一些签名,以便与新的解析器进行比较.此签名包含成功解析的项目的计数,一些哈希码的总和以及最多10个伪随机选择的项目.

我认为这是一个好主意,因为哈希码的相等性总和保证了输出完全相同,并且样本允许我看到什么是错误的.我只使用样品,否则会变得非常大.

问题

基本上,给定一个无序的字符串集合,我想得到一个最多10个字符串的列表,这样当集合稍微改变时,我仍然在相同的位置得到大部分相同的样本(输入是无序的,但是输出是一个列表).当缺少某些东西时,这也应该有用,所以像第100个最小元素这样的想法是行不通的.

ImmutableList<String> selectSome(Collection<String> list) {
        if (list.isEmpty()) return ImmutableList.of();
        return IntStream.range(1, 20)
            .mapToObj(seed -> selectOne(list, seed))
            .distinct()
            .limit(10)
            .collect(ImmutableList.toImmutableList());
    }

所以我从1到20的数字开始(所以在distinct我仍然很可能有我的10个样本之后),调用一个无状态确定性函数selectOne(在下面定义),根据一些有趣的标准返回一个最大的字符串,删除重复项,限制结果并使用番石榴收集它.所有步骤应该是恕我直言确定性和"有序",但我可能忽略了一些东西.另一种可能性是我的所有30个新解析器都是错误的,但考虑到散列是正确的,这是不可能的.而且,解析的结果看起来正确.

String selectOne(Collection<String> list, int seed) {
    // some boring mixing, definitely deterministic
    for (int i=0; i<10; ++i) {
        seed *= 123456789;
        seed = Integer.rotateLeft(seed, 16);
    }
    // ensure seed is odd
    seed = 2*seed + 1;

    // first element is the candidate result
    String result = list.iterator().next();
    // the value is …

我一直在阅读有关Quicksort的文章,并发现有时候它被称为"确定性的Quicksort".

这是普通Quicksort的替代版本吗？普通Quicksort和确定性Quicksort有什么区别？

我如何保证.NET应用程序中的浮点计算(比如在C#中)始终产生相同的位精确结果？特别是在使用不同版本的.NET并在不同平台上运行时(x86 vs x86_64).浮点运算的不准确无关紧要.

在Java中我会使用strictfp.在C/C++和其他低级语言中,这个问题基本上是通过访问FPU/SSE控制寄存器来解决的,但这在.NET中可能是不可能的.

即使控制了FPU控制寄存器,.NET的JIT也会在不同平台上生成不同的代码.在这种情况下,像HotSpot这样的东西会更糟糕......

我为什么需要它？我正在考虑编写一个实时策略(RTS)游戏,它在很大程度上依赖于快速浮点数学和锁定步进模拟.基本上我只会通过网络传输用户输入.这也适用于通过存储用户输入来实现重放的其他游戏.

不是一个选择:

• 小数(太慢)
• 固定点值(使用sqrt,sin,cos,tan,atan时太慢和麻烦......)
• 像FPS一样在网络上更新状态:不能选择发送数百或几千个单位的位置信息

有任何想法吗？

我所谓的确定性程序会在不同的运行中产生一些略有不同的输出.输入,编译器和计算机是不变的.我不确定哪个输出是正确的,因为它看起来总是合理的.

除了对rand()的迷路调用之外,怎么可能呢？

为什么查询版本2要快得多？

我怀疑数据库引擎多次调用表值函数"GetUsageStatistic",所以有没有办法告诉引擎"GetUsageStatistic"是确定性的,应该只调用一次？

查询版本1

--Takes ~10 minutes
select *
from RosterLevel r
left join GetUsageStatistics( @mindate, @maxdate ) usage on r.UserID = usage.UserID;

查询版本2

--Takes ~10 seconds
select * into #usage from  GetUsageStatistics( @mindate, @maxdate );
select *
from RosterLevel r
left join #usage on r.UserID = #usage.UserID;

在SQL SELECT语句中,我想执行一个对该SELECT语句范围具有确定性的函数(或者事务也可以):

select t.x, t.y, my_function(t.x) from t

许多值t.x都是相同的,因此Oracle可以省略一次又一次地调用相同的函数,以加快速度.但是如果我将函数标记为DETERMINISTIC,则可以在此查询的多次执行之间缓存结果.我无法使用的原因DETERMINISTIC是因为my_function使用了不时更改的配置参数.

我可以使用其他任何关键字吗？是否有任何我应该注意的问题(内存问题,并发性等)？或者也许任何其他技巧,例如分析函数,每个t.x值只调用一次函数(没有重大的性能影响)？

我的网络包括“torch.nn.MaxPool3d”，根据 PyTorch 文档（版本 1.7 - https://pytorch.org/docs/stable/ generated/torch.set_definistic.html#torch），当 cudnn 确定性标志打开时，它会抛出运行时错误.set_确定性），但是，当我在代码开头插入代码“torch.backends.cudnn.确定性 = True”时，没有运行时错误。为什么该代码不抛出运行时错误？我想知道该代码是否能保证我的训练过程的确定性计算。