可以在ASIC中建立多个电路逻辑,同时并发的计算多个指令。例如,上文的a + b + c + d指令可以被设计为(a + b) + (c + d),将在2个周期中完成计算。
目前,这种流水线化的思想还被广泛地应用于诸如x86之类的现代处理器中,这些x86中具有分支预测器[2]和流水线微处理器。一种避免处理器计算流水线的方法是执行多个if-then-else命令,然后在不同的分支上执行不同的代码路径,这使得流水线和分支预测变得很难。
为了打破执行过程的并发性,我们可以考虑采用于状态依赖的思路——任何未来的指令都依赖于当前状态,而这种状态(当前状态)可以频繁地被改变,这意味着我们不能预先执行未来的指令。
基于顺序统计的哈希算法
在本节中,我们将介绍我们提出的顺序统计哈希算法(Oshash)。该算法试图打破流水线,使代码的执行路径变得更加随机。在介绍这种新算法之前,让我们重新回顾一下Ethash算法的核心内容,看看Ethash是如何生成一个哈希值的:
Input:
– state: 128-byte state
– datablock: an array of large amount of data, each data is 64 bytes
– H(x, y): a fast hash algorithm, x and y has the same size, return the hash value with the same size as x
– R(x): return an 32-bit random integer derived from x
Algorithm:
for i in range(64):
p = R(state) % (len(datablock) – 1)
newdata = [datablock[p], datablock[p + 1]]
state = H(state, newdata)
return state Oshash算法的初步方案如下:
Input:
– state: 128-byte state
– datablock: an long array with each entry being 8 bytes
– H(x, y): a fast hash algorithm, x and y has the same size, return the hash value with the same size as x
– R(x): return an 64-bit random integer derived from x
Algorithm:
for i in range(64):
p = R(state) % len(datablock)
newdata = []
for j in range(128 / 8):
newdata = newdata.add(datablock.find_by_order(p))
# Remove the pth smallest element from datablock
datablock.remove_by_order(p)
# Add a random data to the datablock, e.g.,
# datablock.insert(R([newdata[end]]))
# Find the next index, e.g.,
# p = R([state, p]) % len(datablock)
state = H(state, newdata)
return state Oshash算法与Ethash的关键差异如下:
Yang, Y-H. E. and Prasanna, V. K., High Throughput and Large Capacity Pipelined Dynamic Search Tree on FPGA, 18th Annual ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays, 2010