顺序线性表这词搁软件那边就是一个数组加一个长度变量十行代码的事。但把同样的东西搬到Verilog里用时钟、状态机、寄存器去实现一遍味道就完全变了一个周期能搬几个数据、存储体到底用触发器还是块RAM、插入时搬移方向反了会不会把整张表冲掉这些问题在C语言里根本不存在。这几年我在几个FPGA项目里反复写过这类“硬件版数据结构”从最简单的顺序表、栈、队列到后面带优先级调度的链式缓冲踩过的坑几乎都能追到最开始的这张表没设计干净。这篇就把顺序线性表的RTL实现从头到尾拆一遍它解决什么实际问题、存储体怎么选、状态机怎么划、插入删除的搬移怎么写才不出错、仿真怎么验、综合出来长什么样、哪些地方最容易翻车。刚学完Verilog语法想找个能落地的练手项目的人或者已经在写RTL但没系统想过“数据结构在硬件里长什么样”的人应该都能捞到能直接抄的片段。1. 先把需求想清楚硬件里为什么需要一张表1.1 软件思维和RTL思维的分水岭写软件的时候我们对内存有一种近乎挥霍的信任内存近乎无限分配失败再说时间是弹性的一次memmove多花几十纳秒没人管地址是字节级的随便对齐。RTL里这三条全部反过来——面积是先算死的时序是逐拍卡死的访问是地址译码出来的。同样一张能存64个32位数据的表软件里int a[64]一句话硬件里你得先决定这2048个比特是躺在触发器里、躺在查找表里还是躺在一块块RAM里然后每一个读写动作都要问自己“这一拍能不能做完”。这个差别直接决定了设计的走向。软件的顺序表靠“连续地址”实现随机访问硬件里同样成立但“连续地址”在寄存器阵列里体现为一路巨大的多路选择器在块RAM里体现为一个同步读端口。前者一拍出结果但面积吓人后者面积便宜但读数据要晚一拍。所以硬件实现顺序表的第一课不是写代码而是先把“容量、位宽、访问模式、延迟要求”这四个数摁在纸上再决定用哪种存储体。顺序表在硬件里最大的价值也在这里只要地址算出来取数延迟是确定的做流水线的时候敢把它的输出直接接到下一级不用像链表那样追着指针等“第几个周期才有效”。1.2 几张真实会用到它的场景第一类是索引和配置表。比如一组系数、一组门限、一张小路由表运行时偶尔被改写读的时候要求确定性延迟。这种表通常几十项位宽16到64用寄存器阵列实现读是一条线过去写走状态机最省心。第二类是采样缓冲和行缓存。图像处理里按行缓存像素雷达或传感器采样缓存若干点这类表的特点是“先写满再按地址回读”容量稍大块RAM是首选插入删除反而不常用主要是尾插和清空。第三类是命令与槽位管理。在模拟项目X里我给一个多通道调度器做过“槽位表”每个槽位记录一条待执行命令的描述符新命令插到指定优先级位置执行完把槽位删掉。这里删除和插入都很频繁容量只有32最后选了寄存器阵列加多周期搬移。第四类是验证环境的激励生成器。写测试平台时经常需要一个“先攒一批报文再乱序发出”的缓冲用顺序表实现比用动态数组更可控因为硬件里不存在“动态”这回事。最后一类是学习和面试。顺序表麻雀虽小把参数化、状态机、存储体映射、边界处理、参考模型全串了一遍比写一个分频器有意思得多。1.3 存储体三选一寄存器、分布式RAM、块RAM这是整个设计里最影响后续所有代码的选择我做了一张对照表实际选型时基本照这个走对比项寄存器阵列分布式RAMLUTRAM块RAM典型容量几项到一两百项几十项几百项以上读延迟0拍异步或1拍1拍同步1到2拍同步视配置同拍多地址访问支持代价是MUX通常只支持一到两个口一般两个口变量索引读出支持代价随深度上升支持支持复位可逐位复位复位受限通常整体清复位受限面积最大每比特一个触发器中等最省适合谁小表、要搬移、要并行中等规模、单口够用大缓冲、顺序访问为主选型的判断逻辑很朴素要不要在一拍里同时读两个地址。顺序表的插入搬移天然是“读mem[i-1]写mem[i]”寄存器阵列两个动作同时发生毫无压力块RAM只有一个写口一个读口虽然也能一拍完成读改写但读数据是上一拍地址的搬移循环里就得多绕一个状态。容量一旦超过128项寄存器阵列的MUX树会深到影响时序这时候只能乖乖换块RAM用“逐拍搬移读延迟补偿”换面积。提示不要凭感觉估面积。64项×32位就是2048个触发器这已经是一片中等规模器件里相当可观的一块了。写代码前先用这个乘法算一下再决定要不要上块RAM。2. 顺序线性表的硬件模型与接口定义2.1 三个核心要素存储体、长度寄存器、游标硬件版顺序表只需要三样东西就能立起来。第一是存储体mem深度MAX_LEN、位宽DATA_W它是数据的家。第二是长度寄存器len它记录当前有效元素个数也是所有边界判断的唯一依据。第三是游标寄存器ptr搬移和扫描时指向当前处理的位置它是个临时工不参与对外语义。这里有一个很多人第一版会写错的地方len的位宽。如果MAX_LEN64索引需要6位0到63但长度需要能表示0到64这65个值所以len必须是7位也就是$clog2(MAX_LEN1)。用$clog2(MAX_LEN)写成6位表满的时候len会回绕成0整个表瞬间“变空”而且仿真里如果只测到63个元素根本发现不了。我第一版就栽在这上面上板后跑满容量直接行为异常查了两个晚上。存储体的声明方式直接决定了综合结果reg [DATA_W-1:0] mem [0:MAX_LEN-1];这一行看起来平平无奇但综合工具会根据你的访问方式自己判断如果所有读写都是常量索引比如for循环展开后它可能把整个数组打散成触发器如果有变量索引且容量不大可能映射成LUTRAM容量大到一定程度才推成块RAM。也就是说同一个声明不同写法综合结果可能差出几倍的资源。这一点后面第4节会展开说。2.2 命令接口怎么定才不容易翻车接口设计上我试过两种风格最后稳定在用第二种。第一种是valid/ready双向握手每个操作都有独立的请求通道和应答通道。好处是理论上能背靠背发命令坏处是顺序表同一时刻只能做一个操作尤其插入删除要搬移背靠背根本用不上反而多了一堆握手状态要维护代码膨胀得厉害。第二种是单命令通道done脉冲我最终都用的这个。接口大概长这样信号方向位宽说明clk / rst_nin1时钟与低有效复位cmd_validin1命令有效需在busy为低时给出cmdin3操作码尾插、按位插入、按位删除、按位读、按值查找、清空cmd_posinAW位置参数插入删除读用cmd_dininDATA_W数据参数插入和查找用cmd_doutinDATA_W读出的数据或查到的下标cmd_doneout1单拍完成脉冲cmd_errout1越界、满、空、未找到等错误标志list_lenoutLW当前元素个数供外部观察这个接口的关键约定只有两条cmd_valid拉高的那一拍busy必须是低的cmd_done只脉冲一拍外部看到done就等于这次操作彻底结束结果已经在cmd_dout/cmd_err上稳定了。把“结果稳定”和“done”绑在同一拍外部逻辑就不用再等一个周期省掉一堆“done_d”打拍。比valid/ready更省心的地方在于调用方只需要“给命令—等done—取结果”三步中间不需要维护任何握手状态机。代价是吞吐低一次操作最快也要两三个周期。顺序表本来就不是高吞吐结构这个代价我认为完全值得。2.3 参数与位宽的一次性算清参数化不是摆样子顺序表里几个位宽之间有硬约束算错了综合不报错、仿真可能过、上板才炸。我习惯在模块头里一次性写全module seq_list #( parameter integer DATA_W 32, parameter integer MAX_LEN 64, parameter integer AW (MAX_LEN 1) ? 1 : $clog2(MAX_LEN), parameter integer LW $clog2(MAX_LEN 1) )( ... );以DATA_W32、MAX_LEN64为例AW6LW7。所有和位置相关的比较都要注意位宽统一比如判断cmd_pos是否越界cmd_pos是6位len是7位直接写cmd_pos len在Verilog里会按无符号数扩展比较结果是对的但如果你写成cmd_pos len - 1len为0时len-1在7位无符号下变成127判断就彻底错了。这类问题不会报错只会让空表删除的时候不报错反而乱删数据。我的做法是所有和长度相关的减法先做前置判断比如删除操作先判len 0直接报错判完再进正常流程绝不把len-1和位置比较混在一起写。3. 状态机设计与各操作的时序实现3.1 状态怎么划六个状态够用顺序表的操作分两类一类是一拍能收工的尾插、按位读、清空一类是要多拍循环的按位插入搬移、按位删除搬移、按值查找扫描。所以状态机可以划得很薄S_IDLE等待命令同时做越界和边界检查S_MOVE统一的搬移循环靠方向位区分插入还是删除S_SCAN查找扫描循环S_WR搬移完成后把新数据真正写进空出来的槽位S_END产生done脉冲的唯一出口加一个S_RD其实不必要读操作用组合索引取数在IDLE那一拍就能完成。我最初把插入和删除拆成两套搬移状态结果是两份几乎一样的代码改一处忘一处后来合并成一个S_MOVE加一个dir方向位代码少了三分之一出错概率也降下来了。这个思路值得推广到栈、队列凡是“沿一个方向逐格挪动”的操作都可以抽象成同一个循环用方向位和终止条件参数化。状态机本身用三段式或者一段式都行我这段用的是一段式加默认值的写法好处是长度、游标、输出全部在一个always里不会出现“某个分支忘了给done清零”的漏赋值。代价是代码块比较长但顺序表逻辑本来就线性读起来反而顺。3.2 插入和删除搬移方向决定生死这是整篇文章我最想强调的一点。顺序表的插入是在位置p腾出一个空位把p以及p之后的所有元素都往后挪一格。关键在于必须从表尾开始挪。假设你从p开始往后挪先把mem[p]搬到mem[p1]但mem[p1]里的原始数据还没搬走一瞬间就被覆盖了后面所有数据全错。这就像排队插队后面的人必须从队尾那位开始依次后撤一步如果从最前面那位开始后撤他一转身就把第二个人挤没了。删除正好相反把p之后的元素全部往前挪一格必须从p开始往前挪先把mem[p1]搬到mem[p]再处理mem[p2]。如果从表尾往回挪同样会覆盖。用一个生活场景记插入是“从后往前填空”删除是“从前往后压紧”。我在笔记本上就写了这八个字之后所有类似结构栈的压入弹出、队列的出队入队都拿这套逻辑套没再错过。搬移的终止条件也要写对。插入时游标从len开始每次执行mem[ptr] mem[ptr-1]直到ptr pos1那一拍完成最后一次搬移此时mem[pos1]已经等于原来的mem[pos]空位在mem[pos]。删除时游标从pos开始mem[ptr] mem[ptr1]直到ptr len-2最后一次把mem[len-1]搬到mem[len-2]有效区整体压紧然后len减一。这里有个细节删除的“快速路径”。如果pos len-1删的是最后一个元素根本不需要搬移直接len减一如果len 1删完就是空表len置0。把这两条快速路径单独拎出来S_MOVE里就永远不会遇到len-2下溢的情况代码清爽很多也不会出现7位无符号数减出个天文数字的怪事。3.3 查找与遍历扫描循环怎么写才不卡死按值查找是一个从0扫到len-1的循环命中就停。我要求返回最小下标的第一个匹配因为多个相同值的时候返回哪个下标如果没定义上层调用就是不确定行为。用early exit实现S_SCAN: begin if (mem[ptr] data_r) begin cmd_dout ptr; // 命中低位零扩展 state S_END; end else if (ptr len - 1b1) begin cmd_err 1b1; // 扫到底没找到 state S_END; end else begin ptr ptr 1b1; end end这段代码有三个容易漏的点。第一进入扫描前必须先把len 0挡掉否则len-1会下溢扫描循环永远等不到终止条件状态机直接挂死。第二命中即退不要在命中后继续扫完再比较那样延迟翻倍还多此一举。第三cmd_dout是DATA_W位下标是AW位赋值时Verilog会自动零扩展但如果DATA_W小于AW就会截断参数化的时候要在注释里写清楚约束。还有一种“遍历输出”的需求比如把一个表的所有元素依次吐给下游模块。这个不用单独做命令加一个“读游标读使能”的旁路接口更实用外部自己驱动地址、每拍取一个数比走命令通道快得多。顺序表的随机访问优势就体现在这——只要地址不要协议。3.4 核心代码一段式状态机版本下面是我实际用的一版多周期搬移参数化去掉了所有厂商相关的写法localparam C_PUSH 3d0, C_INSERT 3d1, C_DELETE 3d2, C_GET 3d3, C_FIND 3d4, C_CLEAR 3d5; localparam S_IDLE 3d0, S_MOVE 3d1, S_WR 3d2, S_SCAN 3d3, S_END 3d4; reg [DATA_W-1:0] mem [0:MAX_LEN-1]; reg [LW-1:0] len; reg [AW-1:0] ptr, pos_r; reg [DATA_W-1:0] data_r; reg [2:0] state; reg dir; // 0: 插入搬移(后往前) 1: 删除搬移(前往后) always (posedge clk or negedge rst_n) begin if (!rst_n) begin state S_IDLE; len 0; cmd_done 1b0; cmd_err 1b0; cmd_dout 0; ptr 0; pos_r 0; data_r 0; dir 1b0; end else begin cmd_done 1b0; case (state) S_IDLE: begin if (cmd_valid) begin cmd_err 1b0; case (cmd) C_PUSH: begin if (len MAX_LEN) begin cmd_err 1b1; state S_END; end else begin mem[len] cmd_din; len len 1b1; state S_END; end end C_INSERT: begin if (len MAX_LEN || {1b0, cmd_pos} len) begin cmd_err 1b1; state S_END; end else if ({1b0, cmd_pos} len) begin mem[len] cmd_din; len len 1b1; state S_END; end else begin pos_r cmd_pos; data_r cmd_din; ptr len[AW-1:0]; dir 1b0; state S_MOVE; end end C_DELETE: begin if (len 0 || {1b0, cmd_pos} len) begin cmd_err 1b1; state S_END; end else if (len 1) begin len 0; state S_END; end else if ({1b0, cmd_pos} len - 1b1) begin len len - 1b1; state S_END; end else begin pos_r cmd_pos; ptr cmd_pos; dir 1b1; state S_MOVE; end end C_GET: begin if ({1b0, cmd_pos} len) begin cmd_err 1b1; end else begin cmd_dout mem[cmd_pos]; end state S_END; end C_FIND: begin if (len 0) begin cmd_err 1b1; state S_END; end else begin data_r cmd_din; ptr 0; state S_SCAN; end end C_CLEAR: begin len 0; state S_END; end default: state S_END; endcase end end S_MOVE: begin if (dir 1b0) begin mem[ptr] mem[ptr - 1b1]; if (ptr pos_r 1b1) state S_WR; else ptr ptr - 1b1; end else begin mem[ptr] mem[ptr 1b1]; if (ptr len[AW-1:0] - 2d2) begin len len - 1b1; state S_END; end else begin ptr ptr 1b1; end end end S_WR: begin mem[pos_r] data_r; len len 1b1; state S_END; end S_SCAN: begin if (mem[ptr] data_r) begin cmd_dout ptr; state S_END; end else if (ptr len[AW-1:0] - 1b1) begin cmd_err 1b1; state S_END; end else begin ptr ptr 1b1; end end S_END: begin cmd_done 1b1; state S_IDLE; end default: state S_IDLE; endcase end end这段代码里有几处是我刻意写的值得单独点出来。len[AW-1:0]这种截位写法是因为len比ptr宽一位比较时要把高位切掉更稳妥的写法是显式扩展ptr去比两种都行但截位在某些综合工具里更省一点逻辑。mem[ptr] mem[ptr-1]这种变量索引的读写综合工具会自动推断出合适的存储器或触发器阵列不需要手写原语。S_WR单独拆出来而不是在S_MOVE最后一拍直接写是为了避免同一拍对同一个地址既读又写导致的语义混乱——虽然最后写的是不同地址但把写操作单独放一拍波形上非常清楚出问题一眼能看出来。4. 仿真验证怎么做得像样4.1 参考模型让软件替你算答案硬件顺序表最怕的是“仿真看起来对”因为随机操作下边界条件极多。我的做法是永远配一个软件参考模型用Verilog数组模拟同一张表同一个随机操作序列同时打到DUT和参考模型上每一步比对长度、比对指定位置的值。reg [31:0] ref_mem [0:63]; integer ref_len; task ref_do(input [2:0] c, input [5:0] p, input [31:0] d); integer i; begin case (c) C_PUSH: if (ref_len 64) begin ref_mem[ref_len] d; ref_len ref_len 1; end C_INSERT: if (ref_len 64 p ref_len) begin for (i ref_len; i p; i i - 1) ref_mem[i] ref_mem[i-1]; ref_mem[p] d; ref_len ref_len 1; end C_DELETE: if (ref_len 0 p ref_len) begin for (i p; i ref_len - 1; i i 1) ref_mem[i] ref_mem[i1]; ref_len ref_len - 1; end C_CLEAR: ref_len 0; endcase end endtask注意参考模型里的循环方向和RTL必须相反软件里从后往前搬写的是ref_mem[i] ref_mem[i-1]RTL里也是这个方向但因为软件是顺序执行从前往后写也不会覆盖出错。所以参考模型其实验证不了搬移方向对不对——它只验证“最终结果对不对”。搬移方向写反了RTL结果是错的参考模型结果是“软件语义上”对的一比就露馅。反过来说如果RTL也写成了从前往后搬那它算出来的结果和参考模型就对不上一样能抓到。所以配参考模型这件事不管方向对不对都能兜住值得做。随机测试我一般跑500到2000次操作权重设置上让“插入”和“删除”占大头接近满和接近空的时候命中率更高。另外专门写一段定向测试空表删除、满表插入、位置0插入、位置len插入、删最后一个、连续删到空再插回去。这六个用例能覆盖90%的边界错误。4.2 波形上到底看什么仿真跑通不等于没问题波形我至少要看四个点。第一看cmd_done是不是严格的单拍脉冲如果发现它连着两拍高说明S_END状态停留了两个周期大概率是cmd_done的默认清零被某个分支覆盖了。第二看插入操作里ptr的递减轨迹从len一路减到pos1中间不能跳变、不能停在中间某值不动。第三看删除操作完成时len是不是在最后一拍才减如果提前减了ptr的终止条件会算错。第四看连续命令之间cmd_valid是否在cmd_done之后才重新拉高如果外部模块在done之前就发下一条状态机还在忙命令会被吞掉。第四点我踩过。当时一个上层模块看到busy其实就是state ! S_IDLE就等了但它等的是一个打拍后的busy信号比真实状态晚一拍于是在最后一次搬移那一拍就把新命令送上来了状态机正好在S_WR命令丢了表现为“偶尔丢一次操作”跑几千次才出现一次查了很久。后来统一改成“等done脉冲”问题消失。这个教训就是多拍操作的模块对外只暴露一个结束信号不要让调用方去猜内部状态。4.3 综合结果长什么样以DATA_W32、MAX_LEN64的寄存器阵列版本为例资源大概是这样的存储体本身2048个触发器搬移路径每比特需要一个二选一加上变量索引译码LUT大约在1500到3000之间具体看综合工具的优化力度和状态机编码方式。这个规模在中小器件上是可以接受的但如果MAX_LEN提到256触发器变成8192个译码树深度也跟着涨时序就会开始吃紧。时序上最关键的一条路径是mem[ptr] mem[ptr-1]这条读改写路径ptr是变量读要经过一整棵多路选择树写又要经过地址译码两头都在同一拍里完成。MAX_LEN64的时候这条路径通常还能撑住深度到128、256就建议改块RAM方案把搬移拆成“读一拍、写一拍”两个状态用两拍换时序余量。块RAM方案下有个必须提前想清楚的事同步读有一拍延迟。你给出地址数据下一拍才出来。搬移循环里如果直接写mem[ptr] mem[ptr-1]综合工具会推断成“读改写同一地址”块RAM做不到这种零延迟的读改写要么报错要么插入额外逻辑。正确写法是拆成两个状态S_RD发读地址、锁存读数据S_WR用锁存的数据写目标地址。这样每个元素搬移要两拍64项的表最坏情况搬移128拍延迟明显变长但资源省下来了。选哪个还是回到第1节那张表。5. 踩坑记录与常见问题速查5.1 第一个坑搬移方向反了数据被静默吞掉症状很有意思单次插入到表中间仿真能过因为表里当时只有两三个元素从头往后搬恰好也没覆盖一旦元素多起来插入后表尾出现重复值中间某个值消失了。这种bug最难查因为它不是崩是“错得很有规律”。我第一次遇到时盯着波形看了半天没看出问题最后是打印整个mem数组的内容才发现的。排查方法很土但有效在插入操作完成的下一拍把整个mem数组$display出来和参考模型比对。如果发现从pos到len-1这一段出现了“某个值重复两次、某个值消失”那百分之百是方向问题。定位之后改一行就好但前提是你得知道往哪个方向改。5.2 第二个坑块RAM读延迟导致的off-by-one换成块RAM之后读数据晚一拍。原本S_SCAN里写的是“这一拍比较mem[ptr]和key不等就ptr加一”结果比较的其实是上一拍地址的数据扫描整体错位一格最后一个元素永远比不到查找最后一个元素总是返回“未找到”。修法是把扫描拆成“发地址—下一拍比较”的流水或者干脆用寄存器阵列版本的思路加一个rd_valid打拍信号只有rd_valid有效时才做比较。后一种更好维护代价是多一个触发器和一个状态位。这个坑的通用教训是只要存储体是同步读的任何“变量地址访问”的地方都要多问一句“我拿到的是哪个地址的数据”。5.3 第三个坑len位宽不够满表瞬间归零前面提过len必须是$clog2(MAX_LEN1)位。6位存64会回绕成0而0意味着“表空”。表现出来就是写到第64个元素表突然变空第65次插入又从头开始写。仿真如果只测50次操作永远测不出来。防范手段很简单在断言里加一条插入完成后检查len是否为0或者是否比操作前小如果是就报错。这一条断言值一晚上调试时间。5.4 第四个坑复位策略和仿真综合不一致mem数组到底要不要复位我的建议是不复位。2048个触发器全接复位综合出来复位网络会很重而且块RAM根本没法逐位复位。但这就带来一个问题仿真开始时mem里是X如果代码里读了一个没写过的位置仿真出X综合后是随机值行为可能不一致。解决办法是把“读未初始化位置”这件事从设计上禁掉所有读操作前必须判pos len而len初始为0天然保证不会读到未写区域。这样mem不需要复位仿真也不会出X。这条规则我在所有带存储体的模块里都执行效果很好。5.5 常见问题速查表现象可能原因排查动作处理方式插入后表尾重复、中间丢失搬移方向写反打印整个数组与参考模型比对插入改为从len递减删除改为从pos递增查找最后一个元素总失败同步读延迟未补偿检查比较时的地址与数据是否同拍加读有效打拍或拆成两状态满表后长度为0len位宽不足检查$clog2(MAX_LEN1)加宽一位空表删除偶发乱删len-1无符号下溢看len0时的比较表达式先判空再走流程状态机卡死不返回扫描终止条件永远不满足看ptr是否停下、len是否合法提前挡掉len0边界单独处理done脉冲出现两拍某分支漏清cmd_done波形看done宽度改为默认清零单一出口连续命令偶尔丢失上层在done前发下一条看cmd_valid与state关系统一等done再发综合后资源远超预期数组被展开成寄存器看综合报告的存储器映射改访问方式或换块RAM5.6 几条不那么技术但很管用的经验第一先写单周期的“笨版本”再优化。我最早那版就是所有搬移用for循环一拍完成慢是慢但逻辑一眼能看懂仿真跑通之后再改成多周期对比结果一致就说明优化没错。反过来先写复杂版本出了错连基准都没有。第二命令编码留一个NOP。状态机的default分支指向NOP或者直接报错调试时可以在不改变代码的情况下插一条空命令看时序非常方便。第三把长度和空满标志引出来观察。调试时不用抓内部信号直接看list_len、list_empty、list_full就能判断状态机走到哪一步了省很多时间。6. 想再快一点几种优化路子6.1 提升搬移吞吐的三种做法最直接的是单周期并行搬移把搬移写成一个for循环integer k; always (posedge clk) begin if (ins_en) begin for (k MAX_LEN-1; k 0; k k - 1) if (k ins_pos k len) mem[k] mem[k-1]; mem[ins_pos] ins_data; end end综合工具会展开成MAX_LEN个并行的二选一插入一次只要一拍。代价是面积64项的时候还算能接受128项以上基本放弃。这个写法还有个隐患循环是组合展开的展开后的路径可能很长时序报告要看清楚。第二种是分段并行一次搬4个或8个元素用计数器控制搬几轮。面积和延迟折中实现上要注意每段的起止地址对齐别把同一段搬两次。这个方案我在一个容量256的槽位表里用过一次搬8个插入延迟从平均128拍降到16拍资源只多了不到两成。第三种是留空洞不做连续搬移插入时直接找个空槽放进去用一张位图记录哪些槽有效读取时按位图过滤。这实际上已经不是严格的顺序表了但对外接口可以伪装成顺序表代价是遍历时要跳过空洞而且“第k个元素”不再是O(1)。这种方案适合删除远多于“按位置访问”的场景。6.2 查找加速从串行扫描到并行比较按值查找在串行扫描下最坏要len拍。如果查找是热点操作可以一次比较多个integer j; always (*) begin hit_any 1b0; hit_idx 0; for (j MAX_LEN-1; j 0; j j - 1) begin if (j len mem[j] key) begin hit_any 1b1; hit_idx j[AW-1:0]; end end end倒着遍历赋值最后留下的就是最小下标一拍出结果。代价是MAX_LEN个比较器加一棵优先编码树容量大了面积吃不消。折中的做法是分组每4个一组并行比组间串行延迟降到四分之一面积只涨四倍比较器。再往上就是CAM内容寻址存储器的思路了写入即建立匹配关系查找一拍完成。但那已经超出顺序表的范畴属于另一个话题。6.3 从这个模块能长出的东西这张表写顺手之后栈和队列几乎是白送的。栈就是只允许在len处插入、len-1处删除的顺序表把pos固定住搬移逻辑直接删掉一个周期压入弹出。队列是头删尾插头删要搬移所以更常见的做法是环形缓冲加读写指针把“搬移”这个动作彻底消灭掉。再往后是带优先级的插入插入位置不再是外部给的而是根据优先级扫描出来的把查找和插入串起来就是优先级队列。我在模拟项目X里的调度器就是这么搭的先扫描找到第一个优先级低于待插入项的位置再从这个位置开始搬移。两个状态机串起来代码量不大但把顺序表的两个基本操作都用上了。至于链表硬件里做链表要额外维护空闲块管理和指针域复杂度比顺序表高一个量级只在“插入删除极频繁、容量很大、位置访问不重要”的时候才值得。我一般的判断是容量不超过256、按位置访问是常态就用顺序表别折腾。我个人在实际操作中的体会是这类“硬件版数据结构”最大的价值不在于性能而在于它逼着你把每一个边界、每一拍时序、每一块面积都想清楚。软件里一个数组越界可能只是段错误硬件里它就是一个永远查不出来的偶发错误。写完这张表再去写更复杂的状态机心里会踏实很多。