针对PathORAM的叉型访问方法
[0025]B1.首先判断LRQ是否已满(即充满数据请求)，如果不满，在LRQ中插入无意义label(dummy label)；
[0026]B2.对于LRQ中的所有label，判断label对应的path与当前正被访存path的重叠部分块数。判断具体可以通过异或两个path的label值，看异或结果中O出现的最高位，例如是label中的第k个比特，那么重叠块数即为Z(篮子bucket里内存块的数量)*k。重叠得最多的块会被提前到LRQ的最前，成为下次被执行的LRQ请求；
[0027]B3.在B2步骤执行过程中，如果有新的A步骤(A4步骤和B步骤同时进行)产生的IabeI请求进入LRQ，新的label会替换无意义label，并且这个IabeI会和LRQ最前的label进行比较，看谁与当前path的重合度更高，更高的会在LRQ最前；
[0028]B4.最前的LRQ请求会被传输给地址转换逻辑，等待地址转换逻辑将其转化为内存能理解的读写操作；
[0029]C.在地址转换逻辑处理LRQ请求的阶段，转换逻辑对label请求进行处理，将其转化为针对内存逻辑地址的读写序列;执行如下操作:
[0030]Cl.对于每个label即将转化成的请求中读的部分，对应path中与LRQ中上一个label (即IabeI ’)对应的path不重合的部分，当前请求不访问上一个请求访问过的逻辑地址;即上一个请求访问过的逻辑地址，本请求不会访问；
[0031]C2.对于每个label即将转化成的请求中写的部分，对应path中与LRQ中下一个IabeI对应的path不重合的部分；当前请求不写回上一个请求即将访问的逻辑地址，即下一个请求即将访问的逻辑地址，本请求不会将其写回。
[0032]C3.地址转换逻辑得到的大量读写请求将被传输给MAC;
[0033]在C2和C3步骤的控制下，树状结构的模式不可见存储器(ORAMtree)的被访问的方式恰好是叉型的，因此，本发明提供方法称为叉形访问方法。而现有的Path ORAM的访问方式下，把柄部分会被多读写I次;因此，本发明提供方法提高了效率。
[0034]在C2和C3步骤的控制下，树状结构的模式不可见存储器(ORAMtree)的被访问的方式恰好是叉型的，因此，本发明提供方法称为叉形访问方法。而现有的Path ORAM的访问方式下，把柄部分会被多读写I次;因此，本发明提供方法提高了效率。
[0035]D.在merge的缓存结构(Merging Aware Cache(MAC)处理地址转换逻辑请求的阶段，针对MAC接受读写序列后，通过对应的标签(tag)位判断是否hit以及miss，操作方式和普通cache—致;执行如下操作:
[0036]Dl.对于MAC，只缓存Path ORAM从“相邻路径平均重叠长度”层数以及向上一定层数的块地址，缓存的块数和MAC的大小有关;缓存的块数等于MAC大小除以数据块大小;相邻路径平均长度取决于标签请求队列LRQ的长度，经验公式是2+log2(LRQ长度)这个数的像下取整。
[0037]D2.对于每个请求，MAC首先判断是否属于那些自己缓存的层，如果不属于，直接将此请求传输给内存；即:只要请求对应的块处于“相邻路径平均重叠长度”层数以及向上一定层数的块地址，这个块会被缓存，否则不会。
[0038]D3.如果属于相应的层，那么首先计算出在对应的set (组)，通过对应的标签(tag)位判断是否hit(命中)，如果hit，直接进行读写操作。计算方法如下:首先将请求的地址转化为对应树状结构中的X层的第y个块。然后X除以每个set大小，假设得到W。那么在第w+1那个组中去检验tag，看是否有tag值等于请求的逻辑地址，若等于为hit、若不等于为miss。如果miss(未命中)，那么向内存发送相应的请求，并采用LRU(最近使用策略)替换此set中相应的块；
[0039]E.内存处理MAC请求阶段:在内存接收到MAC请求后，返回或者写入对应的数据即可:数据返回给ORAM controlIer或者数据写入内存:
[°04°] El.0RAM controller接收返回数据后，把数据全部放在stash中，并且把LLC的{op，addr}请求所需数据返回给CPU ；
[0041 ] E2.posit1n map中LLC请求对应的块的label会随机分配一个新的值。
[0042]与现有技术相比，本发明的有益效果是:
[0043]本发明提供一种针对PathORAM的叉型访问方法，该方法是一种隐藏访存模式的硬件结构优化方法。通过本发明所提供的Path ORAM的访存模式，利用去除相邻两个路径的重叠部分的访问，减小了ORAM访存的数量，加快了ORAM系统的执行速度，并且还可以降低功耗。具体地，本发明具有如下优点:
[0044](— )通过叉形访问来避免对两个相邻ORAM请求重叠部分的访问；
[0045](二)通过对LRQ中的ORAM请求的顺序进行调度来增加相邻ORAM请求重叠程度；
[0046](三)通过在地址转换逻辑后增加一个只缓存从“相邻路径平均重叠长度”层数以及向上一定层数的块地址数据的缓存进一步减小访存数量。
【附图说明】
[0047]图1是本发明提供的针对PathORAM的叉型访问方法的流程框图。
[0048]图2是本发明提供方法中ARQ处理LLC请求的流程框图。
[0049]图3是本发明提供方法中LRQ处理ARQ请求的流程框图。
[0050]图4是本发明提供方法中地址转换逻辑处理LRQ请求流程框图。
[0051 ]图5是本发明提供方法中MAC处理地址转换逻辑请求的流程框图。
[0052]图6是本发明提供方法中内存处理MAC请求阶段的流程框图。
【具体实施方式】
[0053]下面结合附图，通过实施例进一步描述本发明，但不以任何方式限制本发明的范围。
[0054]本发明提供一种针对PathORAM的叉型访问方法，该方法是一种隐藏访存模式的硬件结构优化方法，能够达到在很小的硬件代价下降低Path ORAM的访存代价，从而大大提高系统整体性能。
[0055]本发明提供的针对Path ORAM的叉型访问方法具体包括五个阶段一一ARQ处理LLC请求阶段，LRQ处理ARQ请求阶段，地址转换逻辑处理LRQ请求阶段，MAC处理地址转换逻辑请求阶段，内存处理MAC请求阶段。
[0056]对于I个Path ORAM(例如三层的DDR3内存)，Path ORAM的层数取决于内存、数据块的大小以及bucket的大小；每个bucket中包含Z个(Z是一个大于等于4的整数)加密后的memory块(数据块)；新来的末级缓存LLC请求序列是{opl ,addrl}，{op2，addr2}(其中opl，op2 = read或者write)。{opl ,addrl}表示对addrl的数据进行opl操作(读或者写)的一个请求，{op2，addr2}表示对addr2的数据进行op2操作(读或者写)的一个请求。现在正在处理的请求是{op0，addrO}。ARQ能存储128个请求(ARQ长度可以是任意正整数，本例中ARQ长度128)，LRQ的长度是64(LRQ长度可以是任意正整数，本例中为64)，MAC的大小可以是任意整数个的数据块大小，假设processor内部控制ORAM工作的相关电路包含的地址表(Posit1nMap)中，{opl ,addrl} , {op2，addr2} , {op0，addr0}这3个请求对应的标签分别叫做labell、label2、IabelO ；针对Path ORAM的叉型访问方法包括如下步骤:
[0057]A.在地址请求队列ARQ处理末级缓存请求LLC阶段，执行如下操作:
[0058]Al.当末级缓存(LLC)发生一次miss(未命中)需要对memory进行访问，对于每个末级缓存请求1p，addr} (op表示请求是读还是写操作，addr表示末级缓存希望访问的逻辑地址)，首先判断ARQ中是否有和ad
文档序号 :
【 9826212 】
技术研发人员：孙广宇,张宪,张超,张玮其
技术所有人：北京大学
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除
技术研发人员：孙广宇,张宪,张超,张玮其
技术所有人：北京大学
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除