对量化算法瓶颈的响应内存与计算。

计算科学 算法
2021-12-04 01:04:03

对这个问题的第一反应很棒。

通过翻牌计数进行算法分析过时了吗？

现在，唯一的问题是我并不真正理解它。这是我为什么不清楚的例子。请让我知道我做错了什么。

将上述分析应用于 FFT：

假设我想计算一个长度为 n 的向量的 fft。然后我需要做大约 nlog(n) 次失败。假设是 64 位系统，进行计算所需的字节数为 8n。所以 = log(n)/8。β

假设我的处理器工作在 2GHz=Fmax 并且我有 8Gbytes=Bmax 的 RAM。然后，我在以下情况下平等：

log(n)/8 (flops/byte) = (Bmax/Fmax) (bytes/Hz) = 4 这意味着

log(n) = 32 => n = 2^32 = 4,294,967,296

那么，我应该能够计算大小为 n 的向量的 fft 吗？我不知道。另外，为什么不取消单位？

2个回答

你误解了马特想对说什么。它不是操作总数除以算法所需的内存量（或相反）的比率，而是操作总数除以内存访问总数的比率。在您的情况下，您可能需要个内存位置，但您肯定需要不止一次地读取每个位置。事实上，在大多数应用程序中，内存访问的次数与浮点运算的次数成正比，那么这个比率就是。然而，对于不同的算法，这个因素是不同的。β8nβ

马特在那边的回答不是关于您是否可以计算特定大小的问题。这是关于您的算法是否可能在特定架构上受到内存访问限制或计算限制。所以，让脱离这个界限是没有意义的。和一起是输入。nnBmaxFmax

其它你可能感兴趣的问题
上一篇均衡各种多边形随机镶嵌面积的算法 下一篇从经验累积分布函数中提取时间尺度信息