针对PathORAM的叉型访问方法
[0059]l)(op’ ,op) = (read,read)，将{op,addr}当做普通请求处理即可；
[0060]2)(op，,op) = (read,write), {op,addr}被挂起等待{op’，addr}被处理完才能发射；
[00??] 3)(op’ ,op) = (write,read)，直接返回数据给末级缓存；
[0062]4) (op，,op) = (write ,write)，{op，，addr}会被取消。
[0063]A2.如果addr不冲突，ARQ中没有和addr相同的请求{op’ ,addr}，直接将LLC请求插入到ARQ即可;
[0064]A3.对于ARQ中的所有请求，通过查询地址表，被转换为对应的label，如果地址表中没有对应的label，会通过h层次化的模式不可见存储器(hierarchy 0RAM)中的相应机制转化为一个新的label ；
[0065]A4.ARQ请求(已被转换为对应的label请求)会不停传输至标签请求队列LRQ，直到标签请求队列LRQ已经充满数据请求，这时ARQ会等待LRQ有空位再传输(直到LRQ中没有无意义请求时停止传输);
[0066]B.在标签请求队列LRQ处理地址请求队列ARQ请求的阶段，label进入到LRQ，队列中的label经历调度算法后，最前的label传递给地址转换逻辑;调度具体执行如下操作:
[0067]B1.首先判断LRQ是否已满(即充满数据请求)，如果不满，在LRQ中插入无意义label(dummy label)；
[0068]B2.对于LRQ中的所有label，判断label对应的path与当前正被访存path的重叠部分块数。判断具体可以通过异或两个path的label值，看异或结果中O出现的最高位，例如是label中的第k个比特，那么重叠块数即为Z*k。重叠得最多的块会被提前到LRQ的最前，成为下次被执行的LRQ请求；
[0069]B3.在B2步骤执行过程中，如果有新的A步骤(A4步骤和B步骤同时进行)产生的IabeI请求进入LRQ，新的label会替换无意义label，并且这个IabeI会和LRQ最前的label进行比较，看谁与当前path的重合度更高，更高的会在LRQ最前；
[0070]B4.最前的LRQ请求会被传输给地址转换逻辑，等待地址转换逻辑将其转化为内存能理解的读写操作；
[0071]C.在地址转换逻辑处理LRQ请求的阶段，转换逻辑对label请求进行处理，将其转化为针对内存逻辑地址的读写序列;执行如下操作:
[0072]Cl.对于每个label即将转化成的请求中读的部分，对应path中与LRQ中上一个label(即label，)对应的path不重合的部分；即上一个请求访问过的逻辑地址，本请求不会访问；
[0073]C2.对于每个label即将转化成的请求中写的部分，对应path中与LRQ中下一个label对应的path不重合的部分；即下一个请求即将访问的逻辑地址，本请求不会将其写回。
[0074]C3.地址转换逻辑得到的大量读写请求将被传输给MAC;
[0075]在C2和C3步骤的控制下，树状结构的模式不可见存储器(ORAMtree)的被访问的方式恰好是叉型的，因此，本发明提供方法称为叉形访问方法。而现有的Path ORAM的访问方式下，把柄部分会被多读写I次;因此，本发明提供方法提高了效率。
[0076]D.在merge的缓存结构(Merging Aware Cache(MAC)处理地址转换逻辑请求的阶段，针对MAC接受读写序列后，通过对应的标签(tag)位判断是否hit以及miss，操作方式和普通cache—致;执行如下操作:
[0077]Dl.对于MAC，只缓存Path ORAM从“相邻路径平均重叠长度”层数以及向上一定层数的块地址，缓存的块数和MAC的大小有关;缓存的块数等于MAC大小除以数据块大小;相邻路径平均长度取决于标签请求队列LRQ的长度，经验公式是2+log2(LRQ长度)这个数的像下取整。
[0078]D2.对于每个请求，MAC首先判断是否属于那些自己缓存的层，如果不属于，直接将此请求传输给内存；即:只要请求对应的块处于“相邻路径平均重叠长度”层数以及向上一定层数的块地址，这个块会被缓存，否则不会。
[0079]D3.如果属于相应的层，那么首先计算出在对应的set (组)，通过对应的标签(tag)位判断是否hit(命中)，如果hit，直接进行读写操作。计算方法如下:首先将请求的地址转化为对应树状结构中的X层的第y个块。然后X除以每个set大小，假设得到W。那么在第w+1那个组中去检验tag，看是否有tag值等于请求的逻辑地址。如果miss(未命中)，那么向内存发送相应的请求，并采用LRU(最近使用策略)替换此set中相应的块；
[0080]E.内存处理MAC请求阶段:在内存接收到MAC请求后，返回或者写入对应的数据即可:数据返回给ORAM controlIer或者数据写入内存:
[0081]El.0RAM controller接收返回数据后，把数据全部放在stash中，并且把LLC的{op，addr}请求所需数据返回给CPU ；
[0082]E2.posit1n map中LLC请求对应的块的label会随机分配一个新的值。
[0083]下面通过实例对本发明做进一步说明:
[0084]对于I个三层的DDR3内存，每个bucket中包含Z个加密后的memory块;假设Z的值是4，并且假设新来的LLC请求序列是(read,O) (write, I) (read,2) (write ,3)，现在正在处理的请求是(write，0) c^ARQ’LRQ的长度都是4，MAC的大小是一个块大小，假设processor内部控制ORAM工作的相关电路包含的地址表(Posit1n Map)中，O，I，2，3四个逻辑地址对应的label分别是2，0，1，3。本发明的工作分为五个阶段，如图1所示，包括ARQ处理LLC请求阶段，LRQ处理ARQ请求阶段，地址转换逻辑处理LRQ请求阶段，MAC处理地址转换逻辑请求阶段，内存处理MAC请求阶段。
[0085]图2是ARQ处理LLC请求的流程图。如图2所示，在ARQ处理LLC请求阶段，由于(read，0)与(Write，0)是读写同一个地址，(read，0)请求直接被返回数据，因此ARQ中会加入3个请求(write，I)、(read，2)、(write，3)，查询 Posit 1n Map 注册表经过 posmap 的转换后，0，1,3这三个label请求会被发送给LRQ。
[0086]图3是LRQ处理ARQ请求的流程图。如图3所示，LRQ处理ARQ请求阶段，由于path-3与path-2重合度最高(path-3和path-2重合路径长度为2个bucket，另外两个的重合路径长度只有I )，所以4这个请求会被提到最前，作为下一个被LRQ传输给下一阶段的请求。因此LRQ中的请求顺序是3,0，I。
[0087]图4是地址转换逻辑处理LRQ请求流程图。参考图4，在地址转换逻辑处理LRQ请求阶段，由于path-3和path-2重合的地址是(O，1,2,3)(8,9,10,11),和path-Ο重合的地址是(0，1，2，3)。转换逻辑对label请求进行处理，将其转化为针对内存逻辑地址的读写序列，所以这个label请求会转化为对(20，21，22，23)这些地址的读请求，以及对(4，5，6，7)(12，13，14，15)这些地址的写请求(括号中四个数表示一个bucket)。
[0088]图5是MAC处理地址转换逻辑请求的流程图。参考图5，在MAC处理地址转换逻辑请求，假设(20，21，22，23)这个地址恰好在MAC中，那么这四个地址会直接返回给LLC;若不然，对(20，21，22，23)这四个地方的读请求会发送给内存，并且在数据进入MAC后会替换原有的数据。
[0089]图6是内存处理MAC请求阶段的流程图。参考图6，在内存接收了MAC的读请求后，会返回(20，21，22，23)这四个地址的数据给ORAM c
文档序号 :
【 9826212 】
技术研发人员：孙广宇,张宪,张超,张玮其
技术所有人：北京大学
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除
技术研发人员：孙广宇,张宪,张超,张玮其
技术所有人：北京大学
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除