目录

一、问题背景

二、问题深入

三、C model代码

四、初始思路分析

五、方案存在的问题

六、问题解决方式

七、总结

一、问题背景

假设存在这样的单链表，链表每个节点为16bit，其中bit14为1标明该节点是否为根节点，如果是根节点则bit 13-0用于存储根节点对应数据；如果bit14为0则标明该节点是中间节点，bit 13-0则存储该节点指向的下一节点位置。

二、问题深入

在此题设下如果一个单链表存储在sram中，需要完成这个单链表的遍历，即找出链表中每条单链的根节点，获取根节点中存储的数据，赋给每一个中间节点，例如单链表连接如下：

需要经过遍历后所有中间节点都存储根节点信息：

三、C model代码

四、初始思路分析

与C model一致，对每个节点先读出，判断是否为根节点，不是根节点则顺着链表往下知道找到根节点，得到根节点中存储数据；随后再次从头节点开始，先读出该节点数据得到下一个节点地址，随后将根节点数据写入到该节点中，如此往复，下面以上面图中的链表为例描述memory读写行为：

第一步：找出根节点，需要依次读memory的地址7->3->5->2->1

第二步：再次顺着链表刷掉中间节点，同样依次读地址7->3->5->2->1；同时也需要依次写地址7->3->5->2，写的数据是从地址1中读出的数据。

五、方案存在的问题

1、每条单链表需要访问每个地址2次；

2、因为sram读使能与读数据之间有一个cycle的latency，因此需要2个cycle才能完成在链表中一级跳转，效率低。

六、问题解决方式

1、将初始思路中第一步遍历链表时的地址记录进fifo，第二次访问时直接从fifo中获取链表跳转地址，省去第二次链表读操作：

2、将链表头按照奇数偶数分成2组，穿插着进行遍历，即在读sram是的ram_ren的下一个cycle，原本需要等待数据从sram中出来，但是此时可以用于另一条链的遍历。

例如有下面两个链：

遍历7->3->5->2->1时，可穿插着遍历10->9->8，具体时序如下：

分组可以按照不同的方式，例如可以按照起始节点地址大小分，也可以按照奇偶地址分，修改后模块示意图为：

七、总结

到此解决了上述的问题，可以比较高效完成多个单链表遍历，每个cycle可以在链表中跳转一次。

最后

以上就是激昂向日葵最近收集整理的关于＜RTL设计的艺术＞ verilog实现单链表遍历一、问题背景二、问题深入三、C model代码四、初始思路分析五、方案存在的问题六、问题解决方式七、总结的全部内容，更多相关＜RTL设计的艺术＞内容请搜索靠谱客的其他文章。