CPU->GPU->ASIC->Memory

[quickhorse]

挖矿从CPU到GPU到ASIC的过程，大家都了解了。如何设计一种只能CPU挖矿的算法呢？其实很简单，估计看完本文，你也就会了。
本文是我看了Scrypt算法以后的一些感受。

整篇文章我也没全看，主要是其中的各个证明，全是数学的东西，我就跳过了。但对于其中提到的三种算法，我是理解了。
这三种算法，其实就是三句话，1：要防止破解，需要用大量的内存。2：要防止破解，要不可并行。3：要防止破解，要在内存中分散存储。

如果真正使用了大量的内存，是不可能出现矿机的。LTC矿机之所以出现，是因为LTC也只使用了128K的内存，是比sha256的288字节大的多了，但还是不够大。
我们来看一下，LTC的Scrypt算法在CPU和GPU中的情况。
对PC而言，一般4核CPU，所有的数据只能动员512K的内存，但因为只有4个核，就只可以启动四个进程。
对显卡而言，N卡有1000+个计算单元，A卡有3000+个计算单元，动员100多M和400多M内存，启动1000+或3000+个进程。当然每个进程的速度可能比不上CPU但总计效率提升几百到几千倍。

对于ASIC而言，（还是说BTC的矿机吧）一个内核中有几千个门电路，可以在一个时钟周期内，完成CPU、GPU需要几千时钟周期内完成的工作。差不多一个矿机内核，顶的上一块显卡。（烤猫USB 333M，就是这样一个核）
而avalon两模块就是8*10*2=160个芯片，320个内核。速度直接就上去了。


设想一下，如果有一个算法，在整个计算过程中，需要使用1G内存，会发生什么情况。
对PC而言，一般有4核CPU，和4G内存。不考虑什么操作系统了。就算他正好，可以同时开4个进程来计算。
对显卡而言，N卡有1000+个计算单元，A卡有3000+个计算单元。但是，就算你是再高端，也不过4G显存。你也不过开4个进程同时计算。
前面所说的算法要求，不可并行，就是指从内存角度讲，只够同时开展4项工作，那么就只能动员4个计算单元。无法用多个计算单元来同时完成一项工作。
对ASIC来说，如果一块ASIC能够直接访问1G内存，他就已经不能被称为ASIC了，至少已经是定制CPU了。

那么我们看看这种定制CPU是否值得制造呢？
目前4G内存200大洋，而如果用于挖矿还需要配的CPU主板、电源，不会超过2000大洋。即内存价格占总计价格的10%以上。
如果出现了专业矿机，就算他芯片的价格为0，但仍旧是需要使用200块的内存，才能达到上述计算机的性能。即专业矿机的性价比，不超过普通计算机的10倍。
以这样的性价比提升，是不值得来设计如此复杂的专用芯片的。

好了，大家已经知道了，只要设计出一种使用真正大内存的算法，就可以只运行CPU挖矿。当然，算法如像算力提升那样，可以将需要使用的内存进行调整，那就更好了。

那么如何设计一种这样的算法呢？我们仍旧只讨论hash算法，质数算法什么的，我还没研究呢。
其实，就拿sha256做一个变异就行了。我称之为sha256M，
sha256算法中，有w数组，共64项。直接把这个数组扩大到256M项，占用1G内存。
并把算法中涉及这个数组的各种64次的循环，变成256M次。应该就可以了。

但是问题来了，一般CPU的sha256算力为1M每秒，而我这个sha256M，因为用不上cache，估计速度为0.1次每秒。好像太低了。
那也没问题，先让一下步，来个sha256-1M，-2M什么的。当算力提升上去以后，在逐步调整难度么。

对于Scrypt来说，就更简单了。LTC中使用的Scrypt是MFcrypt算法的一种特例，是使用了SMix和sha256，并将长度定为128K的MFcrypt算法。
Scrypt本身就有个N参数调整内存使用大小。将他调大，并可以根据算力继续调整就行了。

好了，回到文章的标题吧。
如果存在矿机，那么挖矿的门槛直接就提高了，个人无法与机构抗衡。但如果只能用CPU挖矿，即便是再大的机构，也不过能动员几万到几百万台计算机集中。这些计算机足以被淹没于人民大海中。
而要去中心化，只能用CPU挖矿，也就是必须使用真正足够大的内存来计算。
也就是说，未来的挖矿，不是比CPU，不是比GPU，更不是比ASIC，而是比MEMORY。

[zafery]

电子货币的价值 寄托于真正的去中心化 无论是资本还是技术 现在看来无论如何 BTC模式只能是一个先驱

[BenHur]

好文章，支持个。

[ef_asm]

占用内存过大的话，普通不挖矿的客户端的负担就会比较重。

[bitbbs]

学习了

[yingfeng]

嗯，正有此意，如果你打算开一个 新算法新币的话，记得叫上我一起....

[luckyboy]

要我说，楼主说的话也挺像一个预言家！

[arowser]

其实就是三句话，1：要防止破解，需要用大量的内存。2：要防止破解，要不可并行。3：要防止破解，要在内存中分散存储。

赞，非常精辟

[quickhorse]

但是，为什么没有出现使用如此大算法的电子币呢？世界上的比我聪明的人多的是。
其实原因，上面已经有人提到了。就是“验证”

我们还是先来看看BTC把。参照我前面的文章，算力与难度 https://bitcointalk.org/index.php?topic=352114.0
BTC中即便是难度1，计算与验证的工作量比，是4G比1。举个例子，目前在矿池中，满足难度1的计算结果可以作为是一次提交。全网算力目前算是8P，那么没秒会产生满足难度1的结果2M个，而在1秒内验证2M次，一台稍微好的PC就足够了。
而对于只使用钱包，而不挖矿的机器来说，用于验证的时间更是微乎其微。没有人会为了节省一点点验证的时间而放弃验证的。

但如果使用我上面的算法，验证时间可能就会占到总时间的10%以上。而验证同样需要使用1G内存，浪费了挖矿资源。于是就会有人放弃验证，进而产生漏洞。

所以，真正需要的是一种这样的算法
在计算时，需要大量的内存，大量的时间；而在验证时却仅需要不多的内存和时间。
RSA使用的大质数分解倒是一个满足的算法，但问题是谁来出题呢？谁来保证不同的分解大致需要相同的时间呢？

所以，说到底，电子币的根本还在算法，恕我在数学上才疏学浅，实在是不知道有什么算法满足这样的条件。

[eastneo]

好文章，喜欢讨论技术的文章，赞！

最后一句不能苟同，MEMORY有那么大的功力吗？
你搞一个可以调整的算法，ASIC不就死了吗？

[lanfanblue]

版上真应该多一些这样讨论技术的文章！
LZ的思路和我的基本一致，但也有些地方不同，我也写写我的看法。

首先说说“计算需要大量内存，但验证只需要很少内存的算法”。
在bitcoin及其衍生出的各种coin体系中，计算的算法和验证的算法其实是同一个算法。挖矿的本质实际上是在不同组合中搜索找到一个能满足验证要求的组合，由于这种算法本身的特性，使得搜索结果不可预测，因此只能采用类似穷举的方法去逐一尝试。
如果想提升验证算法的复杂性和内存占用量，从而“伤害”矿工收益，那么这些复杂性的提高也会同等程度地“伤害”到普通客户端的验证工作；反之，若想让一般用户得益于验证的简单，矿工也会同等程度地受益。也就是说现有体系内，算法是“对称的”。
LZ想引入求解问题（或优化问题）的方式来区别普通用户和矿工的复杂度，但如LZ所说，问题由谁来出是一方面。另一方面，这类问题很容易触到数学中的NP问题，使得难度不可控，最后整个体系不可控。
所以满足这类要求的算法，恐怕很难实现。

另外，关于内存容量问题。我的观点是：我认为能限制ASIC矿机速度疯涨的不是内存容量，而是内存带宽。
看LZ的讨论似乎没有涉及到ASIC设计制造相关的话题，我就假定LZ没有IC设计经验了。
事实上，要在一个芯片中集成内存是非常容易的事情，各大工艺厂商基本上都提供的现有的内存单元。在ASIC矿机中集成大量内存没有技术上的难度，但有成本上的劣势：增加芯片面积导致成本增加。但成本问题会随着币值上升得到改善。最近LTC的行情不也带来的LTC ASIC矿机么，即便它的性能并不如人意，至少证明了它是可能的。
一般来说，ASIC中每次内存写需要一个时钟周期，每次内存读需要两个时钟周期（良好的流水线设计可能可以改进到一个周期）。以LTC使用的128K内存为例，假定时钟周期为200M，那么若要实现一个周期完成一次scrypt算法（即200MHash/s），那么内存带宽至少需要200M*128K=25600Gbit/s。显卡的内存带宽算比较高了，但不用去查证也能猜到远达不到这样的要求。而且这里还没有讨论高带宽内存带来的各种信号串扰的问题。
再看看最近出的Gridchip LTC矿机，有60kHash/s算力，那么它的带宽至少有60k*128K=7.68Gbit/s。这样的带宽不低了，所以我觉得Gridchip团队芯片设计能力还是很强的！

最后，另一位朋友提到”可调整算法“。我的观点是”可调整算法“也是算法，只要算法的功能行为可以预测，那么就可以在ASIC中实现它，ASIC始终活着。唯一需要考虑的是成本效率等各方面其他因素。

以上是我的一些想法，欢迎讨论！

[quickhorse]

多谢各位提出的意见。在此一并感谢。

首先是eastneo所说
关于多个算法混用的问题，确实可以解决掉ASIC。找上100种算法变种，分别执行一次，就可以让ASIC的设计复杂上100倍。
但这首先在数学上不美，其次干不掉GPU。我的本意是设想一种只能CPU执行的算法。即便我们想不出来算法，也可以讨论一下这个算法应该具有的特性。
YAC在这方面做了尝试，但如果他真正能够发展到目前BTC的规模，他就会遇到“验证时间占比”的问题了

还有lanfanblue所说
目前电子币的算法都是“对称”的，以解决难度的控制。确实是如此。出题的问题，我认为密码学家们会解决的。但是“不对称”的算法可能陷入NP，我也认同。所以才会认为算法的难以确定。

但对于内存带宽的问题，我是如此认为的。
首先说明一点，我是没有IC经验，是纯软出身。所做过的电子产品，只有小时候的收音机了。
但AVALON的公开资料还是看了的，也知道他那两根串行线，不过512B/s。
我认为不需要这么高的带宽，矿机本来就是靠数量取胜的。即便由IBM、Intel来设计，单核的速度也不会超过4G，而目前一个核300M的速度应该是速度与功耗之间的一个折中点。不论是几百G的矿机，还是几T的矿机，都是靠内核数量的增加而提升的。
而因为每一次计算是独立的。所以与其设计一个带宽25600G的核，还不如设计2560个10G的核，当然这会增加芯片面积。设计人员会在电路数量与带宽之间找到一个平衡点的。

[lanfanblue]

我所说的带宽是处理单元到内存的数据带宽，如果把内存集成到芯片内部的话，那么这个带宽就是芯片内部带宽。
串口通信带宽属于外部带宽，这两个带宽是两个东西，而且与内部带宽相比，外部带宽几乎可以完全忽略。

“所以与其设计一个带宽25600G的核，还不如设计2560个10G的核。”这话没错，但要考虑若是设计不出10G的核呢？若是设计的核仅有10M，用2560k个核去实现相同算力，是否还合算呢？问题其实又回到单片芯片的性能是否合算的问题上了。

设计矿机是一个成本收益问题，而随着算法复杂度的提高，成本问题主要集中在内存上。LZ和我在这一点上是一致的。
LZ认为内存容量是成本的瓶颈，而我所指出的是在内存容量成为问题之前，会先遇到内存带宽问题。
我们以最新出的Gridchip为例分析吧。Gridchip Datasheet里有具体参数，一个芯片里有160BTC单元，4个LTC单元，我们姑且认为两者成本各占一半，也就是说160BTC单元的成本和4LTC单元的成本相同。另外，做ASIC基本上是看面积收费的，我们可以认为两者面积相同。
如果不考虑带宽的话，那么LTC的算力应该是BTC的1/40（2.25G/40=~56M）。极端一点设想一个1G内存算法，那么1个1G算法单元所占面积相当于320kBTC单元（4LTC=512k相当于160BTC，1G相当于160*2*1kBTC），那么1G算法的算力应该是BTC的1/320k（2.25G*2*1k/320k=~14M）
但考虑带宽的话，LTC算力只有60k，相当于单核内存带宽上限60k*128K=7.68GB/s（纠正之前一个错误，这里应该是GB/s而非Gbit/s）。对应到1G算法下，其算力仅有7.68Hash/s（7.68*1G=7.68GB/s）
也就是说，LTC算法遇到56M容量瓶颈之前，会先遇到60K的带宽瓶颈，这也就是Gridchip LTC算力只有60K的原因；而1G算法在遇到14M容量瓶颈之前，会先遇到7.68的带宽瓶颈。这里的瓶颈都是指性能成本比的瓶颈。

所以，总的来说：LZ和我在内存问题这个大方向上是一致的，LZ仅考虑的内存容量所带来的成本问题，进而使得性能成本比下降。我所指出的是在内存容量成为成本问题之前，会先遇到带宽上限所导致的性能极限问题，同样会使得性能成本比下降。

[quickhorse]

我有点清楚我和你意见分歧的原因了。说到底是习惯的不同，造成了对ASIC结构理解的不同。
对于ICer来说，所谓ASIC是在一个时钟周期内，完成一次算法操作。得到一个输出。
而对SOFEer来说，习惯于微指令，一个算法可以在多个时钟周期中完成，而得到一个输出。

举个例子来说吧。每一次sha256的计算，就是对W数组的48次循环，和64次主循环。每个W循环约24个CPU指令，主循环大致需要30个CPU指令，再加上一些附加内容总计约3100个CPU指令。因为这些都是最简单的与或非操作，所以用ASIC来实现也就意味着3100个门电路。所以一个核就是这么3100个电路。
但是对我来说，我会设计一个W数组核，一个主循环核，并按3:4配比（当然，稍微浪费一点，用1:1来配比，可以简化不少结构），形成一个小核。在一个时钟周期内，W数组核执行一次，主循环核也只执行一次。
再用16个小核形成一个大核。这样的一个核也是3100个门电路。

原来是在一个时钟周期中产生一个结果，而我的这个流水线核，是在64时钟周期内，产生64个结果。执行的效果与原来的核一样。
由于各个同类型的核之间，没有数据交换，可以认为他们的总线是割裂的。所以造成的最大的好处，就是对带宽的要求降低64倍。
当然，我都称其为流水线核了，设计这个一个核的难度，比原来的要难。
所以，我认为，对内存带宽的要求，会随着流水线长度的增加而减少。不过就是增加设计难度么。

当然，我没有IC经历，我的这些推导，是根据CPU结构而想象的。不知道是否正确。

[Leather]

说的太好了，必须得赞一下，希望这样的技术贴越来越多

[lanfanblue]

我上一次回复用的单位都是“每秒”，其实我是想避开时钟周期的问题，避免讨论流水线。因为流水线过于底层了，而且详细分析流水线的结果，其实和在更高抽象层次分析的结果是一样的…………
不过既然已经打开流水线话题了，那就聊聊吧。

简单说几个前提：
流水线对于IC设计者来说并不复杂，事实上这算是IC设计的基本功了。如果觉得设计流水线对性能有帮助，就尽管让IC设计者做流水线，如果他做不出来，那就炒了他吧。实际上，IC设计者应该主动去设计流水线。
可以参考BTC的FPGA矿机Verilog代码（里面有个UNROLL参数用于调整流水线深度），现在的BTC ASIC设计基本上都是64级流水线：每一次计算都需要经历64个周期，但每个周期都会有1个结果输出。
习惯上来讲，64个周期完成64个结果，我们还是会称其1个周期完成1个结果。因为从平均状态上来看，两者性能是一样的。也就是说，我最开始那一次回复里提到的“一个周期完成一次运算”也隐含了流水线设计。

另外，我们要统一一下流水线的架构，就借用你所熟悉的CPU架构吧。每一个CPU处理器核心，只拥有一条流水线（不考虑超线程或其他类似技术），只能访问一块L1 Cache的数据（L2 Cache和主内存的访问属于memory hierarchy的问题）。多核处理器有多个核心，多条流水线，多块L1 Cache。讨论流水线的话，先考虑单核处理器，多核属于并行化的问题。
说到这里，应该比较清楚了吧。一条流水线里，无论分多少级，里面各级所连接的内存是同一块！
如果分64级，对于某一个特定的运算过程而言，它的内存带宽占用确实减小到了1/64；但是，在同一时刻，流水线里还在执行着其他63个不同的运算，这些运算也都需要占用内存带宽。从平均状态来看，和1个周期完成1次运算所占用的内存带宽是一样的。
换个角度考虑，假设64级流水线中，只有1级是需要访问内存的（类似于CPU流水线的memory access级）。那么每一个时钟周期内，都有不同的运算需要访问内存，所需的内存带宽其实也没变。
考虑内存带宽时，我个人喜欢直接从内存的角度来看问题，在处理单元角度看有点绕。在这个问题里，可以这么想。若要1个周期内完成1次运算，无论有没有流水线，它都需要访问128k内存（假设128k），那么时钟为1M的话，它所需要的带宽就是128GB/s。这个带宽需求无论怎样改设计，都无法改变。
所以我说：无论是从处理器流水线的角度去看，还是从更高抽象层次去看，结果都是一样的……

希望我描述清楚了……

[quickhorse]

lanfanblue老师你好，我是一个IC初学者向您请教，请不要介意问题的幼稚与无知。

关于同一个“串行”流水线，因为“一条流水线里，无论分多少级，里面各级所连接的内存是同一块”，所需内存带宽与不分流水线是一样的。这个问题我已经知道了。

但是“并行”流水线呢？因为事实上循环的64次，操作都是一样的，经过一次操作后，本级流水线把自己的输出当输入继续计算。64次以后提交结果。这也就是我说的“同类型的核之间，没有数据交换”。

串行流水线中，同类型的核之间是交换数据的。

一个最小的核，有24个门电路完成W数组循环，30个门电路完成主循环。另需要64*4*2字节内存存放两个W数组。另外8*4字节存放h数组。对于K数组，那是常量，多少个小核共享一个K数组，需要权衡一下。
每一个时钟周期内W和Main各执行一遍。
前64个周期，W电路将前64*4字节，第一个W数组填满。
次64周期，Main电路处理前64*4字节，64次。W电路将后64*4字节，第二个W数组填满。
可能需要一个周期进行输出。
再次64周期，Main处理后64*4字节64次。W填写前64*4字节。
如此往复。

这样64，或者可能是65个小核组成一个大核。实现一个周期输出一个结果。这样的结构，是否能减少内存带宽的使用呢？

谢谢。

[quickhorse]

是不是在一个IC中，内存是统一编址的，共享总线，不能分割？

[sunjar2013]

好文章，拜读了。

[Depeex]

学习学习...