针对PathORAM的叉型访问方法
[0090]需要注意的是，公布实施例的目的在于帮助进一步理解本发明，但是本领域的技术人员可以理解:在不脱离本发明及所附权利要求的精神和范围内，各种替换和修改都是可能的。因此，本发明不应局限于实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。
【主权项】
1.一种针对Path ORAM的叉型访问方法，包括:地址请求队列ARQ处理末级缓存请求LLC阶段、标签请求队列LRQ处理地址请求队列ARQ请求的阶段、地址转换逻辑处理标签请求队列LRQ请求的阶段，MAC处理地址转换逻辑请求阶段和内存处理MAC请求阶段，所述叉型访问方法通过隐藏访存模式的硬件结构优化，达到在很小的硬件代价下降低Path ORAM的访存代价，从而大大提尚系统整体性能;具体包括如下步骤: A.在地址请求队列ARQ处理末级缓存LLC请求阶段，执行如下操作: Al.设末级缓存(LLC)请求为{op,addr}，op表示读操作请求或写操作请求，addr表示末级缓存希望访问的逻辑地址；当末级缓存LLC发生一次miss未命中时，需要对内存进行访问； A2.当末级缓存LLC对内存进行访问时，对于每个末级缓存LLC请求{op，addr}，当地址请求队列ARQ中没有和addr相同的请求时，直接将末级缓存LLC请求插入到地址请求队列ARQ ； A3.将地址请求队列ARQ中的所有请求转换为标签label; A4.将已被转换为label请求的地址请求队列ARQ请求传输至标签请求队列LRQ，直到标签请求队列LRQ充满数据请求； B.在标签请求队列LRQ处理地址请求队列ARQ请求的阶段，进入到标签请求队列LRQ中的标签label经过调度后，将最前的标签请求传递给地址转换逻辑； C.在地址转换逻辑处理标签请求队列LRQ请求的阶段，转换逻辑对标签label请求进行处理，通过叉型访问方式访问树状结构的模式不可见存储器ORAM tree，将标签label请求转化为针对内存逻辑地址的读写请求序列，所述地址转换逻辑得到的读写请求再被传输给MAC;具体执行如下操作: Cl.当前请求不访问上一个请求访问过的逻辑地址:将每个标签label即将转化成的请求中读的部分，对应path中与标签请求队列LRQ中上一个标签Iabe I’对应的path不重合的部分； C2.当前请求不写回上一个请求即将访问的逻辑地址:将每个label即将转化成的请求中写的部分，对应path中与LRQ中下一个label对应的path不重合的部分； C3.将地址转换逻辑得到的多个读写请求传输给MAC; D.在MAC处理地址转换逻辑请求的阶段:MAC接受步骤C3所述读写请求后，通过对应的标签位tag判断所述读写请求是命中hit或是未命中miss;当所述读写请求为命中hit时，直接进行读写操作；当所述读写请求为未命中miss时，向内存发送所述读写请求，并通过最近使用策略替换相应的块； E.在内存处理MAC请求阶段:在内存接收到步骤D所述MAC请求后，将对应的数据返回给ORAM controlIer或者写入内存。2.如权利要求1所述针对PathORAM的叉型访问方法，其特征是，所述步骤A2中，当地址请求队列ARQ中有和addr相同的请求{op’，addr}时，分为下列四种情况: A21)当(op’，op) = (read,read)时，将{op,addr}当做普通请求处理即可； A22)当(op’，op) = (read,write)时，{op,addr}被挂起等待{op’，addr}被处理完才能发射； A23)当(op’，op) = (write,read)时，直接返回数据给末级缓存； A24)当(op’，op) = (write,write)时，{op，,addr}会被取消。3.如权利要求1所述针对PathORAM的叉型访问方法，其特征是，所述步骤A3所述将地址请求队列ARQ中的所有请求转换为标签label，具体是当地址表中有对应的label时，通过查询地址表转换为对应的label;当地址表中没有对应的label时，通过层次化的模式不可见存储器hierarchical ORAM转化为一个新的label。4.如权利要求1所述针对PathORAM的叉型访问方法，其特征是，所述步骤B所述调度具体执行如下操作: B1.判断标签请求队列LRQ是否已满，当标签请求队列LRQ不满时，在标签请求队列LRQ中插入无意义标签;当标签请求队列LRQ已满时，执行步骤B2; B2.对于标签请求队列LRQ中的所有标签，计算得到该标签对应的path与当前正被访存path的重叠部分块数，重叠得最多的块会被提前到LRQ的最前，成为下次被执行的LRQ请求； B3.在B2步骤执行过程中，如果有新的A步骤(A4步骤和B步骤同时进行)产生的label请求进入LRQ，新的IabeI会替换无意义label，并且这个IabeI会和LRQ最前的IabeI进行比较，看谁与当前path的重合度更高，更高的会在LRQ最前； B4.标签请求队列LRQ中最前的请求会被传输给地址转换逻辑，等待地址转换逻辑将其转化为内存能理解的读写操作。5.如权利要求4所述针对PathORAM的叉型访问方法，其特征是，步骤B2所述计算得到该标签对应的path与当前正被访存path的重叠部分块数，具体通过异或该标签对应的path与当前正被访存path的label值，根据异或结果中O出现的最高位得到重叠块数。6.如权利要求1所述针对PathORAM的叉型访问方法，其特征是，步骤D所述MAC处理地址转换逻辑请求的阶段，具体执行如下操作: Dl.MAC只缓存Path ORAM从相邻路径平均重叠长度的层数和向上的层数的块地址，缓存的块数等于MAC大小除以数据块大小;所述相邻路径平均重叠长度根据标签请求队列LRQ的长度计算得到； D2.针对每个请求，MAC判断该请求是否属于自己缓存的层；当该请求不属于自己缓存的层时，直接将该请求传输给内存；当请求对应的块处于相邻路径平均重叠长度层数和向上层数的块地址时，将该请求缓存； D3.当该请求属于自己缓存的层时，首先计算出在对应的组set，通过对应的标签位tag计算得到是命中hit还是未命中miss ；当命中hit时，直接进行读写操作；当未命中miss时，向内存发送该请求，并通过最近使用策略替换相应的块。7.如权利要求6所述针对PathORAM的叉型访问方法，其特征是，步骤D3所述通过对应的组set和对应的标签位tag计算得到是命中hit还是未命中miss，具体计算方法如下:首先将请求的地址转化为对应树状结构中的X层的第y个块;然后X除以每个set大小得到值设为w;在第w+1组中检验标签位tag，根据是否有tag值等于请求的逻辑地址得到是命中hit还是未命中miss。8.如权利要求1所述针对Pa t h O R AM的叉型访问方法，其特征是，步骤E所述O R AMcontrolIer接收返回数据后，把数据全部放在stash中，并将LLC的请求{op,addr}所需的数据返回给CPU；再随机分配一个新的值赋给posit1n map中LLC请求对应的块的标签IabeI。
【专利摘要】本发明公布了一种针对Path？ORAM的叉型访问方法，包括：地址请求队列ARQ处理末级缓存请求LLC阶段、标签请求队列LRQ处理地址请求队列ARQ请求的阶段、地址转换逻辑处理标签请求队列LRQ请求的阶段，MAC处理地址转换逻辑请求阶段和内存处理MAC请求阶段；MAC处理地址转换逻辑请求阶段，树状结构的模式不可见存储器ORAM？tree的被访问方式是叉型的。本发明方法通过隐藏访存模式的硬件结构优化，利用去除相邻两个路径的重叠部分的访问，减小了ORAM访存的数量和代价，加快了ORAM系统的执行速度，并且还可以降低功耗，从而大大提高系统整体性能。
【IPC分类】G06F12/0802
【公开号】CN105589814
【申请号】CN201510953863
【发明人】孙广宇, 张宪, 张超, 张玮其
【申请人】北京大学
【公开日】2016年5月18日
【申请日】2015年12月17日
文档序号 :
【 9826212 】
技术研发人员：孙广宇,张宪,张超,张玮其
技术所有人：北京大学
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除
技术研发人员：孙广宇,张宪,张超,张玮其
技术所有人：北京大学
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除