本发明涉及集成电路设计，尤其涉及一种基于加载序列的硬件友好型推测加载电路的方法。
背景技术：
：：1、高性能cpu往往采用乱序(out-of-order)执行的方式，即实际的指令派发、发射的顺序不按照程序序(program order)进行。2、当程序序上靠后的加载(load)指令不依赖于前序存储(store)指令时，该load指令可以被推测执行(speculatively executed)，这种加载方式被称作推测加载(speculative load)。比如：存在一条条件分支(conditional branch)指令，其跳转(taken)程序段中包含了一条store指令；与此同时，分支不跳转(non-taken)的逻辑链路上的第一条指令是访问相同内存地址的load指令。假设分支预测器(branch predict unit：bpu)在历史上大概率预测当前的条件分支指令为non-taken。此时，这条load指令就可以被推测执行。这种做法会在很大程度上提升处理器的性能，但是，如果上述例子中的bpu预测失败，程序进入了taken path，即分支内的store指令被执行了，则speculative load也失败，需要重新执行load指令，反而引起性能损失。3、speculative load的正确执行依赖于利用特定的数据结构来存储历史上产生过的raw冲突条目。store-set[1]是一种实现speculative load的方法，原文的设计基于2级级联的键值映射表。其中，第一张表被称作存储序列识别号表(store-set-identifier-table:ssit)；第二张表被称作最近一次获取的存储指令的表格(last-fetched-store-table:lfst)，其表项索引是第一张表项的内容、其表项的内容是最近一次与某个load发生raw冲突的store的指令序列号(sequence number:sn)。4、产生raw冲突之后，将load指令的程序计数器(program counter：pc)移位并且对表项总数ssit_entries取模(％)，得到表项索引：5、load_index＝(load_pc＞＞2)％ssit_entries6、公式10；7、类似的，由store_pc可以计算得到store指令在ssit中的索引8、store_index＝(store_pc＞＞2)％ssit_entries9、公式11；10、表项的内容(content)由load指令的pc经过hash之后生成，得到被存在raw冲突的load/store共享的标签(tag)，称作存储序列识别号(store-set-identifier:ssid)：11、ssid＝(load_pc^(load_pc＞＞10))％lfstentries12、公式12；13、上式有两层含义：一方面，存在raw冲突的load可能存在多个dependent stores，理想情况下需要存放所有历史上与该load存在raw冲突的store。而鉴于store总是顺序退休的，raw的约束关系的最低要求是建立在load以及最近一次与之发生raw冲突的store之间。store-set的原文设计中lfst的每个entry的value都是单元素数值，即只记录最近一次产生raw冲突的store的sn。另一方面，从电路可实现性的角度考虑：存储完整的64-bit pcs所需的面积开销不可接受。因此，公式12采用了对pc hash之后再约束在lfst_entries范围内的做法，从而实现了一定程度上对load的唯一表示。14、这项设计从原理上就无法实现精确的raw约束。15、不同的store_pc根据公式11求得的store_index可能相同，但store_pc与load_pc之间可能是错误的依赖关系，如下所示：16、17、load_pc与store_pc_1共同维护了一组raw约束关系，即占据了一个ssid:99(由公式12得到)。但是，根据公式11，store_pc_1与store_pc_2都可以得到store_index＝28。从而lfst[99]被更新成了store_pc_2的sn:828451，即store-set的原文设计会认定store_pc_2是最近一次与load_pc:0xffffffe000228cc0产生raw冲突的store，而实际上二者的读写地址不同，没有相关性。技术实现思路1、本发明的目的是为了解决现有技术中存在的问题，而提出的一种基于加载序列的硬件友好型推测加载电路的方法。2、为了实现上述目的，本发明采用了如下技术方案：3、一种基于加载序列的硬件友好型推测加载电路的方法，包括节省面积的设计一、优化时序的设计和节省面积的设计二；4、所述节省面积的设计一，具体包括以下步骤：5、s1、提出了load-sets的数据结构，此时的键(key)是store指令有待写入的内存地址st_addr；值(values)是violating load与各个dependent store的pc的差值的集合；6、所述节省面积的设计二，具体包括以下步骤：7、p1、采用推测加载失败的指令的pc vio_ld_pc与其前序存储指令的pc store_pc二者的差值取代store_pc进行存储，如公式1所示；8、即：9、{delta_pc | delta_pc(i)＝(vio_ld_pc-store_pc(i)),i＝1,2,…} 公式1；10、p2、在指令派发阶段(dispatch stage)，将新进的store_pc以及delta_pc作为解码电路的输入，得到公式2中的vio_ld_pc；11、即：12、vio_ld_pc＝delta_pc(i)+store_pc(i),i＝1,2,… 公式2；13、p3、通过获取的vio_ld_pc再去匹配raw！中的key；14、优选地，所述violating load特指存在raw冲突的load指令，与常规的load指令进行区分；15、存储raw约束关系的键值映射表(key-value mapping table)用raw！表示；16、raw！的key是violating load的pc值vio_ld_pc；每个raw！entry的values是一个集合，用于表征与violating load存在raw冲突的stores的值store_pc。17、所述优化时序的设计，具体包括以下步骤：18、l1、当store指令位于dispatch stage时，检索该store是否已经存在于raw！中，若存在，需要将该store更新为“最近一次”与violating load产生raw冲突的store；19、l2、采用load-sets结合raw！的方式进行检索，对检索复杂度进行降维，采用先根据store写入的内存地址锁定所有相关的violating load，再由vio_ld_pc检索得到各个dependent stores的检索方式将检索的复杂度从o(n2)降维到o(n)，从而确保时序收敛(timing closure)；20、优选地，所述优化时序的设计中，如果仅仅依赖raw！对该store的位置进行更新，则需要遍历raw！的各个entries，检索dependent stores中是否包含当前的store；21、检索的总复杂度：22、23、其中，n表示raw！的entries数、m(i)表示raw！的每个entry中包含的dependentstores的数目。24、优选地，所述优化时序的设计中，对l3做出以下分析：25、1)、设load-sets的entries总数是l，则检索特定的st_addr_j的复杂度是o(l)；26、2)、设st_addr_j关联到的vio_ld的数目是x(x远小于n)，即load-sets[st_addr_j]指向x个delta_pc；随后，将这x个delta_pc送入解码电路，得到x个load_pc；27、在raw！的n行中匹配这x个load_pc，复杂度为：28、o(n)+o(n-1)+…+o(n-(x-1))＝x·o(n)29、公式4；30、3)、设命中raw！的第i行后，在其包含的dependent stores中检索delta_pc[j](0≤j≤(x-1))的复杂度为o(m(i))；31、则完成所有x行的delta_pc的检索复杂度为：32、33、因此，load-sets结合raw！的检索方式总复杂度为：34、35、对比上述两种方式：36、1)、如果m(i)约等于n，则公式3所示的第一种方法得到的复杂度可以进一步表示为o(n2)；同时，设l也约等于n，则由公式6给定的复杂度可以进一步表示为：37、38、从而实现从o(n2)->o(n)的降维；39、2)、如果m(i)远小于n，则公式3所示的第一种方法得到的复杂度为：40、41、另一方面，仍旧设l约等于n，则由公式6给定的复杂度为：42、43、44、基于上述，无论m(i)是否与n位于同一量级，相比直接在整个raw！中检索storepc，采用先根据store写入的内存地址锁定所有相关的violating load，再由vio_ld_pc检索得到各个dependent stores的检索方式，总是可以实现检索的复杂度从o(n2)降维到o(n)。45、相比现有技术，本发明的有益效果为：46、1、本发明通过在指令派发阶段(dispatch stage)，将新进的store_pc以及delta_pc作为解码电路的输入，得到vio_ld_pc，采用vio_ld_pc与store_pc二者的差值取代store_pc进行存储，规避了存放全部完整的store_pc耗费大量的电路面积的情况出现。47、2、相比现有技术直接在整个raw！中检索store pc，本发明先在load-sets中匹配st_addr，锁定历史上针对该内存地址进行推测加载失败的load指令，再在raw！中匹配这些load指令，得到各个dependent stores。通过这种分步检索的方式，实现检索的复杂度从o(n2)到o(n)的降维。当前第1页12当前第1页12
技术特征：1.一种基于加载序列的硬件友好型推测加载电路的方法，其特征在于，包括节省面积的设计一、节省面积的设计二和优化时序的设计；
2.根据权利要求1所述的一种基于加载序列的硬件友好型推测加载电路的方法，其特征在于，所述violating load特指存在raw冲突的load指令，与常规的load指令进行区分；
3.根据权利要求1所述的一种基于加载序列的硬件友好型推测加载电路的方法，其特征在于，所述优化时序的设计中，如果仅仅依赖raw！对该store的位置进行更新，则需要遍历raw！的各个entries，检索dependent stores中是否包含当前的store；
4.根据权利要求1所述的一种基于加载序列的硬件友好型推测加载电路的方法，其特征在于，所述优化时序的设计中，对l3做出以下分析：
技术总结本发明公开了一种基于加载序列的硬件友好型推测加载电路的方法，包括节省面积的设计一、节省面积的设计二、优化时序的设计。本发明开辟了写后读数据结构RAW！、提出了加载序列(Load‑Sets)的概念。采用RAW！结合Load‑Sets的检索方式，以较小的电路面积实现推测加载(Speculative Load)过程中对前序存储指令(dependent store)的精确更新。RAW！以Store指令写入的内存地址st_addr为键(Key)、以speculative load与dependent store的程序计数器的差值为值(Values)，避免存放完整的store_pc而耗费大量面积；在优化时序的设计中，先在Load‑Sets中匹配st_addr，锁定历史上针对该内存地址进行推测加载失败的Load指令，再在RAW！中索引这些Load指令，得到各个dependent stores。相比直接在RAW！中检索store_pc的传统做法，这种分步检索的方令检索复杂度从O(N<supgt;2</supgt;)降维到O(N)。
技术研发人员：黄佳森
受保护的技术使用者：深圳奥维领芯科技有限公司
技术研发日：技术公布日：2024/11/26
